필사 모드: 레이트 리밋 알고리즘 고르기 — 고정 윈도우, 슬라이딩, 토큰 버킷의 실제 차이

들어가며 — 분당 100회로 막았는데 200회가 들어왔다

레이트 리밋을 붙였습니다. 키당 분당 100회. 그런데 모니터링을 보니 어떤 클라이언트가 200밀리초 사이에 200개의 요청을 통과시켰습니다. 로그를 뒤져도 코드에는 문제가 없습니다.

버그가 아닙니다. 고정 윈도우 카운터의 정의된 동작입니다. 그리고 이 사실을 모르고 배포한 리밋은 보호하려던 대상을 정확히 보호하지 못합니다.

레이트 리밋은 한 줄짜리 미들웨어처럼 보이지만 실제로는 네 가지 결정의 묶음입니다. 어떤 알고리즘을 쓸 것인가, 무엇을 키로 삼을 것인가, 분산 환경에서 카운터를 어디에 둘 것인가, 막힌 클라이언트에게 무엇을 알려 줄 것인가. 하나씩 봅니다.

네 가지 알고리즘과 트레이드오프

표만 봐도 선택이 좁혀집니다. 슬라이딩 로그는 정확하지만 비싸고, 고정 윈도우는 싸지만 부정확합니다. 실무에서 남는 것은 슬라이딩 윈도우 카운터와 토큰 버킷 둘입니다.

고정 윈도우의 경계 문제를 숫자로

한도가 분당 100회이고 윈도우가 매분 0초에 리셋된다고 하겠습니다. 클라이언트가 이렇게 보냅니다.

10:00:59.900  요청 100개   → 10:00 윈도우 카운터 0 → 100. 전부 통과
10:01:00.100  요청 100개   → 10:01 윈도우 카운터 0 → 100. 전부 통과

200밀리초 동안 200개가 통과했습니다. 임의의 연속된 60초 구간을 기준으로 보면 한도의 두 배입니다. 이것이 고정 윈도우의 상한입니다. 어떤 60초 구간에서도 최대 2배가 통과할 수 있습니다.

한도가 클수록 절대 피해가 커집니다. 분당 6000회 한도라면 순간적으로 12000개가 들어옵니다. 이 정도면 보호하려던 백엔드가 그대로 무너집니다.

윈도우를 짧게 쪼개면 완화됩니다. 분당 100회 대신 초당 2회로 바꾸면 경계 초과폭이 절대량으로 작아집니다. 다만 정상적인 버스트도 같이 잘려서 사용자 경험이 나빠집니다.

슬라이딩 윈도우 카운터는 이전 윈도우의 카운트를 경과 비율만큼 가중해서 더합니다.

현재 시각이 10:01:15 (윈도우의 25% 경과)
이전 윈도우(10:00) 카운트 = 100
현재 윈도우(10:01) 카운트 = 20

추정치 = 100 * (1 - 0.25) + 20 = 95
95 < 100 이므로 통과. 5개만 더 받으면 차단

이전 윈도우의 요청이 균등하게 분포했다고 가정하는 근사입니다. 가정이 어긋나도 오차는 작습니다. 클라우드플레어가 자사 트래픽으로 이 방식을 평가한 결과를 공개한 바 있는데, 잘못 허용되거나 잘못 차단된 요청 비율은 0.003퍼센트 수준이었습니다. 카운터 두 개로 슬라이딩 로그에 근접한 정확도를 얻는 셈입니다.

슬라이딩 로그의 비용도 짚어 둘 만합니다. 레디스 정렬 집합에 요청마다 타임스탬프를 넣으면 원소 하나가 실제로는 수십 바이트에서 100바이트 가까이 차지합니다. 한도 100, 활성 키 100만 개면 항목 1억 개, 수 GB입니다. 카운터 두 개로 끝나는 방식과 비교하면 세 자릿수 차이입니다.

토큰 버킷 — 버스트를 허용하는 것이 API에 맞는 이유

토큰 버킷은 두 개의 숫자로 정의됩니다. 통 크기와 초당 충전 속도입니다. 요청이 오면 토큰 하나를 꺼내고, 없으면 거절합니다. 토큰은 시간에 비례해 채워지되 통 크기를 넘지 않습니다.

충전은 타이머로 하지 않습니다. 요청이 올 때 경과 시간만큼 계산해서 채우면 됩니다. 그래서 저장할 것이 토큰 수와 마지막 갱신 시각 두 개뿐입니다.

function consume(state, now, capacity, refillPerSec, cost = 1) {
  const elapsed = (now - state.updatedAt) / 1000
  const tokens = Math.min(capacity, state.tokens + elapsed * refillPerSec)

  if (tokens < cost) {
    const wait = (cost - tokens) / refillPerSec
    return { allowed: false, retryAfter: Math.ceil(wait), state: { tokens, updatedAt: now } }
  }
  return { allowed: true, state: { tokens: tokens - cost, updatedAt: now } }
}

여기서 중요한 것은 버스트를 명시적으로 정의한다는 점입니다. 통 크기 20에 충전 10개/초라면, 조용히 있다가 한 번에 20개를 쏘는 것은 허용하되 장기 평균은 초당 10개로 묶입니다.

이 성질이 API에 맞는 이유는 실제 클라이언트가 균등하게 요청하지 않기 때문입니다. 페이지 하나를 열면 병렬 요청 여덟 개가 동시에 나갑니다. 사용자가 목록을 열고 필터를 걸면 짧은 구간에 요청이 몰립니다. 엄격한 슬라이딩 윈도우로 초당 10개를 강제하면 이런 정상적인 화면 로드가 잘립니다. 사용자는 서비스가 고장 났다고 느끼는데, 서버는 한가합니다.

레이트 리밋의 목적은 요청 간격을 고르게 만드는 것이 아니라 장기 부하를 상한선 아래로 유지하는 것입니다. 토큰 버킷은 그 목적을 정확히 표현합니다. 그래서 공개 API 대부분이 이 방식을 쓰고, 문서에 통 크기와 충전 속도를 그대로 노출합니다.

비용 가중도 자연스럽게 붙습니다. 목록 조회는 토큰 1개, 리포트 생성은 토큰 20개처럼 엔드포인트마다 비용을 다르게 매기면, 호출 횟수가 아니라 실제 자원 소비를 제한하게 됩니다. 깃허브 API가 쿼리 복잡도에 따라 점수를 다르게 매기는 것이 같은 발상입니다.

분산 환경 구현 — 원자적 연산과 로컬 리밋의 오차

노드가 여럿이면 카운터를 공유해야 하고, 공유하는 순간 경쟁 조건이 생깁니다. 읽고 판단하고 쓰는 세 단계 사이에 다른 노드가 끼어들면 한도를 넘깁니다.

레디스에서 흔히 쓰는 조합에도 함정이 있습니다.

# 위험 — INCR 직후 프로세스가 죽으면 TTL이 없는 키가 영원히 남습니다
INCR rl:user_8812:1784056020
EXPIRE rl:user_8812:1784056020 60

키가 만료되지 않으면 그 사용자는 카운터가 한도에 도달한 채로 영구히 막힙니다. 원자적으로 처리해야 합니다.

-- 슬라이딩 윈도우 카운터. KEYS[1]=이전 윈도우, KEYS[2]=현재 윈도우
-- ARGV: 1=한도, 2=윈도우 길이(초), 3=현재 윈도우 경과 비율
local prev = tonumber(redis.call('GET', KEYS[1]) or '0')
local curr = tonumber(redis.call('GET', KEYS[2]) or '0')
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local elapsed = tonumber(ARGV[3])

local estimated = prev * (1 - elapsed) + curr
if estimated >= limit then
  return {0, limit, 0}
end

curr = redis.call('INCR', KEYS[2])
if curr == 1 then
  redis.call('EXPIRE', KEYS[2], window * 2)
end
return {1, limit, math.floor(limit - estimated - 1)}

Lua 스크립트는 레디스에서 단일 스레드로 원자 실행되므로 판단과 증가 사이에 끼어들 여지가 없습니다. 토큰 버킷도 같은 방식으로 옮길 수 있고, 최근 레디스에는 이 목적의 확장 모듈도 있습니다.

그렇다면 노드마다 로컬 카운터를 두는 방식은 얼마나 틀릴까요. 노드가 N개이고 로드밸런서가 완벽하게 균등 분배한다면, 각 노드에 한도를 N분의 1로 나눠 주면 총합이 맞습니다. 문제는 두 가지입니다.

분배가 균등하지 않습니다. 커넥션 유지 방식이나 해시 기반 라우팅 때문에 한 클라이언트의 요청이 특정 노드로 쏠리면, 그 클라이언트는 전체 한도의 N분의 1만 쓰고 차단됩니다. 실제 한도가 광고한 값보다 훨씬 작아집니다.

노드 수가 변합니다. 오토스케일링으로 노드가 늘면 각 노드의 몫을 다시 계산해야 하는데, 그러지 않으면 총 허용량이 노드 수에 비례해 늘어납니다. 노드 10개에 각각 분당 100을 걸어 두면 실제 한도는 분당 1000입니다.

그래서 실용적인 배치는 두 겹입니다. 노드 로컬에는 자기 자신을 보호하는 느슨한 상한을 두고, 정확한 사용자별 한도는 공유 저장소에서 판단합니다. 저장소 왕복이 부담되면 노드가 중앙 버킷에서 토큰을 묶음으로 임차해 로컬에서 소비하는 방식도 씁니다. 정확도를 조금 내주고 왕복 횟수를 크게 줄이는 절충입니다.

레디스가 죽었을 때의 동작도 미리 정해야 합니다. 전부 차단하면 리밋 저장소 장애가 전면 장애가 되고, 전부 통과시키면 그 순간 보호가 사라집니다. 보통은 통과시키되 노드 로컬 상한은 유지하고, 알람을 올립니다.

무엇을 키로 삼을 것인가

IP를 키로 쓰는 것은 기본값처럼 보이지만 여러 방향으로 깨집니다.

한 IP 뒤에 사용자가 수천 명 있을 수 있습니다. 회사 네트워크, 학교, 통신사의 대규모 NAT가 그렇습니다. IP 기준으로 조이면 정상 사용자 집단이 통째로 막힙니다.

반대로 공격자는 IP를 쉽게 바꿉니다. 클라우드에서 IP를 회전시키는 비용은 거의 없고, IPv6는 호스트 하나에 접두사 하나가 통째로 할당되는 경우가 많아 사실상 무한합니다. IPv6를 키로 쓸 때는 전체 주소가 아니라 상위 접두사 단위로 묶어야 최소한의 의미가 생깁니다.

프록시 뒤에서 클라이언트 IP를 읽는 방식도 자주 틀립니다. X-Forwarded-For는 클라이언트가 임의로 채워 보낼 수 있는 값이라, 목록의 맨 앞을 그대로 믿으면 공격자가 매 요청마다 다른 IP를 주장해서 리밋을 무력화합니다. 신뢰하는 프록시 수를 세어 뒤에서부터 해당 위치의 값을 취해야 합니다.

우선순위는 이렇게 잡습니다. 인증된 요청이면 사용자 식별자나 API 키가 1순위입니다. 요금제와 결부되므로 테넌트 단위 쿼터도 함께 겁니다. 인증 이전 단계, 즉 로그인이나 가입 같은 엔드포인트에서는 IP 외에 쓸 것이 마땅치 않으므로 IP를 쓰되 한도를 넉넉히 잡고, 대신 계정 식별자 기준의 별도 한도를 겹칩니다. 로그인 시도는 IP당 한도와 계정당 한도를 동시에 걸어야 크리덴셜 스터핑과 단일 계정 무차별 대입을 함께 막을 수 있습니다.

키를 여러 겹으로 겹칠 때는 가장 좁은 것부터 검사하고, 어떤 한도에 걸렸는지를 응답에 남겨야 디버깅이 가능합니다.

429와 클라이언트의 재시도

한도를 초과했을 때는 429를 씁니다. 503은 서버 과부하, 403은 권한 없음이므로 의미가 다릅니다. 클라이언트가 상황을 판단할 수 있도록 정보를 실어 보냅니다.

HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
Retry-After: 12
RateLimit-Limit: 600
RateLimit-Remaining: 0
RateLimit-Reset: 12
Cache-Control: no-store

Retry-After는 초 또는 HTTP 날짜를 받으며, 클라이언트는 자신의 백오프 계산보다 이 값을 우선해야 합니다. RateLimit 계열 헤더는 IETF에서 표준화가 진행 중인 필드로, 남은 횟수와 초기화까지 남은 시간을 알려 줍니다. 기존 서비스들이 쓰던 X-RateLimit 접두사 버전이 여전히 널리 쓰이므로 둘 다 내보내는 것도 방법입니다.

429 응답 자체는 값싸야 합니다. 차단된 요청에서 DB를 조회하거나 무거운 직렬화를 하면, 공격 트래픽이 그대로 부하가 됩니다. 리밋 판정은 가능한 한 앞단에서 끝내고 응답 본문은 짧게 유지합니다. 그리고 429에는 캐시 헤더를 붙이지 않습니다. 중간 캐시가 429를 저장했다가 정상 상태의 클라이언트에게 돌려주는 사고가 실제로 발생합니다.

이제 클라이언트 쪽입니다. 차단된 클라이언트가 고정 간격으로 재시도하면 무슨 일이 벌어지는지가 핵심입니다.

서버가 잠시 흔들려서 1000개의 클라이언트가 동시에 실패했다고 합시다. 모두 1초 후에 재시도하면, 1초 뒤에 1000개가 동시에 도착합니다. 서버가 다시 흔들리고, 다시 2초 후 재시도하면 2초 뒤에 또 1000개가 동시에 도착합니다. 지수 백오프를 넣어도 간격이 결정적이면 재시도가 동기화된 파도로 남습니다. 이것이 썬더링 허드입니다.

해법은 무작위성입니다.

// 하지 마세요 — 모든 클라이언트가 같은 순간에 깨어납니다
const delay = Math.min(cap, base * 2 ** attempt)

// 풀 지터 — 0과 상한 사이에서 무작위로 뽑습니다
const delay = Math.random() * Math.min(cap, base * 2 ** attempt)

AWS가 공개한 백오프 비교 실험에서 풀 지터는 총 재시도 횟수와 전체 완료 시간을 함께 줄였습니다. 상한의 절반을 고정으로 깔고 나머지만 무작위로 하는 방식보다도 나았습니다. 직관과 어긋나 보이지만, 대기 시간을 넓게 퍼뜨리는 것이 충돌을 줄이는 데 더 효과적이기 때문입니다.

재시도 구현에서 함께 지켜야 할 것들이 있습니다. 서버가 Retry-After를 줬으면 그 값을 따릅니다. 최대 시도 횟수와 전체 마감 시간을 두어 무한 재시도를 막습니다. 429와 5xx는 재시도하되 4xx의 나머지는 재시도하지 않습니다. 그리고 멱등하지 않은 요청을 재시도할 때는 멱등성 키를 함께 보내서 중복 실행을 막아야 합니다. 타임아웃으로 실패한 결제 요청을 그냥 재시도하면 두 번 결제될 수 있습니다.

마치며 — 알고리즘보다 먼저 정할 것

레이트 리밋을 붙일 때 가장 먼저 정할 것은 알고리즘이 아니라 무엇을 보호하려는가입니다. 백엔드 용량을 지키려는 것이라면 비용 가중 토큰 버킷이 맞고, 공정한 분배가 목적이라면 테넌트 단위 쿼터가 맞고, 무차별 대입을 막으려는 것이라면 계정과 IP를 겹친 좁은 한도가 맞습니다. 목적이 다르면 키도 한도도 달라집니다.

고정 윈도우는 언제나 한도의 두 배를 통과시킬 수 있고, 카운터 두 개짜리 슬라이딩 윈도우로 바꾸는 비용은 거의 없습니다. 그다음에는 클라이언트에게 상태를 알려 주는 일이 남습니다. 남은 횟수와 재시도 시각을 정확히 내려 주면 잘 만든 클라이언트는 스스로 물러섭니다. 알려 주지 않으면 모두가 같은 순간에 다시 문을 두드립니다.