# Why Aren't We SIEVE-ing?

DevFeed: [Why Aren't We SIEVE-ing?](<https://devfeed.tech/articles/why-aren-t-we-sieve-ing-12548.md>)

Original publisher: [Read original article](<http://brooker.co.za/blog/2023/12/15/sieve.html>)

Author: Marc Brooker

Published: 2023-12-15T00:00:00Z

Content type: opinion

Language: en

Sources: [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog.md>), [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog-2.md>)

Topics: [Caching](<https://devfeed.tech/topics/caching.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Latency](<https://devfeed.tech/topics/latency.md>), [systems](<https://devfeed.tech/topics/systems.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [cache](<https://devfeed.tech/tags/cache.md>), [caching](<https://devfeed.tech/tags/caching.md>), [design](<https://devfeed.tech/tags/design.md>), [latency](<https://devfeed.tech/tags/latency.md>), [performance](<https://devfeed.tech/tags/performance.md>)

## AI overview

The article discusses SIEVE, a cache eviction algorithm presented as a simple enhancement to a FIFO queue. It compares cache eviction strategies and explains tradeoffs involving miss ratio, access and eviction cost, latency, efficiency, and metadata size. The supplied text reports that SIEVE outperforms nine state-of-the-art algorithms on more than 45% of 1,559 traces and reduces synchronization needs by avoiding queue reordering on access.

## Source excerpt

Why Aren't We SIEVE-ing? Captain, we are being scanned! Long-time readers of this blog will know that I have mixed feelings about caches. One on hand, caching is critical to the performance of systems at every layer, from CPUs to storage to whole distributed architectures. On the other hand, caching being this critical means that designers need to carefully consider what happens when the cache is emptied, and they don't always do that well1. Because of how important caches are, I follow the literature in the area fairly closely. Even to a casual observer, it's obvious that there's one group of researchers who've been on a bit of a tear recently, including Juncheng Yang, Yazhuo Zhang, K. V. Rashmi, and Yao Yue in various combinations. Their recent papers include a real-world analysis of cache systems at Twitter, an analysis of the dynamics of cache eviction, and a novel FIFO-based cache design with some interesting properties. The most interesting one to me, which I expect anybody who enjoys a good algorithm will get a kick out of, is the eviction algorithm SIEVE (their paper is coming up at NSDI'24). SIEVE is an eviction algorithm, a way of deciding which cached item to toss out when a new one needs to be put in. There are hundreds of these in the literature. At least. Classics including throwing out the least recently inserted thing (FIFO), least recently accessed thing (LRU), thing that's been accessed least often (LFU), and even just a random thing. Eviction is interesting because it's a tradeoff between accuracy, speed (how much work is needed on each eviction and each access), and metadata size. The slower the algorithm, the less latency and efficiency benefit from caching. The larger the metadata, the less space there is to store actual data. SIEVE performs well. In their words: Moreover, SIEVE has a lower miss ratio than 9 state-of-the-art algorithms on more than 45% of the 1559 traces, while the next best algorithm only has a lower miss ratio on 15%. What's