【実務・中級編】 レートリミット（Rate Limiting）のアルゴリズム：トークンバケットとリーキーバケット – Web APIアーキテクチャ・データ連携実践ガイド

APIの寿命を握る「流量制御」の深層：トークンバケットとリーキーバケットの現場哲学

こんにちは。ネットワークの底流を流れるパケットの挙動に思いを馳せ、数々の修羅場をくぐり抜けてきたインフラアーキテクトです。

あなたが深夜のオンコール対応で叩き起こされる原因の多くは、データベースのデッドロックか、あるいは突発的なトラフィック（バースト）によるAPIのダウンでしょう。「ウチのAPI、なぜか急なアクセス増で全滅するんです」という若手エンジニアの悲鳴を聞くたびに、私はこう問いかけます。「おい、レートリミット（流量制御）のアルゴリズム、何を選んだ？」と。

教科書には「APIを守るために制限をかけましょう」とサラリと書いてありますが、現場ではどのアルゴリズムを選択するかによって、UX（ユーザー体験）が劇的に変わります。今回は、Web APIを守る盾として最も重要な「トークンバケット（Token Bucket）」と「リーキーバケット（Leaky Bucket）」という2大アルゴリズムにスポットを当て、パケットの挙動レベルから徹底的に比較していきましょう。

—

1. なぜAPIに「流量制御」が必要なのか？

現代のWebアプリケーションにおいて、APIはシステムの血管です。フロントエンド、モバイルアプリ、そして外部のサードパーティサービスが、この血管を通じて絶えずデータをやり取りしています。

しかし、セキュリティ対策やリソース保護（C10K問題ならぬ、C10M問題への備え）が不十分なAPIに、悪意あるスクリプトや、バグを抱えたクライアントからのリクエストが殺到するとどうなるでしょうか。スレッドプールは枯渇し、CPUはコンテキストスイッチの嵐で悲鳴を上げ、最終的には全ユーザーに対して HTTP 503 Service Unavailable を返す「仲良く全員沈没」の悲劇が幕を開けます。

ここで登場するのが Rate Limiting（レートリミット） です。
APIサーバーの手前（API Gatewayやリバースプロキシ）でトラフィックを制御し、許容量を超えたリクエストを弾く、あるいは遅延させることで、システム全体の健常性を保ちます。

この制御を実現するためのアルゴリズムとして、RFCやIETFの議論でも頻繁に引き合いに出されるのが、トークンバケット と リーキーバケット です。それぞれの内部動作を、物理的なメタファーを交えて解き明かしていきます。

—

2. トークンバケット（Token Bucket）：バーストを許容する「現実主義者」

仕組みとパケットの挙動

トークンバケットアルゴリズムは、その名の通り「バケツ」をイメージしてください。

1. バケツには最大容量（Capacity）があります。
2. 一定のレート（例：毎秒10個）で、バケツに「トークン」が補充されます。バケツが満杯になると、あふれたトークンは捨てられます。
3. クライアントからリクエストが1件届くたびに、バケツからトークンを1つ消費します。
4. トークンがバケツに残っていれば、リクエストは即座に許可（通過）されます。
5. トークンが空のときにリクエストが来ると、そのリクエストは拒否（HTTP 429 Too Many Requests）されるか、キューに回されます。

この方式の最大の特長は、「バースト（突発的なトラフィック）を許容できる」点です。例えば、容量100のバケツがあり、普段はあまり使われていなければ、100個分のトークンが溜まっています。そこに一瞬だけ「100リクエスト/秒」のバーストが来ても、バケツのストックから一気に消化するため、すべて正常に処理されます。

実務におけるユースケース

一般的なWeb API、GraphQLのクエリ、ECサイトのチェックアウト処理など、「普段は静かだが、ボタンを押した瞬間に数件の並行リクエストが走る」ような、ユーザーの快適なUXを損ねたくない場面で最適です。

—

3. リーキーバケット（Leaky Bucket）：一定流量を保つ「厳格な調停者」

仕組みとパケットの挙動

リーキーバケットもバケツを使いますが、構造が根本的に異なります。「穴の開いたバケツ」を想像してください。

1. クライアントからのリクエストは、まずキュー（バケツ）に溜められます。
2. バケツの底には一定の大きさの「穴」が空いており、そこから一定のレート（例：毎秒5個）でリクエストが「漏れ出し（処理され）」ます。
3. バケツの最大容量を超えてリクエストが流れ込むと、あふれた分（あふれた水）は即座に破棄（ドロップ）されます。

ネットワークエンジニアならピンと来るでしょう。これはルーターのQoS（Quality of Service）やシェーピング機能（Traffic Shaping）そのものです。入力がどれだけ波があろうとも、出力側は完全に「一定の流量」に均されます。

実務におけるユースケース

動画配信のストリーミング、金融取引システムへの注文送信、あるいは「下流のサードパーティAPIのレート制限が非常に厳しいため、こちら側から絶対に急激な負荷をかけてはいけない」という上流プロキシの制御において真価を発揮します。

—

4. アルゴリズムの比較マトリクス

実務でどちらを採用すべきか、以下の比較表をアーキテクチャ選定の判断材料にしてください。

| 評価項目 | トークンバケット (Token Bucket) | リーキーバケット (Leaky Bucket) |
| :— | :— | :— |
| バーストへの耐性 | 高い（溜まったトークン分を一気に処理可能） | 低い（キューのサイズまでしかバーストを吸収できず、出力は一定） |
| 出力トラフィックの平滑化 | しない（処理能力の許す限り即座に通す） | する（一定のレートで強制的に出力する） |
| メモリ/計算コスト | 低い（タイムスタンプとトークン数の保持のみ） | 中程度（FIFOキューの管理が必要） |
| 主な用途 | 一般的なWeb API, マイクロサービス間通信 | 下流APIの保護, トラフィックシェーピング |

—

5. 実装例：RedisとLuaスクリプトによる堅牢なトークンバケット

分散システム環境（複数台のAPIサーバー構成）において、インメモリだけでレートリミットを実装すると、サーバー間の同期が取れずに崩壊します。現場では、Redisをストアとして使い、アトミック性を担保するためにLuaスクリプトでトークンバケットを実装するのがデファクトスタンダードです。

以下に、実務でそのまま使えるPython（redis-py）のサンプルコードを示します。

import time
import redis

# Redisクライアントの初期化
r = redis.Redis(host='localhost', port=6379, db=0)

# トークンバケットを処理するLuaスクリプト
# 競合状態（Race Condition）を防ぐため、Redis上でアトミックに実行する
TOKEN_BUCKET_SCRIPT = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local fill_rate = tonumber(ARGV[2])
local requested = tonumber(ARGV[3])
local now = tonumber(ARGV[4])

-- 現在の状態を取得（存在しない場合は初期化）
local bucket = redis.call('HMGET', key, 'tokens', 'last_updated')
local tokens = tonumber(bucket[1])
local last_updated = tonumber(bucket[2])

if not tokens then
    tokens = capacity
    last_updated = now
else
    -- 経過時間に基づいてトークンを補充
    local delta = math.max(0, now - last_updated)
    local tokens_to_add = delta * fill_rate
    tokens = math.min(capacity, tokens + tokens_to_add)
    last_updated = now
end

-- リクエスト分のトークンが足りるか判定
if tokens >= requested then
    tokens = tokens - requested
    redis.call('HMSET', key, 'tokens', tokens, 'last_updated', last_updated)
    redis.call('EXPIRE', key, 60) --  TTLの設定（メモリリーク防止）
    return 1 -- 許可
else
    -- トークンが足りない場合でも、状態の更新は保存しておく
    redis.call('HMSET', key, 'tokens', tokens, 'last_updated', last_updated)
    return 0 -- 拒否
}
"""

# スクリプトをRedisに登録（SHAをキャッシュ）
token_bucket_sha = r.script_load(TOKEN_BUCKET_SCRIPT)

def check_rate_limit(user_id: str, capacity: int = 10, fill_rate: float = 1.0) -> bool:
    """
    指定されたユーザーのレートリミットをチェックする関数
    :param user_id: ユーザーを一意に識別するID
    :param capacity: バケツの最大容量（バースト許容量）
    :param fill_rate: 1秒あたりに補充されるトークン数
    :return: Trueなら許可、Falseなら制限超過
    """
    key = f"rate_limit:{user_id}"
    now = time.time()
    requested = 1

    # EVALSHAでスクリプトを実行
    result = r.evalsha(
        token_bucket_sha, 
        1, 
        key, 
        capacity, 
        fill_rate, 
        requested, 
        now
    )
    
    return bool(result)

# --- 実行シミュレーション ---
if __name__ == "__main__":
    user = "client_alpha"
    print("--- レートリミット検証開始 ---")
    
    for i in range(12):
        allowed = check_rate_limit(user, capacity=5, fill_rate=0.5)
        if allowed:
            print(f"Request {i+1}: 200 OK (通過)")
        else:
            print(f"Request {i+1}: 429 Too Many Requests (制限超過)")
        time.sleep(0.1)

—

6. クライアントへの優しさ：標準的なHTTPヘッダーの設計

レートリミットを実装する際、サーバー側でこっそり弾くだけでは、APIを利用するフロントエンドエンジニアやサードパーティの開発者がデバッグできずに発狂してしまいます。

IETF（インターネットエンジニアリングタスクフォース）のドラフト仕様（Draft RFC: RateLimit Fields for HTTP）に沿って、以下のレスポンスヘッダーを必ず返却するように設計しましょう。

  • RateLimit-Limit: ウィンドウ内で許可されている最大リクエスト数
  • RateLimit-Remaining: 現在のウィンドウ内で残っているリクエスト数
  • RateLimit-Reset: 制限がリクエスト可能な状態にリセットされるまでの残り時間（秒、またはUNIXタイムスタンプ）

cURLでのレスポンス確認例

実際にAPIを叩いた際に、これらのヘッダーがどのように返ってくるか、curlコマンドの -i オプション（ヘッダーを含むすべての出力）で確認してみましょう。

curl -i -X GET "https://api.example.com/v1/resource" \
     -H "Authorization: Bearer secret_token_xyz"

期待されるレスポンスのイメージ:

HTTP/1.1 200 OK
Content-Type: application/json
RateLimit-Limit: 100
RateLimit-Remaining: 85
RateLimit-Reset: 42
Retry-After: 42

{
  "status": "success",
  "data": [...]
}

もし HTTP 429 Too Many Requests が返された場合は、Retry-After ヘッダーを含めることで、クライアント側に「あと何秒待てば再試行できるか」を明確に伝えることができます。行儀の良いクライアントであれば、この値を見て自動的にバックオフ＆リトライ（指数バックオフ）を実装してくれます。

—

7. まとめ：現場のアーキテクトからの提言

レートリミットの設計は、単なる「サーバー防衛のためのプログラム」ではありません。それは、「システムが予測可能な負荷の範囲内で美しく稼働し続けるためのコントラクト（契約）」です。

  • ユーザーの利便性を最優先し、突発的な操作に耐えたいなら トークンバケット を選ぶ。
  • 下流システムやデータベースを保護するため、トラフィックを極限まで平滑化したいなら リーキーバケット を選ぶ。

どちらのアルゴリズムを採用するにせよ、Redisなどの分散ストアを用いたアトランザクション管理と、クライアントに優しく状況を伝える RateLimit-* ヘッダーの整備を忘れないでください。

インフラが静かな夜を迎えるために、あなたのAPIに正しい「バケツ」を配置しましょう。それでは、良きパケットの旅を！

スポンサーリンク

コメント

タイトルとURLをコピーしました