SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches
Talkat 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24) · 2024-04-16..04-18·
summary
SIEVE is an eviction algorithm that uses a moving “S” hand to give lazy promotion and quick demotion, keeping hits lock-free so cache hits require no locking. Implementations in five production cache libraries average under 20 lines of change; a prototype doubles throughput versus an optimized 16-thread LRU. On 1,559 real traces SIEVE cuts miss ratio up to 63.2% versus ARC, beats nine state‑of‑the‑art algorithms on >45% of traces (next best 15%), and users report up to 3× miss reduction and 16% CPU savings.
AI-written summary · about
chapters (16)
- 0:00SIEVE introduction
- 1:01Web cache eviction challenges
- 2:48LRU scalability issues
- 3:08Simplicity in cache design
- 5:37Introducing SIEVE
- 5:58Efficient eviction properties
- 8:34FIFO Reinsertion limits
- 10:21SIEVE lazy promotion
- 12:54SIEVE design benefits
- 13:14Evaluation setup results
- 14:39SIEVE on production traces
- 15:02Throughput vs LRU
- 15:22SIEVE simplicity adoption
- 15:42SIEVE building block
- 16:46SIEVE effectiveness limits
- 17:09Conclusion impact
related talks
42mCaching for Cash
16mCacheSifter: Sifting Cache Files for Boosted Mobile Performance and Lifetime
01h 01mWhat do you mean by "Cache Friendly"?
38mThe power of cache in a slow world
58mCaching the uncacheable: delivering personalized experiences without sacrificing performance
34mCache = Cash! 2.0
27mNext-gen Caching Infrastructure
30mCaching for Speed: Practical Performance Optimization in OpenSearch & Lucene