5 ms·

Anyone familiar with caching algorithms will groan when they read the description of the "sampling" LRU. First, LRU isn't that great--it is a _lot_ better than

Anyone familiar with caching algorithms will groan when they read the description of the "sampling" LRU. First, LRU isn't that great--it is a _lot_ better than nothing and having a suitably large cache tends to cover up cache eviction problems, but LRU is still susceptible to a number of problems. The pseudo-LRU redis used to have is appropriate for very high-speed caches (it's essentially a 5-way associative cache), but is so very not appropriate when going out to disk, where the access latency is horrible. ARC as mentioned below incorporates the LFU statistics, but it is patent encumbered. A number of other NoSQL systems implement either 2Queues ("Segmented LRU") or LIRS. My team recently implemented both of these for a block-caching system and found LIRS to perform better for our purposes; essentially LIRS has a bit more information that it collects so it can evict low future-probability data faster and thus retain more data that is likely to be accessed again in the future. It only takes a few more hits to be worth it. The downside to LIRS is that it's more complicated than 2Queues, and far less well-described in the literature. See https://en.wikipedia.org/wiki/Cache_algorithms https://en.wikipedia.org/wiki/Cache_algorithms The thing that's really necessary, though, is to collect metrics and to have an instrumented version that will log all accesses. Given a log of all accesses, you can compare whatever implementation you use to Bélády's algorithm (i.e., perfection). Without instrumentation and testing, it is very very difficult to know what the right strategy is. Anyway, this helps confirm redis in my mind as a great amateur NoSQL system.

eternalban 10y ago
> "amateur NoSQL" That was entirely unnecessary and imho open to question given that quite a lot of /businesses/ run on Redis.
- jonstewart 10y ago
  A lot of businesses also run on MS Access. I think redis is in the great tradition of amateurism, and is about as good as you can get under that approach. It's a lot better than a number of other systems, and it's also somewhat limited.
  - zaroth 10y ago
    Redis is no Access, but at least it goes to show that heavily-funded enterprise software is often worse, not better. To me this smacks of academic eliteism. At the scale and density it is used, Redis is by definition not amateurish. Amateur means either unpaid or inept. Describing Redis as inept can only mean you've never used it and are unable to appreciate the incredible diversity of problems for which Redis provides truly excellent reliability, usability, and performance all at once. Antirez succeeded in providing a great measure of all 3 of those traits all at once, and in a code base which is surprisingly easy to read and maintain. To me Redis is in fact a modern marvel. Proof of what a 10x engineer can achieve when left alone to get shit done.
    - jonstewart 10y ago
      I definitely don't mean to suggest that antirez is inept. While redis is technically now a commercial/professional endeavor, I don't think that the commercial side of it (which is not a technical comparison at all) compares to some of the other NoSQL vendors, and that means it's hard to hire experts. Hence, redis is a great amateur NoSQL system. And to be clear, it is way better than Access.
      - zaroth 10y ago
        I look at it a bit differently. Would Redis be better today if antirez had raised $10m and hired 50 engineers and then gone out to maximize profit? Certainly that option existed. Personally I doubt the end product really would be that much better, and it would be a tragedy to lose such a great piece of free and open source software.
        tedunangst 10y ago
        >> (which is not a technical comparison at all)
        zaroth 10y ago
        Yes, I saw that. Which is why I responded to discuss the economic aspect -- like other NoSQL startups, should Redis have raised a war-chest and gone out an hired all those experts? I just have a gut feeling that VC funds would endanger the Redis we know and love more than it could actually help it.
- GFK_of_xmaspast 10y ago
  Lots of them run on visual basic too.
antirez 10y ago
Hello jonstewart, That LRU is not that great, is the main argument of the blog post, this is why now Redis contains an eviction policy with LFU elements. Pseudo-LRU in Redis is a compromise between different goals: Redis has many use cases, so there are tensions between different features. The Pseudo-LRU/LFU, augmented with the pool of visited objects, as you can see reading the whole blog post, provide quite good results without forcing Redis to bind the eviction policy to the underlying data structure used to represent the key space, and especially, without using additional memory. All we can do for now is to have 24 bits per object, which is different than a 24-bit overhead per object, as the 24 bits must be stored in the object itself. With the new LFU policy I hope to provide a more quality eviction strategy to Redis compared to the previous one, however note that in practice the sampling LRU + the pool provided acceptable real world performances in many use cases. What I think you don't get, is that providing real-world software that has many features is not like: let's read the Wikipedia page about caching algorithms plus 100 papers, select the best, and implement. System software that works in many use cases and environments is an exercise in compromises, not "pick the best". Otherwise whoever is able to read the latest paper on a topic and implement it would be the winner, which is not the case.
- a-priori 10y ago
  This is probably over-complicated and would cause hard-to-diagnose behaviour, but here's a random idea: use a multi-armed bandit algorithm to pick which eviction policy to use. You'll want to keep a queue of recent evictions. When you get a cache miss, check if the key was recently evicted, and if so, penalize the algorithm that evicted it. Otherwise, if after a period of time you don't get a cache miss, credit the algorithm that evicted it so it's used more often. This way Redis would self-tune its overall eviction policy to the workloads it's presented with. The idea is that, hopefully, you wouldn't have to do as many upfront trade-offs between conflicting use cases.
  - jonstewart 10y ago
    The problem is that then you have K caching algorithms in use, and the memory used by K-1 of them would be better used if given to the winner. The more sophisticated algorithms that use a combination of recency and frequency, like LIRS and ARC, will adapt to most workloads. 2Queues does better than LRU at not letting sequential reads evict frequently accessed data and it's pretty simple to implement, but, in my experience, LIRS seems to evict low probability data faster, letting you use more memory for higher probability data. Regardless, if you have instrumentation, you can do a lot of testing and offline analysis.
rawnlq 10y ago
Thanks for the insight on the cache algorithms. Just wondering, are your implementations of 2Q and LIRS open-sourced? Also I agree that not having more expertise on caching is amateur-ish for maintainers of redis. But as long as they keep up this level of openness and learn from the community calling them out on it, they won't/can't stay amateurs for too long!
- jonstewart 10y ago
  No, they're not open source at this time. It's possible to find some Java ones out there.
bentorfs 10y ago
> The pseudo-LRU redis used to have is appropriate for very high-speed caches (it's essentially a 5-way associative cache), but is so very not appropriate when going out to disk, where the access latency is horrible. Redis is an in-memory database, so what's the problem? Also, keep in mind that it has to fit in 24 bits, so not all solutions are possible, even if they are theoretically better
- onetwotree 10y ago
  It's possible that he refers to a cache miss "going out to disk" by requiring a read from a different data store (a SQL database, for example). But this is really kind of silly - the entire idea with caching is that misses are much slower than hits. The statement is something like "you need a stupid good cache because misses hurt". Software engineering is always about tradeoffs, and antirez does a fantastic job of describing them in this post.
NovaX 10y ago
I also ran an exhaustive analysis and had similar conclusion. I found that TinyLFU (mentioned in the article) matches or beats LIRS in database and search workloads. It is also much simpler to implement and is more memory efficient. https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency The W-TinyLFU variant better handles recency by using an admission window so that new entries are not immediately discard. This resolves antirez's concern and improves performance in sparse burst workloads. In a way its similar to the HIR/LIR regions (window/main) using TinyLFU as a frequency filter. Happy to work with you, antirez, and others to simulate more policies and add trace files.

eternalban 10y ago

> "amateur NoSQL" That was entirely unnecessary and imho open to question given that quite a lot of /businesses/ run on Redis.

jonstewart 10y ago
A lot of businesses also run on MS Access. I think redis is in the great tradition of amateurism, and is about as good as you can get under that approach. It's a lot better than a number of other systems, and it's also somewhat limited.
- zaroth 10y ago
  Redis is no Access, but at least it goes to show that heavily-funded enterprise software is often worse, not better. To me this smacks of academic eliteism. At the scale and density it is used, Redis is by definition not amateurish. Amateur means either unpaid or inept. Describing Redis as inept can only mean you've never used it and are unable to appreciate the incredible diversity of problems for which Redis provides truly excellent reliability, usability, and performance all at once. Antirez succeeded in providing a great measure of all 3 of those traits all at once, and in a code base which is surprisingly easy to read and maintain. To me Redis is in fact a modern marvel. Proof of what a 10x engineer can achieve when left alone to get shit done.
  - jonstewart 10y ago
    I definitely don't mean to suggest that antirez is inept. While redis is technically now a commercial/professional endeavor, I don't think that the commercial side of it (which is not a technical comparison at all) compares to some of the other NoSQL vendors, and that means it's hard to hire experts. Hence, redis is a great amateur NoSQL system. And to be clear, it is way better than Access.
    - zaroth 10y ago
      I look at it a bit differently. Would Redis be better today if antirez had raised $10m and hired 50 engineers and then gone out to maximize profit? Certainly that option existed. Personally I doubt the end product really would be that much better, and it would be a tragedy to lose such a great piece of free and open source software.
      - tedunangst 10y ago
        >> (which is not a technical comparison at all)
        zaroth 10y ago
        Yes, I saw that. Which is why I responded to discuss the economic aspect -- like other NoSQL startups, should Redis have raised a war-chest and gone out an hired all those experts? I just have a gut feeling that VC funds would endanger the Redis we know and love more than it could actually help it.
GFK_of_xmaspast 10y ago
Lots of them run on visual basic too.

antirez 10y ago

Hello jonstewart, That LRU is not that great, is the main argument of the blog post, this is why now Redis contains an eviction policy with LFU elements. Pseudo-LRU in Redis is a compromise between different goals: Redis has many use cases, so there are tensions between different features. The Pseudo-LRU/LFU, augmented with the pool of visited objects, as you can see reading the whole blog post, provide quite good results without forcing Redis to bind the eviction policy to the underlying data structure used to represent the key space, and especially, without using additional memory. All we can do for now is to have 24 bits per object, which is different than a 24-bit overhead per object, as the 24 bits must be stored in the object itself. With the new LFU policy I hope to provide a more quality eviction strategy to Redis compared to the previous one, however note that in practice the sampling LRU + the pool provided acceptable real world performances in many use cases. What I think you don't get, is that providing real-world software that has many features is not like: let's read the Wikipedia page about caching algorithms plus 100 papers, select the best, and implement. System software that works in many use cases and environments is an exercise in compromises, not "pick the best". Otherwise whoever is able to read the latest paper on a topic and implement it would be the winner, which is not the case.

a-priori 10y ago
This is probably over-complicated and would cause hard-to-diagnose behaviour, but here's a random idea: use a multi-armed bandit algorithm to pick which eviction policy to use. You'll want to keep a queue of recent evictions. When you get a cache miss, check if the key was recently evicted, and if so, penalize the algorithm that evicted it. Otherwise, if after a period of time you don't get a cache miss, credit the algorithm that evicted it so it's used more often. This way Redis would self-tune its overall eviction policy to the workloads it's presented with. The idea is that, hopefully, you wouldn't have to do as many upfront trade-offs between conflicting use cases.
- jonstewart 10y ago
  The problem is that then you have K caching algorithms in use, and the memory used by K-1 of them would be better used if given to the winner. The more sophisticated algorithms that use a combination of recency and frequency, like LIRS and ARC, will adapt to most workloads. 2Queues does better than LRU at not letting sequential reads evict frequently accessed data and it's pretty simple to implement, but, in my experience, LIRS seems to evict low probability data faster, letting you use more memory for higher probability data. Regardless, if you have instrumentation, you can do a lot of testing and offline analysis.

rawnlq 10y ago

Thanks for the insight on the cache algorithms. Just wondering, are your implementations of 2Q and LIRS open-sourced? Also I agree that not having more expertise on caching is amateur-ish for maintainers of redis. But as long as they keep up this level of openness and learn from the community calling them out on it, they won't/can't stay amateurs for too long!

jonstewart 10y ago
No, they're not open source at this time. It's possible to find some Java ones out there.

bentorfs 10y ago

> The pseudo-LRU redis used to have is appropriate for very high-speed caches (it's essentially a 5-way associative cache), but is so very not appropriate when going out to disk, where the access latency is horrible. Redis is an in-memory database, so what's the problem? Also, keep in mind that it has to fit in 24 bits, so not all solutions are possible, even if they are theoretically better

onetwotree 10y ago
It's possible that he refers to a cache miss "going out to disk" by requiring a read from a different data store (a SQL database, for example). But this is really kind of silly - the entire idea with caching is that misses are much slower than hits. The statement is something like "you need a stupid good cache because misses hurt". Software engineering is always about tradeoffs, and antirez does a fantastic job of describing them in this post.

NovaX 10y ago

I also ran an exhaustive analysis and had similar conclusion. I found that TinyLFU (mentioned in the article) matches or beats LIRS in database and search workloads. It is also much simpler to implement and is more memory efficient. https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency The W-TinyLFU variant better handles recency by using an admission window so that new entries are not immediately discard. This resolves antirez's concern and improves performance in sparse burst workloads. In a way its similar to the HIR/LIR regions (window/main) using TinyLFU as a frequency filter. Happy to work with you, antirez, and others to simulate more policies and add trace files.