さまざまなレート制限アルゴリズムをアニメーションでわかりやすく視覚化するとこんな感じ

スパム防止などのためのレート制限を行うアルゴリズムは多数存在しています。さまざまなアルゴリズムの特徴をアニメーションでわかりやすくまとめたブログ記事をChatGPT関連のサービスsmudge.aiが開発ブログにて公開しました。
rate limiter – smudge.ai blog
https://smudge.ai/blog/ratelimit-algorithms
配信のチャット欄にスパムが出現するという状況において、レート制限がない場合にはスパマーは短時間のうちに多数の投稿を行ってチャット欄を一人で埋め尽くしてしまいます。

左上の「Enable rate limiting」にチェックを入れるとレート制限を加えた場合の挙動が確認できます。レート制限が加わったことで、スパマーの投稿のほとんどをブロックしてチャット欄に与える影響を下げることができました。このとき、状況に応じて適切なアルゴリズムを選択することで一般ユーザーのチャットに与える影響を下げつつ効果的にスパムをブロックできるようになるわけです。

レート制限アルゴリズムとして一般的に使用されているのは「Fixed windows(固定ウィンドウ)方式」で、このアルゴリズムでは一定の期間内にアクセスできる回数を制限します。ブログのアニメーションではタイムラインが流れており、手動で「Hit」をクリックするとアクセスをシミュレートできます。例は「1日ごとに6件」という制限になっており、日付変更直後に6回アクセスに成功した後その日の間はアクセスできなくなっています。

固定窓方式は単純で実装しやすく、ユーザー側も理解しやすいなどの長所がありますが、期間の区切り付近では想定よりも多くのアクセスが集中してしまう場合があります。

期間の区切り付近での連続アクセスをふせぐには、期間をユーザーの最初のアクセス時点からスタートすればOK。この方法を使用する場合、レート制限が回復するのがいつなのかをユーザーに示すことが重要とのこと。

固定ウィンドウ以外でよく使用される方式の一つが「Sliding windows(スライドウィンドウ)方式」です。スライドウィンドウ方式ではアクセスが発生するごとにレート制限の期間が発生し、一定時間後にレート制限が1ずつ回復していくという特徴があります。スライドウィンドウ方式はトラフィックをスムーズに分散するため、高負荷環境での利用に向いていますが、一方で実装が複雑で負荷が高まってしまいがちとのこと。

負荷を緩和するためにレート制限する場合、レート制限アルゴリズムが負荷を高めてしまっては本末転倒です。そのため、多くのサービスではフローティングウィンドウ(floating window)方式という近似方式で計算を行います。フローティングウィンドウは固定ウィンドウ方式をベースに、前のウィンドウで発生したアクセス回数を現在から一定時間前までのうち前のウィンドウが占める割合で重み付けしてレート制限の対象に加えます。
例えば下図の場合、前のウィンドウで5回のアクセスが発生しており、「現時点」から一定時間前までに占める前のウィンドウの割合は57％です。5×0.57＝2.85がレート制限の対象に加えられるため、現在のウィンドウで3回しかリクエストが発生していないにもかかわらずレート制限が発生してリクエストが失敗します。

厳密にはスライドウィンドウ方式とフローティングウィンドウ方式でアクセスできるタイミングは異なるものの、アクセスする回数は平均的にみて同じになるうえ、フローティングウィンドウ方式は実装がはるかに簡単で負荷も軽いというメリットが存在しています。

また別のレート制限方式として、「トークンバケット(Token buckets)方式」が紹介されています。トークンバケット方式では期間内のアクセスを追跡する代わりに、「一定時間ごとにトークンがたまるバケット」を使用します。バケット内にトークンが存在していればアクセスが許可され、トークンを使い切った後は補充されるまでレート制限が発生する仕組みです。

トークンバケット方式ではトラフィックの急激な上昇が発生する可能性は残るものの、一定期間のアクセスを追跡せずとも連続アクセス数の上限を明確にできるほか、長期的な許容平均アクセスレートはトークンの補充間隔以内になるという特徴が存在しています。
さらにトークンバケット方式は柔軟性が高く、他の方式を模倣することも可能とのこと。例えばトークンを毎回上限と同じ数だけ補充する設定にすることで、ユーザーのアクセス時点から期間が始まる固定ウィンドウ方式と同じレート制限を実現することができます。

いずれの方式を利用する場合でも、レート制限によってユーザーのアクセスを拒否した場合には429ステータスコードや「RateLimit-Remaining」「RateLimit-Reset」などのHTTPヘッダでユーザーに通知するべきとのこと。
元のブログの末尾では今回取り上げられているレート制限の方式を比較することができるインタラクティブなアニメーションが用意されているため、気になる人は確認してみてください。

関連記事
「アルゴリズムって何？」を専門家が分かりやすく解説 - GIGAZINE
「アルゴリズム」という言葉の由来は？ - GIGAZINE
コンピュータを進化させてきた偉大なるアルゴリズムまとめ - GIGAZINE
ハッシュ関数「SHA-256」の計算プロセスをわかりやすく視覚化してくれる「Sha256 Algorithm Explained」 - GIGAZINE
興味のあるものをオススメしてくれる「レコメンデーション」に欠かせない5つのアルゴリズム - GIGAZINE