Token Bucket

The industry's default. Each client owns a bucket holding at most capacity tokens. Tokens drip in at refill_rate per second; each request spends one. Idle clients accumulate tokens (up to the cap) and may spend them all at once; busy clients are held to the refill rate on average. That's the whole idea — and it gives you two independent knobs: capacity sets how big a burst you tolerate, refill_rate sets the sustained rate. No other algorithm in this course separates those two concerns so cleanly.

The lazy-refill idiom. No background thread tops buckets up. Each request computes how many tokens would have dripped in since the last visit (elapsed * refill_rate) and adds them, capped by min(capacity, ...). Idle clients cost nothing; math replaces timers. This one trick is why token buckets are O(1) time and O(1) memory per client.

Tokens are floats. With refill_rate=0.5, one elapsed second yields half a token — keep the fraction.

Trace it: capacity=3, refill_rate=0.5, bucket starts full, requests at t = 0, 0, 0, 0, 1, 2, 3, 4:

• t=0 × 3 → ALLOW, ALLOW, ALLOW — the burst spends the full bucket (3 → 2 → 1 → 0)
• t=0 again → DENY (0 tokens)
• t=1 → 0 + 0.5 = 0.5 → DENY (the half-token stays)
• t=2 → 0.5 + 0.5 = 1.0 → ALLOW (back to 0)
• t=3 → 0.5 → DENY
• t=4 → 1.0 → ALLOW

Exactly the promise: an instant burst of capacity, then a steady 0.5 requests/second.

Who runs this: AWS API Gateway's throttling is documented as a token bucket (a rate plus a burst); Stripe's engineering blog describes their request rate limiter as a token bucket implemented in Redis; Envoy's local rate limiting is configured literally as max_tokens / tokens_per_fill / fill_interval. Whenever an API's docs mention both a "rate" and a "burst," you are looking at a token bucket.

Three traps:

1. Dropping the min(). Without the cap, a client idle over a weekend banks 0.5 × 172,800 = 86,400 tokens and legally floods you on Monday morning. The cap is the algorithm.
2. Integer tokens. Store tokens as an int and a client polling once per second at refill_rate=0.5 gains int(0.5) = 0 tokens per visit — the bucket never refills and the client is locked out forever. This bug reliably survives tests that only use whole-number rates.
3. Uniform cost. Real APIs charge expensive operations more: if tokens >= cost: tokens -= cost. A heavy search might cost 5 tokens, a status check 1. Same bucket, better fairness — the Tiered Limits lesson builds on this.

Your exercise

Implement TokenBucket and reproduce the trace above exactly — eight verdicts:

ALLOW ALLOW ALLOW DENY DENY ALLOW DENY ALLOW

The giveaway failures: DENY on the third t=0 request means your bucket didn't start full; ALLOW at t=1 means you rounded the half-token up (or refill one whole token per visit regardless of rate); DENY at t=2 means you threw the fraction away when the t=1 request failed — the code above keeps it, and that's precisely why t=2 succeeds.