32. Distributed Rate Limiter

Business context. A public API platform. Rate limits protect availability (one customer can't take everyone down), enforce pricing tiers (free: 100 req/min, pro: 10k), and limit abuse cost (scraping, credential stuffing).

Requirements. Limits per API key, user, IP, and endpoint; multiple windows (per second and per day); < 2 ms overhead; accurate within a few percent; fail open for paying customers if the limiter is down (a business decision: availability over strict enforcement); 1M+ req/s across the fleet.

Algorithms.

Design.

Client → Edge/API gateway ──(check)──▶ Local limiter (in-process token bucket, per-instance share)
                                  └──▶ Redis cluster (global counters, Lua script for atomicity)
Rules: config service → pushed to gateways (cached locally; changes propagate in seconds)

Atomic token bucket in Redis (Lua):

-- KEYS[1] = bucket key; ARGV = capacity, refill_per_sec, now_ms, cost
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local cap, rate, now, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])
local tokens = tonumber(b[1]) or cap
local ts = tonumber(b[2]) or now
tokens = math.min(cap, tokens + (now - ts) / 1000 * rate)
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(cap / rate * 1000) * 2)
return { allowed and 1 or 0, tokens }

Deep dives.

• Latency vs accuracy: a Redis round trip on every request costs about 0.5–1 ms and makes Redis a hard dependency. The hybrid: each gateway holds a local bucket and periodically syncs usage to the global store (approximate, but with no network hop per request). Use exact global checks only for low-limit, high-value keys (login attempts).
• Hot keys: one huge customer key hammers one Redis shard. Split that customer's budget across N sub-keys, or use the local-allocation approach.
• Multi-region: enforce per region with the global limit divided proportionally, or accept approximately N× overshoot. Explain which one the business can tolerate.
• Fail-open vs fail-closed: fail open for normal API traffic (availability), fail closed for security limits (login, OTP).

Strategic lens. Rate limiting is product policy encoded in infrastructure. Rules belong to product (tiers), security (abuse), and SRE (protection), so build one engine with layered policies and clear ownership, plus customer-facing headers and dashboards so customers can self-diagnose (fewer support tickets).

Follow-ups: cost-based limits (a heavy query costs 10 tokens); concurrency limits vs rate limits; adaptive limits (lower everyone's limits when the backend is unhealthy); how quickly a rule change propagates.

🏗️ Flow: layered limits at the edge.

 Request ─▶ Edge PoP: per-IP / per-ASN coarse limits (DDoS, scraping) — counted locally per PoP
        ─▶ API gateway:
              1. identify key (API key → account, tier) from cached key store
              2. local token bucket (fast path, per gateway instance share)
              3. global check (Redis Lua) only for: low limits, expensive endpoints, auth endpoints
              4. concurrency limiter (in-flight per account) for CPU-heavy endpoints
        ─▶ Service: fleet load shedder (priority-based) when utilization > threshold
 Reject: 429 + RateLimit-Limit/Remaining/Reset headers (+ Retry-After)

🌍 How it's built in production.

• Stripe runs four layers (§14.5): request rate limiter (token bucket in Redis), concurrent-requests limiter, fleet usage load shedder, and worker utilization load shedder. The last two are about protecting the system, not enforcing pricing.
• Lyft / Envoy global rate limit service: Envoy sidecars call a central rate-limit service (backed by Redis) with descriptors (domain, key, value). Rules live in config, and enforcement is distributed.
• Cloudflare (2017, "How we built rate limiting capable of scaling to millions of domains"): counts per PoP with a sliding-window approximation (previous window count × overlap fraction + current count), which avoids a global store on every request.
• GitHub GraphQL: limits by computed query cost (points) instead of request count, because one GraphQL request can cost 1 or 10,000 units of work.

⚠️ Corner cases.

• Clock skew between gateways: token-bucket refill uses now. Use the Redis server time inside the Lua script (TIME) rather than each client's clock.
• IPv6: each user can have huge numbers of addresses. Limit per /64 (or /48) prefix, not per /128.
• NAT and carrier-grade NAT: thousands of legitimate users share one IPv4 address (offices, mobile carriers). Prefer authenticated keys, and use IP limits only as a coarse abuse guard with high thresholds.
• Retries counting against the limit: a client retrying 429s without backoff burns its own budget. Return Retry-After, and document client backoff.
• Key cardinality explosion: per-IP keys during a botnet attack create millions of Redis keys. Use TTLs, approximate structures (count-min sketch) for detection, and edge-level blocking.
• Multi-tenant fairness: a tenant with 10,000 API keys multiplies its limit. Apply hierarchical limits (key ≤ account ≤ organization).