Comment by bhaney
2 years ago
The algorithm described here (randomly picking some small number of keys and evicting the oldest one among them) is the core of how Redis' "LRU" cache eviction policies work, in case anyone was wondering.
2 years ago
The algorithm described here (randomly picking some small number of keys and evicting the oldest one among them) is the core of how Redis' "LRU" cache eviction policies work, in case anyone was wondering.
In a similar vein, there's a neat "Efficient Page Replacement" strategy described in a LeanStore paper [0] that combines random selection with FIFO:
> Instead of tracking frequently accessed pages in order to avoid evicting them, our replacement strategy identifies infrequently-accessed pages. We argue that with the large buffer pool sizes that are common today, this is much more efficient as it avoids any additional work when accessing a hot page
> by speculatively unswizzling random pages, we identify infrequently-accessed pages without having to track each access. In addition, a FIFO queue serves as a probational cooling stage during which pages have a chance to be swizzled. Together, these techniques implement an effective replacement strategy at low cost
[0] https://db.in.tum.de/~leis/papers/leanstore.pdf
Came here to say the same thing.
There's a follow-up paper from last year that talks about some refinement of this strategy (6.2 page replacement), among other things.
"The Evolution of LeanStore"
https://dl.gi.de/server/api/core/bitstreams/edd344ab-d765-44...
Thanks for the pointer :) it seems there's a follow-up to that paper in turn, with an explicit focus on that eviction strategy: "Write-Aware Timestamp Tracking"
https://www.vldb.org/pvldb/vol16/p3323-vohringer.pdf
1 reply →