DragonFlydb: Cache Design

I did not claim that DrashCache is "the absolutely best" algorithm. But some caching algorithms could be better than others on real-world data.

Would you want me to run something like https://github.com/twitter/cache-trace on both Redis/(LRU,LFU) and Dragonfly and see which one has higher hit-rate for the same memory requirements? Would this be a good test to decide if Dragonfly improves on Redis caching quality?

Backward compatibility is good? I disagree with you regarding this specific case. Redis philosophy is to add more and more settings, requiring from an end-user to understand internals and low-level trade-offs. And I am sorry, but in the case of caching use-case, a user wants it to "just work" and it's a reasonable expectation. I've run Redis myself in a startup I worked at - I tried LRU, LFU and it did not work very well due to mixed traffic patterns. And I even did not know if it did not work well due to LFU/LRU heuristic or due to the fact that Redis does random sampling and evicts a small number of items it tests. Eventually, I gave up and moved on. I am sure most users do the same or try increasing its cache capacity to ridiculous sizes.

So yeah, I do not completely ignore Redis LFU, I just did not find useful to mention it because from my experience, Redis LFU is not being widely used, and does not have significant advantage over Redis LRU (if at all) and I wanted to maintain the focus and keep my post succinct and clear.

I also have not provided any benchmarks in the post, not because I have something to hide, just because I do not have an easy setup to benchmark cache efficiency vs Redis and I do not have time to invest into it right now.

Back then when I developed DashCache, I used Caffeine simulator to compare it to dozens other heuristics implemented in Caffeine using real-world data (twitter traces) and it was better than most of then (including LFU). It lost to algorithms that keep some information about evicted items (like TinyLFU or its extensions).

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.

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.

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