Distributed Rate Limiting Architecture: Token Bucket, GCRA, Redis and Envoy (2026)

A rate limiter that works on one process is a ten-line exercise. The same limiter spread across forty gateway pods, three regions, a Redis cluster that occasionally fails over and a client population that includes both a mobile app and a runaway retry loop is an entirely different system. Most production incidents involving distributed rate limiting are not caused by the wrong algorithm. They come from the seams: a counter that is not atomic, a clock that disagrees with its neighbour, a hot key that melts one shard, or a limiter that fails closed and turns a cache blip into a full outage.

This guide treats rate limiting as a distributed-systems design problem. We compare the six common algorithms with worked arithmetic, build a two-tier architecture with local and global enforcement, write the atomic Redis scripts, wire it into Envoy’s rate limit service, and then spend real time on failure modes, hot keys, multi-region and LLM token budgets.

What this covers: algorithm math and burst behaviour, token bucket vs GCRA, Redis Lua implementations, Envoy local and global limiting, fail-open policy, hot keys, headers and 429 semantics, and capacity planning.

Context and Background

Rate limiting protects a shared resource by bounding how fast any one caller can consume it. The goals differ by deployment: a public API wants fairness and abuse resistance, an internal service mesh wants protection from retry storms, and a billing-sensitive platform wants quota accounting. Those goals pull the design in different directions, which is why published designs from large API providers look so different from one another.

Stripe describes four distinct mechanisms in its engineering write-up: a request rate limiter, a concurrent request limiter, a fleet usage load shedder and a worker utilization load shedder. Its request limiter is a token bucket backed by Redis, and the post is explicit about operational safeguards: fail open on errors, kill switches via feature flags, and dark launches that observe what a limiter would block before enforcing it (Stripe: Scaling your API with rate limiters). GitHub publishes numeric primary limits (for example 5,000 requests per hour for an authenticated user and 60 per hour unauthenticated by IP) plus secondary limits on concurrency, per-minute points and CPU time, with REST reads costing roughly one point and most writes five (GitHub REST API rate limits). Cloudflare popularised the sliding window counter at edge scale.

Notice what these designs share: layered limits (per-second burst plus per-hour quota), cost-weighted requests rather than flat counts, and a deliberate stance on what happens when the limiter itself breaks. Your gateway layer matters too. If you are choosing the enforcement point, our API gateway comparison of Kong, Envoy Gateway and Apache APISIX covers how each handles the plugin and filter model, and the shift towards Kubernetes Gateway API over Ingress is changing where policy attaches.

One framing helps throughout. Every limiter answers one question: given the history for this key, may this request proceed at this moment? Algorithms differ in how much history they keep (a counter, two counters, a timestamp, a log) and therefore in memory, accuracy and burst shape. Distribution adds a second question: who owns that history, and how stale may a replica’s view be?

The Algorithms, With Worked Math

Six algorithms cover almost every production system. We use one running example: a limit of 100 requests per minute per API key.

Short answer: which algorithm should I use? For most APIs, use a token bucket or GCRA when you want controlled bursts with O(1) state per key, and a sliding window counter when you want a “requests per rolling window” contract that is cheap and close to exact. Use sliding log only when exactness matters more than memory.

Fixed window counter

Divide time into aligned one-minute buckets and increment a counter per key per bucket. State is one integer. The flaw is the boundary: a client can send 100 requests at 12:00:59 and another 100 at 12:01:00, producing 200 requests in two seconds while never violating the limit. The worst-case burst is exactly 2x the limit. Fixed windows remain popular because the implementation is a single atomic increment with an expiry, and Envoy’s reference rate limit service is built around per-unit counts of this kind.

Sliding log

Store a timestamp for every accepted request and count those inside the trailing 60 seconds. This is exact, but state is O(limit) per key: 100 timestamps of 8 bytes is 800 bytes of payload plus structure overhead, per key. At a million active keys that is on the order of a gigabyte before overhead, and trimming the log costs O(log n) in a Redis sorted set. It is the right choice for low-volume, high-value limits such as password reset attempts, where accuracy beats cost.

Sliding window counter

Keep two integers: the previous window count and the current window count. Estimate the rolling rate by weighting the previous window by how much of it still overlaps the trailing interval. Cloudflare’s published example uses a limit of 50 per minute, 15 seconds into the current minute, with 42 requests in the previous minute and 18 in the current one: 42 x (60 – 15) / 60 + 18 = 49.5, so one more request pushes the estimate over the limit (Cloudflare: Counting things). The estimate assumes the previous window’s requests were spread evenly, which is the approximation. Cloudflare reported testing it on 400 million requests from 270,000 sources, with 0.003% of requests wrongly allowed or limited and an average 6% difference between estimated and real rate. Those are Cloudflare’s numbers on their traffic; your traffic shape will differ.

Token bucket

A bucket holds up to B tokens and refills at rate r tokens per second. A request spends one token, or its cost. With B = 20 and r = 100/60 = 1.67 per second, a client idle for 12 seconds has a full bucket and may send 20 requests instantly, then settles to 1.67 per second. Over any interval t, the maximum allowed is B + r*t, so over a minute that is 20 + 100 = 120, not 100. That is a feature: the bucket separates burst size from sustained rate, two knobs that fixed windows conflate. State is two values, tokens and last refill time, and refill is computed lazily on arrival rather than by a timer.

Leaky bucket

The leaky bucket is the mirror image. Requests enter a queue of size B and drain at a constant rate. As a meter it behaves like a token bucket; as a shaper it smooths output, which is why it appears in traffic shaping and in Nginx’s limit_req with burst and delay settings. The practical difference: a shaper delays requests, a policer rejects them. API gateways overwhelmingly police, because holding connections open to smooth bursts consumes the very resources you are protecting.

GCRA

The Generic Cell Rate Algorithm comes from ATM networking and is equivalent to a token bucket, with one state value per key: the theoretical arrival time (TAT). Define the emission interval T = 1/rate and the burst tolerance tau = (B – 1) x T. For a request at time now: let TAT’ = max(TAT, now). If TAT’ – now is no more than tau, allow the request and store TAT’ + T (times cost). Otherwise deny, and the client should wait TAT’ – now – tau seconds. Brandur Leach’s widely read write-up describes the same state machine and recommends using the data store’s clock for shared deployments (Brandur: Rate limiting, Cells, and GCRA).

Worked example: rate 100/min, so T = 0.6 s; burst B = 20, so tau = 19 x 0.6 = 11.4 s. A cold key has TAT = now, and each accepted request pushes TAT forward 0.6 s. After 20 back-to-back requests, TAT is now + 12 s, so the gap TAT – now exceeds tau on the 21st attempt and it is denied, with a retry hint of 12 – 11.4 = 0.6 s. That is exactly one refill interval. The deny path returns an exact Retry-After with no extra bookkeeping, which is one reason GCRA is attractive.

Figure 1: Two-tier distributed rate limiting. Each Envoy holds a local token bucket and consults a shared rate limit service backed by sharded Redis.

Token bucket vs GCRA

Token bucket vs GCRA is mostly an implementation question, because both enforce the same contract. A token bucket stores two fields, tokens and last-refill timestamp, and must do floating-point refill arithmetic and clamp at capacity. GCRA stores a single timestamp, so the Redis value is one string, the update is one SET, and there is no clamp. GCRA also makes variable cost natural: a request of cost c advances TAT by c x T and is admitted if the resulting gap fits tau. The trade-off is conceptual: engineers find “tokens remaining” easier to explain than “theoretical arrival time”, and GCRA’s remaining-quota header must be derived as floor((tau – (TAT – now)) / T) + 1. Pick GCRA when you want minimal state and exact retry hints; pick a token bucket when you want to expose a quota number to customers directly.

Burst and accuracy summary

Algorithm	State per key	Worst-case burst	Accuracy	Typical home
Fixed window	1 counter	2x limit at boundary	Exact per window	Simple quotas, Envoy RLS
Sliding log	N timestamps	None	Exact	Login, OTP, reset flows
Sliding window counter	2 counters	Slightly above limit	Approximate	Edge / CDN
Token bucket	tokens + time	B above steady rate	Exact	API gateways, Stripe
Leaky bucket	queue + time	Shaped out	Exact	Traffic shaping
GCRA	1 timestamp	tau / T + 1	Exact	Redis modules, Throttled

Distributed Rate Limiting Reference Architecture

Direct answer: a robust distributed rate limiter has two tiers. A local tier inside each proxy absorbs bursts and sheds obvious abuse with no network hop. A global tier, usually a rate limit service over Redis, enforces the cross-instance quota with atomic scripts. Envoy documents exactly this split: local limiting uses a token bucket and is applied first, global limiting finishes the job.

Why a single local limiter is not enough

Suppose forty Envoy pods each enforce 100 requests per minute per key locally, and the load balancer spreads a client’s traffic evenly. The client effectively gets 4,000 per minute. If traffic is skewed, some pods reject while others have headroom. Dividing the quota by pod count (100/40 = 2.5 per pod) fails the other way: autoscaling changes N, and a small tenant’s traffic landing on a few pods hits the 2.5 ceiling long before the true quota. Local limits are therefore a protective bound, not an accounting system.

Global enforcement needs a shared store. Envoy’s documentation notes that global limiting suits cases where many hosts forward to few hosts with low latency, such as database servers, and that the local filter reduces load on the global service (Envoy global rate limiting). The reference rate limit service is written in Go with a Redis backend.

The decision path

Figure 3 shows a single request. The proxy first takes a token from its local bucket; if empty it returns 429 immediately without touching the network. It then sends a ShouldRateLimit gRPC call to the rate limit service carrying descriptors, which are ordered key/value pairs such as (api_key, abc123) or (remote_address, 10.1.2.3). The service looks up the matching rule in its configuration, runs one atomic Redis operation per descriptor, and returns OK or OVER_LIMIT. The proxy then forwards or rejects.

Figure 3: Request path. The local bucket gates first; only survivors pay for a gRPC call and a Redis round trip.

Descriptor design deserves care. A descriptor is the identity of the quota. Putting the route, the tenant and the plan tier into one descriptor chain gives you rules like “tenant X on plan Pro may make 600 POST /orders per minute”. Putting only the IP gives you a crude per-source limit that punishes shared NATs. Mixed strategies layer both: a generous per-IP limit as an abuse backstop, and a strict per-credential limit as the product contract.

Atomicity: why Lua

The naive implementation is read-modify-write: GET the counter, compare, SET the new value. Two gateways interleaving those steps both read 99 and both write 100, admitting 101 requests. Racing is the default failure of home-grown limiters. The fixes are an atomic primitive (INCR for counters) or a server-side script. Redis executes a Lua script atomically: no other command runs between its steps, which makes compound logic like GCRA safe. Scripts are cached by SHA and called with EVALSHA to avoid resending the body.

Here is a GCRA limiter as a Redis Lua script. It uses the Redis server clock so that gateway clock skew cannot change the answer.

-- KEYS[1] = rate limit key
-- ARGV[1] = emission interval T in milliseconds
-- ARGV[2] = burst tolerance tau in milliseconds
-- ARGV[3] = cost (number of units this request consumes)
local t_ms   = tonumber(ARGV[1])
local tau_ms = tonumber(ARGV[2])
local cost   = tonumber(ARGV[3])

local now = redis.call('TIME')
local now_ms = tonumber(now[1]) * 1000 + math.floor(tonumber(now[2]) / 1000)

local tat = tonumber(redis.call('GET', KEYS[1]))
if tat == nil or tat < now_ms then tat = now_ms end

local increment = cost * t_ms
-- allowed if the new TAT does not run further ahead than tau + increment
local new_tat = tat + increment
local allow_at = new_tat - (tau_ms + t_ms)

if allow_at > now_ms then
  -- denied: tell the caller how long to wait
  return {0, allow_at - now_ms}
end

-- TTL keeps idle keys from accumulating
redis.call('SET', KEYS[1], new_tat, 'PX', (new_tat - now_ms) + 1000)
local remaining = math.floor((tau_ms + t_ms - (new_tat - now_ms)) / t_ms)
return {1, remaining}

Check it against the worked example: T = 600 ms, tau = 11,400 ms, cost 1. The 20th rapid request has new_tat = now + 12,000, allow_at = 12,000 – 12,000 = now, so it passes. The 21st has new_tat = now + 12,600, allow_at = now + 600, so it is denied with a wait of 600 ms. The script is O(1), one GET and one SET.

A caution on TIME: reading the clock inside a script is permitted in modern Redis versions because scripts replicate by effect, but if you run an old deployment with verbatim script replication, check your version’s behaviour before relying on it. Our Valkey vs Redis vs Dragonfly ADR compares how the engines differ on scripting, threading and licensing, which matters for a store that sits on every request path.

Calling it from Python

A thin client wraps the script. This version uses redis-py and degrades according to an explicit policy, which we return to in the failure-mode section.

import time, redis

r = redis.Redis(host="rl-redis", port=6379, socket_timeout=0.02)
GCRA = r.register_script(open("gcra.lua").read())

def check(key: str, rate_per_min: int, burst: int, cost: int = 1,
          fail_open: bool = True):
    t_ms = 60_000 / rate_per_min
    tau_ms = (burst - 1) * t_ms
    try:
        allowed, extra = GCRA(keys=[f"rl:{key}"], args=[t_ms, tau_ms, cost])
    except (redis.TimeoutError, redis.ConnectionError):
        return (True, None) if fail_open else (False, 1000)
    if allowed:
        return True, int(extra)          # remaining units
    return False, int(extra)             # retry after milliseconds

The 20 ms socket timeout is deliberate. A limiter on the request path must have a budget far below the request’s own latency target, otherwise a slow Redis becomes a slow API.

Sliding window counter in Lua

If you prefer the rolling-window contract, the two-counter estimate is also atomic in a script:

-- KEYS[1]=current window key, KEYS[2]=previous window key
-- ARGV[1]=limit, ARGV[2]=window ms, ARGV[3]=elapsed ms in current window
local limit, win, elapsed = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local cur  = tonumber(redis.call('GET', KEYS[1]) or '0')
local prev = tonumber(redis.call('GET', KEYS[2]) or '0')
local est  = prev * ((win - elapsed) / win) + cur
if est + 1 > limit then return {0, math.ceil(est)} end
redis.call('INCR', KEYS[1])
redis.call('PEXPIRE', KEYS[1], win * 2)
return {1, math.ceil(est) + 1}

Both keys must live in the same Redis Cluster hash slot or the script is rejected, so wrap the shared part of the key in braces, for example rl:{tenant42}:1728800400. Hash tags are the standard way to force co-location.

Envoy configuration

Local limiting is configured on the HTTP filter. The documented fields are a token_bucket with max_tokens, tokens_per_fill and fill_interval, plus filter_enabled and filter_enforced runtime fractions (Envoy local rate limit filter).

http_filters:
- name: envoy.filters.http.local_ratelimit
  typed_config:
    "@type": type.googleapis.com/envoy.extensions.filters.http.local_ratelimit.v3.LocalRateLimit
    stat_prefix: http_local_rate_limiter
    token_bucket:
      max_tokens: 200
      tokens_per_fill: 100
      fill_interval: 1s
    filter_enabled:
      runtime_key: local_rl_enabled
      default_value: { numerator: 100, denominator: HUNDRED }
    filter_enforced:
      runtime_key: local_rl_enforced
      default_value: { numerator: 100, denominator: HUNDRED }
    enable_retry_after_header: true

Note the split between enabled and enforced: setting enforced to 0 while enabled is 100 gives you a free dark launch, since requests are evaluated and counted but not blocked. Also note that by default the bucket is shared per Envoy process; the per-connection mode is a separate option.

The global filter points at the rate limit service. Per the docs, failure_mode_deny returns a 500 when the service errors if set to true; when false, errors let traffic through and are counted in a failure_mode_allowed stat.

- name: envoy.filters.http.ratelimit
  typed_config:
    "@type": type.googleapis.com/envoy.extensions.filters.http.ratelimit.v3.RateLimit
    domain: public_api
    failure_mode_deny: false
    rate_limit_service:
      transport_api_version: V3
      grpc_service:
        envoy_grpc: { cluster_name: ratelimit }

On the route you declare which descriptors to build, and on the service side the rule file maps them to limits:

# ratelimit config (envoyproxy/ratelimit format)
domain: public_api
descriptors:
  - key: api_key
    descriptors:
      - key: route
        value: orders_post
        rate_limit:
          unit: minute
          requests_per_unit: 600

The service supports units of second, minute, hour and day, a shadow_mode flag per rule, a local cache for keys already over limit, and a near-limit ratio statistic that defaults to 0.8 (envoyproxy/ratelimit README). The README does not describe a sliding window algorithm, so assume fixed-window semantics and its 2x boundary burst unless you verify your build otherwise. If you need GCRA or sliding windows behind Envoy, implement the same gRPC service yourself, since Envoy will talk to any implementation of the protocol.

Deeper Analysis: Consistency, Clocks, Hot Keys and Regions

The GCRA decision in one picture

Before the distributed concerns, it helps to hold the single-key logic in mind. The decision is one comparison against one stored timestamp, and the same branch yields the retry hint.

Figure 2: GCRA decision flow. One read, one comparison, one conditional write with a TTL.

The flow explains why GCRA is cheap to distribute. A denial performs no write, so abusive clients who hammer a limited key generate reads but not write amplification. That matters on a replicated store, where every write costs replication bandwidth.

Clock skew and time sources

GCRA and token buckets are functions of time. If each gateway passes its own wall clock into the algorithm, two gateways that disagree by 300 ms produce different TAT values for the same key, and the key can appear to jump backwards or forwards. At a rate of 10 requests per second, T is 100 ms, so 300 ms of skew is worth three requests of phantom credit or debt. NTP typically keeps well-run servers within milliseconds, but VMs paused during live migration or containers on overloaded hosts can drift far more.

The robust answer, which Brandur also recommends, is to take time from the data store. The Lua script above calls Redis TIME, so there is exactly one clock for all gateways. The cost is that Redis becomes a time authority, which is fine for a single primary but needs thought across failovers: a replica promoted with a clock behind the old primary can briefly accept requests that the old primary would have denied. For fixed and sliding window counters the issue is milder, because the window index is derived from time at the caller; use the store’s time there too, or accept that windows are skewed by the clock error, which only shifts boundaries.

Sharding, cells and the cost of a round trip

One Redis primary can serve on the order of tens to a couple of hundred thousand simple operations per second depending on hardware, pipeline depth and network; treat these as illustrative figures and benchmark your own deployment, because the count depends on script cost and TLS. Suppose a gateway fleet handles 60,000 requests per second and every request needs one global check. A single primary is already near its comfortable ceiling, and you have added a network hop of perhaps 0.3 to 1 ms inside a zone to every request.

Three techniques reduce this. First, shard by key: hash the limit key to one of N Redis primaries, so the load divides by N. Because each key’s state is independent, there is no cross-shard coordination, which is why rate limiting shards so cleanly. Second, apply the local tier first so that obviously over-limit traffic never reaches the global tier; Envoy’s local filter exists for this reason. Third, cache negatives: once a key is over limit until a known time, remember that in process. The envoyproxy/ratelimit service does this with a local cache of over-limit keys, avoiding repeated Redis reads for a key that is already blocked.

A fourth technique is batching with leases: a gateway asks the global tier for a lease of k units for a key and spends them locally. With k = 10 against a 600 per minute key, the global call rate for that key falls tenfold. The price is accuracy: up to (instances x k) units may be in flight on gateways, so choose k small relative to the limit. This is the same bargain eventually consistent counters make everywhere: less coordination, bounded over-admission.

Hot keys

Sharding by key fails when one key is the load. A single tenant sending 40,000 requests per second hammers one shard no matter how many you have. Symptoms are one Redis CPU pegged near 100% while the others idle, with latency tail spikes on exactly the requests that need the answer most.

The mitigations form a ladder. Place a strict local limit ahead of the global check for the offending key, so most of its excess dies at the proxy. Split the key into N sub-counters (cells) such as tenant42#0 to tenant42#7, give each a limit of limit/N, and route each request to a random or round-robin cell; a miss on one cell can retry on another. This scales one logical limit across N shards at the cost of fragmentation: with N = 8 and a limit of 800, a cell denies at 100 even if the others have room, unless you retry a second cell. Or move the key to a leased model as described above. For known enterprise tenants, a dedicated Redis or a purely local limit with a generous share is often the pragmatic answer.

Multi-region

Cross-region synchronous counting is rarely worth it. A 70 ms round trip between continents would sit in every request path, and a partition would force the fail-open or fail-closed decision on a regional scale. The common patterns:

Regional quotas. Split a global limit into per-region allowances (for example 60/30/10 percent by historical traffic) and enforce each locally. Simple, fast, and wasteful when traffic shifts.
Asynchronous reconciliation. Each region enforces locally and periodically exchanges consumed counts, then adjusts local budgets. The global limit may be exceeded by roughly (sync interval x regional rate) in the worst case, a bound you can compute and state.
Home-region pinning. Route each tenant’s traffic, or at least its limit checks, to a single home region. Accurate, but cross-region requests pay latency.

Eventually consistent counters (CRDT G-counters, for instance) fit pattern two naturally because counts only grow within a window. Whichever you choose, document the over-admission bound in the API contract so customers and on-call engineers share the same expectations.

Figure 4: Failure policy by endpoint class, then hot-key handling. The metric emission step is not optional.

Responses: 429, Retry-After and the RateLimit Headers

A rejected request should return HTTP 429 Too Many Requests, defined in RFC 6585, with a Retry-After header. Clients that receive 429 without guidance tend to retry immediately and amplify load. Be careful that retry hints do not synchronise clients: the IETF draft itself notes that Retry-After and the effective window can cause many throttled clients to return at the same moment, so add jitter to the value you emit or recommend client-side jitter.

There is no final standard for quota headers yet. The IETF HTTPAPI working group’s RateLimit header fields draft was at version 11, dated 23 May 2026, still an Internet-Draft expiring in November 2026 (draft-ietf-httpapi-ratelimit-headers). It defines two fields. RateLimit-Policy advertises the quota policy, with parameters q (quota, required), qu (quota unit, default requests), w (window in seconds) and pk (partition key). RateLimit reports current state, with r (remaining quota, required), t (seconds until the effective window resets) and pk. An example shape is RateLimit-Policy: "burst";q=100;w=60 with RateLimit: "burst";r=72;t=25. When both Retry-After and the effective window are present, the draft says clients should give Retry-After precedence.

In practice, many APIs still ship the older de facto names. GitHub, for example, uses x-ratelimit-limit, x-ratelimit-remaining, x-ratelimit-used, x-ratelimit-reset (UTC epoch seconds) and x-ratelimit-resource, and returns 403 or 429 for both primary and secondary limit violations; for secondary limits it instructs clients to honour retry-after if present, otherwise wait at least a minute and then back off exponentially. The lesson: emit what clients can act on today, and plan the migration to the standard names once the draft stabilises, possibly emitting both during the transition. Since a draft can change, do not hardcode its syntax into SDKs without a version switch.

Retries interact with limits in a way that deserves its own design step. A client that retries a POST after a 429 may duplicate work if the first attempt partly succeeded elsewhere; pair rate limiting with idempotency keys so that retried writes are safe. Our guide to idempotent API design covers the key lifecycle, and the two features together are what let you tell clients “retry freely”.

Weighted and Token-Based Limits for LLM APIs

Request counts are a poor unit for LLM workloads. One request may carry 200 tokens and the next 120,000, with output length unknown until generation finishes. Providers therefore limit on several axes at once: requests per minute and tokens per minute, and often separate input and output budgets. This is the cost-weighted idea GitHub applies with points, taken further.

The core difficulty is that the cost is only partly known at admission time. A workable design uses reserve then settle. At admission, estimate cost as input tokens plus a bounded max_output_tokens, reserve that many units from the bucket, and admit if available. After the response, compute the true usage and refund the difference. With GCRA this is natural: advance TAT by estimated cost x T at admission, then move it back by (estimate – actual) x T on completion, never below now. The unused reservation is released promptly, so conservative estimates do not starve a client for long.

A second axis is concurrency. Token rate does not bound GPU time when requests stream for minutes, so add a concurrent-request limiter (Stripe lists one among its four types) implemented as a counter incremented on start and decremented on finish, with a TTL to recover from crashed workers that never decrement. If you route among several models or providers, the limiter must be applied per upstream as well as per tenant, because each upstream has its own quota. We discuss routing and fallback in LLM model routing architecture. A fair-share scheme, where a tenant’s weight scales its share of a pooled token budget, avoids one batch job starving interactive users.

Capacity Planning, With Illustrative Numbers

Treat the following as a method; substitute your measurements.

Memory. GCRA stores one integer per key. Allow roughly 100 bytes per key including Redis key and expiry overhead (the real figure depends on key length and version, so measure with MEMORY USAGE). At 5 million active keys that is about 500 MB. A sliding log with 100 entries per key would be hundreds of times larger. TTLs bound growth: each key expires when its TAT has passed, so memory tracks active, not total, keys.

Operations. If the fleet serves 30,000 requests per second, the local tier rejects 10 percent, and 60 percent of the remainder needs a global check on at least one descriptor with an average of 1.5 descriptors per check, then the global tier sees about 30,000 x 0.9 x 0.6 x 1.5 = 24,300 script calls per second. Divided across four primaries that is about 6,000 each, comfortably inside the range most deployments sustain, and leaving headroom for failover. Add the latency budget: at 1 ms p99 per check and a gateway timeout of 20 ms, you have a 20x safety factor before the limiter hurts users.

Network. Each call is a few hundred bytes. At 24,300 calls per second and about 300 bytes round trip, bandwidth is roughly 7 MB/s. Negligible, but connection pools matter: the envoyproxy/ratelimit README lists a default per-second Redis pool size of 10, so check pool settings against your concurrency rather than assuming defaults suffice.

Failover. A Redis primary failover typically loses writes not yet replicated. For a rate limiter this means counters may rewind by up to the replication lag, a short window of over-admission. That is usually acceptable, and it argues against paying for synchronous replication on this data.

Trade-offs, Gotchas, and What Goes Wrong

Fail open or fail closed? This is the most consequential policy choice. Fail open, as Stripe describes, keeps the API available when the limiter or Redis breaks, at the cost of losing protection exactly when the system may already be stressed. Fail closed protects the backend but turns a limiter outage into an API outage; in Envoy, failure_mode_deny set to true returns a 500 on service error. A sound compromise is by endpoint class: fail open for ordinary reads while falling back to the local bucket, fail closed for expensive or abuse-prone operations such as credential checks or bulk exports. Whatever you choose, emit a metric on every degraded decision and alert on it. Envoy exposes failure_mode_allowed for this.

Retry storms. A limiter that rejects is itself traffic: clients retrying a 429 at full speed can consume the proxy and the rate limit service. Cap the work done per rejected request, and use exponential backoff with jitter on the client.

Identity problems. Limiting by IP penalises carrier-grade NAT users and misses botnets with many addresses. Limiting by API key misses unauthenticated abuse. Layer both, and treat X-Forwarded-For with care since a client can forge it unless your edge overwrites it.

Boundary and burst surprises. Fixed windows allow 2x bursts at boundaries, and token buckets allow B above the sustained rate over any interval. Document the burst contract so customers do not discover it by accident.

Key explosion. Unbounded key spaces, such as limiting by arbitrary query string or by random header, create memory pressure. Always set TTLs, and limit the cardinality of the descriptors you allow.

Silent misconfiguration. A wrong unit or a shared domain name between services can make a limit ten times too tight or loose. Use shadow mode and dark launches first, which both Stripe and the Envoy tooling support, and review near-limit statistics before enforcing.

Thundering herd at reset. If every client is told to retry at the top of the minute, you create a synchronised spike. Prefer token bucket or GCRA, whose retry times are continuous, and add jitter to fixed-window resets.

Practical Recommendations

Start with the contract, then pick the algorithm. If customers need “N requests per window” in the docs, a sliding window counter or a fixed window with a stated boundary caveat is enough. If you need burst control and cost weighting, use GCRA or a token bucket. Keep all counters in one atomic script per key, and read time from the store.

Build the two tiers deliberately. Put a local token bucket in every proxy sized as a generous per-instance backstop, and put the exact quota in the global tier. Shard the global tier by key, set a strict timeout well under your latency objective, and keep keys short with TTLs.

Decide failure policy per endpoint class before the first incident, and wire the metrics that tell you when it triggers. Dark launch every new rule in shadow mode and review what it would have blocked.

Checklist:

Atomic operation per decision (Lua script or INCR), never read-modify-write.
Store clock as the single time source.
Local tier before global tier; negative caching for blocked keys.
Cost-weighted units for expensive endpoints and LLM tokens, with reserve and settle.
429 with Retry-After and jitter; RateLimit headers documented, with a version switch.
Idempotency keys on retried writes.
Fail-open or fail-closed chosen per endpoint, with alerts on degraded decisions.
Hot-key plan: local cap, cell splitting or leases.
Documented over-admission bound for multi-region.
Shadow mode and a kill switch for every rule.

Frequently Asked Questions

What is distributed rate limiting?

Distributed rate limiting enforces a single usage limit across many servers, proxies or regions rather than per process. A shared store or coordination layer holds each caller’s state so that forty gateway instances count the same caller together. It usually combines a local in-proxy limiter for speed with a global limiter, often Redis, for accurate cross-instance quotas.

Is GCRA better than token bucket?

They enforce the same contract, so neither admits more traffic in steady state. GCRA stores one timestamp per key and computes an exact retry delay on denial, which simplifies Redis scripts and variable-cost requests. A token bucket is easier to explain and to expose as a remaining-tokens number. Choose GCRA for minimal state, token bucket for customer-facing quota semantics.

How do you implement a Redis rate limiter safely?

Use a single Lua script or atomic INCR so the check and update cannot interleave, and read time from Redis TIME rather than from callers. Set a TTL on every key, use hash tags so related keys share a cluster slot, apply a short client timeout, and decide explicitly whether to fail open when Redis is unreachable.

Does Envoy support global rate limiting?

Yes. Envoy integrates with an external gRPC rate limit service, and any service implementing the protocol works; the reference implementation is written in Go and uses Redis. Envoy also ships a separate local rate limit filter using a token bucket. The docs describe the local filter as applied first, with the global service finishing the job.

Should a rate limiter fail open or closed?

It depends on the endpoint. Fail open for general traffic so a limiter outage does not become an API outage, as Stripe describes doing, but fall back to a local bucket and alert. Fail closed for expensive or security-sensitive operations. In Envoy the choice is the failure_mode_deny setting, and the failure_mode_allowed stat counts requests let through.

How do I rate limit LLM APIs by tokens?

Count tokens, not requests. Reserve an estimate at admission (input tokens plus a capped maximum output), then settle against actual usage once the response completes, refunding the difference. Add a concurrency limiter because long streaming responses consume capacity that a per-minute token budget does not capture, and apply limits per upstream model as well as per tenant.