FIFO Cache Eviction Replacing LRU

Cache eviction research considers both which objects to remove and how to reduce contention between threads.

Where LRU stalls on multicore

LRU (Least Recently Used) removes the item referenced longest ago. On each access, it moves the object to the head of a shared linked list. Even a cache hit therefore takes a write lock on the list. The lookup reads data, but its metadata update writes to shared state and creates contention.

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. The S3-FIFO paper reports that S3-FIFO reached roughly 6x the throughput of an optimized LRU implementation with 16 threads.

FIFO (First In First Out) variants such as S3-FIFO and SIEVE defer queue rearrangement until eviction. Hits still update shared per-object metadata, using atomic counters or visited bits. Avoiding linked-list relinking removes that lock from the hit path; it does not eliminate every shared write.

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.

New objects first enter a small queue that checks for reuse. S3-FIFO splits the cache into three FIFO queues of fixed size.

The paper allocates 10% of cache space to Small and 90% to Main. Small promotes an object when its access counter exceeds 1; other evictions enter Ghost. These are the evaluated settings, and their suitability depends on the workload.

flowchart LR
    NEW[New object] --> S[Small queue<br/>10% of cache space]
    S -->|Access counter above 1| M[Main queue<br/>90% of cache space]
    S -->|Access counter at most 1| G[Ghost queue<br/>keys only]
    G -->|Requested again| M
    M -->|Reaches tail after reaccess| M
    M -->|Reaches tail without reaccess| OUT[Removed from cache]

Ghost stores keys or fingerprints rather than object payloads, but its entries and index still consume memory. A returning key found in Ghost is admitted directly to Main. This recognizes reuse after eviction without retaining a second payload copy.

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.

The paper evaluates 6,594 traces across 14 datasets. At a cache size of 10% of each trace's object footprint, the dataset-level results are as follows.

These aggregate results show broad effectiveness across the evaluated traces, without guaranteeing a win on every individual 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

A hit sets one visited bit. S3-FIFO reinserts objects during promotion, but SIEVE does not move objects on hits or evictions. The hand pointer moves from tail to head. When an object's visited bit is set, the pointer clears that bit and continues.

The insertion position enables quick demotion. New objects enter at the head while the pointer scans behind them. If an object receives no further access, the scan removes it when the pointer arrives.

The SIEVE paper reports 21% mean miss-ratio reduction against FIFO on the CDN1 dataset at its large cache size. The best 10% of those traces exceed 42% reduction. In a separate Meta trace experiment, throughput exceeds optimized LRU and TwoQ by 2x at 16 threads.

The authors implemented SIEVE in five production cache libraries, with fewer than 20 changed lines on average. These include groupcache, lru-rs, lru-dict, and mnemonist. That demonstrates porting effort; it does not establish company-wide production adoption of SIEVE.

A hit records reuse in the visited bit. The eviction scan clears that bit without promoting the object.

The queue itself is the remaining bottleneck

S3-FIFO and SIEVE avoid the linked-list lock on hits, but the queue remains shared. Concurrent insertions and removals can contend at its head and tail. Improving the miss ratio therefore leaves a throughput bottleneck.

Mobius (SIGMETRICS 2025, Dong, Wang, Jiang, Feng) addresses queue contention. Two lock-free FIFO queues permit concurrent insertion and removal without locks. Lock-free designs update shared state with atomic instructions. Other threads can continue to make progress if one thread stalls.

Mobius also changes eviction. Its consecutive detection mechanism combines several removal-related state changes into one atomic operation to reduce data races. Fewer changes reduce the opportunities for threads to conflict.

The authors evaluated implementations in CacheLib and RocksDB on synthetic and real workloads. The published abstract reports improved concurrency while maintaining high hit ratios. The relevant result is performance within those implementations, not a guaranteed gain for every cache.

These algorithms optimize different aspects of eviction. S3-FIFO and SIEVE improve the choice of objects to remove. Mobius reduces the cost of making that choice concurrently across threads.

Choosing between the two axes

Miss ratio and throughput can change independently. Reducing the miss ratio by one percentage point decreases backend requests. But halving cache throughput can eliminate that benefit. First measure which factor limits the system.

Miss ratio takes priority where a single miss is expensive. If origin access dominates response time, reducing misses can save more time than optimizing the cache lookup. In that case the lower miss ratio of S3-FIFO and SIEVE converts directly into response time.

Throughput takes priority when misses are inexpensive and requests arrive frequently. Examples include in-memory caches and storage engine block caches. More cores can make lock contention dominate total latency. The workloads evaluated with Mobius in CacheLib and RocksDB are in 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

The evaluated cache traces contain temporal locality and repeated access to popular objects. Quick demotion benefits workloads where many newly inserted objects are not reused before eviction. The same miss-ratio ranking need not hold when those access patterns change.

The SOLAR paper (2026-07, arXiv:2607.00394) reports a workload without temporal locality or concentrated access frequency. Its target is the semantic retrieval buffer of a large language model (LLM) agent. In this environment, a carefully tuned policy can perform worse than LRU, LFU, or plain FIFO.

SOLAR separates replacement timing from content selection, using regret accumulation and Bayesian online learning. It reports 5-75% relative improvement over FIFO at tight capacities. This measures semantic retrieval quality with continuous similarity, not the binary cache miss ratio used in the earlier experiments.

These results do not invalidate S3-FIFO or SIEVE. Web caches, CDNs, and storage block caches often have clear temporal locality and remain the majority of workloads. All three algorithms were evaluated on such traces. If embedding similarity determines cache access, it is safer to evaluate the policy on your own traces before adoption.

Summary

S3-FIFO and SIEVE defer queue changes and filter objects unlikely to be reused. Mobius applies lock-free queues to reduce contention during concurrent insertion and eviction.

Compare miss ratio and throughput together, using the cost of origin access to weigh their impact. Replay the actual workload before adoption, especially when semantic similarity changes what a cache hit means.