分散環境で Rate Limit を設計する

はじめに

API に Rate Limit を設定すると、一定時間内に処理できるリクエスト数を制限できます。

Rate Limit は、過剰なアクセスからサービスを守るだけでなく、利用者間の公平性や契約プランごとの quota を実現するためにも使います。

しかし、Rate Limit のカウンタを各サーバのメモリに置いたままサービスを水平スケールすると、サービス全体の上限を守れなくなります。

例えば、1つの API key に対して 100 req / window を設定しても、同じアプリケーションを2台起動すると、各サーバが100件ずつ許可する可能性があります。

この記事では、単一サーバの Fixed Window から始め、複数サーバでカウンタを共有する構成を検証してみます。

検証には、Traefik、Go アプリケーション2台、Valkey、k6 を使用します。

アルゴリズムの詳しい比較と Token Bucket の実装は、以前の記事で扱いました。

Goで始めるトークンバケット：基礎理論とgolang.org/x/time/rateの実装を読み解く

成果物

https://github.com/kntks/blog-code/tree/main/2026/08/distributed-rate-limit

使用バージョン

Rate Limit の単位を決める

Rate Limit の設計では、リクエストを数える単位を先に決めます。

サーバ単位でそのサーバ自身を守るのか、複数サーバからなるサービス全体の quota を守るのかによって、必要な構成が変わります。

サーバ単位の制限

サーバ単位の制限では、各サーバが独立してリクエストを数えます。

app-1: 100 req / window
app-2: 100 req / window

この制限は、1つのサーバが過負荷になることを防ぐ用途に向いています。

一方で、サービス全体の利用者 quota を表す制限ではありません。

サービス全体の制限

サービス全体の制限では、複数サーバが同じカウンタを参照します。

全サーバが同じ API key のカウンタを更新するため、サービス全体の上限を一つの値として扱えます。

ローカルカウンタと共有カウンタは優劣ではなく目的が違う

共有カウンタはサービス全体の quota を守れますが、ローカルカウンタの上位互換ではありません。

カウンタを共有ストアへ移すと正確性の範囲が広がる一方で、リクエストごとにネットワーク I/O が発生し、共有ストアが新しい依存先になります。

ローカルカウンタが適するのは、制限値が「各サーバが安全に処理できる量」を表す場合です。

例えば、各サーバが同時に10件までしか重い処理を実行できないなら、サービス全体のカウンタを作るより、各サーバで concurrency limit を設定する方が保護対象に近くなります。
共有ストアが停止してもローカルの保護は継続でき、追加のネットワーク往復もありません。

共有カウンタが適するのは、契約プランの quota、tenant ごとの公平性、課金対象の利用量など、どの replica が処理しても同じ上限を適用したい場合です。

ローカル方式と共有方式を組み合わせる

本番環境では、どちらか一方だけを選ぶとは限りません。

ローカル制限は各サーバが処理できる最大量を守り、共有制限は利用者単位の quota を守ります。
この2つは保護対象が異なるため、同じリクエストに重ねて適用できます。

Local rate limiting can be used in conjunction with global rate limiting to reduce load on the global rate limit service.

訳：ローカルレート制限は、グローバルレート制限サービスへの負荷を軽減するために、グローバルレート制限と組み合わせて使用​​できます。

引用：Global rate limiting - Envoy

別の方法として、中央のサービスが全体 quota を各 replica へ分配し、各 replica は割り当てられた範囲をローカルカウンタで消費する構成もあります。

この構成は hot path のネットワーク往復をなくせますが、replica 数の変化を反映するまでの遅延、未使用 quota の偏り、lease が切れたときの挙動を設計する必要があります。
後述する Monzo の事例は、この方式に近い構成です。

参考：Enabling horizontal autoscaling with co-operative distributed rate limiting

API key をキーにする

この検証では、Rate Limit のキーに API key を使います。

rate:apikey:{api_key_hash}:{window_id}

API key は認証処理を通過した後に取得し、Rate Limit の middleware に渡します。

検証では認証処理を簡略化するため、k6 から次のヘッダーを送信します。

X-API-Key: test-key-a

実際のサービスでは、API key、JWT の sub、tenant ID など、認証と認可の結果から得た identity を使用できます。

単一サーバで Fixed Window を実装する

まず、Rate Limit の状態を1つの Go プロセスに保持します。

Fixed Window は、時間を一定の長さの窓に区切り、窓ごとにリクエスト数を数える方式です。

例えば、window の長さを60秒にすると、次のようにカウンタを分けます。

rate:apikey:hash-a:2026-08-03T12:00:00Z
rate:apikey:hash-a:2026-08-03T12:01:00Z

現在時刻から window_id を求め、API key と組み合わせてカウンタのキーを作ります。

window_id = floor(unix_time / window_seconds)
key = api_key_hash + ":" + window_id

単一サーバの検証では、カウンタを Go のメモリに保持します。

複数の goroutine が同じ API key を更新するため、カウンタの読み書きには mutex などの排他制御が必要です。

上限を超えた場合は 429 Too Many Requests を返します。

HTTP/1.1 429 Too Many Requests
Retry-After: 12

Retry-After には、次の window までの秒数を設定します。

単一サーバであれば、この実装によってサーバ単位の上限を管理できます。

Fixed Window の境界でバーストが起きる

Fixed Window では、window の境界をまたぐと短時間に多くのリクエストを受け付ける可能性があります。

例えば、前の window の終わりに100件を許可し、新しい window の直後にも100件を許可すると、短時間に200件が通過します。

estimated_count = previous_count * (1 - α) + current_count

水平スケールでカウンタが分かれる

単一サーバの実装をそのまま複数サーバへ増やすと、各サーバが別々のカウンタを持ちます。

server-1 のカウンタが上限に達していても、scale-out で追加された server-2 のカウンタは空のため、server-2 へ振り分けられたリクエストは新たに許可される可能性があります。

1つの API key に対する上限を100 req / window とします。

リクエストが2台へ分散すると、各サーバは同じ API key に対して100件まで許可できます。

app-1: test-key-a を100件まで許可
app-2: test-key-a を100件まで許可

サービス全体: 最大200件近くを許可する可能性がある

replica が N 台あり、各 replica の上限が L なら、ローカルカウンタでサービス全体が許可し得る上限は最大で N × L まで増えます。

ただし、実際の許可数が常に N × L になるわけではありません。
replica i に到達したリクエスト数を R_i とすると、許可数は次の合計です。

allowed = Σ min(R_i, L)

例えば、250件が app-1 に200件、app-2 に50件と偏ると、上限が各100件でも許可数は150件です。
両方に100件以上が到達した場合は、200件まで許可されます。

これは各サーバの実装が壊れているからではありません。

各サーバは自分のメモリにあるカウンタを正しく更新していますが、他のサーバのカウンタを知らないため、サービス全体の上限を判定できません。

Rate Limit の目的がサーバ単位の過負荷防止であれば、ローカルカウンタで足ります。

API key ごとの quota をサービス全体で守るなら、状態を共有する仕組みが必要です。

Valkey でカウンタを共有する

複数サーバから参照できる場所へカウンタを移すと、各サーバが同じ状態を使って判定できます。

この検証では、Go から Valkey へ接続するために go-redis を使用します。

go-redis は Redis／Valkey との接続を担当するクライアントであり、Rate Limit のアルゴリズムを決めるライブラリではありません。

Fixed Window の判定処理は Lua スクリプトとして自分で定義します。

local count = redis.call("INCR", KEYS[1])

if count == 1 then
  redis.call("EXPIRE", KEYS[1], ARGV[1])
end

return count

Go 側では、このスクリプトを Eval で実行します。

INCR、初回の EXPIRE、カウンタ値の取得を Valkey 内で一つの処理として実行するため、複数のアプリケーションから同時に呼び出しても処理の途中へ別のコマンドが割り込みません。

go-redis/redis_rate のような既存ライブラリを使う方法もあります。

このライブラリは Lua を内部で使用するため、利用者が Lua を直接書く必要はありません。

ただし、採用するアルゴリズムは今回の Fixed Window ではなく GCRA 系です。

今回の検証では Fixed Window の共有状態を説明するため、go-redis と自作 Lua を使用します。

application -> Valkey: INCR
Valkey: count 42 -> 43
Valkey --x application: response lost

TTL を window の境界に合わせる

Fixed Window のキーには window_id が含まれるため、window が変わると新しいキーを使います。
古いキーを残し続ける必要はないので、初回の INCR と同時に TTL を設定します。

この実装で ARGV[1] に渡すのは window の長さそのものではなく、次の window までの秒数である retryAfter です。

TTL = window_seconds - (unix_time % window_seconds)

60秒 window の残り5秒で初めて使われたキーは、約5秒後に削除されます。
毎回 EXPIRE 60 を設定すると、判定には使わない古いキーが window 終了後も最大60秒残ります。
正しさへの影響は小さくても、key cardinality が大きい環境ではメモリ使用量に差が出ます。

共有カウンタの負荷と障害を考える

rate:apikey:{api_key_hash}:current_window
rate:apikey:{api_key_hash}:previous_window

Valkey 障害時の挙動を決める

Rate Limit の共有ストアが利用できないとき、リクエストを通すか拒否するかを決める必要があります。

この検証では fail-closed を採用します。

Valkey に接続できない場合は Rate Limit の判定をスキップせず、リクエストを拒否します。

quota を超えた場合は 429 Too Many Requests を返します。

Valkey 障害によって判定できない場合は、quota 超過とは異なるため、503 Service Unavailable を返します。

quota exceeded       -> 429 Too Many Requests
rate limit store error -> 503 Service Unavailable

本番環境では、すべての endpoint に同じ挙動を設定する必要はありません。

課金 API やログイン API では fail-closed にし、可用性を優先する読み取り API では fail-open やローカル制限へのフォールバックを選択することも設計の選択肢にできます。

検証環境を構成する

検証環境は Docker Compose で構成します。

compose.yaml には、HTTP の入口となる traefik、Rate Limit の共有カウンタを保存する valkey、リクエストを処理する app を service として定義します。

services:
  traefik:
    image: traefik:v3.7.10
    userns_mode: host
    container_name: traefik
    command:
      - --api.insecure=true
      - --providers.docker=true
      - --providers.docker.exposedbydefault=false
      - --entrypoints.web.address=:80
    ports:
      - "80:80"
      - "8080:8080"
    volumes:
      - /var/run/docker.sock:/var/run/docker.sock:ro
    networks:
      - rate-limit

  valkey:
    image: valkey/valkey:9.1.1-alpine3.24
    container_name: valkey
    ports:
      - "6379:6379"
    networks:
      - rate-limit
    healthcheck:
      test: ["CMD", "valkey-cli", "ping"]
      interval: 5s
      timeout: 3s
      retries: 5

  app:
    build: .
    environment:
      RATE_LIMIT_MODE: ${RATE_LIMIT_MODE:-shared}
      RATE_LIMIT_MAX: ${RATE_LIMIT_MAX:-100}
      RATE_LIMIT_WINDOW: ${RATE_LIMIT_WINDOW_SECONDS:-60}s
      VALKEY_ADDR: valkey:6379
    depends_on:
      valkey:
        condition: service_healthy
    deploy:
      mode: replicated
      replicas: 2
    labels:
      - traefik.enable=true
      - "traefik.http.routers.rate-limit.rule=PathPrefix(`/`)"
      - traefik.http.routers.rate-limit.entrypoints=web
      - traefik.http.services.rate-limit.loadbalancer.server.port=8080
    networks:
      - rate-limit
    healthcheck:
      test: ["CMD", "wget", "--quiet", "--spider", "http://localhost:8080/healthz"]
      interval: 5s
      timeout: 3s
      retries: 5
      start_period: 5s

networks:
  rate-limit:
    driver: bridge

Go アプリケーションからは、同じ Compose network 上の service name valkey とポート 6379 を使って接続します。
Traefik は Docker provider でアプリケーションの labels を読み取り、ホスト側の 80 番ポートで受けたリクエストを、アプリケーションのコンテナ内 8080 番ポートへルーティングします。
app 自体はホストへ直接ポート公開していません。

コンテナを起動した後は、API key を X-API-Key ヘッダーに指定して、ホスト側からリクエストを送信できます。

curl -H 'X-API-Key: test-key-a' http://localhost/

/healthz はアプリケーションの healthcheck 用エンドポイントのため、API key は必要ありません。

同じ Go アプリケーションを2つ起動し、次の2つのモードを比較します。

ローカルカウンタ

各アプリケーションが、API key ごとのカウンタを自分のメモリに保持します。

app-1: ローカルカウンタ
app-2: ローカルカウンタ

共有カウンタ

各アプリケーションが、API key ごとのカウンタを Valkey に保存します。

検証用レスポンスには、リクエストを処理したアプリケーションを確認するために X-Instance-ID を付けます。

X-Instance-ID: app-1

k6 では、総リクエスト数、許可数、拒否数、インスタンスごとの処理数を集計します。

検証で確認すること

ローカルカウンタでは、各アプリケーションが独立して上限までリクエストを許可します。

共有カウンタでは、app-1 と app-2 の許可数を合算しても、サービス全体の上限を超えないことを確認します。

この比較では、両方のモードで Fixed Window と API key を使います。

アルゴリズムを変えずにカウンタの保存場所だけを変えることで、水平スケールによる差を分離して観測できます。

検証結果をどう読むか

既定の検証条件は、2 replicas、上限100件、総リクエスト250件です。

RATE_LIMIT_MODE=shared docker compose up -d --build
k6 run -e RATE_LIMIT_MODE=shared k6/rate-limit.js

共有モードでは、どちらの replica が処理しても同じ Valkey key を更新するため、許可数は合計100件です。

RATE_LIMIT_MODE=local docker compose up -d --force-recreate app
k6 run -e RATE_LIMIT_MODE=local k6/rate-limit.js

ローカルモードでは、Traefik が両方の replica へ十分な数を振り分けると、それぞれ100件、合計200件を許可します。

ここで観測しているのは、Valkey の方が常に優れているという結果ではありません。
共有モードはサービス全体の quota を守る代わりに、判定のたびに Valkey へアクセスします。
ローカルモードは global quota を守れない代わりに、外部 I/O なしで各サーバを保護できます。

この検証は許可数の違いを観測するもので、性能 benchmark ではありません。
性能を比較する場合は、Rate Limit 判定だけの p50、p95、p99、Valkey の command latency、接続プール待ち時間を別に計測し、同じ負荷と接続条件で比較します。

$ RATE_LIMIT_MODE=local docker compose up -d --force-recreate app

$ k6 run -e RATE_LIMIT_MODE=local k6/rate-limit.js

  █ THRESHOLDS

    allowed_requests
    ✓ 'count==200' count=200

    checks
    ✓ 'rate==1' rate=100.00%

    instance_requests
    ✓ 'count==250' count=250

    missing_instance_responses
    ✓ 'count==0' count=0

    rejected_requests
    ✓ 'count==50' count=50

    unexpected_responses
    ✓ 'count==0' count=0


  █ TOTAL RESULTS

    checks_total.......: 750     7939.280384/s
    checks_succeeded...: 100.00% 750 out of 750
    checks_failed......: 0.00%   0 out of 750

    ✓ status is 200 or 429
    ✓ instance ID is present
    ✓ 429 includes Retry-After

    CUSTOM
    # ↓ 200リクエストが成功している。
    allowed_requests...............: 200   2117.141436/s
    instance_requests..............: 250   2646.426795/s
    missing_instance_responses.....: 0     0/s
    # ↓ 50リクエストが拒否されている
    rejected_requests..............: 50    529.285359/s
    unexpected_responses...........: 0     0/s

    HTTP
    http_req_duration..............: avg=5.49ms min=472µs    med=1.27ms max=87.96ms p(90)=3.16ms p(95)=38.65ms
      { expected_response:true }...: avg=5.49ms min=472µs    med=1.27ms max=87.96ms p(90)=3.16ms p(95)=38.65ms
    http_req_failed................: 0.00% 0 out of 250
    http_reqs......................: 250   2646.426795/s

    EXECUTION
    iteration_duration.............: avg=5.93ms min=503.49µs med=1.36ms max=94.01ms p(90)=3.21ms p(95)=43.63ms
    iterations.....................: 250   2646.426795/s

    NETWORK
    data_received..................: 46 kB 482 kB/s
    data_sent......................: 25 kB 265 kB/s

$ RATE_LIMIT_MODE=shared docker compose up -d --force-recreate app
$ k6 run -e RATE_LIMIT_MODE=shared k6/rate-limit.js


  █ THRESHOLDS

    allowed_requests
    ✓ 'count==100' count=100

    checks
    ✓ 'rate==1' rate=100.00%

    instance_requests
    ✓ 'count==250' count=250

    missing_instance_responses
    ✓ 'count==0' count=0

    rejected_requests
    ✓ 'count==150' count=150

    unexpected_responses
    ✓ 'count==0' count=0


  █ TOTAL RESULTS

    checks_total.......: 750     8125.765176/s
    checks_succeeded...: 100.00% 750 out of 750
    checks_failed......: 0.00%   0 out of 750

    ✓ status is 200 or 429
    ✓ instance ID is present
    ✓ 429 includes Retry-After

    CUSTOM
    # ↓ 100リクエストが成功している。
    allowed_requests...............: 100   1083.435357/s
    instance_requests..............: 250   2708.588392/s
    missing_instance_responses.....: 0     0/s
    # ↓ 150リクエストが拒否されている
    rejected_requests..............: 150   1625.153035/s
    unexpected_responses...........: 0     0/s

    HTTP
    http_req_duration..............: avg=6.09ms min=622µs    med=1.84ms max=85.77ms p(90)=5.42ms p(95)=38.91ms
      { expected_response:true }...: avg=6.09ms min=622µs    med=1.84ms max=85.77ms p(90)=5.42ms p(95)=38.91ms
    http_req_failed................: 0.00% 0 out of 250
    http_reqs......................: 250   2708.588392/s

    EXECUTION
    iteration_duration.............: avg=6.48ms min=685.25µs med=1.92ms max=91.03ms p(90)=5.45ms p(95)=43.08ms
    iterations.....................: 250   2708.588392/s

    NETWORK
    data_received..................: 52 kB 560 kB/s
    data_sent......................: 25 kB 274 kB/s

$ docker compose exec -it valkey valkey-cli

127.0.0.1:6379> keys *
1) "rate:apikey:{481c559bdf5d7f39c4ef16f7c81b093f096ce7b4c3d4bb1242400e56d8a1aae3}:29794427"

127.0.0.1:6379> get rate:apikey:{481c559bdf5d7f39c4ef16f7c81b093f096ce7b4c3d4bb1242400e56d8a1aae3}:29794427
"250"

Rate Limit を置く場所を分ける

Rate Limit は、制御する対象に応じて配置する層を分けます。

外部利用者の API key quota は、認証情報を取得できる Application 層で判定します。

DB や外部 API を守る制御は、Rate Limit だけでなく queue や concurrency limit も使います。

環境ごとの適用

検証した構成を、実際の実行環境へそのまま移植できるとは限りません。

環境ごとに、Rate Limit を置く場所と共有ストアの選択肢が変わります。

Kubernetes の Gateway API 自体はルーティングの仕様であり、Rate Limit の機能や設定方法は利用する実装に依存します。
Gateway API 対応の実装で route 単位の流量を制御し、Application 層で API key、user、tenant 単位の quota を判定するように役割を分けます。

Redis／Valkey は Kubernetes の Pod として配置し、Service 経由で複数の Application replica から共有する構成も選べます。
Redis／Valkey が一時的に利用できない場合に、可用性を優先して Rate Limit の判定を通過させる fail-open も可能です。
ただし、この間は利用者単位の制限が効かず、下流のサービスや高コストな処理に負荷が集中するおそれがあります。

Redis／Valkey を単一 Pod にすると、その Pod が単一障害点になります。
本番環境で共有 quota の可用性を重視する場合は、HA 構成またはマネージドサービスも検討します。

Kubernetes や Envoy の設定例は、今回の Go アプリケーションの実装には含めません。

企業の事例から設計を比較する

ここまでの検証では、すべてのリクエストで Valkey の共有カウンタを更新しました。
しかし、実際の設計は「ローカル方式か共有方式か」の二択ではありません。

各社の公式技術ブログを、課題、制約、解決策、代償の順に比較します。
以下は各資料の公開時点で確認できる内容であり、現在の内部実装を示すものではありません。

Cloudflare

Cloudflare の課題は、数百万の domain とさらに多くの rule に一致するリクエストを、client IP ごとに edge で数えることでした。
閾値を超えたリクエストを origin へ到達させず、ブルートフォース攻撃や L7 DoS などの悪意あるトラフィックから origin を保護することが目的です。

課題：ローカルだけでは不十分で、中央ストアは遠すぎる

Cloudflare の edge server は NGINX で動作しています。
NGINX の標準レートリミットは使いやすく効率的ですが、設定を変更するたびに config の reload が必要です。
また、同じ client からの新しい TCP 接続が PoP 内の複数サーバへ分散すると、サーバごとにカウンタが分かれて機能しません。

一方、世界中に広がる Cloudflare のネットワークでは、すべてのカウンタを単一の中央拠点へ集めると、レイテンシが大きくなります。
中央サービスの可用性を保証することも難しくなります。

Cloudflare は Anycast によって、通常は同じ client IP からのトラフィックが同じ PoP へ到達する性質を利用しました。
ただし、新しい TCP 接続は同じ PoP 内の別のサーバへ到達する可能性があります。
そこで、PoP ごとに独立したカウントシステムを作り、PoP 内のサーバ間だけでカウンタを共有します。
これにより、レイテンシを抑えながら、PoP 内の複数サーバで同じカウンタを参照できます。

解決策：PoP 内で分散し、Sliding Window Counter を使う

各 PoP には、SSL session ID のためにすでに利用していた Twemproxy と memcached の cluster がありました。
この cluster によって、memcached のデータを複数サーバへ分割できます。
consistent hashing でキーを shard へ分散するため、cluster のサイズ変更時に再配置されるキーを少数に抑えられます。
各サーバーが1つの shard を担当します。

アルゴリズムには、現在と直前の sampling period を使う Sliding Window Counter を採用しました。

estimated_rate
  = previous_count * (remaining_time / sampling_period)
  + current_count

すべてのリクエストの timestamp を保存する方式よりメモリ使用量が小さく、カウンタの更新は memcached の INCR で実行できます。
推定値も GET と単純な計算で求められます。

ただし、推定値を取得するには memcached への query が必要です。
大規模な L7 攻撃では memcached の cluster が圧迫されるおそれがあり、通常時でも正当なリクエストを遅くします。
そのため、increment job を非同期で実行して、リクエスト処理を遅延させないようにしています。
rate が閾値を超えた場合は、その client への mitigation を開始する情報を PoP 内のすべてのサーバへ伝えます。
リクエスト処理では、その情報だけを確認します。

mitigation が始まると終了時刻を把握できるため、その情報を各サーバーの memory に cache できます。
サーバーが client への mitigation を開始した後のリクエストでは、別の query を実行する必要がありません。

近似値の精度

Sliding Window Counter は、直前の sampling period にリクエストが一定の rate で発生したと仮定して、実際の rate を近似します。

公式記事では、4億リクエストと27万の source を分析した結果、誤って許可または制限したリクエストは0.003%、実測 rate と近似 rate の平均差は6%だったと報告しています。

• How we built rate limiting capable of scaling to millions of domains

Stripe

Stripe では、API の可用性を維持するために、利用者ごとの requests per second だけでなく、状況に応じた複数の制御を使っています。

• 1 利用者のスクリプトが大量のリクエストを送ったり、サーバーを意図的に過負荷にしようとしたりしても、他の利用者に影響させない
• CPU 負荷の高い endpoint への同時リクエスト集中を抑える
• 障害時に低優先度のリクエストを落とし、より重要なリクエストを通す
• worker にリクエストが滞留したときに、優先度の低いトラフィックを段階的に落とす

Stripe は、これらの問題に対して4種類の制御を使い分けています。

目的の異なる制御を組み合わせる

Request Rate Limiter は、user ごとに割り当てた Token Bucket を使って実装し、Redis で状態を管理しています。
リアルタイムイベント中の急激な利用増加に対しては、上限を一時的に超えるバーストも許容します。

Concurrent Requests Limiter は「1秒に何件」ではなく「今、何件が処理中か」を制限します。
リソース消費の大きい endpoint では、同時に多くのリクエストを受けるとリソース競合が起きやすくなります。
さらに、応答を待つユーザーの再試行が負荷を増大させます。
同時実行数を制限することで、こうしたリソース競合を抑えられます。

Fleet Usage Load Shedder では traffic を critical と non-critical に分け、Redis cluster で各タイプの現在の request 数を数えます。
例えば capacity の20%を critical request 用に予約し、non-critical request が80%の割り当てを超えた場合は503で拒否します。

Worker Utilization Load Shedder は最後の防御線です。
traffic を critical methods、POSTs、GETs、test mode traffic の4カテゴリーに分け、worker に余裕がなくなると、まず test mode traffic から優先度の低いトラフィックを徐々に切り捨てます。
切り捨てと復旧を急に行うと flapping が起こり得るため、traffic を落とすときも戻すときも段階的に行います。

レート制限を安全に導入する

Stripe の記事では、レート制限のコードにバグがある場合や Redis が停止した場合でも API を機能させ続けるため、すべてのレベルで例外を捕捉して fail-open にする方針が説明されています。
これは、本記事で説明した fail-closed とは異なる方針です。

また、kill switch、alert、metrics を用意し、dark launch によって「実際にはどの request を拒否するか」を観測します。

• Scaling your API with rate limiters

Monzo

Monzo は Kubernetes 上で多数のマイクロサービスを運用し、各 service を最低3 replicas で動かしています。
当初は、Kafka consumer などの limit をレプリカごとに設定していました。

課題：replica 数に依存する limit と autoscaling

例えば、1 replica あたり100 events/sを設定すると、3 replicas では全体300 events/s、6 replicas では600 events/sになります。

replica 数を変えると limit の意味まで変わるため、Rate Limit を使う service は horizontal autoscaling を避ける必要がありました。

公式記事では、ほかにも次の課題を挙げています。

• 利用量が急増したとき、0件から上限まで即座に許可してしまい、autoscaling が追いつかない
• 利用者数や platform の capacity が成長しても、過去に手動設定した limit が自動では追随しない

最初の改善対象は、replica数と全体limitを切り離すことでした。

Autoscaling systems and instant surges don’t typically go well together.

訳：オートスケーリングシステムと、瞬間的な負荷急増は、通常うまく両立しません。

制約：低カーディナリティ、高スループット、信頼できる内部サービス間の制御

Monzo が主に解こうとしたのは、低カーディナリティかつ高スループットな内部処理です。

Redis counter を毎回更新する方式は、数千 events/s の処理ごとに network round trip が発生するため高コストです。
一方、これは信頼できない外部 client を制限する用途ではなく、同じ組織内の service 同士の制御です。
そのため、client が割り当てを守ることを前提にできます。

解決策：中央で capacity を分配し、判定を local にする

service.distrate という中央 service が、設定された全体 capacity を client へ lease として分配します。
client は定期的に poll し、受け取った capacity で local の golang.org/x/time/rate を更新します。

これにより、全体 capacity は中央で調整しながら、個々の処理では network round trip を発生させません。
client が消えたときは lease の期限で capacity を回収します。

分配には、全 capacity を client 数で割る EvenShare を使います。
中央 service が利用できず lease も切れた場合に完全停止しないよう、client へ safe capacity も返します。

制約：polling と EvenShare による均衡の遅れ

新しい client を発見するのは polling なので、replica 増減後に割り当てが均衡するまで時間がかかります。
また、EvenShare では使っていない capacity を必要な client へ即座に回せず、利用率に偏りがあると非効率です。
公式記事でも、usage に基づく再分配を今後の改善候補として挙げています。

service.distrate は状態を memory に持ち、1つの leader が分配を決定します。
leader 交代後は client からの poll を待って状態を再学習します。
構成は安価ですが、即座に完全な状態を復元する方式ではありません。

• Enabling horizontal autoscaling with co-operative distributed rate limiting

企業事例から得られる設計原則

3社に共通するのは、最も正確なカウンタを無条件には選んでいないことです。

1. 保護対象から制限の単位を決める
   • origin を守る Cloudflare は client IP と PoP を利用する
   • 公開 API を守る Stripe は user、concurrency、priority を使い分ける
   • 内部処理を守る Monzo は service 全体の capacity を分配する
2. hot pathで払えるコストを決める
   • Stripe の Redis や本記事の Valkey は request ごとに共有状態を更新する
   • Cloudflare は更新を非同期化する
   • Monzo は capacity だけを中央で調整し、判定を local にする
3. 必要な正確性の範囲を決める
   • process、PoP、service、account、世界全体では、必要な共有方法が異なる
   • 近似や収束を許せるなら、レイテンシと可用性を改善できる
4. 障害時に何を守るか決める
   • quota を優先して fail-closed にするのか
   • API の継続を優先して fail-open にするのか
   • safe capacity やローカルフォールバックで縮退するのか

したがって、設計の出発点は「Redis／Valkeyを使うか」ではありません。
何を、どの範囲で、どの程度正確に、障害時にも守りたいかを決め、その要件から状態の配置を選びます。

まとめ

ローカルカウンタと共有カウンタは、正確性、レイテンシ、可用性、運用コストの交換です。

• ローカルカウンタは global quota を保証できない代わりに、高速で外部障害の影響を受けにくい
• 共有カウンタは共有範囲の quota を守れる代わりに、network round trip と共有ストアへの依存が増える
• quota を replica へ lease し、全体量を調整しながら hot path を local にする中間的な方式もある

今回の検証では、Fixed Window のカウンタを Valkey へ保存し、go-redis と Lua で1回の判定を atomic に処理します。
2 replicas で上限100件を設定したとき、local モードでは最大200件、shared モードではサービス全体で100件が許可されることを確認しました。

ただし、Luaのatomicityだけでは、network timeout、clock skew、hot key、failoverによる巻き戻りは解決しません。

Rate Limit の保存場所と共有範囲は、制限の目的に合わせて選びます。

• サーバ自身を守る：ローカルカウンタ、concurrency limit
• サービス全体の利用者 quota を守る：共有カウンタ
• high-throughput な内部処理を守る：quota の lease とローカルリミッタ
• 入口の異常アクセスを抑える：WAF、Gateway
• DB や外部 API を守る：queue、concurrency limit

企業事例でも、世界全体で1つの厳密なカウンタへ収束させているわけではありません。
Cloudflare は PoP、Stripe は目的別の複数層、Monzo は capacity lease を選びました。

設計時には、次の順番で問いを立てます。

1. 何を守るのか
2. 誰または何をキーにして数えるのか
3. process、cluster、region のどこまで共有するのか
4. 何件、何秒の誤差を許容できるのか
5. 共有コンポーネントが停止したとき、可用性と quota のどちらを優先するのか

アルゴリズムの選択、特に Token Bucket の詳細は別の記事で扱います。

参考資料

• Goで始めるトークンバケット：基礎理論とgolang.org/x/time/rateの実装を読み解く
• Valkey EVAL command
• Rate limits
• API Gateway throttling
• go-redis/redis_rate
• How we built rate limiting capable of scaling to millions of domains
• Scaling your API with rate limiters
• Enabling horizontal autoscaling with co-operative distributed rate limiting