There is no absolutely "better" algorithm in caching. Depends on the usage pattern of the user. We believe LRU is very simple, predictable and works well for most use cases, so it's a good default . It is unrelated to the fact that the Redis LFU implementation is good or not. Your argument is not valid to justify you misrepresented Redis abilities in the post.
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?
Aside for anything else, backwards compatibility is good (repeatability for a certain behaviour). And it doesn't seem relevant as to why you'd completely ignore it when discussing cache eviction compared to Redis.
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).
To me, 2Q reminded me a lot of the ARC, Adaptive Replacement Cache[1], as I know it from ZFS.
Mixing frequency of access with time of access seems to be a requirement for any cache that sees a mixed workload. On that note, has anyone tried frecency[2] for caching? I never gotten around to testing it myself and can't decide if it'd do a good job or not.
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.
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.
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.
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.
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.
MySQL approximates a hacky version of a similar idea with the bufferpool (newest additions don't go to the top of the LRU so they age out faster if not re-accessed) to avoid random full table scans from thrashing the cache:
Dash sounds super interesting. I hadn't heard of that until now.
If 2Q sounds interesting see also the TinyLFU paper[0]. TinyLFU is the strategy used by Ristretto, the Go LFU cache used by Dgraph, Vitess, and SpiceDB. In the introduction of the paper it lists related works including 2Q and nice high level descriptions of alternatives.
> TinyLFU does not handle dynamic changes to demand to the cache like 2Q does
That was resolved in a follow up paper [1], though Ristretto does not implement this. It is implemented by Caffeine, mentioned briefly in this article, which is popular in the Java ecosystem.
I ended up shortly after editing my post to exclude that sentence because it was a bit more subtle than how I was putting it. Caffeine is definitely a library that makes me jealous of the JVM ecosystem on a regular basis :P
26 comments
[ 4.0 ms ] story [ 72.8 ms ] threadOther similar and interesting non-LRU caches:
MySQL https://medium.com/@arpitbhayani/what-makes-mysql-lru-cache-...
Intel Sandy Bridge+ https://blog.stuffedcow.net/2013/01/ivb-cache-replacement/
https://redis.io/docs/manual/eviction/
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?
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).
https://news.ycombinator.com/item?id=31560547
Mixing frequency of access with time of access seems to be a requirement for any cache that sees a mixed workload. On that note, has anyone tried frecency[2] for caching? I never gotten around to testing it myself and can't decide if it'd do a good job or not.
[1]: https://en.wikipedia.org/wiki/Adaptive_replacement_cache
[2]: https://wiki.mozilla.org/User:Jesse/NewFrecency?title=User:J...
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.
Perhaps you can provide some citations to some of the things you have written here.
This is database pages not CPU cache lines. It is not that high.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...
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.
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.
> 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.
[1] http://antirez.com/news/109
[2] https://github.com/twitter/cache-trace
https://dev.mysql.com/doc/refman/5.7/en/innodb-performance-m...
If 2Q sounds interesting see also the TinyLFU paper[0]. TinyLFU is the strategy used by Ristretto, the Go LFU cache used by Dgraph, Vitess, and SpiceDB. In the introduction of the paper it lists related works including 2Q and nice high level descriptions of alternatives.
[0]: https://www.cs.technion.ac.il/~gilga/TinyLFU_PDP2014.pdf
That was resolved in a follow up paper [1], though Ristretto does not implement this. It is implemented by Caffeine, mentioned briefly in this article, which is popular in the Java ecosystem.
[1] https://dgraph.io/blog/refs/Adaptive%20Software%20Cache%20Ma...