【ITニュース解説】Token Bucket Algorithm Explained

あらゆるAPIやオンラインシステムには、処理できるリクエストの量に物理的な限界がある。もし、この限界を超えて大量のリクエストが集中すると、サーバーはパンク状態になり、システム全体が停止してしまう可能性がある。これは、たとえ一人のユーザーからの意図しない過剰なリクエストであっても起こりうる問題である。このような事態を防ぎ、システムを安定稼働させるために、「レートリミット（処理速度制限）」という仕組みが導入されている。レートリミットは、一定時間内に許可するリクエストの数を制限することで、サーバーの過負荷を防ぎ、すべてのユーザーに公平なサービス提供を保証する重要な技術である。

レートリミットを実現するためのアルゴリズムはいくつか存在する。例えば、特定の時間枠でのリクエスト数を単純に数える「固定ウィンドウ（Fixed Window）」方式や、時間枠を動的にずらす「スライディングウィンドウ（Sliding Window）」方式、リクエストを一定のペースで処理する「リーキーバケット（Leaky Bucket）」方式などがある。その中でも特に広く使われ、バランスの取れた性能を持つのが「トークンバケット（Token Bucket）」アルゴリズムである。トークンバケットは、通常の安定したトラフィック制御に加え、短時間だけ集中するリクエスト（バーストトラフィック）にも柔軟に対応できるという特徴があり、これが人気の理由となっている。

トークンバケットアルゴリズムは、概念的にはトークン（許可証）が入った仮想的な「バケット（貯蔵庫）」をイメージすると理解しやすい。このバケットには、次のようなルールが適用される。 まず、トークンは一定の決められた速度でバケットに補充され続ける。例えば、毎秒5個のトークンが補充される、といった具合である。次に、システムへのリクエストは、通過するために1つ以上のトークンを「消費」する必要がある。リクエストが来た際、バケット内にトークンが残っていれば、そのリクエストは許可され、トークンが一つ消費される。もしバケットが空でトークンがなければ、そのリクエストは拒否されるか、または後で処理するために待機させられる。 重要な点として、バケットには最大容量が設定されているため、トークンは無限に増え続けることはない。バケットが満タンになると、それ以上のトークンは補充されず破棄される。この仕組みにより、過去にリクエストが少なかった期間にトークンが蓄積されていれば、一時的にリクエストが急増しても、バケット容量の範囲内でそのバーストを許容できる。しかし、トークンは補充レートを超えて増えることはないため、長期的には平均的なリクエストレートが強制されることになる。

このトークンバケットの動作を具体的な数式で見てみよう。 Cをバケットの最大容量、Rをトークンの補充レート（1秒あたりに補充されるトークン数）、Tを前回のトークン補充からの経過時間とする。 ある時点でのバケット内のトークン数は、tokens = min(C, tokens + R * T)という計算で求められる。ここでmin関数は、カッコ内の二つの値のうち小さい方を選ぶことを意味する。つまり、補充されたトークン数がバケット容量を超えないように調整される。 リクエストがシステムに到達した際には、まず現在のトークン数をチェックする。もしtokens > 0であれば、リクエストは許可され、バケット内のトークン数から1が引かれる (tokens -= 1)。そうでない場合は、トークンがないためリクエストは拒否される。

具体的な例で動作を確認すると、より理解が深まるだろう。 例えば、バケットの容量が10トークン、補充レートが1秒あたり1トークンと設定されているとする。

• 時刻0秒の時点で、バケットは満タンの10トークンが入っている。
• この直後にユーザーが5つのリクエストをほぼ同時に送信したとする。各リクエストは1トークンを消費するため、バケットには10 - 5 = 5トークンが残る。
• その後、5秒間リクエストがなかったとする。この5秒間に5秒 * 1トークン/秒 = 5トークンが補充される。現在の5トークンに5トークンが加わり、バケットは再び満タンの10トークンとなる。
• その直後にユーザーが今度は15個のリクエストを送信しようとした場合、バケットには10トークンしかないため、最初の10個のリクエストは許可されるが、残りの5個のリクエストはトークン不足により拒否される。 この例からわかるように、トークンバケットは、一時的なバーストトラフィックをバケットの容量まで許容する一方で、長期的には補充レートによってリクエスト数を制限する役割を果たす。

トークンバケットアルゴリズムには、いくつかの利点と欠点がある。 利点としては、バースト的なリクエストを一時的に許容しながらも、長期的な平均リクエストレートを確実に制限できる点が挙げられる。また、トラフィックの流れをスムーズに整形する効果があるため、ネットワーク通信やAPIの管理に非常に適している。実際に、ネットワーク機器や多くのAPIサービスで広く採用されている実績がある。 一方で欠点としては、固定ウィンドウ方式のような非常にシンプルなアルゴリズムと比較すると、多少実装が複雑になる点が挙げられる。また、複数のサーバーで構成される分散システムでレートリミットを実装する場合、トークンバケットの状態（バケット内のトークン数や最終補充時刻など）を正確に同期させるための仕組みが必要となり、その設計には注意が求められる。

このアルゴリズムは、プログラムとして具体的に実装できる。JavaScriptの例では、TokenBucketというクラスを作成し、その中にバケットの最大容量、現在のトークン数、補充レート、そして最後にトークンが補充された時刻を管理する。 refill()メソッドでは、現在時刻と最終補充時刻との差から経過時間を計算し、その経過時間に応じて補充レート分のトークンを計算してバケットに追加する。このとき、トークン数が最大容量を超えないように調整する。そして、allowRequest()メソッドが呼び出された際には、まずrefill()を呼び出してトークンを最新の状態に更新し、トークンが残っていればリクエストを許可してトークンを1つ消費する。トークンがなければリクエストを拒否する。このように、コードでトークンの補充と消費のロジックを実装することで、トークンバケットの動作を実現できる。

トークンバケットアルゴリズムは、さまざまな現実世界のシステムで活用されている。 代表的な例としては、APIゲートウェイが挙げられる。Amazon Web Services (AWS) のAPI Gatewayや、Nginx、Envoyといったプロダクトは、このアルゴリズムの派生形を利用して、API利用者が過剰なリクエストを送らないように制御している。また、ネットワークルーターでも、特定の種類のトラフィックが帯域幅を独占しないように、トラフィック整形のためにトークンバケットが利用されることがある。さらに、メッセージキューシステムにおいても、メッセージを処理するコンシューマ（消費者）がメッセージの量で過負荷にならないよう、受信レートを制限するために使われる場合がある。

他のレートリミット方法と比較すると、トークンバケットの特長が際立つ。 固定ウィンドウカウンターは実装が非常にシンプルだが、期間の切れ目でリクエストが集中すると、短期間に規定値を超えるリクエストを許してしまう可能性があるという弱点がある。リーキーバケットは、リクエストを一定の安定したレートで処理するため、非常にスムーズなトラフィックフローを実現するが、一時的なバーストトラフィックに対しては柔軟性がなく、すべてキューに入れて処理するか、オーバーフロー分を破棄することになる。 これに対してトークンバケットは、安定したレート制限と、短期間のバーストトラフィックへの柔軟な対応という、両者の利点をバランス良く兼ね備えているため、特にAPIのレートリミットには最も適した選択肢の一つとされている。

結論として、トークンバケットアルゴリズムは、レートリミットを実装するための非常に実用的かつ効果的な方法である。その仕組みは比較的シンプルでコードに落とし込みやすく、一時的なリクエストの集中（バースト）を許容しながらも、長期的にはリクエストの平均レートを適切に制御し、システム資源の公平な利用を保証する。APIを構築する場合や、多数のコンポーネントが連携する分散システムを設計する際には、トークンバケットアルゴリズムをレートリミットの主要な選択肢として検討することが推奨される。