Choosing an Algorithm

In one line: an interviewer rarely wants all five recited. They want one, chosen for a stated reason. This lesson is the decision procedure.

The comparison

Algorithm	Space efficient	Allows burst?
Token bucket		Yes, it allows a burst of traffic within a defined limit
Leaking bucket
Fixed window counter		Yes, it allows bursts at the edge of the time window and can exceed the defined limit
Sliding window log	No — maintaining the log requires extra storage	Yes, it allows bursts when the window is empty or nearly empty, though it smooths out traffic as the window fills
Sliding window counter	Yes, but requires relatively more space than other space-efficient algorithms	Smooths out the burst

The 'allows burst' column conflates two very different things

Read rows 1 and 3 carefully — both say "yes," and they mean opposite things.

Token bucket allows a burst by design, within a bound you configured. Capacity C is a parameter you chose precisely to say how large a spike you tolerate. The burst is intentional and bounded.

Fixed window counter allows a burst as a defect. Nobody chose 2x; it falls out of resetting a counter at an arbitrary instant, and a client can trigger it deliberately.

Sliding window log allows a burst in the mildest sense — a client that was idle can use its full allowance at once, which is exactly correct behaviour and not an overshoot at all. It never exceeds L per window.

So the column really encodes three distinct behaviours: configured burst, defective overshoot, and legitimate use of an unused allowance. Collapsing them into one "yes" is the table's weakness, and spotting that is a strong signal.

A decision procedure

Choose	When	Because
Token bucket	The default for API rate limiting	Two independent knobs — burst tolerance and sustained rate — with O(1) state computed lazily. Real traffic is bursty, not paced
Leaking bucket	The downstream cannot absorb spikes — a legacy system, a third-party API with hard caps, fixed-rate hardware	Guarantees the downstream never sees more than `R_out`, whatever arrives
Fixed window counter	The limit is an approximate capacity guard and state must be minimal	One integer per client per window; `INCR` + `EXPIRE` and you're done. Accept the 2x boundary
Sliding window log	Strict enforcement on a small, trusted client set	Exact — never more than L in any window. Only viable where memory can't be weaponized
Sliding window counter	Strict-ish enforcement at scale	Fixes the boundary with constant state; sub-1% error in practice. What most CDNs and gateways run

The two questions that actually decide it

Everything above reduces to two:

Does the downstream tolerate bursts? If genuinely no, it is leaking bucket and nothing else — it is the only algorithm that guarantees a constant output rate.
Does the limit need to be enforceable, or is it a capacity guard? An enforceable limit — a billing quota, a brute-force defence, a contractual API tier — a client has incentive to game, so the fixed-window boundary is disqualifying and you want a sliding window. A capacity guard just needs to stop runaway traffic, so a 2x edge case is irrelevant and cheapness wins.

Answer those two out loud before naming an algorithm, and the choice sounds derived rather than recalled.

Different limits in one system can use different algorithms

Nothing requires one algorithm everywhere, and real systems mix them:

Public API quotas → token bucket. Clients get burst headroom, sustained rate is enforced, state is tiny.
Login and password reset → sliding window counter, per-IP and per-target-account. Strict enforcement matters and the boundary is exploitable by exactly the people attacking you.
Calls to a metered third-party API → leaking bucket. You must never exceed their rate, so pace your own output.
Global capacity backstop → fixed window. Coarse, cheap, and only needs to catch aggregate runaway.

Volunteering that these are per-limit rather than per-system decisions is a strong close, because it shows you have thought about a real deployment rather than a single-algorithm toy.

One thing the table doesn't capture: what the client experiences

Memory and burst are the two axes here, but a third matters operationally: how the client finds out.

Leaking bucket makes the client wait — it will see latency and may time out, having no idea it was throttled. Every counter-based algorithm rejects immediately with a 429, which the client can act on.

Fast, explicit rejection with a Retry-After is almost always kinder than silent delay: it lets the client back off correctly and it doesn't hold your memory. That is a real argument for counter-based algorithms beyond anything in the comparison table, and it connects back to Lesson 5's point about 429 versus 503.

Key takeaway

Compare on memory and burst — but note "allows burst" means three different things across the rows: configured, defective, and legitimate. Two questions decide it: can the downstream absorb spikes, and does the limit need to be enforceable or is it a capacity guard? Default to token bucket; use sliding window counter where enforcement matters at scale.

One more worth knowing by name

GCRA — the generic cell rate algorithm — is what several production limiters use under the hood, and it is worth recognizing because it looks unfamiliar and is not a sixth idea.

It is token bucket expressed as a single timestamp rather than a stored count. Instead of tracking tokens and refilling them, it stores the earliest time at which the next request would be conforming, and compares the clock against it. Same behaviour as token bucket including the configured burst, with one value per client and no refill loop — which is why it appears where memory and atomicity both matter.

Mentioning it signals familiarity with real implementations. Just do not present it as a distinct strategy: it is an implementation of token bucket, not an alternative to it.

Interview signal by level

Level	What a strong answer sounds like
L4	"I'd use token bucket, it's the most common."
L5	Chooses with a reason: "token bucket, because capacity and refill rate are independent, so we can allow a reasonable spike while holding the sustained rate — and it's O(1) state per client."
Staff+	Derives it and mixes: "two questions — can the downstream take a spike, and is the limit enforceable or a capacity guard. For a public API it's a capacity guard with burst tolerance, so token bucket. For login it's enforceable and attackers will game a fixed window's boundary, so sliding window counter, keyed on IP and target account. And for our calls out to a metered third party, leaking bucket, because there we must never exceed their rate. Different limits, different algorithms."

Next: the whole design under interview conditions.