16. 레이트 리미팅 알고리즘: 토큰 버킷·누수 버킷·고정/슬라이딩 윈도우와 분산 적용

난이도: 중

1. 왜 필요한가

레이트 리미팅은 클라이언트별 요청 속도에 상한을 두어 ① 채팅 도배/스팸(session_network/problem16), ② 로그인 무차별 대입(brute force), ③ 거래/우편/가챠 API 남용(봇·매크로), ④ 특정 엔드포인트 폭주로 인한 백엔드 과부하·연쇄 장애(distributed_systems/problem7)를 막는다.

단순히 "초당 N회"만 세면 버스트를 잘못 다룬다. 정상 사용자도 화면 전환 시 여러 요청을 몰아 보내고, 반대로 공격자는 평균은 낮게 유지하며 순간 폭주로 큐를 채울 수 있다. 좋은 리미터는 평균 속도는 제한하되 짧고 합리적인 버스트는 허용해야 한다 — 이 균형을 알고리즘이 결정한다.

2. 토큰 버킷(token bucket)

용량 B 인 버킷에 초당 r 개씩 토큰을 채운다(가득 차면 넘침은 버림). 요청이 오면 토큰 1개(또는 비용만큼)를 소비하고, 토큰이 없으면 거부/지연한다.

• 리필 속도 r → 장기 평균 허용 속도를 통제.
• 용량 B → 허용 버스트 크기를 통제(버킷에 쌓인 토큰만큼 순간 몰아쓰기 가능).
• 그래서 "평소엔 쉬다가 가끔 몰아 보내는" 패턴을 자연스럽게 허용하면서 평균은 묶는다. 구현은 타임스탬프 기반 lazy refill 로 O(1): tokens = min(B, tokens + (now - last) * r) 후 1 차감. 게임 API 리밋의 사실상 표준.

3. 누수 버킷(leaky bucket)

요청을 큐(버킷)에 넣고, 큐에서 고정 속도 r 로 하나씩 빼서 처리("새어나감"). 큐가 가득 차면 새 요청을 드롭(또는 거부).

• 토큰 버킷이 버스트를 통과시키는 반면, 누수 버킷은 출력을 평활화(항상 일정 속도로 처리)한다 — 다운스트림을 일정 부하로 보호하는 트래픽 셰이핑에 적합.
• 단점: 버스트를 큐잉하므로 지연이 늘고, 큐 크기가 곧 버퍼링 한계. 게임에선 "다운스트림(예: DB 쓰기)을 일정 속도로 보호"할 때.

4. 고정 윈도우 vs 슬라이딩 윈도우

• 고정 윈도우 카운터: "매 분 100회"처럼 윈도우마다 카운터를 리셋. 단순·가볍지만 경계 폭주 문제 — 한 윈도우 끝 0:59 에 100회, 다음 윈도우 시작 1:00 에 또 100회를 몰면 2초 만에 200회가 통과해 사실상 한도의 2배.
• 슬라이딩 윈도우 로그: 각 요청 타임스탬프를 저장하고 "지금-윈도우" 안의 개수를 센다. 정확하지만 요청마다 기록이 쌓여 메모리·정리 비용이 크다.
• 슬라이딩 윈도우 카운터(근사): 현재 윈도우 카운트 + 직전 윈도우 카운트 × (겹치는 비율)로 추정. 경계 폭주를 크게 완화하면서 메모리는 카운터 두 개로 가볍다. 실무에서 가장 흔한 절충.

5. 게임 적용과 분산 환경

• 무엇을 키로: 보통 여러 차원을 동시에 — 계정별(거래/우편), IP·디바이스별(로그인·회원가입, 계정 우회 방지), 엔드포인트별(비싼 API 는 더 빡빡하게), 전역(백엔드 보호). 키 = (엔드포인트, 식별자).
• 위반 시 정책: 즉시 거부(429류)·지연(throttle)·점증 백오프·일시 차단·CAPTCHA(로그인). 정상 사용자 경험을 해치지 않게 한도를 정하고, 응답에 남은 한도/재시도 시각을 알려주면 클라가 협조한다.
• 분산의 핵심 문제: 서버가 N대인데 각자 로컬 카운터로 "분당 100" 을 재면, 라운드로빈으로 분산될 때 전체는 최대 N×100 까지 새어나간다(distributed_systems/problem8 초과 판매와 같은 구조). 로컬 근사 + 주기 동기화는 동기화 지연만큼 초과를 허용.
• 중앙 저장소로 정확히: Redis 같은 공유 저장소에서 원자 연산으로 카운트한다. 고정 윈도우는 INCR key + EXPIRE, 토큰 버킷/슬라이딩 윈도우는 Lua 스크립트로 "읽기-판정-갱신"을 한 번에 원자 실행(경합 제거). 장점은 전역 정확성, 비용은 ① 매 요청 네트워크 왕복 지연, ② Redis 가 단일 장애점/병목이 될 수 있음.
• 하이브리드: 흔히 로컬 토큰 버킷으로 1차 흡수(빠른 거부) + 중앙으로 전역 한도 보정. 또는 노드별로 전역 한도를 미리 배분(lease)하고 소진 시 중앙에서 추가 할당받아 왕복을 줄인다 — 정확성과 지연의 트레이드오프.

정리

토큰 버킷(버스트 허용·평균 제한)이 게임 API 리밋의 기본, 누수 버킷은 출력 평활화, 슬라이딩 윈도우 카운터는 경계 폭주를 막는 가벼운 카운팅. 다중 키로 계정/IP/엔드포인트를 함께 제한하고, 여러 서버에선 중앙 원자 연산(Redis+Lua)이나 lease 배분으로 전역 한도를 지키되 지연·단일 장애점을 관리한다.