DesignFlix 10: Token Bucket Bursts and Leaky Bucket Waiting

Ten requests arrive together. Do we let some through immediately, or make them wait and leave at a steady pace?

Both can be sensible rate-limiting policies. A user opening a page may need a short burst of calls. A downstream service with tight capacity may need smoother arrivals. Token buckets and leaky buckets help express those different needs.

Let's compare the same small burst under both, so the bucket metaphor turns into behaviour we can test.

A token bucket lets you spend saved capacity

A token bucket fills at a configured rate up to a maximum. Each accepted request spends a token. If no token is available, the limiter applies its configured rejection or waiting policy.

Suppose the bucket holds six tokens and refills at two per second. After an idle period, six requests can pass immediately. A seventh arriving at the same moment cannot spend a token that isn't there.

After one second, two tokens have returned, so two more requests can pass. The maximum capacity caps the saved allowance; an hour of inactivity doesn't accumulate an hour's worth of unlimited requests.

This suits features where a small burst is normal but sustained traffic must be bounded. The burst allowance and refill rate are separate choices. Setting "two per second" without saying "up to six at once" leaves an important part of the policy unstated.

No token? You shall not pass!

Calculate refill from elapsed time

A limiter doesn't necessarily need a background task adding tokens every second. It can calculate the refill when a request arrives.

Here's a single-process teaching example with a caller-supplied elapsed-time clock:

def consume(tokens, last_time, now):
    tokens = min(6, tokens + 2 * (now - last_time))
    if tokens < 1:
        return False, tokens, now
    return True, tokens - 1, now

tokens, last_time = 6, 0
for _ in range(6):
    allowed, tokens, last_time = consume(tokens, last_time, 0)
    assert allowed
assert consume(tokens, last_time, 0)[0] is False
assert consume(tokens, last_time, 1)[0] is True

The example shows accumulation capped at six and immediate requests consuming that allowance. A real implementation needs monotonic time and an atomic update of shared state. Two callers must not both spend the same final token.

If every server keeps a separate bucket, the combined allowance grows with the number of servers. That may be an intentional local protection policy, but it isn't automatically a global account limit. Envoy's local rate limiter is one documented token-bucket implementation with that scope distinction.

A queueing leaky bucket smooths departures

Now use the queueing version of a leaky bucket. Requests enter a bounded queue and leave at a chosen rate, such as two per second. A burst can wait in the queue instead of all reaching the destination immediately.

That gives the downstream service smoother arrivals, at the cost of waiting time. Six queued requests represent roughly three seconds of work at two per second, before considering the service's own delays.

When the queue is full, the implementation must refuse or drop excess work according to its policy. An unlimited waiting room would simply turn overload into unbounded memory and latency.

The name "leaky bucket" also appears in meter-style limiters that track a draining level rather than literally queueing requests. Check the product's behaviour instead of inferring it from the metaphor. NGINX's request-limiting module, for example, exposes delay and burst controls.

Compare the user-visible trade-off

For our burst, the important difference is when requests reach the destination:

Neither guarantees that the destination can handle every accepted request. An expensive export and a cheap health check shouldn't necessarily cost the same allowance. Choose the scope and cost model around the resource you're protecting.

Is your feature hurt more by a short burst, or by making every request wait?

Tell callers how to recover

For an HTTP API, a rejected request may return 429 Too Many Requests with useful retry guidance. Callers should wait rather than immediately retry in a tight loop.

A waiting policy needs a deadline too. If a request becomes useless after a second, placing it behind several seconds of queued work is not a helpful success. Make the admission result and expected behaviour visible in the API contract.

Monitor rejections, waiting time and downstream pressure. A limiter that protects one service by making every user wait indefinitely has met only part of the requirement.

Choose the allowance before choosing the metaphor

For a burst-friendly API, start by defining how much immediate work is acceptable and what sustained rate you can support. For a smoother pipeline, define how long work may wait and how much can be queued.

Those decisions give the algorithms their purpose. Then test a burst, a sustained overload and simultaneous calls on multiple instances. The question to answer is simple: does the actual traffic match the policy we meant to offer?