Rate Limiting | Thomas Kim

Rate Limiting은 일정 시간 내 허용되는 요청 수를 제한하는 메커니즘이다.

Rate Limiting 은 특히나 대용량 트래픽을 목표로 하는 서버에서는 필수적으로 들어가는 개념이다.

서비스 가용성을 보호하기 위한 안전장치이자, 트롤링도 방지한다.

항시 대용량 트래픽이 있는 서버가 아니더라도 예상치 못한 트래픽 폭주로 비용이 폭주하거나 일시적인 장애가 생기는 것을 방지해준다.

Rate Limit 을 구현하는 몇 가지 알고리즘을 살펴보자.

Token Bucket

일정한 속도로 토큰을 버킷에 추가한다. 요청이 들어오면 토큰 하나를 소비하고, 버킷이 비면 요청을 거부한다.
미사용 토큰은 버킷 용량까지 축적된다.

flowchart LR
    Refill[일정한 속도로 토큰 충전] --> Bucket[버킷<br/>최대 용량 = Burst 크기]
    Request[요청] --> Check{토큰이 남았는가?}
    Check -->|예| Consume[토큰 소비 → 통과]
    Check -->|아니오| Reject[429 Too Many Request]
    Bucket --> Check

축적된 토큰으로 순간적인 트래픽 급증을 처리할 수 있는 기법이다.

장기적으로 토큰 충전 속도에 트래픽 처리량이 수렴하게 된다.

토큰 충전 속도를 Rate, 버킷 용량을 Burst Size 라고 한다.

장점	단점
버스트 트래픽 유연하게 처리	Token count + last refill time 추적 필요
API Rate Limiting에 가장 적합	순간 버스트가 다운스트림을 압도할 수 있음

Leaky Bucket

요청은 고정된 속도로만 처리된다. 버킷이 가득 차면 새 요청은 버려진다. (물이 새는 양동이처럼)

flowchart TB
    Request[요청 유입] --> Bucket["버킷 (큐)<br/>고정 용량"]
    Bucket --> Process["처리<br/>(고정 속도)"]
    Bucket -->|초과| Drop[버림]

Token Bucket과의 차이

항목	Token Bucket	Leaky Bucket
출력 속도	가변 (버스트 가능)	고정
초과 요청	즉시 거부	큐에 대기 또는 즉시 거부

Fixed Window Counter

시간을 고정 구간으로 나누고, 각 구간에서 요청 수를 카운트한다. 구간이 바뀌면 카운터가 리셋된다.

경계 문제 (Boundary Problem)

이 알고리즘의 치명적 약점이다. 윈도우 경계에서 요청을 집중시키면 제한의 2배까지 통과할 수 있다.

flowchart LR
    subgraph "11:59"
        A["11:59:50~59<br/>100건 요청"]
    end
    subgraph "12:00"
        B["12:00:00~10<br/>100건 요청"]
    end
    A -->|"20초 사이<br/>200건 통과"| B

Sliding Window Log

모든 요청의 정확한 타임스탬프를 기록한다. 새 요청이 오면 윈도우 밖의 오래된 기록을 삭제하고, 남은 기록 수로 제한 여부를 판단한다.

어떻게 보면 가장 정확한 Rate Limiting 기법이다. 또한 많이 쓰이기도 한다.

Redis 의 Sorted Set 자료구조를 사용해서 구현하는 사례가 많다.

ZREMRANGEBYSCORE: 윈도우 밖 기록 삭제
ZCARD: 현재 기록 수 확인
ZADD: 새 요청 타임스탬프 추가

Sliding Window Counter

이전 윈도우와 현재 윈도우의 카운터를 가중 평균하여 경계 문제를 완화한다.

만약 현재 윈도우 진행률이 30%라면:

가중 카운트 = (이전 윈도우 카운트 × 70%) + (현재 윈도우 카운트 × 100%)