The token bucket algorithm, step by step

A token bucket is a rate-limiting algorithm with two numbers: a capacity and a refill rate. Tokens drip into a bucket at the refill rate until it is full; every request takes one token, and a request that finds the bucket empty is refused or delayed. A quiet client can therefore send a short burst, while a busy one is held to the steady rate, which is close to how real applications behave.

Section Rate limiting Updated 12 Oct 2026 Parameters capacity, refill rate

Quick facts

Capacity: The largest burst allowed after a quiet period
Refill rate: The sustained rate a client can keep up indefinitely
State per client: Token count and the time of the last refill
Also used in networks: Traffic policing, for example the single rate three color marker (RFC 2697)
Close relative: Leaky bucket, which smooths output instead of admitting bursts

The other algorithms, fixed and sliding windows, are compared on rate limiting algorithms.

How the token bucket algorithm works

Each client has a bucket. Keyed by whatever the limit counts: address, user or API key.
Tokens are added at the refill rate. Not by a timer, but by computing how many would have arrived since the last request.
The bucket never holds more than its capacity. Extra tokens are discarded.
Each request takes one token. Expensive requests can take more than one.
No token, no request. The request is refused, usually with 429 and a Retry-After value, or queued.

pseudocode

on request(key, cost = 1):
    b = bucket[key] or {tokens: CAPACITY, last: now}
    elapsed = now - b.last
    b.tokens = min(CAPACITY, b.tokens + elapsed * RATE)
    b.last = now
    if b.tokens >= cost:
        b.tokens -= cost
        bucket[key] = b
        return allow
    wait = (cost - b.tokens) / RATE
    bucket[key] = b
    return refuse(retry_after = ceil(wait))

Choosing capacity and refill rate

Set the refill rate from what a legitimate client needs over a minute or an hour, and the capacity from the largest burst it produces in normal use. For example, a page that loads twenty resources at once needs a capacity of at least twenty, even if the client then sends one request a second.

Measure before choosing: run the limit in a mode that only records what it would refuse, as on monitor mode, and read who would have been refused. Bursts are the most common cause of limits that refuse real users; see bursts and rate limits.

// four algorithms, and what makes the token bucket different

A token bucket example, step by step

Take a capacity of 10 and a refill rate of 1 token a second. A client that has been quiet starts with 10 tokens and sends 10 requests at once: all pass, and the bucket is empty. Half a second later an eleventh request finds half a token and is refused, with a retry after one second.

Three seconds after the burst the bucket holds 3 tokens, so three more requests pass. If the client then settles at one request a second, every request passes indefinitely, because each spends exactly what the refill adds. Ten seconds of silence restore the full capacity, and the client may burst again.

Token bucket vs leaky bucket

A leaky bucket holds requests in a queue and releases them at a constant rate, like water from a hole in a bucket. Output is perfectly smooth, but a burst becomes a wait, and a full queue refuses new requests.

A token bucket admits a burst immediately as long as tokens remain. Use a token bucket when clients are interactive and bursts are normal; use a leaky bucket when the system behind the limit needs a steady flow, such as a downstream service with a fixed capacity.

Token bucket in networking: policing and shaping

Networks used token buckets long before web applications did. A policer drops or marks packets that find no token, which keeps a flow within its contract at the cost of losses. A shaper holds such packets in a queue until tokens arrive, which smooths the flow at the cost of delay. Both appear in the architecture for differentiated services, RFC 2475.

Web rate limits mostly behave like policers: a request without a token is refused with 429 rather than held. Queuing requests, the shaping approach, is possible, but it ties up connections while they wait and suits background jobs better than interactive clients.

Running a token bucket on several servers

With one server, the bucket lives in memory. With several, the bucket must be shared, or each server enforces its own share of the rate. A shared store needs the read, refill and decrement to happen as one atomic step, or two servers will both spend the last token.

Per-server shares are simpler and drift when traffic is uneven between servers. The trade-offs are on distributed rate limits.

Questions

What is the token bucket algorithm?

A rate-limiting algorithm in which tokens are added to a bucket at a fixed rate up to a capacity, and each request spends a token; requests that find the bucket empty are refused or delayed.

What is the difference between token bucket and leaky bucket?

A token bucket admits bursts up to its capacity and then holds clients to the refill rate. A leaky bucket queues requests and releases them at a constant rate, smoothing output.

How do I choose token bucket parameters?

Set the refill rate from what a legitimate client needs over time and the capacity from its largest normal burst, then confirm by recording what the limit would refuse before enforcing it.