Lru cache

[alanprot]

trafficstars

What this PR does:

Previously, the postings cache used a FIFO (First-In, First-Out) strategy for expiring items.

This PR updates the expiration strategy to LRU (Least Recently Used).

The implementation remains largely the same, with the key difference being that items are now moved to the back of the list whenever they are accessed. (items are expired from the front of the queue).

https://github.com/cortexproject/cortex/compare/master...alanprot:lru-cache?expand=1#diff-2fbd6f34014d2c606685456d6f0ff05de42c9df131c81bc28c6e225a89f5b7ecR343

I will keep this in draft for now.

Which issue(s) this PR fixes: Fixes #

Checklist

• [ ] Tests updated
• [ ] Documentation added
• [ ] CHANGELOG.md updated - the order of entries should be [CHANGE], [FEATURE], [ENHANCEMENT], [BUGFIX]

[alanprot]

cc @GiedriusS that is implementing the same in thanos.

[GiedriusS]

Have you considered using some alternative and perhaps more efficient admission/eviction policies like TinyLFU or some others?

[stale[bot]]

This issue has been automatically marked as stale because it has not had any activity in the past 60 days. It will be closed in 15 days if no further activity occurs. Thank you for your contributions.