For decades, cache eviction has been a contest of cleverness. LRU tracks recency, LFU tracks frequency, and a long line of adaptive policies tries to balance the two with auxiliary data structures, tunable parameters, and locks on the hot path. The conventional wisdom held that better hit ratios required more bookkeeping.

Working across hundreds of production cache clusters, we kept noticing the opposite. Most objects in a caches are requested once and never again.1 The expensive machinery built to rank "warm" objects spends most of its energy managing items that will never be reused.

One queue, one second chance#

The core idea behind S3-FIFO2 and SIEVE3 is almost embarrassingly small: keep a plain FIFO queue, and give an object exactly one chance to prove it is worth keeping. New objects enter at the head. When the cache is full, we scan from the tail; an object that was requested since it was inserted survives and moves on, while an object that was never reused is evicted immediately.

This quickly filters out the flood of one-hit objects without ever promoting them, so the limited cache space is spent on the items that actually repeat.

A FIFO queue where objects enter at the head and an eviction scan runs from the tail, keeping objects that were requested again and dropping objects that were never reused
One FIFO queue with one second chance: reused objects survive the scan and have their marker reset; objects never requested again are evicted from the tail

Simplicity is not a constraint we accepted reluctantly. On real workloads it turned out to be the source of the performance.

Why it matters in production#

A FIFO-based design is not just competitive on hit ratio — it wins on it. Across 6,594 traces from 14 datasets, S3-FIFO had a lower miss ratio than each of twelve state-of-the-art algorithms refined over the past decades, cutting LRU's miss ratio by as much as 72% on some traces — or, framed the other way, reaching LRU's hit ratio on roughly 46% less memory. SIEVE, the even simpler single-queue variant, reduces the miss ratio of ARC — long a gold-standard adaptive policy — by up to 63.2% on skewed web workloads.

The simplicity pays off a second time in the engineering. Because a FIFO queue avoids per-request promotions and the locking they require, S3-FIFO sustains about 6× the throughput of an optimized LRU at 16 threads, and it is far friendlier to flash, where every rewrite costs endurance. And because there is so little to it, SIEVE dropped into five production cache libraries with fewer than 20 lines of change each.

That combination — better hit ratios with a fraction of the complexity — is why these algorithms have been adopted in production at companies like VMware, Google, and Redpanda, and in open-source projects far beyond where they started.

The lesson I keep returning to: before adding a parameter, ask what the data is actually asking for.

Footnotes

  1. This one-hit-wonder effect is quantified across the production traces in the S3-FIFO study: on many web and key-value workloads the majority of objects are requested exactly once during their time in the cache, so any effort spent ranking them is wasted. ↩

  2. Juncheng Yang, Yazhuo Zhang, Ziyue Qiu, Yao Yue, and K. V. Rashmi. "FIFO queues are all you need for cache eviction." In Proceedings of the 29th ACM Symposium on Operating Systems Principles (SOSP '23), 2023. Project page: https://s3fifo.com. ↩

  3. Yazhuo Zhang, Juncheng Yang, Yao Yue, Ymir Vigfusson, and K. V. Rashmi. "SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches." In Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24), 2024. Project page: https://sievecache.com. ↩