레이트 리미팅 알고리즘 — 토큰 버킷·슬라이딩 윈도우 구현과 분산 환경에서의 정확도

API를 운영하다 보면 어느 순간 반드시 이 질문이 온다. "특정 클라이언트가 초당 수천 번씩 때리는데 어떻게 막죠?" 방화벽으로 IP를 끊는 건 너무 무디고, 애플리케이션 레벨에서 "이 키는 분당 100회까지"처럼 세밀하게 제어하려면 결국 레이트 리미터를 직접 이해해야 한다. 나는 API 게이트웨이와 결제 백엔드 양쪽에서 이걸 붙여봤는데, 알고리즘 선택보다 상태 저장소와 동시성 처리에서 훨씬 많이 데였다.

레이트 리미팅 알고리즘은 왜 여러 개일까?

정답이 하나면 알고리즘이 여럿일 이유가 없다. 실제로는 "메모리 사용량", "경계에서의 폭주 허용 여부", "버스트(순간 몰림)를 얼마나 봐줄지", "구현 복잡도"라는 네 축의 트레이드오프이고, 각 알고리즘은 이 축에서 서로 다른 지점을 찍는다. 그래서 "무조건 슬라이딩 윈도우가 우월하다" 같은 말은 반은 맞고 반은 틀리다.

핵심만 먼저 요약하면 이렇다. 고정 윈도우는 가장 싸지만 경계에서 두 배까지 샌다. 슬라이딩 윈도우 로그는 정확하지만 요청마다 타임스탬프를 다 저장한다. 토큰 버킷은 버스트를 자연스럽게 허용하면서 평균 속도를 지키고, 리키 버킷은 출력을 완벽히 평탄하게 만든다. 아래 표가 이걸 한눈에 정리한 것이다.

고정 윈도우는 왜 경계에서 두 배까지 새는가?

고정 윈도우는 "12:00:00~12:00:59에 100개"처럼 시계를 딱딱 잘라 그 구간의 카운트만 센다. 문제는 이 경계다. 12:00:59에 100개를 몰아 보내고, 창이 바뀌는 12:01:00에 다시 100개를 보내면, 실제로는 1초 안에 200개가 통과한다. 분당 100 제한을 걸었는데 순간적으로 2배가 새는 것이다. 이게 고정 윈도우의 유명한 boundary burst 문제다.

그래도 장점은 명확하다. 상태가 카운터 하나라 메모리가 거의 안 들고, Redis INCR + EXPIRE 두 줄이면 끝난다. 초기 트래픽을 대충 걸러내는 1차 방어선으로는 충분히 쓸 만하다.

-- 고정 윈도우: Redis Lua (KEYS[1]=리밋키, ARGV[1]=한도, ARGV[2]=윈도우초)
local current = redis.call('INCR', KEYS[1])
if current == 1 then
  -- 이 윈도우의 첫 요청일 때만 만료 설정
  redis.call('EXPIRE', KEYS[1], tonumber(ARGV[2]))
end
if current > tonumber(ARGV[1]) then
  return 0   -- 차단
end
return 1     -- 허용

슬라이딩 윈도우는 그 문제를 어떻게 없애나?

슬라이딩 윈도우는 고정된 시계 구간 대신 "지금 이 순간부터 뒤로 60초"라는 움직이는 창을 본다. 방식은 두 가지다. 정확한 로그 방식과, 메모리를 아끼는 근사 카운터 방식.

로그 방식은 요청 하나하나의 타임스탬프를 Redis Sorted Set에 넣고, 매 요청마다 윈도우 밖(60초 이전) 타임스탬프를 제거한 뒤 남은 개수를 센다. 완벽하게 정확한 대신, 초당 수천 요청을 받는 키라면 그만큼의 원소가 쌓인다. 메모리가 트래픽에 비례해 늘어난다는 게 유일하지만 치명적인 단점이다.

-- 슬라이딩 윈도우 로그: Redis Lua
-- KEYS[1]=ZSET키, ARGV[1]=현재ms, ARGV[2]=윈도우ms, ARGV[3]=한도, ARGV[4]=고유멤버
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])
-- 윈도우를 벗어난 오래된 요청 제거
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window)
local count = redis.call('ZCARD', KEYS[1])
if count < limit then
  redis.call('ZADD', KEYS[1], now, ARGV[4])
  redis.call('PEXPIRE', KEYS[1], window)
  return limit - count - 1   -- 남은 허용량 반환
end
return -1                    -- 차단

카운터 방식은 현재 윈도우와 직전 윈도우의 카운트 두 개만 들고, 직전 윈도우 값을 겹치는 비율만큼 가중해서 더한다. 예를 들어 현재 창이 30% 진행됐다면 추정치 = 현재창 + 직전창 × 0.7이다. 정확한 로그 대비 오차가 있지만, 여러 벤더가 공개한 분석에서 실무상 오차율이 1% 미만 수준으로 보고될 만큼 근사가 좋다. 메모리는 키당 정수 두 개. 나는 공개 API 기본값으로 이걸 가장 자주 쓴다.

토큰 버킷은 어떻게 버스트를 봐주면서 평균을 지키나?

토큰 버킷의 핵심 아이디어는 "크레딧이 일정 속도로 채워지는 지갑"이다. 버킷 용량이 100이고 초당 10개씩 리필된다면, 평소엔 초당 10개 평균을 지키지만 한동안 안 쓰다가 쌓인 크레딧으로 순간 100개까지 한꺼번에 쓸 수 있다. 이 "봐주는 버스트"가 토큰 버킷의 정체성이다. 모바일 앱처럼 화면 진입할 때 API 여러 개를 몰아 부르는 클라이언트에 특히 잘 맞는다.

구현의 포인트는 백그라운드 타이머로 토큰을 채우지 않는다는 것이다. 그건 키가 수백만 개면 감당이 안 된다. 대신 "마지막으로 본 시각"만 저장해두고, 요청이 올 때 경과 시간 × 리필속도만큼을 그 자리에서 계산해 채운다(lazy refill). 상태는 실수 두 개(현재 토큰, 마지막 갱신 시각)면 충분하다.

-- 토큰 버킷: Redis Lua (HASH에 tokens, ts 저장)
-- KEYS[1]=버킷키, ARGV[1]=용량, ARGV[2]=초당리필, ARGV[3]=현재초, ARGV[4]=요청토큰수
local cap    = tonumber(ARGV[1])
local rate   = tonumber(ARGV[2])
local now    = tonumber(ARGV[3])
local want   = 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 = cap; ts = now end
-- 경과 시간만큼 지연 리필(용량 상한)
local delta = math.max(0, now - ts)
tokens = math.min(cap, tokens + delta * rate)
local allowed = 0
if tokens >= want then
  tokens = tokens - want
  allowed = 1
end
redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
-- 오래 안 쓰면 자동 정리: 버킷이 꽉 차는 데 걸리는 시간만큼 TTL
redis.call('EXPIRE', KEYS[1], math.ceil(cap / rate) + 1)
return { allowed, math.floor(tokens) }   -- {허용여부, 남은토큰}

왜 read-modify-write를 반드시 Lua로 묶어야 하나?

한 문장으로 답하면, 애플리케이션에서 값을 읽고(GET) 판단하고 다시 쓰는(SET) 사이에 다른 요청이 끼어들어 같은 값을 읽으면 리밋이 그대로 샌다. 이게 전형적인 read-modify-write 경쟁 조건(race condition)이다. 서버 인스턴스가 10개면 동시에 10개가 "아직 99개니까 OK"를 읽고 전부 통과시켜, 100 제한이 순간 109가 된다.

Redis는 단일 스레드로 명령을 처리하고, EVAL로 실행되는 Lua 스크립트는 그 전체가 하나의 원자 단위로 돈다. 즉 스크립트가 도는 동안 다른 클라이언트 명령이 절대 끼어들지 못한다. 위 예제들이 전부 GET/계산/SET을 스크립트 안에 넣은 이유가 이것이다. 프로덕션에서는 EVAL 대신 SCRIPT LOAD로 한 번 등록하고 SHA로 EVALSHA 호출하는 게 네트워크로 스크립트 본문을 매번 안 보내서 낫다.

# Node.js(ioredis) — 스크립트를 커맨드로 등록해 EVALSHA로 호출
const Redis = require('ioredis');
const redis = new Redis();

redis.defineCommand('tokenBucket', {
  numberOfKeys: 1,
  lua: TOKEN_BUCKET_LUA,   // 위 Lua 문자열
});

async function allow(key) {
  const now = Date.now() / 1000;
  // [allowed, remaining]
  const [ok, remaining] = await redis.tokenBucket(
    `rl:${key}`, 100, 10, now, 1
  );
  return { allowed: ok === 1, remaining };
}

429를 내려줄 때 어떤 헤더를 함께 보내야 하나?

차단은 HTTP 429 Too Many Requests로 응답하고, 클라이언트가 "언제 다시 시도할지"를 알 수 있도록 Retry-After를 반드시 붙여야 한다. 이게 없으면 클라이언트는 감으로 재시도하다가 리밋을 더 악화시킨다. Retry-After는 초 단위 정수(Retry-After: 30) 또는 HTTP-date 형식 둘 다 유효하다. 나는 정수 초를 쓴다. 파싱이 단순하고 시계 문제에서 자유롭다.

여기에 더해, 차단되지 않은 정상 응답에도 현재 상태를 알려주는 헤더를 얹어주면 잘 만든 클라이언트는 스스로 속도를 조절한다. 사실상의 관례로 굳어진 X-RateLimit-* 계열과, 이를 표준화하려는 IETF RateLimit 헤더 초안이 있다. 아래 표가 실무에서 쓰는 조합이다.

// Express 미들웨어 — 429와 헤더 처리
async function rateLimit(req, res, next) {
  const key = req.headers['x-api-key'] || req.ip;
  const { allowed, remaining } = await allow(key);

  res.set('X-RateLimit-Limit', '100');
  res.set('X-RateLimit-Remaining', String(Math.max(0, remaining)));

  if (!allowed) {
    const retry = 30;                 // 리필/리셋 계산값
    res.set('Retry-After', String(retry));
    res.set('X-RateLimit-Reset', String(retry));
    return res.status(429).json({
      error: 'rate_limited',
      message: '요청이 너무 많습니다. 잠시 후 다시 시도하세요.',
      retry_after: retry,
    });
  }
  next();
}

분산 환경에서는 정확도가 어디서 깨지나?

서버가 여러 대일 때 정확도가 깨지는 지점은 크게 셋이다. 첫째는 앞서 말한 read-modify-write 경쟁인데, 이건 상태를 공유 Redis에 두고 Lua로 원자화하면 해결된다. 남는 건 둘째와 셋째, 즉 "중앙 저장소 자체가 병목/단일 장애점이 되는 문제"와 "저장소를 안 쓰고 노드끼리 근사하려다 생기는 오차"다.

중앙 Redis 방식은 정확하지만 모든 요청이 Redis를 한 번씩 왕복한다. 지연이 붙고, Redis가 죽으면 리미터 전체가 흔들린다. 그래서 큰 규모에서는 두 가지 완화책을 쓴다. 하나는 로컬 근사 + 주기 동기화다. 각 노드가 인메모리로 대략 세면서 짧은 주기로 Redis와 맞춰, 정확도를 조금 포기하는 대신 왕복을 줄인다. 다른 하나는 쿼터 분배다. 노드가 5대면 분당 100 제한을 노드당 20씩 나눠주는 식인데, 트래픽이 노드마다 고르지 않으면 어떤 노드는 남고 어떤 노드는 모자라 실효 한도가 들쭉날쭉해진다.

그리고 반드시 정해야 할 게 하나 더 있다. 리미터 저장소가 죽으면 어떻게 할 것인가. Redis 타임아웃 시 요청을 다 통과시킬 것인가(fail-open), 다 막을 것인가(fail-closed). 로그인·결제처럼 남용이 곧 사고인 엔드포인트는 fail-closed가 맞고, 일반 조회 API는 대개 fail-open이 낫다. 이건 알고리즘이 아니라 정책 결정이라, 처음부터 명시적으로 코드에 박아둬야 장애 순간에 당황하지 않는다.

그래서 뭘 골라야 하나 — 실전 선택 가이드

결론부터 말하면, 대부분의 공개 REST API는 슬라이딩 윈도우 카운터 또는 토큰 버킷 둘 중 하나면 충분하다. 버스트를 봐주고 싶고 남은 크레딧을 헤더로 내려주고 싶으면 토큰 버킷, 순간 속도를 최대한 평탄하고 예측 가능하게 만들고 싶으면 슬라이딩 윈도우 카운터를 쓴다.

• 단일 서버, 대충 막기: 인메모리 고정 윈도우. 라이브러리 하나면 끝.
• 여러 서버, 일반 API: Redis + 슬라이딩 윈도우 카운터(Lua 원자화).
• 버스트를 봐줘야 하는 SDK·모바일: 토큰 버킷.
• 다운스트림을 일정 속도로 보호(예: 외부 벤더 호출): 리키 버킷.
• 결제·인증처럼 정확도가 곧 돈: 슬라이딩 윈도우 로그 + fail-closed.

그리고 직접 다 짜기 전에, 이미 검증된 게이트웨이 레벨 리미팅(예: Nginx limit_req는 리키 버킷 기반, Envoy·Kong의 리미팅 필터)이 요구사항을 커버하는지 먼저 보라. 애플리케이션 코드로 내려오는 건 "키 단위 세밀 제어"나 "비즈니스 규칙과 엮인 동적 한도"가 필요할 때다. 나도 처음엔 다 직접 짰다가, 결국 무딘 1차 방어는 게이트웨이에 맡기고 세밀한 2차만 앱에서 하는 2단 구조로 정착했다.

자주 묻는 질문

토큰 버킷과 리키 버킷은 결국 같은 거 아닌가요?

수학적으로는 매우 가깝지만 목적이 다릅니다. 토큰 버킷은 쌓인 크레딧으로 순간 버스트를 허용해 입력 속도를 제어하고, 리키 버킷은 출력이 항상 일정 속도로 나가도록 강제해 버스트를 평탄하게 만듭니다. 버스트를 봐줄지 말지가 갈림길입니다.

왜 애플리케이션 코드에서 GET/SET으로 세면 안 되나요?

읽고 나서 쓰는 사이에 다른 요청이 같은 값을 읽는 read-modify-write 경쟁 때문입니다. 인스턴스가 여러 개면 동시에 같은 잔량을 읽고 다 통과시켜 한도가 샙니다. Redis Lua 스크립트로 읽기·계산·쓰기를 하나의 원자 연산으로 묶어야 합니다.

Retry-After는 초와 날짜 중 뭘 써야 하나요?

둘 다 HTTP 표준상 유효합니다. 실무에서는 초 단위 정수(예: Retry-After: 30)를 권합니다. 파싱이 단순하고 클라이언트·서버 시계 차이의 영향을 받지 않기 때문입니다. 클라이언트는 이 값에 약간의 지터를 더해 재시도 폭주를 피하는 게 좋습니다.

분산 환경에서 정확도와 성능 중 뭘 우선해야 하나요?

엔드포인트 성격에 따라 다릅니다. 결제·인증처럼 남용이 곧 사고인 곳은 중앙 Redis + Lua로 정확도를 지키고, 초고트래픽 조회 API는 로컬 근사 + 주기 동기화로 약간의 오차를 감수하며 지연을 줄입니다. 한 시스템 안에서도 경로별로 다르게 가는 게 정상입니다.

리미터로 쓰는 Redis가 죽으면 어떻게 되나요?

미리 정한 정책에 따라야 합니다. 요청을 다 통과시키는 fail-open은 일반 조회 API에, 다 차단하는 fail-closed는 로그인·결제 같은 민감한 경로에 적합합니다. 코드에 명시적으로 박아두지 않으면 장애 순간 예상 못 한 동작을 하게 됩니다. 타임아웃 값도 짧게 잡아 리미터가 전체 지연을 끌어올리지 않게 하세요.

고정 윈도우는 절대 쓰면 안 되나요?

아닙니다. 경계 폭주(최대 2배)를 감당할 수 있는 내부 API나 대략적인 1차 방어선으로는 여전히 유효합니다. 카운터 하나로 끝나 메모리와 구현 비용이 가장 낮습니다. 다만 외부 공개 API의 엄격한 한도 보장에는 슬라이딩 계열이나 토큰 버킷이 더 안전합니다.

사용자 단위와 IP 단위 중 무엇을 키로 잡아야 하나요?

인증된 트래픽은 API 키나 사용자 ID를, 비인증 트래픽은 IP를 키로 씁니다. IP는 NAT·프록시 뒤에서 여러 사용자가 공유될 수 있어 오탐이 생기므로, 신뢰할 수 있는 프록시가 넘겨준 실제 클라이언트 IP를 정확히 뽑아 써야 합니다. 이상적으로는 사용자·IP·엔드포인트 등급을 조합한 다층 키를 씁니다.