Cache eviction can be simple.

A small queue absorbs new objects, a ghost queue remembers the ones that washed out, and a main queue holds what proved itself. No object is ever moved on a hit, which is what makes it scale — and being FIFO-only means writes stay sequential, so it suits flash too.

• Up to 72% lower miss ratio than LRU — as published on s3fifo.com
• 46% smaller cache and 6× the throughput of LRU — at a 10% target miss ratio, 16 threads
• Evaluated on 6,594 traces across 14 datasets — lower miss ratio than state-of-the-art algorithms across them

Juncheng Yang, Yazhuo Zhang, Ziyue Qiu, Yao Yue, K. V. Rashmi.

Genuinely simpler than LRU: one queue, one pointer, one bit per object. A hit just sets the bit — nothing moves. A “hand” walks from the tail towards the head looking for the first object whose bit is clear, and evicts it. That is the whole algorithm, which is why it drops into an existing LRU implementation without changing its data structures, and why it works as a building block for more advanced ones.

• Lower miss ratio than 9 state-of-the-art algorithms on >45% of 1,559 traces — the next best manages 15%
• >2× the throughput of an optimized LRU at 16 threads — and 16% faster single-threaded
• 12–21 lines to add to a production cache library — each port took about an hour

Yazhuo Zhang, Juncheng Yang, Yao Yue, Ymir Vigfusson, K. V. Rashmi. Read the ports for yourself — SIEVE dropped into groupcache (Go, 21 lines), mnemonist (JavaScript, 12), lru-rs (Rust, 16) and lru-dict (Python + C, 21).

Everyone relaxes LRU to escape lock contention, but nobody had said which relaxation to pick. We benchmark five of them — Probabilistic-LRU, Batch-LRU, Delay-LRU, FIFO-reinsertion and Random-LRU — on production traces, and introduce promotion efficiency: hits earned per promotion performed.

• Delay-LRU and FIFO-reinsertion substantially improve promotion efficiency
• Batch-LRU and Probabilistic-LRU cannot cut promotions without paying in miss ratio
• Two new designs follow from that — Delayed FIFO-reinsertion and Age-Guided Eviction — with 20–60% fewer promotions — at a similar or lower miss ratio

Qinghan Chen, Muhammad Haekal Muhyidin Al-Araby, Ziyue Qiu, Zhuofan Chen, Rashmi Vinayak, Juncheng Yang.

Metadata caches have a problem the algorithms above do not solve: a single logical operation can touch the same block several times in a row, and every policy that counts references mistakes that burst for a hot block. Clock2Q+ keeps three queues and a reference bit, and adds one idea — a correlation window at the head of the small queue, inside which a reference does not set the bit. Blocks have to earn their promotion after the correlated burst has passed, and unlike 2Q or CART, identifying them costs no extra misses.

• Up to 28.5% lower miss ratio than S3-FIFO on metadata traces — S3-FIFO being the next best
• Also lower on ordinary data workloads — which do not show the correlated pattern it targets
• Shipping in VMware vSAN and VDFS — two flagship storage products at VMware by Broadcom

Yiyan Zhai, Bintang Dwi Marthen, Sarath Balivada, Vamsi Sudhakar Bojji, Eric Knauft, Jitender Rohilla, Jiaqi Zuo, Quanxing Liu, Maxime Austruy, Wenguang Wang, Juncheng Yang.

Learned caches usually put a model on the data path and pay for it on every request. S4-FIFO splits the two apart: a plain FIFO heuristic makes every admission and eviction decision, while an offline-trained gradient-boosted model periodically picks the best configuration from cache-level workload features. Because the model never sees an individual object, throughput stays at heuristic parity and the policy stays legible — it is five operational parameters, not a black box.

• +26% mean efficiency over S3-FIFO and +8% over 3L-Cache — as reported in the artifact’s reproduction guide
• Worst case costs 0.8% miss ratio against plain FIFO — where 3L-Cache costs 8.8%

Haocheng Xia, William Nixon, Bintang Dwi Marthen, Pranav Bhandari, Juncheng Yang.

A cache simulator, a trace analyzer and a library for building your own simulators. It replays traces at over 20 million requests per second with a small, predictable memory footprint, parallelizes across cores out of the box, and ships more than twenty eviction algorithms — FIFO, LRU, ARC, 2Q, LFU, LHD, LRB, TinyLFU, GL-Cache, Belady’s optimal, S3-FIFO and SIEVE among them — plus admission and prefetching policies.

• 20M+ requests/sec on a realistic trace replay
• The only feature-rich cache trace analyzer we know of
• Add a new algorithm or trace format by implementing one interface

The same engine, driven from Python, for when an experiment should take an afternoon rather than a build cycle. It streams traces straight out of our S3 bucket, exposes individual requests and cache internals, and lets you prototype a brand-new eviction policy in pure Python with no compilation step.