복잡도

레이트 리미터는 모든 요청 앞에서 실행되므로, 한 번의 판정이 얼마나 빠른지와 키 하나가 얼마나 많은 메모리를 쓰는지가 곧 서비스 비용이 됩니다. 이 장에서는 다섯 알고리즘의 시간·공간 복잡도와 정확도, 버스트 처리 방식을 비교합니다. 아래에서 L은 창 하나의 한도, K는 활성 키의 수입니다.

요청 하나를 판정하는 시간

• 고정 창: 창 번호를 계산하고 카운터 하나를 올립니다. O(1)입니다.
• 슬라이딩 창 로그: 창 밖으로 나간 기록을 앞에서 버린 뒤 개수를 셉니다. deque를 쓰면 기록 하나는 한 번만 들어가고 한 번만 나가므로 분할 상환 O(1)이지만, 한 번의 호출에서는 최악 O(L)개를 버릴 수 있습니다. Redis 정렬 집합(sorted set)으로 구현하면 추가와 범위 삭제에 O(log n)이 듭니다.
• 슬라이딩 창 카운터: 곱셈 한 번과 덧셈 한 번입니다. O(1)입니다.
• 토큰 버킷: 경과 시간 × rate를 더하고 비교합니다. O(1)입니다.
• 리키 버킷(큐): 넣기와 꺼내기가 각각 O(1)입니다.

키 하나가 쓰는 메모리

전체 메모리는 여기에 활성 키 수 K를 곱합니다. 한도가 "시간당 10,000번"이고 활성 사용자가 10만 명이면, 슬라이딩 창 로그는 최악의 경우 시각 10억 개를 저장해야 합니다. 같은 상황에서 토큰 버킷은 숫자 20만 개면 됩니다. 이 차이 때문에 대규모 서비스는 로그 방식을 거의 쓰지 않습니다.

def worst_case_bytes(keys: int, limit: int, bytes_per_number: int = 8) -> dict[str, int]:
    return {
        "fixed_window": keys * 2 * bytes_per_number,
        "sliding_log": keys * limit * bytes_per_number,
        "sliding_counter": keys * 3 * bytes_per_number,
        "token_bucket": keys * 2 * bytes_per_number,
    }


for name, size in worst_case_bytes(keys=100_000, limit=10_000).items():
    print(f"{name:16} {size / 2**20:10.1f} MiB")
# sliding_log 은 약 7,629 MiB, 나머지는 몇 MiB 수준

실제 메모리는 언어와 저장소의 부가 비용 때문에 이보다 큽니다. 그래도 크기의 차수는 그대로입니다.

정확도와 버스트

토큰 버킷의 상한은 공식으로 바로 계산됩니다. 버킷이 가득 찬 상태에서 시작하면 길이 T 동안 최대 capacity + rate × T개가 통과합니다. 그래서 "평균 초당 10개, 최대 버스트 20개"처럼 두 숫자로 설정합니다.

def max_admitted(rate: float, capacity: float, seconds: float) -> int:
    # 가득 찬 버킷에서 시작해 seconds 동안 통과할 수 있는 최대 요청 수
    return int(capacity + rate * seconds)


print(max_admitted(rate=10, capacity=20, seconds=1))    # 30
print(max_admitted(rate=10, capacity=20, seconds=60))   # 620

고정 창 경계 문제를 숫자로 확인하기

다음 코드는 경계 바로 앞뒤로 요청을 보냈을 때 고정 창과 슬라이딩 창 로그가 각각 몇 개를 허용하는지 셉니다.

from collections import deque


def fixed_window(times, limit, window):
    counts = {}
    ok = 0
    for t in times:
        w = int(t // window)
        counts[w] = counts.get(w, 0) + 1
        ok += counts[w] <= limit
    return ok


def sliding_log(times, limit, window):
    log, ok = deque(), 0
    for t in times:
        while log and log[0] <= t - window:
            log.popleft()
        if len(log) < limit:
            log.append(t)
            ok += 1
    return ok


burst = [59.5] * 5 + [60.5] * 5        # 경계 앞뒤로 5번씩
print(fixed_window(burst, 5, 60))      # 10
print(sliding_log(burst, 5, 60))       # 5

분산 환경의 비용

여러 서버가 한도를 나눠 쓰면 판정마다 Redis 같은 공유 저장소에 한 번 다녀와야 합니다. 이때 비용은 알고리즘의 O(1)보다 네트워크 왕복 시간(보통 수백 마이크로초에서 수 밀리초)이 지배합니다. 그래서 명령 여러 개를 Lua 스크립트 하나로 묶어 왕복을 한 번으로 줄이고, 아주 큰 트래픽에서는 서버마다 로컬 버킷을 두고 공유 저장소와는 주기적으로만 맞추기도 합니다. 후자는 정확도를 조금 내주고 지연 시간을 얻는 선택입니다.

정리

• 고정 창, 슬라이딩 창 카운터, 토큰 버킷은 시간과 키당 공간이 모두 O(1)입니다.
• 슬라이딩 창 로그는 정확하지만 키당 O(L) 메모리가 들어 대규모에는 부담입니다.
• 토큰 버킷은 길이 T 동안 최대 capacity + rate × T개를 허용합니다.
• 분산 환경에서는 알고리즘보다 네트워크 왕복이 비용을 결정합니다.