동작 원리

이 장에서는 작은 예제를 따라가며 다섯 알고리즘이 요청을 어떻게 허용하고 거절하는지 한 단계씩 살펴봅니다. 같은 문제를 서로 다르게 푸는 방식을 비교하면, 어느 상황에 어떤 알고리즘이 맞는지 감이 잡힙니다.

고정 창과 경계 문제

한도가 "1분에 5번"인 고정 창은 시각을 60으로 나눈 몫(창 번호)마다 카운터를 셉니다. 창이 바뀌면 카운터는 0부터 다시 시작합니다. 문제는 창의 경계입니다.

0:59부터 1:01까지 약 2초 사이에 10번이 허용되었습니다. 어떤 60초 구간을 잡아도 5번을 넘지 않기를 바랐다면 한도의 두 배가 통과한 셈입니다. 이 약점을 고치는 것이 슬라이딩 창입니다.

슬라이딩 창 로그

허용한 요청의 시각을 큐(deque)에 쌓아 두고, 요청이 올 때마다 창 밖으로 나간 오래된 시각을 앞에서 버린 뒤 남은 개수를 셉니다. 한도는 "10초에 3번"으로 둡니다.

창을 (지금 - 10초, 지금]으로 보므로 시각 11에서는 1이 빠집니다. 어떤 10초 구간에서도 3번을 넘지 않으므로 정확합니다.

from collections import deque


def sliding_log(times: list[float], limit: int, window: float) -> list[bool]:
    log: deque[float] = deque()
    result = []
    for now in times:
        while log and log[0] <= now - window:
            log.popleft()                 # 창 밖으로 나간 기록 버리기
        if len(log) < limit:
            log.append(now)               # 허용한 요청만 기록
            result.append(True)
        else:
            result.append(False)
    return result


print(sliding_log([1, 2, 3, 5, 11, 12], limit=3, window=10))
# [True, True, True, False, True, True]

슬라이딩 창 카운터

로그 대신 카운터 두 개(직전 창, 현재 창)만 둡니다. 직전 창의 요청이 고르게 퍼져 있었다고 가정하고, 지금 시각에서 거꾸로 60초를 잡았을 때 직전 창이 겹치는 비율만큼만 셉니다.

추정치 = 직전 창 횟수 × (1 - 현재 창에서 지난 시간 / 창 길이) + 현재 창 횟수

한도가 "60초에 10번", 직전 창(0~60초)에 8번, 현재 창(60~120초)에 지금까지 3번이 있었다고 합시다.

시간이 흐를수록 직전 창의 영향이 줄어들어 자연스럽게 다시 허용됩니다. 직전 창 요청이 한쪽에 몰려 있었다면 추정이 조금 틀릴 수 있지만, 키마다 숫자 두 개만 저장하면 됩니다.

토큰 버킷

버킷에 초당 rate개씩 토큰이 차고, 최대 capacity개까지만 담깁니다. 요청은 토큰 1개를 꺼내 쓰고, 토큰이 1개 미만이면 거절됩니다. 토큰을 실제로 매초 채우는 타이머는 필요 없습니다. 요청이 올 때 "마지막으로 본 뒤 지난 시간 × rate"만큼 한꺼번에 더하면 됩니다(게으른 리필).

rate = 초당 1개, capacity = 3으로 따라가 보겠습니다.

처음에는 버킷이 가득 차 있어 0.4초 안에 3번(버스트)이 통과하고, 그 뒤로는 초당 1번 속도로 맞춰집니다. 오래 쉬면 토큰이 다시 차서 다음 버스트를 받아 줍니다.

def token_bucket(times: list[float], rate: float, capacity: float) -> list[bool]:
    tokens, last = capacity, times[0] if times else 0.0
    result = []
    for now in times:
        tokens = min(capacity, tokens + (now - last) * rate)   # 게으른 리필
        last = now
        if tokens >= 1:
            tokens -= 1
            result.append(True)
        else:
            result.append(False)
    return result


print(token_bucket([0, 0.2, 0.4, 0.6, 1.5, 3.5, 3.6, 3.7], rate=1, capacity=3))
# [True, True, True, False, True, True, True, False]

리키 버킷

리키 버킷은 바닥에 구멍 난 양동이에 비유합니다. 들어온 요청은 크기가 정해진 큐에 쌓이고, 처리기는 큐에서 일정한 속도로 하나씩 꺼내 처리합니다. 큐가 가득 차면 새 요청은 버려집니다. 큐 크기 3, 초당 1개 처리일 때 시각 0에 요청 5개가 한꺼번에 오면 3개는 큐에 들어가고 2개는 거절됩니다. 큐에 들어간 요청은 1초, 2초, 3초에 차례로 처리됩니다.

from collections import deque


def leaky_bucket(arrivals: list[int], queue_size: int, leak_per_tick: int) -> None:
    queue: deque[int] = deque()
    for tick, count in enumerate(arrivals):
        for _ in range(leak_per_tick):           # 먼저 일정한 속도로 내보내고
            if queue:
                print(f"t={tick}: 요청 {queue.popleft()} 처리")
        for i in range(count):                   # 새 요청은 자리가 있을 때만 받는다
            if len(queue) < queue_size:
                queue.append(tick * 100 + i)
            else:
                print(f"t={tick}: 요청 {tick * 100 + i} 거절")


leaky_bucket([5, 0, 0, 0], queue_size=3, leak_per_tick=1)

토큰 버킷과 달리 처리 속도가 절대 rate를 넘지 않으므로 뒤쪽 시스템을 일정한 속도로 보호할 때 알맞습니다. 대신 큐에서 기다리는 만큼 응답이 늦어집니다. 참고로 큐 없이 "들어온 양을 재는" 방식의 리키 버킷(meter)은 수학적으로 토큰 버킷과 같은 판정을 내립니다.

정리

• 고정 창은 단순하지만 창 경계에서 한도의 두 배까지 통과할 수 있습니다.
• 슬라이딩 창 로그는 정확하고, 슬라이딩 창 카운터는 숫자 두 개로 이를 근사합니다.
• 토큰 버킷은 용량만큼의 버스트를 허용하면서 평균 속도를 지킵니다.
• 리키 버킷은 큐로 출력을 고르게 펴지만 대기 시간이 생깁니다.