Tworld 대기열은 어떤식으로 구현되어있을까?

최근 SKT 해킹 사건으로 인해 유심 보호 및 교체 신청이 급증하면서 Tworld 접속 시 대기열이 발생했다.
이에 따라 Tworld의 대기열 시스템이 어떤 방식으로 구현되어 있는지 추측해보려고 한다.

 

---

흐름

 

1. 대기열 큐 생성

2. SSE 연결

3. 대기열 큐 상태 조회

---

 

대기열 큐 생성

 

https://care.tworld.co.kr/api/queue

{
    "ticketId": "535357ec-2a08-4164-b245-5cbcf3511015",
    "usersInQueue": 45396,
    "nextPolling": 10,
    "status": "IN_WAIT_QUEUE"
}

HTTP/1.1 200 OK
...
set-cookie: WEB_SESSION=974c2d4a-6a69-45cd-910c-2e231abcb598; Path=/; Secure; HTTPOnly; SameSite=None
Content-Encoding: gzip
Set-Cookie: TS01b2c5b7=01621d42d1551833aaba996f542c87592e8de47b9ae220ec6171b5e28ece742fbe1f3c1c140973eb3093160ed87f4b59f00c91080b01bf1a4fc7a1fd1e909fca40422cda39; Path=/; 
Transfer-Encoding: chunked

 

처음 대기열에 요청을 보내면, 현재 순번과 함께 쿠키 생성 헤더가 반환됩니다.
이때 ticketId, nextPolling는 실제로 사용되지 않으며, 대기 중인 사용자는 WEB_SESSION 쿠키를 통해 구분됩니다.

---

 

SSE 연결

 

https://care.tworld.co.kr/api/queue/listen

data:CONNECTED

data:REMAINS 44746

...

data:REMAINS 696

data:READY

 

이후 SSE 연결을 통해 주기적으로 자신의 순번을 전달받으며, 순번이 도달하면 READY 응답을 받게 됩니다.

 

---

 

대기열 큐 상태 조회

 

https://care.tworld.co.kr/api/queue

{
    "status": "READY"
}

 

이후 상태를 조회하여 READY 응답을 받으면, 정상적으로 서비스를 이용할 수 있습니다.

대기열 정보는 쿠키(UUID)와 세션에 저장되므로, 세션이 유효한 경우에는 새로고침을 하더라도 SSE 연결 없이 재접속이 가능합니다.

 

---

 

상세 구현 추측

 

세션 저장소

Map<세션 아이디, 세션 정보> sessions = new ConcurrentHashMap<>();

세선 정보 {
	long expireTime; //대기 만료 시간
	boolean isWaiting; //대기 큐를 통과 했는지
}

 

대기큐

Queue<세션 아이디> queue = new ConcurrentLinkedQueue<>();

 

아마도 Redis에는 위와 같은 형식으로 데이터가 저장되어 있을 것으로 예상됩니다.
이후 동시에 처리할 수 있는 요청 수에 따라, 스케줄러가 큐에서 순차적으로 사용자를 꺼내고 세션 저장소의 상태를 적절히 변경하는 작업이 이루어집니다.

 

시간 복잡도

대기열 큐 생성 : O(1)

1. usersInQueue 조회 [Redis Sorted Set의 경우 ZCARD O(1)]

2. 세션 조회 및 등록 [O(1)]

 

SSE 연결 현재 대기열 순위 조회 : O(Nlog(N))

1. 현재 대기열 순위 조회 [Redis Sorted Set의 경우 ZRANK O(log(N))]

현재 대기중인 N명에게 대기열 정보를 SSE로 제공해야하기때문에 전체적으로는 O(Nlog(N))의 시간복잡도를 가지게 됩니다.

 

대기열 큐 상태 조회 : O(1)

1. 세션 조회 [O(1)]

 

스케줄러 작업 : O(N)

1. Queue에서 사용자 제거 [O(1)]

2. 사용자 세션 정보를 변경 [O(1)]
그러나 스케줄러를 통해 한 번에 N명의 사용자를 처리하게 되므로 전체적으로는 O(N)의 시간 복잡도를 가지게 됩니다.

 

문제

대기열 서비스에서 가장 빈번하게 일어나는 작업이 SSE 연결 현재 대기열 순위 조회, 스케줄러 작업 인데,
두 작업이 가장 시간복잡도가 높기 때문에 개선을 해보면 좋을것같습니다.

 

상세 구현 추측 개선

 

세션 저장소

Map<세션 아이디,세션 정보> sessions = new ConcurrentHashMap<>();

세선 정보 {
	long expireTime; //대기 만료 시간
	boolean isWaiting; //대기 큐를 통과 했는지
	long ticketNumber; //사용자 번호
}

큐

AtomicLong ticketNumber; // 사용자에게 부여하는 번호, 계속 증가
AtomicLong allowedNumber; // 접근 가능한 사용자 번호, 계속 증가

 

사용자가 큐에 접근하면 ticketNumber를 증가시킨 뒤 해당 값을 반환하며, 이후 ticketNumber가 allowedNumber 이하인 경우에만 접근을 허용한다.

 

시간 복잡도

 

대기열 큐 생성 : O(1)

1. ticketNumber 조회 [Redis INCR O(1)]

2. 세션 조회 및 등록 [O(1)]

 

SSE 연결 현재 대기열 순위 조회 : O(N)

1. allowedNumber 조회 [O(1)]

2. 세션 ticketNumber 조회 [O(1)]

3. 만약 ticketNumber-allowedNumber<=0 이라면 세션 상태 변경 [O(1)]

현재 대기 순번은 ticketNumber-allowedNumber

현재 대기중인 N명에게 대기열 정보를 SSE로 제공해야하기때문에 전체적으로는 O(N)의 시간복잡도를 가지게 된다.

 

대기열 큐 상태 조회 : O(1)

1. 세션 조회 [O(1)]

 

스케줄러 작업 : O(1)

1. allowedNumber 증가 [O(1)]

 

 

결론

위와 같이 구현하면 기존 방식에 비해 시간 복잡도를 크게 개선할 수 있습니다.

추가적으로 고려해야 할 점은 ticketNumber와 allowedNumber가 계속 증가하기 때문에 오버플로우가 발생할 수 있습니다.

하지만 long 타입의 범위를 감안하면, 며칠 동안 대기열이 유지되더라도 충분히 감당할 수 있을 것으로 예상됩니다.
이후 대기열이 줄어들어 상황이 안정되면, 기존 세션을 모두 허용한 뒤 ticketNumber와 allowedNumber를 초기화하는 과정을 추가하면 보다 안정적인 운영이 가능할 것으로 보입니다.

 

 

참고

https://youtu.be/3pO9GJ4zndE?si=WcyEjFtJs3-4sauH