Leaky Bucket 알고리즘

Nginx는 대규모 트래픽을 효율적으로 처리하기 위해 Leaky Bucket 알고리즘을 사용해 처리량을 제한한다.

Leaky Bucket의 핵심 개념

양동이 비유로 이해하기

들어오는 요청 = 양동이에 물을 붓는 것
처리되는 요청 = 구멍으로 일정한 속도로 물이 빠져나가는 것
버스트(burst) = 양동이의 크기 (일시적으로 담을 수 있는 최대 용량)
양동이 overflow = 요청 거부 (503 에러)

시간에 따른 동작 과정

rate = 10 r/s, burst = 20, nodelay=off 일 때, 다음과 같이 동작한다:

왜 Nginx는 Leaky Bucket을 선택했을까?

1. 예측 가능한 부하

웹 서버는 안정적이고 예측 가능한 성능이 중요하다. Leaky Bucket은 출력 속도가 일정하므로 서버 부하를 정확히 예측할 수 있다.

2. 메모리 효율성

클라이언트마다 단 하나의 노드만 유지하면 된다. 토큰을 계속 생성/소비할 필요가 없어 메모리 효율적이다.

3. 구현의 단순성

핵심 공식 하나로 모든 것이 해결된다:


excess = lr->excess - ctx->rate * ms / 1000 + 1000;

이 단순함은 버그 발생 가능성 감소, 유지보수 용이성, 성능 최적화로 이어진다.

Leaky Bucket 핵심 공식의 의미


excess = previous_excess - (rate × time_elapsed / 1000) + 1000
         └─────────────┘   └──────────────────────────┘   └──┘
            이전 누적량             시간에 따른 "누출"          현재 요청

단계별 계산 예시 (rate=10r/s, burst=20)

t=0초: 첫 요청


excess = 0 - (10000 × 0 / 1000) + 1000 = 1000
양동이: 1/20 => 허용

t=0.1초: 5개 요청 동시 도착


요청 1: excess = 1000 - (10000 × 100 / 1000) + 1000 = 1000
요청 2: excess = 1000 - (10000 × 0 / 1000) + 1000 = 2000
요청 3: excess = 2000 - (10000 × 0 / 1000) + 1000 = 3000
요청 4: excess = 3000 - (10000 × 0 / 1000) + 1000 = 4000
요청 5: excess = 4000 - (10000 × 0 / 1000) + 1000 = 5000

양동이: 5/20 => 모두 허용

t=0.2초: 20개 요청 동시 도착


요청 1: excess = 5000 - (10000 × 100 / 1000) + 1000 = 5000
요청 2: excess = 5000 - (10000 × 0 / 1000) + 1000 = 6000
요청 3: excess = 6000 - (10000 × 0 / 1000) + 1000 = 7000
요청 4~16: excess가 계속 증가... = 20000
요청 17: excess = 20000 + 1000 = 21000 > burst(20000) => 거부!