perf: count RetryBudget and the rate-mode window in time buckets - #181

What changed

RetryBudget used to keep one timestamp per deposit and per withdrawal in two deques, and trimmed them on every call. It now keeps counters in ten buckets of ttl / 10, plus running totals. A call moves the current bucket forward if time has moved on, then bumps one bucket and one total. The lock is held for a fixed amount of work no matter how much traffic the budget has seen.

The circuit breaker's rate-mode window (_RollingWindow) was already split into ten buckets, but it summed all ten on every recorded outcome. It now keeps running totals too, so recording an outcome and reading the rate are both constant-time. Its window semantics are unchanged, and nothing outside the class was touched.

The constructor parameters, their defaults, the 0.22.0 validation and the injectable clock are all unchanged.

Why

At 50k requests per second with the default 10 s ttl, the budget held about 500k timestamps (17 MB). After a quiet spell longer than ttl, the next call had to drop all of them while holding the lock, and every thread and event loop sharing the budget waited for it. Bucketed counters need about 1.3 KB at any traffic level, and the worst call does at most ten bucket resets.

Measurements

Simulated 50k rps over a 10 s window with the injectable clock, CPython 3.14.7 on an Apple Silicon laptop. Per-operation numbers are best-of-7 timeit with the clock-advance cost subtracted. The machine was busy with other work, so the ranges come from four alternating before/after runs.

The rate-mode window's memory was already constant and stays so. The slowest single steady-state call was in the millisecond range both before and after, which is scheduler preemption on a loaded machine, so those numbers are left out of the table.

Behaviour change for 0.22.0

RetryBudget now counts in steps of ttl / 10. A deposit or withdrawal stops counting between 0.9 * ttl and ttl after it was made, instead of exactly ttl after. With the default ttl=10.0, a request can drop out of the budget up to one second early. Nothing is ever counted for longer than ttl.

The rate-mode circuit breaker already moved its window in steps of window_seconds / 10, so its behaviour does not change. Both are now stated in docs/resilience.md.

Tests

• New unit tests pin the bucket edge for the budget: a deposit at 0.5 s with ttl=10 stops counting at 10.0 s, withdrawals expire with their bucket, and an expired bucket releases only its own counts. Two of them fail on main on purpose, because they describe the new edge.
• A new Hypothesis property drives random deposits, withdrawals and clock steps against a reference that keeps every timestamp. Each try_withdraw() answer must be one the reference allows when events expire anywhere between 0.9 * ttl and ttl. A similar property checks _RollingWindow.totals against a timestamp reference. Both fail when the bucket width or the eviction is broken.
• A new stress test rotates buckets under 16 threads with a 10 ms ttl and checks that the running totals still equal the bucket sums. It fails within one run on free-threaded 3.14t if the lock is removed.
• Tests that read the old deques (len(budget._deposits), len(budget._withdrawn)) now read the counters. No existing test about expiry timing had to change: they all step the clock by more than a bucket.