5 ms·

DragonFlydb: Cache Design

84 points by anhldbk 4y ago

alecco 4y ago
Very cool. Other similar and interesting non-LRU caches: MySQL https://medium.com/@arpitbhayani/what-makes-mysql-lru-cache-scan-resistant-a73364f286d7 https://medium.com/@arpitbhayani/what-makes-mysql-lru-cache-... Intel Sandy Bridge+ https://blog.stuffedcow.net/2013/01/ivb-cache-replacement/ https://blog.stuffedcow.net/2013/01/ivb-cache-replacement/
Andys 4y ago
It seems odd that the article doesn't mention Redis's LFU mode which improved on LRU since about 5+ years ago.
- xbar 4y ago
  I'd love to see an article that discusses the differences.
- romange 4y ago
  If Redis LFU mode improved LRU then why they kept the LRU mode? The official recommendation by Redis is to use LRU. https://redis.io/docs/manual/eviction/ https://redis.io/docs/manual/eviction/
  - antirez 4y ago
    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.
    - romange 4y ago
      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 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?
  - Andys 4y ago
    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.
    - romange 4y ago
      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).
alberth 4y ago
HN post from 3 months ago with 350+ comments. https://news.ycombinator.com/item?id=31560547 https://news.ycombinator.com/item?id=31560547
- Andys 4y ago
  And Redis LFU not mentioned even once... seems like the most unknown feature of Redis!
magicalhippo 4y ago
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. [1]: https://en.wikipedia.org/wiki/Adaptive_replacement_cache https://en.wikipedia.org/wiki/Adaptive_replacement_cache [2]: https://wiki.mozilla.org/User:Jesse/NewFrecency?title=User:Jesse/NewFrecency https://wiki.mozilla.org/User:Jesse/NewFrecency?title=User:J...
- jandrewrogers 4y ago
  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.
  - heisjustsosmart 4y ago
    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.
makmanalp 4y ago
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: https://dev.mysql.com/doc/refman/5.7/en/innodb-performance-midpoint_insertion.html https://dev.mysql.com/doc/refman/5.7/en/innodb-performance-m...
jzelinskie 4y ago
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. [0]: https://www.cs.technion.ac.il/~gilga/TinyLFU_PDP2014.pdf https://www.cs.technion.ac.il/~gilga/TinyLFU_PDP2014.pdf
- NovaX 4y ago
  > 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. [1] https://dgraph.io/blog/refs/Adaptive%20Software%20Cache%20Management.pdf https://dgraph.io/blog/refs/Adaptive%20Software%20Cache%20Ma...
  - jzelinskie 4y ago
    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
antirez 4y ago
Redis has LFU, implemented many years ago.

84 points by anhldbk 4y ago

Very cool. Other similar and interesting non-LRU caches: MySQL https://medium.com/@arpitbhayani/what-makes-mysql-lru-cache-scan-resistant-a73364f286d7 https://medium.com/@arpitbhayani/what-makes-mysql-lru-cache-... Intel Sandy Bridge+ https://blog.stuffedcow.net/2013/01/ivb-cache-replacement/ https://blog.stuffedcow.net/2013/01/ivb-cache-replacement/

Andys 4y ago

It seems odd that the article doesn't mention Redis's LFU mode which improved on LRU since about 5+ years ago.

xbar 4y ago
I'd love to see an article that discusses the differences.
romange 4y ago
If Redis LFU mode improved LRU then why they kept the LRU mode? The official recommendation by Redis is to use LRU. https://redis.io/docs/manual/eviction/ https://redis.io/docs/manual/eviction/
- antirez 4y ago
  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.
  - romange 4y ago
    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 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?
- Andys 4y ago
  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.
  - romange 4y ago
    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).

alberth 4y ago

HN post from 3 months ago with 350+ comments. https://news.ycombinator.com/item?id=31560547 https://news.ycombinator.com/item?id=31560547

Andys 4y ago
And Redis LFU not mentioned even once... seems like the most unknown feature of Redis!

magicalhippo 4y ago

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. [1]: https://en.wikipedia.org/wiki/Adaptive_replacement_cache https://en.wikipedia.org/wiki/Adaptive_replacement_cache [2]: https://wiki.mozilla.org/User:Jesse/NewFrecency?title=User:Jesse/NewFrecency https://wiki.mozilla.org/User:Jesse/NewFrecency?title=User:J...

jandrewrogers 4y ago
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.
- heisjustsosmart 4y ago
  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.

makmanalp 4y ago

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: https://dev.mysql.com/doc/refman/5.7/en/innodb-performance-midpoint_insertion.html https://dev.mysql.com/doc/refman/5.7/en/innodb-performance-m...

jzelinskie 4y ago

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. [0]: https://www.cs.technion.ac.il/~gilga/TinyLFU_PDP2014.pdf https://www.cs.technion.ac.il/~gilga/TinyLFU_PDP2014.pdf

NovaX 4y ago
> 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. [1] https://dgraph.io/blog/refs/Adaptive%20Software%20Cache%20Management.pdf https://dgraph.io/blog/refs/Adaptive%20Software%20Cache%20Ma...
- jzelinskie 4y ago
  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

antirez 4y ago

Redis has LFU, implemented many years ago.