Token Bucket: Refill Math, Burst Allowance, and GCRA
Concept
Token bucket is the algorithm most production API rate limiters actually implement, because it's the only one of the classic four that natively expresses "allow a burst, then settle to a steady average" — the shape real client traffic takes. A bucket holds up to capacity tokens; tokens refill at rate tokens/second; each request consumes one token (or more, for weighted-cost requests); a request is allowed if a token is available and rejected otherwise. See Rate Limiting Algorithms for how it compares conceptually to the other three; this note goes one level deeper — into how the refill is actually computed, and why most real implementations don't run a timer at all.
Continuous vs. discrete refill: a naive implementation ticks a timer every second and adds rate tokens to the bucket, capped at capacity. This works but wastes a background job per bucket — untenable at the scale of one bucket per API key across millions of keys. The implementation nearly everyone actually ships instead is lazy/continuous refill: store only tokens_remaining and last_refill_timestamp; on each request, compute tokens_to_add = (now - last_refill_timestamp) * rate, add it (capped at capacity), update the timestamp, then evaluate the request against the updated count. No background process, no timer — the bucket "catches up" exactly at request time, and an idle bucket costs nothing between requests.
GCRA — the same idea without floating-point drift: the Generic Cell Rate Algorithm (from ATM networking, reused for rate limiting) reframes the bucket as a single value: the theoretical arrival time (TAT) at which the next request would be allowed with an empty bucket. Each request compares now against TAT; if now is late enough (accounting for burst capacity), it's allowed and TAT advances by the fixed inter-request interval. GCRA needs only one stored value instead of two (no separate token count and timestamp), and — because it works in fixed time increments rather than accumulating fractional token counts — it avoids the floating-point rounding drift that a naive continuous-refill implementation can accumulate over millions of requests. This is the algorithm behind the throttled and redis-cell Redis rate-limiting modules.
Tradeoffs
| Implementation | Storage per key | Precision | Operational cost |
|---|---|---|---|
| Timer-driven refill (background job per bucket) | Token count + running timer/goroutine | Exact | Doesn't scale — one live timer per key is untenable past a few thousand keys |
| Lazy continuous refill (compute on request) | Token count (float) + last-refill timestamp | Exact, but float accumulation can drift over very long uptimes | O(1) per request, no background work |
| GCRA (theoretical arrival time) | One timestamp (TAT) |
Exact, integer/fixed-point safe | O(1) per request, no background work, no float drift |
| Fixed-size token array partitioned per second (rare) | O(bucket capacity) | Exact | Higher memory than the above for no accuracy gain |
Lazy refill and GCRA both land at the same O(1)-per-request cost; GCRA is the more common choice in mature rate-limiting libraries specifically because avoiding a separate token-count field removes a whole class of float-precision bugs, not because it changes the algorithm's actual burst-then-refill behavior.
When to use / when not to
- Default choice for public/partner-facing API rate limits — it's what Stripe, most API gateways (Kong, Envoy, AWS API Gateway), and most CDN edge rate limiters implement as their primary algorithm, because bursty-then-idle is how real API clients behave.
- Use a weighted-cost variant (a request can consume more than one token) when different endpoints have meaningfully different backend cost — a bulk-export call shouldn't cost the same single token as a cheap read, and token bucket's per-request consumption model expresses this cleanly without a second limiter.
- Stripe's real production setup is instructive: it runs four token-bucket limiters in series per request (e.g. a per-second request-rate limiter and a separate concurrent-in-flight-requests limiter), because a single limiter can't simultaneously bound both "how fast" and "how many at once" — a pattern worth copying rather than trying to encode both constraints into one bucket.
- Avoid it when the actual goal is traffic shaping (smoothing bursty producer output into a steady, capacity-bounded downstream rate) rather than client fairness — that's leaky bucket's job (see Leaky Bucket), since token bucket deliberately allows bursts through rather than smoothing them out.
- In a horizontally-scaled service, the bucket state must live in a shared store (Redis, with the refill computed atomically via Lua script or
redis-cell) — a per-instance in-memory bucket multiplies the effective limit by the instance count, the same failure mode as every other rate-limiting algorithm run without shared state.
Common pitfall
Implementing the refill as a separate background job or a naive periodic tick instead of lazy/on-request computation. Beyond the scaling problem (one live timer per key doesn't survive past a few thousand keys), it also introduces a subtler bug: a bucket that hasn't been touched in a while either needs its own persistent timer (wasteful) or silently stops refilling once the process managing it restarts, producing buckets that are wrongly still full or wrongly still empty relative to real elapsed time. Lazy refill sidesteps this entirely because the refill amount is always derived from now - last_refill_timestamp, so a bucket picks up exactly where it should regardless of any gap in activity or a process restart, as long as the timestamp itself is durably stored.
Engineering Lens
Token bucket's real design lesson isn't the bucket-and-tokens metaphor — it's that "rate limiting" is actually two related but distinct questions (how fast, and how many concurrently), and conflating them into a single limiter is a common under-design. Stripe running four limiters in series is the concrete evidence that a mature rate-limiting layer decomposes the constraint rather than trying to encode every failure mode into one algorithm. The GCRA vs. naive-float-refill choice is a smaller but transferable instance of a broader pattern: when a stateful counter needs to survive at scale and under concurrency, reframing the state (a single timestamp instead of a count-plus-timestamp pair) to eliminate a class of drift/precision bugs is usually worth the extra conceptual indirection. This same reasoning applies identically to a trading system's per-client order-submission throttle or a payments gateway's per-merchant API cap — same bucket, different label on the door.
Sources
- Scaling your API with rate limiters — Stripe
- Rate Limiting Algorithms: Token Bucket vs Sliding Window vs Fixed Window — Arcjet