필사 모드: レートリミットのアルゴリズム選び — 固定ウィンドウ、スライディング、トークンバケットの実際の違い

はじめに — 毎分100回で止めたのに200回が入ってきた

レートリミットを付けました。キーあたり毎分100回。ところがモニタリングを見ると、あるクライアントが200ミリ秒のあいだに200個のリクエストを通していました。ログを漁ってもコードに問題はありません。

バグではありません。固定ウィンドウカウンターの定義された動作です。そしてこの事実を知らずにデプロイしたリミットは、守ろうとした対象をきちんと守れません。

レートリミットは一行のミドルウェアのように見えますが、実際には四つの決定の束です。どのアルゴリズムを使うか、何をキーにするか、分散環境でカウンターをどこに置くか、止められたクライアントに何を伝えるか。ひとつずつ見ていきます。

四つのアルゴリズムとトレードオフ

表を見るだけで選択肢が絞られます。スライディングログは正確ですが高価で、固定ウィンドウは安いですが不正確です。実務で残るのはスライディングウィンドウカウンターとトークンバケットの二つです。

固定ウィンドウの境界問題を数字で

上限が毎分100回で、ウィンドウが毎分0秒にリセットされるとします。クライアントがこう送ります。

10:00:59.900  リクエスト100個   → 10:00 ウィンドウのカウンター 0 → 100。全部通過
10:01:00.100  リクエスト100個   → 10:01 ウィンドウのカウンター 0 → 100。全部通過

200ミリ秒のあいだに200個が通りました。任意の連続する60秒区間を基準に見れば上限の2倍です。これが固定ウィンドウの上限です。どの60秒区間でも最大2倍が通過しえます。

上限が大きいほど絶対的な被害が大きくなります。毎分6000回の上限なら瞬間的に12000個が入ってきます。これくらいになると、守ろうとしたバックエンドがそのまま崩れます。

ウィンドウを短く刻めば緩和されます。毎分100回の代わりに毎秒2回に変えれば、境界での超過幅が絶対量として小さくなります。ただし正常なバーストまで一緒に切られてユーザー体験が悪くなります。

スライディングウィンドウカウンターは、ひとつ前のウィンドウのカウントを経過割合ぶん重みづけして足します。

現在時刻が 10:01:15 (ウィンドウの25%が経過)
前のウィンドウ(10:00)のカウント = 100
現在のウィンドウ(10:01)のカウント = 20

推定値 = 100 * (1 - 0.25) + 20 = 95
95 < 100 なので通過。あと5個受けたら遮断

ひとつ前のウィンドウのリクエストが均等に分布していたと仮定する近似です。仮定が外れても誤差は小さいです。クラウドフレアが自社トラフィックでこの方式を評価した結果を公開したことがありますが、誤って許可されたり誤って遮断されたりしたリクエストの割合は0.003パーセント程度でした。カウンター二つでスライディングログに近い精度を得られるわけです。

スライディングログの費用も押さえておく価値があります。Redisのソート済みセットにリクエストごとのタイムスタンプを入れると、要素ひとつが実際には数十バイトから100バイト近くを占めます。上限100、アクティブなキーが100万個なら項目1億個、数GBです。カウンター二つで済む方式と比べれば三桁の差です。

トークンバケット — バーストを許すことがAPIに合う理由

トークンバケットは二つの数字で定義されます。通のサイズと毎秒の充填速度です。リクエストが来たらトークンをひとつ取り出し、なければ拒否します。トークンは時間に比例して満たされますが通のサイズを超えません。

充填はタイマーではやりません。リクエストが来たときに経過時間ぶんを計算して満たせば済みます。だから保存するものはトークン数と最終更新時刻の二つだけです。

function consume(state, now, capacity, refillPerSec, cost = 1) {
  const elapsed = (now - state.updatedAt) / 1000
  const tokens = Math.min(capacity, state.tokens + elapsed * refillPerSec)

  if (tokens < cost) {
    const wait = (cost - tokens) / refillPerSec
    return { allowed: false, retryAfter: Math.ceil(wait), state: { tokens, updatedAt: now } }
  }
  return { allowed: true, state: { tokens: tokens - cost, updatedAt: now } }
}

ここで重要なのはバーストを明示的に定義するという点です。通のサイズ20に充填10個/秒なら、静かにしていて一度に20個を撃つことは許しつつ、長期平均は毎秒10個に縛られます。

この性質がAPIに合う理由は、実際のクライアントが均等にリクエストしないからです。ページをひとつ開けば並列リクエストが八つ同時に出ます。ユーザーが一覧を開いてフィルタをかければ短い区間にリクエストが集中します。厳格なスライディングウィンドウで毎秒10個を強制すると、こうした正常な画面ロードが切られます。ユーザーはサービスが壊れたと感じるのに、サーバーは暇です。

レートリミットの目的はリクエストの間隔を均一にすることではなく、長期の負荷を上限より下に保つことです。トークンバケットはその目的を正確に表現します。だから公開APIの大半がこの方式を使い、ドキュメントに通のサイズと充填速度をそのまま公開しています。

コストの重みづけも自然に付きます。一覧照会はトークン1個、レポート生成はトークン20個のようにエンドポイントごとに費用を変えれば、呼び出し回数ではなく実際の資源消費を制限することになります。GitHubのAPIがクエリの複雑度に応じて点数を変えているのも同じ発想です。

分散環境の実装 — 原子的操作とローカルリミットの誤差

ノードが複数あればカウンターを共有しなければならず、共有した瞬間に競合状態が生まれます。読んで判断して書く三段階のあいだに別のノードが割り込むと上限を超えます。

Redisでよく使われる組み合わせにも落とし穴があります。

# 危険 — INCRの直後にプロセスが死ぬとTTLのないキーが永遠に残ります
INCR rl:user_8812:1784056020
EXPIRE rl:user_8812:1784056020 60

キーが期限切れにならないと、そのユーザーはカウンターが上限に達したまま永久に止められます。原子的に処理しなければなりません。

-- スライディングウィンドウカウンター。KEYS[1]=前のウィンドウ、KEYS[2]=現在のウィンドウ
-- ARGV: 1=上限、2=ウィンドウの長さ(秒)、3=現在のウィンドウの経過割合
local prev = tonumber(redis.call('GET', KEYS[1]) or '0')
local curr = tonumber(redis.call('GET', KEYS[2]) or '0')
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local elapsed = tonumber(ARGV[3])

local estimated = prev * (1 - elapsed) + curr
if estimated >= limit then
  return {0, limit, 0}
end

curr = redis.call('INCR', KEYS[2])
if curr == 1 then
  redis.call('EXPIRE', KEYS[2], window * 2)
end
return {1, limit, math.floor(limit - estimated - 1)}

LuaスクリプトはRedisで単一スレッドで原子的に実行されるので、判断と増加のあいだに割り込む余地がありません。トークンバケットも同じ方式に移せますし、最近のRedisにはこの目的の拡張モジュールもあります。

ではノードごとにローカルカウンターを置く方式はどれくらい外れるのでしょうか。ノードがN個で、ロードバランサーが完璧に均等分配するなら、各ノードに上限をN分の1ずつ割り当てれば総和は合います。問題は二つです。

分配が均等ではありません。コネクション維持方式やハッシュベースのルーティングのせいで、あるクライアントのリクエストが特定のノードに偏ると、そのクライアントは全体の上限のN分の1しか使えずに遮断されます。実際の上限が広告した値よりずっと小さくなります。

ノード数が変わります。オートスケーリングでノードが増えれば各ノードの取り分を計算し直さなければならず、そうしなければ総許容量がノード数に比例して増えます。ノード10個にそれぞれ毎分100を掛けておくと、実際の上限は毎分1000です。

だから実用的な配置は二重です。ノードローカルには自分自身を守る緩い上限を置き、正確なユーザー別の上限は共有ストアで判断します。ストアの往復が負担なら、ノードが中央のバケットからトークンをまとめて借りてローカルで消費する方式も使います。精度を少し譲って往復回数を大きく減らす折衷です。

Redisが落ちたときの動作もあらかじめ決めておく必要があります。全部遮断すればリミットのストア障害が全面障害になり、全部通せばその瞬間に保護が消えます。ふつうは通しつつノードローカルの上限は維持し、アラートを上げます。

何をキーにするか

IPをキーにするのは既定値のように見えますが、いくつもの方向で壊れます。

ひとつのIPの後ろにユーザーが数千人いることがあります。会社のネットワーク、学校、通信事業者の大規模NATがそうです。IP基準で締めると、正常なユーザー集団が丸ごと止められます。

逆に攻撃者はIPを簡単に変えます。クラウドでIPを回す費用はほとんどなく、IPv6はホストひとつにプレフィックスひとつが丸ごと割り当てられる場合が多いので事実上無限です。IPv6をキーにするときは、アドレス全体ではなく上位プレフィックス単位でまとめてはじめて最低限の意味が出ます。

プロキシの後ろでクライアントIPを読む方式もよく間違えます。X-Forwarded-Forはクライアントが任意に埋めて送れる値なので、リストの先頭をそのまま信じると攻撃者が毎リクエストで別のIPを名乗ってリミットを無力化します。信頼するプロキシの数を数えて、後ろからその位置の値を取る必要があります。

優先順位はこう立てます。認証されたリクエストならユーザー識別子やAPIキーが第一です。料金プランと結びつくのでテナント単位のクォータも一緒に掛けます。認証以前の段階、つまりログインや登録のようなエンドポイントではIP以外に使えるものが乏しいので、IPを使いつつ上限を余裕をもって取り、代わりにアカウント識別子基準の別の上限を重ねます。ログイン試行はIPあたりの上限とアカウントあたりの上限を同時に掛けてはじめて、クレデンシャルスタッフィングと単一アカウントへの総当たりを一緒に防げます。

キーを何重にも重ねるときは最も狭いものから検査し、どの上限に引っかかったのかをレスポンスに残してはじめてデバッグが可能になります。

429とクライアントの再試行

上限を超えたときは429を使います。503はサーバー過負荷、403は権限なしなので意味が違います。クライアントが状況を判断できるように情報を載せて送ります。

HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
Retry-After: 12
RateLimit-Limit: 600
RateLimit-Remaining: 0
RateLimit-Reset: 12
Cache-Control: no-store

Retry-Afterは秒またはHTTP日付を受け取り、クライアントは自分のバックオフ計算よりこの値を優先すべきです。RateLimit系のヘッダーはIETFで標準化が進んでいるフィールドで、残り回数とリセットまでの時間を知らせます。既存のサービスが使ってきたX-RateLimit接頭辞のバージョンも依然として広く使われているので、両方を出す手もあります。

429レスポンス自体は安くあるべきです。遮断されたリクエストでDBを照会したり重いシリアライズをしたりすると、攻撃トラフィックがそのまま負荷になります。リミットの判定はできるだけ手前で終わらせ、レスポンスボディは短く保ちます。そして429にはキャッシュヘッダーを付けません。中間キャッシュが429を保存して正常な状態のクライアントに返してしまう事故は実際に起きます。

ここからはクライアント側です。遮断されたクライアントが一定間隔で再試行すると何が起きるかが肝心です。

サーバーが少し揺らいで1000個のクライアントが同時に失敗したとしましょう。全員が1秒後に再試行すれば、1秒後に1000個が同時に到着します。サーバーがまた揺らぎ、また2秒後に再試行すれば、2秒後にまた1000個が同時に到着します。指数バックオフを入れても間隔が決定的なら、再試行は同期した波として残ります。これがサンダリングハードです。

解法はランダム性です。

// やらないでください — すべてのクライアントが同じ瞬間に目を覚まします
const delay = Math.min(cap, base * 2 ** attempt)

// フルジッター — 0と上限のあいだからランダムに引きます
const delay = Math.random() * Math.min(cap, base * 2 ** attempt)

AWSが公開したバックオフの比較実験では、フルジッターは再試行の総回数と全体の完了時間をともに減らしました。上限の半分を固定で敷いて残りだけをランダムにする方式よりも優れていました。直感に反して見えますが、待ち時間を広く散らすほうが衝突を減らすのに効果的だからです。

再試行の実装で一緒に守るべきこともあります。サーバーがRetry-Afterをくれたならその値に従います。最大試行回数と全体の締め切り時間を置いて無限の再試行を防ぎます。429と5xxは再試行しますが、4xxの残りは再試行しません。そして冪等でないリクエストを再試行するときは冪等性キーを一緒に送って重複実行を防がなければなりません。タイムアウトで失敗した決済リクエストをそのまま再試行すると二重に決済されることがあります。

おわりに — アルゴリズムより先に決めること

レートリミットを付けるときにまず決めるべきなのはアルゴリズムではなく、何を守ろうとしているのかです。バックエンドの容量を守るのならコストで重みづけしたトークンバケットが合い、公平な分配が目的ならテナント単位のクォータが合い、総当たりを防ぐのならアカウントとIPを重ねた狭い上限が合います。目的が違えばキーも上限も変わります。

固定ウィンドウはいつでも上限の2倍を通しうるのに対し、カウンター二つのスライディングウィンドウに変える費用はほとんどありません。そのあとに残るのは、クライアントに状態を伝える仕事です。残り回数と再試行の時刻を正確に返してやれば、よくできたクライアントは自分から引き下がります。伝えなければ、全員が同じ瞬間にもう一度ドアを叩きます。