Design a Rate Limiter

Before any box moves, three things have to be pinned, and they are the three the day-one server hand-waved: how we tell one client from another, how we count its requests, and what we send back when it is over. None of them need a new machine — all three are the shape of the check itself. Start with the client. The limit is per-client, so everything depends on how a client is identified: this is the limiter key, the value we count against. The obvious key is the caller's IP address — always present, needs nothing — but an IP is not a caller. A whole office, a whole carrier, a whole cloud region can sit behind one address. The opposite key is the authenticated identity — a user id or API key — which names an actual account, so the limit lands exactly where it should.

The day-one server used a plain counter that resets every minute. That is a real algorithm — a fixed window — and it has a specific, well-known flaw. Because the window snaps back to zero at a fixed instant, a client can send its whole allowance in the last second of one window and its whole allowance again in the first second of the next: two windows a fraction of a second apart, so the client just got about twice its limit in an eyeblink. That factor of two is the flaw every better algorithm exists to fix.

The exact fix is a sliding window log: store the timestamp of every request, and on each new request drop the ones older than the window and count what is left. Perfectly accurate — the window really slides, so there is no boundary to game — but the cost is memory. You store one entry per request, per client, even for requests you rejected. Figma measured this and found the log costs about ten times the memory of the cheaper approach. Ten times the memory to remove a flaw that lets someone send double for one second is a bad trade, which is why nobody ships the exact log at scale.

That leaves two that differ in one property: whether a client may burst. A leaky bucket — what nginx does — smooths the outflow to a fixed, steady rate and never lets a burst through. A token bucket does the opposite where it matters: a bucket holds some tokens and refills at a steady drip; each request takes one, and a client that has been quiet can spend a burst all at once, up to the bucket's size, then is held to the drip rate. The acceptable alternate is Figma's sliding-window counter, the approximate cousin of the log — chop the window into slices, keep a count per slice, add up the trailing slices — which you pick if you want smooth enforcement without a burst allowance and can accept up to a minute of leniency at the edge.

Token bucket — allow a burst up to a size, then enforce the average. Token bucket. The deciding reason is that real traffic is bursty and mostly fine — a user opens an app and it makes twelve calls at once; a nightly job wakes up and syncs. Punishing those with a leaky bucket's flat rate makes the product feel broken for behaviour that was never abusive. The token bucket allows the burst up to a set size and enforces the average after it, which is what almost every client actually needs. It is also the answer two independent production systems reached: Stripe runs its rate limiter on the token bucket, and AWS API Gateway does too, exposing exactly two dials — a rate, which is the refill speed, and a burst, which is the bucket size.

And what we say when a client is over. A rejection has to be an answer the client's code can act on, or the client just retries in a tight loop and makes everything worse. The status code is 429 Too Many Requests, and it may carry a Retry-After header saying how many seconds to wait before trying again. Those two things are the whole ratified contract, and 429 responses are explicitly not to be cached — a cached over-the-limit would keep rejecting a client that is now under it. You will also see extra headers like X-RateLimit-Remaining, and they are genuinely useful, but they are a convention several companies invented separately, not a web standard — so send them, but do not call them a standard.

Every app server is running the token-bucket check against a counter in its own memory, and that is broken in the way the single-server version warned about: a client hitting ten servers gets ten separate counters and ten times its limit. So the counter cannot live in the servers — it has to live in one place they all share. That much is forced. What is not obvious is that moving the counter to a shared place does not, by itself, make it correct. Put the counters in one shared, fast, in-memory store every app server talks to. Redis is the obvious choice and the right one: it holds a value by key in memory, a read or write is well under a millisecond, and the count for this limiter key is exactly a value by key. Now every server checks the same shared count, so the ten-servers problem is gone. Is the count correct?

Watch the race. Server A reads the count from the shared store: one token, allow. Server B reads at the very same instant — also one token, because A has not written its change back yet — so B also decides allow. Then both write the new count back. Two requests allowed on a budget of one, and it happened precisely because two servers read the same value before either of them wrote. At millions of checks a second, two requests for the same key landing between each other's read and write is not rare, it is constant.

The reflex fix is worth naming because it is the single most common wrong answer: Redis has an atomic increment, INCR, so use that — increment the count atomically and separately set the key to expire with EXPIRE. It looks correct and it is not, for two reasons. The small reason is that INCR and EXPIRE are two separate round trips, so a crash or interleave between them can leave a counter that was incremented but never given an expiry — and a counter that never expires never resets, so that client is limited forever. The large reason is that atomic increment solves the wrong half of the problem. Our check is not add one. It is read the count, decide whether it is under the limit, and only then add one. INCR makes the adding atomic, but the deciding still happens in the app server, after a separate read — and that is exactly where the race lives. Two servers can both read a safe value, both decide to allow, and both then atomically increment. The increment being atomic did not help, because the decision was already made on a stale read.

So just put the counter in Redis is not the fix either. The fix is to make the whole thing — read, decide, update — happen as one indivisible step, with nothing able to slip in between the read and the write.

One atomic Lua script — read, decide, write as one indivisible step. Run the entire read-decide-update as one atomic Lua script. Redis executes a small Lua script sent with EVAL as a single, indivisible operation: the script reads the count, checks it against the limit, and writes the new count, and while it runs nothing else touches that key. Server A's whole check completes before server B's read can even begin, so B reads the value A already wrote, sees zero tokens, and rejects. One request allowed on a budget of one, which is correct. The two round trips also collapse into one — the script sets the count and its expiry together, so there is no window where a counter exists without a reset.

Both sizings now, because they are about to disagree in an instructive way. Capacity first: a client's whole state is those two numbers plus the key and a short expiry — call it fifty bytes — so even ten million clients active at once is about five hundred megabytes, which fits one node with room to spare. Throughput is the other story: every request is one check, and a check is one round trip to this store, so three million checks a second against a single node that does about a million operations a second does not fit. This store is going to have to be split — not because the data is big, but because the traffic is. Two sizings, same box, opposite directions; when they disagree you take the larger, so the split is the next-but-one use case. For now one thing is settled and it is the important one: the count is correct.

The count is correct and it lives in one shared store. But look at who is calling that store: every app server, on every request, before doing the actual work. We put the check there because that is where the code already was, back when the counter lived in the server's memory. Now that the counter has moved out, the check does not have to run in the app servers at all. A rate-limit check has one job — reject the requests that are over the limit as early and as cheaply as possible, so the service behind it never has to deal with them. So where along the path from the client to the app servers should that check physically run?

The first option is where it is right now: in the app servers themselves, in-process. Simple, and it has one real virtue — the app server knows everything about the request, so it can make rich decisions. But a request that is going to be rejected has already travelled all the way to an app server, taken a connection, and woken application code, just to be told no. The servers you are trying to protect are doing the work of turning traffic away, which is the work you least wanted them doing under load.

The second option is a dedicated rate-limit service: a separate fleet whose only job is the check, called by the app servers before handling a request. Clean to reason about and easy to scale on its own, and some large systems run exactly this. The cost is a network round trip — every request makes an extra hop to the rate-limit service and back before anything happens, on the latency budget of every call, including the ones that were always going to be allowed. You have bought organizational tidiness with latency every user pays.

The third lives inside a service mesh: a sidecar proxy deployed next to every service instance, each running the check. It has the gateway's core virtue — the check runs in a proxy, not in application code — but spread out, one proxy per service instead of one shared layer. That is the right shape when there is no single front door to put a check in front of, which is exactly what a mesh is for. For a public API that already funnels every request through one edge, it is more proxies to configure and operate for no added reach.

At the gateway — the edge every request already passes through. Run the check at the gateway — the reverse proxy or edge layer that already sits in front of the app servers, that every request already passes through. The reason is that the gateway is the only place where the check is both early and free. Early, because a rejected request never reaches the servers you are protecting — the entire reason those servers exist without ever seeing blocked traffic. Free, because the request already passes through the gateway, so the check adds no hop that was not already happening. This is what nginx does, what AWS API Gateway does, what Cloudflare does at the edge. The one honest limit is that the gateway sees the request as HTTP and not much more — the API key, the IP, the path, the headers, but not deep application state. For rate limiting that is exactly enough, because the limiter key is right there in the request.

And the failure choice the brief insisted on. The gateway is stateless, so a dead one just leaves the load balancer's rotation and the rest carry on. The counter store is the interesting failure: what happens to a request when the gateway cannot reach the counter store at all? There are only two answers, and you must pick one before it happens, never during. Fail open means allow the request; fail closed means reject it. For a rate limiter the usual choice is to fail open, because rate limiting is a protection, not a gate — taking the entire service down because the limiter's counter store hiccupped would be the limiter causing the outage it was meant to prevent. So most systems let requests through when the counter is unreachable and accept that during that window the limit is not enforced. The only wrong move is to not have made the decision.

The board is built and it is correct. Before trusting it, try to break it — and the place it breaks is the number we deferred two use cases ago. The counter store is still a single node, a single node does about a million operations a second, and we are sending it three million checks a second. So it is already over its ceiling. The ordinary fix is to split it: three million against a million per node is about three nodes' worth of work, so the counter store becomes about three shards, and with three copies of each for redundancy that is around nine nodes. The hard constraint most sharding does not have is that a single limiter key's whole count must live on one shard — you cannot split one client's count across two, or no single shard knows the client's real total. So shard by the limiter key, using consistent hashing, and the three million checks spread flat because different clients hash to different places.

Now break it on purpose. Sharding by the key spread the load beautifully, on one assumption: that no single key carries too much of it. But the whole point of a limiter key is that it can be one client, and one client can go viral or go rogue — one IP running a scraper, one leaked API key hammered by a botnet. That is a single limiter key, which means it is a single shard, taking the entire flood by itself. It can send a million checks a second on its own — one whole shard's budget — from one key. This is a hot key, and it is the thing sharding cannot help with, because every one of those checks is for the same key, and the same key hashes to the same shard no matter how many shards you have.

The reflex is add more shards, and it is wrong here for an exact reason: it is the right answer to aggregate load, which is why it was the right answer thirty seconds ago when the whole store was over its ceiling. It does nothing for a single hot key, because a single key is one shard's problem forever. Every one of the hot key's checks is for the same key, the same key hashes to the same shard, and adding shards just moves the hot key from one overloaded shard to a different overloaded shard.

The second reflex is the one that works for hot keys in other designs — make copies of the key across several nodes and spread the reads — and it is wrong here too, in an interesting way. Copying a key works when the key is hot because it is being read a lot, because every reader can use any copy. Our hot key is hot because it is being written — every request increments the count — and you cannot spread a count across copies, because then no copy knows the true total, which is the same constraint that forced all of one key onto one shard in the first place. A count is the one thing that cannot be copied to make it faster.

The move that fits is to stop the flood before it reaches the shard. A flood is a client massively over its limit, and you do not need the exact count to know the answer is no — so the gateway's local token bucket rejects it from its own memory, and a small local reject list keeps a persistent offender from reaching the shard at all. The offender that ignores Retry-After is exactly the one the local reject list is for.

Reject the offender locally — local bucket, a reject list, and client backoff. Reject the offender before it reaches the counter, and let good clients back off. A hot key that is a genuine flood is, by definition, a client that is massively over its limit — and once a client is that far over, you do not need the exact count to know the answer is no. So the two tiers from the last use case earn their keep. The gateway's local token bucket catches the flood in its own memory and rejects it without ever touching the shared shard — the flood dies at the front door. For a persistent offender the gateway keeps a small list of keys that are currently and badly over their limit, learned from the counter store, and rejects those keys locally for a short while without asking the shard at all. That list is a few entries, it costs nothing to check, and it keeps one leaked key from taking down the shard that also holds a million innocent clients' counts. The third piece is cooperation: the 429 and Retry-After from the first use case tell a well-behaved client to slow down, so a lot of would-be flood never gets sent.

And the rule that transfers out of this problem into whatever your interviewer actually asks. A key that is hot because it is being read is fixed by making more copies of it — every reader can use any copy. A key that is hot because it is being written cannot be spread at all, because then no copy knows the true total. Our hot key is hot because it is being written — every request increments the count — so copies are the wrong move and splitting is the wrong move; you reject the offender instead. Read-hot and write-hot are opposite problems, and reaching for the wrong fix makes things worse rather than simply not helping.

Step back and look at what we built. It is correct: one shared count per client, made atomic by a Lua script, sharded for throughput, hardened against a hot key. For a service in one region at a few million checks a second, this is the right design and it is done. Now someone hands you Cloudflare's problem, and the whole thing falls over — not because it is wrong, but because its central assumption stops holding. Cloudflare runs a rate limiter across the entire planet: several billion requests a day, served from hundreds of datacenters, and it has absorbed a single-domain attack of about four hundred thousand requests a second. Our design says every check is a round trip to one shared, exact count. Where does that count live when the requests arrive in a hundred datacenters at once?

Pick any one datacenter to hold the exact count, and every check from every other datacenter is now a round trip across the world — tens or hundreds of milliseconds, on every request, the exact latency the brief said the limiter must not add. That is one exact option, and it is unbearably slow at planet scale.

Replicate the count to every datacenter so each check is local, and it stops being one count — keeping the copies in agreement is the cross-datacenter coordination we ruled out in the brief as the wrong trade. That is the other exact option, and it is either not actually one count or it pays the coordination cost we already refused. The exact, centralized count that was correct in one region is, at planet scale, either unbearably slow or not actually one count, and no amount of sharding fixes it, because sharding spreads load within a region and this problem is between regions.

So the move is to give up exactness on purpose: each datacenter keeps its own local count, never synchronized, and estimates the rate with a two-window weighted guess. At internet scale, approximate and fast beats exact and coordinated.

Approximate per-datacenter counting — local counts, never synchronized. Stop trying to be exact, and stop coordinating at all. This is the opposite move to everything so far, and it is the point of the whole use case. Cloudflare's answer is that each datacenter — each point-of-presence — keeps its own local count, and the counts are never synchronized across datacenters. Anycast routing keeps a given client landing at the same nearby datacenter, so that one datacenter sees almost all of that client's traffic and its local count is close to the truth. Almost, not exactly. And each datacenter smooths its own count over time so the fixed-window flaw does not come back: it keeps the count for the current window and the count for the previous window, and estimates the rate as the current window's count plus a shrinking fraction of the previous window's, weighted by how far into the current window we are. Their own worked example: with eighteen requests so far this minute, forty-two in the previous minute, and fifteen seconds elapsed, the estimate is eighteen plus forty-two times three-quarters, which is forty-nine and a half. A weighted guess, two numbers per client, and no coordination anywhere.

Now the number that justifies the whole approach. This count is approximate, so how wrong is it? Cloudflare measured it against four hundred million real requests and found it made the wrong decision about three thousandths of one percent of the time, with an average difference from the true rate of about six percent. For a rate limiter, being wrong three times in a hundred thousand, in exchange for zero coordination and a check that never leaves the local datacenter, is a trade you take every time. This is the same trade as the sliding-window log from the first use case, made one more time and much larger: there, the exact log cost ten times the memory to remove a flaw the product could live with, so nobody shipped it; here, the exact global count costs cross-planet coordination to remove an error of six percent the product can live with, so Cloudflare does not ship it. A rate limit is a safety margin, not a bank ledger.