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 golang-lru. We believe it could be a beneficial addition to the library and the community.

Looking forward to your feedback!

[venkatsvpr]

I have been using golang-lru repo for many years now. Thanks everyone who contributed.

I read the Sieve paper and it is super cool. I would like to volunteer to integrate sieve into golang-lru.

Thanks!

cc - @yazhuo

[1a1a11a]

Awesome! Let us know if you need any help or have any question. :)

[yazhuo]

@venkatsvpr Great to hear from you! Thanks for your support.

Btw, I think it might be better to integrate SIEVE in an opt-in manner.

[venkatsvpr]

Thanks @1a1a11a @yazhuo

Yes - Agree!

[venkatsvpr]

Hi folks, @irenarindos @mgaffney @paskal

Want to touch base with you to see if the proposal make sense to you.

Thanks!

[mgaffney]

Hi!

We are interested in seeing a more detailed proposal. Keep in mind that any proposed changes should not change the default behavior or characteristics of the current v2 implementation (meaning using SIEVE would have to be optional). We could then gather feedback from users and consider making it the default in the next revision (v3).

[venkatsvpr]

Hi @mgaffney Thanks for getting back.

I have added two New methods (NewSieve and NewSieveWithEvict) which would work with SIEVE evicition.

Please take a look at this PR and add your comments.

[mgaffney]

@venkatsvpr that PR is not for this repo

[venkatsvpr]

Yes. Let me complete the PR and send out another PR for this repo. Thanks!

[venkatsvpr]

I've updated the PR https://github.com/hashicorp/golang-lru/pull/169

Please take a look.mgaffney

Also, if & when there is a v3 version, It'd be great with the change the New signature. This would make us future proof the new changes we might have. (like sieve)

[venkatsvpr]

@mgaffney Did you get a chance to check out the PR #169
Let me know if I can be of any help.

Thanks!