←

Distributed Rate Limiter

System Design

Understand it step by step (한국어로 이해 → 영어로 말하기)

여러 대의 API 서버 앞에서 클라이언트별로 요청 속도를 제한해야 한다. 예를 들어 "사용자당 초당 100건"을 넘으면 429(Too Many Requests)를 돌려준다. 서버가 50대로 흩어져 있어도 카운트가 한 곳처럼 합쳐져야 하고, 이 판단은 모든 요청마다 1~2ms 안에 끝나야 한다.
  1. 1

    핵심 기능: (1) 클라이언트(user_id 또는 API key)별 요청 수를 세서 한도를 넘으면 거절한다. (2) 한도 초과 시 429와 Retry-After 헤더를 준다. (3) 규칙은 동적으로 바꿀 수 있다(무료 100 req/s, 유료 1000 req/s). 비기능: 정확성보다 '가용성과 낮은 지연'이 우선. 레이트 리미터가 느리거나 죽으면 모든 API가 같이 죽으므로, 약간 새는(살짝 초과 허용) 한이 있어도 빨라야 하고, 카운트 저장소가 죽으면 'fail-open'으로 통과시킨다.

    ⚖️ Trade-off: 강한 일관성(정확히 100건)을 고집하면 분산 락이 필요해 지연이 커진다. 그래서 약간의 오차(101~105건 통과)를 받아들이고 가용성과 속도를 택한다.

    🔧 도구:RedisHTTP 429

    🗣 영어로 말해

    “Availability and low latency matter more than counting exactly; we tolerate a small overshoot.”

    checking microphone…

  2. 2

    규모 추정: 전체 1,000,000 req/s (피크) 가정. 모든 요청이 리미터를 거치니 리미터 QPS = API QPS = 1M/s. 활성 클라이언트 1,000만 명, 키 하나당 카운터 약 50바이트 → 약 500MB, 메모리에 충분히 들어간다. 읽기:쓰기 비율은 거의 1:1 (요청마다 카운터를 읽고 INCR로 1 증가). 핵심은 데이터 크기가 아니라 1M/s의 쓰기 트래픽과 1~2ms 지연이다.

    🔧 도구:RedisINCR

    🗣 영어로 말해

    “About one million requests per second, roughly one read and one write each, fits in memory.”

    checking microphone…

  3. 3

    API와 데이터 모델: 리미터는 별도 엔드포인트가 아니라 API 게이트웨이 안의 미들웨어로 동작한다. 내부 호출은 allow(key, rule) → {allowed, remaining, retry_after}. 저장 모델은 키-값: key = rate:{rule_id}:{client_id}:{window}, value = 현재 카운트(정수). 파티션 키는 client_id라 같은 클라이언트의 카운트가 한 샤드에 모인다. 규칙은 별도 테이블(rule_id, limit, window_sec)에 두고 캐싱한다.

    🔧 도구:RedisAPI Gatewayconsistent hashing

    // gateway middleware
allow(key, rule) -> { allowed: bool, remaining: int, retry_after: int }

// redis key shape
rate:{rule_id}:{client_id}:{window_ts} = <count:int>  // TTL = window_sec
    🗣 영어로 말해

    “The key is client id plus rule plus time window, and the value is just the current count.”

    checking microphone…

  4. 4

    상위 설계: 클라이언트 → 로드밸런서 → API 게이트웨이(여기에 리미터 미들웨어) → 백엔드 서비스. 흐름은: 요청이 게이트웨이에 도착하면 미들웨어가 Redis에 카운터를 올리고(INCR), 한도 이하면 백엔드로 보내고, 넘으면 즉시 429를 돌려준다. 카운트 저장소는 중앙 Redis 클러스터(샤딩)로 둬서 게이트웨이 50대가 같은 숫자를 본다. 규칙 변경은 관리 API → 설정 저장소 → 게이트웨이가 몇 초마다 폴링/구독.

    ✅ Fix: 게이트웨이 로컬 메모리로만 세면 50대가 각자 100건씩 허용해 합쳐서 5000건이 새므로, 카운터는 중앙 Redis에 둬서 모든 게이트웨이가 한 숫자를 공유한다.

    🔧 도구:Redis ClusterAPI GatewayLoad Balancer

    🗣 영어로 말해

    “The gateway increments a counter in shared Redis and rejects with 429 when the limit is exceeded.”

    checking microphone…

  5. 5

    딥다이브 1 — 알고리즘과 원자성: 단순 고정 윈도우(매 초 0으로 리셋)는 경계에서 폭주한다(0.9초에 100건 + 1.1초에 100건 = 0.2초에 200건). 그래서 슬라이딩 윈도우나 토큰 버킷을 쓴다. 분산에서 가장 중요한 건 '읽고-비교하고-증가'가 한 번에 원자적으로 일어나는 것. Redis Lua 스크립트로 INCR + TTL + 한도 비교를 하나의 원자 연산으로 묶어 race condition(두 게이트웨이가 동시에 99→100 통과)을 막는다.

    ⚖️ Trade-off: 토큰 버킷은 버스트(짧은 폭주)를 허용해 유연하지만 구현이 조금 복잡하다. 고정 윈도우는 단순하지만 경계 폭주가 있다. 슬라이딩 윈도우 로그는 정확하지만 메모리를 많이 쓴다.

    ✅ Fix: Redis Lua 스크립트(EVAL)로 카운트 증가와 한도 검사를 원자적으로 처리하고, 알고리즘은 슬라이딩 윈도우 카운터를 써서 경계 폭주를 누른다.

    🔧 도구:Redis Lua (EVAL)token bucketsliding window counter

    -- atomic check-and-increment (Lua, runs on Redis)
local c = redis.call('INCR', KEYS[1])
if c == 1 then redis.call('EXPIRE', KEYS[1], ARGV[2]) end
if c > tonumber(ARGV[1]) then return 0 end  -- reject
return 1  -- allow
    🗣 영어로 말해

    “I use a Redis Lua script so increment and limit-check happen atomically, avoiding race conditions.”

    checking microphone…

  6. 6

    딥다이브 2 — 핫 키와 Redis 부하: 인기 클라이언트(대형 파트너 API 키) 하나가 초당 수십만 건을 쏘면 그 키의 샤드 하나만 과부하된다(핫 키). 또 모든 요청이 Redis 왕복(0.5ms)을 하면 1M/s 네트워크 부하가 크다. 해결: 게이트웨이마다 로컬 메모리에 토큰을 미리 한 묶음 받아두고(예: 1초치를 10조각으로) 로컬에서 차감, 다 쓰면 Redis에서 다음 묶음을 가져온다. 이러면 Redis 호출이 1/N로 줄고 지연도 마이크로초 단위가 된다.

    ⚖️ Trade-off: 로컬 배치(local token bucket)는 Redis 호출을 줄이지만, 한도가 약간 더 새고(각 게이트웨이가 가진 잔여 토큰만큼) 규칙 변경 반영이 한 묶음만큼 늦어진다.

    ✅ Fix: 핫 키는 게이트웨이 로컬 캐시 + 배치 토큰 가져오기로 Redis 왕복을 줄이고, 샤드 핫스팟은 client_id 해시 샤딩 + 인기 키를 여러 슬롯으로 분산(key splitting)해서 푼다.

    🔧 도구:local token bucketRedis Cluster shardingkey splitting

    🗣 영어로 말해

    “Each gateway pulls tokens in batches into local memory, cutting Redis round-trips for hot keys.”

    checking microphone…

  7. 7

    트레이드오프 + 모니터링: 포기한 것 — (1) 완벽한 정확성(로컬 배치와 비원자 폴백 때문에 한도를 살짝 초과 허용). (2) 강한 일관성(eventual하게 카운트가 맞춰짐). 운영 결정: Redis가 죽으면 'fail-open'(통과)으로 가서 리미터가 전체 장애를 만들지 않게 한다(단, 어뷰징 위험은 알람). 모니터링: 429 비율, 클라이언트별 거절 수, Redis p99 지연/메모리/핫 키, 게이트웨이→Redis 타임아웃 비율, fail-open 발동 횟수를 본다.

    ⚖️ Trade-off: fail-open은 가용성을 지키지만 장애 중 어뷰저가 무제한 통과할 수 있다. 보안이 중요한 엔드포인트(로그인 등)는 반대로 'fail-closed'로 막는 식으로 엔드포인트별로 다르게 설정한다.

    ✅ Fix: 대부분 엔드포인트는 fail-open, 인증/결제 같은 민감 엔드포인트는 fail-closed로 정책을 분리하고, fail-open 발동을 알람으로 즉시 감지한다.

    🔧 도구:PrometheusGrafanafail-open / fail-closed

    🗣 영어로 말해

    “We watch the 429 rate, Redis p99 latency, and how often we fail open during outages.”

    checking microphone…

7단계 영어를 다 말하면 → 이 메커니즘 전체를 영어로 설명할 수 있게 된다.

🎙 이 카드 AI랑 음성 대화 · 기록 저장