A rate limiter, as a test bench
“Five requests a second” sounds like one rule. It is at least four different machines, and they disagree about bursts. Here a hopper sends every request, a steel ball, down four lanes at once: a fixed-window counter, a sliding-window log, a token bucket and a leaky bucket, all configured with the same limit. A ball that gets through rolls to a tray; a refused one drops into a bin. Fire a burst and see which lanes let it through.
- 3 requests/s offered
- 5 limit r per second
- 10 L per window
- – tokens in the bucket
- 0 refused, last 10 s
Same requests, four answers
Each row is one limiter over the last twenty seconds. A black tick is a request let through, a red cross a refusal. Fire a burst and compare the rows: the fixed window and the sliding window pass the first L at once and refuse the rest, the token bucket does the same and then trickles at r as the tube refills, and the leaky bucket never passes more than one every 1/r seconds, however hard it is hit.
The dashed verticals are the fixed window's boundaries. Every time one passes, the clock hand wraps and the peg rack empties, whether or not the traffic has calmed down.
What each rule actually guarantees
A limit of “L per window” is a promise about some span of time, and the four machines keep it differently. The table records the most each lane has let through in any half second and in any window-length span, against the most its rule permits.
Press “Burst across a window boundary”: half the burst lands at the end of one fixed window and half at the start of the next, so the fixed window lets through 2L in under a second while the sliding log still stops at L. That is the fixed window's well-known flaw, and the reason many gateways approximate a sliding window instead.
Drop it, or make it wait
Three of the limiters answer immediately: through, or refused. The leaky bucket instead queues what it cannot pass yet and releases it at exactly r, so a burst is not lost but delayed, by up to L/r seconds. Smooth output has a price in latency, and a full queue still refuses.
Which is right depends on the caller. An interactive request that arrives late is often as useless as one refused; a background batch usually prefers waiting to failing.
Refusals that come back
A limiter protects a service only if refused callers stay refused for a while. Choose a client policy under “Refused clients” and press “Retry storm”: each refusal is retried, so the gates see several calls for every request anyone wanted to make, and the red bars climb above the limit line.
Compare the policies. Fixed retries return together and refuse together; exponential backoff without jitter spaces the waves out but keeps them synchronised; full jitter spreads them across the interval, which flattens the peaks. The server can help too, by telling callers when to return with a Retry-After header.
The token bucket is a bound, not just a bucket
A bucket of B tokens refilled at r per second can let through at most B + r·Δ requests in any span of Δ seconds: the bank, plus what refilled while the span lasted. That one inequality is the whole contract, a burst allowance B and a sustained rate r, and it is why the same algorithm appears as the generic cell rate algorithm in telecom traffic policing. The tests behind this page check it against that algorithm decision for decision.
Why the fixed window leaks twice the limit
A fixed window counts per aligned slot, so it forgets everything at the boundary. A client that sends L requests in the last instant of one window and L in the first instant of the next has sent 2L in an instant, and been refused nothing. The sliding log keeps timestamps and counts the true last W seconds, at the price of memory proportional to L per client. The common compromise, a weighted blend of the current and previous window's counts, trades a small error for constant memory.
Shaping and policing are different jobs
The token bucket and the windows police: over the rule, refuse. The leaky bucket as built here shapes: over the rate, wait. Its output is spaced at least 1/r apart by construction, which is what you want in front of a fragile dependency and not what you want in front of a user. Under a sustained flood all four settle at r requests per second; the sliding log settles a hair under it, at L/(W + 1/λ), because each freed slot waits for the next arrival.
What architects do with it
Pick the rule for the failure you fear. Token bucket where bursts are fine but the average matters; a sliding window where a hard cap per period is a contract; a leaky bucket in front of a dependency that cannot absorb bursts. Limit per key, not globally, so one noisy tenant cannot spend everyone's budget. Charge by cost when requests differ by orders of magnitude. Refuse with 429 and a Retry-After, and tell clients to back off with jitter, or the limiter becomes the load. Share the counters when more than one gateway node enforces the limit, and decide what happens when the counter store is unreachable.
What is simulated, and what is simplified
One limiter instance per lane stands for one key (one client) of one gateway node: no shared counters, no clock skew, no distributed store. New requests arrive as a Poisson stream, plus the bursts you fire, which arrive 25 a second. Every request is offered to all four limiters, after 0.45 s of travel from the hopper. The fixed window counts per aligned window starting at time 0; the sliding log keeps one timestamp per admitted request; the token bucket starts full and refills continuously; the leaky bucket is a queue of L waiting requests released by a wheel that ticks every 1/r seconds whether or not anyone waits. The limit is L = round(r·W). Retried calls are sent again to the lane that refused them, after the delay the chosen policy gives. Real clients also time out, hedge and give up on their own schedule, and real limiters answer in a few microseconds rather than half a second; the shape of each rule is what transfers.
Sources
- ITU-T Recommendation I.371: Traffic control and congestion control in B-ISDN (the generic cell rate algorithm)
- Stripe, Scaling your API with rate limiters
- Cloudflare, How we built rate limiting capable of scaling to millions of domains
- RFC 6585, section 4: 429 Too Many Requests
- RFC 9110: the Retry-After field
- Amazon Builders' Library, Timeouts, retries and backoff with jitter
Built with the anatomy kit · every ball, dial and chart is driven by one simulation, checked against GCRA and brute-force counts