이희준 ‐ 추첨 이벤트

주요 로직이 어떻게 되는가?

추첨 이벤트 로직은 AccSumBasedWinnerPicker에 구현되어 있다.

현재 추첨 이벤트는 누적 합 알고리즘을 바탕으로 2가지 방식을 혼용하여 사용하고 있다.

누적 합 알고리즘의 개략적인 동작 방식은 다음과 같다.

1. 계산된 점수에 대해 누적 합 배열을 구성한다.
2. 무작위로 하나의 구간 내 하나의 값을 선택한다.
3. Binary Search로 해당 값이 속한 구간을 찾는다.
4. 해당 구간의 사용자는 당첨자가 된다.

두 방식은 위 로직을 기반으로 서로 다른 특징의 작업을 수행한다.

1. pickMany: 당첨자를 뽑을 때마다 누적합 배열을 갱신한다.
2. pickManyUsingSet: 최초 한번 누적합 배열을 생성하고 무작위로 유저를 선택하되, Set 자료구조를 이용하여 중복 당첨되는 경우를 막는다.

유저의 수를 N, 뽑는 수를 M이라고 할 때, 두 알고리즘은 대략 다음과 같은 시간 복잡도를 가진다.

1. pickMany: M * (N + logN) = 테이블 생성 + 뽑기 M회 반복
2. pickManyUsingSet: N + (M + C) * logN = 테이블 1회 생성 + 뽑기 M + C회 반복

충돌이 최소한으로 발생하는 경우, pickManyUsingSet 방식이 pickMany에 비해 압도적으로 유리하다. MlogN < MN이기 때문이다.

그러나 당첨자 수 M이 유저 수 N에 근접하거나 더 커지면 충돌 C가 급격하게 증가(무한대로 발산)하므로, 해당 상황에서는 사용할 수 없는 문제가 있다.

따라서, 현재 팀은 두 알고리즘을 혼용해서 사용하고 있다. 대부분의 경우 M은 N에 비해 훨씬 작아 pickManyUsingSet을 사용하지만, 두 값이 비슷해지는 상황에서는 pickMany를 사용하여 시간은 오래 걸리더라도 작업을 처리할 수 있도록 구현했다.

fallback은 어떻게 구현했나?

관련 코드

위와 같이 문제를 예방하기 위해 노력하더라도, 실제 상황에서는 작업이 무한히 진행되는 불상사가 생길지도 모른다. 작업이 CompletableFuture에 의해 처리되고 있으므로, 24시간의 Timeout을 둬서 하루 안에 종료되지 않은 작업은 강제로 종료되도록 구현했다.

왜 @Async를 사용하면서 Executor을 등록하지 않았나?

관련 라인

추첨 작업은 시간이 오래 걸릴 수 있으므로, 내부적으로 @Async 어노테이션 및 CompletableFuture을 이용해서 작업을 비동기로 처리하도록 구현하고 있다. 인터넷의 자료들을 찾아보다 보면 @Async는 별도의 Executor을 등록하지 않았을 때 SimpleAsyncTaskExecutor을 사용해 다수의 요청이 들어오게 되면 스레드를 무한히 만들 위험이 있다고 알려져 있지만, 사실 Spring Boot는 내부적으로 ThreadPoolTaskExecutor을 Configuration으로 등록하므로, 걱정할 필요가 없다고 한다. 스레드 풀 관련 설정은 최적화하지 않으면 오히려 악영향을 주기 때문에, Spring boot에서 제공하는 기본 값을 사용하되, 문제가 있다면 변경하기로 했다.

• 참고한 글: https://xxeol.tistory.com/44#%EC%8B%A4%ED%97%98%ED%95%98%EA%B8%B0-1

중복 이벤트 추첨은 어떻게 막았나?

일단 이벤트 추첨 작업이 완료되면 낙장불입의 원칙이 지켜져야 한다. 관리자가 임의로 추첨 로직을 한번 더 처리하여 추첨 인원을 변경하게 되면, 기존에 당첨된 사용자들에게 손해를 입힐 수 있기 때문이다.

이러한 낙장불입의 원칙을 지키려면 이벤트 추첨이 한번 이상 완료되어서는 안된다. 모든 시간대에서 동시에 추첨이 진행되는 상황을 방지하고, 추첨 된 이벤트를 다시 추첨할 수 없게 하기 위해 나는 mysql + redis을 이용했다.

1. 이벤트 추첨이 진행되었는지 검사한다. 추첨 여부 정보는 DB에 저장되어 있다.
2. 이벤트가 추첨이 아직 진행되지 않았다면, 현재 이벤트 추첨이 진행 중인지 검사한다. redis에서 increment는 키가 없을 때 1을 반환한다. 특정 이벤트 키를 이용하여 increment를 수행한 후 반환된 키 값이 1이라면 추첨이 진행 중이지 않은 동시에 추첨 상태에 돌입한다. redis는 single thread 기반으로 동작하므로 동시에 increment를 수행할 수 없기 때문에 반드시 하나의 요청이 추첨 상태에 돌입하는 것을 보장한다.
3. 추첨이 정상적으로 진행되었다면 추첨 이벤트의 상태를 "추첨 완료"로 변경한다.
4. 모든 작업을 마친 후 redis 키를 초기화하여 다른 이벤트도 진입할 수 있게 풀어준다.

만약 3과 4의 순서를 변경하게 되면 "진행 중" 플래그가 사라진 후, "추첨 완료" 플래그를 설정하기 전 짧은 시간 동안 draw 요청이 들어오면 완료된 추첨이 다시 처리될 수 있다. 따라서 "추첨 완료" 플래그를 mysql 상에 설정한 후에 "진행 중" 플래그를 설정해야 한다.