Rate Limiting 알고리즘 비교와 분산 환경 구현

Rate Limiting은 한 클라이언트가 정해진 시간 동안 보낼 수 있는 요청 수를 제한해, 일부 사용자의 폭주나 남용이 전체 서비스를 무너뜨리지 않게 하는 장치다. 이 글은 Fixed Window, Sliding Window, Token Bucket, Leaky Bucket 다섯 가지 알고리즘을 버스트·메모리·정확도 기준으로 비교하고, 서버가 여러 대일 때 Redis와 Lua로 원자적으로 구현하는 방법과 429 응답, 키 설계, 배치 위치까지 정리한 것이다.

한눈에 보기

기준은 버스트 허용 여부와 정확도다. 대부분의 API는 Token Bucket이나 Sliding Window Counter로 충분하다.

Fixed Window와 경계 문제

가장 단순한 구현은 "분 단위 창마다 카운터 하나"다. 키에 창 번호를 넣고 INCR한 값이 한도를 넘으면 거절한다.

INCR  rl:ip:203.0.113.7:29180854
EXPIRE rl:ip:203.0.113.7:29180854 60

문제는 창의 경계다. 한도가 분당 100회일 때 00:59에 100회, 01:00에 100회를 보내면 두 창 모두 한도 안이지만 실제로는 약 2초 동안 200회가 들어온다. 한도의 두 배가 경계마다 허용된다.

순간 폭주가 문제 되지 않는 일 단위 할당량에는 이 단순함이 장점이다. 서버 용량 보호가 목적이면 다른 알고리즘을 쓴다.

Sliding Window Log와 Sliding Window Counter

Sliding Window Log는 요청 시각을 모두 저장하고 최근 창 길이 안의 기록 수를 센다. Redis Sorted Set에서 ZREMRANGEBYSCORE로 창 밖 기록을 지우고, ZCARD가 한도 미만이면 ZADD로 기록한다. 정확하지만 키마다 요청 수만큼 메모리를 쓰므로(분당 1만 회 한도면 원소 1만 개) "10분에 5회" 같은 작은 한도에 쓴다.

Sliding Window Counter는 직전 창과 현재 창의 카운터 두 개로 근삿값을 낸다.

추정치 = 직전 창 카운트 × (1 - 현재 창 경과 시간 / 창 길이) + 현재 창 카운트

분당 100회 한도에서 직전 창이 80회, 현재 창이 15초 지났고 30회라면 80 × 0.75 + 30 = 90이라 허용한다. 직전 창 요청이 고르게 퍼져 있었다고 가정한 값이라 오차가 있지만, 메모리는 Fixed Window와 거의 같고 경계 문제는 사라진다.

Token Bucket과 Leaky Bucket

Token Bucket은 용량 C인 버킷에 초당 r개씩 토큰이 채워지고, 요청마다 토큰을 하나(또는 비용만큼) 꺼내는 방식이다. 버킷이 차 있으면 C개까지 한 번에 통과하고, 그 뒤로는 평균 r개/초로 제한된다. "평소엔 초당 5회, 화면 첫 진입 때 20회 몰림은 허용" 같은 요구를 C=20, r=5로 그대로 표현할 수 있어 공개 API와 게이트웨이에서 가장 많이 쓴다. 요청마다 비용을 다르게 줄 수도 있다. LLM API를 감싼 서비스라면 요청 수보다 토큰 수를 비용으로 쓰는 편이 실제 부담에 가깝다(LLM Structured Output과 응답 스키마 검증 설계).

Leaky Bucket은 요청을 대기열에 넣고 일정한 속도로 꺼내 처리한다. 출력이 항상 일정해서 처리 속도가 고정된 하류(외부 기관 연계, 결제 대행)를 보호하는 데 맞다. 대신 대기열에 있는 동안 응답이 늦어진다. Nginx의 limit_req가 이 방식이다.

limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s;

server {
  location /api/ {
    limit_req zone=api burst=20 nodelay;
    limit_req_status 429;   # 지정하지 않으면 503을 돌려준다
  }
}

burst=20은 대기열 길이, nodelay는 대기열 요청을 기다리게 하지 않고 바로 처리하라는 뜻이다. 그러면 동작이 Token Bucket과 비슷해진다.

분산 환경 구현: Redis와 Lua로 원자성 지키기

서버 4대가 각자 메모리에서 분당 100회를 허용하면 실제 한도는 400회다. 그래서 카운터를 Redis 같은 공유 저장소에 둔다.

INCR 뒤 EXPIRE의 경쟁. 위의 Fixed Window 두 명령은 따로 실행된다. INCR만 실행되고 프로세스가 죽으면 TTL 없는 키가 남는다. 키에 창 번호가 없는 설계라면 그 클라이언트는 영원히 거절된다. 읽고 비교하고 쓰는 동작은 Lua 스크립트 하나로 묶어 Redis가 한 번에 실행하게 한다. 분산 락 글에서 락 해제를 Lua로 묶은 것과 같은 이유다.

Token Bucket을 Lua로 쓰면 다음과 같다. Redis 5 이상을 전제로 한다.

-- KEYS[1]: 버킷 키, ARGV[1]: 용량, ARGV[2]: 초당 보충량, ARGV[3]: 이번 요청 비용
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])

local t   = redis.call('TIME')            -- Redis 서버 시계 하나만 쓴다
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000

local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or capacity
local ts     = tonumber(b[2]) or now

tokens = math.min(capacity, tokens + (now - ts) * rate)

local allowed, retry_after = 0, 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
else
  retry_after = math.ceil((cost - tokens) / rate)
end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) * 2)
return { allowed, retry_after }

redis-cli --eval token_bucket.lua rl:user:42 , 20 5 1

• 시계는 하나만 쓴다. 애플리케이션 서버가 각자 현재 시각을 ARGV로 넘기면 서버 간 시계 차이만큼 보충량이 틀어진다. 늦은 시계를 가진 서버가 쓰면 경과 시간이 음수가 될 수도 있다. TIME으로 Redis 시계를 쓰면 이 문제가 없다. Redis 5부터는 스크립트가 명령이 아니라 결과(effects)로 복제되므로 TIME 뒤에 쓰기를 해도 된다. 그보다 오래된 버전은 redis.replicate_commands()가 필요하다.
• 키는 하나로. Redis Cluster에서는 스크립트의 키가 모두 같은 슬롯에 있어야 한다. 키를 둘 이상 쓰면 {user:42}처럼 해시 태그로 묶는다.
• TTL로 정리한다. 버킷이 가득 차는 시간(C/r)이 지나면 키가 없을 때와 같으므로 지워도 된다.

Redis가 죽으면? Redis 장애가 곧 API 장애가 되지 않게 정책을 미리 정한다. 일반 API는 제한 없이 통과(fail-open)시키고 서버 메모리의 느슨한 한도로 대신하며, 로그인·OTP처럼 남용 방지가 목적인 곳은 거절(fail-closed)한다. 이 판단은 Graceful Degradation과 Circuit Breaker 설계의 기능별 강등 원칙과 같다.

거절 응답: 429와 Retry-After

한도를 넘은 요청에는 429 Too Many Requests(RFC 6585)를 돌려준다. 503은 서버 장애로 읽힌다.

HTTP/1.1 429 Too Many Requests
Retry-After: 3
Content-Type: application/json

{"code":"RATE_LIMITED","message":"요청이 많습니다. 3초 뒤 다시 시도하세요."}

• Retry-After는 초 단위 정수다. 위 Lua 스크립트의 retry_after를 그대로 쓴다.
• 남은 한도를 알려 주는 헤더는 X-RateLimit-Limit, X-RateLimit-Remaining 같은 관행이 많다. IETF에서 RateLimit-Policy·RateLimit 필드를 표준화하는 작업은 아직 초안이고 형식이 바뀌어 왔으므로, 쓴다면 초안 버전을 문서에 적는다.
• 클라이언트는 Retry-After를 지키고, 없으면 지수 백오프에 무작위 지연(jitter)을 더해 재시도한다. 모든 클라이언트가 정확히 3초 뒤 동시에 재시도하면 다시 한도를 넘는다.

어디에 두고 무엇을 키로 삼을까

게이트웨이는 경로·헤더로 판단할 수 있는 공통 제한을, 애플리케이션은 업무 의미가 필요한 제한을 맡는다. 게이트웨이의 역할 나누기는 API Gateway와 BFF 도입 기준에서 다뤘다. Spring Cloud Gateway의 RedisRateLimiter(replenishRate, burstCapacity, requestedTokens)는 Redis 기반 Token Bucket이고, 애플리케이션 안에서는 Bucket4j가 Redis 등 분산 저장소와 함께 쓰인다.

키 설계에서 조심할 점이 있다.

• IP는 사람이 아니다. 회사망과 모바일 통신사는 IP 하나를 여럿이 공유한다. 인증 뒤에는 사용자 ID를 키로 바꾼다. IPv6는 주소 하나가 아니라 대역(예: /64) 단위로 묶어야 우회가 어렵다.
• IP는 믿을 수 있는 곳에서 읽는다. X-Forwarded-For를 그대로 쓰면 클라이언트가 값을 바꿔 한도를 피한다. 신뢰할 프록시 목록은 TLS 종료 지점과 Reverse Proxy 신뢰 경계 설계에 정리했다.

자주 하는 실수

• 인스턴스마다 메모리에 한도를 둔다. 서버를 늘릴 때마다 실제 한도가 같이 늘어난다. resilience4j RateLimiter처럼 JVM 안에서 동작하는 도구는 인스턴스별 한도라는 점을 알고 쓴다.
• INCR와 EXPIRE를 따로 실행한다. 둘 사이에 프로세스가 죽으면 TTL 없는 카운터가 남는다.
• 거절을 503으로 돌려준다. Nginx limit_req의 기본값이 503이다. 클라이언트는 장애로 보고 재시도를 더 세게 하고, 알람은 장애로 울린다.
• 요청 수 제한으로 동시 실행 수까지 막았다고 믿는다. 초당 10회여도 요청 하나가 30초 걸리면 동시에 300개가 돈다. 느린 하류는 동시 실행 수 제한(세마포어, 커넥션 풀)으로 따로 지킨다(Java Virtual Thread 도입 시 Pinning과 자원 고갈 함정).
• Redis 장애 시 동작을 정하지 않는다. 전체 API가 500을 낸다.

점검표

• 제한마다 지키려는 대상(서버 용량, 공정 분배, 남용 방지, 외부 한도)을 적었다.
• 알고리즘을 버스트 허용 여부와 정확도 요구로 골랐다.
• 한도 저장소가 모든 인스턴스가 공유하는 곳에 있다.
• 읽기·비교·쓰기가 Lua 스크립트 하나로 원자적으로 실행된다.
• 시각은 Redis TIME 하나만 쓰고, 애플리케이션 서버 시계를 섞지 않는다.
• 모든 한도 키에 TTL이 있다.
• 거절 응답은 429이고 Retry-After가 들어 있다.
• 인증 전은 IP(신뢰 프록시 기준), 인증 후는 사용자 ID로 키를 바꾼다.
• Redis 장애 시 fail-open과 fail-closed 중 무엇을 할지 경로별로 정했다.
• 거절 건수를 키 종류별로 모니터링한다.

Rate Limiting은 지키려는 대상과 버스트 허용 여부로 알고리즘을 고르고, 공유 저장소에서 원자적으로 계산하며, 429와 Retry-After로 클라이언트가 언제 다시 올지 알려 주는 일이다.