Caching plays a crucial role in optimizing the performance and efficiency of various computing systems, from web servers to database management systems. As the amount of data we deal with continues to grow exponentially, the management of limited cache resources becomes increasingly critical. That's where cache eviction algorithms come into play.

Recently, I stumbled upon a remarkable cache eviction algorithm called SIEVE. According to its homepage, SIEVE is touted as a simpler alternative to the widely used LRU algorithm, with proven superior efficiency compared to many other well-known cache eviction strategies. Intrigued by its potential, I embarked on a deep dive into SIEVE, exploring its inner workings and uncovering its unique benefits. Now, I am excited to share my findings through this blog post.

I. Motivation

Numerous cache eviction algorithms have been developed over the years, all with the goal of improving efficiency. However, these improvements often come at the cost of increased implementation complexity.

This added complexity can lead to hidden issues, such as:

• Increased difficulty in debugging when issues arise
• More computational operations required
• Greater memory usage, as many algorithms need to store more per-object metadata, effectively reducing the cache size available for data caching

II. SIEVE Design

With the motivation of designing a cache eviction algorithm which achieves both simplicity and efficiency, SIEVE was born. Here we come to the SIEVE core design and see what makes it efficient.

1. Lazy promotion and quick demotion

SIEVE effectively incorporates both lazy promotion and quick demotion. As mentioned in this document, it shows that Lazy promotion and Quick demotion are two important properties of efficient cache eviction algorithms

• Lazy promotion is the strategy which promoting cached objects only at eviction time. LRU uses eager promotion, which means that each time the object is accessed/requested, it will be promoted right away
• Quick demotion: which means remove the objects quickly after it’s inserted into the cache. We will talk more about this in the implementation section

2. Implementation

Here is the visualization of how SIEVE works

• Source: SIEVE miss ratio plots / Juncheng Yang | Observable (observablehq.com) Note: In this link we have comparison on multiple traces, please go to the link for further detail.
  • Library used in benchmarks: Mnemonist
  • SieveCacheMyLinkedList is the SIEVE implementation in Typescript that I provided above. The results of my implementation aren't always consistent. At times, it outperforms the LRU, but occasionally, it performs worse. However, when comparing the complexity of my implementation with the LRU implementation from the aforementioned libraries, mine is more efficient.

    

    

From the above benchmark, it's clear that the sieve algorithm can achieve the same or better performance than LRU. Its straightforward implementation makes it a promising cache eviction algorithm worth exploring further.

IV. Downsides

• SIEVE is not scan-resistance, so that it’s only suitable for web cache workload, for I/O workload, it might not be a good choice
  • scan-resistance: With some workloads, i.e I/O workload, there will be a lot of request items which is one hit wonder - item that only requested one time. If that case happens, after the queue of SIEVE is full, every requested item after that will cause cause SIEVE to always evict item

V. References & Source Code

Source code: trunghieu99tt/sieve-cache-eviction-algorithm (github.com)

References:

• nsdi24-SIEVE.pdf (junchengyang.com)
• SIEVE is simpler than LRU - SIEVE: an Efficient Turn-Key Eviction Algorithm for Web Caches (cachemon.github.io)
• Sieve is simpler than LRU | Hacker News (ycombinator.com)
• scalalang2/golang-fifo: Modern efficient cache design with simple FIFO queue only in Golang (github.com)
• Why Aren't We Sieve-Ing? | Hacker News (ycombinator.com)
• SIEVE miss ratio plots / Juncheng Yang | Observable (observablehq.com)
• FIFO can be Better than LRU: the Power of Lazy Promotion and Quick Demotion (jasony.me)
• osdi20-yang.pdf (usenix.org)
• Why Aren't We SIEVE-ing? - Marc's Blog (brooker.co.za)