Distributed Rate Limiting: Token Bucket, Redis Lua, Multi-Region (2026)

Q: Which rate limiting algorithm should I pick for a production API?

For most user-facing APIs, the token bucket algorithm is the right default: it allows controlled bursts (up to the bucket capacity) followed by sustained rate enforcement at the refill rate, which matches how real traffic is actually shaped. For tight per-second limits where the boundary burst of fixed window is unacceptable, use sliding window counter (weighted across the previous and current window) — it is O(1) memory per identity, accurate within a few percent, and dominates production deployments. Use leaky bucket only when the downstream cannot absorb bursts at all and the queueing latency is acceptable. Use fixed window for coarse limits (per-day, per-month quotas) where simplicity is worth the boundary artefact. Sliding window log is rarely the right choice — it is exact but its O(N) memory cost grows with the limit size and the identity count. The single most common failure is using one algorithm for all limits; pick per-limit based on the use case, not globally.

Q: Why is Redis with Lua the standard implementation for distributed rate limiting?

Three properties make Redis with Lua scripts the dominant choice. First, latency: a warm Redis Lua call sits at 0.3-0.8 ms p50, which fits inside the request hot path; SQL or general-purpose data stores are far too slow. Second, atomicity: a Lua script runs atomically inside the Redis server — read state, compute decision, write new state, return result, all in one indivisible operation, so concurrent requests cannot race and bypass the limit. Pipelined commands without Lua are not enough; two concurrent GET-then-INCR sequences can both read N and both pass the check. Third, shared state across application instances: the limit is enforced globally across all application replicas, not per-instance. Memcached lacks the data structures and atomicity; in-memory counters cannot share state. Always store the Lua script by SHA, load it at startup with EVALSHA, version it, and never edit a deployed script — deploy a new version and switch over.

Q: How do I handle hot keys when one customer has 100x more traffic than the others?

Three solutions, often combined. (1) Sub-key sharding: instead of one key per heavy customer, split into 16-64 sub-keys (e.g. customer:42:shard:0 through customer:42:shard:15) and have the application hash the request to a sub-shard. Per-sub-shard limit is set to global_limit / shard_count. Throughput distributes across many keys (and likely many Redis shards). The trade-off is approximate enforcement — worst-case a few percent over the limit if traffic is unevenly distributed across application instances. (2) Cell-based isolation: dedicated application pool and dedicated Redis for the top tenants (typical threshold: above 5% of global traffic). Their traffic cannot affect other tenants' limiter performance because they are physically separate. (3) Local pre-check: each application instance keeps a small local counter (global_limit / instance_count) that allows requests without consulting Redis until exhausted. Auto-promote heavy keys to sharding based on observed throughput; do not wait for the production incident to identify them.

Q: How does multi-region rate limiting work without unacceptable cross-region latency?

Three production patterns. (1) Cell-based local limits with proportional partitioning: divide the global quota across regions based on observed traffic distribution (e.g. 60% US-East, 30% US-West, 10% EU); each region enforces its share locally with regional Redis. No cross-region coordination on the hot path — every check is sub-millisecond. Reconcile quotas every 30-90 seconds based on observed usage. (2) Eventually-consistent global counter: each region checks locally for an immediate decision and asynchronously reports usage to a global aggregator; the aggregator computes true global usage with 1-5 second lag and pushes adjusted local quotas down. The most common production choice. (3) Sticky-region sharding: each identity has a home region; all their requests route there; limit is enforced only in the home region. No coordination needed; excellent accuracy. Trade-off is failover behaviour. Synchronous cross-region coordination on the hot path is never the right answer — 80-200 ms cross-region round trip on every API call is unacceptable.

Q: What should the rate limiter do when Redis is down or slow?

The decision should be per-limit, declared in configuration, not a global default. General API limits should fail open: when Redis is unavailable or the limiter call exceeds its deadline (typically 5-20 ms), allow the request through. Losing rate limiting is preferable to losing the service entirely — a Redis outage should not become a full platform outage. Authentication and security-critical limits should fail closed: deny when Redis is unavailable. Allowing unlimited login attempts during a Redis outage is a security incident even if the application tier is healthy. Always log the fail-open/closed event and emit a metric so the team knows the limiter is degraded. Set the limiter call deadline tightly (5-20 ms) so a slow Redis does not add latency to every request. The most common production mistake is having no deliberate policy at all — the limiter just throws when Redis errors, and the application returns 500 to every request.

Q: How do I prevent the limiter keys from leaking memory in Redis?

Always set a TTL on every limiter key. Without a TTL, every identity that ever made a request keeps a key forever — slow memory leak that becomes catastrophic at scale. For a per-minute window, use a TTL of 2-5 minutes. For token bucket, use a TTL of (capacity / refill_rate) plus a safety margin so an idle bucket eventually expires but an active one does not. The Lua script must reset the TTL on every accepted request (using EXPIRE inside the script) so active identities keep their state and inactive ones are reclaimed. Configure Redis maxmemory and an eviction policy as a safety net (allkeys-lru is usually wrong for a limiter; volatile-lru combined with TTLs on every limiter key is correct — only TTL'd keys are eligible for eviction, so non-limiter data is preserved). Monitor Redis used_memory and key count per pattern; the count should plateau, not grow linearly with time.

Q: What is the race condition in naive rate limiter implementations?

The classic bug is GET key, check (count < limit), INCR key as separate operations. Two concurrent requests both read the current count N (which is below the limit), both decide they pass the check, both INCR the key (to N+1 and N+2), and both are accepted — even though only one should have been allowed by the limit. The race window is small but frequent in high-throughput systems; a 10,000 req/s limit can be exceeded by 5-15% under sustained concurrent load. Pipelining the commands does not fix it because the GET still reads stale state before the INCR commits. The fix is atomicity: either use INCR first and then check the returned value (INCR returns the post-increment count, so checking it for limit+1 is race-free for simple counters), or use a Lua script that does the entire read-decide-write-return cycle inside Redis as a single atomic operation. Lua is required for non-trivial algorithms (token bucket, sliding window counter, leaky bucket) where the decision logic is more complex than a single INCR.

Q: How do I rate-limit AI/LLM API calls where each request has different cost?

AI rate limits typically have two dimensions: requests per time window (RPM) and tokens per time window (TPM). Use two separate token-bucket limiters per identity: one with refill rate equal to the customer's RPM allowance and capacity equal to a small burst (10-50), one with refill rate equal to the TPM allowance and capacity equal to a meaningful working-set size (often equal to one request's maximum context). On each request, estimate the token cost (input tokens are countable up-front; output tokens are estimated from max_tokens or from historical averages for the prompt class), check both buckets, deduct from both if both pass. After the call completes with the actual token count, reconcile the difference (either give tokens back if you over-deducted or charge the additional tokens if the response was longer than estimated). Multi-region coordination uses the same proportional quota allocation as for API limits. Hot tenants get sub-key sharding or cell isolation. The composition with category-aware guardrails works the same way — different categories may have different bucket parameters reflecting different cost profiles.

Q: When should I use cell-based isolation instead of sub-key sharding for heavy customers?

Sub-key sharding is the lighter-weight solution: it distributes limiter throughput for one heavy key across multiple Redis sub-keys, but the customer's requests still share application instances and Redis nodes with everyone else. It works well for customers who are 10-100x average but not catastrophically large. Cell-based isolation — dedicated application pool, dedicated Redis instance per heavy customer — is the heavyweight solution and is justified when (1) the customer is above roughly 5% of global traffic on their own, where their behaviour can affect platform-wide latency for other tenants; (2) the customer has SLA commitments that demand independence from noisy-neighbour effects; (3) the customer's traffic patterns are pathologically bursty in a way that is hard to shape with general-purpose limits. Cell isolation costs more per customer (dedicated infrastructure) but provides the strongest isolation. Most production platforms use sub-key sharding for the top 50 customers and cell isolation only for the top 5-10. The two patterns compose: cells can use sub-key sharding internally for further isolation.

Q: What are the most common production failures of distributed rate limiters?

Five recurring failure modes. (1) Hot-key Redis CPU saturation: one customer's key receives 100x normal traffic, the Redis shard holding that key saturates CPU, latency spikes for everyone sharing the shard. Fix: sub-key sharding plus hot-key detection that auto-promotes. (2) Cross-region quota leakage: each region has its own Redis with no coordination, so a customer can exceed their global limit by hitting multiple regions in parallel. Fix: proportional regional quotas plus periodic reconcile, or sticky-region routing. (3) Race conditions in non-atomic implementations: GET-then-INCR allows a few percent of requests to bypass the limit under load. Fix: atomic Lua scripts. (4) Memory leak from missing TTLs: limiter keys accumulate forever, Redis runs out of memory, evictions corrupt limit state. Fix: always set TTL, reset on accepted requests. (5) Fail-open by accident during Redis outages: limiter just allows everything when Redis errors, the application tier gets hammered just when it can least cope. Fix: deliberate fail-open/closed policy per limit, with metrics and alerts on the fail-open event rate.