Diving into a new cache eviction algorithm called SIEVE

A new cache eviction algorithm called SIEVE.

Its implementation is as easy as LRU, and the results on web traces are amazing.

Main idea behind this algorithm:

1. Demote elements out of the cache quickly 📤
2. Lazy Updates 💤

SIEVE does this by maintaining a list of elements:

1. Always add elements at the head.
2. When an element is accessed, mark it as visited.
3. Keep a current pointer (initially at tail).
4. When you run out of cache space and need an eviction, move the current pointer towards the head.
   • If the element is not visited: Kick it out and stop.
   • If not, remove the visited marker for this element.
5. Tada!

This simple algorithm outperforms state-of-the-art ML cache eviction algorithms.

Link to paper: Here.

For more details on caching algorithms, check out the system design course at InterviewReady.