Rate Limiters Explained: How Stripe Says No a Million Times

0:00The Question

Stripe's own API said no to millions of requests in a single month, and nothing had failed. A small program at the front door counted every request and turned away the ones over the line. If you have ever hit that line, you know the shape of it. A script runs fine for an hour, then every call comes back four twenty-nine, too many requests, and the retry loop just keeps knocking. The server can't tell your bug from your success, and it doesn't have to. That program is a rate limiter, and building one is a classic system design interview question. It guards almost every API you have ever called. Design a rate limiter. It sounds small, and that is the trap, because the interviewer is really asking three harder questions. How do you count requests, where do you keep the count, and what do you say when the answer is no? I can't tell you what your interviewer wants to hear. I can show you the machine, one part at a time, with the same client in every version. By the end you will know why the simplest counter lets twice the limit through, and why Stripe and NGINX chose opposite buckets. You will see how Cloudflare gets by with two numbers, and why the fix for a shared counter is to stop reading it. The last part is new: proposed headers that let an API warn you before it says no. Watch the front door first, because everything else is built behind it.

1:49The Contract

Every rate limiter, from GitHub's to the one you would sketch on a whiteboard, enforces the same three-part contract. Who you are: an account, an address, or whatever you signed in with. A window of time. And a budget: how many requests that window is allowed to hold. Spend the budget before the window closes, and every extra request gets the same answer, four twenty-nine, too many requests. Sometimes a note comes with it, a header called Retry-After, telling you how long to wait before you knock again. Take GitHub's version of the deal. Sign in, and you get five thousand requests an hour, with headers on every reply counting down what is left. The limit, the count still left, and the time the window resets all sit in the reply, for anyone who reads them. Now notice what the standard behind four twenty-nine leaves out. Written back in 2012, it never says how the server knows who you are, or how it counts requests. That blank is where all the engineering lives, and it is what the interview is really testing. One more thing before we open the counter: where does this program sit? Usually at the front door, in the gateway or proxy that every request passes through before it reaches your servers. Keep that picture, because later that one door turns out to be many, and the count has to be shared. So the contract is someone, a window, a budget, and an honest no when the budget is gone. Everything that follows is about how to count.

3:45The Fixed Window

Let's give the counter a real client, and keep that client for the rest of the video. One caller, one account, and a budget of fifty requests a minute. The simplest counter is called the fixed window, and it is probably the one you would draw first. Start a count at zero, add one for every request, and reset it to zero on the minute, every minute. It is easy to build and nearly free to run: the whole state is one number per client. Watch our client run through it. Fifty requests spread across the minute pass, and the fifty-first bounces with a four twenty-nine. Then the minute ends, the counter forgets everything, and the client is fresh again. Now for the blind spot, because every interviewer will ask about it. Nothing stops the client from spending all fifty in the last second of one minute. The counter resets, and the same client spends fifty more in the first second of the next. That is twice the limit landing in about two seconds, and every one of those requests was legal. The client did not cheat, and the limiter did not fail. The design simply cannot see across the reset, and that is exactly the burst you built the limiter to stop. In plain terms, the fixed window counts honestly inside each minute and remembers nothing across the boundary, the line between minutes. Cloudflare's engineers describe the same flaw: the counter is reset at regular intervals, so regular traffic spikes go straight through. So the first fix is a counter that remembers, and the two most common shapes are both buckets.

5:47The Two Buckets

A token bucket is a counter that refills slowly instead of resetting all at once. Picture a bucket that holds fifty tokens, and a tap that drips new tokens in at fifty a minute. Every request takes one token to pass. A request that finds the bucket empty gets the four twenty-nine. Now watch our client again. It sits quiet for a minute, the bucket fills to fifty, and then it fires fifty requests at once. All fifty pass, because the tokens were saved up, and the fifty-first is refused until the next token drips in. That is this bucket's personality: a burst is forgiven, as long as the average stays at fifty a minute. Stripe runs its request limiter this way, taking tokens on each request and slowly dripping more into the bucket. The leaky bucket flips the same picture upside down. Requests pour in at the top, wait in a line inside, and drip out of the bottom at one fixed rate. If the line is full, whatever spills over the rim is discarded and never served. Watch the same burst hit this bucket. All fifty arrive together, but the server sees them one at a time, evenly spaced, however hard the flood pours. This is NGINX's design, in its own words: the water is the requests, the bucket is a queue where they wait, the overflow is discarded. The token bucket forgives the burst and enforces the average; the leaky bucket flattens the burst and enforces the spacing. Put simply, Stripe lets you be bursty and NGINX makes you be smooth, and neither of them is wrong. Choosing between them says who your API is for, and that is a good answer in an interview.

7:57The Sliding Window

Both buckets remember, but they answer a different question from the one in the contract. Our client's contract said fifty requests a minute, and the fixed window failed it at the boundary. So the third design keeps the window, and lets it slide. Instead of a minute that starts on the minute, ask: how many requests arrived in the sixty seconds ending right now? The exact way is to store the time of every request, then count the ones inside the last minute. That is the sliding log, and it is exact. But Cloudflare's engineers call its memory and processing cost huge, and worse the longer the window runs. Every request costs you a timestamp, kept for as long as the window lasts, for every client. Cloudflare's shortcut needs only two numbers per client: last minute's count and this minute's. Here is the trick, using their own example, with our budget of fifty a minute. Last minute, the client made forty-two requests. This minute is fifteen seconds old, and it holds eighteen so far. Three quarters of the last minute still sits inside the window, so take three quarters of its count and add this minute's. That comes to just under fifty, so this request passes, and one more would tip it over. It is an estimate, because it assumes last minute's requests were spread evenly. So Cloudflare measured it against real traffic, and it almost never allowed or refused the wrong request. Watch what that buys: two numbers, one sum, and no boundary to exploit. The sliding window estimates the last sixty seconds from two counters instead of remembering every request. And that leaves the question the interviewer was waiting for: where do those two numbers live?

10:12Where the Counter Lives

Every design so far kept one number, or two, per client. The trap is assuming that number lives in one place. Remember the front door from the contract: the gateway that every request passes through. At any real size that door is many machines, and the same client's requests land on different ones. If each machine keeps its own count, our client gets fifty per machine, and the limit means nothing. So the count moves out of the machines into one shared store, usually a fast in-memory database. Stripe keeps its limiters in Redis, and Cloudflare keeps its counters in memcached, where adding one is a single command. Now watch the race, because this is the bug the interviewer is hoping you will spot. Two gateway machines each receive a request from our client at the same instant. Both read the shared counter, both see forty-nine, and both decide there is room for one more. Both add one, and our client has slipped one request past the limit. Read, then add, is two steps, and anything that happens between them is hidden from both. The fix is to stop reading first. Redis has an increment command that adds one and hands back the new total in one atomic step, so nothing can slip in between. Ask for the increment, take the number that comes back, and refuse the request if it is over fifty. Redis's own docs show this pattern, with an expiry on the counter so each window cleans itself up. A shared counter is only safe when adding and reading are one step, never two. Our client is back to fifty a minute, across every machine, and the count now lives in one place. That leaves the last part of the contract, left blank by the standard for fourteen years: what the no should say.

12:31What the No Should Say

Every API we have looked at says no in a different dialect. GitHub sends its own headers, spelled x-ratelimit-limit, remaining and reset. NGINX, by default, answers overflow with a different status code, shown on screen. The IETF's own words, this year: there is no standard way for servers to communicate quotas so that clients can throttle their requests to prevent errors. In plain words, there is no agreed way to warn a client before it hits the limit. So a working group at the IETF is drafting one. It is a draft, and I want to be exact about that: not a standard yet, and it may still change. It proposes two headers, and our client's contract fits inside them exactly. RateLimit-Policy is the server announcing the deal up front. Look at the example: a policy named permin, holding our whole contract, the fifty and the minute. RateLimit is the running count on every reply: the quota left, meaning our unspent budget, and how many seconds it lasts. A client that reads those two lines can slow itself down before the no ever arrives. That is the news, and it changes your last answer in the interview: what does a good client do? Start with what a bad one does. When the four twenty-nine comes, it retries at once, and so does every client refused alongside it. They come back together, get refused together, and do it again. Backing off, waiting longer after each failure, still leaves them moving in step. Add jitter, a little randomness to each wait, and the crowd spreads into a steady flow. So the good client does three things. It reads the limit headers, it honours Retry-After when it is sent, and it backs off with jitter when it is not. Our client, fifty a minute, slows down before the fifty-first, and never sees a four twenty-nine at all.