Token Bucket and Leaky Bucket
Core idea: Both algorithms count events against a clock, but they answer opposite questions — token bucket asks "have you saved up enough credit to spend right now?" (so it tolerates bursts), while leaky bucket asks "is there room in a queue that drains at a fixed rate?" (so it forces a smooth, steady output).
Heads-up — this is a design lesson, not a LeetCode puzzle. It lives in the Line Sweep chapter because rate limiting is time-windowed counting: you sweep a clock forward and tally events against a budget, exactly like sweeping a line across interval events. But there's no array to scan and no single "correct" output to assert — it's a systems-design topic about traffic, and the interview question is usually "design a rate limiter," not "return the answer." We'll treat it that way: two algorithms, side by side, with the trade-offs that actually come up in a design review.
Problem, rephrased
You run the API gateway in front of a payments service. Clients hammer it, and the backend falls over above roughly 5 requests per second per client. You need a gate at the edge that, for each incoming request, decides allow or reject (HTTP 429) — cheaply, in O(1), using almost no memory per client (you may be tracking millions of them).
The subtlety is how you spread the budget over time. "5 per second" could mean:
- "At most 5 in any one-second window, and a client may fire all 5 at once." That's bursty-but-bounded — what an API quota usually means.
- "Exactly one request every 200 ms, no clumping." That's a smooth, paced stream — what a downstream that can't absorb spikes needs.
These are different policies, and they map to the two algorithms. Consider a client that sends a clump of requests, then goes quiet:
time (s): 0.00 0.05 0.10 0.15 0.20 ... 1.00
request: R1 R2 R3 R4 R5 R6
Five requests arrive in the first 200 ms (a burst), then nothing until t = 1.0.
| request | arrives at | Token bucket (cap 5, refill 5/s) | Leaky bucket (drain 5/s, queue 5) |
|---|---|---|---|
| R1 | 0.00 s | allow (5 tokens, spend 1 → 4) | allow (queue 0→ serve now) |
| R2 | 0.05 s | allow (≈4 tokens → 3) | queued (drains 0.20 s later) |
| R3 | 0.10 s | allow (≈3 tokens → 2) | queued (drains 0.40 s later) |
| R4 | 0.15 s | allow (≈2 tokens → 1) | queued (drains 0.60 s later) |
| R5 | 0.20 s | allow (≈1 token → 0) | queued (drains 0.80 s later) |
| R6 | 1.00 s | allow (refilled to ~4 → 3) | allow (queue long drained) |
Same long-run rate (5/s), opposite short-run behavior. Token bucket let the burst of 5 through instantly. Leaky bucket accepted the same 5 but released them one every 200 ms — the client's clump became a smooth trickle to the backend. That difference is the whole topic.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson