hesela.devSIEVE cache eviction
SIEVE is a cache replacement policy that retains insertion order and uses a visited bit and a moving pointer to select an unvisited eviction victim.
New entries start unvisited; a hit sets their bit without moving them. Eviction clears visited bits while advancing the pointer, leaving survivors in place instead of reinserting them with newcomers. [1]
The NSDI paper explicitly reports that SIEVE is not scan-resistant; some block-cache workloads perform worse than LRU. A web-cache result does not identify an SSD's internal policy. [2]
Relations
- related
- clock-replacement, lru-replacement, cache-pollution, cache-admission
Citations
- NSDI24-SIEVE author artifact, commit 0861f8261c37b8286a70449a1defb5a4749c72d2: Sieve.c, insertion and eviction operations.
- Zhang et al. SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches. NSDI 2024, sections 3, 4 and 7.2.