3 ms·

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

by 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.
jonstewart 10y ago
Hello antirez, Indeed, I think the pseudo-LRU approach as you describe, especially when combined with a pool, is a pragmatic caching solution for when you don't want to make major changes to your codebase. You found 24 bits, you dedicated a small data structure off to the side, and those two in combination are a really good approximation of LRU, without a lot of code. I'm obviously not as familiar with the guts of redis's implementation as you are, so I don't know all the ways that keys can be stored and what the implications for caching are. Generally a caching data structure can be used that references the cached data/objects (pointers, basically), so it could be external to how you otherwise store data. That may not be the right approach with a low-level C/C++ block caching server, but that's not what redis is, either. I think you would find that adding a separate data structure would help you out, but that's just naïve advice; I don't know the guts of redis so perhaps you can't store keys in a separate structure. I also well understand that providing real-world software is an exercise in compromises. However, I recently discovered how horrible an existing LRU implementation performed in practice for my application (digital forensics) and spent considerable resources exploring alternatives. And what we really found out during all of this is that instrumentation and testing under a diverse set of input is necessary in order to make an informed decision. For some input, LRU was gangbusters. For others, it was lousy. I've also learned that sometimes it's necessary to put pragmatism aside and go off and implement the ideal approach; it can pay off. Cheers, Jon
- eternalban 10y ago
  The "ideal approach" to caching, Jon, is an oracle. There is no such thing as an "ideal cache eviction algorithm", just FYI.
  - jonstewart 10y ago
    Also known as Bélády's algorithm.
    - eternalban 10y ago
      This is my final note (and I am not downvoting you, fyi) but you said "implement the ideal approach". Magic? Let's see the code. I checked your github repo and can't find this "implementation".

by antirez 10y ago

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.

jonstewart 10y ago

Hello antirez, Indeed, I think the pseudo-LRU approach as you describe, especially when combined with a pool, is a pragmatic caching solution for when you don't want to make major changes to your codebase. You found 24 bits, you dedicated a small data structure off to the side, and those two in combination are a really good approximation of LRU, without a lot of code. I'm obviously not as familiar with the guts of redis's implementation as you are, so I don't know all the ways that keys can be stored and what the implications for caching are. Generally a caching data structure can be used that references the cached data/objects (pointers, basically), so it could be external to how you otherwise store data. That may not be the right approach with a low-level C/C++ block caching server, but that's not what redis is, either. I think you would find that adding a separate data structure would help you out, but that's just naïve advice; I don't know the guts of redis so perhaps you can't store keys in a separate structure. I also well understand that providing real-world software is an exercise in compromises. However, I recently discovered how horrible an existing LRU implementation performed in practice for my application (digital forensics) and spent considerable resources exploring alternatives. And what we really found out during all of this is that instrumentation and testing under a diverse set of input is necessary in order to make an informed decision. For some input, LRU was gangbusters. For others, it was lousy. I've also learned that sometimes it's necessary to put pragmatism aside and go off and implement the ideal approach; it can pay off. Cheers, Jon

eternalban 10y ago
The "ideal approach" to caching, Jon, is an oracle. There is no such thing as an "ideal cache eviction algorithm", just FYI.
- jonstewart 10y ago
  Also known as Bélády's algorithm.
  - eternalban 10y ago
    This is my final note (and I am not downvoting you, fyi) but you said "implement the ideal approach". Magic? Let's see the code. I checked your github repo and can't find this "implementation".