Token bucket, leaky bucket and sliding window: how rate-limiter algorithms differ

What it is

The policy side (which key, which headers, which status) is covered elsewhere; this article compares the counting algorithms.

• Fixed window: one counter per key and interval, reset at the boundary. Cheapest, but a client can spend a full limit at the end of one window and another at the start of the next: twice the nominal rate in a short span.
• Sliding log: keep every request's timestamp and count those inside the trailing interval. Exact; memory grows with volume.
• Sliding-window counter: keep the current and the previous window's counts and estimate the trailing interval as previous * (1 - elapsed / window) + current. Approximate, constant memory, no boundary burst.
• Token bucket: a bucket holds up to a maximum number of tokens and is refilled at a fixed rate; each request takes one token and is rejected when none is left. Envoy's TokenBucket configuration names exactly these parameters: max_tokens, tokens_per_fill and fill_interval, and the bucket starts full.
• Leaky bucket: requests enter a queue that drains at a fixed rate; the queue has a capacity beyond which requests are rejected. nginx's limit_req documents this as its method, with rate, a burst size and nodelay or delay to choose whether excess requests within the burst are delayed to the rate or served immediately.

Why it matters

The algorithm determines burst tolerance, memory per key and whether clients see rejection or added latency. Clients that retry at a fixed-window reset arrive together; a token bucket absorbs a short burst and then enforces the average; a delaying leaky bucket smooths backend load at the price of queueing time.

How to apply

• Default to a token bucket per key: store the token count and the last refill time, refill lazily on each request, and make the update atomic (one Redis script, or an in-process lock).
• Set the bucket size to the burst you accept and the refill rate to the sustained limit; document both numbers.
• Use a sliding-window counter when the promise is a plain "N requests per minute" and boundary bursts are unacceptable.
• Use a delaying leaky bucket in front of a backend, not at the edge, where interactive clients prefer a fast 429 with Retry-After.
• In a distributed deployment centralise the state per key or accept that per-instance limits multiply by the instance count; use a monotonic clock for refill arithmetic.

Pitfalls

Wall-clock jumps corrupt refill arithmetic. A bucket that starts empty blocks every new key until it fills. Sliding logs are a memory attack surface. Keying by client IP behind NAT or a CDN limits the wrong population. Undocumented burst rules make well-behaved clients guess.