分散レートリミットとグローバル制限の難しさ

グローバル制限の本質：分散カウントは合意問題に化ける

レートリミットは単純に見えます。「このAPIキーは毎秒1000リクエストまで」。単一サーバーなら、メモリ上のカウンタを1つ持ち、窓ごとにリセットすればよい。難しさは 複数ノードが同じ1つの上限を共有する 瞬間に立ち上がります。リクエストはロードバランサで複数のゲートウェイに分散され（/devops/load-balancer-algorithms/）、各ノードは自分が受けた分しか知りません。いま全体で何リクエスト消費したか という単一の真実を、分散したノード群でどう共有するかが核心です。

ここで問題は分散システムの一般問題に化けます。「グローバルカウンタの現在値」という共有状態を複数ノードが同時に読み書きする以上、厳密にやれば各更新を直列化する必要があり、これは事実上の合意・直列化のコストを背負います。正確さ（上限を1も超えない） と レイテンシ／スループット（毎リクエストの判定が速い） は真っ向から対立し、分散レートリミットの設計とは「この対立をどこで妥協するか」を決める作業です。

集中カウンタ：正確だがレイテンシと競合が壁

最も素直な解は 集中カウンタ です。Redis のような共有ストアにキーごとのカウンタを置き、全ノードが毎リクエストでそれをアトミックにインクリメントし、上限と比較します。Redis の INCR は単一スレッドで直列に処理されるので、競合状態なしに正確なカウントが得られます。トークンバケットを Lua スクリプトで実装すれば、残トークンの確認と減算を1往復・アトミックに行えます。

集中カウンタ（トークンバケット）の判定（擬似コード）
リクエスト到着:
    残量, 最終補充時刻 = store.get(key)         # 1往復目（または取得込みのLua）
    経過 = now - 最終補充時刻
    残量 = min(容量, 残量 + 経過 * 補充レート)    # 時間経過ぶん補充
    if 残量 >= 1:
        残量 -= 1
        store.set(key, 残量, now)               # アトミックに確定
        return 許可
    return 拒否

正確さは申し分ありません。問題は3つです。第一に レイテンシ。全リクエストが共有ストアへの往復を1回背負い、ストアが別ゾーンにあれば数ミリ秒が毎回乗ります。第二に スループットの上限。あるキーが極端に人気だと、そのキーへの更新が1点に集中する ホットキー となり、Redis の単一スレッド処理が直列ボトルネックになります。シャーディングしてもキー単位の更新は分割できません。第三に 可用性と障害結合。共有ストアが落ちると全ノードの判定が止まる。フェイルオープン（落ちたら通す）にすれば制限が無効化され、フェイルクローズ（落ちたら拒否）にすれば全体が落ちる、というジレンマを抱えます。

ローカル割当：速いが偏りで利用率が落ちる

レイテンシと競合を避ける逆方向の解が ローカル割当（local quota） です。グローバル上限をノード数で割り、各ノードに固定の割当を配ります。毎秒1000・ノード10台なら各100。各ノードは自分のローカルカウンタだけを見て判定するので、共有ストアへの往復がゼロになり、判定はインメモリで完結して極めて速く、ストア障害にも影響されません。

代償は 利用率の低下 です。トラフィックが各ノードへ均等に来る保証はありません。ロードバランサのハッシュ偏り、特定クライアントの粘着接続、ノードごとの能力差で、配分は必ず偏ります。あるノードは割当100を使い切って正当なリクエストを拒否する一方、別ノードは20しか使っておらず80が遊ぶ。全体ではまだ余裕があるのに、局所的な枯渇で拒否が起きる のがローカル割当の構造的弱点です。

偏りによる過小利用の例（グローバル上限 1000 / 10ノード、各割当 100）
ノードA: 到着 150 → 100許可・50拒否（割当を超過）
ノードB: 到着  20 →  20許可（80が遊休）
...
全体: 到着合計は 1000 未満なのに、Aで拒否が発生し利用率が落ちる

割当を粗く固定するほどこの無駄は大きくなります。さらに窓の境界問題もあります。固定窓（毎秒0でリセット）だと窓の変わり目に瞬間的なバーストが上限の2倍まで通りうる。トークンバケットやスライディングウィンドウで境界を滑らかにする必要がありますが、ローカルに閉じている限り 他ノードの消費を知らない という根本は変わりません。

ローカル割当＋定期同期：配分を動的に補正する

ローカル割当の速さを保ちつつ偏りを緩和するのが、ローカル割当＋定期同期 です。各ノードはローカルカウンタで高速に判定しつつ、一定間隔（例：100ミリ秒〜1秒）で自分の消費量を共有ストアやピアにブロードキャストし、全体の消費を概算します。その推定に基づき、自分の割当を動的に調整します。よく使うリクエストの多いノードへ配分を寄せ、遊んでいるノードから割当を回収する、という再分配を周期的に行うわけです。

定期同期型（各ノード、間隔 T ごと）
毎リクエスト（高速パス）:
    ローカル割当内なら許可、超えたら拒否   # ストア往復なし

間隔 T ごと（低速パス、バックグラウンド）:
    自ノードの直近消費を共有ストアへ書く
    全ノードの消費合計を読む
    残り全体予算 = グローバル上限 - 合計消費
    新ローカル割当 = 残り予算 を需要比で再配分

この構造は集中カウンタの正確さとローカル割当の速さの中間に位置します。共有ストアへのアクセスは 毎リクエストではなく間隔 T に1回 に減り、ホットキー競合とレイテンシが桁で下がります。各ノードのブロードキャストを全ノードに直接送らず、ゴシップで伝播させれば（/devops/gossip-protocol/）、ノード数が増えても同期コストが破綻しません。

問題は 間隔 T のぶんだけ全ノードの認識が古い ことです。同期と同期の間、各ノードは T 前のグローバル状態を見て判定します。この遅れが2種類の誤差を生みます。

• 超過（overshoot）：複数ノードが「まだ全体に余裕がある」と古い情報で同時に許可し、合計が一瞬上限を超える。T が長いほど、トラフィックが急増するほど大きくなる。
• 過小利用（undershoot）：再分配が追いつかず、需要が移ったのに割当が前の配分のままで、新たに混み始めたノードが余裕のあるうちに拒否する。

T を短くすれば誤差は減りますが同期トラフィックとストア負荷が増え、長くすれば軽くなるが誤差が増える。T は許容誤差と同期コストのトレードオフ であり、ここでも「どこまでのズレを許すか」が設計を決めます。

確率的・近似アルゴリズム：厳密さを捨てて誤差を有界化する

「上限を1も超えない」を諦め、有界な誤差の中で速く判定する のが近似アルゴリズムです。厳密な一意カウントを放棄する代わりに、レイテンシ・スループット・可用性を稼ぎます。

スライディングウィンドウ近似 は、固定窓のバースト問題と厳密スライディングウィンドウのコストの中間を取ります。厳密スライディングウィンドウは全リクエストのタイムスタンプを保持する必要があり高コストですが、近似版は「直前の窓のカウント」と「現在の窓のカウント」を、現在窓の経過割合で加重平均して推定値とします。

スライディングウィンドウ近似（現在窓の 25% を経過した時点）
推定カウント = 直前窓のカウント * (1 - 0.25) + 現在窓のカウント
            = 直前窓 * 0.75 + 現在窓
直前のトラフィックが一様だったと仮定して案分する近似

カウンタ2つで済むため軽量で、固定窓のような境界での倍バーストを抑えます。トラフィックが窓内で一様という仮定が外れると誤差が出ますが、その誤差は有界で、実務の許容範囲に収まることが多い。

確率的減算（probabilistic counting） は、毎リクエストではなく確率 p でのみカウンタを更新し、観測値を 1/p 倍して実数を推定します。共有ストアへの書き込み回数が p 倍に減り、ホットキー競合を大幅に下げられます。代償は推定の分散で、サンプリング誤差がそのまま制限精度の揺らぎになります。

CRDTカウンタ は、各ノードが自分のカウントをローカルに増やし、ノード間でマージしても矛盾しない構造（増加のみの G-Counter なら各ノードの値を要素ごとに最大／合計でマージ）を使います。中央の直列化なしに各ノードが独立更新でき、いずれ収束する 結果整合（eventual consistency） を提供します。ただし収束は瞬時ではなく、収束前の各ノードはグローバル合計を過小評価しがちで、その間は超過方向にズレる。これは整合性モデルの一般論（/devops/consistency-models/）どおり、強整合を捨てて可用性とレイテンシを得た代償です。

誤差の見積もり：超過の上限を設計時に押さえる

近似や同期を採るなら、最悪どれだけ超過しうるか を設計時に見積もるのが上級者の作法です。定期同期型のおおまかな超過上限は、同期間隔 T と全ノードの合計到着レートで決まります。各ノードが古い情報で許可しうる量は、最悪 「T のあいだに全ノードが上限ぶん許可してしまう量」 で押さえられます。ノード数 N、同期間隔 T、グローバル上限レート R に対し、超過は概ね「N と T が大きいほど、また同期遅延が大きいほど増える」方向に効きます。

定期同期型の超過オーダー（直感）
最悪超過 ≈ 各ノードが同期遅延ぶん独立に走った許可の合算
        → 同期間隔 T を短く・ノード数 N の認識を新鮮に保つほど縮む
許容超過から逆算して T と再分配頻度を決める

この見積もりにより「上限1000・許容超過5%なら T はどれだけ短くすべきか」を逆算できます。さらに 時刻のズレ が誤差を増幅する点に注意が要ります。各ノードの窓境界がクロックスキューでずれると、窓のリセットタイミングが食い違い、境界付近で余計な超過や取りこぼしが出ます。物理時刻に頼らず、論理的な順序や単調増加クロックで窓を管理する設計が安全です（/devops/logical-clocks/）。

まとめ

• 分散レートリミットの本質は 「全体でいくつ消費したか」という単一の真実を複数ノードで共有する ことにあり、厳密にやると合意・直列化のコストを背負う。正確さとレイテンシ／可用性は対立する。
• 集中カウンタ は正確だが、毎リクエストのストア往復レイテンシ、ホットキー競合、単一障害点という3つの壁を持つ。
• ローカル割当 は速くて障害に強いが、トラフィックの偏りで一部ノードが先に枯渇し、全体に余裕があるのに拒否が起きて利用率が落ちる。
• ローカル割当＋定期同期 は両者の中間で、共有アクセスを間隔 T に1回へ減らす。代償は T ぶんの認識遅れによる超過と過小利用で、T は許容誤差と同期コストのトレードオフ。
• 近似アルゴリズム（スライディングウィンドウ近似、確率的減算、CRDTカウンタ）は厳密さを捨てて有界誤差で速く判定する。最悪超過を設計時に見積もり、目的から定めた許容誤差に収まることを確認するのが正攻法。