トークンバケットアルゴリズムの理解

トークンバケットアルゴリズムの仕組み

トークンバケットは最も広く使用されているレート制限アルゴリズムの1つです。AWS API Gateway、Shopify、多くのクラウドプロバイダーで使用されています。

核心概念

1. バケット：最大容量（バケットサイズ）を持つトークンのコンテナ
2. トークン：各リクエストはバケットから1つのトークンを消費
3. リフィルレート：一定のレートでトークンがバケットに追加される
4. オーバーフロー：バケットが満杯の場合、新しいトークンは破棄される

ステップバイステップの例

サイズ = 10、リフィルレート = 2トークン/秒のバケットを考えます：

時間 (秒)	イベント	変更前トークン	変更後トークン
0.0	開始（満杯）	10	10
0.0	5リクエスト到着	10	5
0.5	1トークン補充	5	6
1.0	1トークン補充	6	7
1.0	8リクエスト到着	7	0（1つ拒否）
1.5	1トークン補充	0	1
2.0	1トークン補充	1	2

主要特性

• バースト容量はバケットサイズに等しい（即座に10リクエスト）
• 持続レートはリフィルレートに等しい（2リクエスト/秒）
• 枯渇回復：空のバケットが完全に回復するまで バケットサイズ / リフィルレート 秒（10/2 = 5秒）

他のアルゴリズムとの比較

アルゴリズム	バースト処理	メモリ	複雑さ
トークンバケット	バケットサイズまでのバーストを許可	O(1)	低
リーキーバケット	すべてのトラフィックを平滑化	O(1)	低
固定ウィンドウ	境界で2倍のバーストを許可	O(1)	低
スライディングウィンドウログ	バーストなし	O(n)	高