Rate Limiter 설계 — 알고리즘보다 분산 환경이 어렵다

알고리즘 자체는 30분 문제가 아니다

Rate Limiter를 설계하라고 하면 대부분 토큰 버킷이나 슬라이딩 윈도우 같은 알고리즘 이름을 꺼내는 데서 시작합니다. 알고리즘을 아는 건 필요조건이지 충분조건이 아닙니다. 이 문제의 진짜 난이도는 알고리즘이 아니라 "그 알고리즘의 카운터를 여러 대의 서버가 공유해야 한다"는 데서 나옵니다. 단일 서버라면 이 문제는 사실 5분 안에 끝납니다. 여러 서버, 여러 리전으로 넘어가는 순간 이야기가 완전히 달라집니다.

알고리즘 비교 — 정확도와 메모리의 트레이드오프

import time

class FixedWindowLimiter:
    def __init__(self, limit, window_seconds):
        self.limit = limit
        self.window = window_seconds
        self.counters = {}  # key -> (window_start, count)

    def allow(self, key):
        now = int(time.time())
        window_start = now - (now % self.window)
        entry = self.counters.get(key)
        if entry is None or entry[0] != window_start:
            self.counters[key] = [window_start, 1]
            return True
        if entry[1] < self.limit:
            entry[1] += 1
            return True
        return False


class SlidingWindowLogLimiter:
    def __init__(self, limit, window_seconds):
        self.limit = limit
        self.window = window_seconds
        self.logs = {}  # key -> list of timestamps

    def allow(self, key):
        now = time.time()
        timestamps = self.logs.setdefault(key, [])
        # 윈도우 밖으로 나간 기록 제거
        while timestamps and timestamps[0] <= now - self.window:
            timestamps.pop(0)
        if len(timestamps) < self.limit:
            timestamps.append(now)
            return True
        return False

고정 윈도우(fixed window)는 구현이 단순하고 메모리도 적게 씁니다. 하지만 경계 문제가 있습니다. 1분에 100건 제한이라면, 0분 59초에 100건을 다 쓰고 1분 01초에 또 100건을 쓸 수 있습니다. 2초 사이에 200건이 통과하는 겁니다. 슬라이딩 윈도우 로그는 이 문제를 정확히 해결하지만, 사용자마다 모든 요청 타임스탬프를 들고 있어야 해서 트래픽이 많은 사용자일수록 메모리를 많이 씁니다. 실무에서는 이 둘 사이 절충안인 슬라이딩 윈도우 카운터(이전 윈도우 카운트에 가중치를 줘서 근사)를 많이 씁니다. 어떤 걸 고를지는 "정확도가 얼마나 중요한가 vs 메모리를 얼마나 쓸 수 있는가"의 문제이지, 하나가 항상 우월한 게 아닙니다.

진짜 문제 — 여러 서버가 카운터를 어떻게 공유하는가

로드밸런서 뒤에 서버가 10대 있다고 해봅시다. 각 서버가 자기 메모리에 카운터를 들고 있으면, 사용자의 요청이 매번 다른 서버로 갈 때마다 다른 카운터를 보게 됩니다. 실제로는 사용자당 초당 100건 제한인데 서버 10대에 요청이 고르게 퍼지면 사실상 초당 1,000건까지 통과하는 셈이 됩니다.

flowchart TD
  Client["클라이언트"] --> LB["로드밸런서"]
  LB --> S1["서버 1"]
  LB --> S2["서버 2"]
  LB --> S3["서버 3"]
  S1 --> Redis["Redis: 공유 카운터"]
  S2 --> Redis
  S3 --> Redis

해법은 로드밸런싱 챕터에서 다룬 "상태는 공유 저장소로"라는 원칙을 그대로 적용하는 겁니다. 카운터를 Redis 같은 중앙 저장소에 두고, 모든 서버가 같은 카운터를 보고 판단합니다. 문제는 이제 새로운 형태로 옮겨갑니다. Redis의 INCR 연산이 원자적이긴 하지만, "카운터를 읽고, 비교하고, 증가시키는" 로직 전체를 원자적으로 만들려면 Lua 스크립트나 Redis의 트랜잭션 기능이 필요합니다.

# Redis Lua 스크립트로 read-check-increment를 원자적으로 처리
RATE_LIMIT_SCRIPT = """
local current = redis.call('GET', KEYS[1])
if current and tonumber(current) >= tonumber(ARGV[1]) then
    return 0
end
redis.call('INCR', KEYS[1])
redis.call('EXPIRE', KEYS[1], ARGV[2])
return 1
"""

이 스크립트를 언급하는 것 자체가 핵심은 아닙니다. 중요한 건 "카운터를 여러 서버가 공유하게 만드는 순간, 그 카운터에 대한 연산이 원자적이어야 경쟁 상태(race condition)가 안 생긴다"는 점을 아는 것입니다. 이걸 놓치면 두 요청이 거의 동시에 들어왔을 때 둘 다 카운터가 아직 한도 미만이라고 읽고, 둘 다 통과시켜 실제로는 한도를 넘기는 상황이 생깁니다.

Rate Limiter 자체가 병목이 되면 안 된다

마지막으로 짚을 역설이 있습니다. Rate Limiter는 시스템을 보호하려고 넣는 건데, Redis 하나에 모든 요청이 매번 왕복하면 그 Redis가 새로운 병목이자 새로운 단일 장애점이 됩니다. Redis가 느려지거나 죽으면 어떻게 할지 — "fail open"(제한 없이 통과시킨다)으로 갈지 "fail closed"(전부 막는다)로 갈지 — 도 결정해야 합니다. 저는 보통 fail open을 권합니다. Rate Limiter가 죽었다고 서비스 전체를 막는 건 목적과 수단이 뒤바뀐 것이기 때문입니다. 다만 이건 도메인에 따라 다릅니다. 결제 API처럼 남용이 곧바로 금전적 손실로 이어지는 곳이라면 fail closed가 맞을 수도 있습니다.