Random notes on improving the Redis LRU algorithm
antirez.com
antirez.com
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
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.
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.
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
EDIT: p.s. if somebody is inclined to test it, in 24 bits, I'm sure it's possible to implement some kind of LIRS approximation easily, by using two 12 bits timestamps. The problem with a 12 bit timestamp is that all objects having more than 1 hours are ranked the same, but in the case of a cache like Redis, it could be acceptable perhaps... Anyway to try different approaches in the unstable branch is just as hard as writing a few lines of code AFAIK.
Let's see the code. I checked your github repo and can't find this "implementation".
But I am also aware of the oracle algorithm.
Have to retract the last comment['s promise of final note] and (academically) note here that "ideal" and "optimal" are distinct notions in computer science.
A provably "optimal" algorithm is implementable. An "ideal" that requires magical facilities is a trope to make a point and spare one from attempting the impossible.
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.
Regardless, if you have instrumentation, you can do a lot of testing and offline analysis.
That was entirely unnecessary and imho open to question given that quite a lot of /businesses/ run on Redis.
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.
And to be clear, it is way better than Access.
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.
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
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.
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!
[1] https://en.wikipedia.org/wiki/Adaptive_replacement_cache
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.