Rate limiting

The problem it solves

A limit exists to protect something. Usually it is protecting a shared resource from one caller — a scraper, a runaway retry loop, a customer whose batch job starts at midnight — and occasionally it is protecting the caller from a bill. Either way, the limit is a promise: no more than this much, per this long.

The interesting part is that the promise is harder to keep than it looks, and the ways it fails are invisible from inside the limiter. A fixed-window limiter set to 100 requests per second can admit 200 requests inside one second, report that it never exceeded 100, and be telling the truth by its own definition. The service behind it, which experiences seconds as they actually pass rather than as the limiter has decided to slice them, gets twice what it was promised.

The mechanism

Fixed window counts requests in the current calendar-aligned window and resets the counter at the boundary. It is one integer per key, which is why it is everywhere. Its flaw is the boundary: the count knows nothing about the previous window, so a burst at 0.999s and another at 1.001s both pass, and the service sees 2× the limit inside a one-second interval that happens not to align with the limiter’s window.

Sliding window fixes that by counting over the trailing window rather than the current one. The exact version keeps a timestamp per request — accurate and memory-hungry. The common approximation blends the current and previous window counts by how far into the window you are, which is close enough and costs two integers.

Token bucket takes a different view: a bucket refills at rate tokens per second up to a capacity of burst, and a request costs a token. Quiet periods accumulate allowance; a burst spends it. That makes it a limiter with a memory, which is usually what you want — real traffic is bursty, and a limiter that refuses to let anyone ever exceed the mean rate is a limiter that rejects normal users.

Leaky bucket is the token bucket’s mirror image: requests enter a queue that drains at a fixed rate. Instead of allowing a burst through, it smooths one out — arrivals may wait, but downstream sees a perfectly constant rate. Use it when the thing you are protecting cares about instantaneous rate rather than about totals.

What the simulation shows

The default configuration aims a burst directly at a window boundary. Watch the rolling one-second count — not the limiter’s own counter, the count of what actually got through in any one-second interval — and it reaches roughly twice the configured limit. The limiter’s own metric never exceeds 100. Both numbers are honest. Only one of them is the number your database experiences.

Now switch to a sliding window and the rolling count flattens to the limit, because the window travels with the request instead of with the clock.

Then try a token bucket with a burst of 300. The behaviour is different in kind: the quiet period before the burst has been saved, and the burst spends it. Instantaneous throughput exceeds the limit deliberately and then settles to exactly the refill rate. That is not a bug in the limiter, it is the feature you selected. Whether it is acceptable depends entirely on whether the thing downstream can absorb 300 at once — which is a queueing question, and the answer is on the utilisation curve.

The numbers worth carrying

A fixed window admits up to 2× its limit across a boundary, in the worst case, and the worst case is not rare — it is what an adversary picks and what a cron job stumbles into. If you are using fixed windows anywhere the limit actually matters, size for double.

The token bucket’s two parameters mean different things and are frequently confused: rate is what you sustain, burst is what you tolerate at once. Sustained load is bounded by rate regardless of burst; instantaneous load is bounded by burst regardless of rate. Pick burst from what the downstream can swallow in one gulp, not from the rate.

Where it breaks down

Distributed limiting. Everything above assumes one counter. With ten API gateways, either each enforces limit/10 — which rejects a caller whose traffic happens to land unevenly, and unevenness is the norm — or they share state, and now every request costs a round trip to Redis and the limiter has an availability story of its own. The usual compromise is local buckets with periodic reconciliation, which is approximate by construction; know that you have chosen approximate, and by how much.

Clock skew. Windows are defined by time, and distributed limiters disagree about time. Skew of a few hundred milliseconds against a one-second window is a large error.

The wrong key. Limiting per IP punishes everyone behind a NAT and does nothing to a botnet. Limiting per user does nothing to unauthenticated abuse. Limiting per API key is right until one customer runs their whole fleet through one key. Most real systems limit on several keys at once and reject if any is exceeded.

Rejection as an amplifier. A 429 that clients retry immediately is not a limit, it is a load multiplier — the failure documented on retry storms. A limiter must return Retry-After and clients must honour it, and neither half is free.

What people get wrong

“Fixed window is fine, the error is small.” The error is a factor of two, and it is concentrated exactly where you least want it.

“Token bucket and leaky bucket are the same thing.” They are opposites at the moment that matters. A token bucket lets a burst through; a leaky bucket smooths it out and makes the burst wait. If somebody uses the names interchangeably, they have not built either.

“429 means we are protected.” It means you decided. Where the decision is enforced matters: a limiter after the expensive work — after authentication, after a database lookup to find the tenant’s tier — has already spent most of the resource it was installed to protect.

“Rate limiting is a security feature.” It is a capacity feature that has security uses. It will not stop a distributed attacker with many keys, and treating it as a defence leads to sizing it for adversaries rather than for load.

In production

Nginx’s limit_req is a leaky bucket with an optional burst and nodelay; Envoy has local token buckets and a global rate-limit service; Cloudflare and AWS API Gateway implement sliding-window approximations. Stripe’s published API limiter is a token bucket per key with separate concurrency limits, which is a good pattern to name in an interview: rate and concurrency are different constraints and a system with only one of them is under-specified.

On the response side, the useful convention is to return RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset, plus Retry-After on a 429, so a well-behaved client can be well-behaved. Without those headers you are asking clients to guess, and their guess is “retry now”.

The follow-up questions

“Your limiter is 1000 per minute. A client sends 1000 at 59 seconds and 1000 at 61. What happened?” — 2000 in two seconds, allowed. This is the boundary problem, and the expected answer is a sliding window or a token bucket.

“How do you enforce this across twenty gateway instances?” — Shared counter with its own latency and failure mode, or local buckets that are approximate. Say which you chose and what the approximation costs.

“What does a client do when it gets a 429?” — Back off exponentially with jitter, honour Retry-After. If the answer is “retry”, you have just built the failure on the retry storm page.

“Where in the stack does the limiter sit?” — Before the expensive work. If it is behind authentication, say what authentication costs and why that is acceptable.