レート制限の実装アルゴリズム｜6方式を同じ条件で動かして比較

レート制限（Rate Limiting）とは、一定時間あたりに受け付けるリクエスト数に上限を設け、超えた分を拒否または待たせる仕組みです。 APIやWebサーバーを、急なアクセス集中や機械的な連続アクセスから守り、利用者どうしで公平に資源を分け合うために使います。

この記事では、代表的な6つのアルゴリズム（固定ウィンドウ、スライディングログ、スライディングウィンドウカウンタ、トークンバケット、リーキーバケット、GCRA）をPythonで実装し、窓の境界をまたぐバーストを含む同じリクエスト列を流して、許可数の違いを表で比較します。さらに、Redis＋Luaで複数サーバーから使えるトークンバケットを作り、原子的でない実装との差を実測し、nginxの limit_req の burst / nodelay / delay の挙動をローカルで実際に叩いた結果も載せます。記事中の「実行結果」はすべてこの記事のために手元で動かした出力です（Python 3.11、Redis 6.2.14、nginx 1.24.0）。

レート制限アルゴリズムの早見表

レート制限の基本：何を・どの単位で・どう返すか

アルゴリズムを選ぶ前に「キー」「上限」「超えたときの動作」の3つを決めると、実装がぶれません。

以降の検証では、上限を「10秒あたり10回（平均1回/秒）」にそろえて6方式を比べます。

6つのアルゴリズムをPythonで実装する

6方式とも allow(now) が True/False を返すだけの同じ形にしておくと、比較もテストもしやすくなります。 時刻を引数で渡すのは、テストで時間を自由に進めるためです。

"""6つのレート制限アルゴリズム（上限: 10秒あたり10回 = 平均1回/秒）"""
import math
from collections import deque

LIMIT = 10      # 回
WINDOW = 10.0   # 秒


class FixedWindow:
    def __init__(self):
        self.win = None
        self.count = 0

    def allow(self, now):
        w = math.floor(now / WINDOW)
        if w != self.win:
            self.win, self.count = w, 0
        if self.count < LIMIT:
            self.count += 1
            return True
        return False


class SlidingLog:
    def __init__(self):
        self.log = deque()

    def allow(self, now):
        while self.log and self.log[0] <= now - WINDOW:
            self.log.popleft()
        if len(self.log) < LIMIT:
            self.log.append(now)
            return True
        return False


class SlidingWindowCounter:
    def __init__(self):
        self.win = None
        self.cur = 0
        self.prev = 0

    def allow(self, now):
        w = math.floor(now / WINDOW)
        if w != self.win:
            self.prev = self.cur if self.win == w - 1 else 0
            self.cur, self.win = 0, w
        elapsed = (now - w * WINDOW) / WINDOW          # 現ウィンドウの経過割合
        estimated = self.prev * (1 - elapsed) + self.cur
        if estimated < LIMIT:
            self.cur += 1
            return True
        return False


class TokenBucket:
    def __init__(self, capacity=LIMIT, rate=LIMIT / WINDOW):
        self.cap, self.rate = capacity, rate
        self.tokens, self.ts = capacity, 0.0

    def allow(self, now):
        self.tokens = min(self.cap, self.tokens + (now - self.ts) * self.rate)
        self.ts = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False


class LeakyBucketQueue:
    """キュー型: 容量まで受け付け、一定間隔(1秒)で1件ずつ処理する"""
    def __init__(self, capacity=LIMIT, interval=WINDOW / LIMIT):
        self.cap, self.interval = capacity, interval
        self.next_free = 0.0     # 次に処理できる時刻
        self.done_at = []        # 受け付けた各リクエストの処理時刻

    def allow(self, now):
        queued = sum(1 for t in self.done_at if t > now)
        if queued >= self.cap:
            return False
        start = max(now, self.next_free)
        self.next_free = start + self.interval
        self.done_at.append(start)
        return True


class GCRA:
    """T=放出間隔, tau=許容バースト幅。TAT(理論到着時刻)1つだけを保存"""
    def __init__(self, T=WINDOW / LIMIT, burst=LIMIT):
        self.T = T
        self.tau = T * (burst - 1)
        self.tat = 0.0

    def allow(self, now):
        tat = max(self.tat, now)
        if tat - now > self.tau:
            return False
        self.tat = tat + self.T
        return True

各方式のしくみを短く

• 固定ウィンドウ：時刻を10秒単位で区切り、区切りごとにカウントを0に戻します。実装は最も簡単ですが、区切りの直前と直後に集中すると、短時間に上限の2倍まで通ります。
• スライディングログ：許可した時刻をすべて記録し、「今から10秒前」より古いものを捨てて数えます。正確ですが、キーごとに最大10件（上限の数）の時刻を持つため、上限が大きいとメモリを使います。
• スライディングウィンドウカウンタ：「前の窓のカウント ×（1 − 現在の窓の経過割合）＋ 現在の窓のカウント」で直近10秒の回数を推定します。カウント2つで済み、スライディングログに近い精度が出ます。
• トークンバケット：容量10のバケツに毎秒1個トークンがたまり、1リクエストで1個使います。たまっていれば一気に使えるので、平均を守りつつ短いバーストを許します。
• リーキーバケット：受け付けたリクエストをキュー（待ち行列）に入れ、一定間隔で1件ずつ処理します。下流に流れる速度は常に一定になり、代わりに待ち時間が生じます。 なお、キューを使わず「たまった水の量」だけを計算する「メーター型」もあり、こちらは許可/拒否の結果がトークンバケットと同じになります。
• GCRA（Generic Cell Rate Algorithm）：「次のリクエストが来てよい理論上の時刻（TAT）」を1つだけ保存し、今の時刻と比べて判定します。状態が時刻1つだけなので、Redisなどに置くときに省メモリで高速です。 結果はトークンバケットと同等になります（下の実測で確認します）。

同じリクエスト列で6方式を比較（実行結果）

同じリクエスト列でも、方式によって許可数ははっきり変わります。 次の2つのシナリオをシミュレーションしました。

• シナリオA：静かな状態から、窓の境界（10秒）をまたいで 9.9秒に10件、10.1秒に10件（0.2秒で20件）
• シナリオB：0〜7.5秒に0.5秒間隔で16件（平均の2倍の速さ）→ 9.9秒と10.1秒に10件ずつ → 15〜19.5秒に0.5秒間隔で10件（計46件）

シナリオA：窓の境界をまたぐバースト（実行結果）

固定ウィンドウだけが、0.2秒で上限の2倍（20件）を通しました。 10秒の区切りでカウントが0に戻るためです。スライディングウィンドウカウンタは近似なので1件多く通っています（10.1秒時点の推定値が 10×0.99＝9.9 で、上限10未満だったため）。リーキーバケットの1件は、0.2秒の間に1件分処理が進んでキューに空きができたぶんです。

シナリオB：時間帯ごとの許可数（実行結果）

リーキーバケットは受け付けた30件を0秒から29秒まで1秒間隔で処理し、処理時刻で見た「任意の10秒の最大」は10件、最大の待ち時間は10秒でした。

この表から読み取れるポイントは次のとおりです。

• 「10秒で10回」を厳密に守るのはスライディングログとスライディングウィンドウカウンタです。 任意の10秒で最大10件に収まりました。
• トークンバケットとGCRAは、許可/拒否の推移が完全に一致しました。 両者は同じ制限を別の表現で計算していることが確認できます。
• トークンバケット・GCRAは「平均1回/秒＋最大10件のバースト」という意味の制限です。 満タンの10件を使い切った後も毎秒1件ずつ補充されるので、任意の10秒で最大19件まで通ります。これは仕様どおりの挙動で、「10秒で10回」を厳密に守りたいならスライディング系、「平均速度」を守りたいならトークンバケット系を選ぶとよい、という判断材料になります。
• リーキーバケットは拒否が少ない代わりに、待ち時間が伸びます。 利用者を待たせてよい内部処理（メール送信キューなど）に向いています。

方式選びの判断表

Redis＋Luaで分散対応のトークンバケットを作る

サーバーが複数台あるときは、カウンタをRedisなどの共有ストアに置き、「読む→計算→書く」を1つのLuaスクリプトで原子的に実行します。 Redisはスクリプトの実行中にほかのコマンドを割り込ませないため、同時アクセスでもトークンの数え間違いが起きません。

import redis

r = redis.Redis(port=7061, decode_responses=True)

# KEYS[1]=バケットのキー  ARGV[1]=容量  ARGV[2]=毎秒の補充数
TOKEN_BUCKET_LUA = """
local cap  = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local t    = redis.call('TIME')                 -- Redisサーバーの時計を使う
local now  = tonumber(t[1]) + tonumber(t[2]) / 1000000

local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or cap
local ts     = tonumber(b[2]) or now

tokens = math.min(cap, tokens + (now - ts) * rate)
local allowed = 0
local retry_after = 0
if tokens >= 1 then
  tokens = tokens - 1
  allowed = 1
else
  retry_after = math.ceil((1 - tokens) / rate)
end
redis.call('HSET', KEYS[1], 'tokens', tostring(tokens), 'ts', tostring(now))
redis.call('EXPIRE', KEYS[1], math.ceil(cap / rate) * 2)
return {allowed, math.floor(tokens), retry_after}
"""
take = r.register_script(TOKEN_BUCKET_LUA)

allowed, remaining, retry_after = take(keys=["tb:user:42"], args=[10, 1])

実装のポイントは3つです。

• 時刻はRedisの TIME で取る：アプリサーバーごとの時計のずれに影響されません（Redis 5以降はスクリプトの効果を複製する方式が既定のため、TIME を使ったうえで書き込めます）。
• EXPIRE で使われなくなったキーを自動で消す：満タンに戻るまでの時間より長めにしておけば、動作に影響しません。
• 戻り値に残数と再試行までの秒数を含める：そのままレスポンスヘッダー（後述）に使えます。

実行結果：単発の動作

容量10・毎秒1個で12回連続で呼び、最後の3回と、2.1秒待った後の1回を表示しました（(許可, 残数, 再試行秒)）。

連続12回: [(1, 0, 0), (0, 0, 1), (0, 0, 1)]
2.1秒後: (1, 1, 0)

10回目で残数0、11・12回目は拒否され「1秒後に再試行」、2.1秒後には2個補充されて許可されています。

実行結果：同時アクセスで原子的な実装と比べる

50スレッドから同時に4回ずつ（計200リクエスト）、容量10のバケットを叩きました。比較用に、HGETALLで読んでPythonで計算しHSETで書く「非原子的」な版も用意しています（通信や処理の隙間を想定し、読んでから書くまでに1ミリ秒の待ちを入れた版と、入れない版）。

Luaで原子的に実行した版は、毎回ちょうど容量どおり10件だけを許可しました。 別コマンドの版は、複数のスレッドが同じ「残り10個」を読んでから書き戻すため、上限をほぼ素通りしています。分散環境のレート制限では、判定と更新を1つの原子的な操作にまとめることが最重要ポイントです。

nginx limit_req の burst / nodelay を実際に叩く

nginxの limit_req はリーキーバケット方式で、burst と nodelay / delay の組み合わせで「待たせるか・すぐ通すか」が変わります。 公式ドキュメントの説明を、実際に10件同時リクエストで確かめました。

user root;   # 検証環境の都合（静的ファイルの読み取り権限のため）
worker_processes 1;
events { worker_connections 256; }
http {
  limit_req_zone $binary_remote_addr zone=z_plain:1m   rate=2r/s;
  limit_req_zone $binary_remote_addr zone=z_burst:1m   rate=2r/s;
  limit_req_zone $binary_remote_addr zone=z_nodelay:1m rate=2r/s;
  limit_req_zone $binary_remote_addr zone=z_delay:1m   rate=2r/s;
  limit_req_status 429;          # 既定は503
  server {
    listen 127.0.0.1:7060;
    root html;
    location /plain   { limit_req zone=z_plain;                   try_files /ok.txt =404; }
    location /burst   { limit_req zone=z_burst burst=5;           try_files /ok.txt =404; }
    location /nodelay { limit_req zone=z_nodelay burst=5 nodelay; try_files /ok.txt =404; }
    location /delay   { limit_req zone=z_delay burst=5 delay=2;   try_files /ok.txt =404; }
    error_page 429 @too_many;
    location @too_many {
      add_header Retry-After 1 always;
      return 429 "too many requests\n";
    }
  }
}

実行結果：10件同時に送ったとき

（同じテストを2回実行し、2回とも同じ結果でした）

• burstなし：rate=2r/s は内部的に「0.5秒に1件」として扱われるため、同時に来ると1件だけ通り、残りは即429です。
• burst=5：超過分を5件までキューで待たせ、0.5秒間隔で順に処理します。最後の1件は2.5秒待ちました。
• burst=5 nodelay：5件ぶんの枠を待たせずにすぐ処理します。ただし枠の回復は0.5秒に1件のままです。
• burst=5 delay=2（nginx 1.15.7以降）：最初の数件は即時、それを超えた分は待たせる2段階の動きになります。

拒否時の error.log には次のように記録されました（遅延されたリクエストは warn レベル）。

[error] ... limiting requests, excess: 5.996 by zone "z_delay", client: 127.0.0.1, ...
[warn]  ... delaying request, excess: 4.996, by zone "z_delay", client: 127.0.0.1, ...

検証でつまずいた点：return だけのlocationでは制限がかからない

最初は各locationを return 200 "ok"; で書いたところ、10件すべてが200になりました。 return はrewriteフェーズで応答を返し終えるため、その後のフェーズで動く limit_req に到達しません。動作確認では静的ファイルやプロキシ先を返すlocationで試すと、実際の挙動を確認できます。

HTTP 429・Retry-After・RateLimitヘッダー

制限にかかったときは、HTTP 429 Too Many Requests と、いつ再試行してよいかを示す Retry-After を返すのが基本です。

最新ドラフトでの書き方の例は次のとおりです。以前の版にあった RateLimit-Limit / RateLimit-Remaining / RateLimit-Reset の3つに分かれた形から、2つのヘッダーにまとめられています。

HTTP/1.1 429 Too Many Requests
Retry-After: 1
RateLimit-Policy: "default";q=10;w=10
RateLimit: "default";r=0;t=1
Content-Type: application/problem+json

{"type": "about:blank", "title": "Too Many Requests", "status": 429,
 "detail": "10秒あたり10回までです。1秒後に再試行してください。"}

q は上限、w は窓の秒数、r は残り、t は回復までの秒数です。ドラフトは改訂が続いているため、採用する場合はRetry-Afterを必ず併記し、クライアントがRetry-Afterだけでも正しく動けるようにしておくと安心です。

クライアント側の作法

クライアントは429を受けたらRetry-Afterの秒数だけ待ち、ヘッダーがなければ指数バックオフ（1秒、2秒、4秒…と待ち時間を倍にする）＋ジッター（ランダムなゆらぎ）で再試行します。 ゆらぎを入れると、多数のクライアントが同じ瞬間に再試行して再び制限にかかることを避けられます。

よくある失敗と直し方

よくある質問

Q. トークンバケットとリーキーバケットはどう違いますか？ A. トークンバケットは「たまった分だけ一気に通す」、リーキーバケット（キュー型）は「一定速度で流す」方式です。実測でも、トークンバケットは10件を即時に許可し、リーキーバケットは受け付けた分を1秒間隔で処理しました（最大10秒待ち）。なお、キューを使わない「メーター型」のリーキーバケットは、許可/拒否の結果がトークンバケットと同じになります。

Q. GCRAを使う利点は何ですか？ A. 保存する状態が「理論到着時刻」1つだけなので、キーが多い場合でも省メモリで、計算も比較1回で済みます。 今回の実測でも、結果はトークンバケットと完全に一致しました。Redisで大量のキーを扱うときに向いています。

Q. nginxの burst と nodelay はどちらを使うべきですか？ A. 応答の速さを優先するなら burst ＋ nodelay、バックエンドへの流量を平準化したいなら nodelay なしが目安です。中間として delay=N で「N件までは即時、それ以降は待たせる」設定もできます。

Q. RateLimitヘッダーはもう使ってよいですか？ A. 2026年9月時点ではIETFのInternet-Draft（RFC未確定）です。使う場合は、ドラフトの版が変わりうることを前提に、標準化済みの429とRetry-Afterを必ず一緒に返すとよいでしょう。

まとめ

• レート制限は「キー・上限・超えたときの動作」を先に決めると設計がぶれない
• 固定ウィンドウは境界で上限の2倍を通す（実測で0.2秒に20件）。短い窓ではスライディング系を選ぶ
• 「N秒でN回」を厳密に守るならスライディングログ/カウンタ、平均＋バーストならトークンバケット/GCRA
• トークンバケットとGCRAは同じ結果になり、GCRAは状態が時刻1つで省メモリ
• 分散環境ではRedis＋Luaで判定と更新を原子的に。別コマンド版は同時アクセスで上限を素通りした
• nginxは burst で待たせ、nodelay で即時処理。return だけのlocationでは制限がかからない点に注意
• 429とRetry-Afterを返す。RateLimitヘッダーはドラフト段階なので併記で使う

株式会社RJCでは、アルゴリズムを実際に動かして挙動を確かめる姿勢を、プロジェクトの中で仲間と学び合っています。こうした知識を共有しながら、日々技術を磨いています。

株式会社RJC ― SI事業・SES事業・AI駆動開発。RJCは一緒に成長を楽しめる会社です。