Design a globally distributed rate limiter

The obvious design is a single Redis in one region that every region calls. It is exact, but a Frankfurt request pays ~120 ms per check and every region depends on one region's availability, so a Mumbai outage turns into a worldwide rate-limiting outage. Strongly consistent global stores (Spanner, CockroachDB, DynamoDB global tables with conditional writes in one home region) have the same latency problem. The practical answer is local enforcement with asynchronous coordination. Option 1, quota splitting: the global limit L is divided into regional shares, initially by recent demand (e.g. Mumbai 55%, Hyderabad 25%, Singapore 15%, Frankfurt 5%); each region enforces its share exactly and locally. Coordinators recompute shares every few seconds from observed demand plus a small minimum floor, so a region with a sudden burst gets more within seconds. Option 2, shared view: each region enforces against the full limit but subtracts the latest known usage of other regions (a grow-only counter per region per window, merged like a CRDT G-counter). Option 2 adapts instantly to traffic shifts but overshoots by up to rate × sync interval × other regions; option 1 never overshoots but can wrongly reject when demand moves faster than rebalancing. Many systems combine them: shares as the base, plus borrowing from peers' unused share.

Request limits are easy because each request costs 1. LLM token limits are harder: the prompt size is known before the call, but the output size is only known when the response ends, which may be 30 seconds later, and streaming responses can be cancelled midway. If you only count after the response, a burst of 500 parallel requests all pass the check before any of them is charged. If you reserve max_tokens, you reject legitimate traffic, since max_tokens is often 4-10x the real output. The usual pattern is reserve-then-settle: at admission, reserve prompt tokens plus an estimate of the output (the p90 output for that feature or model, or a fraction of max_tokens), which bounds concurrency honestly. When the provider returns usage (in the final streaming chunk), settle: refund the unused part or charge the extra, which can push the bucket negative, so the next requests wait. Reservations carry a TTL so a crashed gateway does not leak capacity forever. Also add a concurrency limit (max in-flight streams per tenant), because tokens per minute alone does not stop one tenant from opening 5,000 slow streams. Always bill from the provider's reported usage, not your estimate.

A rate limiter is on the path of every request, so its failures must be designed, not discovered. Slow Redis is worse than dead Redis: if the limiter waits 200 ms per check, the API slows down for everyone. So every call has a strict timeout (2-5 ms), and a circuit breaker stops calling Redis after repeated failures. What to do then is a policy per limit, documented in an ADR. Fail open (allow) protects availability but removes protection, acceptable for general quotas over a few minutes. Fail closed (reject) is right where abuse costs money or security: OTP sends, login attempts, payouts. The common middle ground is a local in-process token bucket per instance, with capacity = share ÷ instance count, which keeps the worst abuse in check without any network. When regions lose contact with each other, each region keeps enforcing its last known share and coordinators stop moving shares; since the shares sum to the global limit, the global total cannot exceed L even during the partition, but a tenant whose traffic shifts may be limited too early. With the shared-view approach a partition instead causes overshoot, bounded by each region's own share. Make the system observable: fallback-mode count per region, overshoot estimate per tenant, sync lag.

Splitting guarantees the global sum and keeps each check purely local, but may reject traffic that moves quickly between regions. Shared counters with gossip follow traffic instantly but overshoot during bursts and partitions. Use splitting for hard limits tied to cost (LLM token budgets tied to a provider contract) and shared counters for soft fairness limits.

A central service per region (like Envoy's global rate limit service) keeps logic in one place but adds a network hop. A library that talks to Redis directly saves the hop and is easier to keep under 1 ms, but must be maintained in every language. With most traffic through a gateway and an LLM gateway, an in-gateway library is the pragmatic choice.

Token bucket allows controlled bursts and naturally supports cost-weighted takes; GCRA stores just one timestamp per key and is equivalent in behaviour (used by redis-cell); sliding window counters suit 'N per minute' quotas. For token budgets per minute plus burst control, token bucket with lazy refill in Lua is the simplest correct choice.

A tenant doing 50k checks/s overloads its shard. Batch locally: each instance takes a lease of N tokens (e.g. 1% of its share) from Redis and spends it in memory, returning unused tokens on expiry. This cuts Redis calls by 10-100x at the cost of small inaccuracy.

Syncing every tenant every second does not scale to millions of keys. Sync only active keys (touched in the window), compress deltas, and sync large tenants more often than small ones whose overshoot does not matter.

That region keeps enforcing its current shares (stored in Redis), which remain valid. Shares stop adapting until a standby coordinator takes over via leader election (a lease in Redis or etcd); no request-path impact.

Each Lua script uses its own Redis server time, and sync messages carry window ids and sequence numbers rather than wall-clock comparisons, so skew of a few hundred milliseconds only shifts window boundaries slightly.

Validate config (floors per plan), roll out new limits in shadow mode first (log would-be 429s), and keep the previous version for instant rollback.