[NSDI 2024]: SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches

[JackTan25]

Note: Please use Issues only for bug reports. For questions, discussions, feature requests, etc. post to dev group: https://groups.google.com/forum/#!forum/rocksdb or https://www.facebook.com/groups/rocksdb.dev

Motivation

We can use SIEVE to improve cache hit for rocksdb

Abstract

Caching is an indispensable technique for low-cost and fast data serving. The eviction algorithm, at the heart of a cache, has been primarily designed to maximize efficiency— reducing the cache miss ratio. Many eviction algorithms have been designed in the past decades. However, they all tradeoff throughput and/or simplicity to achieve high efficiency. Such a tradeoff often hinders adoption in production systems.

This work presents SIEVE, an algorithm that is simpler than LRU and provides better than state-of-the-art efficiency and scalability for web cache workloads. We implemented SIEVE in five production cache libraries, and it requires fewer than 20 lines of code change on average. Our evaluation using 1559 cache traces from 7 sources shows that SIEVE achieves up to 63.2% lower miss ratio than ARC. Moreover, SIEVE has lower miss ratio than 9 state-of-the-art algorithms on more than 45% of the 1559 traces, while the next best algorithm only achieves 15%. SIEVE’s simplicity comes with superior scalability as cache hits require no locking. Our prototype in Cachelib achieves twice the throughput of an optimized LRU at 16 threads. SIEVE is more than an eviction algorithm; it can be used as a cache primitive to build advanced eviction algorithms just like FIFO and LRU.

[JackTan25]

/assign me

[1a1a11a]

This is the author of S3-FIFO and SIEVE. If you just want to implement one, I think S3-FIFO might be a better option because the workload is blockI/O, but SIEVE may also work (we do not know). But if you want to test SIEVE, I am happy to learn the result.

[chrisxu333]

This is the author of S3-FIFO and SIEVE. If you just want to implement one, I think S3-FIFO might be a better option because the workload is blockI/O, but SIEVE may also work (we do not know). But if you want to test SIEVE, I am happy to learn the result.

Thank you for your advise! Sorry for the late response. Since @JackTan25 may have started implementing SIEVE, I think we'll finish it off first before working on S3-FIFO. Will let you know when its done :)

[1a1a11a]

Cool! :)