!This gives away every stage. For a clean attempt, practise it first, then come back.

Before we start

You’ve seen rate limiting even if you’ve never built it. Try logging in with the wrong password too many times and you get “try again in 15 minutes”. Hammer refresh on a ticket booking site and you get “too many requests”. Use any public API and you’ll find a limit like “1,000 requests per hour”.

That’s the job: count what each user does, and say no when they go over. It protects the servers behind it, and keeps one noisy user from slowing things down for everyone else.

Many candidates treat this as an algorithms question, recite “token bucket”, and stop. The interviewer then asks “what happens when the counting server is slow?”, and that’s where the interview really starts. So we’ll cover the algorithms properly, but also the parts that break in production.

Minutes 0–5Requirements

The question about strictness is the most important one, and most people skip it. “A few percent over is fine, double is not” will rule out some designs before we draw anything. And “you tell me” is an invitation: the interviewer wants to see that you know it’s a real decision.

Functional requirements

1. Limit requests per API key (and per IP address when there’s no key), against a budget we configure.
2. Let some endpoints cost more than others against the same budget. A search might cost 10, reading a post 1.
3. When a client is over the limit, reject the request with a clear error that says when to try again.
4. Let us change a customer’s limit without shipping new code.

Not today: charging customers for going over, and banning abusers permanently. Both use the rate limiter’s data, but they’re separate systems.

Non-functional requirements

1. Accurate enough: within a few percent of the limit, and never close to double.
2. Fast: the check runs on every request, so it should add well under a millisecond most of the time, and a few milliseconds at worst.
3. Doesn’t take the API down: if the rate limiter has a problem, the API should keep working. (That’s our answer to “you tell me”. More in the deep dives.)
4. Big: about 200,000 requests a second at the busiest time, from about a million different API keys.
5. Short bursts allowed, within a sensible bound.

Minutes 5–10Back-of-the-envelope estimates

Notice what the numbers tell us: memory doesn’t matter, but the number of updates and round trips does. Saying “memory isn’t the problem” out loud is useful too. It tells the interviewer you won’t waste time there.

Minutes 10–15Core entities and the API

Core entities

• Rule: who it applies to (a plan, one customer, or an IP address), the limit, the time period, how big a burst is allowed, and what each endpoint costs.
• Counter state: for each API key, one or two numbers, depending on the algorithm. Small, and safe to lose.
• Decision: allowed or not, how much budget is left, and when to try again.

The API

The rate limiter is a check the gateway runs on every request, plus some headers the client sees:

429 is the standard “too many requests” status code. Retry-After tells the client how many seconds to wait, and almost every HTTP library understands it.

Send the “remaining” header on every response, not just rejections. A well-written client can see its budget running low and slow down before it hits the wall. GitHub’s API does exactly this.

Minutes 15–30The design, built up

Start with the simplest version that works, then let growth break it.

Stage 1One server, counts in memory

This is correct, and it’s worth saying why. There’s exactly one count per key, so nothing can disagree with it. It’s also very fast, because nothing leaves the server. We’ll pick a better counting method later. For now this simple “count per minute” is fine.

Stage 2Fifty gateways, fifty separate counts

This is where “double is not okay” pays off. It rules out separate counts on each gateway.

Stage 3Shared state: one atomic call to Redis

An operation that happens in one indivisible step like this is called atomic. (Lesson 6.3 walks through Redis scripts for rate limiting.)

One practical detail: when Redis is split across several servers, a script can only touch data on one server. Name your keys so everything for one API key lands together. Redis lets you mark part of a key name with curly braces, like rl:{ak_9f2}, and only that part decides which server it goes to.

Stage 4Production: rules, telemetry and a fallback

Checking the design against the requirements

Deep diveEvery rate limiting algorithm, explained

This is the part interviewers almost always ask about, so let’s go through every common algorithm properly. To keep things easy to follow, we’ll use a small example throughout: a limit of 5 requests per minute.

For each one, look at three things: what it remembers, what it gets right, and how it can be fooled.

Fixed window

How it works: split time into fixed blocks, like 12:00 to 12:01, 12:01 to 12:02. Keep one counter per block. Each request adds one. If the counter is already at 5, say no. When the next minute starts, the counter starts again at zero.

What it remembers: one number per user.

Good: the simplest possible design, and very cheap. One INCR in Redis does the whole thing.

The catch: look at the edges of the blocks. A user sends 5 requests at 12:00:59, the counter resets at 12:01:00, and they send 5 more. That’s 10 requests in two seconds, double the limit, and all of them were allowed.

Used by: Envoy’s popular rate limit service counts this way. It’s a fair choice when limits are a loose safety net, not a promise.

Sliding log

How it works: remember the exact time of every request. When a new one arrives, throw away timestamps older than one minute and count what’s left. Fewer than 5? Allow it and add its time.

What it remembers: one timestamp per request in the last minute.

Good: perfectly accurate. In any 60-second stretch, the user never gets more than 5.

The catch: memory. A limit of 5 a minute stores at most 5 timestamps, fine. A big customer allowed 500,000 a minute means storing up to 500,000 timestamps for one key.

Sliding window counter

How it works: a clever middle ground. Keep just two counters: this minute, and the previous minute. To estimate the last 60 seconds, take this minute’s count plus the part of the previous minute that still overlaps. If we’re 15 seconds into the current minute, 45 seconds of the previous minute still count, so:

What it remembers: two numbers per user.

Good: nearly as accurate as the sliding log, nearly as cheap as the fixed window. Cloudflare measured it on 400 million real requests and found only 0.003% of decisions wrong.

The catch: it assumes last minute’s requests were spread out evenly. Someone who sends all of them in the last second of a minute breaks that assumption, and can get close to double the limit if they time it carefully.

Token bucket

How it works: picture a bucket that holds up to 5 tokens. Each request takes one token; no token, no entry. Tokens drip back in at a steady rate, one every 12 seconds (5 per minute). The bucket never holds more than 5.

What it remembers: how many tokens are left, and when we last added some. Two numbers.

Good: bursts are built in. A user who’s been quiet has a full bucket and can make 5 requests at once, then settles into the steady rate. You can choose the bucket size and the refill rate separately.

The catch: that burst adds to the total. A full bucket of 5, plus 5 more that drip in over the minute, means up to about 10 requests in one minute. The bigger the bucket, the bigger the worst case.

Used by: Stripe’s API rate limiter and AWS API Gateway both describe their limits as token buckets.

Leaky bucket

How it works: the mirror image of the token bucket. Requests pour into a bucket (a queue), and leak out the bottom at a fixed rate, say one every 12 seconds, to be processed. If the bucket is full, new requests are rejected.

What it remembers: the queue of waiting requests, or just how full the bucket is.

Good: the output is perfectly smooth. Whatever arrives, the servers behind it see a steady flow. Great for protecting something fragile.

The catch: bursts don’t get through faster, they wait in line. That adds delay, which is fine for background jobs but annoying for a user waiting on a page.

Used by: NGINX’s built-in rate limiting is a leaky bucket. Shopify describes its API limits the same way.

GCRA

GCRA (the generic cell rate algorithm) behaves exactly like a token bucket, but stores just one number: the time when the user’s next request would be “due” if they sent at exactly the allowed rate. Each request pushes that time forward. If it’s too far in the future, the request is rejected, and the gap tells you exactly how long the client should wait. One number per key, and a free Retry-After. Lesson 6.3 has a step-by-step demo:

All of them, side by side

Here’s the comparison most write-ups skip. Below, a client waits for the best moment and then sends as fast as each algorithm allows. Watch how many requests get through in the worst minute:

Which one should you pick?

The key thing to say out loud: allowing bursts and never going over the limit pull against each other, and the burst size is the dial between them.

Deep diveWhen Redis gets slow

Bad solutionBlock everything, or wait as long as it takes

If a Redis problem means every request gets rejected, our safety feature has taken the whole API down. Waiting is just as bad. A gateway handling 4,000 requests a second, each waiting 1.5 seconds on Redis, ends up with 6,000 requests stuck at once. It only has a few hundred workers, so within a moment they’re all stuck, and the perfectly healthy API behind them gets nothing. (This “requests in flight = rate × waiting time” rule is Little’s law, from lesson 6.1.) Many Redis libraries wait several seconds by default.

Good solutionGive up quickly and let requests through

Wait only a few milliseconds for Redis, then allow the request. The API stays up. But during the problem there’s no limit at all, so the one abusive client you were holding back now gets unlimited access.

Great solutionGive up quickly, use a rough local limit, and stop asking for a while

When Redis doesn’t answer in time, each gateway falls back to a rough limit of its own: the customer’s limit divided by 50 gateways, kept in memory. Not accurate, but it stops the worst abuse. And after a run of failures, the gateway stops asking Redis at all for a few seconds, then tries again carefully. That’s a circuit breaker (lesson 6.1). Accuracy drops during the problem, but the API stays up.

One exception worth mentioning: for a login page’s “too many attempts” limit, blocking is safer than letting an attacker try unlimited passwords. Saying that shows you decide per endpoint, not by rule of thumb.

Deep diveOne partner, 8,000 requests a second

Bad solutionAdd more Redis servers

More servers spread different keys around. They can’t split one key, so the busy server stays busy.

Good solutionCount locally, sync every 100 ms

Each gateway keeps a local tally for that key and sends it to Redis every 100 ms in one update (Redis’s INCRBY, which adds any number at once), reading back the total. That’s 50 gateways × 10 updates a second = 500 updates instead of 8,000. The price: between syncs, gateways don’t know what the others have allowed, so a little extra can slip through after the limit is reached.

At 100 ms, the worst case is about 800 extra requests against a limit of 480,000 a minute. That’s 0.17%, well inside “a few percent”. Giving that number is what makes the answer convincing.

Great solutionOnly do it for busy keys, and hand out tokens in advance

Most customers send a few requests a minute and can go to Redis every time. Spot the busy ones and only batch those. Even better, let each gateway take a small batch of tokens from Redis in advance, say 200, and spend them locally. Then the most that can slip through is clear (50 gateways × their unused tokens). And remember who’s already over their limit: Envoy’s rate limiter keeps a local list of keys that are over, and rejects them without asking Redis until the minute rolls over. That matters most during abuse, exactly when Redis would otherwise be busiest.

Deep diveTwo data centres

This is a classic trade: speed versus perfect accuracy (lesson 5.4). “A few percent over is fine” is what makes it acceptable.

Deep diveWhat clients do with a 429

Then one more idea strong candidates bring up on their own. A rate limiter is about fairness: is this one client using more than its share? It doesn’t know whether the servers are healthy. Load shedding is the other half: when servers are overloaded, drop less important requests, whoever sent them. Stripe describes running both. You need both, because sometimes many well-behaved clients add up to too much at once.

The complete architecture

Here’s everything together: the full design from the last stage, with every part we added along the way. If you only remember one picture from this question, make it this one.

How one request travels through it:

1. A request arrives at any of the 50 gateways. The gateway already has the rules for this key’s plan in memory, pushed from the rules service.
2. It makes one call to Redis: a Lua script that reads the current and previous window (or the GCRA timestamp), decides, updates and returns allowed, remaining and reset. One round trip, atomic, so 50 gateways can’t race each other.
3. If allowed, the request goes on to the API services with rate-limit headers added to the response.
4. If not, the gateway replies 429 with Retry-After and never touches the backend.
5. If Redis doesn’t answer within a few milliseconds, the gateway falls back to a local limit (the key’s limit divided by the number of gateways) and lets the request through on that basis. A circuit breaker stops it waiting on Redis at all while Redis is unhealthy.
6. 429 decisions are sampled into a log so support can answer “why am I being limited?” and so you can alert when a big customer suddenly hits their limit.

How this answer gets scored

Interviewers don’t tick boxes, but their notes on this question tend to land on the same few moments. Here’s what each one sounds like from the other side of the table.

What the left column has in common: every choice points back to a requirement or a number from earlier. If you can say where each box came from, the interviewer will notice.