Case study: Rate limiter
Design a distributed rate limiter: choose the algorithm, decide where counters live, and make the limiter's own slowness or failure survivable.
30 min9 steps
By the end you can
- Estimate counter memory, counter-store throughput and the latency budget of a check
- Design globally consistent per-client limits with atomic counter updates
- Choose fail-open or fail-closed behaviour and place the limiter in the request path
- Predict what a burst, a slow counter store and a dead limiter do to clients
Requirements
Per-key/user/IP quotas
- Allow bounded bursts; live rule updates; 429 + Retry-After
Check p99 <1 ms
- Shared limits within tolerance; explicit outage policy
Estimates
Checks/s
50k
One counter operation/request
Counter memory
150 MB
1M clients / 3 rules / 50 B
Shard throughput
~100k ops/s
Illustrative; three shards for headroom
Check latency
0.6 ms
0.5ms RTT + 0.1ms operation
Simulated capacity
3,200/s
2 / 16 workers / 10ms
Admission
2,000/s
400-token burst
API and headers
Allowed
- Pass request; expose limit, remaining, reset
Rejected
- 429 + Retry-After; internal rule API pushes cached configuration
Counter state
Token bucket
- Tokens + last refill; sustained r, burst B; TTL per client/rule
Atomic updates
- Lua or atomic increment + expiry; sliding count weights previous window
High-level design
Order the checks a request passes, cheapest and broadest first.
- 1Limiter checks the key's quota in the shared counter store
- 2Service admits the request only if it has a free worker (concurrency limit)
- 3Gateway authenticates the API key and rejects oversized bodies
- 4Edge or CDN drops floods with a coarse per-IP limit
Deep dive: making shared counters fast and safe
Shared counters
- Shard by client; atomic update; tight timeout
Local token chunks
- Fewer network calls; bounded overshoot; fail-open local fallback for overload protection
Alternatives
No limiter
- Similar throughput; 10x median latency; slow timeouts
Local limiter
- No hop; quota grows with fleet
Sliding window
- Reduces boundary burst; token bucket expresses rate + burst
Failure scenarios you can run
Inject
6x burst
Observe
Admit ~2,000/s; remainder 429
Result
Backend stays near two-thirds utilisation
Inject
Counter store 50x slower
Observe
Every request pays check latency
Result
Timeout and local fallback needed in production
Inject
Limiter dies
Observe
Fixture requests time out throughout outage
Result
Production overload policy: fail open to local cap
Wrap up
Watch
- 429/client, check latency, fail-open events
Decide
- Hot-key shards; timeout; bounded local fallback
Then score each stage from 1 to 4.
Answer this step to continue.