MediumRate LimitingPython 3
Token Budget Ledger
Maintain rolling-window token spend per caller with expiry on every read and write path.
35m3 sample tests5 hidden tests
Track a rolling token budget per key with deterministic expiry. Unlike a continuously refilling bucket, each accepted spend returns to the budget only when that exact event ages out of its window.
Requirements
- Define
TokenBudget(limit, window_seconds, now). spend(key, tokens)records spend if it fits the current rolling window.- Return
Truewhen spend is accepted, otherwiseFalse. - A rejected spend must not add an event or change the remaining budget.
remaining(key)returns remaining tokens in the current window.- Events expire when
now() - event_time >= window_seconds. - Expired spend must not count on reads or writes.
- Different keys are independent.
- Zero-token spend is allowed when it fits (
tokens == 0); only negative spends are rejected for sign. remainingon a never-seen key is the fulllimit.
Example
For a 10-token limit and a 60-second window, the expiry boundary is exact:
| Time | Operation | Accepted? | Remaining budget |
|---|---|---|---|
0 | spend 7 | yes | 3 |
20 | spend 4 | no | 3 |
59 | read remaining | not applicable | 3 |
60 | read remaining | not applicable | 10 |
The rejected four-token request creates no hidden event. These assertions exercise that invariant directly:
python
1clock = {"t": 0}
2budget = TokenBudget(10, 60, now=lambda: clock["t"])
3assert budget.spend("org", 7)
4assert budget.remaining("org") == 3
5assert not budget.spend("org", 4)
6assert budget.remaining("org") == 3Constraints
- Use injected time.
- Don't allow negative spends.
- Don't share spend across keys.
- Purge expired events before both
spendandremaining.
Editor