Design a Rate Limiter

• Cap requests per client per time window
• Protects backends from abuse, overload and noisy neighbours
• Decision per request: allow or reject, before the backend is touched

• Configurable rules: client, endpoint, limit, window
• Return 429 with Retry-After when rejected
• Rule changes go live without redeploy
• Example tiers: free 100/min per API key, paid 1,000/min, login 5/min per IP

• Enforce at the edge: rejected traffic never reaches the backend
• Local in-process check first (cheap, no network)
• Redis check second, only when the local check passes
• Reject answers 429 straight from the gateway

• Bucket holds up to B tokens (capacity), refilled at R tokens/s
• Each request takes 1 token; empty bucket means reject with 429
• Allows bursts up to B, then settles to R req/s

• Key = client:floor(now/window), so every request in one window hits the same counter
• Per request: INCR the key, and EXPIRE it on the first hit
• O(1) memory: one integer per client, the simplest algorithm
• Reject once the count passes the limit, e.g. 100/min

window = floor(now / 60)
key   = "u42:" + window
count = INCR key
if count == 1: EXPIRE key 120
allow = count <= 100

limit 100/min, TTL 2 × window

• Schema: rl:{client_id}:{rule_id}:{window_start}
• Wrap only client_id in braces: it is the hash tag
• Redis Cluster hashes the first {...} pair only
• So all of one client's keys share a slot and one shard

• Limit 100/min is checked by 50 gateways at the same time, so reads and writes interleave
• A GET then SET is two round trips: nothing stops another node from slipping in between
• Result: every lost update lets one extra request through; under load the overshoot grows

• Order: API key → user ID → IP
• IP is only the fallback for anonymous traffic
• Rule = (key, endpoint, limit, window), looked up per request

• Reject with 429 Too Many Requests
• Never 503 (looks like an outage) and never 403 (looks like a permission failure)
• Send the headers on every response, so clients can slow down before they hit 429

• Exact counts: every gateway updates one shared counter
• Cost: one network hop, about 0.5 ms per request
• Redis becomes a hot dependency: 1M req/s peak all lands on it
• Fits the budget: under 2 ms p99 added latency

• Local counters sync with Redis every 100 ms: no hop per request
• Overshoot is up to nodes × local batch size

• Shard: 1M req/s ÷ 150k ops/s ≈ 7, so 8 masters sized for the uncached peak
• Only the 8 masters hold counters: about 250 MB each (2 GB total)
• Replicate: 1 replica per master for failover; replicas hold copies, not extra capacity
• Local cache: 80% fewer Redis calls leaves about 200k ops/s
• After the cache, 2 shards could carry the load; the other 6 are headroom for spikes and failover

• Token bucket: capacity B, refill rate R tokens/s, 1 token per request
• Lazy refill: tokens = min(B, tokens + (now - last) × R), no timer
• State is 2 numbers per key; burst friendly up to B
• Example: B=10, R=5/s lets 10 pass instantly, then 5 req/s
• Time comes from the server or Redis TIME, never the client

• Sliding counter: est = cur + prev × (1 - fraction)