レートリミッター ── アルゴリズムと分散実装
扱うCS概念：トークンバケット、スライディングウィンドウ、固定ウィンドウ、分散カウンター、Redis Lua スクリプト
この章で何ができるようになるか：4つのレートリミットアルゴリズムの動作と特性を説明できるようになる。単一サーバーから分散環境への拡張でどんな問題が起きるかと、その解決策を設計できるようになる。
問題設定
レートリミッターは「1ユーザーが1分間に最大100リクエスト」のようなルールを強制する仕組みだ。
なぜ必要か：
DoS/DDoS 対策：
悪意のあるクライアントが大量リクエストを投げてサービスを落とす
コスト管理：
API の過度な利用（スクレイピング、バースト呼び出し）を制限する
SLA の均等化：
一部のユーザーが帯域を使いすぎて他のユーザーに影響しないようにする
外部 API 呼び出し制御：
Stripe や SendGrid などのサードパーティ API のレート制限に準拠するアルゴリズム1：固定ウィンドウカウンター（Fixed Window Counter）
最もシンプル。時間を固定の窓（例：1分）で区切り、各窓のカウントを記録する。
class FixedWindowRateLimiter:
def __init__(self, redis_client, limit: int, window_seconds: int):
self.redis = redis_client
self.limit = limit
self.window = window_seconds
def is_allowed(self, user_id: str) -> bool:
now = int(time.time())
window_key = now // self.window # 同じ窓内は同じキー
key = f"rate:{user_id}:{window_key}"
count = self.redis.incr(key)
if count == 1:
self.redis.expire(key, self.window * 2) # 窓終了後に自動削除
return count <= self.limit問題：境界付近での爆発（Boundary Burst）
制限：1分間に100リクエスト
00:59:50 に 100リクエスト → OK（0分の窓の上限）
01:00:10 に 100リクエスト → OK（1分の窓の上限）
→ 20秒間に200リクエストが通る！graph LR
subgraph 0分の窓
A[00:59:50〜01:00:00<br/>100リクエスト]
end
subgraph 1分の窓
B[01:00:00〜01:00:10<br/>100リクエスト]
end
A --> C[20秒間に200リクエスト！]
B --> Cアルゴリズム2：スライディングウィンドウログ（Sliding Window Log）
各リクエストのタイムスタンプを記録し、「過去N秒間」のリクエスト数を正確に数える。
class SlidingWindowLogLimiter:
def __init__(self, redis_client, limit: int, window_seconds: int):
self.redis = redis_client
self.limit = limit
self.window = window_seconds
def is_allowed(self, user_id: str) -> bool:
now = time.time()
key = f"rate_log:{user_id}"
window_start = now - self.window
# Lua スクリプトでアトミックに実行（競合を防ぐ）
lua_script = """
local key = KEYS[1]
local now = tonumber(ARGV[1])
local window_start = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])
local window = tonumber(ARGV[4])
-- 窓より古いエントリを削除
redis.call('ZREMRANGEBYSCORE', key, '-inf', window_start)
-- 現在のカウント
local count = redis.call('ZCARD', key)
if count < limit then
-- リクエストを記録（score=タイムスタンプ, member=ユニークID）
redis.call('ZADD', key, now, now .. '-' .. math.random())
redis.call('EXPIRE', key, window * 2)
return 1 -- 許可
else
return 0 -- 拒否
end
"""
result = self.redis.eval(lua_script, 1, key, now, window_start,
self.limit, self.window)
return result == 1✅ 長所：境界バーストが起きない。正確な「過去N秒間」を見る。
❌ 短所：各リクエストのタイムスタンプをメモリに保持する → ユーザー数が多いとメモリを大量消費。
アルゴリズム3：スライディングウィンドウカウンター（Sliding Window Counter）
固定ウィンドウとスライディングログのハイブリッド。精度よりメモリ効率を優先。
class SlidingWindowCounterLimiter:
"""
現在の窓のカウント + 前の窓のカウント × (重複している割合)
で近似的なスライディングウィンドウを実現
"""
def is_allowed(self, user_id: str, limit: int, window_seconds: int) -> bool:
now = time.time()
current_window = int(now // window_seconds)
prev_window = current_window - 1
current_key = f"rate:{user_id}:{current_window}"
prev_key = f"rate:{user_id}:{prev_window}"
# 前の窓がどれだけ現在のスライディング窓に重なるか
elapsed_in_current = now % window_seconds
prev_weight = 1.0 - (elapsed_in_current / window_seconds)
current_count = int(self.redis.get(current_key) or 0)
prev_count = int(self.redis.get(prev_key) or 0)
# 近似カウント
estimated_count = current_count + prev_count * prev_weight
if estimated_count < limit:
self.redis.incr(current_key)
self.redis.expire(current_key, window_seconds * 2)
return True
return False✅ 長所：メモリ効率が良い（2つのカウンターのみ）。ほぼ正確（Cloudflare の実測では、4億リクエスト中で誤判定されたのは全体の約0.003%）。
アルゴリズム4：トークンバケット（Token Bucket）
バーストを許容しつつ、平均レートを制限する。Stripe や AWS API Gateway が採用している実世界標準。
バケットに容量 C のトークンが入る。
一定レート R でトークンが補充される。
リクエストごとに1トークン消費する。
トークンがなければリクエストを拒否。class TokenBucketLimiter:
def is_allowed(self, user_id: str, capacity: int, refill_rate: float) -> bool:
"""
capacity: バケットの最大容量（バーストの上限）
refill_rate: 1秒あたりのトークン補充数
"""
now = time.time()
key = f"token_bucket:{user_id}"
lua_script = """
local key = KEYS[1]
local now = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local refill_rate = tonumber(ARGV[3])
-- 現在の状態を取得
local data = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(data[1]) or capacity
local last_refill = tonumber(data[2]) or now
-- 経過時間分だけトークンを補充
local elapsed = now - last_refill
tokens = math.min(capacity, tokens + elapsed * refill_rate)
if tokens >= 1 then
-- トークンを消費して許可
redis.call('HMSET', key, 'tokens', tokens - 1, 'last_refill', now)
redis.call('EXPIRE', key, 3600)
return 1
else
-- トークン不足：拒否
redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
return 0
end
"""
result = self.redis.eval(lua_script, 1, key, now, capacity, refill_rate)
return result == 1使用例：
# 1分間に100リクエスト（バースト最大20）
# → refill_rate = 100/60 ≈ 1.67 トークン/秒
# → capacity = 20（バーストで最大20リクエストを瞬時に処理できる）
limiter.is_allowed(user_id, capacity=20, refill_rate=1.67)4アルゴリズムの比較
| アルゴリズム | メモリ使用 | 精度 | バースト対応 | 実装複雑度 |
|---|---|---|---|---|
| 固定ウィンドウ | 低 | △ 境界バーストあり | 不可 | 低 |
| スライディングログ | 高 | ◎ 完全正確 | 不可 | 中 |
| スライディングカウンター | 低 | ○ ほぼ正確 | 不可 | 中 |
| トークンバケット | 低 | ◎ 正確 | ✅ 対応 | 中〜高 |
| リーキーバケット | 低 | ◎ 均一 | ❌ 平滑化 | 中 |
分散環境での問題と解決策
単一サーバーでは上記の実装で十分だが、複数サーバーにまたがるとカウンターが分断される。
3台のAPIサーバーがある場合：
リクエストAが Server1 に → Server1 のカウンター: 1
リクエストBが Server2 に → Server2 のカウンター: 1
リクエストCが Server3 に → Server3 のカウンター: 1
合計3リクエスト。しかし各サーバーは「自分が1件処理した」としか知らない
→ 制限値を超えても気づかない解決策：集中カウンター（Centralized Counter）
graph LR
Client --> LB[ロードバランサー]
LB --> API1[APIサーバー1]
LB --> API2[APIサーバー2]
LB --> API3[APIサーバー3]
API1 --> Redis[(Redis<br/>集中カウンター)]
API2 --> Redis
API3 --> Redis全サーバーが同じ Redis を参照する。Lua スクリプトでアトミック操作を保証する（INCR + 判定の間に別リクエストが割り込まない）。
問題：Redis がボトルネックになる
対策：Redis Cluster でシャーディング（ユーザーIDで Partition を分割）。または Redis への呼び出しをローカルキャッシュで吸収する（1秒ごとにまとめて同期するなど）。
Nginx / API Gateway でのレートリミット
実務ではアプリケーション層でなく、**インフラ層（Nginx, Kong, AWS API Gateway）**でレートリミットを実装することが多い。
# nginx.conf
http {
limit_req_zone $binary_remote_addr zone=api:10m rate=100r/m;
# $binary_remote_addr = IPアドレスをキー
# zone=api:10m = "api"という名前の10MBの共有メモリ
# rate=100r/m = 1分間に100リクエスト
server {
location /api/ {
limit_req zone=api burst=20 nodelay;
# burst=20: 上限を超えた分を最大20件バッファ（トークンバケット相当）
# nodelay: バッファしたリクエストを遅延せず即処理
proxy_pass http://backend;
}
}
}Nginx はリーキーバケットアルゴリズムを使用している。burst パラメーターがバケット容量に相当する。
実際のシステムでの設定例
Stripe API：
- ライブモード: 100 read + 100 write requests/second（トークンバケット）
- テストモード（sandbox）: ライブモードの約 1/4（25 read + 25 write requests/second）
- レート超過時: HTTP 429 + Retry-After ヘッダーGitHub API：
- 認証済み: 5000 requests/hour（固定ウィンドウ）
- 未認証: 60 requests/hour
- GraphQL: 5000 points/hour（操作の複雑さに応じたコスト計算）
- X-RateLimit-Remaining ヘッダーで残り回数を通知まとめ
| 判断ポイント | 推奨選択 |
|---|---|
| バーストを許容したい | トークンバケット |
| 完全に均一なレートが必要 | リーキーバケット |
| シンプルに実装したい | 固定ウィンドウ |
| 境界バーストを避けたい・メモリ効率も重視 | スライディングウィンドウカウンター |
| 分散環境での正確な制御 | Redis + Lua スクリプト（集中カウンター） |
| インフラ層で完結させたい | Nginx / Kong / API Gateway |
次章では、全文検索エンジンがどうやって「数十億文書から関連文書を100ms以内に返す」のかを見ていく。