【ITニュース解説】Step 5: Design a Rate Limiter - Algorithm and Technique

レートリミッターとは、システムが処理できるリクエストの数を制御し、過負荷を防ぐための重要な仕組みだ。多数のユーザーが同時にアクセスするような大規模なシステムでは、システムがダウンしたり、応答が遅くなったりするのを防ぎ、安定性、公平性、セキュリティを確保するために、このリクエスト制限が不可欠となる。ここでは、主要なレートリミッターのアルゴリズムを、システムエンジニアを目指す人にもわかりやすく解説する。

まず、トークンバケットアルゴリズムは、リクエストの利用券である「トークン」が入ったバケツを使う。トークンは一定速度でバケツに追加され、リクエストが来るとトークンを一つ消費する。バケツにトークンがなければリクエストは拒否される。この方法の利点は、バケツにトークンが貯まっていれば、一時的な集中アクセスである「バースト」を許容できる点だ。例えば、ユーザーが短時間に多くの投稿を行うソーシャルメディアのような場面で有効である。実装は比較的簡単で、ユーザーごとのトークン数を分散キャッシュに記録し、増減をアトミックな操作で管理できる。しかし、バーストが許可されるため、悪意のあるユーザーがこれを悪用する可能性も考慮する必要がある。

次に、リーキーバケットアルゴリズムは、バケツに水が流れ込み、一定の速さで水が漏れ出すイメージで説明される。リクエストは「水」としてバケツに入り、バケツから「漏れ出す」速さで処理される。バケツが満杯になると、それ以上水は入らず、リクエストは拒否される。このアルゴリズムはバーストを一切許容せず、常に一定の速度でリクエストを処理するため、システムの負荷を平滑化するのに非常に優れている。クレジットカードの決済処理のように、厳格な処理速度が求められるシステムに適している。リクエストをキューに入れて管理するため、大規模になるほどキューの管理が複雑化し、リソースを多く消費する可能性がある。

固定ウィンドウカウンターアルゴリズムは、時間を固定された間隔（例えば60秒間）に区切り、その時間枠内でリクエスト数をカウントする。カウントが上限に達すると、そのウィンドウが終わるまで以降のリクエストは拒否される。この方法はシンプルで実装も容易だが、ウィンドウの境界でリクエストが集中する「境界問題」という欠点がある。例えば、ウィンドウ終了直前と次のウィンドウ開始直後にそれぞれ上限いっぱいのリクエストが送られると、短い期間に通常の2倍近いリクエストが集中してしまう可能性がある。日ごとのAPI呼び出し制限など、比較的緩やかな制限に用いられることが多い。

スライディングウィンドウログアルゴリズムは、各リクエストが発生した正確な時刻を全て記録し、常に現在の時刻から過去一定期間内のリクエスト数を数える。この方法の最大の利点は、非常に高い精度でレートを制御できることだ。固定ウィンドウカウンターのような境界問題も発生しない。しかし、個々のリクエスト時刻を全て記録するため、特にリクエストが多いシステムでは、大量のメモリを消費するという大きな欠点がある。また、古いタイムスタンプを定期的に削除する処理も必要となる。ログイン試行回数を厳密に制限してブルートフォース攻撃を防ぐような、精度が最優先される場面で有効だが、大規模システムではリソースの制約が課題となる。

最後に、スライディングウィンドウカウンターアルゴリズムは、固定ウィンドウカウンターとスライディングウィンドウログの長所を組み合わせた、バランスの取れた方法だ。時間をさらに小さな「サブウィンドウ」（例えば10秒間のウィンドウを1秒間のサブウィンドウに分ける）に分割し、それぞれのサブウィンドウのリクエスト数をカウントする。そして、現在のスライディングウィンドウ内のリクエスト数を、関連するサブウィンドウのカウンターを合計して計算する。この際、現在のウィンドウとサブウィンドウの重なり具合を考慮して重み付けを行うことで、スライディングウィンドウログに近い精度を実現しつつ、メモリ使用量はログ方式よりも大幅に抑えることができる。実装は固定ウィンドウより複雑になるが、精度とリソース効率のバランスが良いため、大規模なAPIレート制限で広く推奨される。

これらのアルゴリズムを、10億人規模のユーザーと1日数億のリクエストを処理するようなシステムに適用する場合、特にリソース効率が重要になる。トークンバケットはバースト許容、リーキーバケットは定常処理に特化し、固定ウィンドウはシンプルだが境界問題がある。スライディングウィンドウログは高精度だがメモリ消費が課題だ。そのため、多くの大規模分散システムでは、特に短い時間窓での精度とリソース効率のバランスを考えると、スライディングウィンドウカウンターが最も現実的な選択肢となる。Redisのような高速な分散キャッシュシステムを活用し、シャード（データを複数のサーバーに分散させる手法）や複数のデータセンターへの展開を組み合わせることで、大規模な要件にも対応可能となる。