The brief#
TL;DRthe 30-second version
- Limit each client to N requests per window across a fleet of stateless servers.
- One counter per client key; the only hard question is where that counter lives.
- Local counters are fast but wrong; a shared store is correct but adds a hop.
- Pick the algorithm for the burst behaviour you want; pick the store for your accuracy budget.
The functional ask is tiny: given a client identifier (API key, user id, or IP) and a limit like “100 requests per minute”, decide allow or deny for each incoming request. The hard part is the word you did not say out loud — across the fleet. Your API runs on dozens of stateless servers behind a load balancer, so a client's requests land on different machines, and the limit is global. A rate limiter is therefore a distributed-counting problem wearing a one-line spec.
Nail the requirements first: what is the limit keyed on, is it a hard cap or a smooth rate, what happens on a breach (429 with a Retry-After, or silently shed), and — the question that decides the whole design — how much inaccuracy at the boundary is acceptable. A login endpoint wants a strict cap; a public content API can tolerate a few extra requests to save a network round-trip.
PredictTwo API servers each keep a local “50 per minute” counter for the same key. What limit does the client actually experience across the fleet?
Hint: Requests spread across servers by the load balancer. Nothing tells one server about the other's count.
Up to 100 per minute — each server enforces its own 50 independently, so the effective global limit is the per-server limit times the number of servers. Local counters do not compose. That is exactly why the counter usually has to move off the box into a shared store.
The composition#
A rate limiter is three decisions stacked on top of each other: which algorithm counts, where the counter is stored, and how the store is sharded when one node is not enough. Each decision reuses a primitive you can already simulate.
Algorithm — the token bucket is the default answer: a bucket of tokens refills at a steady rate and each request spends one; an empty bucket means deny. It allows controlled bursts (a full bucket) while bounding the long-run rate, which is what most APIs actually want. Sliding-window-counter is the other common pick when you want a smooth cap with cheap storage. Both are just arithmetic over a per-key number — step through them in the
rate-limiting simulator (/ratelimit/sim) to see the bucket drain and refill token by token.
Storage — the counter is a single integer per key, read and written on every request, so it wants an in-memory store with atomic increments: Redis. The classic implementation is one atomic INCR plus an EXPIRE on first write, or a small Lua script for token bucket so the read-modify-write cannot race. This is a distributed cache used as a counter — the same tier you would design in /cachestrategy/sim, with the same hot-key and eviction concerns.
Sharding — one Redis node handles a lot, but at fleet scale you shard the keyspace across several. Route each key to a shard with consistent hashing so adding or removing a node only remaps a small slice of keys instead of reshuffling everything. That is exactly the /chash/sim ring: the client key is the ring key, the Redis nodes are the ring nodes.
What it costs
Per request you pay one network round-trip to the counter store (sub-millisecond inside a datacentre) and one or two O(1) operations there — an INCR and a compare, or a short Lua script for token bucket. Memory is one small record per active key: a counter plus a TTL, on the order of tens of bytes, so a million active clients is tens of megabytes — trivial for Redis.
- Latency added per request: ~1 store round-trip. Co-locate the store in the same AZ to keep it sub-ms.
- Store throughput: one INCR per request — a single Redis node does ~100k+ ops/s, so shard when you exceed that.
- Memory: O(active keys), each key expiring after its window, so idle clients cost nothing.
- Failure blast radius: if the store is unreachable the limiter must choose fail-open or fail-closed (see pitfalls).
The one optimisation worth naming: a small per-server local cache in front of the shared store. If a key is already far under or already over its limit, you can short-circuit without the round-trip and only consult the store near the boundary. That trades a little accuracy for a lot of saved hops — the local/shared split from the brief, made concrete.
The core trade-off: local vs shared
Every rate-limiter design lives on one axis: how far the counter sits from the request. Closer is faster and more available; farther is more accurate and globally consistent. The interview is really asking where you put yourself on that axis and why.
- Local (in-process) counters: zero network cost, perfect availability, but N servers means up to N× the limit — only acceptable when the limit is a coarse safety valve.
- Shared store (Redis): one global counter, accurate to the algorithm, at the cost of a round-trip and a dependency you must handle when it is down.
- Local cache + shared store: the pragmatic middle — approximate locally, reconcile at the store near the boundary. Most large APIs land here.
- Client-side / edge limiting: push the check to the CDN or gateway to shed load before it reaches your servers, backed by the same shared counter.
State this trade-off out loud and the interviewer knows you understand the problem. Everything else — which algorithm, which store — is downstream of where you chose to keep the count.
Choosing the algorithm
| Algorithm | Burst behaviour | Memory / key | Boundary accuracy | Best for |
|---|---|---|---|---|
| Fixed window | Allows 2× at the edge | 1 counter | Poor (edge spikes) | Simple coarse caps |
| Sliding log | Exact | 1 timestamp per request | Perfect | Low-volume, strict limits |
| Sliding window counter | Smooth | 2 counters | Good (approximate) | General-purpose APIs |
| Token bucket | Controlled bursts | 1 count + timestamp | Good | Most production APIs |
| Leaky bucket | Smooths to constant rate | 1 queue / count | Good | Shaping outbound traffic |
The fixed-window edge problem is the classic gotcha: a client can send a full window at 0:59 and another full window at 1:01, so a “100/min” limit permits 200 in two seconds. Sliding-window-counter fixes it cheaply by weighting the previous window; token bucket sidesteps it by refilling continuously. Pick token bucket unless you have a specific reason not to — walk the family in the /ratelimit/sim scenarios to feel the difference between them.
How the big APIs do it
- Stripe runs multiple limiter types (request-rate, concurrency, and load-shedding) in front of the API, backed by Redis and tuned per-endpoint.
- Cloudflare and other CDNs limit at the edge — the check happens in the PoP nearest the client, shedding abusive traffic before it crosses the network.
- GitHub, Twitter/X and most public APIs return the limit state in headers (X-RateLimit-Limit / Remaining / Reset) so honest clients can back off.
- Envoy and API gateways ship a global rate-limit service so the limiter is a shared sidecar rather than logic duplicated in every service.
The common thread: the counter lives in a shared, fast store; the check runs as close to the client as the accuracy budget allows; and the limit state is returned to the client so well-behaved callers self-throttle instead of hammering into 429s.
Pitfalls & misconceptions
If the Redis counter is down, do you allow or deny?
A deliberate choice, not an accident. Fail-open (allow) keeps the API available but drops your protection exactly when you might be under attack; fail-closed (deny) protects the backend but turns a cache outage into an API outage. Most pick fail-open for user-facing traffic with a strict local fallback cap, and fail-closed for expensive or dangerous endpoints.
Isn't a single shared counter a bottleneck and a single point of failure?
That is why you shard by key with consistent hashing and replicate each shard. The keyspace spreads across nodes, one hot key only loads its own shard, and a replica covers a node loss. It is the same sharding + replication story as any distributed cache.
Why not just count locally on each server — it's so much faster?
Because local counters do not compose: N servers enforce N independent limits, so the client gets up to N× the intended rate. Local counting is only valid as a coarse safety valve or as an approximate cache in front of the shared store.
Does the read-modify-write on the counter race under concurrency?
It can, which is why the increment must be atomic — a single Redis INCR, or a Lua script for token bucket so the whole check-and-decrement runs as one operation. Two servers hitting the same key at once must not both read the same pre-increment value.
In the interview
- Clarify the requirements: what is the key, is it a hard cap or a smooth rate, what is the response on breach, and how much boundary inaccuracy is tolerable.
- State the core insight: it is a distributed-counting problem — local counters do not compose, so the count usually lives in a shared store.
- Pick the algorithm (token bucket for controlled bursts) and justify it against the fixed-window edge problem.
- Put the counter in Redis with an atomic INCR/Lua script; return X-RateLimit headers so clients self-throttle.
- Scale it: shard the keyspace with consistent hashing, replicate each shard, and name your fail-open vs fail-closed choice.
- Mention the optimisation: a local cache in front of the store to skip the round-trip away from the boundary.
The whole answer is four primitives — a counting algorithm, a shared store, consistent-hash sharding, and a failure policy. If you can operate each one on its own, you can assemble this live. Open the component simulators below to rehearse the parts before you compose them.
QuizAn interviewer asks why you chose token bucket over a fixed window for a public API. Best answer?
- Token bucket uses less memory per key.
- Fixed window allows up to 2× the limit at the window boundary; token bucket refills continuously and bounds bursts.
- Token bucket does not need a shared store.
- Fixed window cannot be sharded.
Show answer
Fixed window allows up to 2× the limit at the window boundary; token bucket refills continuously and bounds bursts. — The decisive reason is boundary behaviour: a fixed window lets a client spend a full window on each side of the reset (2× in a moment), while token bucket refills continuously so the long-run rate is bounded and bursts are capped by the bucket size. Memory and sharding are similar for both.
References
- Stripe — Scaling your API with rate limiters — The four limiter types Stripe runs in production, backed by Redis.
- Cloudflare — How we built rate limiting at the edge — Counting at the edge across a global fleet.
- System Design Primer — Rate limiter — The canonical interview framing and variations.
Rehearse the parts: the counting algorithms in /ratelimit/sim, the shared counter tier in /cachestrategy/sim, and key-to-shard routing in /chash/sim. This design is just those three, wired together.