레이트 리미터는 모든 요청 앞에서 실행되므로, 한 번의 판정이 얼마나 빠른지와 키 하나가 얼마나 많은 메모리를 쓰는지가 곧 서비스 비용이 됩니다. 이 장에서는 다섯 알고리즘의 시간·공간 복잡도와 정확도, 버스트 처리 방식을 비교합니다. 아래에서 L은 창 하나의 한도, K는 활성 키의 수입니다.
요청 하나를 판정하는 시간
- 고정 창: 창 번호를 계산하고 카운터 하나를 올립니다.
O(1)입니다. - 슬라이딩 창 로그: 창 밖으로 나간 기록을 앞에서 버린 뒤 개수를 셉니다. deque를 쓰면 기록 하나는 한 번만 들어가고 한 번만 나가므로 분할 상환
O(1)이지만, 한 번의 호출에서는 최악 O(L)개를 버릴 수 있습니다. Redis 정렬 집합(sorted set)으로 구현하면 추가와 범위 삭제에 O(log n)이 듭니다. - 슬라이딩 창 카운터: 곱셈 한 번과 덧셈 한 번입니다.
O(1)입니다. - 토큰 버킷: 경과 시간 × rate를 더하고 비교합니다.
O(1)입니다. - 리키 버킷(큐): 넣기와 꺼내기가 각각
O(1)입니다.
키 하나가 쓰는 메모리
전체 메모리는 여기에 활성 키 수 K를 곱합니다. 한도가 "시간당 10,000번"이고 활성 사용자가 10만 명이면, 슬라이딩 창 로그는 최악의 경우 시각 10억 개를 저장해야 합니다. 같은 상황에서 토큰 버킷은 숫자 20만 개면 됩니다. 이 차이 때문에 대규모 서비스는 로그 방식을 거의 쓰지 않습니다.
def worst_case_bytes(keys: int, limit: int, bytes_per_number: int = 8) -> dict[str, int]:
return {
"fixed_window": keys * 2 * bytes_per_number,
"sliding_log": keys * limit * bytes_per_number,
"sliding_counter": keys * 3 * bytes_per_number,
"token_bucket": keys * 2 * bytes_per_number,
}
for name, size in worst_case_bytes(keys=100_000, limit=10_000).items():
print(f"{name:16} {size / 2**20:10.1f} MiB")
# sliding_log 은 약 7,629 MiB, 나머지는 몇 MiB 수준
실제 메모리는 언어와 저장소의 부가 비용 때문에 이보다 큽니다. 그래도 크기의 차수는 그대로입니다.
정확도와 버스트
토큰 버킷의 상한은 공식으로 바로 계산됩니다. 버킷이 가득 찬 상태에서 시작하면 길이 T 동안 최대 capacity + rate × T개가 통과합니다. 그래서 "평균 초당 10개, 최대 버스트 20개"처럼 두 숫자로 설정합니다.
def max_admitted(rate: float, capacity: float, seconds: float) -> int:
# 가득 찬 버킷에서 시작해 seconds 동안 통과할 수 있는 최대 요청 수
return int(capacity + rate * seconds)
print(max_admitted(rate=10, capacity=20, seconds=1)) # 30
print(max_admitted(rate=10, capacity=20, seconds=60)) # 620
고정 창 경계 문제를 숫자로 확인하기
다음 코드는 경계 바로 앞뒤로 요청을 보냈을 때 고정 창과 슬라이딩 창 로그가 각각 몇 개를 허용하는지 셉니다.
from collections import deque
def fixed_window(times, limit, window):
counts = {}
ok = 0
for t in times:
w = int(t // window)
counts[w] = counts.get(w, 0) + 1
ok += counts[w] <= limit
return ok
def sliding_log(times, limit, window):
log, ok = deque(), 0
for t in times:
while log and log[0] <= t - window:
log.popleft()
if len(log) < limit:
log.append(t)
ok += 1
return ok
burst = [59.5] * 5 + [60.5] * 5 # 경계 앞뒤로 5번씩
print(fixed_window(burst, 5, 60)) # 10
print(sliding_log(burst, 5, 60)) # 5
분산 환경의 비용
여러 서버가 한도를 나눠 쓰면 판정마다 Redis 같은 공유 저장소에 한 번 다녀와야 합니다. 이때 비용은 알고리즘의 O(1)보다 네트워크 왕복 시간(보통 수백 마이크로초에서 수 밀리초)이 지배합니다. 그래서 명령 여러 개를 Lua 스크립트 하나로 묶어 왕복을 한 번으로 줄이고, 아주 큰 트래픽에서는 서버마다 로컬 버킷을 두고 공유 저장소와는 주기적으로만 맞추기도 합니다. 후자는 정확도를 조금 내주고 지연 시간을 얻는 선택입니다.
정리
- 고정 창, 슬라이딩 창 카운터, 토큰 버킷은 시간과 키당 공간이 모두
O(1)입니다. - 슬라이딩 창 로그는 정확하지만 키당
O(L) 메모리가 들어 대규모에는 부담입니다. - 토큰 버킷은 길이 T 동안 최대
capacity + rate × T개를 허용합니다. - 분산 환경에서는 알고리즘보다 네트워크 왕복이 비용을 결정합니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.