DEV

Token bucket 알고리즘(feat.redis)

Token bucket 알고리즘의 개념과, SCG 내부에서 어떻게 redis를 사용해 구현되어 있는지

jiheon2234

— 4 min read
Token bucket 알고리즘(feat.redis)

Intro

토큰 버킷(Token Bucket)알고리즘은 처리율 제한(rate limit)알고리즘 중 가장 유명한 알고리즘이에요. 대표적으로 Amazon, Google 등의 대규모 트래픽을 다루는 빅테크에서도 사용하죠.

이 글에서는 토큰 버킷 알고리즘의 개념을 알아보고, 실제 어떻게 구현되는지까지 살펴볼게요

알고리즘 개념

토큰 버킷 알고리즘은 꽤 단순해요:

  • 버킷은 매초 R개의 토큰이 채워짐
  • 버킷은 최대 C개까지만 담을 수 있고, 넘치면 버림
  • 요청시엔
    • 토큰이 있으면 → 토큰 소모 후 통과
    • 토큰이 없으면 → 429

여기서C는 최대 버스트 처리량, R은 평균 처리율을 의미해요. 이 두 값을 어떻게 튜닝하냐에 따라 시스템의 성능 특성을 조절할 수 있죠.

시간의 흐름에 따라 보면 다음과 같아요:

from System Design Interview book

특징

  • 장기적으로는 초당 R 이하의 평균처리량을 보장해요
  • 버킷에 토큰이 남아있는 한, C 이하의 갑작스러운 버스트 트래픽도 처리할 수 있어요. (하지만 이게 다운스트림 순간 과부하로 이어질 위험도 있죠)
  • 구현이 간단하고, 비교적 적은 메모리를 사용해요. (다른 rate limit 알고리즘에 비해서)

알고리즘 구현

사실, 이 글은 Spring Cloud gateway(SCG)를 공부하다가 작성했어요. SCG에서 요청 제한을 거는 RateLimiter는 기본적으로 RedisRateLimiter를 사용하는데, 이게 토큰 버킷 알고리즘으로 동작하거든요.

여기서는 RedisRateLimiter가 내부적으로 사용하는 Lua 스크립트를 통해, 알고리즘이 실제로 어떻게 구현되는지 살펴볼게요.

-- redis.replicate_commands()  redis 7이하일때만 호환

-- 자바에서 전달하는 값들
local tokens_key = KEYS[1] -- 버킷
local timestamp_key = KEYS[2] -- 마지막으로 채운 시간
local rate = tonumber(ARGV[1]) -- 'R' (초당 토큰 보충개수)
local capacity = tonumber(ARGV[2]) -- 'C' (버킷 cap)
local now = tonumber(ARGV[3]) or redis.call('TIME')[1] --(현재시각)
local requested = tonumber(ARGV[4]) -- 요청에 필요한 토큰 개수 (기본 1)

-- TTL = 버킷 풀충시간 * 2
local fill_time = capacity / rate 
local ttl = math.floor(fill_time * 2)

-- 현재버킷상태
local last_tokens = tonumber(redis.call("get", tokens_key)) or capacity 
local last_refreshed = tonumber(redis.call("get", timestamp_key)) or 0  

-- 경과시간만틈 토큰을 채우고,허용여부 결정
local delta = math.max(0, now-last_refreshed)
local filled_tokens = math.min(capacity, last_tokens+(delta*rate))
local allowed = filled_tokens >= requested
local new_tokens = allowed and filled_tokens - requested or filled_tokens

-- 버킷 업데이트
if ttl > 0 then 
  redis.call("setex", tokens_key, ttl, new_tokens)
  redis.call("setex", timestamp_key, ttl, now)
end

return { allowed and 1 or 0, new_tokens } -- 이걸 자바에서 List<Long>으로
-- //boolean allowed = results.get(0) == 1L;
-- //Long tokensLeft = results.get(1);

원본링크

1초마다 정해진 개수를 채우지 않고, 요청 시점에 delta 만큼 한꺼번에 채우는 점만 살짝 다르고, 나머지는 위에서 설명한 알고리즘 그대로죠?

Final

처리율 제한 알고리즘에는 토큰 버킷 알고리즘 말고도 누출 버킷(Leaky Bucket), 고정 윈도 카운터(Fixed Window Counter),이동 윈도 로그(Sliding Window Log), 이동 윈도 카운터(Sliding Window Counter)등등의 다양한 방식이 있어요.

이번 글에서는 토큰 버킷만 설명했지만, 상황에 따라 다른 알고리즘을 선택할 수도 있죠. (기회가 생기면 다른 알고리즘도 다뤄볼게요)

3-Point

  1. 토큰 버킷 알고리즘은 가장 널리 사용되는 처리율 제한 기법이다.
  2. 메모리 사용이 적으면서도 버스트 트래픽을 흡수할 수 있다.
  3. SCG의 기본 RateLimiter 역시 이 알고리즘을 기반으로 한다.

Read more