レート制限アルゴリズムをまとめてみた
はじめに
レート制限（Rate Limiting）は、APIやWebサービスにおいて、一定時間内のリクエスト数を制限する重要な技術です。システムの安定性を保ち、悪意のある攻撃や過度な負荷から守るために不可欠な機能となっています。
本記事では、代表的な5つのレート制限アルゴリズムについて、それぞれの仕組み、特徴、メリット・デメリットを解説します。
各アルゴリズムの概要比較
| アルゴリズム | 実装難易度 | メモリ使用量 | 精度 | バースト対応 |
|---|---|---|---|---|
| 固定ウィンドウカウンタ | 低 | 低 | 低 | △ |
| スライディングウィンドウログ | 中 | 高 | 高 | ○ |
| スライディングウィンドウカウンタ | 中 | 低 | 中 | ○ |
| トークンバケット | 中 | 低 | 高 | ◎ |
| リーキーバケット | 中 | 中 | 高 | × |
1. トークンバケット（Token Bucket）
原理
トークンバケットアルゴリズムは、一定の容量を持つバケツに、一定のレートでトークンが追加されるイメージです。リクエストが来るたびに、バケツからトークンを1つ消費します。トークンがない場合、リクエストは拒否されます。
https://www.geeksforgeeks.org/system-design/rate-limiting-in-system-design/
動作の流れ
- バケツに最大容量（capacity）まで保持できる
- 一定の時間間隔でトークンが補充される（refill rate）
- リクエスト時にトークンが1つ以上あれば許可し、トークンを消費
- トークンがない場合はリクエストを拒否
メリット
- バーストトラフィックに柔軟に対応できる
- 平均レートを維持しながら、短期間の急増を許容
- 実装がシンプルで効率的
デメリット
- バケツの容量設定が難しい場合がある
- 長期間リクエストがないと、次のバーストで大量のリクエストが許可される可能性
適用シーン
- API Rate Limiting（多くのクラウドサービスで採用）
- ネットワーク帯域制御
- 一時的なトラフィックスパイクを許容したい場合
2. リーキーバケット（Leaky Bucket）
原理
リーキーバケットは、底に穴の開いたバケツをイメージします。リクエストは上から水として注がれ、バケツから一定のレートで漏れ出します（処理されます）。バケツが満杯になると、新しいリクエストは溢れて拒否されます。
https://www.geeksforgeeks.org/system-design/rate-limiting-in-system-design/
動作の流れ
- リクエストがキューに追加される
- 一定のレート（leak rate）でキューからリクエストが処理される
- キューが満杯の場合、新しいリクエストは拒否される
- 処理レートは常に一定
メリット
- 出力レートが完全に一定に保たれる
- ネットワークの輻輳制御に適している
- リクエストのキューイングにより、スムーズな処理が可能
デメリット
- バーストトラフィックに対して柔軟性がない
- キューが満杯になると、即座に拒否される
- メモリ使用量がキューサイズに依存
適用シーン
- ネットワークトラフィックの平滑化
- 下流システムへの負荷を一定に保ちたい場合
- リアルタイムストリーミング処理
3. 固定ウィンドウカウンタ（Fixed Window Counter）
原理
固定された時間ウィンドウ（例：1分間）内のリクエスト数をカウントし、制限値を超えたら拒否するシンプルな方式です。
https://www.geeksforgeeks.org/system-design/rate-limiting-in-system-design/
動作の流れ
- タイムウィンドウ（例：0秒〜60秒）を設定
- ウィンドウ内のリクエスト数をカウント
- 制限値を超えたら拒否
- ウィンドウが終了したらカウンタをリセット
メリット
- 実装が非常にシンプル
- メモリ使用量が少ない
- 理解しやすく、デバッグが容易
デメリット
-
境界問題：ウィンドウ境界付近で2倍のリクエストを許可してしまう可能性
- 例：1分100リクエスト制限の場合、0:59に100件、1:00に100件で、1秒間に200件処理される
- 精度が低い
適用シーン
- 簡易的なレート制限
- 厳密な制御が不要な内部API
- プロトタイピング段階
4. スライディングウィンドウログ（Sliding Window Log）
原理
各リクエストのタイムスタンプをログとして記録し、現在時刻から過去のウィンドウ期間内のリクエスト数をカウントします。固定ウィンドウの境界問題を解決する精度の高い方式です。
https://www.geeksforgeeks.org/system-design/rate-limiting-in-system-design/
動作の流れ
- 各リクエストのタイムスタンプを記録
- 新しいリクエスト時に、古いタイムスタンプ（ウィンドウ外）を削除
- ウィンドウ内のリクエスト数が制限値以下なら許可
メリット
- 非常に高い精度
- 境界問題が発生しない
- 正確なレート制限が可能
デメリット
- メモリ使用量が多い（全リクエストのタイムスタンプを保存）
- リクエスト数が多いとパフォーマンスに影響
- ログのクリーンアップ処理が必要
適用シーン
- 厳密なレート制限が必要な課金API
- セキュリティが重要なエンドポイント
- リクエスト数が比較的少ないAPI
5. スライディングウィンドウカウンタ（Sliding Window Counter）
原理
固定ウィンドウとスライディングウィンドウの折衷案です。前のウィンドウと現在のウィンドウのカウンタを使用し、重み付け平均で現在のレートを推定します。
https://trycatch22.net/counter-sliding-window/
動作の流れ
- 現在のウィンドウと前のウィンドウのカウンタを保持
- 現在時刻のウィンドウ内での位置を計算
- 重み付け計算で推定リクエスト数を算出
- 推定値が制限以下なら許可
メリット
- メモリ効率が良い（2つのカウンタのみ）
- 固定ウィンドウより精度が高い
- 境界問題を軽減
デメリット
- 推定値のため完全に正確ではない
- トラフィックパターンによっては誤差が生じる
- 実装がやや複雑
適用シーン
- バランスの取れた実装が必要な場合
- Redis等のストレージで効率的に実装したい場合
- 大規模なAPIゲートウェイ
まとめ
レート制限アルゴリズムは、それぞれ異なる特性とトレードオフを持っています。システムの要件に応じて適切なアルゴリズムを選択することが重要です。
- トークンバケット：柔軟性とバースト対応のバランスが良い、最も広く採用されている
- リーキーバケット：出力レートの一定性が求められる場合に最適
- 固定ウィンドウカウンタ：シンプルだが境界問題に注意
- スライディングウィンドウログ：高精度だがメモリ使用量が多い
- スライディングウィンドウカウンタ：精度とメモリ効率の良いバランス
実際のプロダクション環境では、これらのアルゴリズムを組み合わせたり、分散環境に対応したRedisベースの実装を使用することも一般的です。システムの特性を理解し、適切なアルゴリズムを選択しましょう。
Discussion