レートリミッタの設計

レートリミッタは「単位時間あたりの許可リクエスト数を超えたものを拒否する」だけの一見単純な部品ですが、分散環境での正確なカウント共有とレース回避、そして超過時の作法まで含めると、設計判断の宝庫になります。ここではシステム設計面接の解答フォーマットに沿って、要件定義から具体的な数値見積もり、内部アルゴリズム、スケール時のトレードオフまでを順に組み立てます。

要件と規模の見積もり

まず機能要件と非機能要件を分けます。機能要件は「あるキー（ユーザーID・APIキー・IPアドレスなど）ごとに、決められた閾値を超えるリクエストを拒否する」「超過時は明確に429を返し、いつ回復するかをクライアントに伝える」「ルールは動的に変更・追加できる」の3点です。非機能要件が本質で、(1) 判定の追加レイテンシは小さいこと（目安として p99 で 1ms 前後、ネットワーク越しでも数ms以内）、(2) リミッタ自身が単一障害点にならないこと、(3) 分散環境でカウントが正確、あるいは既知の誤差内に収まること、(4) メモリ消費が有界であること、を満たす必要があります。

規模感をフェルミ推定で押さえます。全社APIゲートウェイが日次1億リクエストを捌くとします。1日は約86,400秒なので平均は 1e8 / 86400、おおよそ 1,160 QPS。ピークは平均の5倍と見積もって 約6,000 QPS とします。リクエストのたびにレートリミッタが1回判定するので、リミッタも同じ 6,000 QPS 級を処理します。

ストレージも見積もります。カウンタ方式なら状態は「キー＋整数カウント＋TTL」で、1エントリおおよそ100バイト。アクティブキーがユニークユーザー100万人ぶんだとすると 1e6 * 100B で 約100MB。これは単一のRedisインスタンスのメモリに余裕で収まる桁で、「分散カウンタ共有にインメモリストアが妥当」という後段の判断根拠になります。一方でスライディングウィンドウlog方式（後述）は、キーごとにウィンドウ内の全リクエストのタイムスタンプを保持するため、ピーク時に1キーが毎秒100リクエストを送ると60秒窓で6,000要素、これがアクティブキーぶん積み上がり、メモリが桁で増える点が効いてきます。

帯域は軽微です。判定リクエストとその応答は数十バイト規模で、6,000 QPS × 数百バイトでも数MB/s に届かず、ボトルネックは帯域ではなく判定のレイテンシとカウンタ更新の競合だと分かります。この見積もりが「Redisのアトミック操作でレースを潰す」設計へ導きます。

大枠の設計

外部インタフェースはシンプルに保ちます。中核は1つの述語関数です。

allow(key, cost=1) -> { allowed: bool, remaining: int, reset_at: epoch_ms }

key は制限単位（ユーザーID・APIキー・IP・エンドポイント名、あるいはそれらの組み合わせ）、cost は重い操作を複数トークン消費として扱うための重みです。呼び出し側はブール値を見て通すか429を返すかを決め、remaining と reset_at を応答ヘッダに転記します。

データモデルはアルゴリズムに依存しますが、トークンバケットを例に取ると、キーごとに保持する状態は次の2つだけです。

tokens        : 現在の残トークン数（浮動小数可）
last_refill_ms : 最後に補充を計算した時刻（ミリ秒）

全体構成は次の流れです。リクエストがゲートウェイに到達すると、ゲートウェイは key を抽出し、共有カウンタストア（Redis）に対してアトミックな判定を1回実行します。許可なら上流のサービスへ転送し、拒否なら即座に 429 を返します。ローカルにインメモリのL1キャッシュを置き、「明らかに枯渇済みのキー」を短時間だけローカルで弾いてRedisアクセス自体を減らす最適化も一般的です。ルール（キーあたりの上限・窓幅）は設定ストアから配布し、ホットリロードします。

アルゴリズムの選択が設計の心臓部です。主要4方式を比較します。

判断根拠はこうです。固定ウィンドウは最も安いものの、窓の境界問題（後述）で瞬間的に上限の約2倍を通してしまいます。スライディングログは完全に正確ですが、メモリが窓内リクエスト数に比例して膨らみ、規模見積もりで見た通りコストが桁で効きます。多くの実務では、バースト許容が欲しければトークンバケット、境界問題を安く抑えたければスライディングウィンドウカウンタが既定解になります。以降はこの2つを深掘りします。

主要コンポーネントの深掘り

トークンバケットの原理

トークンバケットは「容量 capacity のバケツに、毎秒 refill_rate 個のトークンが補充され、リクエストは1個（または cost 個）のトークンを消費し、空なら拒否する」モデルです。肝は、補充をタイマーで定期実行しない点です。キーごとにスレッドやタイマーを持てば状態爆発します。代わりに、判定のたびに経過時間から補充量を遅延計算（lazy refill）します。

now      = 現在時刻ms
elapsed  = now - last_refill_ms
tokens   = min(capacity, tokens + elapsed/1000 * refill_rate)  # 経過ぶん補充
last_refill_ms = now
if tokens >= cost:
    tokens = tokens - cost
    allow
else:
    deny

この方式なら状態はキーあたり2値で済み、アクセスされたキーだけが計算されます。capacity がバースト許容量、refill_rate が定常レートを独立に決めるので、「定常は毎秒10件だが、貯めておけば瞬間的に50件まで許す」といった要求を自然に表現できます。リーキーバケットは出力側を固定レートにする双対で、入力のバーストを吸収して下流へ一定速度で流したいとき（キューやワーカーの保護）に選びます。両者は「バーストを通したいか、均したいか」で選び分けます。

分散環境でのカウンタ共有

本当の難所はここです。ゲートウェイは水平スケールして複数インスタンスが並走します。各インスタンスがローカルにカウンタを持つと、キーの状態がインスタンス間で分裂し、N台なら実効的に上限がN倍に緩みます。したがってカウンタは共有ストアに集約します。低レイテンシと豊富なアトミック操作から、実務ではRedisが定番です。1キーの状態は必ず1シャードに乗るようキー設計し、シャード分散にはコンシステントハッシュ法の考え方が効きます。

ここで正確さと可用性のトレードオフが顔を出します。カウンタを厳密に1箇所へ集約すればカウントは正確ですが、そのストアが落ちれば判定できません。地理分散したストアで強整合を取ろうとすると、CAP定理が示す通り、分断時に一貫性と可用性のどちらかを諦めることになります。多くのレートリミッタは可用性を優先し、ストア障害時は「開放（fail-open、通してしまう）」か「局所的な近似で凌ぐ」設計を採ります。過剰に絞って正規ユーザーを巻き込むより、多少緩めて可用性を保つ方が実害が小さいという判断です。

レース回避 — Luaによるアトミック実行

分散カウンタの最大の罠が read-modify-write のレースです。素朴に「Redisから tokens をGET → アプリ側で補充と減算を計算 → SET」とすると、2つのゲートウェイが同時に同じ tokens を読み、両方が「残っている」と判断して両方通し、上限を超えます。これはチェックと更新が分離しているために起きる古典的な競合です。

解決は判定ロジック全体を1つのアトミック単位にすることです。Redisは単一スレッドでコマンドを処理し、EVAL で渡したLuaスクリプトを他コマンドに割り込まれず一括実行するため、read・compute・write をスクリプト内に閉じ込めれば、その間に別の判定が入り込めません。トークンバケットのアトミック判定は次の形になります。

-- KEYS[1]=状態キー  ARGV: now, capacity, refill_rate, cost, ttl
local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1])
local ts     = tonumber(state[2])
local now    = tonumber(ARGV[1])
local cap    = tonumber(ARGV[2])
local rate   = tonumber(ARGV[3])
local cost   = tonumber(ARGV[4])
local ttl    = tonumber(ARGV[5])

if tokens == nil then
  tokens = cap; ts = now          -- 初回はフル
end
-- 経過ぶんを補充（上限は容量）
local delta = math.max(0, now - ts) / 1000 * rate
tokens = math.min(cap, tokens + delta)

local allowed = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
end
redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], ttl)   -- TTLで自動回収
return { allowed, tokens }

固定ウィンドウのように「窓内で件数を数えるだけ」なら、Luaを使わず INCR（返り値が新カウント、1が初回）＋EXPIRE の2コマンドでも原子性は担保できます。ただし「INCRの結果を見てから上限判定し、超過なら戻す」ような分岐が絡むならLuaに寄せるのが安全です。いずれの方式でも、キーには必ずTTLを設定します。窓幅ぶんの余裕を持たせたTTLで、非アクティブなキーの状態が自動で失効し、メモリが有界に保たれます。これが規模見積もりで置いた「100MBに収まる」前提を実際に守る仕組みです。

スライディングウィンドウカウンタ

固定ウィンドウの境界問題を安く緩和するのがこの方式です。現在の窓のカウント cur と直前の窓のカウント prev を保持し、現在時刻が現窓のどこにいるかの割合 p（0から1）で加重した推定値 estimate = prev * (1 - p) + cur を使います。窓ぶんの全タイムスタンプを持つログ方式と違い、状態はキーあたり2カウンタと軽く、それでいて境界での急なリセットが平滑化されるため、実務では正確さとコストのバランス点としてよく選ばれます。

ボトルネックとトレードオフ

横にスクロール

固定ウィンドウの境界問題を数値で押さえます。上限が「1分あたり100件」だとします。あるクライアントが 00:00:59 に100件を送り切り、直後の 00:01:00 に窓がリセットされてまた100件送ると、実時間わずか約1秒の間に200件が通ります。窓が0起点でリセットされる限りこの2倍バーストは避けられず、下流のキャパシティ設計を狂わせます。スライディングウィンドウはこの尖りを均すために存在します。

単一ストアがボトルネック・単一障害点になる問題があります。全判定が1つのRedisを叩けば、そのスループットとレイテンシが全体の天井になり、落ちれば判定不能です。対策は多層です。(1) ゲートウェイ各インスタンスにローカルL1を置き、「枯渇済み」キーを短時間ローカルで弾いてストアアクセスを間引く。(2) キー空間でRedisをシャーディングし負荷を分散する（1キー1シャードは維持）。(3) ストア障害時の挙動を fail-open（通す）か fail-closed（止める）か事前に決める。課金や不正防止が絡む経路は fail-closed 寄り、可用性最優先の一般APIは fail-open 寄り、と用途で判断します。

厳密な集中管理か、緩い分散近似かという上位のトレードオフもあります。グローバルに完全正確なカウントを追うと、判定ごとにネットワーク往復が要り、レイテンシと単一障害点リスクを負います。代替案として、各ノードにグローバル上限を按分したローカル予算を配り、ノード内はローカル判定で高速に捌き、消費実績だけを非同期でゲートウェイ間に集約して予算を再配分する方式があります。厳密さは落ちますが、ホットパスからネットワーク往復を除去できスケールに強くなります。この「予算を配って後で突き合わせる」発想は、L4ロードバランサの内部設計におけるコネクション分配の考え方とも通じます。

配置の階層でも役割が分かれます。クライアント側（SDK）はサーバーの RateLimit-Remaining を見て先回りで送信を絞り、無駄な429往復を減らします（ただし自衛にはならず、悪意あるクライアントは無視できる）。ゲートウェイ／APIゲートウェイが全体防御の主戦場で、全テナント横断の上限とDDoS的な濫用をここで断ちます。個別サービスは自分のキャパシティに合わせた局所的な上限を持ち、内部呼び出しや特定の重いエンドポイントを保護します。3層は排他ではなく重ねるもので、外側ほど広く粗く、内側ほど狭く具体的に効かせます。

最後に429応答の作法です。超過時は 429 Too Many Requests を返し、いつ再試行してよいかを機械可読で伝えます。

より広い分散システムの設計原則はデータベース、ネットワーク、DevOpsの各トピックも参照してください。