はじめに
API Gateway のリクエスト数制限で使われているという『トークンバケットアルゴリズム』についてなんとなくでしか理解していなかったので、少し時間を使って学ぶ事にした。これは、その際のメモを整理したもの。
改めて学んでみて、概要は理解できていたが『non-conformant 状態』について認識が曖昧だった事に気がつけた。
参考
- トークンバケット - Wikipedia
- トラフィックシェーピング - Wikipedia
- リーキーバケット - Wikipedia
- API リクエストを調整してスループットを向上させる - Amazon API Gateway
トークンバケットアルゴリズム
日本語 Wikipedia では以下の様に定義されている。
トークンバケット（英: token bucket）とは、ネットワークへのデータ流入量を制御するアルゴリズムの一種であり、バースト性のあるデータ送信を許容する。いくつかの用途があるがトラフィックシェーピングの手法として使うことが多い。
トークンバケット - Wikipediaトラフィックシェーピング（英: Traffic shaping）とは、コンピュータネットワークのトラフィック（通信量）を制御し、パケットを遅延させることで通信性能を最適化/保証し、レイテンシを低減し、帯域幅を確保することである[1]。パケットシェーピングともいう。
トラフィックシェーピング - Wikipedia
トラフィック(≒ API リクエスト数)を制御するために利用できるアルゴリズムで、バースト(瞬間的なトラフィック増大)を許容しつつ、トラフィックの平均的な流量を一定以下に保つことができるものである、と理解した。
トークンとバケット
一度に転送可能なトラフィックの最大を『バケット(バケット)』で表現し、トラフィックの転送を許可するための手形を『トークン』で表現する。
ひとつのトークンは一定サイズのトラフィックに対応し、トラフィックを転送する際にトラフィックに応じた数のトークンが消費(削除)される。
non-conformant 状態
トラフィックに応じた数のトークンがバケットに無い場合、そのトラフィックは non-conformant 状態となる。
non-conformant 状態となったトラフィックの扱い方は実装によって異なる模様。
- 捨てる
- 充分なトークンが追加されるまで遅延させる
- non-conformant 状態である事をマーキングした上で、かまわず転送してしまう
転送レート
一定時間に決まった数のトークンがバケットに追加され続ける。バケットには容量(バケットサイズ)があるため、これを超えてトークンを追加する事は出来ない。
このトークンを追加するペースが転送レート(≒ スロットリングレート)につながる。
バースト
その時点でバケットに存在するトークンの数だけのトラフィックを転送できるのが、トークンバケットアルゴリズムである。つまり、最大でバケットサイズに応じたトラフィックを一度に転送させる事が許容されている。
要するに、バケットサイズに応じたバーストを許容できるということ。
API Gateway の例を読み解く
教材: API リクエストを調整してスループットを向上させる - Amazon API Gateway
デフォルトでは、API Gateway はリクエストの定常レートを 10,000 リクエスト/秒 (rps) に制限します。また、バースト (最大バケットサイズ) を AWS アカウント内のすべての API にわたって 5,000 リクエストに制限します。
上記の前提のもと、教材の例をみていく。
発信者が、1 秒間に等しく 10,000 リクエストを送信した場合 (たとえば、ミリ秒毎に 10 リクエスト)、API Gateway は 1 つも削除することなくすべてのリクエストを処理します。
バケットに 10,000 個のトークンがあると仮定すると、バーストせず 10 req/ms のペースでリクエストが 1 秒間続けば開始時点のトークンで全てのリクエストをまかなうことが出来る。
バーストによってバケットが空になった直後だと仮定する。直後とは言え 1ms 後に新しいリクエストが開始されたとすれば 10 個のトークンがあると期待できるので、それ以降も 10 req/ms であれば問題なく処理しきれると期待できる。
non-conformant 状態が発生しないと考えられるので、このケースは理解しやすい。
発信者が、最初の 1 ミリ秒間で 10,000 リクエストを送信した場合、API Gateway はそのうち 5,000 に対応し、残りは 1 秒間中に調整します。
If the caller sends 10,000 requests in the first millisecond, API Gateway serves 5,000 of those requests and throttles the rest in the one-second period.
当初、『調整』という日本語が何を意味するのかがよく分からなかったが、トークンバケットアルゴリズムの『non-conformant 状態』となったトラフィックを API Gateway の流儀で処理する事を意味しているのだと解釈した。
バケットサイズ 5,000 は問題なく処理できるが、残りは non-conformant 状態となる。一律で転送されないのか、一定のアルゴリズムによって可能な限り転送するのか。
レート 10 / バースト 1 で設定して並行 10 リクエストを送信してみた結果、全て受け入れられる事もあれば、数不定で 429 応答を返すパターンも見られた。
単純に non-conformant 状態のリクエストを破棄するわけではなく、何かしらの仕組みによって可能な限り受け入れてくれるのだと認識。
発信者が 5,000 リクエストを最初の 1 ミリ秒に送信し、さらに 5,000 リクエストを残りの 999 ミリ秒に等しく広げた場合 (たとえば、ミリ秒毎 5 リクエスト)、API Gateway は 429 Too Many Requests エラー応答を返すことなく全 10,000 リクエストを 1 秒間中に処理します。
バケットにあるトークンの数を上回ることないペースでリクエストする(non-conformant 状態を発生させない)という事。
発信者が 5,000 リクエストを最初の 1 ミリ秒に送信し、次の 5,000 リクエスト を送信するのに 101 ミリ秒目まで待った場合、API Gateway は 6,000 リクエストを処理し、残りを 1 秒間中に調整します。これは、10,000 rps のレートで、API Gateway は最初の 100 ミリ秒後に 1,000 リクエストに対応し、よって同じ量でバケットを空にしたためです。次の 5,000 リクエストのスパイクのうち、1,000 はバケットを埋め、処理待ちとしてキューされます。残りの 4,000 は最大バケット容量を超え、破棄されます。
If the caller submits 5,000 requests in the first millisecond and waits until the 101st millisecond to submit another 5,000 requests, API Gateway processes 6,000 requests and throttles the rest in the one-second period. This is because at the rate of 10,000 rps, API Gateway has served 1,000 requests after the first 100 milliseconds and thus emptied the bucket by the same amount. Of the next spike of 5,000 requests, 1,000 fill the bucket and are queued to be processed. The other 4,000 exceed the bucket capacity and are discarded.
最初のリクエストから 100ms 後にトークンが 1,000 個あると読み、5,000 のうち 1,000 リクエストを受け入れられると解釈。残り 4,000 は non-conformant 状態となるはずだが、今度は『破棄』と明確に書かれている。原文でも discarded という表現になっている。
先のバケットサイズを超えて同時にリクエストされた例では『調整』という表現である事との違いが理解できない。
発信者が 5,000 リクエストを最初の 1 ミリ秒に送信し、101 秒目で 1,000 リクエストを送信して、さらに 4,000 リクエストを残りの 899 ミリ秒に等しく広げると、API Gateway は調整することなく全 10,000 リクエストを 1 秒間中に処理します。
これも、バケットにあるトークンの数を上回ることないペースでリクエストする(non-conformant 状態を発生させない)という事。
まとめ
トークンバケットアルゴリズムを学んだ。
API Gateway が non-conformant 状態をどう処理しているのか、教材としたドキュメントに書かれていた例から読み解くことは出来なかった。