대기열 시스템 구상하기

이번에 티켓 예매 서비스를 주제로 프로젝트를 진행하게 되었다. 티케팅의 경우 대규모 트래픽이 몰릴 수 있는 이벤트이기 때문에 이를 안정적으로 처리할 대기열 시스템을 구상해보기로 한다.

 

0. 요구 사항

요구사항은 크게 2가지로 정리할 수 있다.

• 대규모 트래픽 상황에도 사용자들에게 안정적으로 순서를 보장시킬 수 있어야 한다.
• 사용자가 실시간으로 대기열 상황을 확인할 수 있어야 한다.

각 요구사항을 만족시킬 기술들에 대해 고려해보자.

 

---

1. 사용자 순서 보장

1.1. Kafka

 

Kafka는 대규모 데이터 스트리밍을 위한 분산 메시징 시스템으로 높은 처리량과 낮은 지연 시간을 제공하여 대량의 데이터를 처리할 수 있다. 또한 단일 파티션 사용 시에 메시지의 순서를 보장 받을 수 있고, 메시지를 디스크에 저장하기 때문에 시스템 장애 시에도 데이터 손실을 방지할 수 있다. 

 

1.2. Redis

 

Redis는 인메모리 특성으로 인해 빠른 읽기/쓰기 기능을 제공한다.
싱글 스레드 기반으로서 모든 연산을 Atomic하게 처리하기 때문에 동시성 문제를 피할 수 있다. 특히 Sorted Set 자료구조를 이용하면 각 사용자들을 입장 순서에 따라 자동으로 정렬할 수 있다.

 

선택 - Redis

상대적으로 익숙한 Redis를 사용하여 구현해보기로 한다. 사전 조사를 통해 꽤 많은 곳에서 선착순 이벤트에 Redis를 사용하고 있다는 것을 확인하였다. 보장된 성능과 쉬운 개발 난이도에 따라 Redis를 선택하기로 한다.

 

---

2. 대기열 상태 확인

2.1. Polling

클라이언트가 주기적으로 서버에 요청을 보내 데이터를 확인한다. 구현이 간단하지만 요청 주기에 따라 실시간성이 떨어질 수 있다.

 

2.2. WebSocket

클라이언트와 서버 간의 상시 연결을 유지하여 양방향 통신을 가능하게 한다. 핸드쉐이크 과정 이후에는 데이터 전송 시 오버헤드가 적어 리소스를 효율적으로 사용할 수 있다.

 

2.3. SSE

서버가 클라이언트에게 단방향으로 실시간 데이터를 전송하는 방식이다. 클라이언트는 서버에 연결을 유지하고, 서버는 데이터를 푸시할 수 있다.

 

선택 - Polling

WebSocket과 SSE의 경우 한번 연결이 이뤄지면 데이터의 전송에 드는 비용이 Polling 보다 적다는 장점이 있지만, 대기열에 존재하는 사용자들의 수가 빠르게 변할 시에 너무 많은 IO 비용이 발생할 것으로 우려된다. 따라서 요청 주기를 유연하게 수정할 수 있는  Polling을 사용하기로 한다.

 

---

3. 대기열 구현 메커니즘

대기열 구현 메커니즘은 크게 2가지로 정리 할 수 있다.

•  은행 창구 방식: 작업열에서 한 명이 나가면 대기열에서 제일 앞에 있는 한 명이 작업열로 이동
• 놀이 공원 방식: 정해진 시간에 맞춰 일정 인원을 대기열에서 작업열로 이동

놀이 공원 방식은 작업을 빠르게 마치더라도, 대기열에서 정해진 시간까지 계속 기다려야 한다는 점에서 비효율적이다. 이에 유동적으로 사용자들을 이동시켜 대기 시간을 줄일 수 있는 은행 창구 방식을 기반으로 구현하도록 한다.

 

---

4. 대기열 시퀀스 다이어그램

요구사항에 따라 구상한 시퀀스는 다음과 같다.

 

 

---

5. API 시간 복잡도

Redis의 Sorted Set은 O(log(N))의 시간 복잡도를, Key-Value 구조는 O(1)로 낮은 시간 복잡도를 가진다. 이에 정리한 각 API에서의 시간 복잡도는 다음과 같다.

5.1. 대기열 진입 API

- 작업열 카운터 조회: O(1)
- 대기열 진입: O(log(N))

- 작업열 카운터 조회: O(1)
- 작업열 진입: O(1)

5.2. 대기열 상태 확인 API

- 대기열 조회: O(log(N))

- 작업열 조회: O(1)

 

이를 바탕으로 많은 사용자들의 요청을 빠르게 처리할 수 있을 것으로 기대한다.