Proposal to Integrate SIEVE Eviction Algorithm

[yazhuo]

Hi there,

Our team (@1a1a11a )has developed a new cache eviction algorithm, called SIEVE. It’s simple, efficient, and scalable.

Why SIEVE could be a great addition:

• Simplicity: Integrating SIEVE is straightforward, usually needing to change less than 20 lines of code on average.
• Efficiency: On skewed workloads, which are typical in web caching scenarios, SIEVE is top-notch.
• Cache Primitive: SIEVE is not just another algorithm; it's a primitive that could enhance or replace LRU/FIFO queues in advanced systems like LeCaR, TwoQ, ARC, and S3-FIFO.

Welcome to dive into the details on our website sievecache.com and on our SIEVE blog.

We would love to explore the possibility of integrating SIEVE into caffeine simulator. We believe it could be a beneficial addition to the library and the community.

Looking forward to your feedback!

[ben-manes]

Of course, any contribution will be warmly welcome. I am casually working on s3-fifo and sieve during the holidays, and earlier implemented qdlp. All of them should be validated against your simulator using a few sample traces to ensure correctness. If you'd like to implement a policy then please do, or else I will eventually get them integrated as time permits.

[yazhuo]

Thanks for the quick response! Greatly appreciate your work on implementing S3-FIFO and SIEVE.

[ben-manes]

This is ready on the v3.dev branch and I will merge it in once the CI completes (in case it catches any static analyzer goofs).

• Sieve is implemented as a direct port of the python in your blog post.
• S3Fifo is implemented based on the paper's pseudo code and the libcachesim implementation.
• I verified they had the exact same hit and byte hit rates as libcachesim for your sample trace files.
• I tried to match as close to the originals to avoid any deviations, so S3FIFO uses linked lists with hash tables per the reference. That does not highlight the paper proposed optimizations but there is not yet a reference implementation of those. Since they might change the hit rate profile, I decided to strictly track your reference to avoid diverging results.
• libcachesim does not update the entry's size on a cache hit but does record the new byte size with its hit rate, while in this simulator the entry is updated and an eviction is triggered if needed. I verified with your approach before switching to use this one's (can cause a very minor difference).
• I modified both algorithms to immediately reject an entry that exceeds the maximum byte size rather than flushing the cache, exceeding its size, or causing a crash.
• I noticed that the S3FIFO paper's pseudo code does not bound the ghost queue, while the reference and description do. FYI since that might cause a memory leak if an implementor is not careful.
• I removed QDLP because it lacks pseudo code and I could not guarantee that my version would be equivalent to the reference's.
• libcachesim does not build on arm64 as it has a hard dependency on x86-64 (not a problem, just had to switch laptops).

[1a1a11a]

Hi Ben, Thank you for the great work! They all sound good to me.

1. Yes, libCacheSim does not update entry size upon cache hit because some other external libraries do not support it and if new algorithms forgot update size, the comparison is unfair. But you are right, I should support this. Will update this soon.
2. You are right, I did not want spend a lot of space, so it did not bound the queue size. Maybe I should have added it.
3. QD-LP is more of an idea, not an algorithm --- it adds a small FIFO queue to existing algorithms, which can be ARC or TinyLFU.
4. I fixed the issue, and libCacheSim can compile on Mac now! :)

[ben-manes]

Yes, libCacheSim does not update entry size upon cache hit because some other external libraries do not support it and if new algorithms forgot update size, the comparison is unfair. But you are right, I should support this. Will update this soon.

Unfortunately it feels unfair regardless of how one treats the entry's size changing. If it changes by a significant amount then a policy may waste space simply because it cached it earlier or later in the trace. It seemed really odd to update on a hit, but also one of the only fair solutions.

AdoptSize's simulator uses the (trace key + size) as its key. That has the benefit that treating entries as immutable objects which makes sense as the hit was for a different value. However, it fails to remove the old key so multiple entries for that key are in the cache, and this is an even more obscure solution that others would deviate from.

I just try to keep it consistent and keep it in mind when verifying results across simulators. I don't think any choice is better than another's or worth supporting multiple. I don't recall it causing a hit rate difference of more than half a percent, and at 1-3% differences between policies it is mostly noise to not worry about. It's really the 6-8%+ differences that I try to be more thoughtful about and consider anything within a tolerance level to be equivalent.

[1a1a11a]

I agree. Using hash(key + size) is not unreasonable, and I recall that Meta uses a similar approach (key + modifyTime) in some caches. But this would cause more one-hit wonders and make admission algorithms, including S3-FIFO, more valuable than reality...

I agree that being consistent is crucial. Maybe we should have a doc keeping track of the difference between simulators and potential pitfalls when comparing between simulators.