hard Rate Limiting Algorithms: Token Bucket vs Leaky Bucket

Two knobs, one job: cap the request rate without punishing legitimate traffic

A token bucket refills at a steady rate and lets a request through only if it can debit a token, so idle time banks permits that can be spent all at once — a burst passes at full speed until the bank is empty, then throughput settles to the refill rate. A leaky bucket is instead a fixed-depth queue draining at a steady rate: requests queue up to be admitted, but they leave — and hit whatever sits downstream — at a constant pace no matter how bursty the arrivals were. Same average rate, opposite behavior at the burst: one is a limiter that tolerates spikes, the other is a shaper that erases them.

The two update rules

Token bucket (capacity C, refill rate r/s). Store two numbers — tokens and last_updated — and refill lazily on each request rather than running a background timer:

tokens = min(C, tokens + (now - last_updated) * r)   // lazy refill, capped at C
last_updated = now
if tokens >= 1: tokens -= 1; admit
else: reject (429)

Leaky bucket (queue depth C, drain rate r/s). Store queue_len and last_drained, and leak lazily the same way:

queue_len = max(0, queue_len - (now - last_drained) * r)   // lazy leak
last_drained = now
if queue_len < C: queue_len += 1; admit (queued, released downstream at rate r)
else: reject (429, overflow)

Traced: a burst of 20 hits capacity 10, rate 5/s

Both buckets start ready (token bucket full at 10 tokens, leaky bucket's queue empty) and see all 20 requests arrive simultaneously at t=0.

	Requests 1–10 (t=0)	Requests 11–20 (t=0)	After t=0
Token bucket	admitted instantly — 10 tokens spent, bucket → 0	rejected — bucket empty, 0 tokens (429)	+1 token every 0.2s (1⁄r) → 1 retried request admitted every 0.2s; the 10th retry is admitted at t=2.0s
Leaky bucket	enqueued — queue fills to 10/10	rejected — queue full, overflow (429)	1 request leaves the queue every 0.2s → a constant 5/s hits downstream; the 10th leaves at t=2.0s

Read the difference carefully: both admit exactly 10 immediately and reject the same 10, and both fully drain the accepted 10 by t=2.0s (10 requests ÷ 5/s = 2.0s). Where they diverge is what downstream sees. The token bucket's 10 admitted requests are handed off now — downstream takes an instantaneous spike of 10 at t=0. The leaky bucket's 10 admitted requests are queued, then released one every 0.2s — downstream never sees more than 1 at a time. Token bucket is a limiter that tolerates bursts; leaky bucket is a shaper that erases them and trades the spike for up to 2.0s of queueing latency on the last admitted request.

Fixed window: cheapest, but the boundary lets 2× through

A fixed window keeps one counter per clock-aligned window (e.g. per second) and resets it when the window rolls over; admit while count < limit. It's a single INCR + TTL — the cheapest limiter to run, and trivially shared across servers in Redis. Its flaw is the reset itself: nothing tracks how close together requests near a boundary actually are.

Traced: limit = 5 per 1-second window, matching the 5/s target rate. Window A = [0s,1s): 5 requests land at t=0.80–0.99s — count 5 ≤ limit 5, all admitted. Window B = [1s,2s): 5 more requests land at t=1.00–1.08s — count 5 ≤ limit 5, all admitted. Both windows are individually legal. But look at the wall clock: 10 requests landed inside 1.08−0.80 = 0.28 seconds — an instantaneous rate of 10⁄0.28 ≈ 36 req/s, over 7× the intended 5/s, with 2× the per-window limit crossing the boundary in a moment.

Sliding window fixes it — at a memory cost

A sliding-window log stores every request's timestamp and counts how many fall in the trailing window seconds — exact, but memory grows with request volume per key. Evaluate it the instant window B's first request arrives, at t=1.00s: the trailing 1-second window (0.00s,1.00s] already contains window A's 5 requests plus this new one — 6 > limit 5 — so it is rejected immediately, closing the exact bug above (a fixed window would have let it through because it resets, rather than slides).

A sliding-window counter gets most of that accuracy back at O(1) memory: it blends the current window's count with a time-weighted fraction of the previous window's count.

estimate = current_count + previous_count * (1 - elapsed_into_current / window)

At that same instant, t=1.00s (0% into window B): estimate = 1 + 5 × (1 − 0) = 6, above the limit of 5 — it throttles too, without storing a single timestamp. It's an approximation (a lopsided traffic shape inside the previous window makes the weighting inexact), but in practice it tracks the log closely enough that it is the usual production choice (this is the approach Cloudflare documents for its own rate limiter).

Pitfalls

• Confusing "same admit count" with "same behavior." In the traced example both algorithms admit 10 and reject 10 — but a token bucket floods the accepted burst into whatever is downstream immediately, while a leaky bucket delays it. Sizing a token bucket's capacity as if it were "just a rate limit" ignores that C is literally the largest instantaneous flood you will ever forward.
• Per-node buckets multiply the limit. N app servers each running a local in-memory bucket give an effective limit of N×r, not r — centralize the state (Redis + an atomic Lua script for the read-modify-write) or pin each key to one node.
• Wall-clock time, not monotonic. If now - last_updated goes negative (an NTP step back, a paused VM), the lazy refill mints free tokens or the lazy leak corrupts the queue depth. Use a monotonic clock for the elapsed-time term.
• Fixed-window limits reset on a fixed clock boundary, which is exploitable. Anyone who knows the reset instant (e.g. "per calendar minute") can double their real throughput for free by timing requests around it — no cleverness required, as traced above.
• Leaky bucket under sustained overload is pure queueing latency, not extra rejections. If arrivals keep exceeding r, the queue sits full and every newly accepted request waits the maximum; if callers have their own timeouts they can time out while you are still doing the (now wasted) work. Consider shedding load earlier rather than growing an ever-full buffer.

Choosing among the four

The real interview question is rarely "token bucket or leaky bucket" in isolation — it's which of these four fits the endpoint in front of you.

• Token bucket — when bursts are legitimate and you want to allow them under an average cap. The default for public API quotas (Stripe, GitHub, AWS all use a token-bucket-style limiter): a page load firing 8 calls at once, or a batch job flushing, shouldn't be punished if the sustained rate stays under r. Trade-off vs leaky bucket: it lets the burst hit whatever is downstream, which is fine only when that downstream can absorb C requests at once.
• Leaky bucket — when the downstream is fragile or fixed-capacity and must never see a spike. A legacy backend, a payment processor with its own hard cap, an egress feed to a partner (NGINX's limit_req is a leaky bucket for exactly this reason). Trade-off vs token bucket: you buy a flat output rate by paying queueing latency — in the traced example the 10th accepted request waits the full 2.0s even though it was "accepted" at t=0.
• Fixed window — when you only need coarse quota accounting and boundary bursts are harmless ("1000 calls/day"). The cheapest to build and shard (one INCR+TTL per key). Trade-off vs sliding window: you accept the up-to-2× boundary burst in exchange for O(1), trivially-shardable state.
• Sliding window (log or counter) — when you need accurate, burst-suppressing limits and can't tolerate the fixed-window bug. Use the log only at low key cardinality/volume, since memory grows with request count; use the weighted counter (the common production choice) everywhere else — it buys back nearly all the accuracy at O(1) memory per key.

One-line rule: let the burst through (token bucket) when downstream can take it and clients legitimately spike; smooth the burst away (leaky bucket) when downstream can't; use a fixed window only for cheap, coarse quotas; reach for a sliding-window counter whenever you need real accuracy without a full log.

Two things get harder once this single-node picture goes distributed, each covered on its own page: a single hot tenant key still bottlenecks one Redis shard no matter how the cluster is sized, because sharding spreads different keys, never one key (see Rate-Limit Hot Keys); and once the limiter runs in multiple regions, the shared quota becomes a consistency problem where PACELC decides whether you enforce a strict, slower global count or a fast, locally-approximate one (see Multi-Region Rate Limiting).

Takeaways

• Token bucket banks idle capacity as tokens, so a burst up to C passes at full speed before settling to the refill rate r; leaky bucket queues arrivals and drains them at a constant r, so no burst ever reaches downstream.
• With C=10, r=5/s and a burst of 20, both admit the same 10 and reject the same 10 — the difference is timing: token bucket delivers its 10 to downstream instantly at t=0, leaky bucket trickles them out one every 0.2s through t=2.0s.
• Fixed window is cheapest but lets up to 2× the limit through at the window boundary; a sliding-window log fixes this exactly at O(requests) memory, a sliding-window counter fixes it approximately at O(1) memory — the usual production pick.
• Pick by what the downstream needs: allow the burst (token bucket) when it can absorb C at once; erase the burst (leaky bucket) when it can't; reach for windows only when you're purely counting quota, not shaping traffic.

---

Mechanisms follow Tanenbaum & Wetherall's traffic-shaping treatment of token/leaky buckets and the ATM Forum's GCRA (virtual scheduling) formulation of the leaky bucket; the sliding-window counter follows Cloudflare's published rate-limiting design; production usage per Stripe, GitHub, AWS, and NGINX limit_req engineering docs. Re-authored and deepened for this guide with a from-scratch numeric trace (C=10, r=5/s, burst of 20) and a derived fixed/sliding-window boundary-bug example. See also: Rate-Limit Hot Keys; Multi-Region Rate Limiting.

I just read a lesson on **Rate Limiting Algorithms: Token Bucket vs Leaky Bucket** (System Design) and want to truly understand it. Explain Rate Limiting Algorithms: Token Bucket vs Leaky Bucket from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Rate Limiting Algorithms: Token Bucket vs Leaky Bucket** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Rate Limiting Algorithms: Token Bucket vs Leaky Bucket** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Rate Limiting Algorithms: Token Bucket vs Leaky Bucket** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.