기술 요약: API 속도 제한 알고리즘의 비교 조사

문제 정의

현대의 백엔드 시스템은 예측 불가능한 클라이언트 집단에 API를 노출하며, 단일 클라이언트 또는 소규모 그룹으로부터 발생하는 통제되지 않은 트래픽은 과도한 자원을 소비하여 서비스 저하나 연쇄적인 장애를 초래할 수 있습니다. 속도 제한(Rate Limiting)은 특정 시간 간격 내에 클라이언트가 요청할 수 있는 횟수를 제한함으로써 이를 완화하는 기초적인 메커니즘 역할을 합니다.

핵심 과제는 다음과 같은 상충하는 제약 조건들 사이에서 균형을 맞추는 알고리즘을 선택하는 것입니다:

1. 결정 지연 시간(Decision Latency): 알고리즘은 상수 시간 또는 근사 상수 시간에 수락/거부 여부를 계산해야 합니다.
2. 메모리 점유율(Memory Footprint): 클라이언트당 상태 추적은 제한되어야 합니다.
3. 분산 일관성(Distributed Consistency): 메커니즘은 여러 서버에 걸쳐 복제될 때 올바르게 작동해야 하며, 이는 종종 공유 데이터 저장소나 최종 일관성 근사치를 필요로 합니다.
4. 버스트 허용(Burst Tolerance) 대 정밀도(Precision): 서로 다른 사용 사례(예: 취약한 다운스트림 의존성 보호 vs. 가격 책정 계층 적용)는 트래픽 스파이크와 메모리 오버헤드에 대해 서로 다른 수준의 허용치를 요구합니다.

단 하나의 알고리즘이 모든 시나리오에 최적일 수는 없으므로, 버스트 처리, 메모리 비용, 타이밍 정밀도 및 구현 복잡도 간의 트레이드오프에 대한 비교 분석이 필요합니다.

방법론

본 논문은 널리 사용되는 다섯 가지 속도 제한 기법을 비교 조사합니다:

1. 토큰 버킷(Token Bucket): 일정한 속도로 채워지는 컨테이너를 모델링하며, 용량까지 버스트를 허용합니다.
2. 리키 버킷(Leaky Bucket): 요청 시 카운터를 증가시키고 일정한 속도로 감소시켜, 출력을 부드럽게 만들거나 초과분을 폐기합니다.
3. 고정 윈도우 카운터(Fixed Window Counter): 시간을 이산적인 구간으로 나누고 경계에서 리셋되는 단순 카운터를 사용합니다.
4. 슬라이딩 윈도우 로그(Sliding Window Log): 정확한 계수를 위해 트레일링 윈도우 내의 모든 요청에 대한 타임스탬프를 저장합니다.
5. 슬라이딩 윈도우 카운터(Sliding Window Counter): 현재 및 이전 윈도우의 가중치 추정치를 사용하여 로그의 정확도를 상수 메모리로 근사하는 절충안입니다.

실험적 평가:
이론적 질적 분석을 넘어, 저자는 다섯 가지 알고리즘을 모두 Python으로 구현하고 동일한 합성 트래픽 트레이스(Synthetic Traffic Trace)를 대상으로 평가했습니다.

• 구성: 모든 알고리즘은 지속적인 속도 제한을 초당 10회(10 requests/second)로 설정되었습니다. 토큰 및 리키 버킷은 버스트 용량 20을 포함했습니다. 윈도우 기반 알고리즘은 1초 윈도우를 사용했습니다.
• 트래픽 트레이스: 포아송 과정(기본 8 req/s)을 생성된 100초 길이의 트레이스에 두 번의 인위적인 버스트 이벤트를 포함했습니다:
  • 버스트 1: 5초 동안 40 req/s (194 requests).
  • 버스트 2: 2초 동안 60 req/s (125 requests).
• 지표: 연구에서는 수락률(Acceptance Rates), 피크 순간 처리량(Peak Instantaneous Throughput), 그리고 특정 버스트 처리 동작을 측정했습니다.

주요 기여 및 결과

1. 승인 미터로서의 토큰 버킷과 리키 버킷의 등가성

실험 결과, **토کن 버킷(Token Bucket)**과 **리키 버킷(Leaky Bucket)**은 트레이스의 모든 요청에 대해 동일한 수락/거부 결정을 생성함을 입증했습니다.

• 발견: 매칭되는 용량과 속도를 가진 순수 승인 미터(Admission Meter)로 사용될 때, 두 알고리즘은 수학적으로 동일합니다. 리키 버킷의 "수위(Level)"와 토큰 버킷의 "미사용 용량(Unused Capacity)"은 상보적인 양입니다.
• 차이점: 두 알고리즘은 리키 버킷이 출력 타이밍을 부드럽게 하기 위한 큐잉(Queuing) 형태로 사용될 때만 갈라지며, 본 연구의 수락/거부 모델에서는 이러한 동작이 포착되지 않습니다.
• 성능: 두 알고리즘 모두 버스트 동안 가장 높은 트래픽 볼륨을 수락했으며(79.8% 수락률), 구성된 버스트 허용치를 직접 활용하여 29 req/s의 피크 순간 처리량에 도달했습니다.

2. 슬라이딩 윈도우 로그의 정밀도

**슬라이딩 윈도우 로그(Sliding Window Log)**는 설정된 한도를 초과하는 것에 대해 허용 오차가 전혀 없는 유일한 알고리즘으로 식별되었습니다.

• 발견: 어떤 1초 윈도우에서도 10개 이상의 요청을 수락하지 않았으며, 설계 보증을 엄격히 준수했습니다.
• 트레이드오프: 이러한 엄격함은 가장 낮은 전체 수락률(67.9%)과 가장 높은 메모리 오버헤드($O(n)$ per client, 모든 요청에 대한 타임스탬프를 저장해야 함)라는 대가를 치렀습니다.

3. 윈도우 기반 카운터의 성능

**고정 윈도우(Fixed Window)**와 슬라이딩 윈도우 카운터(Sliding Window Counter) 알고리즘은 버킷 알고리즘과 슬라이딩 윈도우 로그 사이의 예측 가능한 중간 지점에 위치했습니다.

• 고정 윈도우: 윈도우 경계에서 의도된 속도의 최대 두 배까지 허용하는 가장 큰 경계 버스트 아티팩트(Boundary-burst artifact)를 보여주었습니다(피크 15 req/s). 구현 복잡성과 메모리 비용은 가장 낮았으나 정확도(73.3% 수락률)는 가장 낮았습니다.
• 슬라이딩 윈도우 카운터: 로그의 정확도를 상수 메모리($O(1)$)로 근사하는 중간 지점을 제공했습니다. 71.1%의 수락률과 13 req/s의 피크를 달성하며, 고정 윈도우에서 나타나는 경계 효과를 부분적으로 교정했습니다.

의의 및 가이드라인

본 논문은 "최적의" 알고리즘은 보편적이지 않으며, 전적으로 특정 시스템의 제약 조건과 트래픽 패턴에 달려 있다고 결론짓습니다:

• 버스트 흡수(Burst Absorption)를 위해: 일반적인 API 속도 제한에는 **토کن 버킷(Token Bucket)**을 권장합니다. 이는 장기적인 평균을 강제하면서도 가장 높은 수락률을 유지하며 버스트 허용과 단순함 사이의 최적의 균형을 제공합니다. 이는 주요 프로덕션 라이브러리(예: Bucket4j)의 사실상 표준(De facto standard)입니다.
• 엄격한 다운스트림 보호를 위해: 취약한 의존성을 보호하기 위해 순간적인 부하에 대한 하드한 무조건적 상한선이 목표라면, 높은 메모리 비용에도 불구하고 스파이크가 발생하지 않음을 보장하는 **슬라이딩 윈도우 로그(Sliding Window Log)**가 우수합니다.
• 일정한 출력 속도를 위해: 다운스트림 소비자에게 엄격하게 비(非)버스트형 요청 속도를 제공해야 하는 시스템은 큐잉 형태의 **리키 버킷(Leaky Bucket)**을 사용해야 합니다.
• 자원 제약 환경을 위해: 정확한 집행이 필요하지만 전체 로그의 메모리 비용이 부담스러운 경우에는 **슬라이딩 윈도우 카운터(Sliding Window Counter)**가 합리적인 절충안이 됩니다.

저자는 선택이 단일 기본 알고리즘에 의존하는 것이 아니라, 측정된 트래픽 특성(예: 버스트 빈도), 지연 시간 예산, 그리고 일관성 요구사항에 의해 결정되어야 함을 강조합니다. 본 연구는 이론적 트레이드오프가 존재함에도 불구하고, 실증적 테스트를 통해 이 알고리즘들이 실제 버스트 시나리오를 처리하는 방식에서 뚜렷한 행동 차이가 있음을 검증합니다.