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....
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
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
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.
Also remember that many DBs are multi-user so any access patterns from each connection will get thrown in the same bucket.
[1] https://github.com/ben-manes/caffeine/wiki/Efficiency#adapti...
> 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.
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.