Token-Bucket State Transitions

Question

Each subject has a token bucket stored in a shared key-value cache. A missing bucket begins full. Refill lazily when a request arrives: add `elapsed_time * refill_rate`, capped at capacity. If time has not advanced, add nothing.

```python
def refill_token_bucket(bucket: TokenBucket, current_time: float) -> TokenBucket: ...

def allow_request(
    cache,
    user_id: str,
    tokens_requested: int = 1,
    capacity: int = 100,
    refill_rate: float = 10.0,
    current_time: float | None = None,
) -> bool: ...
```

Accept only when the refilled balance covers the full request, then subtract it. A rejected request spends nothing. Persist the refilled state in either case. A backward-moving clock must not create tokens.

`TokenBucket` and the in-memory `DistributedCache` test double are provided. This base task is sequential; the cache name does not imply atomic distributed behavior. Refill returns a new bucket without editing its argument. Existing buckets retain their stored capacity/refill rate; call configuration initializes missing buckets only. Explicit fixture times are finite numbers, capacity and requested tokens are positive integers, and refill rate is non-negative. Default `current_time=None` uses wall-clock time. The supplied `run_case` exercises your two functions and returns observed state; do not implement the driver or cache. Invalid arguments are outside the base assessed contract.

## Design discussion (not graded)

1. Support per-subject capacity and refill configuration.
2. Make refill, check, spend, and expiry atomic across service instances.
3. Compare a cache-side script, distributed lock, and optimistic version retry.
4. Contrast token buckets with leaky buckets and exact sliding windows.