Design a rate limiter
You already know the token bucket. This drill is about the part the whiteboard glosses over: the moment one bucket becomes N buckets behind a load balancer, and "100 requests per minute" stops meaning a single, knowable number.
0. Interview hinge — what 15 already settled, and what it didn't
Lesson 15 gives you everything for a single front door: reject early because a request that never touches business logic costs almost nothing (15's economic first principle); token bucket = "burst up to B, cap the average at r"; emit 429 with Retry-After so clients back off. If the interviewer wanted that, they'd have asked a junior. Walk it in thirty seconds and bank the time.
1. Clarify the contract
Treat the prompt as a product contract before a box diagram. What it must do:
- Decide allow/deny per API key / user / IP / route, in single-digit milliseconds.
- Allow short bursts while bounding sustained rate — this is exactly lesson 15's token bucket; don't re-derive it.
- Work across many stateless gateway nodes that autoscale, with a tenant's requests landing on arbitrary nodes.
- Return
Retry-AfterandRateLimit-*headers so well-behaved clients self-throttle.
What it explicitly need not do: it is not a billing meter (that's an offline aggregation, see §6); it need not be exact to the single request for a soft guard; and it is not a place to ration demand below capacity — lesson 15's rule holds, every 429 should map to real abuse or real backend pressure.
2. Put numbers on the shape
The mechanism is cheap. The cost is in the coordination, so the numbers that steer the architecture are about hops and key cardinality, not bytes.
Two of these are load-bearing. The +1 round trip per request means a sub-millisecond Redis hop can exceed the handler time for a cheap endpoint — accuracy is not free. And 50k rps onto one key is a single-partition hot spot: no amount of replication helps a write hot key (07), so the central design that looks exact on the whiteboard melts in production. Hold both numbers; they decide §6.
3. Surface area
Keep it small. The API expresses the decision, never the shard layout.
| API / operation | Why it exists |
|---|---|
check(key, route, cost) -> {allow|deny, remaining, reset} | The hot-path decision; cost enables weighted limiting (15's GitHub-points model). |
consume(key, cost) | Atomic check-and-decrement where the data lives (see §6, atomicity). |
setPolicy(scope, limit, window, tier) | Admin plane; read from a local cache on the hot path so the data path only touches counters. |
4. Data model
The data model is the first architecture; vague ownership makes every later arrow vague.
The split that matters: policy is read-mostly and cacheable per node; counter state is the contended write — its placement is the design question; and a usage stream (an append log of admit/deny events) feeds offline metering and abuse analytics off the hot path. That last one is DDIA Ch. 11 stream aggregation — billing-grade usage is computed by a stream processor over the event log, never read from the live limiter counter, which is approximate and resets every window.
5. Linearized design
Walk a request through the front door. This is lesson 15's flow; the only new step is step 4, where the counter's location forces a decision.
- 1. Normalize identity at the gateway: authenticated key beats user beats IP; route policy beats global default.
- 2. Read policy from a local cache (preloaded; conservative default on miss to avoid a stampede).
- 3. Run the token-bucket check — mechanism per lesson 15, not re-derived here.
- 4. The hinge: the bucket state for this key lives somewhere — local to this node, in a central store, or leased from a budget. This choice sets your accuracy and your per-request cost (§6).
- 5. On deny, return 429 +
Retry-After+RateLimit-*(15's contract). On allow, route inward — the first step that costs real backend resources. - 6. Emit an admit/deny event to the usage stream (Ch. 11) for metering and abuse detection, off the hot path.
6. Deep dives — the part the drill is actually testing
Where the counter lives, and how far each option drifts
Here is the calculation that separates a senior answer from a recited one. Take a hard limit of 100 req/min for one tenant, and a fleet of N gateway nodes. The naive distributed answer is "give each node a local bucket of L = \text{limit}/N." Work it:
- At N = 10: L = 100/10 = 10 per node. If the load balancer spread this tenant perfectly evenly across all 10 nodes, the global accepted rate is 10 \times 10 = 100 — exactly right. The trick works only under perfect spread.
- Now skew the spread. Real load balancers and keyed/sticky routing don't spread one tenant evenly. Say this tenant's requests skew onto just 4 hot nodes. Each of those 4 still holds a full L = 10 bucket, so the tenant gets 4 \times 10 = 40… but that's the under-shoot case. Flip it: a client that deliberately fans out to maximize coverage, hitting all 10 nodes, drains 10 \times L = 100 — and if you'd sized L for a smaller expected spread, the abuser simply spreads wider. The effective limit is (\text{nodes the client touches}) \times L, which the client, not you, controls.
- Now autoscale mid-flight. Traffic spikes, the fleet grows N: 10 \to 25. You re-derive L = 100/25 = 4. But buckets are per-node and stateful — the 10 old nodes are still running with L = 10 until they're recycled, while 15 new nodes come up with L = 4. For the transient, a client touching all nodes can pass up to 10\times10 + 15\times4 = 160 against a limit of 100 — a 60% over-admit that exists purely because the divisor N moved and the state didn't move with it.
That is the whole problem with "divide by N": the global limit is N\cdot L, and both N (autoscaling) and the per-tenant spread (the load balancer and the attacker) are out of your control. The drift isn't a rounding error; it's structural.
The map is the answer to "how do you rate limit across N autoscaling nodes." (a) Local is free and fine for a soft saturation guard where being 1.6× off costs nothing. (b) Central Redis gives an exact global limit — the single source of truth — at the price of a round trip per request and a dependency on the store. (c) Hybrid lease sits between: each node borrows a slice of a global budget every ~200ms and returns the residual, so the hot path stays local (≈0 hops) and the drift is bounded by the un-returned leases — DDIA Ch. 9's eventual consistency applied to a counter. Choose by how wrong you can afford to be, not by reflex.
Why the central path must be atomic where the data lives
The naive central implementation — read counter, compare to limit, write counter+1 — has the textbook race lesson 15 names: two nodes read 99 under a limit of 100, both decide they're under, both write 100, and you've admitted 101. This is DDIA Ch. 7's atomic single-object operation: the check-and-increment must be atomic at the store, not split across a read and a later write from the client. Redis INCR is atomic; to also apply the limit and TTL in one round trip you ship a Lua script (executed atomically server-side) or use CL.THROTTLE (redis-cell's GCRA token bucket in one call). The general law: a distributed counter is correct only if its read-modify-write is atomic where the data physically lives. Move the decision to the client and you've reintroduced the race.
Fail-open vs fail-closed when the store dies
Option (b) makes Redis a dependency on every request, so you must decide its failure mode before it fails. Fail-open (allow on store error) keeps the API serving but removes all protection — fine for low-risk reads, catastrophic for login or payment endpoints where the limiter is an abuse control. Fail-closed (reject) protects the backend but converts a Redis blip into a full outage. The senior move is neither: degrade to per-node local buckets on store failure (option a as a fallback) — you lose global accuracy but stay bounded, and you alert. That degradation path is exactly why the hybrid design earns its complexity: it already has local buckets to fall back to.
The whale tenant: a hot key, not a capacity problem
One tenant at 50k rps against a single counter key is a write hot key (lesson 07). Replication does not help — every request is a write to the same key, so it lands on the same primary partition regardless of replica count, and that one shard melts while the rest of Redis idles. This is the sharpest question in the drill; it's handled below.
7. Trade-offs
| Choice | Buys | Costs | Choose when |
|---|---|---|---|
| Local per-node vs central counter | zero hops, no shared state | effective limit drifts as N·L; client controls it; over-admits on skew/autoscale | soft saturation guard where being ~2× off is harmless |
| Central Redis vs hybrid lease | exact global limit, single source of truth | +1 round trip/req, store is SPOF (13) and hot key (07) | hard contractual quota where exactness is the product |
| Hybrid lease vs central | local hot path + bounded drift | more code; transient over/under-shoot between syncs | very high RPS where the hop or hot key hurts |
| Fail open vs fail closed | availability vs protection | abuse leakage vs self-inflicted outage | read endpoints fail open; auth/payment degrade to local buckets |
The sharpest trade-off is the first one, and it's a trap if you state it as "local is approximate." The senior framing is that local doesn't have an error bar — it has an error the client controls, because the effective limit is (nodes the client touches) × L, and a motivated client spreads to touch more nodes. So "approximate" is fine for a saturation guard but disqualifying for a billing quota, where someone is paid to find that drift.
8. Failure modes
| Failure | Mitigation |
|---|---|
| Effective limit drifts as N autoscales | Use central or hybrid for hard limits; for local, treat N·L as soft and alert on the transient over-admit. |
| Redis (central counter) dies | Degrade to per-node local buckets (bounded, degraded accuracy) + alert. Decide fail-open vs fail-closed per endpoint class up front. |
| Whale tenant hot key (50k rps on one key) | Shard the counter by key + time-slice, or allocate local leases from a central budget — see §9. |
| Retry storm after 429 | Return Retry-After; require exponential backoff + jitter (lesson 13); alert on synchronized retries. |
| Clock skew across nodes | Refill from monotonic local time or server-side time at the store; never trust client timestamps for the window. |
9. Interview prompts you should be ready for
- How do you rate limit across N autoscaling gateway nodes? (senior answer) Name the spectrum: local per-node (free, but effective limit is N·L and drifts — at limit 100 it over-admits to 160 when N goes 10→25 mid-flight), central Redis (exact global limit, +1 hop/req, hot-key + SPOF risk), or hybrid leases that borrow from a global budget every ~200ms (eventually exact, local hot path). Pick by how wrong you can afford to be.
- Why isn't "divide the limit by N" good enough? (senior answer) Because the effective global limit is N·L, and both N (autoscaling) and per-tenant spread are outside your control — a client that fans out to touch all N nodes gets the full N·L, and during a scale-up the old high-L buckets coexist with new low-L ones, so it over-admits. The error is structural and client-controlled, not a rounding error.
- Your Redis limiter is the hot key for one whale tenant at 50k rps — keep global accuracy without melting it. (senior answer) A single key is one partition; replication won't help a write hot key (07). Two real fixes: (1) shard the counter by key + time-slice — split the whale's bucket into K sub-counters (key:shard0..K) and limit/K on each, summing for the global view, spreading 50k rps across K partitions; or (2) local lease allocation — the central store hands each gateway node a lease (say 1/N of the budget) every ~200ms, so the node decides 50k rps locally and only touches the budget at the sync interval. Lease is usually better at this scale: it converts 50k round-trips/s into ~5/s while keeping global accuracy eventually exact.
- Your limiter's Redis goes down — what happens? (senior answer) Decide the mode before it dies. Don't fail-open globally (removes abuse protection on login/payment) or fail-closed globally (turns a blip into an outage). Degrade to per-node local buckets — still bounded, degraded accuracy — and alert. The hybrid design already has those local buckets, which is half of why it earns its complexity.
- Why must the central check-and-increment be atomic, and where? (senior answer) DDIA Ch. 7 atomic single-object op: a split read-then-write races (two nodes read 99, both admit, you get 101). It must be atomic at the store — a Redis Lua script or CL.THROTTLE does check + decrement + TTL in one server-side call. Moving the decision client-side reintroduces the race.
- How is billing-grade usage different from the limiter counter? (senior answer) The live counter is approximate and resets every window — never bill from it. Emit an admit/deny event to a usage log and aggregate it with a stream processor (DDIA Ch. 11). The limiter protects the backend in real time; metering is an offline, exactly-once aggregation over the event stream.
- Token bucket vs sliding window here? (senior answer) Mechanism is lesson 15 — I wouldn't re-derive it. Token bucket for burst-friendly public APIs (allow B, cap average r); sliding-window counter when boundary fairness matters at O(1) memory. The interesting choice in C01 isn't the algorithm, it's where its state lives.
- How does this relate to load shedding (lesson 13)? (senior answer) Same goal — keep the backend below the saturation cliff — different timing. Rate limiting is planned, per-key admission control; shedding is the emergency reaction once already overloaded. The 429-vs-503 split encodes it: 429 = "you exceeded your quota," 503 = "the whole service is hurting." Both want backoff + jitter from clients.
Related foundation lessons
The mechanism — token bucket, the 429 contract, why the edge is the cheapest place to reject — lives in lesson 15; this drill deliberately does not re-derive it. The distributed failure side leans on lesson 13 for the fail-open/closed decision and backoff+jitter (load shedding is C01's sibling — same goal, different timing), and on lesson 07 for why a whale tenant's single counter key is a write hot key that replication can't fix. The eventual-consistency reasoning behind hybrid leases is lesson 09, and the per-hop latency cost of a central store is lesson 02.