Hello Jon, adding an additional data structure has the problem of slowing down the ability to serve queries, and there is a memory overhead problem as well. A lot of time spent when modifying the eviction policy is to make sure there are on speed regressions. Moreover in Redis you can switch on and off the "maxmemory" setting and change eviction policy at runtime: when it's off no resources should be needed, when it is turned on, no pause should happen. So it is very hard to find both the time and space resources in order to implement the perfect solution. However the blog post in its latter part describes the LFU implementation that is now into Redis (unstable branch). This implementation was derived with just a few days of work, I had only that much to work at the problem, but was obtained writing a few simulation programs and traces in order to check the behavior, so I don't think it's an "obvious loser". For instance I can imagine different workloads where it can work better compared to LIRS. For example when you get accesses in "spaced bursts", LIRS, by remembering only the last two access times, may get confused about what data is really worthwhile to take. In teams like your where you have a specific problem to address, and you can test N approaches, you can select a specific algorithm that works the best for you, but in Redis it would be a lot better if there is a more adaptive approach. Intuitively, and by the traces I was able to run on it, it looks like that a logarithmic counter and the halving timer while not always optimal should be able to provide decent performances under different access loads, since in some way, it really is an LFU algorithm (in that the frequency of accesses is retained by the algorithm in a direct way, instead of being guessed by secondary data), so it should not be trivially fooled by odd access patterns. Also being it tunable in the two main parameters, it should be possible for users to improve it for application specific loads. I understand your frustration with LRU implementations, but given you care and have experience on this stuff, I invite you to take a look at the performances of the new Redis algorithm, maybe after all it could work better than expected, or you could be able to do trivial changes to it in order to significantly improve how it works, so that all we could benefit. Regards.

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.

The "ideal approach" to caching, Jon, is an oracle. There is no such thing as an "ideal cache eviction algorithm", just FYI.

Also known as Bélády's algorithm.

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

The last sentence I meant more generally than the domain of cache algorithms, setting up "ideal" as a contrast to "pragmatic", since I'm taking flak for being "academic" (haha, you should have seen my grades). One lesson I've learned in my career is that there are instances where it pays to take some time, see what the research says, experiment, and then refactor. It takes a lot of time, but the best software is also long-lived so it can pay to take the time to make one's software the best. antirez has 24 bits to play with and doesn't want to make major changes, probably also doesn't have a lot of spare time, and that's his choice.

But I am also aware of the oracle algorithm.

You still don't understand what Redis is and what antirez wrote in first reply to you. Your "major changes" will have impact on my use cases. Redis is not only used for caching, I am not using Redis in production for caching and many other people also do not use Redis for caching.

> setting up "ideal" as a contrast to "pragmatic"

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.