FIFO Cache Eviction Replacing LRU

The axis of cache eviction research moved from what to remove toward how to keep many threads from blocking each other while removing it.

Where LRU stalls on multicore

LRU (Least Recently Used) evicts the item referenced longest ago, and it moves an object to the head of a linked list on every access. Every thread shares that ordering list, so a single lookup that hits still takes a write lock on the shared structure. A cache lookup is a read while the metadata update is a write, and that mismatch is where the bottleneck starts.

This is why throughput does not scale in proportion to thread count. Every core contends for the same list head, so the lock wait time grows along with the core count. A follow-up write-up by the S3-FIFO authors reports that S3-FIFO reached roughly 6x the throughput of an optimized LRU implementation with 16 threads.

The FIFO (First In First Out) family avoids this point by deferring the update. On an access it touches only a bit attached to the object, and it postpones any queue rearrangement until eviction actually becomes necessary. The hit path never touches the shared structure, so no lock is required.

Yang, Yue, and Rashmi framed this design at HotOS 2023 along two axes: lazy promotion and quick demotion. Promote as late as possible, demote as early as possible. The two algorithms below implement the same principle with different data structures.

S3-FIFO filters objects used only once

S3-FIFO (SOSP 2023, Yang, Zhang, Qiu, Yue, Rashmi) starts from an observation on measured traces. Under skewed workloads, most objects are accessed exactly once inside a short time window. Admitting such one-hit objects into the main cache pushes out objects that would have been reused.

The remedy is to hold new objects in a small waiting room first. S3-FIFO splits the cache into three FIFO queues of fixed size.

The Small queue carries out quick demotion. One-hit objects live and die inside that 10% of cache space, so the remaining 90% fills with objects whose reuse is confirmed.

The Ghost queue holds only the keys of evicted objects, so it uses almost no memory. When a key pushed out of Small is requested again, the system checks whether it remains in Ghost and decides whether to admit it straight into Main. The structure catches reaccesses at somewhat longer intervals without ever storing the actual object twice.

Lazy promotion operates inside the Main queue. A reaccessed object is not moved to the head immediately. It is promoted by reinsertion only once it reaches the queue tail and faces eviction. The promotion operation therefore happens at eviction time rather than on every hit, which keeps the hit path light.

In an evaluation over 6,594 cache traces across 14 datasets, S3-FIFO lowered the miss ratio consistently against prior algorithms.

The means look small, but every maximum exceeds 49%. The gap widens considerably depending on the workload.

SIEVE reduces it to one queue and one hand

SIEVE (NSDI 2024, Zhang, Yang, Yue, Vigfusson, Rashmi) shares the same insight as S3-FIFO while shrinking the data structure further. Instead of several FIFO lists it uses a single FIFO list and one moving hand pointer.

insert(obj):
    visited[obj] = false
    push_head(queue, obj)        # a new object always enters at the queue head
 
on_hit(obj):
    visited[obj] = true          # set the bit only, with no repositioning
 
evict():
    while true:
        obj = hand.current()
        if visited[obj]:
            visited[obj] = false     # consume one visit chance
            hand.move_toward_head()  # move the pointer only, no rearrangement
        else:
            remove(obj)              # actually remove the unvisited object
            hand.reset_if_needed()
            return

Setting one bit is everything the hit path does. S3-FIFO still performs a reinsertion at promotion time, whereas SIEVE moves no object on a hit or on an eviction. The hand pointer travels from the tail toward the head, and for any object whose visited bit is set it clears the bit and passes by.

The insertion position is where this structure produces quick demotion. New objects always enter at the head while the pointer sweeps behind it, so a new object that is never reaccessed is removed as soon as the pointer arrives.

The evaluation ran on content delivery network (CDN) traces. SIEVE showed a 21% lower miss ratio on average against FIFO, and more than 42% lower on the top 10% of traces. With 16 threads its throughput was more than 2x that of LRU and TwoQ.

Because the structure is small, it was ported into five open source cache libraries with fewer than 20 lines changed on average. Those libraries include groupcache in Go, lru-rs in Rust, lru-dict in Python with C, and mnemonist in JavaScript, and Google, VMware, and Redpanda adopted SIEVE.

The queue itself is the remaining bottleneck

S3-FIFO and SIEVE stripped the lock out of the hit path, but the queue remains a shared data structure. When many threads insert and remove at the same time, contention reappears at the head and the tail of the queue. A throughput problem is left standing where the hit ratio problem was solved.

Mobius (SIGMETRICS 2025, Dong, Wang, Jiang, Feng) addresses that point directly. It manages cache entries in two lock-free FIFO queues so that insertions and removals execute concurrently without any lock. Lock-free means a design that updates shared state with atomic instructions rather than locks, so that other threads keep making progress even when one thread stalls.

The eviction procedure was reworked as well. A consecutive detection mechanism folds the several state changes that used to occur within one removal into a single atomic operation, which reduces data races. Fewer state changes also mean a narrower window in which threads can collide.

Across synthetic workloads and real high-concurrency cluster workloads, Mobius showed concurrent throughput gains of 1.2x to 8.5x over prior state-of-the-art techniques. Latency was lower and the hit ratio stayed at a comparable level. It was implemented and validated inside CacheLib and RocksDB, which sets it apart from a research prototype.

The three algorithms differ in optimization axis rather than competing with one another. S3-FIFO and SIEVE made the decision of what to remove more accurate, and Mobius lowered the cost of many threads making that decision at the same time.

Choosing between the two axes

Miss ratio and throughput do not move together. A miss ratio one percentage point lower reduces backend requests, but that gain can disappear if the throughput of the cache itself drops by half. Measuring which of the two is the bottleneck comes first.

Miss ratio takes priority where a single miss is expensive. If the origin is remote storage or a database, one miss costs milliseconds of latency, and the cost of the cache internal operations is negligible next to it. In that case the lower miss ratio of S3-FIFO and SIEVE converts directly into response time.

Throughput takes priority in the opposite case, where a miss is cheap and the request rate is very high. In-memory caches that resolve entirely in memory and storage engine block caches fall here, and the more cores there are, the more lock contention dominates the overall latency. The workloads Mobius validated in CacheLib and RocksDB belong to this category.

Adoption cost enters the decision as well. SIEVE landed in five open source libraries with fewer than 20 lines changed on average. A lock-free data structure, by contrast, requires handling memory reclamation and the retry path directly. If the cache library already in use supports SIEVE, that is the first option.

Workloads that break the FIFO assumption

Every algorithm covered so far rests on the same assumption: temporal locality within a short time window, with accesses concentrating on a small number of popular objects. Quick demotion, which demotes new objects fast, pays off only when that assumption holds.

The SOLAR work (2026, arXiv:2607.00394) reports a case where the assumption breaks. Its target is workloads with neither temporal locality nor frequency concentration, such as the semantic retrieval buffer of a large language model (LLM) agent. In such an environment, a carefully tuned policy can perform worse than LRU and LFU, and worse still than plain FIFO.

The alternative SOLAR proposes separates when to replace from what to keep. Replacement timing is decided by regret accumulation, and the content to keep is chosen by Bayesian online learning. The paper reports a relative improvement of 5% to 75% over FIFO at tight cache sizes.

That result does not invalidate S3-FIFO or SIEVE. Workloads with clear temporal locality, such as web caches, CDNs, and storage block caches, still make up the majority. The evaluations of all three algorithms ran on traces of that kind. For a cache whose access pattern is determined by embedding similarity, however, reproducing the experiment on your own traces before adoption is the safer course.

Summary

The recent line of work on cache eviction splits into two stages. S3-FIFO and SIEVE used lazy promotion and quick demotion to filter out objects used only once, reaching a lower miss ratio than LRU. They also cut lock contention by never touching the shared list on the hit path. Mobius made the queue itself, the next bottleneck, lock-free and reported concurrent throughput gains of 1.2x to 8.5x over the prior state of the art.

The selection criterion is the cost of a single miss. Look at miss ratio first when origin access is expensive, and at throughput first when cache internal operations dominate latency. All three algorithms presume temporal locality, so for workloads like the semantic retrieval buffer SOLAR points to, reproduce the result on your own traces first.