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

はじめに

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

Rate Limit は過剰なアクセスからサービスを守ります。利用者間の公平性や、契約プランごとの quota を保つ目的にも使います。

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

例えば、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 の設計では、リクエストを数える単位を先に決めます。

制限の対象がサーバ自身か、複数サーバからなるサービス全体かで、必要な構成は変わります。

サーバ単位の制限

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

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

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

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

サービス全体の制限

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

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

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

共有カウンタはサービス全体の 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 の事例は、この方式に近い構成です。

参考：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

実際のサービスでは、認証・認可の結果から identity を取得します。例えば API key、JWT の sub、tenant ID などです。

単一サーバで 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 のカウンタが上限に達しても、追加された 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 台あり、各上限が 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 内で1つの処理として実行します。複数のアプリケーションが同時に呼び出しても、途中に別のコマンドは割り込みません。

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] に retryAfter を渡します。これは window の長さではなく、次の window までの秒数です。

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 に3つの service を定義します。HTTP の入口となる traefik、共有カウンタを保存する valkey、リクエストを処理する app です。

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 用の endpoint です。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 は 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 が使えない場合、可用性を優先して判定を通過させる 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 には Twemproxy と memcached の cluster がありました。SSL session ID 用に、すでに利用していたものです。
この cluster によって、memcached のデータを複数サーバへ分割できます。
consistent hashing でキーを shard へ分散します。そのため cluster のサイズ変更時に再配置されるキーを少数に抑えられます。
各サーバーが1つの shard を担当します。

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

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 できます。
mitigation 開始後に同じ client から届くリクエストでは、追加の query は不要です。

近似値の精度

前の window の rate から、現在の値を近似します。

公式記事では、4億リクエストと27万の source を分析しています。誤って許可または制限した割合は0.003%、実測 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 を2分類します。Redis で件数を集計します。
例えば capacity の20%を critical request 用に予約します。non-critical request が残りの80%を超えると503で拒否します。

Worker Utilization Load Shedder は最後の防御線です。
traffic を4カテゴリーに分けます。critical methods、POSTs、GETs、test mode traffic です。worker に余裕がなくなると test mode から落とします。
切り捨てや復旧を急ぐと 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 では 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 による均衡の遅れ

polling で新しい client を発見するため、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 の 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