Rate Limiter란?
Rate Limiter는 특정 시간 동안 허용되는 요청의 수를 제한하는 메커니즘입니다. API 서버에서 과도한 요청으로부터 시스템을 보호하고, 공정한 자원 사용을 보장하기 위해 사용됩니다.
주요 Rate Limiter 알고리즘
1. Token Bucket Algorithm (토큰 버킷)
동작 원리
- 고정된 크기의 버킷에 일정한 속도로 토큰이 추가됩니다
- 요청이 올 때마다 버킷에서 토큰을 소모합니다
- 토큰이 없으면 요청을 거부하거나 대기시킵니다
핵심 파라미터
bucket_size: 버킷의 최대 용량refill_rate: 토큰이 추가되는 속도 (예: 초당 10개)
장점
- 버스트 트래픽 허용: 버킷에 토큰이 쌓여있으면 순간적으로 많은 요청 처리 가능
- 구현이 직관적이고 이해하기 쉬움
단점
- 메모리 사용: 각 클라이언트별로 버킷 상태를 저장해야 함
사용 사례
AWS API Gateway, Google Cloud Endpoints 등에서 사용
2. Leaky Bucket Algorithm (누수 버킷)
동작 원리
- 요청들이 FIFO 큐 형태의 버킷에 저장됩니다
- 일정한 속도로 버킷에서 요청이 처리됩니다 (누수)
- 버킷이 가득 차면 새로운 요청은 거부됩니다
핵심 파라미터
bucket_size: 대기열의 최대 크기outflow_rate: 처리 속도 (예: 초당 5개 요청)
장점
- 일정한 처리율 보장: 출력 속도가 항상 일정함
- 트래픽 평활화 효과
단점
- 버스트 트래픽에 대한 유연성 부족
- 큐 관리 오버헤드
Token Bucket vs Leaky Bucket
Token Bucket은 버스트를 허용하지만, Leaky Bucket은 항상 일정한 속도로만 처리합니다.
3. Fixed Window Counter (고정 윈도우 카운터)
동작 원리
- 시간을 고정된 윈도우로 나눕니다 (예: 1분 단위)
- 각 윈도우마다 요청 수를 카운트합니다
- 윈도우 내 한계치를 초과하면 요청을 거부합니다
예시
윈도우: 14:00:00 - 14:00:59 (최대 100개 요청)
14:00:30에 이미 100개 요청이 왔다면, 14:00:59까지 모든 요청 거부장점
- 구현이 매우 간단
- 메모리 효율적 (카운터 하나만 필요)
단점
- 경계 문제 (Boundary Issue): 윈도우 경계에서 순간적으로 2배의 요청 가능
경계 문제 예시
13:59:30 ~ 13:59:59: 100개 요청
14:00:00 ~ 14:00:29: 100개 요청
→ 1분 내에 실제로는 200개 요청 처리됨4. Sliding Window Log (슬라이딩 윈도우 로그)
동작 원리
- 각 요청의 타임스탬프를 로그에 저장합니다
- 새 요청이 올 때 현재 시간 기준으로 윈도우 크기만큼 이전 로그들을 확인합니다
- 윈도우 내 요청 수가 한계치를 초과하면 거부합니다
예시
윈도우 크기: 1분, 한계: 100개
현재 시간: 14:01:30
→ 14:00:30 ~ 14:01:30 사이의 모든 요청 로그를 확인장점
- 정확한 Rate Limiting: 경계 문제가 없음
- 세밀한 제어 가능
단점
- 높은 메모리 사용량: 모든 요청의 타임스탬프 저장 필요
- 성능 오버헤드: 매번 로그 스캔 필요
5. Sliding Window Counter (슬라이딩 윈도우 카운터)
동작 원리
- Fixed Window의 단순함과 Sliding Window Log의 정확성을 절충한 방식
- 이전 윈도우와 현재 윈도우의 카운트를 가중평균으로 계산합니다
계산 공식
추정 요청 수 = (이전 윈도우 카운트 × 겹치는 시간 비율) + 현재 윈도우 카운트예시
윈도우 크기: 1분, 현재 시간: 14:00:30
이전 윈도우(13:59:00-13:59:59): 80개 요청
현재 윈도우(14:00:00-14:00:59): 30개 요청
겹치는 시간: 30초 (50%)
추정 요청 수 = 80 × 0.5 + 30 = 70개장점
- 메모리 효율적: 2개 카운터만 필요
- 경계 문제 완화
- 구현 복잡도와 정확성의 적절한 균형
단점
- 근사치 계산으로 완전히 정확하지는 않음
알고리즘 선택 가이드
상황별 권장 알고리즘
버스트 트래픽을 허용해야 하는 경우
→ Token Bucket 사용
일정한 처리율이 중요한 경우
→ Leaky Bucket 사용
간단한 구현이 필요한 경우
→ Fixed Window Counter 사용
정확한 제어가 필요하지만 메모리가 충분한 경우
→ Sliding Window Log 사용
균형잡힌 해결책이 필요한 경우
→ Sliding Window Counter 사용
성능과 정확성 트레이드오프
정확성 높음: Sliding Window Log > Sliding Window Counter > Token Bucket > Fixed Window Counter
성능 높음: Fixed Window Counter > Sliding Window Counter > Token Bucket > Sliding Window Log
메모리 적음: Fixed Window Counter > Sliding Window Counter > Token Bucket > Sliding Window Log실제 구현 시 고려사항
분산 환경에서의 Rate Limiting
중앙집중식 접근
- Redis와 같은 중앙 저장소 사용
- 모든 서버가 동일한 카운터 공유
- 네트워크 지연과 단일 실패점 고려 필요
분산 접근
- 각 서버가 독립적으로 Rate Limiting 수행
- 전체 한계치를 서버 수로 나누어 할당
- 완전히 정확하지 않지만 성능상 유리
저장소 선택
In-Memory (Redis, Memcached)
- 빠른 응답 시간
- 휘발성으로 재시작 시 데이터 손실
Database
- 영구 저장 가능
- 상대적으로 느린 응답 시간
구조적 통찰
Rate Limiter 설계에서 가장 중요한 것은 정확성, 성능, 메모리 사용량 간의 트레이드오프를 이해하는 것입니다.
각 알고리즘은 서로 다른 철학을 가지고 있습니다:
- Token Bucket: "평소에는 여유를 두되, 필요할 때는 폭발적으로"
- Leaky Bucket: "항상 일정하게, 안정적으로"
- Window 기반: "시간 단위로 명확하게 구분하여 관리"
실제 시스템에서는 종종 여러 알고리즘을 조합하거나, 상황에 따라 다른 알고리즘을 적용하는 하이브리드 접근법을 사용합니다.
예를 들어, 일반 사용자에게는 Token Bucket을, 의심스러운 트래픽에는 더 엄격한 Fixed Window Counter를 적용하는 방식입니다. 이러한 설계 사고방식이야말로 시스템 아키텍트로서 갖춰야 할 핵심 역량이라 할 수 있습니다.
