[대규모 시스템 설계 기초] 4장. 처리율 제한 장치의설계 - 2

앞선 글에서는 Rate Limiter를 어디 레이어에 배치할 것인지(클라이언트 vs 서버 vs 게이트웨이 vs 인프라) 에 대해 이제 “어디에 둘 것인가”를 결정했다면, 다음 고민은 자연스럽게 이렇게 이어진다. 정확하고 성능 좋은 알고리즘은 무엇인가? 

Rate Limiter는 단순히 count++로 해결되지 않는다.
Time Window, Token Bucket, Leaky Bucket, Sliding Log, Hybrid 방식 등 여러 알고리즘이 존재하며,
각 방식은 정확도, 성능, 메모리, 구현 난이도, 분산 처리 가능 여부가 모두 다르다.

또한 알고리즘을 선택했다 하더라도, 실제 시스템에서는 아래와 같은 아키텍처적 고민이 필요하다.

• 중앙 저장소를 사용할 것인가? (Redis, DB, in-memory 등)
• Race Condition은 어떻게 해결할 것인가?
• Lua Script 같은 원자적 연산이 필요한가?
• 멀티 인스턴스 / 멀티 리전에서는 어떻게 동기화할 것인가?
• 장애 발생 시 Fail-Open / Fail-Close 중 무엇을 선택할 것인가?

A. 토큰 버킷 알고리즘 

• capacity : 버킷 최대 토큰 수 (버스트 허용량)
• refill_rate : 초당 채워지는 토큰 수 (예: 100 req/s)
• tokens : 현재 남은 토큰 수
• last_refill_ts : 마지막으로 토큰 계산/적용한 시각(밀리초)

요청 1건당 토큰 1개를 소비하고, 남은 토큰이 없으면 제한(429) 으로 생각해보면 된다. 

• in-memory(프로세스 로컬): 지연·비용 최저지만, 인스턴스가 여러 대면 각자 따로 센다 ⇒ 정확성 낮음 (보조 캐시 용도로는 OK) 
• Redis: 단일·클러스터로 확장 가능, Lua 스크립트로 원자성 보장, 지연/비용/정확성 밸런스 가장 좋음
• RDBMS: 트랜잭션은 좋지만 QPS가 높을수록 락/경합/지연 문제. 실시간 레이트 리밋에는 보통 부적합

만약에 고른다면 Redis(싱글 리전은 Cluster, 멀티 리전은 지역별 Redis + 상위정책) 로 선택하고 원자성 확보로 진행할 수 있을거 같다. 

키설계

• subject = 식별자: IP, userId, apiKey, clientId+route 등 조합
• Redis 키: rl:{route}:{subject}

버킷 데이터 모델

HSET rl:{route}:{subject} 
  capacity <int> 
  refill_rate <double> 
  tokens <double> 
  last_refill_ts <millis>

 

TTL: 사용하지 않은 객체를 위해 EXPIRE(예: 10~60분) 걸기

Race Condition 해결: Lua 원자 스크립트

요청마다 리필 계산 + 토큰 차감을 한 번에 수행할 수 있다 (원자성) 

처리 flow

Redis 특성상 명령들은 각각 독립적으로 실행되기 때문에, 그 사이에 다른 클라이언트의 명령이 끼어들게 되면 Race Condition이 발생할 수 있는데 Lua 원자 스크립트를 사용해서 Redis 명령어를 한번에 실행할 수 있다.

Spring Boot
 └─ RedisTemplate
      └─ execute(RedisScript, keys, args...)
             ↓
          Redis (EVAL / EVALSHA)
             ↓
          Lua Script 실행

• (1) 남은 토큰을 시간 경과만큼 리필,
• (2) 1개 소비 가능하면 차감 후 허용,
• (3) 아니면 거절 및 다음 가능 시각 계산.

멀티 인스턴스(단일 리전)

• 중앙 Redis를 공유하면 끝. Race Condition은 Lua로 해결.

B. 누출 버킷 알고리즘

입력은 들쑥날쑥해도, 출력은 항상 일정한 속도로만 흘려보내는 트래픽을 처리하는 알고리즘 

토큰 버킷과 차이점

• 토큰 버킷은 평소 토큰을 모았다가 버스트를 허용하면서 평균 속도 제한, 사용자 경험에 효과적이다.
• 누출 버킷은 출력이 항상 일정하다. 버스트를 지연하거나 드롭시킨다. 

실제 트래픽을 받는다고 가정하고 어떤 알고리즘을 쓸지 고민해본다면

• 짧은 버스트를 허용한다면 토큰 버킷으로 적용
• 백엔드 안정 및 최소화 한다면 일정 배출 속도가 중요하다면 누출 버킷

C. 고정 윈도 카운트 알고리즘

일정한 시간 구간(window, 예: 1초·1분·1시간)마다 요청 수를 세고, 허용치를 넘으면 그 구간의 남은 시간 동안 요청을 차단(429) 하는 방식

시간 구간별 요청 카운트 제한이다. 

고정 윈도 카운트 알고리즘 단점

윈도우가 새로 바뀌는 순간, 두 윈도우 사이에 요청이 몰리면 실제로는 limit * 2 만큼 허용할 수 있다. 

D. 이동 윈도 카운터 알고리즘

정해진 시간 구간 내 요청 수를 부드럽게 계산하여, 고정 윈도(Fixed Window)의 경계 문제를 완화한 방식이다. 이 방식은 윈도우가 고정되어 있지 않고, 시간 흐름에 따라 부드럽게 이동한다. 

E. 슬라이딩 윈도 카운터로 분산 설계

현재 시점 기준으로 이전 윈도우와 현재 윈도우를 동시에 고려해야 한다. Redis에 2개의 카운터(이전/현재)를 저장할 수 있다. 

현재 윈도우 카운터 

key - rate:api:/search:user:1001:curr:20251028T1420 

• 현재 시각 기준 윈도우의 요청 수 

이전 윈도우  카운터

key - rate:api:/search:user:1001:prev:20251028T1419

직전 윈도우 요청 수 

각 윈도우 TTL 은 window * 2 로 설정한다. 두 윈도우가 동시에 존재해야 가중치 계산을 가능하게 해준다.

동작 순서 (Step-by-Step Flow)

1. 클라이언트 요청 수신
   • 예: /api/search 호출
   • 현재 시간: 14:20:30, 윈도우 크기 60초
2. 현재/이전 윈도우 계산
   • 현재 윈도우: 14:20
   • 이전 윈도우: 14:19
   • 경과 시간: 30초 
     → 가중치(weight) = 30 / 60 = 0.5

지금은 새 윈도우의 절반쯤 진행된 시점이니까, 이전 윈도우 트래픽의 절반 정도만 반영한다. 그래서 윈도우가 바뀌는 순간 14:19 ~ 14:20 에 트래픽 카운터가 끊키지 않고 이어지게 된다. 

1. Redis에 INCR 실행
   • 현재 윈도우 키: rate:search:user:1001:curr:14:20
   • 이전 윈도우 키: rate:search:user:1001:prev:14:19
   • 현재 윈도우 카운터는 INCR
   • 이전 윈도우 카운터는 GET
   • 현재 윈도우 (14:20) 에 요청이 들어오면 INCH 1 증가한다. 
   • Rate Limit 는 현재 1분만 보는건 아니고 이전 1분의 일부도 함께 고려한다. 지난 시점에 확보된 요청 수는 증가시키지 않고 읽기만 한다. 
2. 둘이 합쳐서 슬라이딩 계산
   • 현재 시점이 14:20:30 이라면 30초가 지났으므로 현재 윈도우가 50%, 이전 윈도우가 50% 기여하게 됩니다. 

total_requests =
  (prev_count * 0.5) + (curr_count * 0.5)

이렇게 사용자의 요청 한도가 넘었는지 알 수 있다. 

여기까지 Redis 기반 이동 윈도 카운터 방식의 핵심 원리와 구현 과정을 정리해보았다. 
하지만 실제 대규모 트래픽 환경에서는 단순히 알고리즘만으로는 부족하고, 인프라 구조와 동시성 제어, 장애 대응 전략까지 함께 고려해야 한다. 다음 포스팅에서는 이 Rate Limiter를 실제 서비스에 녹여내기 위한 아키텍처 설계를 단계별 써보겠다!!