이 문서를 통해 아래 질문들에 답할 수 있게 됩니다.
- Token Bucket, Sliding Window, Fixed Window는 어떤 트래픽 모양에 맞는가?
- 알고리즘 선택이 burst 허용, 정확도, 저장 비용, 운영 복잡도를 어떻게 바꾸는가?
- Redis 기반 limiter를 만들 때 어떤 원자성, TTL, key 설계를 확인해야 하는가?
개요
Rate Limit 알고리즘은 같은 “분당 60회”라도 전혀 다른 사용자 경험과 부하 모양을 만든다. 어떤 알고리즘은 짧은 burst를 허용하고, 어떤 알고리즘은 최근 사용량을 더 정확히 계산하며, 어떤 알고리즘은 구현이 쉽지만 경계 시간에 약하다.
따라서 알고리즘 선택은 수학 문제가 아니라 트래픽 모양과 보호 대상의 문제다. 로그인 시도 제한과 검색 API 제한은 같은 알고리즘을 쓰지 않아도 된다.
Fixed Window
Fixed Window는 정해진 시간 구간마다 counter를 세는 방식이다.
key = rate:user:42:202607011030
limit = 60 requests / minute장점은 단순함이다. Redis INCR와 EXPIRE로 구현하기 쉽고 저장 비용도 낮다.
문제는 경계 시간이다. 사용자가 10:30:59에 60번, 10:31:00에 60번 요청하면 실제 2초 동안 120번을 허용할 수 있다.
Fixed Window는 다음 조건에 맞다.
- 제한 정확도가 조금 거칠어도 된다.
- 구현과 운영 단순성이 더 중요하다.
- endpoint 비용이 낮고 burst가 치명적이지 않다.
Sliding Window
Sliding Window는 최근 N초나 N분의 요청을 기준으로 제한한다. 구현 방식은 크게 log 방식과 counter 방식으로 나뉜다.
Sliding Window Log는 요청 timestamp를 저장한다.
user:42 -> [10:30:10, 10:30:20, 10:30:55]정확하지만 요청 수가 많으면 저장 비용이 커진다. Sliding Window Counter는 구간을 더 잘게 나눠 근사 계산한다. 정확도는 조금 낮지만 저장 비용이 줄어든다.
Sliding Window는 다음 조건에 맞다.
- 로그인, 결제, 쿠폰처럼 경계 시간 악용을 줄여야 한다.
- 사용자의 최근 행동을 기준으로 판단해야 한다.
- 저장 비용을 감당할 수 있거나 근사 계산을 받아들일 수 있다.
Token Bucket
Token Bucket은 bucket에 token이 일정 속도로 채워지고, 요청마다 token을 하나씩 소비하는 방식이다.
capacity = 100 tokens
refill = 10 tokens / second
request = consume 1 token이 방식은 평균 속도는 10 rps로 제한하지만 bucket에 token이 쌓여 있으면 짧은 burst를 허용한다.
검색 API나 이벤트 페이지 조회처럼 짧은 burst가 정상 행동일 수 있는 곳에 적합하다. 반대로 로그인 brute force처럼 burst 자체가 위험한 곳에는 부적합할 수 있다.
Leaky Bucket
Leaky Bucket은 요청을 bucket에 넣고 일정한 속도로 흘려보내는 모델이다. 유입이 흔들려도 downstream에는 비교적 일정한 속도가 전달된다.
장점은 downstream 보호다. 단점은 대기열이 생기고, 오래 기다린 요청을 언제 버릴지 정해야 한다는 점이다.
실무에서는 queue, worker, concurrency limit과 함께 backpressure 정책으로 나타나는 경우가 많다.
알고리즘 비교
| 알고리즘 | Burst 허용 | 정확도 | 저장 비용 | 적합한 예 |
|---|---|---|---|---|
| Fixed Window | 높음 | 낮음 | 낮음 | 단순 public API quota |
| Sliding Window Log | 낮음 | 높음 | 높음 | 로그인, 쿠폰 발급 |
| Sliding Window Counter | 중간 | 중간 | 중간 | 일반 사용자별 quota |
| Token Bucket | 정책적으로 허용 | 중간 | 낮음~중간 | 검색, 이벤트 조회 |
| Leaky Bucket | 낮음 | 처리 속도 중심 | queue 비용 | 외부 API 보호 |
정확한 알고리즘이 항상 좋은 것은 아니다. 정확도를 높이면 저장소 부하와 운영 복잡도가 커진다.
Redis 원자성
Rate Limit은 경쟁 상태에 취약하다. 여러 애플리케이션 인스턴스가 동시에 같은 key를 갱신하기 때문이다.
나쁜 구현:
1. GET count
2. count < limit 확인
3. INCR count
4. EXPIRE 설정이 흐름은 동시에 요청이 들어오면 제한을 초과해 허용할 수 있고, INCR 후 EXPIRE 전에 실패하면 key가 남을 수 있다.
Redis에서는 Lua script나 atomic command 조합으로 counter 증가와 TTL 설정을 함께 처리해야 한다.
local current = redis.call("INCR", KEYS[1])
if current == 1 then
redis.call("EXPIRE", KEYS[1], ARGV[1])
end
return current이 예시는 단순 fixed window다. token bucket은 현재 token 수와 마지막 refill 시각을 함께 저장해야 한다.
Key 설계
Key는 제한 단위를 드러내야 한다.
rate:login:ip:203.0.113.10
rate:search:user:42
rate:partner-api:key:abc
rate:tenant:acme:endpoint:exportKey 설계의 위험은 cardinality다. userId, IP, endpoint, device를 모두 조합하면 key 수가 급격히 늘 수 있다. TTL과 prefix별 memory 사용량을 관측해야 한다.
Reset과 사용자 경험
알고리즘은 사용자가 보는 reset 시간도 바꾼다.
Fixed Window는 다음 분이 되면 reset된다. Sliding Window는 사용량이 서서히 줄어든다. Token Bucket은 token이 refill되는 만큼 다시 요청할 수 있다.
클라이언트에 Retry-After를 줄 때도 이 차이를 반영해야 한다. token bucket에서 retry after는 다음 token이 생기는 시간이고, fixed window에서는 window reset 시점일 수 있다.
선택 예시
로그인 API:
- IP + 계정 조합 제한
- Sliding Window 또는 점진적 지연
- 실패 횟수와 captcha, lock 정책 연결
검색 API:
- userId 또는 API key 기준
- Token Bucket으로 짧은 burst 허용
- 비싼 query는 별도 낮은 limit
Export API:
- tenant와 job 기준
- concurrency limit 또는 queue 기반 leaky bucket
- 결과 생성 pending 상태 제공
위험 신호
- 모든 API에 fixed window 60/min만 적용한다.
- Redis key에 TTL이 없어 제한 counter가 계속 남는다.
- burst 허용 여부를 사용자 경험과 연결해 설명하지 못한다.
- region별 limiter를 쓰면서 전역 quota처럼 설명한다.
Retry-After가 알고리즘과 맞지 않는다.
개인 프로젝트 기준
- 최소 fixed window와 token bucket 차이를 설명한다.
- Redis 없이 구현했다면 다중 인스턴스에서 정확하지 않다고 적는다.
- 제한 key와 TTL을 로그로 확인할 수 있게 한다.
- 테스트에서 window 경계와 burst를 재현한다.
기업 운영 기준
- 알고리즘별 정책 이름과 version을 관리한다.
- Redis memory, command latency, key cardinality를 본다.
- region별 quota 분산과 clock skew를 검토한다.
- 정책 변경 전후 429 rate와 conversion 지표를 비교한다.
확인 질문
확인 질문
- 확인 질문: Token Bucket이 Fixed Window와 다른 핵심은 무엇인가?
- 답변: 평균 속도는 제한하면서 bucket capacity만큼 짧은 burst를 허용한다는 점이다.
- 확인 질문: Sliding Window가 필요한 상황은 언제인가?
- 답변: window 경계에서 요청을 몰아 제한을 우회하는 문제가 크거나 최근 행동을 더 정확히 봐야 할 때다.
- 확인 질문: Redis limiter에서 원자성이 중요한 이유는 무엇인가?
- 답변: 여러 인스턴스가 동시에 같은 counter를 갱신하므로 증가, 판정, TTL 설정이 분리되면 제한 초과나 key 누수가 생길 수 있기 때문이다.