Chiko IT
보안

Redis rate limiting 구현 실전: Token Bucket vs Sliding Window와 DDoS 방어

Chiko
14min read

목차

변경 전후 한눈에 보기

즉, Redis rate limiting 구현을 단순 INCR + EXPIRE로 끝내두고 6개월을 안심하고 있었다. 결제 API에 외부 파트너가 붙으면서 그 단순함이 무너졌다. 60초당 600회로 걸어둔 제한이 한 파트너의 burst 패턴 앞에서 무력화됐고, 이상 트래픽 알림이 뜨고 나서야 카운터의 동작 방식을 다시 들여다보게 됐다.

구분 Before (Fixed Window) After (Sliding Window Log + 일부 Token Bucket)
알고리즘 INCR + EXPIRE Lua 기반 Sliding Window + 일부 Token Bucket
burst 1초 800req 통과 차단
평균 추적 정확도 윈도우 경계서 ±100% 오차 오차 1% 이하
Redis 명령 수/요청 2 4~5 (Lua 1회로 묶음)
체감 p99 지연 0.3ms 0.7ms
운영 코드 약 30줄 약 120줄 + Lua 60줄

반면, Before는 가볍고 After는 약간 무겁다. 무겁지만 외부 노출 API라면 After가 맞다는 게 결론이다. 어떻게 갈아엎었고 어디서 멈췄는지 그대로 적는다.

첫 시도가 실패한 이유 — Fixed Window의 경계 문제

원래 코드는 이랬다. FastAPI 미들웨어에서 INCR 후 첫 호출이면 EXPIRE로 60초 TTL을 박고, 카운터가 한도를 넘으면 429를 돌려줬다.

# 주의: 이 코드는 burst를 못 막는다 — 아래에서 설명
async def fixed_window_limit(request, redis, limit=600, window=60):
    key = f"rl:{request.client.host}"
    count = await redis.incr(key)
    if count == 1:
        await redis.expire(key, window)  # 첫 호출에만 TTL 설정
    if count > limit:
        raise HTTPException(429, "rate limit exceeded")

또한, 문제는 윈도우 경계였다. 12:00:59에 599회를 쏘고 12:01:00에 다시 600회를 쏘면, 분당 한도는 지키지만 1초 안에 1199회가 들어온다. 외부 파트너의 배치 작업이 정확히 이 패턴이었다. 평균 그래프는 평탄해 보였다. 다만 1초 단위 RPS 그래프를 따로 떠보니 spike가 정확히 매분 0초에 박혀 있었다.

원인을 찾는 데 한참 헤맸다. 처음엔 클라이언트 retry 로직을 의심했고, 그 다음엔 LB 라우팅 분포를 봤다. Redis 카운터의 윈도우 경계 자체가 문제라는 결론은 마지막에 나왔다. Fixed Window는 구현이 단순한 만큼 burst 보호 용도로는 부적합하다. 공식 문서에도 한계가 명시돼 있는데(출처: Redis Rate Limiting 패턴 문서, 작성 시점 2026-04 기준) 처음 깔 때는 별로 신경 쓰지 않았던 부분이다.

Token Bucket으로 바꿔봤는데

다음으로 시도한 게 Token Bucket이다. 통신 분야에서 오래 쓰던 알고리즘이고, burst를 일정 크기까지 허용하면서 평균 rate를 유지하는 모델이다.

동작 방식 요약

실제로, 버킷에 토큰이 쌓이고, 요청 1건당 토큰 1개를 소모한다. 토큰은 정해진 비율로 보충된다. 버킷이 비면 거절한다. 버킷 크기가 burst 허용량이고 보충 속도가 평균 rate다.

-- token_bucket.lua — atomic 처리를 위해 Lua로 묶음
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])  -- tokens per second
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

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

-- 경과 시간만큼 토큰 보충
local elapsed = math.max(0, now - ts)
tokens = math.min(capacity, tokens + elapsed * refill_rate)

local allowed = 0
if tokens >= requested then
    tokens = tokens - requested
    allowed = 1
end

redis.call('HMSET', key, 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', key, 3600)
return {allowed, tokens}

이 방식의 매력은 burst 허용량을 명시적으로 조절할 수 있다는 점이다. 평균 10rps에 버킷 100이면, 평소엔 잠잠하다가도 갑자기 100건까지는 허용한다. 결제 API의 일부 엔드포인트, 예를 들어 정기 정산 트리거처럼 의도적인 burst가 정상인 곳에 적합하다.

그런데 왜 충분하지 않았나

문제는 burst 자체를 거부해야 하는 엔드포인트였다. 외부에 노출된 인증 엔드포인트는 의도된 burst가 없고, 짧은 시간 안에 여러 번 들어오는 시도 자체가 비정상 신호다. Token Bucket은 burst를 정상 동작으로 인정하기 때문에, 1초에 100건이 들어오면 그냥 통과시킨다. 버킷 크기를 1로 만들면 막을 수 있지만 그 순간 알고리즘의 의미가 사라진다.

게다가 버킷 크기와 보충 속도 두 변수의 조합을 엔드포인트마다 튜닝해야 했다. 운영 입장에서 변수가 늘어나는 게 부담스러웠다.

Sliding Window Log — Lua로 원자성 확보

결국 Sliding Window Log로 갔다. 요청 시각을 전부 저장하고 윈도우 안에 들어오는 요청 수를 세는 방식이다. 가장 정확하다. 메모리는 더 든다.

Redis에서는 ZSET으로 구현한다. score에 timestamp(ms), member에 unique id(timestamp + 짧은 nonce)를 넣는다.

-- sliding_window_log.lua
local key = KEYS[1]
local now = tonumber(ARGV[1])      -- 현재 시각(ms)
local window = tonumber(ARGV[2])   -- 윈도우 크기(ms)
local limit = tonumber(ARGV[3])
local member = ARGV[4]

-- 윈도우 밖 요청 제거
redis.call('ZREMRANGEBYSCORE', key, 0, now - window)

local current = redis.call('ZCARD', key)
if current >= limit then
    return {0, current}
end

redis.call('ZADD', key, now, member)
redis.call('PEXPIRE', key, window)
return {1, current + 1}

예를 들어, Python 쪽은 짧다. register_script로 SHA를 캐싱하고 EVALSHA로 호출한다.

import redis.asyncio as redis
import uuid, time

class SlidingWindowLimiter:
    def __init__(self, r: redis.Redis, limit: int, window_ms: int):
        self.r = r
        self.limit = limit
        self.window_ms = window_ms
        self.script = self.r.register_script(LUA_SCRIPT)

    async def allow(self, key: str) -> bool:
        now_ms = int(time.time() * 1000)
        member = f"{now_ms}:{uuid.uuid4().hex[:8]}"
        result = await self.script(
            keys=[key],
            args=[now_ms, self.window_ms, self.limit, member],
        )
        return result[0] == 1

특히, Lua로 묶은 이유는 race condition 때문이다. ZREMRANGEBYSCORE, ZCARD, ZADD를 따로 호출하면 그 사이에 다른 요청이 끼어든다. 한도 근처에서 1~2건씩 새는 게 운영 중 발견됐고, Lua로 묶고 나서야 정확히 떨어졌다.

메모리는 무시 못 한다

예를 들어, ZSET 한 entry가 대략 60~100 byte다. 분당 600 요청 기준 활성 사용자 1만 명이면 600 × 10000 × 80 = 약 480MB가 든다. 사용자가 더 많거나 윈도우가 더 길면 부담이 빠르게 커진다. 윈도우를 60초로 제한하고 ZSET expire를 윈도우와 동일하게 박아서 자연 청소되도록 했다. 그래도 메모리 모니터링은 별도로 걸어둘 필요가 있다.

Sliding Window Counter — 정확도와 메모리 사이 절충

메모리 부담이 클 때는 Sliding Window Counter라는 변형이 있다. Cloudflare가 공개한 방식인데(출처: Cloudflare Blog 2017-04-13 — Counting things, a lot of different things), 두 개의 Fixed Window 카운터를 가중평균으로 섞는다.

현재 시각이 12:00:30이면 12:00:00~12:01:00 윈도우의 카운터와 11:59:00~12:00:00 윈도우의 카운터를 보고 다음과 같이 계산한다.

estimated = current_count + previous_count * (1 - elapsed_in_current / window_size)

물론, 12:00:30 시점이면 이전 윈도우는 50%만 가중치로 반영된다. 정확도는 90~99% 정도, 메모리는 사용자당 카운터 2개로 끝난다.

async def sliding_counter(r, key, limit, window_sec=60):
    now = int(time.time())
    cur_win = now // window_sec
    elapsed = now % window_sec

    cur_key = f"{key}:{cur_win}"
    prev_key = f"{key}:{cur_win - 1}"

    cur, prev = await r.mget(cur_key, prev_key)
    cur = int(cur or 0)
    prev = int(prev or 0)

    estimated = cur + prev * (1 - elapsed / window_sec)
    if estimated >= limit:
        return False

    pipe = r.pipeline()
    pipe.incr(cur_key)
    pipe.expire(cur_key, window_sec * 2)  # 다음 윈도우 계산까지 보존
    await pipe.execute()
    return True

그러나, 이건 Lua를 안 써도 큰 문제 없다. INCR이 atomic하고 estimation은 약간의 오차를 전제로 하기 때문이다. 다만 분산 환경의 한도 근처에서는 보수적으로 거절하는 편이 안전하다.

체감으로는, 정확한 burst 제어가 필요한 결제·인증 엔드포인트는 Sliding Window Log, 검색·조회처럼 폭넓게 적용하는 일반 quota는 Sliding Window Counter를 쓰는 게 운영하기 편하다.

알고리즘 비교 정리

세 방식의 비교를 한 표로 묶었다. 운영하면서 체감한 수치 위주다.

알고리즘 burst 제어 정확도 메모리/사용자 구현 복잡도 권장 용도
Fixed Window 약함 윈도우 경계서 ±100% 오차 가능 카운터 1 (~16B) 낮음 내부 quota, 대략적 제한
Token Bucket 의도적 burst 허용 정확 해시 1 (~80B) 중간 정기 배치, 의도된 burst 허용
Sliding Window Log 강함 오차 0% 윈도우 내 요청 수 × ~80B 중간 인증, 결제 등 정확도 필수
Sliding Window Counter 강함 90~99% 카운터 2 (~32B) 낮음 외부 API 일반 quota

표를 만들면서 다시 느낀 건, 한 알고리즘으로 모든 엔드포인트를 처리하려는 시도 자체가 무리였다는 점이다. 트래픽 특성이 다르면 알고리즘도 다르게 가야 한다.

rate limit만으로 DDoS는 못 막는다

게다가, Rate limit을 정밀하게 깔아두고 DDoS도 자연스럽게 방어된다고 잠깐 착각했다. 실제로는 다른 얘기다.

한편, L7 rate limit이 동작하려면 요청이 애플리케이션까지 도달해야 한다. 도달했다는 건 이미 TCP 핸드셰이크와 TLS 세션이 끝났다는 뜻이다. 초당 수십만 건의 SYN flood나 UDP amplification 앞에서 애플리케이션 레이어 카운터는 무력하다. Redis 자체가 먼저 죽거나, 그 전에 LB가 먼저 죽는다.

다층 방어가 기본

운영 환경에서 실제로 깐 구성:

  • L3/L4: 클라우드 제공자의 DDoS 보호(AWS Shield Standard 또는 Cloudflare). SYN flood, UDP flood 같은 볼륨 공격은 여기서 끊는다.
  • L7 WAF: 비정상 패턴(잘못된 User-Agent, SQL 인젝션 페이로드 등) 차단. CloudFront 또는 Cloudflare WAF로 처리.
  • 애플리케이션 rate limit: Redis 기반 sliding window. 정상 트래픽 안의 비정상 패턴을 본다.
  • 인증 후 quota: API key 또는 사용자 토큰 단위로 별도 카운터.

L3/L4와 WAF가 99%를 걸러내고, Redis rate limiting 구현은 마지막 1%를 정밀하게 처리하는 그림이다. 이 순서를 거꾸로 잡으면 Redis가 먼저 무너진다.

차단 키 설계

IP 단독으로 키를 만들면 NAT 뒤의 다수 사용자를 같이 차단한다. 사내 회선 한 곳에서 들어오는 정상 트래픽이 같이 막혔던 적이 있다. 이후 키 조합을 다음 순서로 바꿨다.

  1. 인증 토큰이 있으면 토큰 기반
  2. 없으면 (IP, User-Agent 해시) 조합
  3. 그래도 의심스러운 패턴이면 (IP, 엔드포인트) 조합

물론, 토큰 기반이 1순위인 이유는 NAT 뒤에서도 토큰별로 분리되기 때문이다. 익명 트래픽에만 IP 기반을 쓰되, 단독 IP는 피했다.

언제 무엇을 쓸 것인가 — 판단 기준

알고리즘 선택은 트래픽 특성과 운영 비용으로 갈린다. 직접 운영하면서 잡은 기준이다.

  • 내부 서비스 간 quota → Fixed Window. 신뢰 도메인 안이고 burst 보호가 필요 없으면 단순함이 정답이다.
  • 의도된 burst가 정상인 엔드포인트(정산, 배치 트리거) → Token Bucket. 버킷 크기로 burst 허용량을 명시.
  • 외부 노출 인증/결제 엔드포인트 → Sliding Window Log + Lua. 정확도 우선, 메모리 비용 감수.
  • 외부 노출 일반 API quota → Sliding Window Counter. 1만~수십만 사용자 규모에서 메모리/정확도 균형이 가장 좋았다.
  • DDoS 방어 → L3/L4 + WAF + L7 rate limit 다층. 단일 레이어 의존 금지.

당장 적용한다면 이 세 가지부터다.

  1. 현재 깔린 rate limit이 Fixed Window라면 1초 단위 RPS 그래프를 따로 떠보고 윈도우 경계 spike가 있는지 확인한다. 있으면 Sliding Window 계열로 옮길 후보다.
  2. Lua 스크립트는 Redis 버전과 함께 명시적으로 버전 관리한다. 같은 EVAL이 환경마다 다르게 동작하면 추적이 끔찍하다(Redis 7.0부터 함수와 ACL 카테고리가 추가돼 이전 버전과 동작/권한이 다르다 — 출처: Redis 7.0.0 release notes).
  3. rate limit 키 설계에 인증 토큰을 1순위로 넣는다. IP 단독은 NAT를 같이 죽인다.

현재 결제 API는 Sliding Window Log 기반으로 6개월째 운영 중이고, 윈도우 경계 spike는 사라진 상태로 운영 중이다. 메모리는 Redis 노드당 1.2GB 수준에서 안정 유지된다. 의도된 burst가 있는 정산 트리거만 Token Bucket을 따로 두고, 검색 API는 Sliding Window Counter로 가볍게 처리한다. 한 알고리즘으로 모든 걸 끝내려던 6개월 전의 발상이 잘못이었다.

관련 글

More posts