先に要点
- レートリミット の代表アルゴリズムは Token Bucket 」 「 Leaky Bucket 」 「 Fixed Window Counter 」 「 Sliding Window の 4 つ。それぞれ バーストを許すか 」 「 公平性をどう取るか 」 「 実装難度 」 「 分散環境での同期コスト が違う。
- 用途別の選び方: API バックエンドの一般的なエンドポイント = Token Bucket または Sliding Window Log 」 「 ストリーム処理 / レート整流 = Leaky Bucket 」 「 単純な実装で十分 = Fixed Window 」 「 公平性を厳密に保つ = Sliding Window Counter / Log。
- 分散環境では Redis などの中央ストアで状態を共有 するのが定番。「複数の API サーバが独自にカウントすると合計超過する」 ので、「カウンタを Redis にまとめる + Lua スクリプトでアトミック更新 」 が標準パターン。
- Fixed Window の罠: 「境界(1 分の切れ目)で 2 倍のリクエストが許される」 ことがある。「23:59:55 に 100 + 00:00:05 に 100 = 10 秒で 200 リクエスト」。Sliding Window はこれを避けるための補正。
- 「 自前実装しない 」 が現代の正解。API Gateway 」 「 AWS WAF 」 「 nginx 」 「 Envoy 」 「 Cloudflare Rate Limiting など、インフラ層に既製のレートリミットがある。自前で書くのは 「特殊な要件があるとき」 だけに限る。
「API に レートリミット を入れたい」 と決めた瞬間、「どのアルゴリズムを使うか」 という問題に当たります。`一見どれも 「1 分に N 回まで」 で同じに見える」 が、バースト挙動 」 「 公平性 」 「 分散環境での同期コスト がまるで違います。
ざっくり言うと、レートリミットの代表は Token Bucket / Leaky Bucket / Fixed Window / Sliding Window の 4 つ。それぞれ得意分野が違うので、「守りたい性質」 に合わせて選ぶのが本筋です。実務では AWS WAF や API Gateway のような既製品に任せるのが現代の標準ですが、どのアルゴリズムが裏で動いているか を理解しておくと、設定の最適化やデバッグで効きます。
この記事では、4 アルゴリズムの仕組み・特性・使い分けを実務目線で整理します。Rate Limit を 「何のために入れるか」 については API レートリミット も併読してください。
まず 4 アルゴリズムを並べる
各アルゴリズムの特性を一覧で整理します。「バーストを許すか」 と 「公平性」 が大きな違い。
| アルゴリズム | バースト | 公平性 | 実装難度 | 典型用途 |
|---|---|---|---|---|
| Token Bucket | ○ 許す(バケットが空でなければ即時消費) | △ バースト分は不公平 | 易 | API バックエンド、「普段は静か、たまにバースト」 のユーザー向け |
| Leaky Bucket | × 平坦化(常に一定レートで処理) | ◎ 厳密にレート一定 | 易 | ストリーム整流、ダウンストリーム保護 |
| Fixed Window Counter | ○(境界で 2 倍許される問題あり) | △ 境界問題 | 最易 | シンプルな実装で十分なケース、軽い保護 |
| Sliding Window Log / Counter | ○ 滑らかに制御 | ◎ | 中〜難(メモリ消費にも注意) | 公平性を厳密に保ちたい API、有料サービスの SLA |
「境界問題」 と 「バースト」 の扱いが、選び方の中心になる軸です。
Token Bucket — バーストを許す柔軟な定番
最も広く使われるアルゴリズム。「バケットにトークンを一定速度で追加し、リクエストごとに 1 つ消費」 する。
仕組み
「 容量 C のバケットに、毎秒 R 個のトークンを補充」。リクエストが来るたびに 1 トークン消費。バケットが空ならリクエストを拒否 / 待たせる。「バケット満杯で N トークン溜まっている状態 → 一気に N リクエスト処理可能(バースト許容)」 が特徴。
Leaky Bucket — 一定レートで処理する整流
Token Bucket と名前が似ているが、「常に一定レートで処理する」 ところが本質的に違う。
仕組み
「 容量 C のキューに、リクエストを入れる(投入)。底から一定レート R で漏れていく(処理)」。キューが満杯になったら新規リクエストを拒否。処理側は 常に R req/sec の一定レート。
整流が本質
「 バックエンドが秒間 100 リクエスト処理が限界 」 という時、入口で 1000 来ても出口は 100 に整流される。「ダウンストリームの保護 」 が本来の用途。バーストを許さないので、「どんな入力にもダウンストリームは安定 」 が約束される。
バーストを許さない弱み
「 1000 リクエストが瞬間的に来ても、出口は 100/sec のまま 」。「まとめて処理して欲しい」 ユーザーには冷たい。公平性が高い反面、UX には不利になりがち。
使うべき場面
「 データベース / メッセージキュー / 外部 API への投げ込み整流 」 「 ストリーム処理 」 「 帯域制御 」。「ダウンストリームの限界を超えさせない 」 のが目的なら Leaky Bucket。「公開 API のユーザー向け」 には硬すぎることが多い。
Fixed Window Counter — 最も単純、境界問題に注意
実装が最も単純。「時間窓(1 分など)ごとにカウンタを持ち、上限を超えたら拒否」 する。
仕組み
「 1 分窓で 100 リクエストまで 」 と決め、「windowKey = floor(timestamp / 60) 」 のような時間ブロックでカウンタを保持。1 分経つとカウンタリセット。シンプルで Redis INCR 一発で済む ので実装が楽。
境界問題
「 23:59:55 〜 00:00:00 で 100 リクエスト送り、00:00:00 〜 00:00:05 でも 100 リクエスト送る 」 と、10 秒間で 200 リクエスト処理 されてしまう。「実質 2 倍のレート 」 を許してしまうのが弱点。
使うべき場面
「 厳密でなくていい場面 」 「 大量のキーに対して低コストで実装したい 」 「 攻撃ではなく単純な過剰アクセス防止 」。「境界問題が許容できる粒度 」 なら最も実装コストが低い。
改善: Sliding Window への移行
「 境界問題が許容できなくなったら Sliding Window Counter へ 」 が定番ルート。「実装コスト中、境界問題が消える 」 のメリットがあります。
Sliding Window — 境界問題を解決する 2 種類
「 Sliding Window Log 」 と 「Sliding Window Counter 」 の 2 種類があり、「境界問題を解決しつつ、それぞれ別のトレードオフ」 がある。
Sliding Window Log
` 全てのリクエストのタイムスタンプを保持し、「現在から N 秒前まで」 のログを数える」 方式。
仕組み
` ユーザーごとにリクエストタイムスタンプの配列を持ち、リクエスト時に 「現在 - 60 秒 」 より古いログを削除 → 残ったログ数を上限と比較 」。境界問題が完全に解決 される。
メモリコスト
「 全リクエストのタイムスタンプを保持 」 するので、リクエスト数に比例してメモリ消費。「1 ユーザーあたり 60 秒で 1000 req 」 なら 1000 件のタイムスタンプを保持。「大量ユーザー / 高頻度アクセス 」 では Redis メモリが厳しくなる。
使うべき場面
「 公平性を厳密に守りたい 」 「 ユーザー数と上限が小〜中規模 」 「 メモリコストを許容できる 」。「SLA を厳密に保証する有料 API 」 で使われる。
実装
Redis の Sorted Set でタイムスタンプを保管し、「ZREMRANGEBYSCORE 」 で期限切れを削除 → 「ZCARD 」 でカウント、というパターンが定番。
Sliding Window Counter
「 Fixed Window のカウンタを 2 つ保持し、現在窓と前窓の重み付け平均で算出 」 する近似アルゴリズム。
仕組み
「 現在窓のカウント + 前窓のカウント × (1 - 現在窓経過率) 」 で 「スライディング上のリクエスト数」 を推定。境界問題を解決しつつ、メモリは Fixed Window と同じ。
メモリと精度のバランス
「 2 つのカウンタだけで済む = メモリコスト最小 」 一方、「完全な精度ではなく近似 」(分布が均一前提)。実用上は 多くの API で十分な精度 が出る。
使うべき場面
「 公平性も性能も両立したい 」 「 大量ユーザー対応 」 「 メモリコストを抑えたい 」。現代の API レートリミットの推奨方式 と言える。Cloudflare Rate Limiting や多くの API Gateway がこのパターンを採用。
実装
` Redis のキーを 「
アルゴリズム選択の判断フロー
「 どれを選ぶか」 を素早く決めるフロー。
このフローを通せば、「どのアルゴリズムを実装すべきか」 がほぼ一意に決まります。
分散環境での実装パターン
複数の API サーバが裏にいる場合、「カウンタをどう同期するか」 が重要なテーマ。
「Redis 中央集約 + Lua スクリプト + Fail Open」 が、多くの現代 API での標準パターンです。
既製レートリミット ── 自前で書く前に確認
「自前実装する前に、既製のレートリミットで足りないか」 を確認するのが現代の作法。
| サービス | 主な機能 | 典型用途 |
|---|---|---|
| AWS WAF Rate-based Rules | 「 同一 IP から N req/5min 」 のような単純なレート制御 + Bot 対策 | CloudFront / ALB / API Gateway の前段で攻撃緩和 |
| API Gateway Throttling / Usage Plan | 「 API キー単位の Throttling 」 「 Burst / Steady 制御 」 | SaaS の料金プラン別レート / 認証ユーザー単位の制御 |
| Cloudflare Rate Limiting | 「 柔軟なルール(IP / Cookie / Header 単位)」 | 公開 API / Web サイトの保護 |
| nginx limit_req / limit_conn | 「 モジュール内蔵のレートリミット(Leaky Bucket ベース)」 | nginx をリバースプロキシに使う構成 |
| Envoy local_ratelimit / global_ratelimit | 「 サイドカーで動くレート制御 」 | サービスメッシュ / Istio 環境 |
「まず既製品を試す → どうしても足りないところだけ自前」 が、「車輪の再発明」 を避ける現代的なアプローチです。
レートリミット実装でハマりやすい点
実装で踏みやすい落とし穴を整理します。
何で識別するか
「 IP 単位 」 「 ユーザー ID 単位 」 「 API キー単位 」 のどれで識別するかが 設計の核。「プロキシ経由で IP が同一」 になるユーザーを誤って制限する事故が起きる。「認証済みユーザーはユーザー ID、未認証は IP 」 の組み合わせが現実的。
分散時のクロック同期
「 複数サーバの時計がずれていると、Sliding Window の境界計算がおかしくなる 」。NTP で時刻同期を必ず維持 し、「サーバ時刻ではなく Redis 側の時刻を基準に 」 する実装も一案。
429 レスポンスの設計
「 429 Too Many Requests 」 を返すときに Retry-After ヘッダ 」 「 RateLimit-Limit / Remaining / Reset ヘッダ を必ず含める。「いつ再試行すべきか」 をクライアントに明示すると、「闇雲なリトライで負荷増」 を防げる。
レートリミットに関するよくある質問
Q. Token Bucket と Leaky Bucket、結局どっちを使えばいい?
A. 公開 API のユーザー保護なら Token Bucket、内部ストリーム整流なら Leaky Bucket。「バーストを許すか」 が判断の核。「UX を考えると Token Bucket が好まれる 」 一方、「ダウンストリームの限界を超えさせないなら Leaky Bucket 」 が安全。
Q. Fixed Window で十分なケースってありますか?
A. あります。「雑な保護で十分 」 「 ユーザーあたりリクエスト数が小さい(数〜数十/window)」 のような場合、境界問題が許容できることが多い。「シンプルなぶん実装と運用が楽 」 という利点も。「境界問題が許容できないと分かった時点で Sliding Window へ移行 」 でも良い。
Q. Sliding Window Counter は本当に近似で大丈夫?
A. ほとんどのケースで十分。「分布が均一 」 を仮定する近似ですが、「実際の API トラフィックは概ね均一に近い 」 ので、誤差は数 % 程度。「厳密な SLA 保証が必要」 でなければ問題なし。Sliding Window Log の半分以下のメモリで動く 利点が大きい。
Q. レートリミットの上限値はどう決める?
A. 観測値の数倍を初期値に、攻撃や負荷試験で調整。「通常ユーザーの最大値(95 パーセンタイル)」 を観測し、その 3〜5 倍 を初期上限に。「実際に攻撃を受けたときの値」 や 「負荷試験のピーク値」 で調整するのが現実的。
Q. Retry-After ヘッダの値はどう決める?
A. 次にトークンが補充される時刻 / 窓がリセットされる時刻 を秒で返す。Token Bucket なら 「(消費したトークン - 現在のトークン) / 補充レート 」、Sliding Window なら 「次の窓のリセットまで 」 を計算。クライアントが指数バックオフで暴走するのを防ぐ 効果がある。
Q. 認証前のリクエストはどう識別する?
A. IP 単位が基本ですが、「プロキシ経由で IP が集約される」 ユーザーへの巻き添えに注意。IP + User-Agent + パスの組み合わせ や 「Cookie で発行した一時 ID 」 など、「本人特定の難しい識別子を組み合わせる」 のが現実的。
Q. レートリミットを掛けたら正常ユーザーが弾かれました
A. 上限値が低すぎる 」 「 識別単位が広すぎる(企業プロキシで巻き添え)」 「 設計上の盲点(画像 / CSS の連続リクエスト) のいずれかが原因。「429 のログを集計 → どの IP / どのパスで弾かれているか確認 」 で、「本来弾きたかったのか、巻き添えなのか」 を判断。「巻き添えなら上限を上げる or 識別単位を細かくする 」 で対処。
まとめ
レートリミットの代表アルゴリズムは Token Bucket / Leaky Bucket / Fixed Window / Sliding Window の 4 つで、「バーストを許すか」 と 「公平性」 で選び分けます。「API Gateway / WAF / Cloudflare / nginx 」 などインフラ層の既製品で済むなら、「自前で書く前にまず試す 」 のが現代の作法です。
「Token Bucket / Sliding Window Counter」 が現代の API レートリミットの主流。「Fail Open / Fail Closed の方針」 「 識別単位の設計」 「 429 Retry-After ヘッダの返却」 を抑えれば、「本番で破綻しないレートリミット」 が組めます。
参考リンク
- Cloudflare: Rate Limiting
- AWS Docs: API Gateway Throttling
- AWS Docs: AWS WAF Rate-Based Rules
- nginx Docs: Rate Limiting with NGINX
- Envoy Docs: Rate Limiting