Token bucket
A rate-limiting algorithm that holds tokens refilled at a fixed rate; each request consumes one. It allows bursts up to the bucket capacity while enforcing an average rate over time. Empty bucket = request denied or delayed.
- API rate limiting where bursts should be tolerated.
- Shaping traffic into a downstream with bounded capacity.
- When you need a hard per-window cap with no bursts (use fixed window).
- Strict ordering/spacing of requests (use leaky bucket).
Definition
Tokens accumulate in a bucket up to a max capacity at a refill rate of R tokens/sec. Each request removes N tokens. If enough tokens exist it's allowed; otherwise rejected or queued. Capacity controls burst size, refill rate controls sustained throughput.
Why it exists
Real traffic is bursty. Fixed windows reject legitimate bursts; token bucket absorbs short spikes while still bounding the long-run average rate, which matches how capacity actually behaves.
How it works
Store (capacity, tokens, last_refill_ts). On each request compute elapsed time, add rate*elapsed tokens (capped at capacity), then subtract. The computation is stateful and must be atomic in a shared store (Redis Lua) to be correct across nodes.
Scaling limits
Single bucket is O(1) and trivial. Millions of per-user buckets need sharded storage; refill math must use a monotonic clock to avoid negative elapsed time.
Cost shape
Memory per bucket (small) and one read-modify-write per request. Cost scales with distinct identities, not request volume.
Alternatives
- Leaky bucket — Smooths to a constant outflow but rejects bursts you might want to allow.
- Sliding window — More precise recent-rate limit, slightly more memory/CPU.
Failure modes
- Non-atomic refill+decrement causing over-allow under concurrency.
- Clock going backwards producing huge elapsed time.