Algorithms for cache replacement are computable approximations of universal sequence predictors, though we don't often think of them that way. As such, they are balancing the number of patterns they can "see" in the workload with the computational cost of representing pattern state. Recency-only algorithms are blind to high-probability patterns in the same way frequency-only algorithms are, so algorithms that can see all high-probability patterns must have elements of both.

For sufficiently complex workload patterns, the details of competent algorithms will have minimal impact on cache hit rates. A good algorithm will capture all of the high-probability cases and the low-probability cases are essentially treated as stochastic. Small differences in synthetic tests of cache hit rates don't map that well to real-world performance.

An under-rated aspect of the algorithms, somewhat ignored in the literature, are their computational cost. In real systems, the cache replacement algorithm is being exercised upwards of 10s of millions of times per second. The design idiom for high-performance cache replacement systems is to filter for algorithms that can see all the standard high-probability cases, of which there are dozens, and then select for optimizability in a classic performance-engineering sense e.g. CPU cache behavior. Marginal differences in cache hit rate become dwarfed by large differences in practical computational cost.

I agree. This is why DashCache is designed to be very efficient in terms of CPU and memory, while providing very strong adaptive capabilities for mixed workloads.

If think the most important part in this design is the realization that we do not need a global order in order to choose an entry to evict: other heuristics like LRU, LFU, frecency - they strive to provide a single number, a metric. Obviously this metric lies because a single number can not represent well both qualities like frequency and recency. DashCache, on the other hand, does not try to do it at all. Instead, it implicitly defines a partial order between entries in the same bucket or segment....

> the most important part in this design is the realization that we do not need a global order in order to choose an entry to evict

This is a key insight many people miss. The optimal eviction is not computable, so any reasonable approximation will likely have a similar outcome. Given this, it makes sense to pick an approximation that facilitates other objectives, like computational performance.

   Recency-only algorithms are blind to high-probability patterns 
   in the same way frequency-only algorithms

A high probability occurrence must be frequent and will stay reasonably recent. Unless it's high probability that just /somehow/ doesn't happen much.

Perhaps you can provide some citations to some of the things you have written here.

   the cache replacement algorithm is being 
   exercised upwards of 10s of millions of times per second

This is database pages not CPU cache lines. It is not that high.

Many databases ordinarily modify the page cache 10 million times per second under load. I have one doing that right now on an i3en.12xlarge, which is only half a server. Not every cache replacement algorithm family has that kind of throughput but some common algorithm families do e.g. clock-sweep variants.

The "high-probability" refers to a type of pattern, not a specific instance, so there is no implication of recency. A page access pattern can be detected frequently but involve different pages each time.

Bélády's optimality theorem means cache replacement algorithm performance is governed by the theoretical limits on sequence prediction. You can optimize for either breadth or depth; improving performance for one pattern necessarily reduces performance for others. In practice, database caches optimize heavily for a few patterns and ignore the rest; the performance for the patterns they ignore is not much worse than if they optimized for all patterns equally, so it is a good trade.

What about MRU-biased workloads? For example an analytical loop or row scanning in a db query? In those cases recency is a negative signal and there may not be much frequency to extract (e.g. equal frequencies in a loop). Instead the policy has to avoid admissions to obtain some hits rather than be flushed for zero hits.

Think you mean round robin, yes, that's an issue but that's equal probability, not high probability (his phrase). I don't know a scheduler that will handle that as well as handling LRU replacement well and if you have any cites I would appreciate them.

Also remember that many DBs are multi-user so any access patterns from each connection will get thrown in the same bucket.

It is handled by W-TinyLFU where I use this scenario as a stress test [1]. While LIRS / LIRS2 did not pass this one scenario, the quality of the work behind that policy leads me to believe it could be improved to handle that case.

[1] https://github.com/ben-manes/caffeine/wiki/Efficiency#adapti...

Appreciate the reply, as I said not my field but I do find it really interesting.

> An under-rated aspect of the algorithms, somewhat ignored in the literature, are their computational cost.

Since I mentioned ZFS... IIRC ZFS struggles to scale to NVMEs in part due to the ARC. When the penalty for missing the cache was hundreds of milliseconds you could afford doing work, but not so much these days.

frecency sounds similar to Redis' LFU which uses logarithmic counters [1]. Unfortunately many of these algorithms only do a good job in specific workloads and under perform in others. That's perfectly fine if one can narrow to a specific use-case, like a cache server which is LRU-biased [2], so the focus on other optimizations like Dragonfly's optimized storage costs makes a lot of sense.

[1] http://antirez.com/news/109

[2] https://github.com/twitter/cache-trace