레이트 리밋 — 알고리즘과 구현
레이트 리밋 — 알고리즘과 구현
레이트 리밋은 자원을 보호하고 비용을 통제하고 남용을 줄입니다. 보기에 단순하지만 분산 환경의 정확성 · 공정성 · UX 사이에서 결정이 누적됩니다. 이 글은 fixed window · sliding window · token bucket · leaky bucket 알고리즘 · Redis 기반 구현 · 다른 층 (CDN · 프록시) 의 옵션 · 429 응답의 구성.
1. 두 축
레이트 리밋의 두 축:
- 정확성 — "정말로 N 회 / 시간 을 넘지 않는가."
- 부드러움 — "버스트가 있어도 사용자가 받는 응답이 끊기지 않는가."
두 축은 트레이드오프 관계. 알고리즘 선택이 그 균형을 정합니다.
2. Fixed Window
특정 단위 시간 (예: 1 분) 의 카운터 유지:
key = "rl:user:42:" + (now / 60)
count = INCR key
EXPIRE key 60 NX
if count > limit: reject
장점 — 단순. 한계 — 경계 효과 (burst at the boundary). 분 단위 50 회 한도라면 59 초 ~ 01 초 사이에 100 회가 통과될 수 있음.
3. Sliding Window Log
각 요청의 타임스탬프를 sorted set 에 저장하고 1 분 이전 항목을 잘라낸 후 카운트:
ZADD rl:user:42 <ts> <ts>
ZREMRANGEBYSCORE rl:user:42 0 (now-60)
count = ZCARD rl:user:42
장점 — 정확. 한계 — 메모리 사용량이 요청 수에 비례.
4. Sliding Window Counter
이전 윈도와 현재 윈도의 카운터를 가중 평균. fixed window 의 메모리 효율 + sliding window 의 평탄함을 절충:
weight = (now - current_window_start) / window_size
estimate = previous_count * (1 - weight) + current_count
Cloudflare 의 공개 글에서 자주 인용되는 방식.
5. Token Bucket
용량 N · 보충 속도 r 의 버킷에 요청이 토큰을 소비. 토큰이 없으면 거부 또는 대기:
on request:
tokens = min(capacity, tokens + (now - last) * rate)
if tokens >= 1:
tokens -= 1; allow
else:
reject
last = now
장점 — 버스트 허용 + 평균 통제. 다양한 라이브러리 · 프레임워크에서 채택 (Guava RateLimiter · NGINX limit_req 의 burst).
6. Leaky Bucket
토큰 버킷의 변형. 요청은 큐에 들어가 일정 속도로 흘러나감. 평균이 일정하지만 버스트가 큐에서 지연되거나 거부. 네트워크 트래픽 셰이핑에서 친숙한 모델.
7. Redis 기반 구현
가장 단순한 카운터:
INCR rl:<key>:<window>
EXPIRE rl:<key>:<window> <ttl> NX
if count > limit: reject
NX 로 EXPIRE 가 한 번만 설정되도록. 그렇지 않으면 매 요청마다 TTL 이 갱신되어 윈도 경계가 흐려질 수 있음.
Lua 스크립트로 원자성 — INCR 과 EXPIRE 사이에 다른 명령이 끼어드는 경합 방지:
local c = redis.call('INCR', KEYS[1])
if c == 1 then
redis.call('EXPIRE', KEYS[1], ARGV[1])
end
return c
Sliding window with Sorted Set:
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, ARGV[1] - ARGV[2])
local count = redis.call('ZCARD', KEYS[1])
if count >= tonumber(ARGV[3]) then
return -1
end
redis.call('ZADD', KEYS[1], ARGV[1], ARGV[1] .. ':' .. ARGV[4])
redis.call('EXPIRE', KEYS[1], ARGV[2])
return count + 1
8. 라이브러리
- Node —
rate-limiter-flexible·@upstash/ratelimit(서버리스 친화). - Java / Spring — Bucket4j · Resilience4j · Spring Cloud Gateway.
- Python —
limits·slowapi(FastAPI) ·django-ratelimit. - Go —
golang.org/x/time/rate.
직접 구현보다 검증된 라이브러리가 안전합니다.
9. 어디서 막는가
CDN · 엣지 — 비용을 가장 일찍 차단:
- Cloudflare Rate Limiting — IP · URL · 헤더 기반.
- AWS WAF Rate-based Rules — IP 단위 카운팅.
- Akamai · Fastly — 유사 기능.
엣지 차단의 강점은 원본까지 도달하지 않는다는 점. 한계는 인증 사용자 단위의 미세 제어가 어렵다는 점.
리버스 프록시:
- NGINX
limit_req/limit_conn— 메모리 기반 leaky bucket. burst 옵션. - HAProxy
stick-table— 다양한 키 기반 카운팅. - Caddy
rate_limit— 모듈로 제공.
애플리케이션 레벨 — 비즈니스 로직 (사용자 · 플랜 · API 키) 에 따른 세밀한 제어. 기본은 Redis 또는 인메모리.
엣지 + 애플리케이션의 두 층 결합이 흔함 — 엣지는 광범위 보호, 애플리케이션은 세밀한 비즈니스 규칙.
10. HTTP 429 응답
RFC 6585 (2012). 서버가 클라이언트에게 너무 많은 요청을 알리는 표준 상태 코드.
함께 보내는 헤더:
| 헤더 | 의미 |
|---|---|
Retry-After |
다음 요청까지 기다릴 시간 (초) 또는 절대 시각 |
X-RateLimit-Limit |
윈도 한도 |
X-RateLimit-Remaining |
남은 요청 수 |
X-RateLimit-Reset |
윈도 리셋 시각 (epoch) |
X-RateLimit-* 헤더는 사실상 표준이 됐지만 정식 RFC 는 아님 (RFC 9210 draft 등 진행). 일관성 있는 이름을 선택해 문서화.
11. 키 선택과 차등
키 선택:
- IP — 익명 사용자에 기본. NAT · 모바일 캐리어 IP 공유에 주의.
- 사용자 ID — 인증 사용자.
- API 키 — 머신 호출.
- IP + 라우트 — 로그인 같은 민감 엔드포인트.
여러 키를 동시에 쓰면 (사용자별 + IP별) 다층 보호.
정책 차등:
- 비인증 · 인증 · 유료 플랜에 따라 다른 한도.
- 라우트별 다른 한도 (쓰기 < 읽기).
- 점진적 백오프 (짧은 위반 → 짧은 차단, 반복 → 긴 차단).
12. 자주 걸리는 자리
분산 환경의 카운터 정확성 — 여러 서버가 같은 사용자 요청을 받으면 카운터를 한 곳 (Redis) 에 모아야 함. 인메모리 카운터는 노드 수만큼 한도가 늘어남.
clock 차이 — 노드 시계가 어긋나면 윈도 경계가 흐려짐. NTP 시간 동기.
시간 기반 키의 캐시 미스 — fixed window 의 키는 시간이 지나면 자동 만료되지만, 첫 요청에 EXPIRE 를 빠뜨리면 키가 영원히 남음. NX 옵션 또는 Lua.
Burst 허용 누락 — 정상 사용자도 페이지 새로고침으로 짧은 버스트. 한도가 너무 빡빡하면 사용자 경험 손상.
공유 IP 의 부수 피해 — NAT 뒤의 여러 사용자가 한꺼번에 막힘. 인증 후에는 사용자 키로 전환.
응답 형식 누락 — 클라이언트가 429 와 일반 에러를 구분 못 하면 재시도 로직이 망가짐. Retry-After 와 표준 형식.
Redis 의 SPOF — 레이트 리밋 시스템이 Redis 에 의존하다 Redis 장애 시 어떻게 동작할지 (fail-open 또는 fail-close) 결정.
테스트의 어려움 — 레이트 리밋 동작은 시간에 의존. 테스트에서는 시간 추상 또는 짧은 윈도.
하고픈 말
레이트 리밋은 단순한 카운터로 시작해도 운영 중에 정확성 · 공정성 · UX 의 트레이드오프가 차곡차곡 드러납니다. Redis Sliding Window Counter + Lua 원자성 + 차등 키 (사용자 / IP / 라우트) + 표준 429 헤더 넷이 함께 있을 때 안정적인 자리. 검증된 라이브러리를 쓰고, 테스트는 짧은 윈도로.
Next
- input-validation-zod
- password-hashing
Cloudflare 블로그 — sliding window · Stripe Engineering — Rate Limiters · RFC 6585 (429) · RFC 9210 draft RateLimit headers · NGINX limit_req · Bucket4j · rate-limiter-flexible · @upstash/ratelimit 을 참고합니다.