Rate Limiting: Token Bucket, Leaky Bucket, Windows

Over five lessons we've built a spectacular front door. It spreads load across a pool, routes by content, notices death and routes around it, and reaches across continents to meet every user near home. And it still has one glaring flaw: it says yes to everyone. Every request that arrives, it dutifully delivers — the real user's click, the intern's runaway while(true) loop, the scraper hammering your API at 4,000 requests a second, the biggest customer's batch job that starts at midnight sharp.

Here's the uncomfortable truth the whole lesson rests on: your servers don't care whether traffic is malicious. A million requests from an attacker and a million requests from your own success look identical to a CPU. Either one can drown a perfectly healthy fleet — and we saw in the health-checks lesson exactly how an overloaded fleet dies: slow, then failing, then ejecting itself into a spiral. If the door lets everything through, the fleet's health is hostage to whoever shows up.

So the last job of the front door is to say no — deliberately, cheaply, and politely. That's rate limiting: deciding how many requests each client may make per unit of time, letting those through, and turning the rest away with a fast, honest rejection instead of a slow, expensive collapse. The interesting part — the part with four competing algorithms and one famous exploit — is that "how many per unit of time" is trickier to define than it sounds. Every algorithm in this lesson is a different answer to a single question: what happens to a burst?

Rate limiting has a reputation as an anti-abuse tool, and it is one — but abuse is only a quarter of the story. Four different failures push teams to add a limiter, and knowing all four changes how you configure it:

• Abuse. Credential-stuffing bots trying ten thousand passwords, scrapers harvesting your catalog, one hot API key gone rogue. A per-client cap is your first line — not against a full distributed DDoS (that's what the anycast edge absorbs), but against the single aggressive source that's 90% of real incidents.
• Cost. Every request burns CPU, database reads, and — increasingly — money per call to some downstream API or LLM. An unlimited endpoint is an unbounded bill. The limiter is the circuit between "free tier" and "finance escalation."
• Fairness. Your API pool is shared. Without caps, one greedy client eats the pool and everyone else's latency pays for it. Per-client limits are how a shared resource stays shared — the polite fiction that everyone gets their slice, enforced.
• Survival. This is the one people forget, and it ties straight back to the health-checks lesson. When traffic exceeds capacity, something fails — and without a limiter it's your whole fleet, slowly and catastrophically, as overload trips health checks and retries amplify the pain. A limiter at the door sheds the excess before it reaches the fleet. Rejecting 5% of requests cheaply beats failing 100% of them expensively. The kindest thing a busy system can do is say no quickly.

Notice what all four have in common: the decision is per-client ("how many has this key/IP/user made?") and per-time ("…in the last minute"). Everything now hinges on how you count that — which is where the algorithms come in.

Start with the algorithm that wins most arguments. Picture a bucket of tokens sitting next to your API. The bucket holds at most capacity tokens, and it refills at a steady rate — say 10 tokens per second. Every request must take one token to pass. Tokens available? Take one, go through. Bucket empty? Rejected. That's the whole machine.

Watch what those two numbers do. The refill rate enforces your long-term average: over any long stretch, a client simply cannot exceed 10 requests per second, because tokens don't appear faster than that. But the capacity does something subtler and kinder — it lets a client who's been quiet save up. If the bucket holds 50 tokens and you haven't called in a while, you can fire 50 requests in one instant — a burst — and they all pass. Then you're metered back down to the refill rate until you've been quiet again.

That burst-forgiveness is why token bucket is the default for public APIs. Real clients are naturally bursty: a page load fires a dozen calls at once, then nothing for minutes; a mobile app syncs in a spike when it wakes. Punishing that shape punishes normal behavior. Token bucket says: bursts are fine, sustained excess is not — and it gives you two independent knobs (rate for the average, capacity for the burst) to tune each one. And the implementation is a pleasure: per client you store just a token count and a last-refill timestamp, computing the refill lazily whenever they show up. Two numbers per client, O(1) everything.

Now the mirror image. Flip the bucket over and make it a funnel: requests pour in the top and join a queue inside; the funnel drains from the bottom at a perfectly fixed rate — one request every 100ms, say — and if the funnel is full when a request arrives, it's dropped.

The consequence is the exact opposite of token bucket: no burst ever comes out. Whatever chaos arrives — a spike, a flood, a perfectly-timed volley — the output is a metronome: evenly spaced requests at precisely the drain rate, forever. The input can be any shape; the output is always the same shape.

That's not usually what a public API wants (you'd be adding queueing delay to every legitimate burst), but it's exactly what some downstreams need. A fragile legacy database that falls over above 50 queries per second, steady. A third-party API that contractually demands you never exceed a fixed pace. A hardware device with a real physical rate. When the thing you're protecting cares about the instantaneous rate — not the average — you want the leaky bucket's flattening. It comes in two temperaments: shaping (queue the excess and let it through late — smooth but adds latency) and policing (drop the excess on the floor — harsh but bounded).

Here's the one-line contrast to carry: token bucket protects the average and forgives the shape; leaky bucket protects the shape and forgives nothing. Same word — "bucket" — opposite philosophy about bursts.

Every claim so far — "absorbs bursts up to capacity," "output is a metronome," and the window exploit coming next — is about shapes of traffic over time, and shapes are for watching, not reading. So below is a live limiter with its internal state drawn in real time: the token bucket's tokens draining and refilling, the leaky bucket's queue dripping, the window counters filling and resetting. You feed it.

Start on token bucket with a gentle stream — everything passes, tokens hover near full. Now hit 🔥 FLOOD. Watch the burst drain the bucket in an instant: the first chunk passes (that's the capacity being spent), then the 429s start, then the refill rate takes over and requests trickle through at exactly the sustained rate. Drag the capacity slider down and flood again — less burst forgiven. That's the two-knob machine, live.

Flip to leaky bucket and flood again: no matter how violent the input, look at the output — perfectly even spacing, the drip. Then the main event: switch to fixed window and press ⏱ time the boundary. It fires one burst just before the window resets and another just after — and watch the accepted counter: roughly double the limit sails through in a couple of seconds, and the limiter never noticed. Same trick on sliding window: caught. That hole is the next section — but you'll believe it more having watched it happen.

The window algorithms take a different tack: instead of modeling a bucket, just count. Fixed window is the version everyone invents first: keep a counter per client per clock window — "100 requests per minute" means a counter that lives for the minute of 12:04, resets at 12:05, and rejects anything past 100. It's one counter and one expiry per client (in Redis, literally INCR plus EXPIRE), the cheapest possible limiter to build and reason about.

And it has a hole famous enough to be an interview question. The limit is 100 per minute. A client sends 100 requests at 12:04:59 — accepted, counter hits 100. One second later it's 12:05:00: new window, fresh counter. The client sends 100 more at 12:05:01 — all accepted. Total: 200 requests in about two seconds, from a limiter configured for 100 per minute. A caller who times the boundary gets double the configured rate, reliably, forever.

Read carefully what went wrong, because the counter never malfunctioned: each window really did stay ≤100. The lie is in the window itself — the clock boundary at 12:05:00 is an artifact of your bookkeeping, and traffic doesn't respect your bookkeeping. "100 per minute" quietly became "100 per calendar minute," which is a different, weaker promise than "100 in any 60-second span." There's a second, smaller wart too: every client's counter resets at the same instant, so clients that were blocked all retry in a synchronized wave at each boundary — a little thundering herd, once a minute, of your own making.

Fixed window is still genuinely useful — cheap, predictable, fine when the stakes are low and clients aren't adversarial. Just know exactly which promise it makes, and which it doesn't.

The obvious fix for the boundary hole: get rid of the boundary. Instead of a counter that resets on the clock, keep a log of timestamps — one per request this client has made. When a new request arrives, discard every timestamp older than 60 seconds, count what's left, and reject if the count is at the limit. The window now slides continuously with time: at 12:05:01, it covers 12:04:01→12:05:01, and the 100 requests from 12:04:59 are still very much in view. The boundary trick dies instantly — "100 per minute" finally means 100 in any 60-second span, exactly.

The price is written right into the data structure: a timestamp per request, per client, retained for the whole window. At 100 requests/minute that's manageable; at 1,000/minute across a few million clients, you're storing hundreds of millions of timestamps and constantly pruning old ones — real memory, real cleanup work, real Redis bills, just to make reject/accept decisions. Sliding window log is what you reach for when the count genuinely must be exact — billing thresholds, strict contractual SLAs, small client populations — and what you quietly walk away from at consumer scale.

Which sets up the engineer's favorite kind of solution: what if we could get almost the log's accuracy for the fixed window's price?

Here's the trick, and it's lovely. Keep just two counters per client — the current window's and the previous window's. When a request arrives, estimate the count in the trailing 60 seconds as:

estimate = current_count + previous_count × (fraction of the previous window still inside the sliding window)

Say you're 15 seconds into the current minute: the sliding 60-second window covers those 15 seconds plus the last 45 seconds of the previous minute — 75% of it. So: current + 0.75 × previous. If the previous window saw 100 requests, they contribute 75 to the estimate. The boundary-timer who fired 100 at 12:04:59 finds those requests still counting against them at 12:05:01 — the exploit is caught, with two integers instead of a timestamp log.

It is an approximation — the formula assumes the previous window's requests were spread evenly across it, which is never exactly true. So how wrong does it get in practice? Cloudflare ran it across 400 million real requests from 270,000 sources and measured just 0.003% of decisions wrong — with the drift concentrated in traffic that was already pathological. That's the kind of error rate you happily trade for O(1) memory at planetary scale, which is why the sliding window counter is the workhorse at big CDNs and gateways: the log's honesty at the fixed window's price, minus a rounding error.

That completes the four machines. Now for the part that separates a whiteboard limiter from a production one: making the count itself survive more than one server.

Everything so far assumed one limiter box watching all traffic. But your gateway is a fleet (we made sure of that — no SPOFs at the front door), and a client's requests land on different instances. If each instance counts alone, a client capped at 100/min gets 100 per instance — ten gateways, a quiet 10× leak. The count has to live somewhere shared — in practice, Redis, sitting microseconds away from every gateway.

And the moment the count is shared, a classic bug appears. The naive code reads the counter, checks it, then increments — check-then-act. Two gateway instances handle two requests from the same client at the same moment: both read 99, both see "under 100, pass," both increment. Counter says 101. The limit leaked — not by much here, but under a real flood, every concurrent request at the boundary slips through the same crack. This is a race condition, and it's the same disease we've met before: two actors, one shared value, no coordination.

The cure is atomicity — make read-decide-increment one indivisible step no other request can interleave. In Redis that's a Lua script: the whole decision runs inside Redis as a single uninterruptible unit, one network round trip, no race. (For fixed windows, a bare INCR is already atomic — one of the reasons the simple algorithm stays popular.)

Two more decisions every production limiter has to make, both about imperfection:

• Exact or cheap? A perfectly global count means every request pays a Redis round trip. The pragmatic alternatives: each node limits locally at limit÷N (drifts when traffic is uneven across nodes), or nodes count locally and sync asynchronously (small overshoots during bursts). Precision versus latency and coupling — you pick per endpoint.
• Fail open or fail closed? Redis goes down. Do you let everyone through (fail open — availability first, the default for public APIs: the limiter protects the fleet, it shouldn't be an outage) or block everyone (fail closed — for login endpoints and payment flows, where "unlimited while the limiter's down" is exactly what an attacker prays for)? Decide it before the outage, per endpoint — it's a security posture, not an implementation detail.

How you reject matters nearly as much as what you reject — because a badly-delivered "no" creates the very stampede the limiter exists to prevent.

The correct "no" is HTTP 429 Too Many Requests, and it must carry a Retry-After header: "come back in 30 seconds." Here's why that header is load-bearing and not garnish. A client that gets a bare 429 with no guidance does the natural thing — retries immediately. So does every other limited client. Your limiter has now converted excess load into a synchronized instant-retry hammer — the retry storm from the health-checks lesson, self-inflicted at the front door. Retry-After breaks the loop: it spreads the comeback over time and tells well-behaved clients exactly when trying again will actually work.

Better still, don't let clients hit the wall blind. The convention popularized by GitHub and Stripe is to put the limit's state on every response, not just rejections: X-RateLimit-Limit: 100, X-RateLimit-Remaining: 12, X-RateLimit-Reset: 1720000000 (an IETF draft is standardizing these as RateLimit-*). Now a well-written client can pace itself — slow down as Remaining shrinks, sleep until Reset — and never see a 429 at all. The rate limit stops being a trap and becomes part of the API contract: published, machine-readable, cooperative.

The full courtesy loop, client-side, should sound familiar — it's the same discipline as the retry budgets we met at the load balancer: read the headers, back off with jitter, respect Retry-After. Limits work best when both sides know the rules.

Strip the names away and you're answering one question — what do bursts mean to you? — plus two practical ones about cost and honesty. The whole decision:

Your situation	Reach for
Public API, real clients with naturally bursty shapes	Token bucket — forgive the burst, enforce the average; two clean knobs
Downstream needs a steady pace (fragile DB, contractual pacing)	Leaky bucket — flatten everything into the drip
Low stakes, easiest possible ops, non-adversarial clients	Fixed window — knowing the 2× boundary hole is open
The count must be exact (billing, strict SLA), few clients	Sliding window log — pay the memory for the truth
Accurate-enough at massive scale	Sliding window counter — the log's honesty at O(1) price

And the prices, so you're never surprised: token bucket's burst is a spike your backend must absorb (capacity is a promise about your own headroom); leaky bucket taxes every legitimate burst with queueing delay or drops; fixed window's simplicity is paid for at the boundary; the log's exactness is paid in memory; the counter's efficiency is paid in a rounding error (0.003% wrong at Cloudflare scale — usually the best deal on the board).

If you remember one default: token bucket for people, leaky bucket for machines — humans arrive in bursts and deserve forgiveness; fragile downstreams need a metronome. Then let scale push you from log toward counter, and let atomicity (Lua, INCR) keep the count honest across the fleet.

Four beliefs that sound right and quietly bite:

• "Rate limiting is for attackers." Mostly it's for your own side: the intern's infinite loop, your best customer's midnight batch job, and your fleet's survival under honest overload. Abuse is one reason of four — if you tune the limiter only for villains, it will mangle your friends.
• "100 per minute means at most 100 in any minute." Under fixed window it means up to 200 in a boundary-straddling 60 seconds — reliably exploitable, forever. Only the sliding log makes the plain-English sentence literally true; the sliding counter gets within a rounding error. Know which promise your limiter actually makes.
• "Rejecting requests hurts users." A fast 429 with Retry-After is the good outcome. The alternative — letting everything through — is thirty-second timeouts for everyone while the fleet melts and health checks start ejecting boxes. The limiter isn't the thing hurting users; it's the thing keeping the site alive for the 95%.
• "Read the count, check it, increment it." On one box, fine. Across a fleet, check-then-act is a race — two gateways both read 99 and both pass. Sharing a counter without atomicity (a Lua script, an atomic INCR) doesn't slow the leak, it is the leak.

Twenty minutes, a terminal, and you'll have exploited the boundary hole with your own hands — which is worth ten readings of it.

1. Stand up the simplest limiter. In nginx, limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s; plus limit_req zone=api; on a location gives you a leaky-bucket-style limiter in two lines. Fire hey -q 5 (under the limit) and watch everything pass; fire hey -n 200 -c 50 (a flood) and watch the 429s (nginx returns 503 by default — set limit_req_status 429; for the proper code).
2. Feel the burst knob. Change to limit_req zone=api burst=20; and flood again — the first 20 excess requests now queue and pass (shaping); add nodelay and they pass instantly (the token-bucket flavor). One directive, three burst philosophies — you just toured token vs leaky in nginx config.
3. Exploit the boundary. Write a 15-line fixed-window limiter (a dict of counters keyed on int(time.time() // 60) in Python is plenty) with a limit of 100/min. Now script the attack: sleep until second 58 of the minute, fire 100 requests, wait 3 seconds, fire 100 more. Count the 200s: ~200 accepted in ~5 seconds. Then swap in two counters and the sliding-window-counter estimate (curr + prev * overlap) and run the same script — watch the second volley get rejected.
4. Race your own counter. Run your limiter on two processes sharing a Redis counter with naive GET-check-INCR, hammer both at once, and log when the counter exceeds the limit. Then move the logic into a Lua script (EVAL) and hammer again — the leak is gone. That's atomicity, felt.

The syntax is disposable; the muscle memory — bursts reveal the algorithm, boundaries hide a hole, shared counters race — is the lesson.

The front door's last job is saying no — cheaply, fairly, and politely — and every rate limiter is an answer to one question: what happens to a burst?

• Token bucket — forgive bursts up to capacity, enforce the average with the refill rate. The public-API default; two independent knobs.
• Leaky bucket — flatten every input into a fixed-rate drip. For downstreams that care about instantaneous pace, not averages.
• Fixed window — one resetting counter; cheapest to run, but a boundary-timer takes 2× your limit, reliably.
• Sliding window log — exact ("100 in any 60 seconds"), paid for in a timestamp per request.
• Sliding window counter — two counters and a weighted estimate; 0.003% wrong across 400M requests at Cloudflare. The workhorse at scale.
• Across a fleet the count lives in a shared store, and check-then-act races — atomicity (Redis Lua, INCR) is mandatory, and you choose fail-open (public APIs) or fail-closed (logins, payments) before the outage.
• Reject with 429 + Retry-After and publish X-RateLimit-* on every response — a limit clients can see is a contract; a bare 429 is a self-inflicted retry storm.

And with that, the front door is complete — in theory. It balances, routes, health-checks, spans continents, and now defends itself. Time to stop drawing and start typing: the next lesson is a codelab where you stand up two real servers, put nginx in front of them, and watch round-robin, health checks, and rate limits actually happen in your terminal. Everything §5 taught you, running on your own machine.