Valkey/Redisで実装するRate Limiting戦略：アルゴリズム別の比較と実装例

概要

Rate Limiting のアルゴリズム紹介と Valkey/Redis での実装例。「Rate Limit は難しい問題」という認識のとおり、方式ごとにトレードオフがある。

詳細

主なアルゴリズム

1. Fixed Window Counter（固定ウィンドウ）

時間枠: 0:00〜0:59、1:00〜1:59 などの固定区間ごとにカウント

実装（Redis）:
  INCR rate:user123:202605031200   # 分単位のキー
  EXPIRE rate:user123:202605031200 60

問題: ウィンドウの境界で2倍のリクエストが通る（バースト問題）
  → 0:59 に 100回、1:00 に 100回 = 1秒間で 200回通過してしまう

2. Sliding Window Log（スライディングウィンドウログ）

実装（Redis Sorted Set）:
  ZADD rate:user123 {timestamp} {request_id}
  ZREMRANGEBYSCORE rate:user123 0 {now - window_size}
  ZCARD rate:user123   # 現在の件数

利点: 精確なレートリミット、バースト問題なし
欠点: 全リクエストのタイムスタンプを保存 → メモリ消費大

3. Sliding Window Counter（スライディングウィンドウカウンター）

前の区間のカウントを重み付けして近似計算する方法:

current_rate = prev_count * (1 - elapsed/window) + curr_count

利点: 固定ウィンドウより精確、ログより省メモリ
欠点: 近似値（厳密ではない）

4. Token Bucket（トークンバケット）

バケツにトークンが一定速度で補充される。
リクエストのたびにトークンを消費。トークンがなければ拒否。

実装（Lua スクリプトでアトミックに）:
  local tokens = redis.call('GET', key) or capacity
  if tokens > 0 then
    redis.call('SET', key, tokens - 1)
    redis.call('EXPIRE', key, ttl)
    return 1  -- 許可
  else
    return 0  -- 拒否
  end

利点: バーストを一定程度許容する（貯まったトークンを一気に使える）
用途: API の利用量制限（GitHub API など）

5. Leaky Bucket（リーキーバケット）

一定速度でリクエストを処理する（超過分はキューかドロップ）。
Token Bucket と逆のイメージ: 出力レートを一定に保つ。

利点: 一定のレートでバックエンドに負荷をかけられる
用途: 送信レートの平滑化（スパイクを均す）

Valkey/Redis での実装選択

シンプルに使う    → Fixed Window（INCR + EXPIRE）
精確に制御したい  → Sliding Window Log（Sorted Set）
省メモリで精確に  → Sliding Window Counter
バースト許容      → Token Bucket（Lua スクリプト）
レート均一化      → Leaky Bucket

なぜ重要か / いつ使うか

• API の Rate Limiting を実装するとき
• DDoS 対策や不正利用の制限を設計するとき
• 面接で「Rate Limiting の実装」を聞かれたとき