Hello, now Redis (4.0, still in release candidate) supports LFU (Least Frequently Used) which should work better in most cases since LRU also is also just a way to approximate LFU, since the most frequently used items are often the last recently used ones.
[...] since LRU also is also just a way to approximate LFU, since the most frequently used items are often the last recently used ones.
That is not really true. LRU and LFU favor different items, LRU ones used frequently in the short term, LFU ones used frequently in the long term. Only under special circumstances does one approximate the other, for example if your cache is large enough that LRU does not evict the most frequently used items when many less frequently used items are placed in the cache before the most frequently used items are accessed again, then LRU approximates LFU.
What I mean is that, the most frequently used objects, if accessed roughly with an even period of time, tend to be also the least frequently used objects, so if the accesses are very even LFU and LRU tend to be similar. For uneven access patterns, they are different, but usually LRU is used because access patterns are even so that it approximates LFU, since what we want to have in cache is, without other application-specific clues, the objects that we use more often. Knowing exactly the access pattern one can use an application-assisted strategy which is optimal, but without clues LRU adapts well to different scenarios while LRU may fail in a catastrophic fashion.
Also note that your idea of LFU (in this context), from what you write, is perhaps one that does not adapt over time. Redis LFU employs a decay strategy so that the recent frequency is computed, not the whole-lifetime frequency of access, so even short lived items accessed very frequently for some time, will do well and will not get easily evicted.
That is what I meant, under specific assumptions about the access pattern they can show similar behavior. Classical LFU tracking the absolute frequency of items will keep items that are used frequently in absolute terms but infrequently in terms of the instantaneous frequency in the cache while LRU will evict such items in favor of items with high instantaneous frequency. Those two algorithms are in some sense two extremes, LRU cares about what is most frequently used right now, LFU cares about what is most frequently used over the entire lifetime of the cache.
The LFU variant you describe in the linked article is somewhere in the middle, it tracks the absolute frequency of access just like classical LRU but then it also decays this frequency and therefore turns it into something like a weighted and averaged relative frequency. But it is, at least for me, hard to tell what exactly the algorithm tracks, how the accesses are wighted over time and therefore were exactly this falls on the spectrum between LRU and classical LFU.
Algorithms like ARC and CAR also try to strike a balance between LRU and LFU with the difference that they adaptively control where on the spectrum to operate.
Yes, there is a tuning problem indeed. I made two parameters user-tunable (the decay and the logarithm factor of the Morris counter), but tuning needs some expertise. I've severe limitations on the number of bits I can use per object, but depending on the user feedbacks I may try some auto-adaptive approach as well in the future.
I used hill climbing to tune TinyLFU. A larger admission window improves recency-biased workloads, while a smaller improves for frequency. By sampling the hit rate and making an initial adjustment, it can determine when to change directions and hone in on the best configuration. Other than a small warm-up penalty, it quickly optimizes itself.
# LRU and minimal TTL algorithms are not precise algorithms but approximated
# algorithms (in order to save memory), so you can select as well the sample
# size to check. For instance for default Redis will check three keys and
# pick the one that was used less recently, you can change the sample size
# using the following configuration directive.
#
# maxmemory-samples 3
Redis does a much better thing in recent versions: it uses a few samples per iteration, but instead of discarding the accumulated data, it takes a pool of good candidates to re-check in the next iteration, so the approximation to LRU is very close compared to vanilla "among 3" algorithms. Moreover since the performance was improved, now the default is to look at 5 items making the algorithm better. More than the precision of LRU itself, I'm more intrigued with the potential improvements that LFU (Redis >= 4.0) can provide, but being 4.0 just in RC state, most users are currently just using LRU.
I wonder if it would be worth adding a k-random eviction strategy, for a balance between the two.