필사 모드: 레이트 리미팅 알고리즘 완전정복: 고정 윈도우·슬라이딩 윈도우·토큰 버킷·리키 버킷

• 들어가며 — 왜 속도를 제한하는가
• 고정 윈도우 카운터 — 가장 단순한 방식
• 슬라이딩 윈도우 로그 — 정확하지만 무겁다
• 슬라이딩 윈도우 카운터 — 실용적인 절충
• 토큰 버킷 — 버스트를 허용하는 우아함
• 리키 버킷 — 흐름을 매끄럽게
• 알고리즘 비교표
• 분산 환경에서의 레이트 리미팅
• 429와 Retry-After — 거절을 잘 전하는 법
• 클라이언트의 백오프 예절
• 마치며
• 참고 자료

들어가며 — 왜 속도를 제한하는가

레이트 리미팅(rate limiting)은 "일정 시간 동안 허용하는 요청 수를 제한하는 것"입니다. 언뜻 사용자를 불편하게 만드는 장치처럼 보이지만, 사실은 시스템 전체를 지키는 안전장치입니다.

레이트 리미팅이 필요한 이유는 여럿입니다. 폭주하는 트래픽이나 오작동하는 클라이언트로부터 서버 자원을 보호하고, 무차별 대입(brute-force) 로그인 시도나 스크래핑 같은 남용을 막으며, 여러 사용자 사이에 자원을 공정하게 나누고, 유료 API의 플랜별 사용량을 강제합니다. 요컨대 안정성과 공정성을 위한 장치입니다.

문제는 "요청 수를 센다"는 단순한 아이디어를 실제로 구현하는 방법이 여러 가지라는 점입니다. 각 방법은 정확성, 메모리 사용량, 버스트 허용 방식에서 서로 다른 트레이드오프를 가집니다. 이 글은 대표적인 알고리즘을 하나씩 대조하고, 분산 환경 구현과 클라이언트 예절까지 다룹니다. 개념을 눈으로 실험해 보고 싶다면 이 사이트의 메시지 큐 놀이터에서 처리량과 흐름 제어를 시각적으로 다뤄 볼 수 있습니다.

고정 윈도우 카운터 — 가장 단순한 방식

가장 직관적인 방법은 시간을 고정된 창(window)으로 나누고, 각 창 안에서 요청 수를 세는 것입니다. 예를 들어 "분당 100회"라면, 매 분이 시작될 때 카운터를 0으로 초기화하고 요청이 올 때마다 1씩 올립니다. 카운터가 100을 넘으면 그 분이 끝날 때까지 거부합니다.

  분당 100회 제한, 고정 윈도우
  [00:00 ~ 00:59]  카운트 0 -> 100 (초과분 거부)
  [01:00 ~ 01:59]  카운트 리셋, 다시 0 -> 100

장점은 명확합니다. 구현이 아주 쉽고, 저장할 상태가 카운터 하나뿐이라 메모리를 거의 쓰지 않습니다. 하지만 치명적인 약점이 있습니다. 창의 경계에서 버스트가 두 배로 터질 수 있다는 점입니다.

예를 들어 어떤 사용자가 00:00:59에 100회를 몰아 보내고, 곧바로 01:00:01에 다시 100회를 보낸다고 합시다. 두 시각은 겨우 2초 차이지만 서로 다른 창에 속하므로 둘 다 허용됩니다. 결과적으로 약 2초 만에 200회가 통과합니다. 명목상 분당 100회 제한인데 실제로는 순간적으로 두 배가 새어 나간 것입니다. 이 경계 문제가 다음 방식들이 등장한 이유입니다.

슬라이딩 윈도우 로그 — 정확하지만 무겁다

경계 문제를 근본적으로 없애려면, 고정된 창 대신 "지금 이 순간으로부터 지난 1분"을 기준으로 삼으면 됩니다. 이것이 **슬라이딩 윈도우 로그(sliding window log)**입니다. 각 요청의 타임스탬프를 모두 기록해 두고, 요청이 올 때마다 "현재 시각에서 1분 이내에 들어온 요청이 몇 개인지"를 세는 것입니다.

  요청이 올 때마다:
  1) 현재 시각 - 60초 보다 오래된 타임스탬프를 로그에서 제거
  2) 남은 로그의 개수를 셈
  3) 개수 < 100 이면 허용하고 현재 타임스탬프 추가, 아니면 거부

이 방식은 완벽하게 정확합니다. 어느 순간을 기준으로 잡아도 정확히 지난 1분간의 요청만 셉니다. 경계에서 두 배로 터지는 일이 없습니다.

대신 비용이 큽니다. 모든 요청의 타임스탬프를 저장해야 하므로, 트래픽이 많을수록 메모리 사용량이 요청 수에 비례해 늘어납니다. 초당 수만 건이 들어오는 API에서 사용자마다 이런 로그를 유지하는 것은 부담스럽습니다. 그래서 정확성은 최고지만, 규모가 큰 곳에서는 다음의 절충안이 선호됩니다.

슬라이딩 윈도우 카운터 — 실용적인 절충

**슬라이딩 윈도우 카운터(sliding window counter)**는 고정 윈도우의 가벼움과 슬라이딩 로그의 정확성 사이의 실용적인 타협점입니다. 아이디어는 현재 창과 직전 창의 카운터만 유지하고, 직전 창의 카운트를 겹치는 비율만큼 가중해서 근사하는 것입니다.

계산은 이렇게 합니다. 현재 창에서 이미 경과한 비율을 알면, 직전 창은 그만큼 덜 겹칩니다. 따라서 추정 요청 수는 다음과 같습니다.

  추정치 = 현재 창 카운트
         + 직전 창 카운트 * (직전 창에서 아직 겹치는 비율)

  예: 분당 100회, 현재 창이 25% 경과한 시점
      직전 창 카운트 = 80, 현재 창 카운트 = 30 이라면
      추정치 = 30 + 80 * (1 - 0.25) = 30 + 60 = 90
      90 < 100 이므로 허용

이 근사는 트래픽이 창 안에서 대체로 고르게 분포한다는 가정에 기댑니다. 완벽하지는 않지만 실무에서 오차가 작고, 저장할 상태가 카운터 두 개뿐이라 매우 가볍습니다. 그래서 상용 서비스의 레이트 리미터가 흔히 채택하는 방식입니다. 고정 윈도우의 경계 버스트 문제를 대부분 해소하면서도 슬라이딩 로그의 메모리 부담을 피합니다.

토큰 버킷 — 버스트를 허용하는 우아함

지금까지의 방식이 "얼마나 많이 왔는가"를 세는 데 집중했다면, **토큰 버킷(token bucket)**은 관점을 바꿉니다. 요청을 세는 대신, 요청을 처리할 권리인 토큰을 나눠 줍니다.

동작 원리는 이렇습니다. 정해진 속도로 버킷에 토큰이 채워집니다(예: 초당 10개). 버킷에는 최대 용량이 있습니다(예: 100개). 요청이 오면 토큰을 하나 꺼내 씁니다. 토큰이 있으면 통과, 없으면 거부입니다.

  토큰 버킷 (용량 100, 리필 속도 초당 10)
   토큰이 초당 10개씩 떨어져 버킷에 쌓임 (최대 100)
       │
       ▼
   [ 버킷: ●●●●●●... 최대 100개 ]
       │  요청 1건당 토큰 1개 소모
       ▼
   토큰 있으면 통과, 없으면 거부

토큰 버킷의 아름다움은 버스트를 자연스럽게 허용한다는 데 있습니다. 한동안 요청이 없으면 토큰이 버킷 가득 쌓입니다(최대 100개). 그러다 갑자기 요청이 몰리면, 쌓여 있던 토큰만큼 한꺼번에 통과시킬 수 있습니다. 즉 평소 조용하던 클라이언트가 순간적으로 몰아 보내는 것을 용인하되, 장기적인 평균 속도는 리필 속도(초당 10개)로 제한합니다. 버킷 용량이 버스트의 최대치를, 리필 속도가 지속 가능한 평균을 결정합니다.

이 유연함 덕분에 토큰 버킷은 실무에서 가장 널리 쓰이는 알고리즘 중 하나입니다. 많은 API 게이트웨이와 네트워크 장비가 이 방식을 씁니다.

리키 버킷 — 흐름을 매끄럽게

**리키 버킷(leaky bucket)**은 이름처럼 "새는 양동이"에 비유됩니다. 요청이 양동이(큐)에 담기고, 바닥의 구멍으로 일정한 속도로 새어 나가며 처리됩니다. 양동이가 가득 차면 넘치는 요청은 버려집니다.

  리키 버킷
   요청이 위에서 큐에 쌓임
       │
       ▼
   [ 큐: 요청들이 대기 ]
       │  바닥에서 일정 속도로 처리 (예: 초당 10건)
       ▼
   큐가 가득 차면 넘치는 요청은 버려짐

토큰 버킷과 리키 버킷은 자주 비교됩니다. 핵심 차이는 출력의 성격입니다.

• 토큰 버킷은 버스트를 허용합니다. 토큰이 쌓여 있으면 순간적으로 많이 통과합니다. 출력이 울퉁불퉁할 수 있습니다.
• 리키 버킷은 출력을 매끄럽게 만듭니다. 아무리 입력이 몰려도 바닥 구멍의 속도로만 나가므로, 처리 속도가 일정합니다. 대신 순간적인 버스트를 흡수하려면 큐에서 기다려야 해서 지연이 생길 수 있습니다.

그래서 선택은 목적에 달렸습니다. "가끔의 버스트를 관대하게 허용하되 평균만 지키고 싶다"면 토큰 버킷, "다운스트림을 보호하기 위해 처리 속도를 일정하게 고르고 싶다"면 리키 버킷이 맞습니다.

알고리즘 비교표

지금까지의 내용을 한 표로 정리하면 다음과 같습니다.

분산 환경에서의 레이트 리미팅

지금까지는 하나의 서버를 가정했습니다. 하지만 실제 서비스는 여러 대의 서버 인스턴스가 로드 밸런서 뒤에서 함께 요청을 처리합니다. 여기서 문제가 생깁니다. 각 인스턴스가 자기만의 카운터를 들고 있으면, 전체 제한이 인스턴스 수만큼 뻥튀기됩니다. 인스턴스가 5대이고 각각 분당 100회를 허용하면, 사용자는 사실상 분당 500회를 쓸 수 있게 됩니다.

해결책은 카운터를 인스턴스 밖의 공유 저장소에 두는 것입니다. 이 역할로 가장 널리 쓰이는 것이 Redis입니다. 빠른 인메모리 저장소이고, 원자적 연산과 키 만료(TTL)를 지원하기 때문입니다.

고정 윈도우를 Redis로 구현하는 간단한 예를 봅시다.

  키:  ratelimit:{user_id}:{현재_분}
  1) INCR 키          -> 카운터를 원자적으로 1 증가시키고 새 값을 받음
  2) 값이 1이면 EXPIRE 키 60   -> 이 창이 지나면 자동 삭제되도록 TTL 설정
  3) 값 > 100 이면 거부, 아니면 허용

여기서 중요한 것은 **원자성(atomicity)**입니다. "읽고, 비교하고, 증가시키는" 과정이 여러 단계로 쪼개지면, 동시에 들어온 요청들 사이에 경쟁 상태(race condition)가 생겨 제한을 넘길 수 있습니다. Redis의 INCR은 그 자체로 원자적이고, 더 복잡한 로직(슬라이딩 윈도우나 토큰 버킷)은 여러 명령을 하나의 원자적 단위로 묶는 Lua 스크립트로 구현합니다. Redis는 Lua 스크립트를 단일 스레드로 원자 실행하므로 경쟁 상태를 피할 수 있습니다.

분산 레이트 리미팅에는 추가로 고려할 점이 있습니다. 공유 저장소에 매 요청마다 접근하면 지연과 부하가 생기므로, 약간의 정확도를 희생하고 로컬에서 근사한 뒤 주기적으로 동기화하는 방식도 씁니다. 정확성과 성능 사이의 트레이드오프는 여기서도 반복됩니다.

429와 Retry-After — 거절을 잘 전하는 법

레이트 리미터가 요청을 거부하기로 했다면, 그 사실을 클라이언트에게 명확히 알려야 합니다. 이때 쓰는 것이 HTTP 상태 코드 429 Too Many Requests입니다. 이 코드는 "당신이 너무 많이 요청했다"는 뜻을 표준적으로 전달합니다.

429만 보내는 것으로 끝이 아닙니다. 좋은 레이트 리미터는 언제 다시 시도하면 되는지도 함께 알려 줍니다. 이를 위한 헤더가 Retry-After입니다. 값은 초 단위 대기 시간이거나 특정 시각일 수 있습니다.

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

{ "error": "rate limit exceeded", "retry_after": 30 }

많은 API는 여기에 더해, 현재 남은 할당량을 알려 주는 헤더도 제공합니다. 예를 들어 RateLimit-Limit(총 한도), RateLimit-Remaining(남은 횟수), RateLimit-Reset(초기화까지 남은 시간) 같은 헤더입니다. 이런 정보가 있으면 클라이언트는 벽에 부딪히기 전에 미리 속도를 조절할 수 있습니다. 429를 비롯한 상태 코드들의 정확한 의미가 궁금하다면 HTTP 상태 코드 도감에서 각 코드를 살펴볼 수 있습니다.

클라이언트의 백오프 예절

레이트 리미팅은 서버만의 일이 아닙니다. 429를 받은 클라이언트가 어떻게 반응하느냐도 시스템 전체의 건강에 큰 영향을 줍니다. 429를 받자마자 곧바로 다시 시도하는 클라이언트는 서버를 더 괴롭힐 뿐입니다.

올바른 반응은 백오프(backoff), 즉 재시도 간격을 점점 늘리는 것입니다.

• 지수 백오프(exponential backoff): 재시도할 때마다 대기 시간을 배로 늘립니다. 1초, 2초, 4초, 8초... 이렇게 하면 서버가 회복할 시간을 줍니다.
• 지터(jitter) 추가: 여러 클라이언트가 똑같은 간격으로 재시도하면, 그 재시도들이 한꺼번에 몰려 다시 서버를 때리는 "천둥 무리(thundering herd)" 문제가 생깁니다. 그래서 대기 시간에 약간의 무작위성을 더해 재시도 시점을 분산시킵니다.
• Retry-After 존중: 서버가 Retry-After로 대기 시간을 알려 줬다면, 자기 계산보다 그 값을 우선해서 따르는 것이 예의입니다.
• 상한 두기: 무한정 재시도하지 않도록 최대 재시도 횟수나 최대 대기 시간을 정해 둡니다.

  429 수신 시:
   대기 = min(기본 * 2^시도횟수, 상한) + 무작위_지터
   Retry-After 헤더가 있으면 그 값을 우선

정리하면, 잘 설계된 레이트 리미팅은 서버의 거절과 클라이언트의 절제가 함께 맞물릴 때 완성됩니다. 서버는 429와 Retry-After로 명확히 신호를 보내고, 클라이언트는 지수 백오프와 지터로 예의 바르게 물러납니다.

마치며

레이트 리미팅은 "요청 수를 센다"는 단순한 목표를 품고 있지만, 그 구현에는 정확성, 메모리, 버스트 허용이라는 세 축을 두고 다양한 절충이 존재합니다. 고정 윈도우는 단순하지만 경계에서 새고, 슬라이딩 로그는 정확하지만 무겁고, 슬라이딩 카운터는 그 사이의 실용적 균형입니다. 토큰 버킷은 버스트를 우아하게 허용하고, 리키 버킷은 출력을 매끄럽게 고릅니다.

여기에 분산 환경에서는 Redis 같은 공유 저장소와 원자적 연산이 필요하고, 클라이언트 쪽에서는 429와 Retry-After에 대한 예의 바른 백오프가 필요합니다. 핵심은 "어떤 알고리즘이 옳은가"가 아니라 "이 시스템이 무엇을 지키려 하는가"입니다. 그 답을 정하면, 어떤 도구를 골라야 할지도 자연스럽게 따라옵니다.

참고 자료

• Cloudflare Learning: What is rate limiting? — https://www.cloudflare.com/learning/bots/what-is-rate-limiting/
• Stripe: Rate limiters — https://stripe.com/blog/rate-limiters
• MDN: 429 Too Many Requests — https://developer.mozilla.org/en-US/docs/Web/HTTP/Status/429
• MDN: Retry-After header — https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/Retry-After
• IETF: RateLimit header fields for HTTP — https://datatracker.ietf.org/doc/draft-ietf-httpapi-ratelimit-headers/
• AWS Architecture Blog: Exponential backoff and jitter — https://aws.amazon.com/blogs/architecture/exponential-backoff-and-jitter/