Design a distributed rate-limiting service for an API Gateway cluster (40 stateless Envoy/Go/Java nodes) handling 400,000 global requests/sec across 10,000,000 active API keys. Each tenant has a configurable sustained rate (e.g., 100 req/s) and burst capacity (e.g., 250 tokens).
From patterns to decisions.
Design a distributed rate-limiting service for an API Gateway cluster (40 stateless Envoy/Go/Java nodes) handling 400,000 global requests/sec across 10,000,000 active API keys. Each tenant has a configurable sustained rate (e.g., 100 req/s) and burst capacity (e.g., 250 tokens).
Fixed Window allows 2x burst.
Fixed Window allows 2x burst spikes across window boundaries (e.g., 100 reqs at 00:59 + 100 at 01:00). Separate GET and SET calls create a TOCTOU race condition under concurrency.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Sliding Window Log is exact but stores a timestamp per request (high memory for 10M keys); Token Bucket uses O(1) memory per key. |
Step 1
Explain boundary burst problem in Fixed Window.
Step 2
Show how Token Bucket enforces smooth refill while allowing bounded burst capacity.
Step 3
Demonstrate the TOCTOU race when two gateways read tokens=1 concurrently.
Alternative 1
Sliding Window Counter (approximates sliding window in O(1) memory, but lacks explicit burst capacity tuning).
Failure Mode 1
Under 50 concurrent requests, non-atomic GET/SET allows up to 50x the intended burst.
# Broken non-atomic pattern (DO NOT USE in production):
tokens = float(redis.get(key) or capacity)
if tokens >= 1:
# Race window: 10 concurrent threads all pass this check!
redis.set(key, tokens - 1)
Production Redis Lua script using.
Production Redis Lua script using redis.call('TIME') for clock-skew immunity, lazy refill, and PEXPIRE auto-eviction, wrapped in a Python client with EVALSHA + NOSCRIPT fallback.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Lua script blocks the single Redis shard thread for ~3-5 microseconds, easily sustaining 80k+ RPS per shard. |
Step 1
Read server time via redis.call('TIME') inside Lua.
Step 2
Compute refilled = math.min(capacity, tokens + (elapsed_ms * rate) / 1000.0).
Step 3
Deduct cost if refilled >= cost, persist via HSET + PEXPIRE, and return [allowed, remaining, retry_after_ms].
Alternative 1
Redis Cell (CL.THROTTLE) module using Generic Cell Rate Algorithm (GCRA) in C.
Failure Mode 1
Passing client now_ms instead of redis.call('TIME') causes token drift across gateways with skewed clocks.
TOKEN_BUCKET_LUA = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate_per_sec = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])
local t = redis.call('TIME')
local now_ms = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local data = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(data[1])
local last_ts = tonumber(data[2])
if tokens == nil then
tokens = capacity
last_ts = now_ms
else
local elapsed_ms = math.max(0, now_ms - last_ts)
tokens = math.min(capacity, tokens + (elapsed_ms * rate_per_sec) / 1000.0)
last_ts = now_ms
end
local allowed = 0
local retry_after_ms = 0
if tokens >= cost then
tokens = tokens - cost
allowed = 1
else
retry_after_ms = math.ceil(((cost - tokens) / rate_per_sec) * 1000)
end
local ttl_ms = math.ceil((capacity / rate_per_sec) * 2000)
redis.call('HSET', key, 'tokens', tostring(tokens), 'ts', tostring(last_ts))
redis.call('PEXPIRE', key, ttl_ms)
return {allowed, math.floor(tokens), retry_after_ms}
"""
Centralized 1-RTT Redis Lua is.
Centralized 1-RTT Redis Lua is simpler and strictly accurate at 400k RPS across 8 shards; local-quota batching is needed only when scaling past 2M+ RPS or across multi-region WAN links.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Centralized checking adds ~0.8 ms network RTT per request vs ~0.01 ms for local batching. |
Step 1
Size 8 Redis shards for 400k RPS (~50k RPS/shard, < 1 ms p99).
Step 2
Show how local batching reduces Redis QPS 10x but breaks strict small-limit enforcement (e.g., 5 req/min).
Step 3
Choose centralized Redis Lua + L1 deny-cache for single-region, or local batching for multi-region.
Alternative 1
Envoy Global Rate Limit gRPC service with local memory batching.
Failure Mode 1
Batching 10 tokens locally when a tenant's limit is 5 req/s allows up to 400 req/s across 40 nodes.
def check_rate_limit(redis_client, sha: str, api_key: str, cap: int, rate: float, cost: int = 1):
key = f"rl:{{{api_key}}}"
try:
allowed, rem, retry_ms = redis_client.evalsha(sha, 1, key, cap, rate, cost)
except Exception as e:
if "NOSCRIPT" in str(e):
allowed, rem, retry_ms = redis_client.eval(TOKEN_BUCKET_LUA, 1, key, cap, rate, cost)
else:
raise
return bool(allowed), int(rem), int(retry_ms)
An L1 in-memory deny-cache on.
An L1 in-memory deny-cache on each gateway intercepts repeated requests for an already-throttled key for min(100 ms, retry_after_ms), cutting Redis traffic on that hot key by > 99%.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | L1 deny-cache can over-block by up to 100 ms even if another process hadn't consumed, which is negligible on an already-exhausted bucket. |
Step 1
Check local deny_cache.get(api_key) before calling Redis.
Step 2
On Redis allowed == 0, store blocked_until = monotonic_ms + min(100, retry_after_ms).
Step 3
Wrap Redis calls in a 3 ms timeout + circuit breaker falling back to local rate/40 bucket.
Alternative 1
Edge WAF / Cloudflare rate limiting in front of the API gateway.
Failure Mode 1
Unbounded l1_deny dict without LRU eviction leaks memory under random-key DDoS.
import time
class GatewayRateLimiter:
def __init__(self, redis_client, sha: str, num_nodes: int = 40):
self.redis = redis_client
self.sha = sha
self.num_nodes = num_nodes
self.l1_deny: dict[str, float] = {} # api_key -> blocked_until_ms
def allow(self, api_key: str, cap: int, rate: float) -> tuple[bool, int]:
now = time.monotonic() * 1000.0
if self.l1_deny.get(api_key, 0.0) > now:
return False, 100
try:
ok, rem, retry_ms = check_rate_limit(self.redis, self.sha, api_key, cap, rate)
if not ok:
self.l1_deny[api_key] = now + min(100.0, float(retry_ms))
return ok, retry_ms
except Exception:
# Fail-open with local fallback or allow; here fail-open on Redis timeout
return True, 0
Each region runs a local.
Each region runs a local Redis Cluster enforcing regional quotas, while an asynchronous gossip/CRDT sync worker periodically redistributes unused token budgets across regions based on traffic share.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Avoids 80-150 ms cross-ocean RTT on every API call at the cost of 1-second eventual consistency. |
Step 1
Keep the hot path strictly intra-region (< 1 ms) using regional Redis Clusters.
Step 2
Split global quota across regions dynamically via a 1-second async quota-rebalancer (CRDT PN-Counter or central coordinator).
Step 3
Accept bounded eventual consistency (e.g., < 5% overshoot during sudden cross-region failover).
Alternative 1
Geo-pinning tenants to a home region so all requests for tenant X route to one Redis cluster.
Failure Mode 1
If cross-region sync stalls, each region must cap at a safe static fallback fraction to avoid 3x global overload.
# Async regional quota allocation: weight regional rate by trailing 10s traffic share
def allocate_regional_rates(global_rate: float, regional_rps: dict[str, float]) -> dict[str, float]:
total = sum(regional_rps.values()) or 1.0
return {region: max(global_rate * 0.1, global_rate * (rps / total)) for region, rps in regional_rps.items()}
Theory & Tips and Tricks
Practical heuristics & interview traps
- 01Interview anchor: A single atomic Redis Lua script eliminates read-modify-write race conditions and cuts network round-trips from 2 to 1, keeping rate-limiter p99 overhead under 1.5 ms.
- 02Trade-off tip: Centralized checking adds ~0.8 ms network RTT per request vs ~0.01 ms for local batching.
- 03Watch out for: Unbounded
l1_denydict without LRU eviction leaks memory under random-key DDoS.
Design Token Bucket Rate Limiter — Normal → Load / Fault → Recovery
A single atomic Redis Lua script eliminates read-modify-write race conditions and cuts network round-trips from 2 to 1, keeping rate-limiter p99 overhead under 1.5 ms.
Putting Design a Token Bucket Rate Limiter Together
A single atomic Redis Lua script eliminates read-modify-write race conditions and cuts network round-trips from 2 to 1, keeping rate-limiter p99 overhead under 1.5 ms.
Putting Design a Token Bucket Rate Limiter Together
- Read server time via
redis.call('TIME')inside Lua. - Compute
refilled = math.min(capacity, tokens + (elapsed_ms * rate) / 1000.0). - Deduct
costifrefilled >= cost, persist viaHSET+PEXPIRE, and return[allowed, remaining, retry_after_ms].
Interview Readiness Check
An L1 in-memory deny-cache on each gateway intercepts repeated requests for an already-throttled key for min(100 ms, retry_after_ms), cutting Redis traffic on that hot key by > 99%.
Walk through bottlenecks, back-of-the-envelope math, and failure recovery.
Make the trade-off yourself.
Practice Check
Test your understanding
Why are standard Redis GET and SET operations unsafe for implementing API rate limiting across multi-threaded gateway nodes?
Design a Token Bucket Rate Limiter
A single atomic Redis Lua script eliminates read-modify-write race conditions and cuts network round-trips from 2 to 1, keeping rate-limiter p99 overhead under 1.5 ms.
