レートリミットのアルゴリズム4種を徹底比較: トークンバケット・リーキーバケット・固定/スライディングウィンドウ【実装と実験】

1. レートリミットはなぜ必要か

API やWebサービスを公開すると、避けて通れないのが「1クライアントあたりのリクエスト数をどこまで許すか」という設計判断である。レートリミット(流量制限)を入れる動機は、大きく3つに整理できる。

• 保護: 特定のクライアント(悪意の有無を問わない)が短時間に大量のリクエストを送ると、CPU・DB接続・下流APIの呼び出し回数といった有限のリソースを食い潰し、他の正常なクライアントの体験を悪化させる。これはDoS攻撃のような明確な悪意がなくても、単なるバグを含むリトライループやバッチ処理の誤爆でも十分に起こり得る。
• 公平性: マルチテナントのSaaSでは、1つのテナントが暴走してリソースを独占すると、他のテナントの処理が遅延する「ノイジーネイバー問題」が起きる。テナントごとに上限を設けることで、公平な配分を担保する。
• 課金・契約の担保: 従量課金のAPI(決済、LLM推論など)では、契約プランに応じた上限を超えるリクエストをそもそも受け付けないことで、意図しないコスト超過や、下流ベンダーとの契約上限違反を防ぐ。

レートリミットに引っかかったリクエストへの応答は、HTTPでは 429 Too Many Requests ステータスコードを使うのが標準である。これは2012年の RFC 6585 で定義され、“The 429 status code indicates that the user has sent too many requests in a given amount of time” と明記されている。RFC 6585はあわせて、いつ再試行してよいかをクライアントに伝える Retry-After ヘッダーを付与することを推奨しており(例: Retry-After: 3600 で1時間後の再試行を促す)、このヘッダーの一般的な仕様自体は RFC 9110のセクション10.2.3 で定義されている。429応答はキャッシュされるべきではない点もRFC 6585に明記されている。

本記事では、この「上限を超えたら429を返す」という判定ロジックそのもの、つまりレートリミットのアルゴリズムを扱う。定番とされる 固定ウィンドウカウンタ・スライディングウィンドウカウンタ・トークンバケット・リーキーバケット の4方式について、classicな定義を確認したうえでPythonで自作実装し、同一のリクエストパターンに対する挙動の違いを実測する。429を受け取ったクライアント側がどう振る舞うべきかについては、指数バックオフを扱ったhttps://yuhi-sa.github.io/posts/20260720_exponential_backoff/1/で別途扱っているので、本記事はサーバー側の判定アルゴリズムに絞って掘り下げる。

2. 固定ウィンドウカウンタ

最も単純な方式が 固定ウィンドウカウンタ(Fixed Window Counter) である。時間を一定幅(例: 1秒や1分)の「窓」に区切り、窓ごとにリクエスト数を数えるカウンタを持つ。カウンタが上限 limit に達するまでは許可し、達したら以降は窓が切り替わるまで拒否する。

def fixed_window(timestamps, limit, window):
    allowed = []
    counts = {}
    for t in timestamps:
        w = int(t // window)          # 現在のリクエストが属する窓番号
        c = counts.get(w, 0)
        if c < limit:
            counts[w] = c + 1
            allowed.append(True)
        else:
            allowed.append(False)
    return allowed

実装はキー(クライアントID等)ごとに「窓番号→カウント」の対応を持つだけなので、メモリ使用量は1キーあたり定数(O(1))で済み、RedisであればINCRとEXPIREだけで実装できる。この単純さが最大の利点だが、窓の境界をまたぐ攻撃に弱い という構造的な欠陥がある。

窓幅を \(W\) 、上限を \(N\) とする。攻撃者が窓 \(k\) の末尾(境界の直前)に \(N\) 件、窓 \(k+1\) の先頭(境界の直後)に \(N\) 件を集中して送ると、固定ウィンドウカウンタはどちらの窓についても「カウント \(N\) /\(N\) 、上限内」としか認識できない。しかし境界をまたぐ任意の幅 \(W\) の区間で見れば、境界に近づくほどこの区間には最大 \(2N\) 件のリクエストが収まってしまう。つまり、窓ごとの上限は守られているのに、実効的な瞬間レートは最大で意図した上限の2倍に達し得る。この問題は Cloudflareのブログ記事 でも、固定ウィンドウ方式は「カウンターが定期的にリセットされるため、正規トラフィックのスパイクが許可されてしまう可能性がある」弱点として指摘されている。この現象は第6節の実験(パターンC)で実測数値として確認する。

3. スライディングウィンドウ(ログ/カウンタ近似)

固定ウィンドウの境界問題を解消する方向性が スライディングウィンドウ(Sliding Window) で、実装の厳密さによって大きく2種類に分かれる。

スライディングウィンドウログは、リクエストが来るたびにタイムスタンプそのものを記録しておき、判定時に「現在時刻 - 窓幅」より古いタイムスタンプを捨てて、残った件数を上限と比較する厳密な方式である。判定は正確だが、窓内に来たリクエスト数だけタイムスタンプを保持する必要があり、メモリ使用量がトラフィック量に比例(O(N))して増えるのが弱点で、高頻度・大量クライアントの環境ではRedisのSorted Set等を使っても無視できないコストになる。

from collections import deque

def sliding_window_log(timestamps, limit, window):
    allowed = []
    log = deque()  # 許可したリクエストのタイムスタンプ
    for t in timestamps:
        while log and log[0] <= t - window:
            log.popleft()
        if len(log) < limit:
            log.append(t)
            allowed.append(True)
        else:
            allowed.append(False)
    return allowed

これに対し スライディングウィンドウカウンタ は、直近2つの固定ウィンドウのカウント値(前の窓のカウントcount_prev、現在の窓のカウントcount_curr)という たった2つの数値 だけを保持し、前の窓のトラフィックが窓内に一様に分布していたと仮定して、現在時刻における実効カウントを線形補間で近似する。

def sliding_window_counter(timestamps, limit, window):
    allowed = []
    counts = {}
    for t in timestamps:
        w = int(t // window)
        elapsed = t - w * window
        prev = counts.get(w - 1, 0)
        curr = counts.get(w, 0)
        est = prev * (1 - elapsed / window) + curr
        if est < limit:
            counts[w] = curr + 1
            allowed.append(True)
        else:
            allowed.append(False)
    return allowed

これはまさに Cloudflareのブログ記事「counting things, a lot of different things」 で紹介されているアプローチで、同記事は利点として「メモリ使用量が小さい: カウンターあたり2つの数値のみ」「計算がシンプル: 1つのGETコマンドと基本的な計算で済む」ことを挙げており、実際memcacheのGET/SET/INCRだけで実装できるとしている。厳密なログ方式と違い近似である点には注意が必要で、前の窓のトラフィックが実際には偏っていた場合(例えば前の窓の末尾に集中していた場合)は推定値が実態とややズレるが、実務上は固定ウィンドウの「最大2倍」問題を大きく緩和できるだけの精度が出ることを第6節で確認する。

4. トークンバケット

トークンバケット(Token Bucket) は、容量 b のバケットに、一定の補充レート r でトークンが注ぎ込まれ続けるというモデルである。リクエストが来るたびにバケットからトークンを1個消費し、消費できれば許可、トークンが枯渇していれば拒否する。バケットが満杯の間はそれ以上トークンは増えない(捨てられる)。

• 補充レート \(r\) : 長期的に許容する平均リクエストレートを決める。
• バースト容量 \(b\) : アイドル状態が続いてバケットが満タンになっていれば、その分だけ一時的に \(r\) を超える瞬間的なバーストをまとめて通すことができる、いわば「貯金」の上限を決める。

def token_bucket(timestamps, rate, capacity):
    allowed = []
    tokens = capacity
    last = timestamps[0] if timestamps else 0.0
    for t in timestamps:
        tokens = min(capacity, tokens + (t - last) * rate)  # 経過時間分だけ補充(上限capacityで頭打ち)
        last = t
        if tokens >= 1.0:
            tokens -= 1.0
            allowed.append(True)
        else:
            allowed.append(False)
    return allowed, tokens

トークンバケットは実務での採用例が非常に多い。決済サービスのStripeは自社のAPIレート制限にトークンバケットを採用しており、平常時のリクエストレートを一定に保ちつつ、フラッシュセールのような瞬間的なトラフィック急増(バースト)を許容できる設計だと説明している( Stripe API rate limitersに関する解説記事 、 Stripe公式ブログ )。\(r\) と \(b\) を独立に調整できるため、「平均レートは厳しく絞りたいが、正常なクライアントの短時間のジッタは殺したくない」という要件に強い。

5. リーキーバケット

リーキーバケット(Leaky Bucket) はトークンバケットとしばしば対比されるが、発想は逆に近い。バケットに水(リクエスト)が不定期に注がれる一方、バケットの底には一定レートの穴が空いていて、常に一定の速度で水が漏れ出る(=リクエストが処理される)。バケットの容量を超えた分の水は溢れて捨てられる(拒否される)。トークンバケットが「許可(受理)そのもの」を制御するのに対し、リーキーバケットは 「実際に処理される速度」そのものを平滑化する 点が本質的に異なる。

nginxのngx_http_limit_req_moduleはまさにこの"leaky bucket" methodでレート制限を実装しており、 公式ドキュメント によれば設定は以下のようになる。

limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;

server {
    location /search/ {
        limit_req zone=one burst=5;  # 平均1r/s、最大バースト5をキューイングで吸収
    }
}

rateが漏れ出る速度(平滑化後の平均処理レート)、burstがキューに溜め込める最大件数を表す。burstを超えたリクエストはデフォルトで503エラーとして破棄される。nodelayオプションを付けると、バースト分は遅延させずに即座に処理するが、その分は依然としてリクエスト数としてカウントされる、という制御も可能である。

自作実装では、実際にリクエストをキューに並べてイベント駆動でシミュレーションする代わりに、仮想キューレベル方式(GCRA: Generic Cell Rate Algorithmとして知られる実装と等価)を使う。「現在キューに積まれている(処理待ちの)仮想的な量」をlevelとして持ち、時間経過に応じてリークさせるだけで、キュー内の各リクエストを個別にシミュレーションせずに同じ挙動を再現できる。

def leaky_bucket(timestamps, rate, capacity, init_level=0.0):
    allowed = []
    depart_times = []       # 各リクエストが実際に処理される(退出する)予定時刻
    level = init_level
    last = timestamps[0] if timestamps else 0.0
    for t in timestamps:
        level = max(0.0, level - (t - last) * rate)  # 経過時間分だけリーク
        last = t
        if level < capacity:
            level += 1.0
            allowed.append(True)
            depart_times.append(t + level / rate)     # このリクエストの処理完了予定時刻
        else:
            allowed.append(False)
            depart_times.append(None)
    return allowed, depart_times, level

「受理(キューに積めるか)」と「実際に処理される時刻」が分離されている点が実装上の肝で、この性質が第6節のバースト実験で顕著な違いとして現れる。

6. 実験: 同一トラフィックに4方式を適用する

まず4方式の仕組みを図で整理しておく。

以降の実験では、窓ベースの2方式(固定ウィンドウ・スライディングウィンドウカウンタ)は上限 limit=10 (窓幅1秒=10req/s相当)、トークンバケットは補充レート r=10 token/s・容量 b=20、リーキーバケットは処理レート rate=10 req/s・キュー容量 20 に統一した。乱数シードはすべて 42 に固定している。実験用の全コードはrate_limit_sim.pyとしてまとめてあり、以下の数値はすべてこのスクリプトを実際に実行して得た実測値である。

パターンA: 一様なリクエスト流(平常時)

まず、平均6req/s(上限10req/sの60%)のポアソン過程で30秒間のリクエスト列を生成し(random.Random(42).expovariate(6.0))、4方式に同時に流す。生成された総リクエスト数は184件だった。

平均レートが上限の60%であっても、ポアソン過程には偶然の偏り(一瞬だけ到着が密集する区間)が生じるため、窓ベースの2方式はその瞬間だけ上限に張り付き、6件を拒否した。一方、トークンバケットとリーキーバケットはb=20・容量20という平常時のジッタを十分に吸収できるバッファを持つため、全リクエストを許可している。固定ウィンドウとスライディングウィンドウカウンタの許可数が完全に一致(178件)している点も興味深く、前の窓の実績(count_prev)がゼロに近い平常時には、両者はほぼ同じ判定になることが実測から確認できる。平常時の挙動としては、4方式とも「概ね同等」と言ってよい結果である。

パターンB: バースト(瞬間集中)

次に、5秒間アイドル状態(トークンバケットは満タンのb=20、リーキーバケットはキューが空の状態)にしたあと、30件のリクエストを20ミリ秒の間に一気に送り込み、その後は再びアイドルにするパターンを流した。

窓ベースの2方式は、窓の上限である10件で機械的に頭打ちになる。トークンバケットは容量b=20まで貯めたトークンを使い切って20件を即座に通過させ、それ以降はトークン切れで拒否している。リーキーバケットは、容量20のキューに対して継続的にリークが起きている影響でわずかに多い21件を受理しているが、ここで重要なのは受理された21件が「いつ実際に処理されるか」である。実測では、最初の受理から最後の受理までは20ミリ秒しかかかっていないにもかかわらず、それらの実際の処理完了時刻は5.100秒〜7.100秒の2.000秒間に分散していた。これはリーク速度10req/sに対し21件を処理するのにちょうど2秒強かかる計算と整合しており、「受理は即座でも出力は一定レートに均される」というリーキーバケットの性質を定量的に裏付けている。トークンバケットがバースト許容量まで一気に通すのに対し、リーキーバケットは受け入れた分をなだらかに吐き出すという、両者の質的な違いがこの実験でくっきりと可視化された。

パターンC: ウィンドウ境界攻撃

最後に、第2節で述べた固定ウィンドウの境界問題を実測する。窓0〜2秒(3つの窓)は上限ちょうどの10req/窓を均等に配置した定常状態のトラフィックを流し、続く窓3([3,4)秒)は本来均等配置されるはずの10件をすべて末尾100ミリ秒(3.90〜3.99秒)に集中させ、窓4([4,5)秒)も同様に10件を先頭100ミリ秒(4.00〜4.09秒)に集中させた。これは「攻撃者が窓の境界を狙って直前・直後にリクエストを集中させる」典型的なシナリオである。トークンバケット・リーキーバケットも同じ定常トラフィックのもとで運用されてきた前提(補充とほぼ均衡した状態)から、同じ集中バーストに晒している。

境界をまたぐ190ミリ秒の区間(3.90秒〜4.10秒、攻撃リクエスト計20件)内で許可された件数は次の通りだった。

固定ウィンドウを窓ごとに見ると、窓3は10/10、窓4も10/10と、どちらの窓も単体では「上限内」に見える。しかし境界をまたぐ190ミリ秒という短い区間には合計20件が通過しており、これはまさに第2節で述べた「最大2倍」問題が理論値とぴったり一致する形で実測されたことになる。一方でスライディングウィンドウカウンタは、窓4の時点では窓3の実績(count_prev=10)がまだ高い重みを持つため推定カウントが上限に張り付き、窓4のリクエストの大半(9/10件)を拒否した結果、攻撃区間全体では11/20に抑えられている。トークンバケットも同様の理由(直前の定常トラフィックでトークンをほぼ使い切っており、余剰の貯金がない)で12/20に抑えられた。リーキーバケットは境界という概念自体を持たないため20件すべてを受理しているが、パターンBと同様に実処理は2秒程度に平滑化されるため、下流システムが瞬間的に20req/190msの負荷を受けるわけではない。「窓」という区切りに起因する脆弱性は、時間を連続的に扱うトークンバケット・リーキーバケットには原理的に存在せず、窓ベースの方式の中でもスライディングウィンドウカウンタは固定ウィンドウよりも明確にこの攻撃に強い、ということが実測数値によって裏付けられた。

7. 分散環境でのレートリミット

ここまでの実装は1プロセス内のメモリ上でカウンタを保持する前提だったが、実際のサービスはロードバランサー配下に複数のアプリケーションサーバーを並べて動かすのが普通である。各サーバーがそれぞれ独立にインメモリでカウンタを持つと、同一クライアントのリクエストがサーバー間で分散された時点で、実効的な上限がサーバー台数倍に緩んでしまう。 Redis公式ドキュメントのレートリミッター解説 も「ロードバランサー配下ではローカルなプロセス単位のカウンタは機能しない。同一クライアントが別インスタンスを叩くことで制限を回避できてしまう」と明確に指摘しており、複数インスタンスに共通のカウンタを持たせるための中央集権的なストアが必要になるとしている。Redisはこの用途に広く使われており、理由は次の3点に整理できる。

1. サブミリ秒のレイテンシ: リクエストの同期経路上でチェックを挟んでも体感できる遅延を生まない。
2. 原子的な操作: INCRとEXPIREを組み合わせれば固定ウィンドウカウンタを実装できるが、この2つのコマンドの間に別プロセスの読み取りが割り込むと、TTLが設定されずカウンタが永遠に残ってしまうレースコンディションが起こり得る。これを避けるため、INCRの戻り値が1(=そのキーの最初のリクエスト)であった場合にのみEXPIREを呼ぶという手順を単一のLuaスクリプトにまとめてEVALで実行するのが定石で、Redisの 公式ドキュメント も「Luaスクリプティングは読み取り・判定・更新のサイクルを原子的に保つため、並行したリクエストがトークンを二重に消費したりカウンタ更新を失ったりすることがない」と説明している。トークンバケットをRedisで実装する場合も同様に、「トークン数」と「最終補充時刻」をハッシュに保持し、経過時間からの補充量計算・容量での頭打ち・消費判定までを1本のLuaスクリプトに閉じ込めることで、ネットワークラウンドトリップを1回に抑えつつ原子性を確保できる。
3. TTLによる自動クリーンアップ: 固定ウィンドウのキーは窓が過ぎれば不要になるため、EXPIREで自動的に消してもらえば明示的な掃除処理が要らない。

複数ノードにまたがる場合の誤差にも注意が要る。単一のRedisインスタンス(またはクラスタの単一シャード)に全ノードが問い合わせる構成であれば判定自体は厳密だが、アプリケーションサーバーとRedis間のネットワーク往復レイテンシの分だけ、極めて高い同時実行数のバーストに対しては瞬間的に上限を超えるリクエストが通過し得る(チェックと更新の間にわずかなラグがあるため)。また地理的に分散したマルチリージョン構成で、リージョンごとに独立したRedisを持たせる(同期コストを避けるため)場合は、そもそも各リージョンのカウンタが分離されているため、グローバルな合計としては意図した上限より緩くなる。 Redis公式ドキュメント はこのトレードオフに対し、CRDTベースで結果整合性を持つActive-Active方式のレプリケーションを紹介している。同様の課題に対し、 Cloudflareのブログ記事 は数百万ドメイン規模のエッジで動くレートリミッターとして、すべてのリクエストで同期的にグローバルカウンタを更新するのではなく、ローカルな概算カウントと非同期の集計を組み合わせることでレイテンシへの影響を最小化しつつ十分な精度を確保するアプローチを取っている。分散環境では「完全に厳密なカウント」と「低レイテンシ」はトレードオフの関係にあり、要件に応じてどこまで近似を許容するかを設計判断として決める必要がある。

8. 選定ガイド

実験結果を踏まえ、要件別にどの方式を選ぶべきかを整理する。

「まず何を守りたいか」から逆算するのが実務的である。下流システムへの負荷を一定に均したいならリーキーバケット、平均レートは絞りつつ正常な利用のジッタは殺したくないならトークンバケット、実装をとにかく単純にしたく境界攻撃のリスクも許容できるなら固定ウィンドウ、固定ウィンドウ並みの軽さで境界問題だけは緩和したいならスライディングウィンドウカウンタ、という順で検討するとよい。

まとめ

固定ウィンドウカウンタ・スライディングウィンドウカウンタ・トークンバケット・リーキーバケットの4方式を自作実装し、同一のリクエスト列に適用する実験を行った。平常時(パターンA)は4方式とも概ね同等の挙動を示す一方、バースト(パターンB)ではトークンバケットが許容量まで即座に通す・リーキーバケットが受理後の処理を平滑化するという質的な違いが、そして境界攻撃(パターンC)では固定ウィンドウが窓ごとには上限内でありながら実効的に上限の2倍(20/20)を通してしまう一方、スライディングウィンドウカウンタがこれを11/20まで抑制するという実測結果が得られた。理論上「言われている」欠陥や特性を、実際に手を動かして数値で確認できたことが今回の一番の収穫である。

FAQ

Q1. トークンバケットとリーキーバケットの違いは?

両者とも平均レートを制御する点は同じだが、制御する対象が異なる。トークンバケットは「許可(受理)」そのものを制御し、バースト許容量bまでは複数のリクエストを瞬時にまとめて通す。リーキーバケットは「実際の処理(出力)」を一定レートに均す。今回のパターンB実験でも、30件のバーストに対しトークンバケットは瞬時に20件を許可して打ち止めになったのに対し、リーキーバケットは21件を受理しつつ実処理を2秒かけて平滑化するという違いが定量的に確認できた。

Q2. レート制限に引っかかったクライアントはどうすべきか?

429を受け取った直後に即座にリトライするのは避け、Retry-Afterヘッダーの指定に従うか、指数バックオフとジッタを組み合わせて再試行間隔を徐々に広げていくのが定石である。具体的な実装や実測はhttps://yuhi-sa.github.io/posts/20260720_exponential_backoff/1/にまとめている。

Q3. 固定ウィンドウはなぜダメなのか?

実装が最も簡単で、平常時のトラフィックであれば大きな問題にはならない。しかし第6節パターンCの実測で示した通り、窓の境界を狙って直前・直後にリクエストを集中させる攻撃に対しては、190ミリ秒という短時間に本来の上限(10件)の2倍にあたる20件が通過してしまう(固定ウィンドウ20/20 vs スライディングウィンドウカウンタ11/20)。境界を突かれるリスクを許容できないなら、スライディングウィンドウカウンタ以上の方式を選ぶべきである。

Q4. レート値(r, b, 窓サイズなど)はどう決めるか?

まず保護対象(自サーバーのCPU余力、下流DBの処理能力、外部APIとの契約上限など)の実測キャパシティから出発する。持続的に処理できるスループットを補充レートr(または固定ウィンドウの上限)として設定し、正常なトラフィックのジッタを吸収できるだけのバースト許容量bをトークンバケットなら追加する。厳しすぎる設定は正規ユーザーを弾き、緩すぎる設定は保護にならないため、本記事のパターンAのように実際のトラフィックパターンを4方式に流し込んで拒否率を観測しながら調整するのが実務的である。

関連記事

• データベースのコネクションプールサイズを待ち行列理論(M/M/c)でモデル化する - こちらは「同時にいくつのリクエストを捌けるようにするか」という容量設計の話で、本記事の「単位時間あたり何件まで受け付けるか」というレートの話とは補完関係にある。
• HPAのPID制御 - 負荷に応じてリソースの量そのものを動的に調整するアプローチで、レートリミットが「入口で弾く」静的な防御であるのに対し、こちらは「後手に回ってでも供給量を増やす」動的な対応にあたる。

他の分野の定番書は エンジニアにおすすめの技術書10選 にまとめている。