Rate Limiting 알고리즘: 토큰 버킷부터 슬라이딩 윈도우까지

왜 rate limit 인가

API 앞단에 요청 빈도 제한을 두는 이유는 하나가 아니다. 여러 동기가 겹쳐서 결국 모든 진지한 서비스가 어떤 형태로든 rate limit 을 둔다.

• 남용·DoS 완화: 한 클라이언트가 비정상적으로 많은 요청을 쏟아붓는 상황을 막는다. 의도적 공격(크리덴셜 스터핑, 스크래핑, L7 DoS)뿐 아니라, 버그로 무한 재시도에 빠진 정상 클라이언트도 같은 방식으로 차단된다.
• 비용 보호: 요청 하나가 곧 비용인 구간이 있다. LLM 추론, 외부 결제 API 중계, 이미지 처리, 콜드 스토리지 조회처럼 호출당 단가가 큰 작업은 무제한 호출을 그대로 비용 폭증으로 흡수한다.
• 공정성(fairness): 멀티테넌트 환경에서 한 테넌트가 공용 자원을 독점하면 나머지가 굶는다. 테넌트별 한도는 "시끄러운 이웃(noisy neighbor)" 문제를 격리한다.
• 하위 시스템 보호: API 서버는 수평 확장이 쉬워도 그 뒤의 DB·메시지 큐·서드파티 API 는 그렇지 않다. 앞단에서 유입 속도를 깎아 두지 않으면 트래픽 스파이크가 그대로 하위 시스템 과부하로 번진다. rate limit 은 일종의 부하 차단기(load shedding)다.

핵심은 "요청을 받을지 말지"를 시간당 허용량으로 환산해 결정하는 것이다. 이 환산을 어떻게 하느냐가 알고리즘의 차이다. 아래에서 다섯 가지를 동작·트레이드오프 순으로 본다.

Fixed window counter

가장 단순한 방식. 시간을 고정 길이 창(예: 1분)으로 자르고, 창마다 카운터를 둔다. 요청이 오면 현재 창의 카운터를 증가시키고, 한도를 넘으면 거부한다. 창이 바뀌면 카운터는 0 으로 리셋된다.

type FixedWindow = { windowStart: number; count: number };
 
const store = new Map<string, FixedWindow>();
const LIMIT = 100;
const WINDOW_MS = 60_000;
 
function allow(key: string, now: number): boolean {
  const windowStart = Math.floor(now / WINDOW_MS) * WINDOW_MS;
  const entry = store.get(key);
 
  if (!entry || entry.windowStart !== windowStart) {
    store.set(key, { windowStart, count: 1 });
    return true;
  }
  if (entry.count < LIMIT) {
    entry.count += 1;
    return true;
  }
  return false;
}

장점: 구현이 가장 쉽고, 메모리는 키당 카운터 하나(정수 한 개)면 된다. 분산 환경에서도 INCR 한 번으로 끝나 원자성 확보가 쉽다.

단점 — 창 경계 버스트: 이게 fixed window 의 결정적 약점이다. 한도가 분당 100 일 때, 어떤 클라이언트가 12:00:59 에 100 개를 보내고 12:01:00 에 다시 100 개를 보내면, 두 요청은 서로 다른 창에 속하므로 둘 다 통과한다. 결과적으로 약 1초 안에 200 개가 들어온다. 즉 경계 부근에서 명목 한도의 2배 버스트가 가능하다. 한도의 목적이 하위 시스템 보호라면 이 2배가 그대로 과부하로 이어질 수 있다.

Sliding window log

경계 버스트를 없애려면 "지금으로부터 과거 1분"이라는 진짜 슬라이딩 구간을 봐야 한다. sliding window log 는 각 요청의 타임스탬프를 전부 기록하고, 매 요청마다 윈도우 밖(now - WINDOW 이전)의 타임스탬프를 버린 뒤 남은 개수가 한도 미만인지 확인한다.

const log = new Map<string, number[]>();
const LIMIT = 100;
const WINDOW_MS = 60_000;
 
function allow(key: string, now: number): boolean {
  const cutoff = now - WINDOW_MS;
  const timestamps = (log.get(key) ?? []).filter((t) => t > cutoff);
 
  if (timestamps.length < LIMIT) {
    timestamps.push(now);
    log.set(key, timestamps);
    return true;
  }
  log.set(key, timestamps);
  return false;
}

장점: 정확하다. 임의의 시점에서 직전 1분 안의 요청 수가 정확히 한도를 넘지 않음을 보장한다. 경계 버스트가 원천적으로 없다.

단점 — 메모리: 키마다 윈도우 안의 모든 타임스탬프를 들고 있어야 한다. 한도가 분당 1만이면 활성 키 하나가 최대 1만 개의 타임스탬프를 쌓는다. 키가 많고 한도가 크면 메모리가 선형으로 폭증한다. Redis 로 구현하면 보통 Sorted Set(ZADD / ZREMRANGEBYSCORE / ZCARD)으로 같은 일을 하는데, 정확한 대신 가장 비싸다.

Sliding window counter

log 의 정확도와 fixed window 의 가벼움 사이의 실용적 타협. 현재 창 카운터와 직전 창 카운터만 유지하고, 직전 창이 현재 슬라이딩 구간에 걸친 비율만큼 가중해 근사한다.

추정 요청 수는 다음과 같다.

estimate = current_count
         + previous_count * (직전 창에서 윈도우에 겹치는 비율)

예를 들어 현재 창에 25% 진입했다면, 직전 1분 중 75% 는 직전 창에 속한다. 그래서 직전 창 카운트의 75% 를 더해 추정한다.

type Counter = { window: number; count: number };
const counters = new Map<string, Counter>();
const LIMIT = 100;
const WINDOW_MS = 60_000;
 
function allow(key: string, now: number): boolean {
  const window = Math.floor(now / WINDOW_MS);
  const elapsed = (now % WINDOW_MS) / WINDOW_MS; // 현재 창 진행 비율 0~1
  const entry = counters.get(key) ?? { window, count: 0 };
 
  let prevCount = 0;
  let curCount = 0;
  if (entry.window === window) {
    curCount = entry.count;
    // prevCount 는 직전 창 카운트 — 실제 구현은 두 칸을 들고 있어야 함
  } else if (entry.window === window - 1) {
    prevCount = entry.count;
  }
 
  const estimate = curCount + prevCount * (1 - elapsed);
  if (estimate < LIMIT) {
    counters.set(key, { window, count: curCount + 1 });
    return true;
  }
  return false;
}

(현실 구현은 현재·직전 두 창 카운트를 동시에 보관한다. 위 예시는 가중 근사식 자체를 강조한 단순화다.)

장점: 메모리는 키당 정수 두 개. 경계 버스트가 fixed window 처럼 2배까지 벌어지지 않고 부드럽게 줄어든다. 정확도와 비용의 균형이 좋아 실무에서 가장 자주 쓰이는 슬라이딩 계열이다. Cloudflare 가 이 근사를 쓴다고 공개한 사례가 잘 알려져 있다.

단점: 근사라서 직전 창 내부의 요청이 균등 분포라고 가정한다. 실제로 직전 창 끝에 요청이 몰려 있었다면 약간 과소·과대 추정이 생긴다. 다만 실측상 오차는 작아서 대부분의 용도에 충분하다.

Token bucket

지금까지가 "구간 안 요청 수 세기"였다면, token bucket 은 발상을 바꾼다. 용량 capacity 의 버킷에 토큰이 일정 속도 refillRate(초당 N 개)로 채워진다. 요청 하나는 토큰 하나(또는 가중치만큼)를 소비한다. 토큰이 있으면 통과·소비, 없으면 거부한다.

type Bucket = { tokens: number; lastRefill: number };
const buckets = new Map<string, Bucket>();
const CAPACITY = 100;
const REFILL_PER_SEC = 10; // 초당 10개 충전 → 평균 10 rps
 
function allow(key: string, now: number, cost = 1): boolean {
  const b = buckets.get(key) ?? { tokens: CAPACITY, lastRefill: now };
 
  // 경과 시간만큼 토큰 보충 (capacity 상한)
  const elapsedSec = (now - b.lastRefill) / 1000;
  b.tokens = Math.min(CAPACITY, b.tokens + elapsedSec * REFILL_PER_SEC);
  b.lastRefill = now;
 
  if (b.tokens >= cost) {
    b.tokens -= cost;
    buckets.set(key, b);
    return true;
  }
  buckets.set(key, b);
  return false;
}

핵심은 lazy refill이다. 백그라운드 타이머로 토큰을 채우는 게 아니라, 요청이 들어온 순간 "마지막 리필 이후 흐른 시간 × 충전 속도"만큼 한꺼번에 더해 준다. 그래서 상태는 키당 tokens 와 lastRefill 두 값이면 충분하고, 유휴 키에 비용이 들지 않는다.

장점:

• 버스트 허용 + 평균 유지: 버킷에 토큰이 쌓여 있으면 순간적으로 capacity 만큼 몰아 쓸 수 있다(버스트). 하지만 장기적으로는 충전 속도가 처리율의 상한이라 평균 rps 가 refillRate 로 수렴한다. "평소엔 여유롭게, 순간엔 버스트 허용, 그러나 평균은 통제"라는 대부분의 API 가 원하는 동작과 정확히 맞는다.
• 가중 비용(cost)을 자연스럽게 표현한다. 무거운 엔드포인트는 토큰을 더 소비하게 만들면 된다.
• 상태가 작고 lazy refill 이라 분산 구현이 깔끔하다.

단점: 버스트를 허용하므로 출력이 완전히 평탄하지 않다. capacity 만큼의 순간 스파이크가 하위 시스템에 부담이면 capacity 를 낮추거나 leaky bucket 으로 가야 한다. 그래서 token bucket 은 가장 널리 쓰이는 기본값이지만 만능은 아니다.

Leaky bucket

token bucket 과 자주 헷갈리지만 목적이 반대다. token bucket 은 입력 측에서 토큰 유무로 통과를 결정하고 버스트를 허용한다. leaky bucket(as a queue)은 요청을 큐에 넣고 고정 속도로만 흘려보낸다(누수). 즉 출력 rate 가 항상 일정하다.

type LeakyBucket = { queue: number; lastLeak: number };
const lb = new Map<string, LeakyBucket>();
const CAPACITY = 100; // 큐 최대 길이
const LEAK_PER_SEC = 10; // 초당 10개씩 처리
 
function allow(key: string, now: number): boolean {
  const b = lb.get(key) ?? { queue: 0, lastLeak: now };
 
  // 경과 시간만큼 큐에서 누수
  const leaked = ((now - b.lastLeak) / 1000) * LEAK_PER_SEC;
  b.queue = Math.max(0, b.queue - leaked);
  b.lastLeak = now;
 
  if (b.queue < CAPACITY) {
    b.queue += 1;
    lb.set(key, b);
    return true; // 큐에 자리 있음 → 수용
  }
  lb.set(key, b);
  return false; // 큐 가득 → 거부(overflow)
}

장점 — 출력 평탄화: 하위 시스템 입장에서 유입 속도가 항상 LEAK_PER_SEC 로 일정하다. 트래픽이 아무리 들쭉날쭉해도 처리 속도가 매끄럽게 유지되므로, 일정 속도를 강하게 보장해야 하는 곳(예: 외부 API 의 분당 호출 상한을 깨면 안 되는 프록시, 하드웨어 보호)에 적합하다.

단점: 버스트를 허용하지 않는다. 큐가 차 있으면 순간 여유가 있어도 새 요청은 거부되거나 대기한다. 또 큐를 비동기로 처리하는 형태(요청을 받아 큐잉 후 나중에 처리)로 구현하면 지연(latency)이 늘고 큐 관리 복잡도가 생긴다. 위 예시처럼 "큐 길이를 카운터로만 추적하고 즉시 수용/거부"하는 형태로 쓰면 token bucket 과 동작이 비슷해진다 — 둘의 진짜 차이는 "요청을 버퍼링해 평탄하게 흘려보내느냐"에 있다.

비교

읽는 법: 대부분의 공개 API 는 "평소 버스트는 봐주되 평균을 통제"하므로 token bucket 이 기본값으로 적합하다. "유입을 일정 속도로 깎아 하위 시스템을 보호"가 목적이면 leaky bucket / sliding 쪽이 맞는다. 정밀한 한도 보장이 필요하면 sliding window log 가 가장 정확하지만 메모리 비용을 감수해야 한다.

분산 구현 — Redis

지금까지의 코드는 단일 프로세스의 인메모리 맵을 가정했다. 서버가 여러 대면 각 서버의 로컬 카운터를 합쳐도 전역 한도가 되지 않는다(서버 N 대면 실질 한도가 N 배로 새어 나간다). 한도를 공유 저장소에 둬야 한다. 대개 Redis 다 — 빠르고, 원자적 연산을 제공하며, TTL 로 만료를 맡길 수 있다.

fixed window — INCR + EXPIRE

가장 단순한 분산 카운터. 키를 rl:{식별자}:{창번호} 로 만들고 INCR 한다. 첫 증가일 때만 EXPIRE 로 창 길이만큼 TTL 을 건다.

// 의사: 두 명령을 분리하면 INCR 후 EXPIRE 직전에 죽을 때 TTL 누락 위험이 있다.
// 그래서 보통 Lua 로 원자화한다(아래).
const window = Math.floor(now / WINDOW_MS);
const redisKey = `rl:${id}:${window}`;
const count = await redis.incr(redisKey);
if (count === 1) await redis.expire(redisKey, WINDOW_SEC);
const allowed = count <= LIMIT;

INCR 와 EXPIRE 를 따로 보내면 그 사이에 인스턴스가 죽었을 때 TTL 이 안 걸려 키가 영원히 남는 미세한 경합이 있다. 이래서 다단계 로직은 Lua 스크립트로 묶어 원자적으로 실행한다(Redis 는 스크립트를 단일 명령처럼 원자 실행한다).

Lua — sliding window counter

여러 읽기·계산·쓰기를 한 번에 원자 실행해야 정확하다. 아래는 sliding window counter 를 Lua 로 옮긴 예다. KEYS 로 현재·직전 창 키를, ARGV 로 한도·창길이·진행비율을 받는다.

-- KEYS[1] = 현재 창 카운터 키
-- KEYS[2] = 직전 창 카운터 키
-- ARGV[1] = limit
-- ARGV[2] = window_ttl_seconds (현재 창 만료)
-- ARGV[3] = elapsed_ratio (현재 창 진행 비율 0~1)
local cur  = tonumber(redis.call('GET', KEYS[1]) or '0')
local prev = tonumber(redis.call('GET', KEYS[2]) or '0')
local limit = tonumber(ARGV[1])
local ratio = tonumber(ARGV[3])
 
-- 직전 창의 (1 - 진행비율) 만큼 가중해 추정
local estimate = cur + prev * (1 - ratio)
 
if estimate >= limit then
  return 0  -- 거부
end
 
local newCount = redis.call('INCR', KEYS[1])
if newCount == 1 then
  redis.call('EXPIRE', KEYS[1], tonumber(ARGV[2]))
end
return 1     -- 허용

Lua — token bucket

token bucket 을 Redis 로 옮기면 키 하나에 tokens 와 last_refill 두 필드를 둔다(Hash 또는 직렬화). 요청마다 경과 시간으로 lazy refill 하고, 토큰이 있으면 차감한다. 읽기→계산→쓰기를 원자화해야 두 요청이 같은 토큰을 동시에 소비하는 경합이 없다.

-- KEYS[1] = 버킷 키 (HASH: tokens, ts)
-- ARGV[1] = capacity
-- ARGV[2] = refill_per_sec
-- ARGV[3] = now_ms
-- ARGV[4] = cost
-- ARGV[5] = ttl_seconds (유휴 버킷 정리용)
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local now      = tonumber(ARGV[3])
local cost     = tonumber(ARGV[4])
 
local data = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(data[1])
local ts     = tonumber(data[2])
 
if tokens == nil then
  tokens = capacity
  ts = now
end
 
-- 경과 시간만큼 보충 (capacity 상한)
local elapsed = math.max(0, now - ts) / 1000.0
tokens = math.min(capacity, tokens + elapsed * rate)
ts = now
 
local allowed = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
end
 
redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', ts)
redis.call('EXPIRE', KEYS[1], tonumber(ARGV[5]))
return allowed

운영 팁: EVAL 로 매번 스크립트 본문을 보내지 말고 SCRIPT LOAD 로 한 번 등록해 SHA 로 EVALSHA 호출하면 대역폭을 아낀다. 다중 노드(Redis Cluster)에서는 한 스크립트가 건드리는 키들이 같은 슬롯에 있어야 하므로, 관련 키에 동일한 hash tag({...})를 붙여 같은 노드로 모은다.

응답 규약

한도를 넘긴 요청에는 429 Too Many Requests 를 돌려주고, 언제 다시 시도하면 되는지 알려 주는 게 예의이자 실용이다. 클라이언트가 무작정 재시도하지 않게 만들어 시스템 전체를 안정화한다.

• Retry-After: 초 단위 정수 또는 HTTP-date. 다음 토큰이 채워질 때까지(혹은 창이 리셋될 때까지) 남은 시간을 넣는다.
• X-RateLimit-Limit: 해당 창/버킷의 한도.
• X-RateLimit-Remaining: 남은 허용량(token bucket 이면 현재 토큰 수, 윈도우면 남은 카운트).
• X-RateLimit-Reset: 한도가 회복되는 시각(epoch 초 또는 남은 초).

function rateLimitResponse(limit: number, remaining: number, resetSec: number) {
  const headers = {
    "X-RateLimit-Limit": String(limit),
    "X-RateLimit-Remaining": String(Math.max(0, remaining)),
    "X-RateLimit-Reset": String(resetSec),
  };
  if (remaining <= 0) {
    return new Response("Too Many Requests", {
      status: 429,
      headers: { ...headers, "Retry-After": String(resetSec) },
    });
  }
  // 통과 시에도 위 X-RateLimit-* 헤더를 함께 실어 주면 클라이언트가 자체 조절한다.
  return null;
}

표준화 흐름에서는 RateLimit / RateLimit-Policy 단일 헤더(IETF draft)도 등장했지만, 현장에서는 여전히 X-RateLimit-* 관습이 가장 널리 쓰인다. 둘을 함께 실어도 된다.

키 설계

"무엇을 단위로 셀 것인가(rate limit key)"가 알고리즘만큼 중요하다. 같은 알고리즘도 키를 잘못 잡으면 보호가 무력화되거나 정상 사용자를 가둔다.

• IP 기준: 인증 전 단계(로그인, 회원가입, 공개 엔드포인트)에서 거의 유일한 식별자. 단 NAT·CGNAT·회사망·모바일 캐리어에서는 수많은 사용자가 하나의 공인 IP 를 공유한다. IP 한도를 너무 빡빡하게 잡으면 그 뒤의 정상 사용자 전체가 같이 막힌다. 반대로 IPv6 는 사용자가 대량의 주소를 가질 수 있어 /64 단위로 묶는 등 prefix 집계가 필요하다. 프록시 뒤라면 X-Forwarded-For 의 신뢰 가능한 hop 만 사용해야 위조를 막는다.
• 사용자 기준: 로그인 이후엔 user id 가 가장 공정하다. IP 가 바뀌어도 따라붙고, NAT 공유 문제도 없다. 인증을 우회하는 공격에는 못 쓰니 IP 한도와 병행한다.
• API 키 기준: 서버-서버 API 의 표준. 키가 곧 과금·플랜 단위라 한도를 플랜 등급에 맞춰 차등하기 자연스럽다.

엔드포인트별 차등도 필수다. 읽기(GET /feed)는 후하게, 비싸거나 위험한 동작(POST /login, POST /password-reset, LLM 호출)은 빡빡하게 둔다. 실무에서는 여러 키를 동시에 적용한다 — 예: "IP 당 분당 60, 사용자당 분당 600, 로그인 엔드포인트는 IP 당 5분에 10" 식으로 계층을 겹쳐 가장 먼저 걸리는 한도가 차단한다.

정리

• 무엇을 막고 싶은지가 알고리즘을 정한다. 평균을 통제하되 합리적 버스트는 허용이 목적이면 token bucket 이 기본값이고, 그래서 가장 널리 쓰인다.
• 출력을 일정 속도로 평탄화해 하위 시스템을 강하게 보호하려면 leaky bucket, 정밀한 슬라이딩 한도가 필요하면 sliding window(메모리를 아끼려면 counter, 정확도를 끝까지 원하면 log)를 택한다.
• fixed window 는 가장 싸지만 경계 2배 버스트를 감수해야 하므로, 보호가 중요한 경로엔 sliding window counter 가 비용 대비 균형이 좋다.
• 서버가 여러 대면 한도를 공유 저장소(Redis)에 두고, 읽기·계산·쓰기를 Lua 스크립트로 원자화한다. 원자성을 빼면 경합으로 한도가 새거나 과하게 막힌다.
• 막을 때는 429 + Retry-After + X-RateLimit-* 로 클라이언트가 스스로 물러서게 만들고, IP·사용자·API 키를 엔드포인트별로 계층화한 키 설계로 보호와 공정성을 함께 잡는다.