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.
> 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
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...