단순 카운터로 만든 rate limit이 경계에서 뚫린 이유

문제 발생

"분당 100건"으로 API rate limit을 걸었는데, 실제로는 짧은 시간에 200건 가까이 요청이 통과되는 상황이 관측됐습니다.

# 고정 윈도우 카운터 방식
request_count[user_id] += 1
if request_count[user_id] > 100:
    raise RateLimitExceeded()
# 매 분 정각에 request_count를 0으로 초기화

원인 분석

이 구현은 고정 윈도우(Fixed Window) 방식입니다. 매 분 정각에 카운터를 0으로 리셋하는데, 문제는 이 경계 부근입니다. 예를 들어 사용자가 0분 59초에 100건을 몰아서 보내고(카운터 100 도달), 1분 00초가 되자마자 카운터가 리셋되어 다시 100건을 몰아서 보내면, 실제로는 단 2초 사이에 200건이 통과합니다. "분당 100건"이라는 규칙의 의도(초당 처리량을 어느 정도 평탄하게 유지)를 경계 부근에서 우회할 수 있는 구조적 허점입니다.

해결 방안

토큰 버킷(Token Bucket) 알고리즘이 이 문제를 해결하는 대표적인 방식입니다.

1. 각 사용자마다 정해진 용량(예: 100개)의 "버킷"을 둡니다.
2. 버킷은 일정한 속도로(예: 초당 100/60개씩) 토큰이 채워지며, 최대 용량을 넘지 않습니다.
3. 요청이 올 때마다 토큰을 하나 소비합니다. 버킷에 토큰이 없으면 요청을 거부합니다.

이 방식은 순간적으로 버킷에 쌓인 토큰만큼 버스트(순간적으로 몰리는 트래픽)를 허용하면서도, 장기적으로는 정해진 평균 속도를 넘지 못하게 막습니다 — 분 경계라는 개념 자체가 없어 경계 우회 문제가 발생하지 않습니다.

# 개념적 예시 (실제로는 Redis 등으로 원자적 연산 필요)
now = time.time()
elapsed = now - bucket.last_refill
bucket.tokens = min(bucket.capacity, bucket.tokens + elapsed * refill_rate)
bucket.last_refill = now

if bucket.tokens >= 1:
    bucket.tokens -= 1
    allow_request()
else:
    reject_request()

비슷한 목적의 대안으로 슬라이딩 윈도우 로그(각 요청의 타임스탬프를 기록하고 윈도우 밖의 것을 지우는 방식, 정확하지만 메모리 사용량이 큼)나 슬라이딩 윈도우 카운터(고정 윈도우 두 개를 가중 평균하는 근사 방식, 구현이 비교적 단순)도 있습니다.

여러 서버 인스턴스에서 동시에 rate limit을 적용해야 한다면, 카운터/버킷 상태를 각 서버 로컬 메모리가 아니라 Redis 같은 공유 저장소에 두고 원자적 연산(Lua 스크립트, INCR 등)으로 갱신해야 경쟁 상태 없이 정확하게 동작합니다.

공식 문서

• Cloudflare Blog: How we built rate limiting capable of scaling to millions of domains — 토큰 버킷과 슬라이딩 윈도우 방식을 비교 설명합니다.
• Redis Docs: Rate limiting patterns