Token-Bucket Rate Limiter

Background

The token bucket algorithm caps request rate while allowing short bursts. The bucket holds at most capacity tokens; tokens refill at refill_rate/s; each request consumes one. When empty, requests are denied.

Problem statement

Implement TokenBucket(capacity, refill_rate) with allow(now) -> bool. Each call:

1. Refills tokens proportional to elapsed time since the previous allow, capped at capacity.
2. If tokens >= 1, decrement and return True.
3. Else return False (no tokens consumed).

Input

• capacity — int >= 1, the bucket size (maximum burst).
• refill_rate — float > 0, tokens added per second.
• allow(now) — now is a monotonically-increasing timestamp in seconds.

Output

allow returns bool — whether the request is admitted.

Examples

Example 1 — initial burst up to capacity

TokenBucket(5, refill_rate=1.0)
allow(0) x 5  → all True
allow(0) once more → False

Example 2 — refill restores capacity over time

After draining at t=0, wait 1s, refill_rate=1.0 → 1 token back.
allow(1) → True

Example 3 — refill is capped at capacity

Idle from t=0 until t=1000; the bucket should not grow past 5 tokens.

Constraints

• Constructor starts the bucket full.
• Refill is min'd against capacity — no infinite accumulation.
• now must be ≥ the previous now (caller's responsibility; we don't validate).

Notes

• vs leaky bucket. Token bucket allows bursts up to capacity; leaky bucket smoothes to a constant rate. Token bucket is the right model for APIs that allow occasional burstiness.
• Distributed limiters. Multi-node services use Redis-backed counters or sticky shard hashing — the in-process variant here is the building block.