Closed scalalang2 closed 9 months ago
SIEVE is a cache eviction algorithm introduced in this paper, NSDI'24.
While the design may be considerably simpler. It exhibits very high efficency in comparison to TinyLFU and other LRU-based cache policy.
itemSize=500000, workloads=7500000, cacheSize=0.10%, zipf's alpha=0.99 CACHE | HITRATE | MEMORY | DURATION | HITS | MISSES -----------------+---------+---------+--------------+---------+---------- sieve | 47.42% | 0.11MiB | 1.696241334s | 3556217 | 3943783 tinylfu | 47.38% | 0.11MiB | 1.83996925s | 3553759 | 3946241 s3-fifo | 47.18% | 0.17MiB | 2.55645275s | 3538858 | 3961142 slru | 46.48% | 0.11MiB | 1.992343833s | 3486209 | 4013791 s4lru | 46.15% | 0.11MiB | 1.494798542s | 3461183 | 4038817 two-queue | 45.49% | 0.17MiB | 2.82819925s | 3411961 | 4088039 clock | 37.34% | 0.10MiB | 1.869039875s | 2800767 | 4699233 lru-hashicorp | 36.59% | 0.08MiB | 1.970333916s | 2744181 | 4755819 lru-groupcache | 36.59% | 0.11MiB | 1.9702115s | 2744181 | 4755819
It only has one FIFO queue (using Doubly Linked List) and one special pointer called hand.
hand
SIEVE
SIEVE is a cache eviction algorithm introduced in this paper, NSDI'24.
While the design may be considerably simpler. It exhibits very high efficency in comparison to TinyLFU and other LRU-based cache policy.
Design
It only has one FIFO queue (using Doubly Linked List) and one special pointer called
hand.