Clustered Index 를 활용한 Full Table Scan 없는 N 명 추첨 알고리즘

N명 추첨

개발하는 과정에서 이벤트 참가자들 중 당첨자를 추첨해야하는 상황이 발생했다. 추첨이라는 메서드는 이벤트 당 1 번만 발생하는 메서드이다. 처음에는 성능을 생각하지 않고 작성하였지만 이벤트 참여자가 1만명 이상이라면 거의 full table scan 을 통해서 1만 이상의 데이터를 가져와 계산하게 된다. 하지만 메모리 상에서 1만 이상의 데이터의 가중치를 계산하는 과정은 매우 위험하다고 생각한다.

실제 Event_user 테이블 기준

 

Data Type	Number of Fields
BIGINT	3
INT	3
DOUBLE	4
BIT(1)	2
DATETIME(6)	2
JSON	1
VARCHAR(255)	2

 

대략 1 객체당 700 바이트 크기이다. 대략 150만개의 객체가 1GB 용량을 차지한다. 결국 이벤트 참가자가 많아질 수록 Full Table Scan 은 위험할 수 있다는 말을 하고 싶다.

1차 추첨

본 서비스에서는 N 명을 추첨하기 위해 모든 이벤트 참가자를 조회하는 것이 아니라 M 배수, NM명을 데이터베이스에서 추출한다.

    @Query("SELECT MAX(eu.id) FROM EventUser eu WHERE eu.subEvent.id = :subEventId")
    long findMaxBySubEventId(Long subEventId);

1. 해당 쿼리를 통해서 추첨하고자하는 SubEventId 를 가진 Max 값 EventUserId 를 찾아낸다.
2. 이후 랜덤 함수를 통해서 1 ~ Max 값 사이에서 랜덤값을 추출한다.
3. 랜덤값 id 값 이상의 NM명을 추출해낸다.

    @Query(value = "SELECT * " +
            "FROM event_users as eu " +
            "WHERE eu.sub_event_id = :subEventId AND eu.id >= :rand " +
            "LIMIT :limit", nativeQuery = true)
    List<EventUser> findNByRand(long subEventId, int rand, int limit);

 

50만건의 EventUser 조회

Step	랜덤 값이 없는 경우	랜덤 값 이상 id 값을 조회하는 경우
starting	0.000088	0.000092
Executing hook on transaction	0.000004	0.000004
starting	0.000009	0.000007
checking permissions	0.000005	0.000005
Opening tables	0.000046	0.000044
init	0.000006	0.000006
System lock	0.000009	0.000009
optimizing	0.000013	0.000014
statistics	0.001714	0.000184
preparing	0.000044	0.000038
explaining	0.000051	0.000052
end	0.000005	0.000004
query end	0.000004	0.000004
waiting for handler commit	0.000010	0.000008
closing tables	0.000010	0.000009
freeing items	0.000043	0.000043
cleaning up	0.000009	0.000014
Total Time	0.002070	0.000533

 

경우에 따라서 랜덤값이 있는 경우 조회 시간을 크게 줄일 수 있다.

 

3-1. 만약 랜덤값이 MAX 와 비슷해 NM 명이 추출되지 않았을 경우 id 1번부터 부족한 인원을 다시 추출해낸다.

2차 추첨

4. 이후 NM 명의 가중치를 실제 계산해 N 명을 추출해낸다.

이때는 1만 건의 데이터가 아닌 NM 개의 레코드만 메모리에 올라가는 것을 보장하기에 훨씬 안정적이라고 할 수 있다.

결론

1. 1차에 무작위로 NM 명을 뽑고 2차에서 N 명을 가중치까지 계산해서 추첨해낸다.
2. 추첨이라는 단어의 본질은 무작위이다. 게임 점수 등은 가중치일 뿐 무작위가 추첨 방식의 근간이다.
3. 따라서 가중치가 높은 사람이 1차 추첨에서 제외될 수 있는 것은 무작위성에 위배되지 않는다고 생각한다.