BOOKS DEEP-READ · SYSTEM DESIGN INTERVIEW VOL 1 · CH 4
System Design Interview: An Insider's Guide · Vol 1 · Ch 4 · Alex Xu · 2020
Plenty of online services hand you a usage cap: the free tier converts five files a day, that forum won't let you post twenty comments in a minute. This chapter is about the little part behind that cap — the rate limiter: a doorman who enforces "at most so many entries per person per minute" and turns away anyone over the line.
You probably assume the door is there to keep bad actors out. Most of what it turns away is well-meaning. More precisely: a well-meaning program with a bug — some customer's software has a loop that forgot to stop and is firing thousands of requests a second. They don't know, they meant no harm, and the effect is identical to an attack. The limiter's day job is to stop one person's slip from becoming everyone's outage.
With no door, everything runs first-come-first-served: whoever shouts loudest gets served. That sounds fair and is brutal in practice — one runaway program can eat a service's entire capacity in seconds, and thousands of perfectly well-behaved users get locked out together. There's a blunter cost too: many services call somebody else's metered API behind the scenes, billed per call, and a loop that won't stop can burn a month's budget overnight.
1. The candy bowl (token bucket). Put a bowl by the door. Two candies drop in every second; the bowl holds at most 40. To get in, take one; empty bowl, no entry. The nice part: if things were quiet for a while the bowl fills up, and then 40 people can walk in at once — it accommodates a short rush, yet over any long stretch the average is still two per second.
2. The queue (leaky bucket). One line at the door. However many people pile up outside, exactly two per second are let in — never more. The pace inside is perfectly even; the price is that once the line is full, latecomers can't even join it and are simply turned away.
3. Reset on the hour (fixed window). The doorman holds a counter that zeroes every minute; five per minute and no more. Simplest possible thing, with one hole: if five people squeeze in at 0:55 and five more at 1:05, then across those few seconds ten actually got in — twice the rule.
4. Look back one minute (sliding window). Change "this minute" to "the minute counting backwards from now," and the hole closes. The cost is that the doorman must remember when each person walked in, and with a crowd that ledger gets thick and expensive. The compromise is to keep no ledger at all and just carry over a fraction of last minute's headcount by overlap — not exactly right, but far cheaper.
Want to leave users room to be occasionally hasty? Candy bowl. Need the pace downstream to be perfectly even? The queue. Just want a crude barrier up fast? Reset-on-the-hour takes half an hour to write.
One honest cost: the door itself can break — and when it does, do you let everyone in or shut everyone out? There's no standard answer, but every team shipping a rate limiter has to settle it in advance.
A rate limiter is a doorman, and what it mostly guards against isn't attackers — it's one person's slip taking everyone down. Four postures: candy bowl (absorbs bursts), queue (even pace), reset-on-the-hour (cheap but leaks at the boundary), look-back-a-minute (accurate but expensive). Which one you pick comes down to whether you can tolerate bursts.
Want the algorithms, magnitudes and diagrams? → switch to Deep
You think a rate limiter is a wall against attackers. It is really a contract for allocating capacity — the first question it answers isn't "how do I keep bad actors out" but "when there isn't enough to go around, who starves first." The value of this chapter isn't the five algorithms either; algorithms are the easy part. The hard parts are three: how much to allow, which layer to enforce it at, and how to make dozens of stateless limiters agree on one counter.
INCR (increment and return the new value) is atomic.429 Too Many Requests, how a server says "you've been limited."This opens Part II, the case studies. Ch1 gave the parts, Ch2 gave the yardsticks, Ch3 gave the order — Ch4 is the first time all three are used together, and the problem is deliberately small: a rate limiter carries no business complexity, so forty minutes takes you from requirements all the way to distributed race conditions. Looking forward, Ch5's consistent hashing answers the loose end this chapter leaves (how limiter state gets spread across machines), and the notification system in Ch10 and the crawler in Ch9 both use rate limiting again. In the real world: every public API you've used (Stripe, GitHub, Twitter all publish their quotas), plus overload protection between internal microservices.
The book opens with three reasons. Stopping resource starvation — without limits, a handful of callers can consume a service's entire capacity and everyone else goes dark. Cost — many requests fan out to metered third-party APIs (credit checks, payments, health records), and a limiter is the first cap on that bill. Preventing server overload — keeping bots and misbehaving users from crowding out real traffic. Twitter caps tweets at 300 per 3 hours; Google Docs APIs default to 300 read requests per user per 60 seconds. Those numbers aren't arbitrary — they're the published price of "how much shared resource one person may hold."
What happens without it? Do the arithmetic: an API sits steadily at 5,000 QPS; one customer's retry logic is wrong — resend immediately on failure, no backoff — and within seconds their errors compound into 50,000 QPS hitting you. Database connection pools fill, and the other 99% of well-behaved customers all get 503s together. What flattened the system wasn't an attack; it was a loop with no backoff.
The conditions the book lists in "establish design scope" are worth memorizing verbatim, because they drive every trade-off later: accurately limit excess requests; low latency (it sits on every request's critical path); low memory footprint; distributed (many limiter nodes sharing one quota); clear feedback to throttled users; and high fault tolerance — when the limiter itself has problems, it must not take the whole system down with it. That last one is the easiest to forget and the most dangerous.
The book offers three positions and rejects the first outright. Client-side limiting is unreliable — client code can be modified, requests can be forged; handing the quota to the caller to police is not policing. Server-side limiting lives in business code with the richest context, but every service reimplements it. Middleware pulls the concern out into its own layer between clients and services — in a microservice architecture that position is usually the API gateway, which already does authentication, SSL termination and IP allowlisting, so folding limiting in is the natural move.
How to choose? The book's criteria are practical: check what your current stack supports and whether the algorithm you want can be implemented at that layer; if you're already on microservices with a gateway doing auth, put it in the gateway; if you intend to build your own, accept that building a rate-limiting service takes time — a third-party gateway is money traded for time.
A bucket holds up to b tokens; the system refills it at a fixed rate and stops once it's full. Each request takes one token — got one, you pass; none left, you're dropped. Two parameters: bucket size (the maximum burst) and refill rate (the long-run average).
The intuition is in one sentence: the tokens you've saved up are the burst you're allowed. A customer quiet for 20 seconds has a full bucket and can fire 40 requests in the next second — but stretched over time, their rate stays pinned to the refill rate. That's exactly the behaviour most public APIs want: being occasionally hasty is fine, being persistently fast is not.
How many buckets? The book lists three granularities, each with a use: one per API endpoint (posting is more precious than reading, so quotas differ); one per IP (for anonymous traffic); and one global bucket (the whole system tolerates at most 10,000 QPS — the last line of self-defence). Real systems stack all three.
The leaky bucket is a FIFO queue: an arriving request is enqueued if there's room and dropped otherwise, while the other end pulls requests off at a constant rate. Two parameters: queue size and outflow rate.
The difference from a token bucket fits in a line: the token bucket governs "can you come in," the leaky bucket governs "the pace inside." A token bucket lets 40 rush in and be processed together; a leaky bucket, however hard it rains outside, still does two per second. So when the downstream has fixed throughput and can't take a shock — an ageing database, a third-party API billed by concurrency — the leaky bucket fits better.
The book states the cost plainly: a burst fills the queue with old requests, and if those can't be drained, newly arriving and possibly more valuable requests get rejected — the queue turns into a device that prioritises stale work, while the user on the other end sees a response that took eight seconds to come back.
The fixed window counter is the obvious one: slice time into whole minutes (or hours), give each window a counter, increment per request, reject once the threshold is hit, reset at the next window. Memory-cheap, easy to reason about, easy to build.
Its flaw is at the boundary, and the book's example is crisp: with a limit of 5 per minute, if 5 requests land in 2:00:30–2:01:00 and 5 more in 2:01:00–2:01:30, then across the rolling minute 2:00:30–2:01:30 exactly 10 got through — twice the quota. An attacker only has to aim traffic at either side of the boundary to collect double reliably.
The sliding window log closes that hole: instead of bucketing by the clock it records a timestamp per request (typically in a Redis sorted set). On arrival it removes timestamps older than the window start, adds the current one, and passes if the remaining count is under the threshold. No rolling window can ever exceed the limit — this is the only truly exact algorithm. The cost is glaring: memory grows with request count, and the book specifically notes that a rejected request still leaves its timestamp behind. For an endpoint currently under abuse that property is dangerous: memory grows precisely when it least should.
The sliding window counter is the hybrid, and the usual engineering compromise: keep only the previous and current window counts and weight the previous one by overlap — current count + previous count × overlap. The book's example: limit 7 per minute, 7 requests last minute, 5 so far this minute, currently 30% into the window, so the weighted value is 5 + 7 × 70% = 9.7, floored to 9, which exceeds 7 — reject.
It's memory-cheap (two numbers per key) and smooths spikes, but it is an approximation: the formula assumes the previous window's requests were evenly distributed, and real traffic never is. How far off? Cloudflare's measured number is below.
Limiting on one machine is a giveaway; going multi-node changes everything. The two problems the book raises are where this chapter's real depth is.
Race conditions. The naive implementation is read-count, add-one, write-back. Two requests arrive nearly together: both read 3, both compute 4, both write 4 — two requests came in and the counter rose by one. Under load that loss recurs and the threshold means nothing. The remedies are in Table 3 below; here just note that locking is the most intuitive and the worst — the book says outright that it will significantly slow the system down, and the limiter sits on every request's critical path.
Synchronization. To scale horizontally the limiter must be stateless, but a client's requests get balanced across different limiter nodes, each keeping its own books, so the quota is over-issued. The book explicitly rejects the lazy fix of sticky sessions — "neither scalable nor flexible": lose a node and every client state pinned to it is gone; scale in or out and traffic reshuffles, scrambling quotas. The right answer is to move state into centralized storage (Redis) so all limiters read and write one counter.
Limiting rules are usually config files on disk, pulled periodically by workers into a cache the middleware reads (the book's sample format comes from Lyft's open-source rate-limiting component: one rule declaring "domain = auth, key = login, 5 per minute"). Changing a threshold then needs no code change and no restart.
Rejected requests get 429 Too Many Requests; where the business allows deferral, they can instead be queued for later. More important are the three response headers — the contract between limiter and caller: X-Ratelimit-Limit (what the quota is), X-Ratelimit-Remaining (how many are left), X-Ratelimit-Retry-After (how long until you may return). Without them a client can only discover its limit by hitting the wall; with them, a well-behaved client slows down on its own.
Monitoring watches two things: whether the rules are too strict (lots of legitimate requests killed), and whether the algorithm fails under bursts — if real users get mass-rejected during a flash sale, it's time to switch to a token bucket.
Table 1 · Five algorithms: the triangle of accuracy, memory and burst tolerance
| Algorithm | How it works | Memory | Bursts | Main cost | Fits |
|---|---|---|---|---|---|
| Token bucket | Refill tokens at a rate; each request takes one | Two numbers per key, tiny | Yes (whatever is saved up) | Two parameters (size, refill rate) are hard to tune | The default for public APIs |
| Leaky bucket | FIFO queue plus constant outflow | Capped by queue length, small | No | A burst fills the queue with stale requests; new ones rejected, latency stretched | Fixed-throughput downstream needing a flat pace |
| Fixed window | Count per clock window, reset each window | Smallest | No | The boundary leaks twice the quota | A crude barrier; quotas settled on natural periods |
| Sliding window log | Store every request timestamp, prune by window | Largest, grows with request count; rejected requests still occupy it | No | Memory grows under abuse — exactly when it shouldn't | Quotas that must never be exceeded (billing, compliance) |
| Sliding window counter | Current window + previous window × overlap | Two numbers per key, small | Partly (spikes smoothed) | An approximation: assumes even distribution in the previous window | Large-scale general use where exactness isn't critical |
Table 2 · Which layer the door goes in
| Position | What it gets you | Cost / risk | Verdict |
|---|---|---|---|
| Client | Zero server cost; avoids pointless requests up front | Forgeable and bypassable; the quota is policed by the caller | A courtesy hint only, never a defence |
| Server-side, in-app | Full business context (which user, which resource, how expensive) | Reimplemented per service; quotas scattered and hard to tune together | Use when limiting must follow business semantics |
| Middleware / API gateway | One entry point, auth and IP allowlisting alongside; services unaware | An extra hop; the gateway itself becomes critical path | The default under microservices |
| Network layer (e.g. iptables) | Drops packets at the IP layer, cheapest possible | Blind to identity, IP-only; hits everyone behind a NAT | A supplement against volume, not a replacement |
Table 3 · Four ways to beat the race in a distributed limiter
| Approach | Correct? | Latency cost | Notes |
|---|---|---|---|
| Distributed lock | Yes | Highest — a lock round-trip on every request | The book names it as something that "significantly slows the system down"; the limiter is on the critical path, so this is the worst pick |
Atomic increment (INCR) | Yes | One round trip, sub-millisecond | The standard fixed-window answer; pair with EXPIRE so counters vanish on their own |
| Lua script | Yes | One round trip | Packs check-and-write into one atomic execution, so richer algorithms (token bucket) also finish in a single step |
| Sorted set | Yes, and exact | One round trip, but memory grows with requests | The natural home for a sliding window log: prune by score range and count in one go |
One more choice, mentioned at the end of the chapter and worth pulling out: hard vs soft limiting. Hard means the threshold can never be exceeded; soft allows a small overshoot for a short time. Billing and compliance demand hard limits; user-facing quotas are usually better soft — locking someone out over a 1% overshoot rarely pays.
The rate limiter is a component nearly every backend engineer eventually touches and few get right on the first try. Getting it right means three things at once: an algorithm that matches the shape of your traffic, state that counts correctly across machines, and a failure mode that doesn't take the system with it. Every public API you use has one — and the choices differ a lot between companies, which is precisely the point: there is no best algorithm, only a matching one.
400 million requests from 270,000 distinct sources, only 0.003% were wrongly allowed or wrongly limited — a hard number showing an approximate algorithm is good enough on real traffic. Cloudflare, "How we built rate limiting capable of scaling to millions of domains," 2017 ↗40 requests per app per store, replenishing at 2 per second, returning 429 with a Retry-After header when exceeded — a verbatim instance of "the leaky bucket fits when you need a steady outflow." Shopify Dev Docs, "REST Admin API rate limits" ↗10,000 requests per second steady-state and 5,000 of burst capacity per account per Region — "refill rate sets the long-run average, bucket size sets the burst ceiling" is legible right there in those two numbers. AWS docs, "Throttle requests to your REST APIs" ↗5,000 per hour, exceeding it returns 403 or 429, and x-ratelimit-remaining reports the balance continuously — a ready-made example of turning a quota into a contract via response headers. GitHub Docs, "Rate limits for the REST API" ↗Retry-After is the floor; what's actually needed is exponential backoff plus jitter. The book covers backoff and client caching, but this second-order effect — retries synchronizing — deserves its own warning.1. In one line: a rate limiter isn't a wall against attackers, it's the contract deciding who starves first when capacity runs short; what it stops day to day is a runaway retry loop, not an adversary.
2. Three reasons: prevent DoS-style resource starvation, cap metered third-party calls, prevent server overload. The requirement people forget: when the limiter itself has problems, it must not take the system down.
3. Three positions: the client is untrustworthy, in-app has the richest context, middleware / API gateway is the default under microservices.
4. Token bucket: bucket size sets the burst ceiling, refill rate sets the long-run average; the only algorithm that natively welcomes bursts, and what Stripe and AWS API Gateway both use.
5. Leaky bucket: FIFO queue plus constant outflow — steady output, no burst tolerance, and a burst fills the queue with stale requests. Shopify uses it.
6. Fixed window is cheapest but leaks twice the quota across the boundary; the sliding window log is exact and costliest (rejected requests occupy memory too); the sliding window counter is the compromise, measured by Cloudflare at only 0.003% misjudgement.
7. Two distributed traps: races (read-modify-write loses counts — use atomic increments or a Lua script, not a lock) and synchronization (no sticky sessions; put state in centralized Redis).
8. Give the whole contract: 429 plus X-Ratelimit-Limit / -Remaining / -Retry-After; keep rules in config pulled by workers so thresholds change without a deploy. The most valuable sentence in an interview is why you picked this algorithm because the business does or doesn't tolerate bursts — not a recital of five names.