Token Bucket Rate Limiter

Implement a per-key token bucket limiter. Each caller owns a refillable balance, so one caller's burst must never spend another caller's capacity.

Requirements

• Define Decision(allowed, retry_after, reason).
• Define TokenBucketLimiter(capacity, refill_rate_per_second, now).
• allow(key, cost=1) returns a Decision.
• Each key has an independent bucket that starts at full capacity.
• Tokens refill continuously based on elapsed time and never exceed capacity.
• A blocked request doesn't consume tokens.
• If now() moves backward, treat elapsed time as zero and keep the previous refill timestamp. Returning to that timestamp later must not create refill credit.
• If a request is blocked, retry_after is the seconds until enough tokens are available.
• When a request is allowed: reason == "allowed" and retry_after == 0.
• When a request is blocked: reason == "rate_limited" and retry_after == (cost - tokens) / refill_rate_per_second (using the bucket's current tokens after refill).
• Assume cost <= capacity and refill_rate_per_second > 0 (callers must not pass larger costs or a zero rate; those inputs are out of scope).

Example

The following clock trace starts with capacity 2 and a refill rate of 1 token per second:

The blocked middle request leaves its half-token intact. The runnable assertions below cover the full-bucket and empty-bucket boundaries:

Constraints

• Use deterministic injected time.
• Use standard-library Python only.
• Preserve the last valid refill timestamp when the injected clock moves backward.