Token bucket

Deep dive

How it works

In: key, cost c, now · Out: allow or deny, and the wait (c − tokens)/r · State: tokens (≤ b) and last per key, about 16 bytes · Cost: O(1) per check; order of 10-30 ns in process.

1. State: tokens (≤ b) and last (time of last update).
2. On a request at now costing c: tokens = min(b, tokens + (now − last)·r), last = now.
3. If tokens ≥ c: tokens −= c, allow. Else deny and report wait time (c − tokens)/r.
4. New keys start full (b tokens) or empty, depending on whether a cold start may burst.
5. Policing drops/rejects excess; shaping delays it until tokens arrive.

rate r ─► ░░░ tokens (≤ b) ░░░ ─► request takes c tokens
           ▲ refilled lazily: + (now − last) · r

Code

use std::time::{Duration, Instant};

/// Fixed-point token bucket: tokens are stored in nano-tokens to avoid float drift.
pub struct TokenBucket {
    rate_per_s: u64,   // tokens per second
    burst: u64,        // capacity in tokens
    nano_tokens: u128, // tokens * 1e9
    last: Instant,
}

const NANO: u128 = 1_000_000_000;

impl TokenBucket {
    pub fn new(rate_per_s: u64, burst: u64, now: Instant) -> Self {
        assert!(rate_per_s > 0 && burst > 0);
        TokenBucket { rate_per_s, burst, nano_tokens: burst as u128 * NANO, last: now } // start full
    }

    fn refill(&mut self, now: Instant) {
        let elapsed = now.saturating_duration_since(self.last).as_nanos(); // monotonic, never negative
        // r tokens/s * elapsed ns = r * elapsed nano-tokens
        let cap = self.burst as u128 * NANO;
        self.nano_tokens = (self.nano_tokens + elapsed * self.rate_per_s as u128).min(cap);
        self.last = self.last.max(now);
    }

    /// Ok(()) if allowed, Err(wait) with the time until `cost` tokens will be available.
    pub fn try_acquire(&mut self, cost: u64, now: Instant) -> Result<(), Duration> {
        self.refill(now);
        let need = cost as u128 * NANO;
        if need > self.burst as u128 * NANO { return Err(Duration::MAX); } // can never succeed
        if self.nano_tokens >= need {
            self.nano_tokens -= need;
            Ok(())
        } else {
            let missing = need - self.nano_tokens;
            let wait_ns = missing.div_ceil(self.rate_per_s as u128); // nano-tokens / (tokens/s) = ns
            Err(Duration::from_nanos(wait_ns as u64))
        }
    }

    pub fn available(&mut self, now: Instant) -> u64 { self.refill(now); (self.nano_tokens / NANO) as u64 }
}

fn main() {
    let t0 = Instant::now();
    let mut b = TokenBucket::new(100, 10, t0);            // 100/s, burst 10
    let ok = (0..15).filter(|_| b.try_acquire(1, t0).is_ok()).count();
    assert_eq!(ok, 10);                                    // burst drained
    let wait = b.try_acquire(1, t0).unwrap_err();
    assert_eq!(wait, Duration::from_millis(10));           // one token per 10 ms
    assert!(b.try_acquire(1, t0 + wait).is_ok());
}

Shared limit in Redis. A limit shared by many API servers usually lives in Redis as a hash {tokens, ts} per key, updated by one server-side script so read-refill-write is atomic: HMGET both fields (missing = full bucket at now), refill min(b, tokens + (now − ts)·r), subtract the cost if enough tokens remain, HSET both fields, and PEXPIRE the key after b/r seconds plus a margin, since a full bucket carries no information. GCRA does the same with one string key and one SET.

Complexity and constants

• In-process: order of 10-30 ns per check (a clock read via vDSO is ~20 ns; reuse one now per batch).
• Redis-backed: one round trip, order of 0.1-1 ms; a single Redis core handles order of 10⁵ script calls/s.
• Memory: ~16-32 bytes per key in process; ~100 bytes per key as a Redis hash.
• Burst behaviour: after idling ≥ b/r seconds a client can send b requests instantly; size b to what downstream can absorb.

Efficiency

• Cost: In process a check costs order of 10-30 ns, of which a vDSO clock read is about 20 ns. Redis-backed it is one round trip of order of 0.1-1 ms, and one Redis core handles order of 10⁵ script calls/s. Memory is about 16-32 B per key in process, about 100 B as a Redis hash. The bound is the clock read and a cache miss locally, the round trip and one Redis core when shared.
• Levers:
  • Lazy refill from elapsed time — no timer per key — always.
  • One now per batch of checks — amortises the clock read — bulk checks.
  • Fixed-point tokens — exact, no float drift — long-running limiters.
  • GCRA form — 16 → 8 B per key, one CAS — many keys.
  • One server-side script per check — 1 round trip instead of 3 — limits shared across servers.
• Naive → standard → state of the art:
  • A refill thread adds tokens every tick, one mutex per key · a timer per key, quantised refill.
  • Lazy-refill bucket in a sharded map · 16-32 B per key, order of 10-30 ns.
  • GCRA with an AtomicU64 per key (governor) · 8 B per key, lock-free.

Implementation notes

• Use a monotonic clock in process; in Redis, pass the time from the caller (or use redis.call('TIME')) consistently.
• Charge by cost: bytes for bandwidth, tokens/units for LLM APIs, weight for expensive endpoints.
• Return Retry-After / X-RateLimit-Remaining from the computed wait so clients back off precisely.
• For many keys, shard the map and use a mutex per shard, or switch to GCRA with one AtomicU64 per key.
• Hierarchical limits (per user, per org, global): check all buckets and only spend if all allow, or accept small overspend.
• Distributed without a central store: give each of N servers r/N with periodic rebalancing; inaccurate under skewed load balancing.

Pitfalls

• Timer-based refill (a thread adding tokens every tick): millions of timers and quantization; lazy refill is exact and free.
• Floating-point tokens accumulating rounding error over long runs; use fixed-point.
• Starting buckets full lets every restarted client burst at once (thundering herd after deploys).
• Only rate-limiting at the edge: internal retries (backoff) can still amplify load past the limit.
• Unbounded per-key maps (one entry per IP forever): evict keys whose bucket is full, since they carry no information.

Variants and alternatives

In production

Linux tc TBF qdisc, AWS API Gateway throttling, Amazon EBS gp2 burst credits (5.4M I/O credits, bursts to 3,000 IOPS), EC2 T-instance CPU credits, Envoy local rate limit filter (token_bucket), Guava RateLimiter (stored permits).

Implementations

Sources

• Andrew S. Tanenbaum, David J. Wetherall, Computer Networks, 5th ed., 2011 (traffic shaping: leaky and token bucket).
• J. Heinanen, R. Guerin, A Two Rate Three Color Marker, RFC 2698, 1999. RFC
• Betsy Beyer et al. (eds.), Site Reliability Engineering, O'Reilly 2016, ch. 21 Handling Overload. book