대기열 시스템

커머스 서비스에서는 이벤트로 인해 짧은 시간에 급격하게 올라가는 트래픽에 대응하기 위해서 대기열 시스템을 적극적으로 활용하고 있다.

 

대기열 시스템의 실제 구현은 서비스의 요구사항, 트래픽 수준 등에 따라 천차만별이다.

이번 포스팅에서는 가상의 요구사항을 제시하고 이를 만족하는 대기열 시스템을 구현해보도록 하겠다.

 

(Fastify 기반의 대기열 시스템 API 예제는 여기에서 확인할 수 있다)

 

요구 사항

이벤트 상품 주문 페이지의 트래픽을 조절할 수 있는 대기열 시스템을 구현한다.

 

이 시스템의 기능적 요구 사항은 아래와 같다.

1. 대기열 시스템은 대기와 입장만 관리하고 입장 이후는 관리하지 않는다.
2. 대기열 시스템은 이벤트 상품 주문 페이지에 5초 당 10명의 사용자를 입장시킨다.
   
   1. 사용자가 대기할 필요가 없는 경우 바로 이벤트 상품 주문 페이지로 입장한다.
   2. 한 번에 입장 시키는 유저의 수는 백오피스를 통해 변경할 수 있다.
3. 이벤트 상품 주문 페이지 재진입 시 해당 사용자는 대기열 맨 뒤로 이동한다.
4. 사용자는 자신의 대기 순번과 예상 대기 시간을 확인할 수 있다.

기능 구현

동작 과정

큰 그림에서 어떻게 전체 시스템이 동작하는지를 확인해보자.

대기열 서비스는 상품 주문 서비스의 support 역할로 상품 주문 서비스와 별도의 서비스로 관리하도록 하였다.

사용자의 이벤트 상품 주문 페이지 입장과 관련된 데이터는 모두 대기열 서비스를 통해 관리된다.

 

대기열 관리

사용자를 대기열에 관리하기 위해 queue 형태로 데이터를 사용할 필요가 있다.

또한 매 5초 마다 10명의 사용자를 입장 시켜야하는데 이는 rate limit에서 사용되는 Token Bucket algorithm을 기반으로 대기열의 사용자 입장을 관리하도록 한다.

 

도식을 단순하게 하기 위해 5초 마다 2명의 사용자를 입장하는 예제를 살펴보면 아래와 같다.

 

5명의 사용자가 이벤트 상품 주문 페이지에 입장을 시도하는 경우,

ⓐ 먼저 요청이 처리되는 2명의 사용자가 토큰을 사용하여 상품 주문 페이지에 입장할 수 있게된다.

ⓑ 남은 토큰이 없기 때문에 그 이후에 처리되는 3명의 사용자는 대기열에서 입장을 대기한다.

 

ⓒ 그리고 5초 뒤 충전될 토큰의 수 만큼 대기열의 있는 사용자를 이동시킨다.

ⓓ 다시 5초 뒤 충전될 토큰의 수 만큼 대기열의 있는 유저를 이동시킨다. 이때 토큰이 1개 남게된다.

ⓔ 마지막으로 5초 뒤 대기열에 유저가 없으므로 토큰은 모두 충전된다.

  (5초 당 최대 2명의 사용자를 입장 시켜야하니 2개 이상 토큰이 충전되지 않는다)

 

(입장한 사용자 데이터는 꼭 queue로써 관리될 필요는 없다)

(입장한 사용자 데이터는 계속 남아 저장 공간을 차지하기 때문에 주기적으로 오래전에 입장한 내역을 날릴 필요가 있다.)

 

Redis Lua script

Redis는 command가 single thread로 처리되기 때문에 원자성이 중요한 데이터를 빠르게 처리해야하는 경우 안성맞춤이다.

하지만 서버 애플리케이션 <-> Redis 간 요청을 여러번 하게 되는 경우 race condition이 발생할 수 있다.

그렇다고 lock을 걸게되면 거기서 오는 overhead와 병목이 생기게게 된다.

 

그렇기 때문에 단일 요청에서 데이터 처리를 위해 Lua script를 적극적으로 활용하고자한다.

어떻게 Lua script를 통해 대기 및 입장과 관련된 데이터를 처리하는지를 살펴보자.

 

(물론 command가 single thread로 처리되는 Redis의 특성 상 단순히 Lua script를 활용한다고 해서 빠른 성능을 보장할 수 없다.

 데이터를 빠르게 저장하고 조회하기 위한 데이터 타입 선택과 사용하는 커맨드의 시간 복잡도의 확인은 필수다.)

 

입장 시도

• 입장 시도 시
  • 현재 남아있는 토큰을 확인하고 토큰이 남아있으면 바로 입장열에 추가된다.
  • 토큰이 남아있지 않으면 대기열에 추가된다.
• 재입장 시도 시
  • 기존에 대기열이나 입장열에 유저가 있는 경우에도 재입장 시 다시 대기를 해야한다.
  • 그렇기 때문에 기존 대기열과 입장열에 있는 사용자 데이터를 제거한 뒤에 그대로 입장 처리를 한다.

local userId = KEYS[1]
local currentTimeMillis = tonumber(ARGV[1])

-- 입장 시도 시 기존 대기열에 있던 사용자 제거
redis.call('ZREM', 'waiting-queue', userId)
redis.call('ZREM', 'entry-queue', userId)

local currentTokens = tonumber(
    redis.call('GET', 'current-token') or
    redis.call('GET', 'refill-token-size') or 10 -- 입장이 없어서 관리되는 `current-token` key가 없는 경우
)

-- 토큰이 있으면 대기없이 바로 입장
if 0 < currentTokens then
    redis.call('ZADD', 'entry-queue', currentTimeMillis, userId)
    redis.call('SET', 'current-token', currentTokens - 1)
    return 'ENTERED'
end

-- 토큰이 없으면 대기 queue에 추가
redis.call('ZADD', 'waiting-queue', currentTimeMillis, userId)
return 'WAITING'

 

대기열 => 입장열 이동 및 토큰 리필

• 토큰이 새로 리필되고 리필된 토큰을 사용해서 사용자가 대기열에서 입장열로 이동하게 된다.
  
  • 만약 대기열에 사용자가 리필된 토큰의 양과 동일하면 모든 토큰을 소모하게 된다.
• 이 스크립트는 요구사항인 5초 마다 실행되어야 한다.
  • 이 스크립트가 처리되는 동안 입장 시도 처리는 blocking 되기 때문에 실행 시간은 최소화 되어야한다.

local currentTimeMillis = ARGV[1]

-- 리필 될 토큰의 양
local numberOfRefilledTokens = tonumber(
    redis.call('GET', 'refill-token-size') or 10
)

-- 대기열에 있는 유저 입장 처리: 토큰 소모
local nextUserIds = redis.call('ZRANGE', 'waiting-queue', 0, numberOfRefilledTokens - 1)

for _i, userId in ipairs(nextUserIds) do
    redis.call('ZREM', 'waiting-queue', userId)
    redis.call('ZADD', 'entry-queue', currentTimeMillis, userId)
    numberOfRefilledTokens = numberOfRefilledTokens - 1
end

-- 추가된 유저를 제외 한 토큰 저장
redis.call('SET', 'current-token', numberOfRefilledTokens)

 

입장 / 대기 상태 확인

• 입장 가능한 상태인지 혹은 대기 중이면 얼마나 기다려야 하는지를 확인하기 위한 스크립트이다.
• 단순 조회 기능이기 때문에 스크립트를 사용하지 않아도 되지만, 되도록 Redis를 여러 번 호출하지 않고 하기 위해 스크립트로 처리했다.

local userId = KEYS[1]

local enteredAt = redis.call('ZSCORE', 'entry-queue', userId)

-- 입장한 경우
if enteredAt ~= false then -- redis.call(ZSCORE)는 key나 value가 없는 경우 false를 리턴함
    return {'ENTERED', -1, -1}
end

local waitingIndex = redis.call('ZRANK', 'waiting-queue', userId)

-- 대기 중인 경우
if waitingIndex ~= false then -- redis.call(ZRANK)는 key나 value가 없는 경우 false를 리턴함
    local refillTokenSize = tonumber(
        redis.call('GET', 'refill-token-size') or -- custom으로 설정한 리필 토큰 수
        10 -- 기본 리필 토큰 수
    )

    return {'WAITING', waitingIndex, refillTokenSize}
end

-- 입장도 대기도 아닌 경우
return {'NOT_WAITING', -1, -1}

 

대기 중일 때 리필되는 토큰의 양을 조회하는 이유는 예상 대기 시간을 계산 하기 위함이다.

아래는 예상 대기 시간을 계산하는 예제 코드이다.

// 5초 마다 토큰이 리필되는 경우
Math.floor(waitingIndex / refillTokenSize + 1) * 5;

 

성능 측정

성능 측정을 위한 부하 테스트는 실제 배포될 운영 환경의 컴퓨팅 스펙과 유사하게 하는 것이 가장 좋다.

하지만 이 포스팅에서는 예제로 단순하게 로컬 PC 내에서 1개의 API 서버를 실행시킨 뒤 간단하게 부하 테스트를 진행하겠다.

(Fastify 기반의 대기열 시스템 API를 부하 테스트 대상으로 사용하였다 - 테스트 스크립트)

 

(부하 테스트 자체만을 하는건 큰 의미가 없다. 요구하는 성능을 만족하는지를 확인하고 그렇지 않다면 어느 부분에서 성능의 병목이 생기는지를 APM 등을 통해 파악하고 이를 개선하는 과정이 필요하다.

보다 정석적인 부하 테스트와 관련해서는 다음 글을 참고하길 바란다 - 스타트업의 부하 테스트 AtoZ, 결제 시스템 성능, 부하, 스트레스 테스트)

 

갑작스럽게 이벤트 상품 페이지에 진입하는 트래픽이 급증하는 예제를 재현하기 위해 Artillery를 사용해서 500TPS로 1분간 입장 시도 요청을 보냈다.

아래는 부하 테스트에 대한 summary이다.

비록 500 TPS가 그렇게 극단적으로 큰 트래픽이 아닐지라도 p99이 74ms 정도로 빠른 처리량을 보이는 것을 확인할 수 있다.

 

추가로 Redis docker container의 CPU 사용량도 확인해보았다.

(로컬에서의 수치를 보는게 큰 의미가 없을 순 있지만) 부하 테스트를 하는 동안에 CPU가 증가하긴 했지만 Redis 에서는 안정적으로 트래픽을 처리할만한 충분한 여유가 있다고 보인다.

 

추가로 API 서버를 여러 대 사용하고 API 서버와 Redis 서버를 분리한 뒤 부하 테스트를 해보면 더 의미있는 결과를 확인할 수 있을 것이다.

(실제 운영 환경에서는 네트워크로 인한 레이턴시도 고려해야한다)

 

---

 

지금까지 이벤트 상품 주문 페이지에 대해서 대기열을 적용하는 예제에 대해서 알아보았다.

하지만 당연히 이 구현 방식이 베스트는 아닐 수 있으며 가용한 리소스나 비즈니스 요구사항에 따라 구현의 디테일은 충분히 달라질 수 있다. 

 

만약 지금과 같이 단일 페이지가 아니라 여러 페이지에 대해서 대기열을 적용해야한다면 추가로 고려해야할 부분이 있다.

• 동일하게 Redis를 사용하는 경우라면 scale out을 위해 Clustering을 적용할 수 있는데,
  Cluster를 적용하면 lua script가 정상적으로 동작하기 위해 Hash Tags를 적용해야하기도 한다.
• 또한 모든 요구사항을 만족시키기 어려울 수가 있다.
  • 대기 관리 대상이 많아진다면 key가 많아지기 때문에 특정 pattern의 key를 찾는 SCAN 커맨드도 전체 실행 시간은 오래걸리게 된다. (결국 모든 key를 끊어서 iterating 하는 것과 다를바가 없기 때문에 - 참고: Redis의 SCAN은 어떻게 동작하는가?)
  • 데이터가 많기 때문에 처리 속도도 느려질 수도 있게되고 대기열의 유저를 입장시키는 주기를 더 길게 잡아야할 수도있다.
  • 네이버 페이에서는 확장 가능한 형태의 시스템 구현을 위해 정확한 대기열 인원을 queue로써 관리를 하지 않았다. (참고 - 네이버페이 주문에 적용된 확장 가능한 대기열 개발기)