Leaking Bucket and Fixed Window Counter

In one line: leaking bucket is the one algorithm that cannot burst, which makes it right for a specific class of downstream. Fixed window is the simplest, and its boundary bug is the most commonly asked question in this chapter.

The leaking bucket algorithm

Token bucket and leaking bucket are near-mirror images

Both use a bucket metaphor, and that similarity hides an opposition worth stating cleanly.

Token bucket holds permits that accumulate while you are idle. A burst is served immediately if credit exists. Output rate is variable; input is unconstrained.

Leaking bucket holds requests that drain at a fixed speed. A burst is queued and paced out. Output rate is constant; input is buffered.

So the deciding question is: what does the downstream need? If it can absorb a spike, token bucket serves the burst and everyone is happier. If it cannot — a legacy system, a third-party API with hard limits, a device with a fixed processing rate — leaking bucket guarantees it never sees more than R_out, no matter what arrives.

Token bucket protects a rate budget; leaking bucket protects a downstream.

Why not always use leaking bucket if constant outflow is 'better'?

"If the leaking bucket ensures a constant outflow, why not always prefer it over the token bucket for predictable systems?"

Because constant outflow buys predictability by spending latency, and it spends it on the wrong requests.

A burst fills the queue. Every request behind that burst now waits — including a request from a completely different user who arrived while the queue was draining. "bursts can fill the bucket quickly, potentially delaying recent requests." Recent, well-behaved traffic pays for earlier bad behaviour.

There are two further costs. It holds state per queued request, not per client, so a deep queue is real memory. And queued requests may become worthless — a client that timed out five seconds ago still has its request sitting in the bucket, and you will dutifully process it, spending capacity on a response nobody will read.

Token bucket rejects immediately instead, which is often kinder: the client learns now and can retry with backoff, rather than waiting and then timing out.

So the answer is: prefer leaking bucket when the downstream genuinely cannot absorb bursts, and accept the latency. Otherwise the fast rejection is usually better behaviour.

The trade that distinguishes it from token bucket: token bucket rejects excess immediately, leaking bucket delays it. Rejection is honest and fast; queuing is gentler on the client and turns an overload into a latency problem, which is worse when the queue is unbounded.

The fixed window counter algorithm

The boundary problem

A significant drawback is the potential for traffic bursts at window edges. The source's example:

Limit: 10 requests per minute

01:00 --------- window 1 --------- 02:00 --------- window 2 --------- 03:00
                              ^^^^         ^^^^
                          10 requests   10 requests
                          at 01:59      at 02:00

Window 1 count = 10   (within limit)
Window 2 count = 10   (within limit)

But the interval 01:59 -> 02:01 saw 20 requests
in roughly two seconds. Twice the intended rate.

Fixed window can serve exactly 2x its limit, and it is trivially exploitable

This is the most-asked follow-up in the whole chapter, so be able to state it crisply: a client can always achieve 2R in a window of size W by firing R requests at the very end of one window and R at the very start of the next.

It is not a rare race — it is deterministic and easy to exploit. Any client that knows your window boundaries (and boundaries are usually aligned to wall-clock minutes, so they are guessable) gets double the limit for free.

Compare with token bucket's edge case from Lesson 8: that overshoot was bounded by the bucket capacity, a parameter you chose deliberately to permit bursts. Fixed window's overshoot is not a design choice — it is an artifact of resetting the counter at an arbitrary instant.

The fix is what the remaining two algorithms do: stop treating time as discrete buckets and start measuring a window that moves with the request.

Fixed window is still the right answer sometimes

Do not over-learn the criticism. Fixed window is one integer per client per window — the cheapest possible state — and it is trivially implementable with INCR plus EXPIRE in Redis, which Lesson 6 showed is atomic and fast.

When the limit is a soft capacity guard rather than a strict contract, 2x overshoot in the worst-aligned instant is often irrelevant. If you are protecting a service that can handle 10x its nominal load, the boundary bug costs you nothing and you saved real complexity.

The rule: fixed window is fine when the limit is approximate and the state budget is tight. It is wrong when the limit is a billing quota, a security control, or anything a client has an incentive to game.

This is the defect that motivates both sliding-window variants, and it is worth drawing rather than describing: the overshoot is not a tuning problem, it is structural to resetting a counter at a fixed instant.

Interview signal by level

Next: the two algorithms that fix the boundary.