Walkthrough: Distributed Rate Limiter

1. Requirements#

Functional

• Limit requests per client (API key, user ID, or IP) per rule, e.g. 100 req/min per user, 10 req/s per IP on /login.
• Return 429 with Retry-After and X-RateLimit-* headers when exceeded.
• Rules configurable without redeploy; multiple rules per endpoint.

Non-functional

• Low overhead: < 1-2 ms added latency; must not become the bottleneck.
• Accurate enough across many gateway nodes (shared state); small memory footprint.
• Highly available; a limiter outage must not take the API down (fail-open policy decided explicitly).

2. Estimates#

• Traffic: 10k req/s average, 50k peak through the gateway; each request = one limiter check.
• Active keys: 10M users × 1 rule = 10M counters. Sliding window counter state ≈ key (8-16 B) + 2 counters (8 B) + timestamp (8 B) ≈ 32 B + Redis overhead ≈ ~100 B → ~1 GB. Token bucket: tokens + last_refill ≈ 16 B payload per key → similar order.
• Redis ops: 1 Lua call per request → 50k ops/s peak; one Redis node handles ~100k ops/s, so 1-2 shards with headroom (cluster for HA).
• Sliding window log instead: 10M users × 100 timestamps × 8 B ≈ 8 GB — why we don't use the log at scale.

3. API sketch#

Middleware/gateway behavior, not a public API:

check(key, rule) -> { allowed: bool, remaining: int, resetAt: ts, retryAfter: sec }Response headers: X-RateLimit-Limit: 100, X-RateLimit-Remaining: 37, X-RateLimit-Reset: 1735689600On deny: HTTP 429 Too Many Requests, Retry-After: 12Rules config (YAML/etcd): { id, match: {path, method}, key: user_id|api_key|ip, limit, window, algorithm }

4. Data model#

Redis, one key per (rule, client):

Token bucket:    HSET rl:{rule}:{client}  tokens 37  last 1735689588123     EXPIRE window*2Sliding counter: INCR rl:{rule}:{client}:{windowStart}  EXPIRE window*2    (two keys: current + previous window)Rules:           stored in etcd/Consul or a config service; cached in each gateway, hot-reloaded on change.

5. High-level design#

client -> LB -> [API gateway / rate-limit middleware x N] -> backend services                      |   local rules cache  <--- watch ---  [rules store: etcd/Consul]                      |   local hot-key cache (optional)                      v             [Redis Cluster]  (atomic Lua: check + decrement)                      |             metrics -> Prometheus (allowed/denied per rule), logs with client key

Flow: extract key (user ID from JWT, else API key, else IP from X-Forwarded-For) → find matching rules → one Lua call per rule → allow or 429.

6. Deep dives#

Algorithm choice

• Token bucket (default): capacity b, refill r/s; permits bursts up to b, averages r. Two fields per key, O(1). Used by AWS, Stripe.
• Sliding window counter: prev × (1 − elapsed/window) + curr; smooths the fixed-window 2x edge burst with two counters. Cloudflare's choice.
• Fixed window: simplest but allows 2x limit straddling the boundary. Sliding log: exact but O(n) memory. Leaky bucket: smooths output; adds queueing latency. Pick token bucket for APIs; sliding counter when you need "N per minute" semantics that match billing/quotas.

Atomicity in a distributed setting

• Read-modify-write races between gateway nodes → use a Redis Lua script (EVALSHA) or MULTI/EXEC; the script reads tokens + last, refills, decrements, writes, sets TTL in one atomic step. Redis Cell module (CL.THROTTLE) implements GCRA natively.
• Clock: use Redis server time (TIME inside the script) to avoid gateway clock skew.

Latency and availability

• Every request pays a Redis RTT (~0.3-1 ms in-AZ). Reduce: colocate Redis per AZ; or local token buckets with periodic sync (accept ±node-count drift); or check only after a cheap local pre-filter.
• Redis down: fail open (allow, log, alert) for public APIs; fail closed for abuse-sensitive endpoints like login/OTP. Decide per rule.

7. Bottlenecks & scaling#

• Redis throughput: shard by client key (Redis Cluster hash slots); each key lives on one shard so scripts stay single-shard.
• Hot keys (one abusive client or a shared IP behind NAT): local in-memory limiter per node as a first line; per-IP limits looser than per-user.
• Rules fan-out: hundreds of rules × every request → index rules by path prefix; evaluate only matches.
• Global vs regional limits: per-region Redis for latency; global quotas enforced asynchronously (eventual, slightly over-admit).
• Observability: counters for allowed/denied per rule, p99 of limiter latency, Redis errors; alert on deny spikes (attack) and on limiter latency.
• Client behavior: document Retry-After; encourage exponential backoff with jitter to avoid synchronized retry storms.

8. Words to say#

token bucket, leaky bucket, fixed window, sliding window log, sliding window counter, GCRA / Redis Cell, atomic Lua script, EVALSHA, race condition, 429 Too Many Requests, Retry-After, X-RateLimit-Remaining, fail open vs fail closed, Redis Cluster hash slots, hot key, local pre-filter, eventual global quota, etcd/Consul rules config, exponential backoff with jitter, retry storm, X-Forwarded-For.