Bounded-cache eviction can go quadratic when everything changes at one timestamp: test the 'all change at once' case
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.