7 ms·

Random notes on improving the Redis LRU algorithm

74 points by dwaxe 10y ago

coldcode 10y ago
I love reading the antirez blog, he has such great analysis you rarely get to read.
rawnlq 10y ago
I wonder if he looked at Adaptive Replacement Cache[1]? It's supposedly the best of both worlds of least recently and least frequently used and the only reason people don't use it more is because of IBM's patent. [1] https://en.wikipedia.org/wiki/Adaptive_replacement_cache https://en.wikipedia.org/wiki/Adaptive_replacement_cache
- tedunangst 10y ago
  With random sampling?
jonstewart 10y ago
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.
squeaky-clean 10y ago
That logarithmic counter trick is awesome. It's obviously not something you'd implement everywhere, but it's seems really elegant here. I've never really thought of treating memory that way, it blew my mind a little.
onetwotree 10y ago
Great post. Antirez delivers once again! I think this is an excellent read for anyone who wants to gain some insight into coming up with pragmatic, real world solutions to problems (caching) that are usually taught in a very formal, "use this bestest algorithm or you're a dummy" kind of way. Also the tricks used here are beyond clever.

74 points by dwaxe 10y ago

I love reading the antirez blog, he has such great analysis you rarely get to read.

I wonder if he looked at Adaptive Replacement Cache[1]? It's supposedly the best of both worlds of least recently and least frequently used and the only reason people don't use it more is because of IBM's patent. [1] https://en.wikipedia.org/wiki/Adaptive_replacement_cache https://en.wikipedia.org/wiki/Adaptive_replacement_cache

tedunangst 10y ago
With random sampling?

jonstewart 10y ago

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.

squeaky-clean 10y ago

That logarithmic counter trick is awesome. It's obviously not something you'd implement everywhere, but it's seems really elegant here. I've never really thought of treating memory that way, it blew my mind a little.

onetwotree 10y ago

Great post. Antirez delivers once again! I think this is an excellent read for anyone who wants to gain some insight into coming up with pragmatic, real world solutions to problems (caching) that are usually taught in a very formal, "use this bestest algorithm or you're a dummy" kind of way. Also the tricks used here are beyond clever.