レートリミッティング徹底解説：API・ウェブサービスの可用性と公正性を守る主要アルゴリズムと実装ガイド
エバープレイ編集部レートリミッティングとは
レートリミッティング（rate limiting）は、ある期間内に許可するリクエスト数や処理量を制限する仕組みです。API やウェブサービス、認証システム、ネットワーク機器などで用いられ、過剰な要求によるサービス劣化（DDoS やバースト負荷、誤ったクライアントの暴走）を防ぎ、リソースを公平に分配するための基本技術です。
なぜ必要か
可用性の保護：過剰なアクセスでバックエンドやデータベースが飽和するのを防ぐ。
公正さ：同一サービスを複数利用者で分配することで、特定ユーザによる独占を防止する。
課金・料金管理：API 利用の課金モデルと組み合わせ、プラン毎に利用上限を設ける。
攻撃緩和：ボットや自動化された攻撃のレートを抑えて発見・対応を容易にする。
主要なアルゴリズム
固定ウィンドウ（Fixed Window）：時間窓（例：1分）ごとにカウントする最も単純な方式。実装はカウンターの INCR と有効期限の設定で行われるが、窓の境界で急増が起きる「窓境界問題」がある。
スライディングウィンドウ（Sliding Window）：リクエストの正確な過去 N 秒／分の数を計測する方式。ログベース（タイムスタンプの集合を保持）やスライディングカウント（より細かいサブウィンドウに分割）など実装パターンがあり、境界問題を緩和する。
トークンバケット（Token Bucket）：一定レートでトークンを補充し、リクエストはトークンを消費して許可される。バースト（短時間の集中）を許容しつつ平均レートを制御できる。
リーキーバケット（Leaky Bucket）：入力はキューに入り、一定速度で処理（漏れる）される。出力は一定速度に平滑化されるため、一定のスループットを厳格に保ちたいときに有効。トークンバケットとの違いは、リーキーバケットはバーストを吸収して平滑化する点にある。
同時接続制限（Concurrency Limit）：単位時間あたりではなく、同時実行数を制御する。ファイルダウンロードや重い処理の制御に有効。
HTTP レベルの運用：ステータスとヘッダー
HTTP ステータス：レート超過を示す標準的なステータスコードは 429 Too Many Requests（RFC 6585）。過負荷時に 503 を返す運用もあるが、429 は「ポリシーによる制限」を明確に示す。
Retry-After：クライアントに再試行までの待機時間を伝えるために用いる（秒数または HTTP-date）。429 と共に設定することが多い。
X-RateLimit-* ヘッダー：X-RateLimit-Limit、X-RateLimit-Remaining、X-RateLimit-Reset などは標準化はされていないが広く使われている慣習で、クライアントに残量やリセット時刻を通知するのに有用。
実装の現場パターン
エッジでの制御（CDN / API Gateway / WAF）：Cloudflare、Akamai、AWS API Gateway、GCP Cloud Endpoints、Fastly などでレート制限を行えばバックエンドへの負荷を早期に遮断できる。スケーラビリティとレイテンシの観点で有利。
プロキシ／ロードバランサ（NGINX / Envoy / HAProxy）：NGINX の limit_req、limit_conn、Envoy の rate limit フィルタ等を使ってリクエスト単位や接続単位で制御する。
バックエンドでの分散実装（Redis 等）：分散環境では中央ストア（Redis）を用いることが多い。固定ウィンドウなら INCR + EXPIRE、スライディングウィンドウは sorted set にタイムスタンプを格納して範囲削除・カウント、トークンバケットは Lua スクリプトで原子操作を行うのが一般的。
アプリ内（ローカル）レートリミット：単一インスタンスやローカルキャッシュで簡易的に行う方法。高速だがクラスタ全体での一貫性は確保されない。
設計上の考慮点
識別方法：API キー、ユーザ ID、IP アドレス、クライアント ID、組み合わせ（user+endpoint）など、何を単位に制限するかを定義する。IP のみだと NAT 環境で誤検知が起きる。
バーストと平滑化：トークンバケットでバーストを許容するか、リーキーバケットで平滑化するか、サービス特性に応じて決定する。
優先度と階層化：重要なサービスや内部ユーザ、課金ユーザに優先度を与える（レート上限の差、サーキットブレーカ併用など）。
フェイルオーバーと一貫性：分散環境での同期遅延やキャッシュの不整合に備える。過度に厳格な同期は可用性を犠牲にすることがある。
適切なレスポンス設計：429 と Retry-After、説明を含むエラーボディを返し、クライアントがバックオフできるようにする。
バックオフ戦略と再試行ポリシー
クライアント側では指数バックオフ（exponential backoff）とジッター（jitter）を組み合わせることがベストプラクティスです。固定間隔の再試行は波状反射（thundering herd）を引き起こすため、ランダム性を混ぜて負荷を分散させます。AWS のアーキテクチャブログ等で詳細に議論されています。
運用と観測（Observability）
メトリクス：許可されたリクエスト数、拒否（429）数、レート制限がトリガーされたキーの分布、レイテンシなどを収集する。
ログ：拒否した理由やユーザ、エンドポイントを記録し、異常検知やチューニングに使う。
アラート：拒否率の急増、特定ユーザの異常なアクセスパターンを検出するルールを用意する。
テスト：負荷テスト（wrk、k6、vegeta、Gatling など）で実運用に近い負荷を検証し、閾値やバースト量を調整する。
よくある落とし穴と対策
窓境界問題：固定ウィンドウだと境界でリクエストが集中する。スライディングウィンドウやトークンバケットで回避。
分散での競合・整合性：複数ノードが同一キーにアクセスする場合、原子操作（Redis の Lua）や中心化したレートリミッタを使う。
クロックずれ：サーバ間で時間に依存する実装は NTP で同期し、タイムスタンプベースの実装は注意する。
過剰なブロッキング：制限が厳しすぎると正当なトラフィックを阻害する。SLO をベースに限度を定め、段階的に制限する。
実装例（概念）
固定ウィンドウ（Redis 簡易実装）:
キー: rate:{user_id}:{window_start}
操作: INCR キー → 値が閾値を超えたら 429、最初の増分時に EXPIRE キー window_size 秒
スライディングウィンドウ（Redis sorted set）:
ZADD key current_timestamp unique_id
ZREMRANGEBYSCORE key 0 (current_timestamp - window_size)
COUNT = ZCARD key
COUNT が閾値以下なら許可、超なら拒否
トークンバケット（Redis + Lua）：現在のトークン数と最終補充時刻をキーに原子更新し、利用可否を判定する。原子性を担保するため Lua スクリプトを使うのが一般的です。
まとめ（実務的な推奨）
まずは「何を単位に制限するか（IP/ユーザ/APIキー/エンドポイント）」を定義する。
エッジ（CDN/API Gateway）での初期防御＋バックエンドでの精緻な制御の二層構成が有効。
トークンバケットかスライディングウィンドウを基本に、サービス特性に応じてバーストや優先度をチューニングする。
クライアントには 429 + Retry-After（および残りリミット情報）を返し、指数バックオフ＋ジッターの実施を推奨する。
メトリクスとログで挙動を可視化し、負荷テストで閾値を検証・調整する。
参考文献
- RFC 6585 — Additional HTTP Status Codes (429 Too Many Requests)
- NGINX: limit_req module
- Envoy: Rate Limit
- Redis: Rate limiting patterns
- Cloudflare Rate Limiting
- AWS API Gateway — Throttling
- AWS Blog: Exponential Backoff And Jitter
- k6: Load testing tool (負荷試験の参考)
- Wikipedia: Token bucket
投稿者プロフィール
