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

게임 서버에서 로그인 시도, 채팅 전송, 우편/거래 API, 매치메이킹 요청 등에 요청 속도 제한(rate limiting) 을 걸어야 한다. 다음을 설명하라.

1. 왜 필요한가 — 레이트 리미팅이 막아주는 것들(스팸/도배, 무차별 대입 로그인, API 남용, 백엔드 과부하·연쇄 장애)을 게임 맥락에서 들고, "초당 N회" 같은 단순 제한이 버스트(순간 폭주) 를 어떻게 다뤄야 하는지 문제 제기하라.

2. 토큰 버킷(token bucket) — 버킷에 일정 속도로 토큰을 채우고 요청마다 토큰을 소비하는 구조를 설명하라. 버킷 용량(burst) 과 리필 속도(rate) 가 각각 무엇을 통제하는지, 왜 짧은 버스트는 허용하면서 평균 속도는 제한할 수 있는지.

3. 누수 버킷(leaky bucket) — 요청을 큐에 넣고 일정 속도로 "새어나가게" 처리하는 구조를 설명하라. 토큰 버킷과의 차이(출력 평활화 vs 버스트 허용), 큐가 차면 어떻게 되는지(드롭/셰이핑).

4. 고정 윈도우 vs 슬라이딩 윈도우 — 고정 윈도우 카운터(분 단위 카운트 리셋)의 경계 폭주 문제를 설명하고, 슬라이딩 윈도우 로그(정확하나 메모리 큼)와 슬라이딩 윈도우 카운터(근사, 가벼움)가 그 문제를 어떻게 완화하는지 비교하라.

5. 게임 적용과 분산 환경 — 무엇을 키로 제한할지(계정/IP/디바이스/엔드포인트별), 위반 시 정책(거부·지연·일시 차단·CAPTCHA). 그리고 서버가 여러 대일 때 각 노드의 로컬 카운터로는 전체 한도를 못 지키는 이유(distributed_systems/problem8)와, 중앙 저장소(예: Redis)의 원자 연산/Lua 스크립트로 분산 레이트 리밋을 구현하는 방법, 그 비용(지연·단일 장애점)을 논하라.