Rate Limitアルゴリズムを可視化して理解する

なぜRate Limit（使用量制限）が必要なのか?

• 参加者の多いTwitchチャットでスパマーが1人いると、使用量制限がなければそのスパマーが会話を支配してしまう。
• 使用量制限によって、各ユーザーが公平に参加する機会を持てる。
• Rate Limiter（使用量制限器）は、一定期間に設定された上限を超えるリクエストを遮断してサービスのトラフィックを制御する。これはチャットでのスパム抑制以外にも有用。
• たとえばログインフォームでは、使用量制限によってブルートフォース攻撃を抑えつつ、少数の誤った推測は許容できる。
• APIエンドポイントにもよく使用量制限が適用され、単一ユーザーがリソースを独占できないようにする。
  • ユーザーが高コストなAPIエンドポイントを1分あたり100回までしか呼び出せないようにするなら、カウンターで1分あたり100回のヒットを追跡し、その後のリクエストは遮断する。
  • これは最も単純な使用量制限アルゴリズムの1つである固定ウィンドウ制限器（Fixed Window Limiter）。
  • サービストラフィックを制御する一般的な方法。

Fixed windowsアルゴリズム

• 固定された時間ウィンドウ内でリクエスト数が制限される。
• 各時間ウィンドウの開始時にリクエストカウンターが0にリセットされる。
• 長所
  • 実装と理解が容易。
  • ユーザーにとって予測しやすい。
• 短所
  • 時間ウィンドウの終わり際にリクエストが始まると、制限の最大2倍までのバーストが許容されうる。
• 実例: GitHub APIは、1時間あたり5,000リクエストを許可する固定時間ウィンドウのレートリミッターを使っている。
• 時間ウィンドウの開始時刻を固定間隔にする代わりに、各時間ウィンドウはそのウィンドウ内でのユーザーの最初のリクエスト時点に生成することもできる。
• このアプローチでは、次の時間ウィンドウまでの残り時間をユーザーに知らせることが特に重要。

スライディングウィンドウ（Sliding windows）アルゴリズム

• 容量を一度にすべて補充する代わりに、スライディングウィンドウは1リクエストずつ容量を補う。
• 長所
  • リクエストトラフィックの分布を滑らかにする。
  • 高負荷に適している。
• 短所
  • 固定時間ウィンドウよりユーザーにとって予測しにくい。
  • 各リクエストのタイムスタンプを保存するのはリソース集約的。
• スライディングウィンドウは高トラフィックなシナリオで最も有用なので、基本アルゴリズムがリソース集約的であることは逆効果になる。
• そのため、実際のスライディングウィンドウ型レートリミッターの多くは近似方式（approximation）を使う。
• 近似方式では、前の固定時間ウィンドウで許可されたリクエスト数と現在の固定時間ウィンドウで許可されたリクエスト数を計算し、前の時間ウィンドウの許可済みリクエストに対して、現在時刻で終わる浮動時間ウィンドウとの重なりに比例した重みを与える。
• この近似方式は、ほぼ同じ比率でリクエストを制限しつつ、はるかに効率的。
• 実例: Cloudflareの構成可能なレートリミッターは近似スライディングウィンドウを使っている。

トークンバケット（Token buckets）アルゴリズム

• 時間ウィンドウの継続時間の代わりに、一定速度で「トークン」で満たされるバケットを想像する。
• 各リクエストはこのバケットから1つのトークンを引き出し、バケットが空なら次のリクエストは遮断される。
• バケットの容量は、サポートできるバーストの最大リクエスト数を表す。
• 補充間隔は、長期平均で許容されるリクエスト間隔を表す。
• 複数のレートリミッターを使わなくても、バースト容量と平均容量を別々に持てることが、このアルゴリズムの主要な利点の1つ。
• 長所
  • 高トラフィックのバーストを許容しつつ、長期平均のリクエストレートを適用できる。
  • ユーザーにとってより柔軟で、許容範囲内でのトラフィック急増を認められる。
• 短所
  • 固定時間ウィンドウより、制限内容や補充時間をユーザーに伝えにくい。
• 実例
  • Stripeは、ユーザーあたり上限500、補充間隔0.01秒のトークンバケットを使い、継続的には毎秒100リクエストを許可しつつ、最大500リクエストまでのバーストを許容している。
  • OpenAIのGPT-3.5無料ティアは、上限200、補充間隔86400秒/200のトークンバケットを使い、1日200リクエストに制限されている。

レートリミット適用時の考慮事項

• レートリミッター用の永続ストレージを用意する必要がある。
• 永続ストレージへのサーバー接続に失敗した場合は、リクエストを遮断せずすべて許可するようにすべき。
• 必要に応じてバーストトラフィックを調整できる。
• 適切なキーを選ぶ必要がある（ユーザーID、APIキーなど）。
• 有用なレート制限エラーを表示すべき（次のリクエストまでの待機時間、429 HTTPステータスコード、x-ratelimit-*レスポンスヘッダーなど）。

[humblebee]

韓国語で要約された記事を読んで、「オーケー、何なのかは分かったけど、どれも同じ内容じゃないの？」と思いながら元リンク先の記事を読んでみたら、本当に説明が上手で、可視化もとても満足できるものでした！ 👍👍👍

[GN⁺]

Hacker Newsの意見

Hacker Newsコメントまとめ要約

• 長年の経験から得られた追加の考慮事項:

  • Rate Limits: バックエンドの容量問題は解決できない。ポリシー上の制限として見なすべき。
  • Bad Traffic: 単純な rate limits 以外の追加措置を検討すべき。認証状態、ユーザー/セッションの優先順位などに基づいてトラフィックの優先順位を決めるのが有用。
  • Communication: 重要な顧客や社内チームが rate limits に達したときの対応策を準備しておくべき。
  • Concertina Effects: すべての固定ウィンドウ、または多数のスライディングウィンドウが同時に期限切れになるのを防ぐため、各ユーザー/セッションのウィンドウに決定論的オフセットを追加すべき。

• マルチテナント環境で DoS 攻撃を防ぐには公平キューイングが最適なアプローチ: 各クライアントに専用キューを割り当て、バックグラウンドルーチンが各キューを繰り返し巡回しながらリクエストを処理する。スパムリクエストを送るクライアントは、自分のキューだけを混雑させることになる。

• クライアント処理コードの実装経験: rate limit に達したときの最適なバックオフ戦略について、以前から気になっていた。サービス側の観点でのトレードオフを読むのが興味深かった。

• 祝福のメッセージ: 短いコンテンツに対する最高の可視化であり、とても情報量が多く、要点がよく整理された投稿。

• GCRAアルゴリズム: rate limiting において、より優れたアルゴリズムだと思う。もっと広く知られ、使われてほしい。

  • GCRA実装例
  • GCRAウィキペディア

• 素晴らしい仕事: この投稿には多くの時間と努力が注ぎ込まれていることが伝わってくる。よくやった。

• AWS Lambdaでの rate-limiting 問題: NodeJS で rate-limiting を実装しようとしたが、AWS Lambda ではタイマーが奇妙に動作して目標値を超えてしまった。ローカルテストでは通ったが、Lambda では失敗した。タイマーの問題なのか、ライブラリの問題なのかは不明。

• Rate limiting レイヤーが飽和状態のときの対処: CF 以外の選択肢があるのか気になる。小さな VPS に対する DoS 攻撃の防御で、nftable ルールがどの程度有効なのか知りたい。

• このリソースが必要だった瞬間が何度もあった: キャリアの中で何度も必要としていたリソース。今これが存在していることがうれしい。

• データ可視化ファン: D3 を使っているのか気になる。