| Disclaimer: this is the co-author. Sorry for the hyped language. If my guess is correct, the blog was "polished" by ChatGPT, and the intention was to "polish" the English. The paper has more content and should be read more seriously. We will fix the animation error and update the writing shortly. Thank you for the feedback! Regarding some of the complaints on SIEVE performance. Here are some more results that I ran for other purposes.
https://observablehq.com/@1a1a11a/sieve-miss-ratio-plots I haven't had time to add other algorithms to the plot, but they are often similar to or worse than TinyLFU (I did not pick TinyLFU to compare deliberately; I happen to have the figures on hand).
While the results do not include byte miss ratio, which is important in some use cases, they are better than the results already shown. We acknowledge that * SIEVE may not work well on some block I/O workloads (this has been the statement in our writing from the beginning). However, SIEVE works well on large multi-tenanted block I/O workloads (see the Tencent and Alibaba figure in the link). For web workloads, SIEVE shows consistently good results. * As the author, when I look at this algorithm. My own feeling is that SIEVE may not be robust because it keeps evicting new objects when the hand moves to the head, effectively behaving as MRU.
However, our large evaluations showed that modern workloads have certain properties that enable SIEVE to achieve a low miss ratio. We are still investigating this property and how to model it. If someone is interested, feel free to shoot me an email. * implementing SIEVE with a log-structured design or circular buffer is not trivial, but we had a design called Segcache (https://segcache.com), which runs a constrained version of SIEVE.
In simple libraries, linked list implementation should be easy, and one can check the examples on the website. |
At first, I thought FIFO-Merge keeping objects in the insertion order (FIFO) helps the eviction because I mostly worked with Twitter data in which popularity decay is common.
But later when I evaluated more traces (including block I/O workloads), it turned out that quickly evicting new objects (quick demotion) is the source of a low miss ratio. That's why we wrote these papers.
Interested readers are welcome to read more of related work 1. FIFO can be better than LRU, the power of lazy promotion and quick demotion https://dl.acm.org/doi/pdf/10.1145/3593856.3595887
2. FIFO queues are all you need for cache eviction https://dl.acm.org/doi/10.1145/3600006.3613147