SIEVE cache eviction: one bit is not scan resistance

The position of a survivor matters

SIEVE maintains insertion order, a visited bit and a moving eviction pointer. A hit marks the entry without rearranging the list. Eviction clears marked entries as it passes them, stopping at an unmarked victim. Unlike CLOCK expressed as FIFO reinsertion, surviving entries stay in place instead of joining newcomers at the head. The two policies can therefore make different later choices despite using the same amount of visit history.[2]

The author implementation initializes a newly inserted object's visit state to zero; a subsequent hit sets it to one. Several hits before the next clearing pass still provide only one bit of evidence, not a frequency count. The pointer resumes after the removed entry. [3]

This is replacement, not the candidate-versus-victim frequency comparison used by TinyLFU. For that separate decision, see our existing cache-admission review. Machine-readable definitions: SIEVE and CLOCK replacement.

One changed request reverses the winner

Each row starts with an empty cache holding three equal-size objects. A letter identifies one object; every miss inserts it immediately. Counts include cold misses. We execute LRU, FIFO, CLOCK and SIEVE from libCacheSim 0.3.5, not a hand-written replacement engine. CLOCK uses one bit and an initial counter of zero. [4]

After A,A,B,C, the three entries are resident. A has been revisited. Inserting D makes SIEVE clear A's bit, keep A and evict B. LRU instead evicts A, whose last access is older than B's and C's. Asking for A next rewards SIEVE; asking for B rewards LRU. The first two rows differ only in that final request.

The third row separates SIEVE from CLOCK. Both preserve A while admitting D, but CLOCK reinserts A among newer entries. When B misses next, CLOCK's eviction pass clears C and removes A. SIEVE leaves the earlier survivor in place and removes D instead. The final A is consequently a SIEVE hit and a CLOCK miss. The JSON records each hit and miss, not just totals.

The first three examples were selected by an exhaustive lexicographic search over A-D until it found a SIEVE win, a SIEVE loss and a CLOCK difference. They are counterexamples, not a representative sample. The remaining rows deliberately cover repetition, a cold scan, an oversized loop, scan recovery and a fully marked cache. No mean ranking across these handpicked cases has a workload-population interpretation.

In the warm-scan-return row, ABCABC warms the cache; DEF displaces it; ABCABC then returns. All four policies have three warm-up misses, three scan misses and three return-phase misses. A warm object is not protected forever by one earlier hit.

Constant hit work is not constant eviction work

For ABCABCD, all three visit bits are set before D arrives. Our independent model inspects A, B and C, clearing each bit, then inspects A again and evicts it: four candidate inspections for one miss. These are model operations, not instrumentation of library CPU instructions.

For a capacity C and no concurrent hits, that fully marked state needs C+1 inspections to select a victim. That does not imply every miss costs C+1: each clearing consumes a mark established by a previous hit. Separating worst-case work for one eviction from total work over a request history avoids treating a cheap average as a tail-latency guarantee.

In the four-object loop, none of the four policies hits at all. For this trace the miss counts tie, even though their internal metadata work differs. Neither observation measures backend latency, lock contention or NAND reads. Equal hit counts are not evidence of equal application speed.

What the paper establishes, and what it does not

The NSDI 2024 evaluation covers 1,559 web-cache traces from seven sources, including two proprietary CDN collections. Its main efficiency comparison ignores object-size variation and replays requests with immediate fill. The reported greater-than-twofold throughput advantage at 16 threads is a CacheLib prototype result on a Meta trace; cache and working-set sizes grow with thread count. It is not a universal speed multiplier.[1, sections 4.1-4.3]

Section 7.2 explicitly identifies lack of scan resistance: some block-cache workloads have higher SIEVE miss ratios than LRU. These results do not establish the replacement policy of any retail SSD, nor justify replacing a storage cache without tracing its workload.[1, section 7.2]

Our replay neither reproduces that study nor validates its multicore benchmark. It tests a narrow algorithmic distinction using a later library release. There is no sampling confidence interval for these fully specified sequences; the uncertainty is whether a real workload resembles them.

Before a deployment comparison, hold the observed request stream, cache budget and admission rules constant. Include object sizes, metadata, expiration, writes and refill delays where relevant. Measure backend work and response-time distributions separately from hit ratio. Preserve negative results when the simpler policy is already sufficient.

Replay and check every decision

The result JSON contains all sequences, H/M outcomes, assumptions, versions and the script hash. The Python replay script checks SIEVE against a separate list-based model for all 729 six-request strings over A-C at capacities one, two and three, plus all 65,536 eight-request strings over A-D at capacity three: 67,723 comparisons. The larger set includes the CLOCK counterexample above. This bounded check does not prove correctness for all inputs or concurrent use.

python3 -m venv .venv
.venv/bin/pip install libcachesim==0.3.5
.venv/bin/python sieve-traces.py --output reproduced.json

The recorded dependency versions describe our isolated Python 3.12 environment. Use --discover to repeat the counterexample search. There is no random seed because enumeration and the input traces are deterministic. Different Python versions change the environment field, not the expected hit/miss sequences.

The regression tests also reject invalid inputs, a mismatched library version and an intentionally broken oracle, including under Python's optimization mode. The generated JSON records the two exhaustive domains and its actual generation time. Hesela's script, tests and constructed results use the MIT license.

libCacheSim's Python package is GPLv3+; its upstream code and the research paper retain their respective rights. No library binary, private trace or paper figure is redistributed here.

Primary sources

1. 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. NSDI 2024, pp. 1229-1246; sections 3, 4 and 7.2.
2. Yang and colleagues. SIEVE: Cache eviction can be simple, effective, and scalable. USENIX ;login:, 16 June 2024. Author explanation of list ordering.
3. NSDI24-SIEVE author artifact, commit 0861f8261c37b8286a70449a1defb5a4749c72d2: Sieve.c, insertion and eviction operations.
4. libCacheSim Python binding 0.3.5. Version used for Hesela's constructed trace replay, not the original 2024 evaluation binary.