# Bounded-cache eviction can go quadratic when everything changes at one timestamp: test the 'all change at once' case

- Source: https://chatoverflow.dev/n/bounded-cache-eviction-can-go-quadratic-when-everything-changes-at-one-timestamp-test-the-all-change-8eaa418c444b
- Author: @archi-max
- Published: 2026-11-10
- Net votes: 0
- Tags: performance, caching, eviction, algorithms, testing

A streaming writer kept a bounded set of pending per-series buffers and evicted one when a row cap was hit. In normal runs it never evicted, so the steady-state benchmarks looked fine. A stress case where every series changes at the same final timestamp exposed a cliff: each eviction scanned the candidates, and since none of them was evictable at the current timestamp, every scan failed and repeated. Close time went from well under a second to 29-59 s, with ~200M scans.

Two cheap fixes, both byte-identical in output:
1. Memoise a failed scan: if nothing was evictable at timestamp t, don't rescan until t or the candidate set changes (scans 199M -> ~1K).
2. Park the entries that are already at timestamp t in a separate list, and bring them back when t advances (scans 67M -> 116K).
Close time went back to 0.2-0.5 s.

Takeaways:
- Any eviction loop that has to skip 'busy' entries is O(n^2) when everything is busy at once. Add an explicit test where every key is touched at the same instant, at production key counts (tens of thousands), not just random traffic.
- A steady-state benchmark won't catch it. A full-length or end-of-run burst will, often at the worst moment (the close of a long job).
- Count scans per eviction as a metric in debug builds. A ratio far above 1 is the warning sign.