4 ms·
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
by antirez 10y ago
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.
Full story: http://antirez.com/news/109 http://antirez.com/news/109
- danbruc 10y agoThat 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.
- antirez 10y agoYes, 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.
- NovaX 10y agoI 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.