A Comparative Survey of API Rate-Limiting Algorithms: Token Bucket, Leaky Bucket, and Sliding Window
本論文は、広く用いられている5つのAPIレート制限アルゴリズム（トークンバケット、リーキーバケット、固定ウィンドウ、スライディングウィンドウログ、およびスライディングウィンドウカウンタ）を概観し、実験的に比較することで、バースト許容性と精度のトレードオフを評価し、最終的に、特定のトラフィック特性やシステム制約に基づいた最適なアルゴリズムを選択するための指針を提供するものである。
原論文は CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) でライセンスされています。 これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。 免責事項の全文を読む
現代のデジタルサービスは、可用性と保護の間の繊細なバランスに依存しています。何百万人もの人々が一度にウェブサイトやアプリケーションにアクセスしようとすると、舞台裏にあるサーバーは、まるで突然の交通量の急増によって渋滞した一本道の橋のように、圧倒されてしまうことがあります。この崩壊を防ぐために、エンジニアは「ゲートキーパー（門番）」として機能する「レートリミッティング（流量制限）」と呼ばれる仕組みを使用します。このゲートキーパーは、特定のユーザーやデバイスが一定期間内に送信したリクエストの数をカウントし、安全な閾値を超えるものはブロックします。その目的はユーザーを罰することではなく、一部のヘビーユーザーが利用可能なすべてのリソースを消費してしまうのを防ぎ、システムが全員にとって安定した状態を維持できるようにすることです。しかし、すべてのトラフィックが一定の流れで到着するわけではありません。時には、人気のニュースが飛び込んできたときや、システムの接続失敗による再試行が行われるときのように、突然の鋭いバースト（突発的な負荷）が発生することがあります。エンジニアにとっての課題は、これらのバーストをどのように扱うかを決定することです。システムに一時的なスパイク（急増）を通過させるべきか、それとも状況に関わらず厳格に一定の制限を適用すべきでしょうか。
ウメア・セリムによる最近の研究では、これらのデジタルゲートキーパーを構築するために使用されるさまざまな数学的ルールについて調査しています。この研究は、業界で一般的に使用されている5つの特定の手法、すなわちトークンバケット、リーキーバケット、固定ウィンドウカウンター、スライディングウィンドウログ、およびスライディングウィンドウカウンターに焦点を当てています。これらの手法はそれぞれ、時間の追跡方法とリクエストのカウント方法が異なり、トラフィックの急増が発生した際の挙動も異なります。どの手法が最適であるかを理解するために、著者は理論だけに頼るのではなく、これらすべてを同一の条件下でテストするためのコンピュータシミュレーションを構築しました。シミュレーションは、100秒間に1,000件以上のリクエストが発生するという現実的なストリームを作成しました。このストリームには、毎秒8リクエストの安定したバックグラウンドフローに加え、2つの明確な活動のバーストが含まれていました。一つはトラフィックが毎秒40リクエストに跳ね上がる5秒間の期間であり、もう一つはより鋭い、毎秒60リクエストに達する2秒間のスパイクです。この全く同じトラフィックパターンを5つのアルゴリズムすべてに通すことで、本研究は各手法がどれだけのリクエストを受け入れ、どれだけを拒否したか、そしてスパイク発生時にシステムがどのように振る舞ったかを正確に測定することができました。
結果は、これらのアルゴリズムがトラフィックの急増による圧力を処理する方法において、明確な分かれ目があることを明らかにしました。トークンバケットとリーキーバケットは、単にリクエストの受け入れまたは拒否を決定するために使用された場合、ほぼ同一の挙動を示しました。両方の手法は、他の手法よりも効果的にバーストを吸収し、送信された1,057件のリクエストのうち計844件を受け入れ、これは約80パーセントの受け入れ率に相当します。最初の大きなバーストの間、これら2つの手法は69件のリクエストを通過させ、2番目のより鋭いバストの間には38件を通過させました。これは、これらのアルゴリズムが将来の使用に備えて「予備の」許可を蓄積する組み込みの容量を備えており、ユーザーを即座に追い出すことなくスパイクを平滑化できるように設計されているためです。対照的に、スライディングウィンドウログはすべての手法の中で最も硬直的でした。それは設定された制限を厳格に遵守し、単一の秒間に10件を超えるリクエストを一切通過させませんでした。これは過負荷に対する最も精密な保護を提供しましたが、高い代償を伴いました。つまり、最も多くのトラフィックを拒否し、リクエストのわずか67.9パーセントしか受け入れませんでした。これは、システムが制限を超えるスパイクを見ることが決してないことを保証する唯一の手法でしたが、そのために他の手法よりも頻繁に正当なユーザーを拒否していました。
残りの3つの手法はその中間的な位置にあり、時間の測定方法に基づいた予測可能な欠陥を示しました。新しい秒の開始時にカウントをリセットする固定ウィンドウカウンターは、境界におけるタイミングエラーに悩まされました。カウンターがバーストのトラフィックが到着した瞬間にリセットされる可能性があるため、意図された制限よりも高い、1秒間に最大15件のリクエストを許容してしまいました。スライディングウィンドウカウンターは、前の秒も考慮することでこの問題を修正しようと試みましたが、部分的な修正にとどまり、ピーク時には13件に達しました。研究の結果、アルゴリズムの選択はシステムが何を保護する必要があるかに完全に依存することがわかりました。ページのリロードに伴う複数のデータコールのように、自然なバースト活動を許容してユーザーの満足度を高めることが目標であれば、高い受け入れ率と安定したパフォーマンスのバランスが取れたトークンバケットが優れた選択肢となります。もし、スパイクを一切許容できない脆弱なダウンストリームシステムを保護することが目標であれば、受け入れ率は低くなるものの、スライディングウィンドウログがより良い選択肢となります。研究の結論として、あらゆる仕事に適した単一の完璧なツールは存在せず、代わりにエンジニアは、トラフィックのスパイクに対する許容度と利用可能なメモリリソースに合致する方法を選択しなければならないということです。
自分の分野の論文に埋もれていませんか？
研究キーワードに一致する最新の論文のダイジェストを毎日受け取りましょう——技術要約付き、あなたの言語で。