レート制限の仕組み - トークンバケット・スライディングウィンドウと 429 の正しい返し方

「APIが乱用されてサーバーが落ちた」「特定ユーザーがリソースを食い潰す」——これらを防ぐのがレート制限（rate limiting）です。仕組みはシンプルに見えて、アルゴリズムの選択や境界の扱いで挙動が大きく変わります。この記事では、主要アルゴリズムと HTTP 429 の正しい返し方を、MDN・IETF を一次ソースに整理します。

レート制限とは・なぜ必要か

レート制限は「一定時間内に送れるリクエスト数を制限する」仕組みです。目的は次のとおり。

• 乱用・DoS の防止
• 公平なリソース配分（一部の利用者の独占を防ぐ）
• バックエンドのコスト・キャパシティ保護
• APIの安定性維持

実施場所は APIゲートウェイ / リバースプロキシ（Nginx・Cloudflare）/ アプリ層 のいずれでも可能。カウント基準は IP・APIキー・認証ユーザー・エンドポイント単位などです。

主要アルゴリズム

• Fixed Window（固定ウィンドウ）: 時間を固定長（例60秒）に区切りカウント。シンプルだが境界バーストの弱点（後述）
• Sliding Window Log: 全リクエストのタイムスタンプを記録し、ウィンドウ外を捨てて数える。最も正確だがメモリを食う
• Sliding Window Counter: 「今のウィンドウ＋前のウィンドウ×残り割合」で近似。キー2個で実用的
• Token Bucket（トークンバケット）: 一定レートでトークンを補充し、1リクエストで1消費。空なら拒否。バーストを容量まで許容しつつ平均レートを守る。多くのAPIが採用
• Leaky Bucket（リーキーバケット）: キューに積み一定レートで流出。トラフィックを平滑化し下流を守る

「多少のバーストは許して平均を守りたい」ならトークンバケット、「出力を一定に均したい」ならリーキーバケット、が基本の使い分けです。

トークンバケットの擬似コード

def is_allowed(key, max_tokens, refill_per_sec, now):
    b = storage.get(key) or {"tokens": max_tokens, "last": now}
    # 経過時間ぶんトークンを補充（容量上限まで）
    b["tokens"] = min(max_tokens, b["tokens"] + (now - b["last"]) * refill_per_sec)
    b["last"] = now
    if b["tokens"] >= 1:
        b["tokens"] -= 1
        storage.set(key, b)
        return True   # 許可
    return False      # 拒否（429）

分散環境では Redis で原子的に

サーバーが複数台あると、各台がローカルにカウンタを持つと実質「台数倍」許してしまいます。Redis 等の共有ストアで数え、操作は原子的にします。

-- KEYS[1]=カウントキー, ARGV[1]=上限, ARGV[2]=ウィンドウ秒
local count = redis.call('INCR', KEYS[1])
if count == 1 then
  redis.call('EXPIRE', KEYS[1], ARGV[2])  -- 初回だけTTLを設定
end
if count > tonumber(ARGV[1]) then
  return 0  -- 拒否
end
return 1    -- 許可

HTTP での返し方: 429 と Retry-After

制限超過は 429 Too Many Requests を返し、Retry-After で「いつ再試行してよいか」を伝えます。

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 50
RateLimit: "permin";r=0;t=50
RateLimit-Policy: "permin";q=50;w=60
 
{"error":"rate_limited","message":"リクエストが多すぎます。しばらく待ってから再試行してください"}

• Retry-After は秒数（例 120）か HTTP-date で指定
• RateLimit / RateLimit-Policy は IETF ドラフト（draft-ietf-httpapi-ratelimit-headers）で標準化が進む新形式。まだRFC化前で、既存APIは X-RateLimit-Limit / X-RateLimit-Remaining / X-RateLimit-Reset の旧来形を広く使っています

ステータスコードの選び方はHTTPステータスコードの実践的な使い分け、API全体の設計はREST API設計と冪等性も参照してください。

クライアント側: 指数バックオフ＋ジッター

429 を受けたクライアントが一斉に同じタイミングでリトライすると、また制限に当たります（thundering herd）。指数バックオフ＋ランダムなジッターでリトライ時刻を散らします。

const wait = Math.min(maxMs, base * 2 ** attempt) * (0.5 + Math.random() * 0.5);

Retry-After がある場合はその値を最優先で尊重します。

よくある落とし穴

• 固定ウィンドウの境界バースト: 毎分100件制限でも、59秒目に100件＋61秒目に100件で2秒間に200件通る。気になるならスライディング系やトークンバケットへ
• X-Forwarded-For の偽装: プロキシ背後でIP制限する際、先頭IPはクライアントが詐称可能。信頼できるプロキシが付与した末尾側を使う（X-Forwarded-For（MDN））
• 非原子的なカウント: 前述の INCR/EXPIRE 分離による永久ブロック
• ジッター無しの一斉リトライ: バックオフにランダム性を必ず入れる
• 粒度設計の失敗: 全エンドポイント横断の単一制限だと、重要APIが軽量APIの消費に巻き込まれる。エンドポイントや操作の重みで分ける

まとめ

• レート制限は乱用防止・公平性・安定性のための土台。IP / APIキー / ユーザー単位で数える
• アルゴリズムはバースト許容なら Token Bucket、平滑化なら Leaky Bucket、精度と実用のバランスは Sliding Window Counter
• 分散環境は Redis で原子的に（INCR＋初回 EXPIRE を Lua で）
• 超過は 429 ＋ Retry-After。RateLimit 系ヘッダは標準化途上（旧来は X-RateLimit-*）
• クライアントは指数バックオフ＋ジッター。固定ウィンドウの境界バーストと X-Forwarded-For 偽装に注意

レート制限は「とりあえず固定ウィンドウ」で始めても、境界バーストや分散の不整合で痛い目を見がちです。用途に合うアルゴリズムと原子的な実装、そして素直な 429——この3点を押さえれば堅牢になります。

参考リンク

• 429 Too Many Requests（MDN）
• Retry-After（MDN）
• RateLimit header fields for HTTP（IETF ドラフト）
• Build Rate Limiters with Redis（Redis 公式）
• REST API設計の基礎と冪等性（当ブログ）
• HTTPステータスコードの実践的な使い分け（当ブログ）