Skip to content
Published on

レートリミットのアルゴリズム徹底解説：固定ウィンドウ・スライディングウィンドウ・トークンバケット・リーキーバケット

🇰🇷KO🇺🇸EN🇯🇵JA
필사 모드
Authors

はじめに — なぜ速度を制限するのか

レートリミット(rate limiting)とは「一定時間に許可するリクエスト数を制限すること」です。一見ユーザーを不便にする仕掛けのように見えますが、実はシステム全体を守る安全装置です。

レートリミットが必要な理由はいくつもあります。暴走するトラフィックや誤動作するクライアントからサーバー資源を守り、総当たり(ブルートフォース)のログイン試行やスクレイピングのような濫用を防ぎ、複数のユーザーの間で資源を公平に分け、有料APIのプランごとの使用量を強制します。要するに、安定性と公平性のための仕組みです。

問題は「リクエスト数を数える」という単純なアイデアを、実際に実装する方法が複数あることです。各方法は正確性、メモリ使用量、バーストの許容の仕方で異なるトレードオフを持ちます。この記事は代表的なアルゴリズムを一つずつ対比し、分散環境の実装とクライアントの作法まで扱います。概念を目で実験してみたければ、このサイトのメッセージキュー・プレイグラウンドでスループットとフロー制御を視覚的に触ってみられます。

固定ウィンドウカウンター — もっとも単純な方式

もっとも直感的な方法は、時間を固定された窓(ウィンドウ)に分け、各窓の中でリクエスト数を数えることです。たとえば「1分あたり100回」なら、毎分の始まりにカウンターを0に初期化し、リクエストが来るたびに1ずつ増やします。カウンターが100を超えたら、その分が終わるまで拒否します。

  1分あたり100回制限、固定ウィンドウ
  [00:00 ~ 00:59]  カウント 0 -> 100 (超過分を拒否)
  [01:00 ~ 01:59]  カウントをリセット、再び 0 -> 100

利点は明確です。実装がとても簡単で、保存する状態がカウンター一つだけなのでメモリをほとんど使いません。ですが致命的な弱点があります。窓の境界でバーストが二倍に噴き出しうるという点です。

たとえばあるユーザーが00:00:59に100回まとめて送り、すぐに01:00:01に再び100回送るとします。二つの時刻はわずか2秒差ですが、別々の窓に属するので両方とも許可されます。結果としておよそ2秒で200回が通過します。名目上は1分あたり100回制限なのに、実際には瞬間的に二倍が漏れ出たのです。この境界問題こそ、次の方式が登場した理由です。

スライディングウィンドウログ — 正確だが重い

境界問題を根本からなくすには、固定された窓の代わりに「今この瞬間からさかのぼった1分」を基準にすればよいのです。これが**スライディングウィンドウログ(sliding window log)**です。各リクエストのタイムスタンプをすべて記録しておき、リクエストが来るたびに「現在時刻から1分以内に入ってきたリクエストが何個か」を数えます。

  リクエストが来るたびに:
  1) 現在時刻 - 60秒 より古いタイムスタンプをログから削除
  2) 残ったログの個数を数える
  3) 個数 < 100 なら許可して現在のタイムスタンプを追加、そうでなければ拒否

この方式は完璧に正確です。どの瞬間を基準に取っても、正確に過去1分間のリクエストだけを数えます。境界で二倍に噴き出すことがありません。

代わりにコストが大きい。すべてのリクエストのタイムスタンプを保存する必要があるので、トラフィックが多いほどメモリ使用量がリクエスト数に比例して増えます。毎秒数万件が入ってくるAPIで、ユーザーごとにこうしたログを保つのは負担です。そのため正確性は最高ですが、規模の大きいところでは次の折衷案が好まれます。

スライディングウィンドウカウンター — 実用的な折衷

**スライディングウィンドウカウンター(sliding window counter)**は、固定ウィンドウの軽さとスライディングログの正確性の間の実用的な妥協点です。アイデアは、現在の窓と直前の窓のカウンターだけを保ち、直前の窓のカウントを重なる割合だけ重み付けして近似することです。

計算はこうします。現在の窓ですでに経過した割合が分かれば、直前の窓はその分だけ重なりが減ります。したがって推定リクエスト数は次のようになります。

  推定値 = 現在の窓のカウント
         + 直前の窓のカウント * (直前の窓でまだ重なっている割合)

  例: 1分あたり100回、現在の窓が25%経過した時点
      直前の窓のカウント = 80、現在の窓のカウント = 30 なら
      推定値 = 30 + 80 * (1 - 0.25) = 30 + 60 = 90
      90 < 100 なので許可

この近似は、トラフィックが窓の中でおおむね均等に分布するという仮定に頼ります。完璧ではありませんが実務では誤差が小さく、保存する状態がカウンター二つだけなのでとても軽いです。そのため商用サービスのレートリミッターがよく採用する方式です。固定ウィンドウの境界バースト問題をほとんど解消しつつ、スライディングログのメモリ負担を避けます。

トークンバケット — バーストを許す優雅さ

ここまでの方式が「どれだけ多く来たか」を数えることに集中していたのに対し、トークンバケット(token bucket)は視点を変えます。リクエストを数える代わりに、リクエストを処理する権利であるトークンを配ります。

動作原理はこうです。決まった速度でバケツにトークンが補充されます(例:毎秒10個)。バケツには最大容量があります(例:100個)。リクエストが来るとトークンを一つ取り出して使います。トークンがあれば通過、なければ拒否です。

  トークンバケット (容量100、補充速度 毎秒10)
   トークンが毎秒10個ずつ落ちてバケツに溜まる (最大100)
       │
       ▼
   [ バケツ: ●●●●●●... 最大100個 ]
       │  リクエスト1件につきトークン1個消費
       ▼
   トークンがあれば通過、なければ拒否

トークンバケットの美しさはバーストを自然に許すところにあります。しばらくリクエストがなければトークンがバケツいっぱいに溜まります(最大100個)。そこへ急にリクエストが殺到すると、溜まっていたトークンの分だけ一度に通過させられます。つまり普段は静かなクライアントが瞬間的にまとめて送るのを許容しつつ、長期的な平均速度は補充速度(毎秒10個)に制限します。バケツの容量がバーストの最大値を、補充速度が持続可能な平均を決めます。

この柔軟さのおかげで、トークンバケットは実務でもっとも広く使われるアルゴリズムの一つです。多くのAPIゲートウェイやネットワーク機器がこの方式を使います。

リーキーバケット — 流れを滑らかに

**リーキーバケット(leaky bucket)**は名前のとおり「漏れるバケツ」にたとえられます。リクエストがバケツ(キュー)に溜まり、底の穴から一定の速度で漏れ出て処理されます。バケツがいっぱいになると、あふれるリクエストは捨てられます。

  リーキーバケット
   リクエストが上からキューに溜まる
       │
       ▼
   [ キュー: リクエストが待機 ]
       │  底から一定速度で処理 (例:毎秒10件)
       ▼
   キューがいっぱいならあふれるリクエストは捨てられる

トークンバケットとリーキーバケットはよく比較されます。核心の違いは出力の性格です。

  • トークンバケットはバーストを許します。トークンが溜まっていれば瞬間的に多く通過します。出力がでこぼこになりえます。
  • リーキーバケットは出力を滑らかにします。いくら入力が殺到しても底の穴の速度でしか出ないので、処理速度が一定です。代わりに瞬間的なバーストを吸収するにはキューで待つ必要があり、遅延が生じることがあります。

そのため選択は目的次第です。「たまのバーストは寛容に許しつつ平均だけ守りたい」ならトークンバケット、「ダウンストリームを守るために処理速度を一定にならしたい」ならリーキーバケットが合います。

アルゴリズム比較表

ここまでの内容を一つの表に整理するとこうなります。

アルゴリズムメモリ正確性バースト許容特徴
固定ウィンドウ非常に小さい低い(境界問題)境界で2倍漏れる実装が最も単純
スライディングログ大きい(リクエスト数比例)完璧なし正確だが重い
スライディングカウンター小さい(カウンター2個)高い(近似)ほぼなし実用的な折衷
トークンバケット小さい高い容量分だけ許容バーストに寛容、平均を制限
リーキーバケット小さい(キューサイズ)高い吸収して平坦化出力速度が一定

分散環境でのレートリミット

ここまでは一台のサーバーを前提にしていました。ですが実際のサービスは、複数のサーバーインスタンスがロードバランサの後ろで一緒にリクエストを処理します。ここで問題が生じます。各インスタンスが自分だけのカウンターを持つと、全体の制限がインスタンス数だけ水増しされます。インスタンスが5台でそれぞれ1分あたり100回を許可すると、ユーザーは事実上1分あたり500回使えてしまいます。

解決策は、カウンターをインスタンスの外の共有ストレージに置くことです。この役割にもっとも広く使われるのがRedisです。速いインメモリストレージであり、アトミックな演算とキーの有効期限(TTL)をサポートするからです。

固定ウィンドウをRedisで実装する簡単な例を見ましょう。

  キー:  ratelimit:{user_id}:{現在の分}
  1) INCR キー          -> カウンターをアトミックに1増やして新しい値を受け取る
  2) 値が1なら EXPIRE キー 60   -> この窓が過ぎたら自動削除されるようTTLを設定
  3) 値 > 100 なら拒否、そうでなければ許可

ここで重要なのは**アトミック性(atomicity)**です。「読んで、比較して、増やす」過程が複数の段階に分かれると、同時に入ってきたリクエストの間で競合状態(race condition)が生じて制限を超えられてしまいます。Redisの INCR はそれ自体がアトミックで、より複雑なロジック(スライディングウィンドウやトークンバケット)は、複数のコマンドを一つのアトミックな単位に束ねるLuaスクリプトで実装します。RedisはLuaスクリプトを単一スレッドでアトミックに実行するので、競合状態を避けられます。

分散レートリミットには追加で考える点があります。共有ストレージに毎リクエストごとにアクセスすると遅延と負荷が生じるので、わずかな正確さを犠牲にしてローカルで近似し、周期的に同期する方式も使います。正確性とパフォーマンスの間のトレードオフは、ここでも繰り返されます。

429とRetry-After — 拒絶をうまく伝える方法

レートリミッターがリクエストを拒否すると決めたら、その事実をクライアントに明確に伝えるべきです。このとき使うのがHTTPステータスコード429 Too Many Requestsです。このコードは「あなたが多く要求しすぎた」という意味を標準的に伝えます。

429を送るだけで終わりではありません。良いレートリミッターはいつ再試行すればよいかも一緒に伝えます。そのためのヘッダーが Retry-After です。値は秒単位の待機時間か、特定の時刻でありえます。

HTTP/1.1 429 Too Many Requests
Retry-After: 30
Content-Type: application/json

{ "error": "rate limit exceeded", "retry_after": 30 }

多くのAPIはこれに加えて、現在の残り割り当てを知らせるヘッダーも提供します。たとえば RateLimit-Limit(総制限)、RateLimit-Remaining(残り回数)、RateLimit-Reset(初期化までの時間)といったヘッダーです。こうした情報があれば、クライアントは壁にぶつかる前にあらかじめ速度を調節できます。429をはじめとするステータスコードの正確な意味が気になれば、HTTPステータスコード図鑑で各コードを見ていけます。

クライアントのバックオフの作法

レートリミットはサーバーだけの仕事ではありません。429を受け取ったクライアントがどう反応するかも、システム全体の健康に大きく影響します。429を受け取るやいなやすぐに再試行するクライアントは、サーバーをさらに苦しめるだけです。

正しい反応はバックオフ(backoff)、つまり再試行の間隔を次第に延ばすことです。

  • 指数バックオフ(exponential backoff): 再試行のたびに待機時間を倍に延ばします。1秒、2秒、4秒、8秒... こうすればサーバーが回復する時間を与えます。
  • ジッター(jitter)を加える: 複数のクライアントが同じ間隔で再試行すると、その再試行が一度に殺到して再びサーバーを叩く「サンダリングハード(thundering herd)」問題が生じます。そこで待機時間にわずかなランダム性を加えて再試行の時点を分散させます。
  • Retry-Afterを尊重する: サーバーが Retry-After で待機時間を伝えたなら、自分の計算よりその値を優先して従うのが礼儀です。
  • 上限を設ける: 無限に再試行しないよう、最大再試行回数や最大待機時間を決めておきます。
  429を受信したとき:
   待機 = min(基本 * 2^試行回数, 上限) + ランダムなジッター
   Retry-After ヘッダーがあればその値を優先

まとめると、よく設計されたレートリミットは、サーバーの拒絶とクライアントの節制が噛み合ったときに完成します。サーバーは429とRetry-Afterで明確に信号を送り、クライアントは指数バックオフとジッターで礼儀正しく引き下がります。

おわりに

レートリミットは「リクエスト数を数える」という単純な目標を抱いていますが、その実装には正確性、メモリ、バースト許容という三つの軸をめぐって多様な折衷が存在します。固定ウィンドウは単純ですが境界で漏れ、スライディングログは正確ですが重く、スライディングカウンターはその間の実用的な均衡です。トークンバケットはバーストを優雅に許し、リーキーバケットは出力を滑らかにならします。

さらに分散環境ではRedisのような共有ストレージとアトミックな演算が必要で、クライアント側では429とRetry-Afterに対する礼儀正しいバックオフが必要です。核心は「どのアルゴリズムが正しいか」ではなく「このシステムが何を守ろうとしているか」です。その答えを決めれば、どの道具を選ぶべきかも自然についてきます。

参考資料

Discuss on Twitter • View on GitHub