대기열 시스템 다양한 설계 방법 탐구 (feat. 레디스와 카프카를 이용한 O(1) 최적화)

이 글에 대해서

항해 플러스 백엔드 5기 과정을 수료하며 대기열 기반의 예약 시스템을 구현했습니다.

 

본 글은 해당 프로젝트를 진행하며 고민하고 결정했던 내용을 다룹니다.

 

주요 내용으로는 은행 창구 방식과 놀이 공원 방식을 포함한 대기열 처리 메커니즘의 비교, 대기 토큰 관리 방법, 활성 토큰을 관리하는 다양한 방식(상태 기반, HashSet 기반, Counter 기반, Kafka 기반), 그리고 이를 개선하기 위한 방법을 다룹니다. 각 방식의 아키텍처, 처리 로직, 장단점을 상세히 설명하며, 최종적으로 Kafka, Redis를 활용한 개선 방안을 제시합니다.

 

소스 코드는 여기에서 보실 수 있습니다.

 

---

개요

대기열 큐를 구현하는 방식으로 두 가지 메커니즘을 고려해볼 수 있다. 첫 번째는 은행 창구 방식이고 두 번째는 놀이 공원 방식이다. 은행 창구 방식은 한 명이 처리열에서 빠져나가면 한 명이 대기열에 들어오는 방식이며, 놀이 공원 방식은 일정 시간 동안 n명을 들여보내고 m 시간이 지나면 자동으로 빠져나가는 방식이다.

은행 창구 방식

은행 창구 방식은 실제 은행 창구에서 사람들이 줄을 서서 기다리는 것과 유사하다. 이 방식에서는 한 명이 처리열에서 빠져나갈 때마다 대기열에서 한 명이 들어온다. 이를 통해 현재 처리 중인 인원 수를 정확히 카운팅하는 것이 중요하다. 예를 들어, 은행 창구 방식에서는 다음과 같은 로직이 필요하다:

• 변수 정의:
  • n: 현재 처리 중인 사람 수
  • m: 대기열에서 기다리는 사람 수
• 처리 로직:
  1. 한 명이 처리열에서 빠져나가면(n--), 대기열에서 한 명이 처리열로 이동(m--, n++).
  2. 이를 통해 전체 서버의 가용량 대비 현재 몇 명을 수용할 수 있는지 파악.
• 예시:
  • 현재 처리 중인 인원이 5명(n=5)이고, 대기열에 10명(m=10)이 있다면:
    1. 한 명이 처리 완료되면(n=4).
    2. 대기열에서 한 명이 처리열로 이동(m=9, n=5).

놀이 공원 방식

놀이 공원 방식은 놀이 공원의 특정 놀이기구에 사람들이 일정 시간 동안 타고 있다가, 일정 시간이 지나면 자동으로 빠져나가는 것과 유사하다. 이 방식에서는 일정 시간 동안 n명을 들여보내고, m 시간이 지나면 자동으로 빠져나가게 된다.

• 변수 정의:
  • n: 일정 시간에 입장한 사람 수
  • m: 일정 시간 후 자동으로 빠져나가는 시간
• 처리 로직:
  1. 일정 시간마다 n명을 들여보낸다.
  2. m 시간이 지나면, 해당 유저들은 자동으로 빠져나가며 새로운 사이클이 시작된다.
• 예시:
  • 30분마다 20명(n=20)이 입장하고, 60분(m=60)이 지나면 자동으로 퇴장.
  • 예를 들어, 9:00에 20명이 입장하면 9:30에 다시 20명이 입장하지만, 9:00에 입장한 20명은 10:00에 퇴장.

이와 같이, 은행 창구 방식과 놀이 공원 방식은 각각의 특징과 처리 방식을 가지고 있다.

 

본 글의 목적은 은행 창구 방식 에서의 다양한 구현 방식을 탐구하고, 그 장단점들을 분석하여 최적의 방법을 모색하는 것이다.

0. 공통: 대기 토큰을 Sorted Set으로 관리

아키텍처

프로세스

1. 다수의 유저가 동시에 요청을 보낸다.
2. 각 유저를 토큰화하여 Redis Sorted Set에 저장한다.

1. 활성 토큰을 상태로 관리하는 방식

아키텍처

프로세스

1. 다수의 유저가 동시에 요청을 보낸다.
2. 개별 건에 대해서, Active 유저를 key-value 저장소에서 전체 조회하여 현재 활성화 할 수 있는 유저 수를 계수한다. O(N)
3. 활성화가 가능한 경우
   1. 해당 유저를 Active 상태를 포함하여 토큰화한다. (e.g. active-xxxxx)
   2. 해당 토큰을 key-value 저장소에 저장한다. O(1)
4. 활성화가 불가능한 경우
   1. 해당 유저를 Waiting 상태를 포함하여 토큰화한다. (e.g. waiting-xxxxx)
   2. 해당 토큰을 Sorted Set에 저장한다. O(logN)

장점

• 로직이 아주 심플하다.
• 별도의 스케줄링 작업이 필요하지 않다.

단점

• 로직의 결합도가 너무 높다: 확장에 유연할까? 부하 분산이 쉬울까?
• 대기열 인입 요청은 본 시스템 중 부하가 가장 큰 구간이다. 해당 구간에서 너무 많은 작업을 하므로 부하가 예상된다. (key-value 저장소에서 전체 조회시 O(N))

2. 활성 토큰을 별도의 토큰으로 분리하는 방식 1: Hashset과 스케줄링을 이용한 카운트

아키텍처

프로세스

로직 1

1. 다수의 유저가 동시에 요청을 보낸다.
2. 각 유저를 토큰화하여 Redis Sorted Set에 저장한다. O(logN)

로직 2

스케줄링으로 다음과 같은 스텝을 반복한다.

1. 활성 토큰 개수를 Set size를 조회하여 확인한다. O(1)
2. 활성 토큰 개수가 임계치 미만인 경우, 즉 수용 가능한 경우
   1. 해당 개수 만큼 대기 토큰에서 인입 순으로 가져온다. O(logN + M: N은 sorted set의 크기, M은 가져오는 요수의 수)
   2. 가져온 대기 토큰을 활성 토큰으로 변환한다.
   3. 변환한 활성 토큰을 Set에 저장한다. O(logN)
   4. 변환한 활성 토큰을 만료 시간 및 기타 메타 정보를 value로 설정하여 HashSet에 저장한다.
   5. 해당하는 대기 토큰을 Sorted Set에서 제거한다. O(logN)
3. 활성 토큰 개수가 임계치 이상인 경우, 즉 수용 불가한 경우
   1. 아무런 작업을 수행하지 않는다.

로직 3

스케줄링으로 다음과 같은 스텝을 반복한다.

1. HashSet을 전체 조회한다. O(N)
2. 조회한 토큰 중 만료 시간이 지난 활성 토큰을 확인한다.
3. 만료 시간이 지난 활성 토큰에 대해서, hashset에서 제거한다. O(1)
4. 만료 시간이 지난 활성 토큰에 대해서, Set에서 제거한다. O(1)

장점

• 로직이 분산되어 확장에 용이하다.
• 유저의 대기열 인입 요청에서 부하를 감당하기 수월하다.

단점

• Set, HashSet, 두 개의 스케줄링 -> 관리 포인트가 많다.
• HashSet 전체 조회 -> O(N)의 복잡도를 가진다. (단, 비동기 작업이므로 부하 감당은 가능하다.)

3. 활성 토큰을 별도의 토큰으로 분리하는 방식 2: Counter와 Redis keyspace notification을 이용한 카운트

아키텍처

프로세스

로직 1

1. 다수의 유저가 동시에 요청을 보낸다.
2. 각 유저를 토큰화하여 Redis Sorted Set에 저장한다. O(logN)

로직 2

스케줄링으로 다음과 같은 스텝을 반복한다.

1. 활성 토큰 개수를 Counter로 조회하여 확인한다. O(1)
2. 활성 토큰 개수가 임계치 미만인 경우, 즉 수용 가능한 경우
   1. 해당 개수 만큼 대기 토큰에서 인입 순으로 가져온다. O(logN + M: N은 sorted set의 크기, M은 가져오는 요수의 수)
   2. 가져온 대기 토큰을 활성 토큰으로 변환한다.
   3. 변환한 활성 토큰을 key-value 저장소에 TTL과 함께 저장한다. O(1)
   4. 저장한 개수를 카운터에 기록한다. O(1)
   5. 해당하는 대기 토큰을 Sorted Set에서 제거한다. O(logN)
3. 활성 토큰 개수가 임계치 이상인 경우, 즉 수용 불가한 경우
   1. 아무런 작업을 수행하지 않는다.

로직 3

레디스의 keyspace notification을 이용하여 만료 시간이 지난 활성 토큰을 확인한다.

1. 레디스는 key-value 저장소 요소 중 만료 이벤트를 keyspace notification으로 발행한다. O(1)
2. 어플리케이션은 keyspace notification을 구독하여 만료 이벤트를 수신한다. O(1)
3. 만료 이벤트를 수신하고 카운터 변수를 -1을 하여 계수 현황을 동기화한다. O(1)

장점

• 로직이 분산되어 확장에 용이하다.
• 유저의 대기열 인입 요청에서 부하를 감당하기 수월하다.

단점

• 카운터라는 별도의 관리 포인트가 생긴다.
• keyspace notification을 이용한 만료 이벤트 수신에서 유실 문제가 있다. 레디스의 keyspace notification은 at least once와 같은 유실 방지 정책을 지원하지 않아 메시지의 필연적 도달을 보장하지 않는다.

4. 활성 토큰을 별도의 토큰으로 분리하는 방식 3: Counter와 kafka pub/sub 이용한 카운트

아키텍처

프로세스

로직 1

다음과 같은 로직을 WaitingQueueService가 수행한다.

1. 다수의 유저가 동시에 요청을 보낸다.
2. 각 유저를 토큰화하여 Redis Sorted Set에 저장한다. O(logN)
3. 저장한 토큰을 Kafka로 발행한다. O(1)

로직 2

다음과 같은 로직을 ActiveQueueService가 수행한다.

1. Kafka로부터 토큰을 수신한다. O(1)
2. 활성 토큰 개수를 Counter로 조회하여 확인한다. O(1)
3. 활성 토큰 개수가 임계치 미만인 경우, 즉 수용 가능한 경우
   1. 가장 최신의 토큰을 가져온다. O(1)
   2. 가져온 대기 토큰을 활성 토큰으로 변환한다.
   3. 변환한 활성 토큰을 key-value 저장소에 TTL과 함께 저장한다. O(1)
   4. 저장한 개수를 카운터에 기록한다. O(1)
   5. TTL 값을 카프카로 발행한다. O(1)

로직 3

다음과 같은 로직을 ExpirationService가 수행한다.

1. Kafka로부터 TTL 값을 수신한다. O(1)
2. TTL 값을 현재 시점 대비 계산하여 만료 여부를 확인한다.
3. 만료 시간이 된 경우
   1. 카운터를 1 차감하여 동기화한다. O(1)
   2. 카프카에 ACK로 응답하여 다음 메시지를 수신할 수 있도록 한다.
4. 만료 시간이 아닌 경우
   1. 카프카에 NACK로 응답하여 다음 메시지를 수신하지 않도록 한다.

추가 개선

이 방식에서 조금 꺼림칙한 부분은 로직 3에서 Kafka를 다루는 방식이다. ACK를 주기 전까지는 계속 retry가 반복되며, Kafka에는 계속 이벤트들이 쌓이게 된다. Kafka는 고가용성의 메시지 큐(MQ)인데, 이 용도에 맞게 Kafka가 사용되는 것인가에 대한 의문이 생긴다.

 

기존의 문제를 해결하는 그 목적 자체를 달성하면서도 이 문제를 개선해볼 수 있을까?

 

레디스를 사용해보면 어떨까? 다음과 같은 개선 방안을 탐구해보자.

개선 방안: Redis 활용

1. TTL 정보 저장:

• TTL 정보를 Redis의 SortedSet에 저장한다. SortedSet은 자동으로 rank로 정렬되기 때문에 가장 앞의 요소를 쉽게 가져올 수 있다.
• 이는 Kafka가 순서를 보장함으로써 기존 방식에서 맨 먼저 발행된 이벤트, 즉 TTL이 가장 빠른 이벤트를 컨슘하는 것과 동일한 효과를 낸다.

2. 소비 메커니즘:

• Kafka 대신 스케줄러를 사용하여 Redis SortedSet을 폴링한다. Kafka에서의 컨슘 메커니즘도 결국 폴링이기 때문에, 이를 어플리케이션에서 구현하는 방식으로 해석할 수 있다.

가능할 것 같다!

 

정리해보면 구체적인 구현 방안은 다음과 같다.

• ActiveQueueService:
  • 활성 토큰에 대한 정보를 Kafka에 발행하는 대신, Redis에 만료 SortedSet을 만들어 해당 SortedSet에 저장한다. 이때 TTL 기준으로 정렬되도록 한다.
• ExpirationService:
  • Redis SortedSet을 폴링하여 만료된 TTL을 확인한다.
  • TTL이 만료된 토큰을 받아서 만료된 값에 따라 카운터 값을 동기화한다.
  • SortedSet 조회는 맨 앞의 요소를 가져오므로 O(1)로 수행할 수 있다. 만약 조회할 요소의 개수가 늘어난다면 조회 개수를 동적으로 조정해도 될 것이다.

결론적으로, Kafka를 사용할 때와 메커니즘 자체는 동일하지만, 보다 적절하게 문제를 해결할 수 있는 방식이다.

 

다만, 이 방식에서는 Sorted Set에서 만료된 값을 지워주어야 하므로, 멀티 인스턴스 환경에서 동시 스케줄링 작동 시 동시성 이슈가 발생할 수 있음을 고려하여 로직을 구현해야 한다.

 

이렇게 Redis의 SortedSet을 활용하여 보다 TTL 처리와 카운터 동기화를 O(1)로 해결할 수 있다.

최종 아키텍처