A token bucket lets traffic burst up to a limit while still capping the long-run average rate -- much friendlier than a hard "N requests per second" wall, which would reject a legitimate burst even when the service has been idle for a while. This is what Envoy's rate limit filter does at the edge of every request.

The bucket starts full (capacity tokens). Every call to allow():

1. Refills first, based on elapsed time since the last call: elapsed * refill_rate tokens are added, capped at capacity.
2. Then checks whether cost tokens (default 1) are available. If so, consume them and return True. If not, consume nothing and return False.

now is always passed in by the caller -- never read from a real clock -- so behavior is exactly reproducible.

Implement TokenBucket.allow(now, cost=1).

Example

bucket = TokenBucket(capacity=3, refill_rate=1)  # 1 token/second
bucket.allow(now=0)   # True  (3 -> 2)
bucket.allow(now=0)   # True  (2 -> 1)
bucket.allow(now=0)   # True  (1 -> 0)
bucket.allow(now=0)   # False (still 0, no time passed)
bucket.allow(now=1.0) # True  (1 second passed -> 1 token refilled -> 0)

Constraints

• Refilling must never push tokens above capacity, no matter how much time elapsed.
• A rejected request (False) must not consume any tokens.

Real-world grounding

• Envoy's local rate limit filter: source/extensions/filters/http/local_ratelimit/

Real rate limiters often need to coordinate across many machines (a distributed counter, not a single in-process bucket) -- but the core token bucket math is exactly what you're implementing here.