Design a Rate Limiter
Throttle requests per user/IP/key to protect services — token bucket, sliding window, and distributed counters.
Overview
A rate limiter caps how many requests a client can make in a window. It protects downstream services from abuse and overload and enforces API quotas. The interesting parts are the algorithm choice and making counters correct and fast across a fleet of servers.
Requirements
Functional
- Limit requests per client (by user id, API key, or IP) within a time window.
- Return HTTP 429 with a Retry-After header when the limit is exceeded.
- Support different rules per endpoint / tier (e.g., 100 req/min free, 1000 paid).
Non-functional
- Low latency — the limiter is on the hot path of every request.
- Accurate under concurrency across many app servers.
- Fail open (or closed) deliberately if the limiter store is down.
- Memory-efficient for millions of distinct clients.
Back-of-the-envelope
The numbers that justify the architecture.
| Requests / sec (peak) | 1M | |
| Distinct clients | 10M | |
| Counter memory | ~few GB | counters are tiny; fit in Redis |
| Added latency budget | < 1 ms |
Reference architecture
A limiter middleware at the edge/gateway consults a shared Redis store holding per-client counters; rules live in config.
Deep dives
Choosing the algorithm
Token bucket: a bucket refills at a fixed rate; each request consumes a token; allows short bursts up to the bucket size. Great default (used by Stripe/AWS). Leaky bucket: processes at a constant rate, smoothing bursts — good for steady downstream. Fixed window: a counter per wall-clock window; simple but allows 2× bursts at the window boundary. Sliding window log: store timestamps, exact but memory-heavy. Sliding window counter: weighted blend of current+previous fixed windows — near-exact with O(1) memory, the usual production pick.
Making it correct across a fleet
With many app servers, in-memory counters diverge. Centralize state in Redis and make the check-and-increment atomic — either a Lua script or `INCR` with an `EXPIRE` set on first hit — so two concurrent requests can't both read '99' and both pass. The Lua script runs server-side in Redis, giving you read-modify-write atomicity in one round trip.
To avoid a Redis round trip per request, some designs keep a local token bucket per node sized to `global_limit / node_count` and periodically reconcile — trading exactness for latency.
Failure mode: fail open vs closed
If Redis is unavailable, do you allow all traffic (fail open — protects UX, risks overload) or block it (fail closed — protects the backend, hurts users)? Most public APIs fail open with a local fallback limiter; security-sensitive endpoints fail closed. State this decision explicitly.
Key trade-offs
For each decision: the two options, and when to pick which.
Bottlenecks & follow-ups
Where it breaks under load — and what an interviewer will probe.
- ▲Redis becomes a hotspot at 1M rps → shard counters by client key; use a Redis cluster.
- ▲Boundary bursts with fixed windows → switch to sliding window.
- ▲Race conditions on read-then-write → atomic Lua / INCR.
What a strong answer sounds like
- ✓Name token bucket vs sliding window and justify your pick for the given traffic shape.
- ✓Call out the atomicity requirement — it's the #1 thing junior answers miss.
- ✓Decide fail-open vs fail-closed explicitly; there's no universally right answer.
A Staff answer picks the algorithm from the requirement (token bucket for bursts, sliding window for smoothness) and then confronts the hard part — distributed state: where the counter lives, the race between replicas, whether approximate limiting is acceptable for latency, and whether the limiter fails open or closed when Redis is down.
Architecture Judgment — Staff & Principal decisions, each with a grading rubric.