レートリミッターの設計
概要
この記事は、「システム設計の面接試験」（Alex Xu 著）を読み学習した内容を個人学習用にまとめ直したものです。
本記事では、Webサービスの安定運用に欠かせないレートリミッターの設計について解説します。
レートリミッターは一見シンプルな仕組みに見えますが、アルゴリズムの選定、分散環境での整合性、配置場所の判断など、設計上の論点が多いコンポーネントです。
レートリミッターとは
レートリミッター（rate limiter）とは、クライアントやサービスが送信するトラフィックのレート（送信率）を制御する仕組みである。HTTP APIの文脈では、一定期間内に送信できるリクエスト数に上限を設け、その閾値を超えたリクエストをブロックする。
具体例
- あるユーザーが1秒間に投稿できる回数を2回までに制限する
- 同一IPアドレスからのアカウント作成を1日10件までに制限する
- 同一デバイスからのリワード（報酬）獲得を1週間に5回までに制限する
レートリミッターを導入するメリット
| メリット | 説明 |
|---|---|
| DoS攻撃の防止 | 大量のリクエストによるサービス停止を防ぐ。大手テック企業のAPIの多くはレートリミッターを導入しており、例えばTwitterは3時間あたりのツイート数を300件に制限している |
| コストの削減 | 過剰なリクエストを制限することで、サーバーリソースの消費を抑える。サードパーティAPIへの課金が発生する場合、不要な呼び出しを減らすことでコスト削減に直結する |
| サーバー負荷の軽減 | Botや異常なトラフィックパターンによる過負荷を防ぎ、サービスの安定稼働を維持する |
本記事で扱う設計の前提条件
レートリミッターの設計はユースケースによって大きく変わる。本記事では、以下の要件を前提として設計を進める。
- 過剰なリクエストを的確に制限すること
- HTTP のレスポンスタイムが遅くならないこと(低遅延)
- 可能な限り少ないメモリで動作すること
- 複数のサーバやプロセスでレートリミッターを共有可能であること(分散型レートリミッター)
- リクエストが制限された時に、ユーザーに明確な例外を表示すること
- レートリミッターに何らかの問題が発生した場合(例: キャッシュサーバがオフラインになった場合)、システム全体には影響しないこと
レートリミッターの配置
レートリミッターはどこに置くべきか。大きく分けて、クライアント側・サーバー側・ミドルウェアの3つの選択肢がある。
クライアント側
クライアント（ブラウザやモバイルアプリなど）にレートリミッターを実装する方法である。しかし、クライアント側のリクエストは悪意のあるユーザーによって容易に偽装・改ざんできるため、一般的には信頼性の低いアプローチである。すべてのクライアントの実装を制御することも現実的ではない。
サーバー側
APIサーバー自体にレートリミッターを組み込む方法である。リクエストを受け取ったサーバーが自ら制限を判定するため、制御は確実だが、サーバーのリソースを消費する。
ミドルウェア
APIサーバーとは別に、レートリミッターをミドルウェアとして配置する方法である。リクエストがAPIサーバーに到達する前にミドルウェアがレートを判定し、閾値を超えたリクエストにはHTTP 429（Too Many Requests）を返す。
クラウド環境では、レートリミッターは一般的にAPIゲートウェイと呼ばれるコンポーネントに実装される。APIゲートウェイはレートリミッターのほかに、SSL終端、認証、IPホワイトリスト管理などを一元的に担うマネージドサービスである。
どこに配置すべきか
最適な配置場所は、技術スタック・チームのリソース・要件によって異なるが、一般的な指針として以下が挙げられる。
- サーバー側の技術スタックが現在のプログラミング言語でレートリミッターを効率よく実装できるか確認する。実装の自由度が必要な場合はサーバー側に置く
- すでにAPIゲートウェイを利用している場合は、ゲートウェイにレートリミッター機能を追加するのが合理的
- 自前でレートリミッターを構築するリソースが十分にない場合は、商用のAPIゲートウェイの利用を検討する
商用のAPIゲートウェイの例:
- AWS API Gateway — AWSのマネージドサービス。レートリミッター（スロットリング）機能を標準搭載
- Google Cloud Apigee — Google Cloudが提供するAPI管理プラットフォーム
- Azure API Management — MicrosoftのAPIゲートウェイサービス
- Kong Gateway — オープンソース版と商用版があり、クラウド非依存で利用可能
レートリミッターのアルゴリズム
レートリミッターは様々なアルゴリズムで実装できる。代表的なものとして以下の5つがある。
- トークンバケット（Token Bucket）
- リーキーバケット（Leaky Bucket）
- 固定ウィンドウカウンター（Fixed Window Counter）
- スライディングウィンドウログ（Sliding Window Log）
- スライディングウィンドウカウンター（Sliding Window Counter）
それぞれ特性が異なり、ユースケースに応じて使い分ける必要がある。以降、各アルゴリズムの仕組みを順に見ていく。
トークンバケット
トークンバケットは広く使われているアルゴリズムで、シンプルかつ理解しやすい。Amazon やStripeなどの企業がAPIのレートリミッターに採用している。
仕組み
トークンバケットアルゴリズムは、あらかじめ容量が決められた「バケツ（バケット）」にトークンを貯め、リクエストごとにトークンを消費するという考え方に基づく。
上図の通り、動作は大きく2つの流れで構成される。
リクエスト処理（左側）: リクエストが到着するとバケット内のトークンを確認し、残っていれば1つ消費して許可、なければ拒否する。
トークン補充（右側）: 一定のレートでトークンが補充される。ただしバケットが満杯の場合、追加のトークンは破棄される。
パラメータ
トークンバケットアルゴリズムは、以下の2つのパラメータで制御する。
| パラメータ | 説明 |
|---|---|
| バケットサイズ | バケットに入るトークンの最大数 |
| 補充レート | 1秒あたりにバケットに追加されるトークンの数 |
バケットの数はレートリミッターのルールに応じて決定する。例えば以下のようなケースが考えられる。
- APIエンドポイントごとにバケットを用意する（例: 投稿用、友達追加用、いいね用に各1つ）
- IPアドレスごとにリクエストを制限する場合、IPアドレスごとにバケットを用意する
- システム全体で1秒あたりのリクエスト数を制限する場合、すべてのリクエストで1つのバケットを共有する
メリットとデメリット
| メリット | デメリット |
|---|---|
| 実装が容易である | バケットサイズと補充レートの2つのパラメータの適切なチューニングが難しい |
| メモリ効率が良い | |
| バーストトラフィック（短期間の大量リクエスト）に対応できる |
リーキーバケット
リーキーバケット（leaky bucket）はトークンバケットと似ているが、トークンバケットがトークンの残量に応じてバーストトラフィックを許容するのに対し、リーキーバケットはリクエストの処理レートを常に一定に保つ点が異なる。Spotifyがレート制限に採用しており、FIFO（先入れ先出し）キューで実装される。
仕組み
リーキーバケットアルゴリズムは、リクエストをキューに入れ、一定のレートでキューから取り出して処理するという考え方に基づく。バケツに穴が空いていて水が一定速度で漏れ出すイメージである。
動作は大きく2つの流れで構成される。
リクエスト受付（左側）: リクエストが到着するとキューの空きを確認する。空きがあればキューに追加し、満杯であればリクエストを拒否する。
リクエスト処理（右側）: キューからリクエストを一定のレートで取り出し、APIサーバーで処理する。
パラメータ
リーキーバケットアルゴリズムは、以下の2つのパラメータで制御する。
| パラメータ | 説明 |
|---|---|
| バケットサイズ | キューに入るリクエストの最大数 |
| 流出レート（outflow rate） | 一定時間内に処理できるリクエストの数 |
メリットとデメリット
| メリット | デメリット |
|---|---|
| キューのサイズが制限されているため、メモリ効率が良い | バーストトラフィックが発生すると、古いリクエストがキューに滞留し、新しいリクエストがドロップされる |
| 一定のレートで処理されるため、安定した出力が求められるユースケースに適している | バケットサイズと流出レートの2つのパラメータの適切なチューニングが難しい |
固定ウィンドウカウンター
固定ウィンドウカウンター（fixed window counter）は、時間を固定長のウィンドウに分割し、ウィンドウごとにリクエスト数をカウントして制限するアルゴリズムである。
仕組み
タイムラインを一定の間隔（例: 1秒、1分）で区切り、各ウィンドウにカウンターを割り当てる。
動作は以下の通りである。
- リクエストが到着すると、現在のウィンドウのカウンターを確認する
- カウンターが閾値未満であればカウンターをインクリメントし、リクエストを許可する
- カウンターが閾値に達している場合、リクエストを拒否する
- 新しいウィンドウが始まると、カウンターは0にリセットされる
パラメータ
| パラメータ | 説明 |
|---|---|
| ウィンドウサイズ | ウィンドウの時間幅（例: 1秒、1分、1時間） |
| 許可リクエスト数 | 1つのウィンドウ内で許可するリクエストの最大数 |
ウィンドウ境界の問題
固定ウィンドウカウンターには、ウィンドウの切り替わりタイミングで閾値を超えるリクエストが通過しうるという問題がある。
例えば、1分あたり最大5リクエストという制限を設定した場合を考える。
ウィンドウ1 (0:00〜0:59) ウィンドウ2 (1:00〜1:59)
| |
・・・・・[● ● ● ● ●]|[● ● ● ● ●]・・・・・
0:55〜0:59 1:00〜1:04
↑ 5リクエスト ↑ 5リクエスト
上記のように、ウィンドウ1の最後の5秒間に5リクエスト、ウィンドウ2の最初の5秒間に5リクエストが送信された場合、各ウィンドウ単体では閾値を超えていないが、実質的に10秒間で10リクエスト（本来の2倍）が通過してしまう。
メリットとデメリット
| メリット | デメリット |
|---|---|
| メモリ効率が良い | ウィンドウ境界でバーストが発生し、一時的に閾値を超えるリクエストが通過する可能性がある |
| 理解しやすく実装が容易である | |
| ウィンドウの切り替わりでカウンターがリセットされるため、直近のリクエストが制限に引きずられない |
スライディングウィンドウログ
スライディングウィンドウログ（sliding window log）は、固定ウィンドウカウンターの境界問題を解決するアルゴリズムである。固定のウィンドウ境界を持たず、リクエストのタイムスタンプを記録して判定する。
仕組み
リクエストごとにタイムスタンプをソート済みセット（Redisの Sorted Set など）に記録し、現在時刻から遡ったウィンドウ内のログ数でレートを判定する。
動作は以下の通りである。
- 新しいリクエストが到着すると、現在のウィンドウより古いタイムスタンプをログから削除する
- 新しいリクエストのタイムスタンプをログに追加する
- ログのサイズが閾値以下であればリクエストを許可し、超えていれば拒否する
具体例
1分あたり最大3リクエストの制限で、以下のようにリクエストが到着した場合を考える。
時刻 ログの状態 ログ数 結果
─────────────────────────────────────────────────────────────
1:00:01 [1:00:01] 1 ✅ 許可
1:00:30 [1:00:01, 1:00:30] 2 ✅ 許可
1:00:50 [1:00:01, 1:00:30, 1:00:50] 3 ✅ 許可
1:01:20 [1:00:30, 1:00:50, 1:01:20] 3 ✅ 許可
↑ 1:00:01 は1分前なので削除
1:01:25 [1:00:30, 1:00:50, 1:01:20, 1:01:25] 4 ❌ 拒否
4番目のリクエスト（1:01:20）到着時、1:00:01のログはウィンドウ（1:00:20〜1:01:20）の範囲外のため削除される。ログ数は3で閾値以下なので許可される。
5番目のリクエスト（1:01:25）到着時、ウィンドウは1:00:25〜1:01:25となる。1:00:30以降のログはすべて範囲内のため削除されず、ログ数が4となり閾値を超えるため拒否される。
このようにウィンドウがリクエスト時点から動的に計算されるため、固定ウィンドウカウンターで発生する境界問題が起きない。
メリットとデメリット
| メリット | デメリット |
|---|---|
| ウィンドウが動的なため、境界問題が発生せず正確なレート制限が可能 | リクエストごとにタイムスタンプを保持するため、メモリ消費が大きい |
| 拒否されたリクエストのタイムスタンプもログに記録されるため、メモリ効率が悪い |
スライディングウィンドウカウンター
スライディングウィンドウカウンター（sliding window counter）は、固定ウィンドウカウンターとスライディングウィンドウログの長所を組み合わせたアルゴリズムである。固定ウィンドウカウンターのメモリ効率の良さを保ちつつ、境界問題を緩和する。
仕組み
前のウィンドウと現在のウィンドウのカウンターを、時間の重なり具合に応じて重み付けして合算することで、スライディングウィンドウを近似的に実現する。
計算式は以下の通りである。
リクエスト数 = 前のウィンドウのリクエスト数 × 前のウィンドウとの重複割合
+ 現在のウィンドウのリクエスト数
具体例
1分あたり最大7リクエストの制限で、以下の状況を考える。
前のウィンドウ 現在のウィンドウ
(0:00 〜 0:59) (1:00 〜 1:59)
┌─────────────────┐ ┌─────────────────┐
│ 5リクエスト │ │ 3リクエスト │
└─────────────────┘ └─────────────────┘
↑ 現在時刻: 1:15
│（ウィンドウの25%が経過）
現在時刻が1:15の場合、現在のウィンドウは25%経過しているため、前のウィンドウとの重複割合は75%となる。
リクエスト数 = 5（前のウィンドウ）× 0.75（重複割合）+ 3（現在のウィンドウ）
= 3.75 + 3
= 6.75
6.75 ≤ 7（閾値）なので、このリクエストは許可される。
メリットとデメリット
| メリット | デメリット |
|---|---|
| 固定ウィンドウカウンターの境界問題を緩和する | 前のウィンドウのリクエスト分布が均等であることを前提とした近似値であり、完全に正確ではない（ただし、Cloudflareの実験では0.003%の誤差に留まることが確認されている） |
| ウィンドウごとのカウンターのみを保持するため、メモリ効率が良い |
アーキテクチャ概要
ここまでで、レートリミッターの配置場所とアルゴリズムを整理した。本セクションでは、これらを踏まえた全体アーキテクチャを示す。
全体構成
レートリミッターをミドルウェアとして配置し、カウンター情報をRedisで管理する基本構成を以下に示す。
処理の流れ
- クライアントからリクエストがレートリミッターミドルウェアに到着する
- レートリミッターはRedisからカウンターの値を取得する
- カウンターが閾値に達しているか確認する
- 閾値未満の場合: カウンターをインクリメントし、リクエストをAPIサーバーへ転送する
- 閾値に達している場合: リクエストを拒否し、HTTP 429（Too Many Requests）を返す
なぜRedisを使うのか
レートリミッターのカウンター管理にRedisが適している理由は以下の通りである。
- 高速: インメモリのデータストアであるため、ディスクベースのデータベースに比べて圧倒的に低レイテンシである
-
原子的操作:
INCR（カウンターのインクリメント）とEXPIRE（有効期限の設定）をアトミックに実行できるため、競合状態を防ぎやすい - 分散環境での共有: 複数のAPIサーバーから共通のRedisインスタンスを参照することで、サーバー間でカウンターを共有できる
運用設計
レート制限ルールの管理
レート制限のルール（例: 「このエンドポイントは1分あたり最大5リクエスト」）は、ディスク上の設定ファイルに保存される。以下はYAML形式のルール定義の例である。
rules:
- endpoint: /api/posts
limit: 5
window: 60s
- endpoint: /api/login
limit: 10
window: 60s
ワーカーが定期的にディスクからルールを読み込み、メモリ上のキャッシュに展開する。リクエスト判定時にはキャッシュ上のルールを参照するため、ディスクI/Oが毎回発生することはない。
なお、ルールの保存先はレートリミッターと同じサーバーのローカルディスクに置く場合もあれば、設定管理サービス（Consul、etcdなど）に保存する場合もある。
レート制限超過時の挙動
レートリミッターがリクエストを制限した場合、クライアントにはHTTP 429（Too Many Requests）ステータスコードが返される。このとき、以下のHTTPレスポンスヘッダーを付与することで、クライアントにレート制限の状態を伝えることができる。
| ヘッダー | 説明 |
|---|---|
| X-Ratelimit-Remaining | 現在のウィンドウ内で許可される残りのリクエスト数 |
| X-Ratelimit-Limit | ウィンドウ内で許可されるリクエストの最大数 |
| X-Ratelimit-Retry-After | 制限が解除されるまでの待機時間（秒） |
制限を超過したリクエストの扱いには、主に2つの方針がある。
- 即座にドロップする: リクエストを破棄し、HTTP 429を返す。最もシンプルな方法である
- メッセージキューに入れる: 制限超過したリクエストをキューに入れておき、後から処理する。リクエストを完全に失いたくないユースケース（注文処理など）に適している
アーキテクチャ詳細設計
ここまでの内容を踏まえ、アーキテクチャ概要の基本構成に運用設計（ルール管理・制限超過時の処理）を加えた詳細設計図を以下に示す。
処理の流れは以下の通りである。
- クライアントからリクエストがレートリミッターミドルウェアに到着する
- レートリミッターはキャッシュからレート制限ルールを参照し、Redisからカウンターの値を取得する
- カウンターが閾値未満の場合、カウンターをインクリメントし、リクエストをAPIサーバーへ転送する
- カウンターが閾値に達している場合、制限超過として処理する
- 破棄: リクエストをドロップし、HTTP 429とレート制限ヘッダーをクライアントに返す
- 保留: リクエストをメッセージキューに追加し、後からAPIサーバーで処理する
なお、レート制限ルールはワーカーがディスク上の設定ファイルから定期的に読み込み、キャッシュを更新する。
分散環境での課題
単一サーバーで動作するレートリミッターの構築は比較的容易である。しかし、複数のサーバーやプロセスにスケールアウトすると、新たな課題が発生する。ここでは代表的な2つの問題と、その対策を整理する。
競合状態（Race Condition）
複数のリクエストが同時にRedisのカウンターを操作した場合、競合状態が発生する可能性がある。
上図のように、リクエスト1とリクエスト2がほぼ同時にカウンターを読み取ると、両方とも値3を取得する。その後それぞれが+1した値（4）を書き込むため、本来5になるべきカウンターが4のままとなり、制限を正しく適用できない。
対策
一般的な解決策としてデータベースロック（排他制御）が考えられるが、ロックの取得・解放によりレイテンシが増大し、レートリミッターに求められる低遅延の要件を満たせなくなるため適切ではない。
代わりに、以下のようなRedisのアトミック操作を活用する。
- Luaスクリプト: Redisはカウンターの取得と更新をLuaスクリプトでアトミックに実行できる。複数の操作を1つの不可分な処理としてRedis上で実行するため、競合状態が発生しない
- RedisのソートセットTODO: Redisのソート済みセット（Sorted Set）を使用することで、タイムスタンプベースのレート制限をアトミックに実現できる
同期の問題
複数のレートリミッターインスタンスを使用する場合、データの同期が問題になる。
各レートリミッターが独自のRedisインスタンスを持つ場合、同一クライアントのリクエストが異なるレートリミッターに振り分けられると、カウンターが分散してしまい正確なレート制限ができない。
対策
スティッキーセッション（同一クライアントのリクエストを常に同じレートリミッターに振り分ける方式）で解決する方法も考えられるが、スケーラビリティや可用性が低下するため推奨されない。特定のレートリミッターに障害が発生した場合、そのクライアントのリクエストが処理できなくなる。
より適切な対策は、中央集権型のRedisストアを使用し、すべてのレートリミッターインスタンスが同一のRedisを参照する構成にすることである。
まとめ
レートリミッターの設計で押さえるべきポイントを整理する。
- 配置: クライアント側は信頼性が低い。ミドルウェアまたはAPIゲートウェイへの配置が一般的である
-
アルゴリズム選定: ユースケースに応じて選ぶ
- バーストを許容したい → トークンバケット
- 安定した処理レートが必要 → リーキーバケット
- シンプルさ重視 → 固定ウィンドウカウンター
- 正確さ重視 → スライディングウィンドウログ
- 正確さとメモリ効率のバランス → スライディングウィンドウカウンター
- データストア: カウンター管理にはRedisが適している（低レイテンシ・アトミック操作・分散共有）
- 分散環境: 競合状態にはLuaスクリプト等のアトミック操作、同期問題には中央集権型Redisで対応する
参考文献
この記事は以下の情報を参考にして執筆しました。