4 ms·

Redis supports LRU and random eviction: https://support.redislabs.com/hc/en-us/articles/203290657-What-eviction-policies-do-you-support- https://support.redisla

by krallja 10y ago

Redis supports LRU and random eviction: https://support.redislabs.com/hc/en-us/articles/203290657-What-eviction-policies-do-you-support- https://support.redislabs.com/hc/en-us/articles/203290657-Wh... I wonder if it would be worth adding a k-random eviction strategy, for a balance between the two.

BillinghamJ 10y ago
Redis's LRU eviction is actually 3-random by default. It does not support true/full LRU. Edit: this is clearer - https://redis.io/topics/lru-cache#approximated-lru-algorithm https://redis.io/topics/lru-cache#approximated-lru-algorithm Excerpt from https://raw.githubusercontent.com/antirez/redis/2.8/redis.conf https://raw.githubusercontent.com/antirez/redis/2.8/redis.co... # 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
- antirez 10y ago
  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.
  - BillinghamJ 10y ago
    Nice! Thanks for the in-depth explanation :)
antirez 10y ago
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.
- danbruc 10y ago
  [...] 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.
  - 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 ago
      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.

by krallja 10y ago

BillinghamJ 10y ago

Redis's LRU eviction is actually 3-random by default. It does not support true/full LRU. Edit: this is clearer - https://redis.io/topics/lru-cache#approximated-lru-algorithm https://redis.io/topics/lru-cache#approximated-lru-algorithm Excerpt from https://raw.githubusercontent.com/antirez/redis/2.8/redis.conf https://raw.githubusercontent.com/antirez/redis/2.8/redis.co... # 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

antirez 10y ago
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.
- BillinghamJ 10y ago
  Nice! Thanks for the in-depth explanation :)

antirez 10y ago

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.

danbruc 10y ago
[...] 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.
- 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 ago
    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.