The Token Bucket: How Rate Limiters Shape Traffic

The mechanism, step by step

A token bucket holds at most B tokens — the burst size or bucket capacity — and is refilled at a steady r tokens per second, the refill rate. Every unit of work — a request, a packet, or a byte — must remove a token to proceed. Three rules govern it:

1. Refill: tokens accrue at rate r, but the bucket never overflows — once it holds B tokens, extra ones are discarded, so idle time saves at most B tokens.
2. Consume: an arriving request inspects the bucket; if at least one token is present it removes one and passes (it is conforming), and the count drops.
3. Empty: if no token is available the request is non-conforming, and the limiter reacts in one of two ways.

Those two reactions name the two operating modes. A policer drops or marks the non-conforming request immediately — this is what a network ingress filter or an API gateway returning 429 Too Many Requests does. A shaper instead delays the request, queuing it until enough tokens accrue, so the output stream is smoothed rather than discarded. The elegance is that saved-up tokens let a client that has been quiet fire a burst of up to B requests at once, while the long-run average can never exceed r. The bucket rewards restraint with slack and still enforces the contract.

Lazy refill: two numbers and some arithmetic

A naïve implementation runs a background timer that adds tokens every tick — but with millions of API keys that means millions of wakeups. Real systems refill lazily, computing the token count only when a request arrives, using pure arithmetic over a stored timestamp. Each bucket stores exactly two numbers, tokens and last_refill:

now      = monotonic_clock()
elapsed  = now - last_refill
tokens   = min(B, tokens + elapsed * r)
last_refill = now
if tokens >= cost:
    tokens -= cost      # cost may be >1 for heavy calls
    return ALLOW
return DENY

This is O(1) time and O(1) space per key — a subtraction, a multiply, a min, and a compare. There is no queue to scan and no per-tick work at all. Three details separate a correct implementation from a subtly broken one. Use a monotonic clock, never wall-clock time: an NTP step or leap-second adjustment can jump wall time backward and mint or destroy tokens out of thin air. Prefer integer arithmetic — track tokens in scaled fixed-point units, say nanotokens — because a repeated floating-point tokens += elapsed*r accumulates rounding drift over long idle spans. And the read-modify-write must be atomic: two concurrent requests that both read the same count can each decide to pass, over-admitting. Real code enforces atomicity with a per-key lock, a compare-and-swap loop, or, in Redis, a Lua script that runs the whole check-and-decrement as one indivisible step.

Why it works: the r·T + B guarantee

The token bucket's promise is precise and provable. Over any time interval of length T, the number of conforming units it admits is bounded by:

admitted(T) ≤ r·T + B

The proof is one sentence. Tokens are created at rate r and the bucket starts an interval with at most B; so the total tokens available to spend during an interval of length T is at most the B already there plus the r·T minted during it — and since each admission spends one token, admissions cannot exceed that supply. The B term is the instantaneous burst the system tolerates; the r term is the enforced long-run average, because as T grows the r·T term dominates and the average rate is pinned to r.

This is not folklore — it is the arrival curve of network calculus, the theory René Cruz formalized in 1991. A source constrained by a token bucket is called (σ, ρ)-regulated, with burst σ = B and rate ρ = r, and its cumulative arrivals obey A(t) − A(s) ≤ ρ·(t − s) + σ. Feed such a flow into a work-conserving link and you get hard, computable bounds on worst-case queue backlog (≤ σ) and delay — which is exactly why token buckets sit at the heart of QoS guarantees. The (r, B) pair is the traffic contract: two numbers that completely describe the promised shape of a flow.

Versus the leaky bucket and the windows

The token bucket is easy to confuse with three look-alikes. The leaky bucket is its most-cited cousin, and the comparison hides a subtlety. The leaky-bucket-as-a-queue (a shaper) holds arrivals in a FIFO and drains them at a fixed rate r, like water through a hole: the output is perfectly smooth and no burst is ever allowed out. That is the true opposite of the token bucket, which lets a saved-up burst of B through instantly. Confusingly, the leaky-bucket-as-a-meter — and its telecom incarnation, the Generic Cell Rate Algorithm (GCRA) that polices ATM cells — is the mathematical dual of the token bucket and makes byte-for-byte identical accept/reject decisions; it just tracks a theoretical arrival time instead of a token count.

The fixed-window counter keeps one integer per key per clock window (say, 100 requests per minute) and resets it at the boundary. It is trivial, but it has an ugly edge: a client can send 100 requests in the last instant of one window and 100 more in the first instant of the next — 200 requests in a fraction of a second, twice the intended rate. The token bucket's r·T + B bound forbids exactly this. Sliding-window logs fix the boundary burst by storing every request timestamp (exact, but O(requests) memory); sliding-window counters approximate it with a weighted blend of the current and previous window (cheap, slightly inexact). The token bucket gets sliding-window smoothness with the O(1) footprint of a counter — which is why it usually wins.

Where it lives in real systems

Token buckets are everywhere once you recognize the shape:

• API gateways. AWS API Gateway throttles with an explicit token bucket: a steady rate plus a burst bucket, defaulting to 10,000 requests/second steady with a 5,000-request burst per account per region; overflow gets 429. Stripe's published engineering work uses token-bucket request limiters backed by Redis, alongside concurrency limiters and load shedders.
• Cloud credits. AWS burstable EC2 instances (T2/T3/T4g) are a token bucket in a costume: CPU credits accrue at a fixed baseline rate and are spent to burst above baseline — one credit buys roughly one vCPU-minute at full tilt. EBS gp2 volumes and burstable network bandwidth work the same way.
• Kernels and proxies. The Linux traffic-control stack ships the Token Bucket Filter (TBF) qdisc and the Hierarchical Token Bucket (HTB) for shaping; nginx's limit_req, by contrast, is a leaky bucket with an optional burst queue.
• Libraries. Go's golang.org/x/time/rate Limiter (used throughout Kubernetes client-go) and Google Guava's RateLimiter are token buckets — the latter offering a SmoothWarmingUp mode that ramps the rate after idle to protect cold caches.
• Network QoS. The DiffServ markers srTCM (RFC 2697) and trTCM (RFC 2698) run token-bucket meters at one or two rates (a single CIR/CBS, or adding a second PIR/PBS) to paint packets green, yellow, or red for differentiated drop treatment.

Going distributed, and how it breaks

Running one logical bucket across a server fleet is where the algorithm gets hard. A single global limit forces shared state: the common design keeps the bucket in Redis and does the check-and-decrement in an atomic Lua script (the redis-cell module implements GCRA directly via its CL.THROTTLE command). That is correct but adds a network round-trip and a hot-key bottleneck on every request. The cheaper alternative gives each of N nodes a local bucket refilling at r/N, which needs no coordination but wastes headroom when load is skewed; hybrids periodically rebalance tokens between nodes to recover the slack.

The failure modes are worth naming. Over-large B defeats the purpose: a burst size bigger than the backend can absorb lets a client save up and stampede it, so B should be tuned to real downstream capacity, not convenience. Skipping atomic updates over-admits under concurrency. Wall-clock time instead of a monotonic clock lets an NTP step forge or vaporize tokens. Per-key memory grows with the number of distinct clients, so idle buckets need TTL eviction or they become a slow leak. And a subtle one: if refill is credited only at coarse intervals, many waiting clients can be released at the same instant and cause a thundering herd — jittering the refill timing spreads the load out. Done right, though, the token bucket is the rare mechanism that is at once two-numbers-simple, O(1) fast, and backed by a hard mathematical bound — which is why it has outlived nearly every framework that has implemented it.

Rate-limiting algorithms compared: bursts, state, and the key weakness

Algorithm	Allows bursts?	State per key	Key weakness
Token bucket	Yes — up to B saved tokens	O(1): token count + timestamp	Must tune B; needs atomic check-and-decrement
Leaky bucket (queue / shaper)	No — constant output rate r	O(queue depth)	Adds latency; cannot exploit idle capacity
Fixed-window counter	Yes, but uncontrolled at edges	O(1): one counter per window	Boundary burst: up to 2·L across the window edge
Sliding-window log	Exact, no edge burst	O(requests in window)	Memory grows with traffic volume
Sliding-window counter	Approximate smoothing	O(1): two counters	Approximation error near the boundary
GCRA / leaky-bucket meter	Yes, via tolerance τ	O(1): one timestamp (TAT)	Dual of token bucket; less intuitive to tune