Token Bucket

In one line: token bucket is the most widely deployed rate-limiting algorithm, and the reason is a feature people mistake for a bug: it allows bursts deliberately.

How it works

Assume a rate limit of R and a total bucket capacity of C:

1. A new token is added to the bucket every 1/R seconds.
2. If the bucket reaches capacity C, incoming tokens are discarded.
3. Incoming requests consume tokens. If N requests arrive and at least N tokens exist, the requests are processed.
4. If the bucket has fewer tokens than incoming requests, the system processes only the available number and discards the rest.

Worked example

Bucket capacity is three, refilling at three tokens per minute:

Start:   [T][T][T]   three tokens

Request 1 arrives within the minute  -> consumes a token   [T][T][ ]
Request 2 arrives within same minute -> consumes a token   [T][ ][ ]
Request 3 arrives within same minute -> consumes a token   [ ][ ][ ]
Request 4 arrives within same minute -> REJECTED, bucket empty

After one minute: refill                                   [T][T][T]

Parameters

Capacity and rate are two independent knobs — that's the whole design

C controls how large a burst you tolerate; R controls the sustained rate. They are separate, and that separation is why token bucket is so widely used.

Set C = 100, R = 10/s and a client can fire 100 requests instantly after being idle, then settles to 10/s. Set C = 10, R = 10/s and it can never burst above 10 no matter how long it has waited.

Most other algorithms conflate these. Fixed window has one number; leaking bucket's queue depth affects latency rather than burst tolerance. Token bucket lets you say "average 10 per second, but I don't mind a spike of 100" — which is exactly how real traffic behaves, since clients are idle and then active rather than perfectly paced.

The idle-time framing is the useful mental model: the bucket accumulates credit while you're quiet, and you can spend it when you're busy.

The reason token bucket is the usual default: the two parameters map onto two questions a product owner can actually answer — how fast may they go on average, and how big a spike is acceptable — rather than onto an implementation detail.

Advantages and disadvantages

Memory efficiency is better than 'minimal state' suggests

Per client, the algorithm needs two values: the current token count and the timestamp of the last refill. That is it.

And you do not run a timer adding tokens — you compute them lazily on access:

elapsed = now - last_refill
tokens  = min(C, tokens + elapsed x R)
last_refill = now

So there is no background process, no per-client scheduling, and the state is a couple of numbers. That is why token bucket scales to millions of clients on modest infrastructure, and it contrasts sharply with sliding window log, which stores a timestamp per request.

The edge case: exceeding the limit

"Apart from permitting bursts, can the token bucket algorithm surpass the limit at the edges?"

Yes. The worked example:

Bucket capacity 3, rate limit 3 requests per minute, giving a refill rate of 0.33 minutes — a new token every 0.33 minutes.

t = 1.00 min   Three tokens accumulated.
               A burst arrives, consumes all three.  -> 3 requests served
               Bucket empty.

t = 1.33 min   A new token is added (refill rate 0.33).
               A new request arrives and consumes it. -> 1 request served

Window from t = 0.66 to t = 1.33  (about 0.67 min):
               4 tokens consumed against a limit of 3 per minute.

This example shows that the token bucket can surpass the limit at the edges.

The overshoot is bounded, and knowing the bound is the useful part

This is not unbounded. In any window, the most a client can consume is C (a full bucket) plus R × window (tokens refilled during it). With C = R, that is at most twice the nominal rate in the worst-aligned window.

That bound is worth having, because it tells you how to control it: shrink C relative to R if you need tighter enforcement, at the cost of tolerating no bursts. It also tells you the algorithm never permits an unbounded overshoot, unlike a naive fixed window where two adjacent windows can both fill completely.

So the honest characterization is: token bucket allows a bounded burst by design, and the edge case is that burst landing at an awkward boundary. If your requirement is a strict per-window ceiling, this is the wrong algorithm — use sliding window log. If your requirement is a sustained rate with tolerance for spikes, this is exactly right.

Where you have already seen this algorithm

Token bucket is everywhere once you recognize it. AWS API throttling, Stripe's API limits, Linux traffic shaping (tc), Envoy and most API gateways, and GitHub's API quota all use it or a close variant.

The reason for that near-universality: it is the only common algorithm that separates burst tolerance from sustained rate while needing constant state per client. Every other option gives up one of those.

If an interviewer asks which algorithm you'd choose and you have no unusual constraint, token bucket is the defensible default — and being able to say why (two knobs, O(1) state, lazy refill, bounded overshoot) is what makes it a considered choice rather than a guess.

Interview signal by level

Next: the algorithm that refuses to burst at all.