缓存淘汰策略

前言

Redis 4.0 之前一共实现了 6 种内存淘汰策略，在 4.0 之后，又增加了 2 种策略。可以按照是否会进行数据淘汰把它们分成两类：

1. 不进行数据淘汰的策略，只有 noeviction 这一种。
2. 会进行淘汰的 7 种其他策略。

在默认情况下（在redis3.0之前，默认是volatile-lru，在redis3.0之后（包括3.0），默认淘汰策略则是noeviction，当内存超过maxmemory 值时并不会淘汰数据，因为默认是noeviction 策略。内存被写满再有写的请求会直接报错。

淘汰策越分为两种。设置了过期时间的数据中进行淘汰和在所有数据范围内进行淘汰。

淘汰策略

1. volatile-ttl 在筛选时，会针对设置了过期时间的键值对，根据过期时间的先后进行删除，越早过期的越先被删除。
2. volatile-random 在设置了过期时间的键值对中，进行随机删除。
3. volatile-lru 使用 LRU 算法筛选设置了过期时间的键值对。
4. volatile-lfu 使用 LFU 算法选择设置了过期时间的键值对。

redis4.0 之后新增的三种淘汰策略

1. allkeys-random 策略，从所有键值对中随机选择并删除数据。
2. allkeys-lru 策略，使用 LRU 算法在所有数据中进行筛选。
3. allkeys-lfu 策略，使用 LFU 算法在所有数据中进行筛选。

LRU

LRU 算法的全称是 Least Recently Used，按照最近最少使用的原则来筛选数据，最不常用的数据会被筛选出来，而最近频繁使用的数据会留在缓存中。

LRU 会把所有的数据组织成一个链表，链表的头和尾分别表示 MRU 端和 LRU 端，分别代表最近最常使用的数据和最近最不常用的数据。

有数据 6、3、9、20、5。如果数据 20 和 3 被先后访问，它们都会从现有的链表位置移到 MRU 端，而链表中在它们之前的数据则相应地往后移一位。因为，LRU 算法选择删除数据时，都是从 LRU 端开始，所以把刚刚被访问的数据移到 MRU 端，就可以让它们尽可能地留在缓存中。

新数据 15 要被写入缓存，数据 15 是刚被访问的，所以它会被放到 MRU 端，算法把 LRU 端的数据 5 从缓存中删除，相应的链表中就没有数据 5 的记录了。

LRU在实际使用中需要链表来管理所有的缓存数据，会有额外的性能消耗，且Redis如果被访问的频繁就带来很多链表移动操作，会很耗时，进而会降低 Redis 缓存性能。

但是在 redis 中 LRU 算法被做了优化。Redis 的键值对数据结构 RedisObject 有一个 lru 字段，它里面记录了当前 key 最后一次访问时间，在 Redis 淘汰数据时，会先随机选取 N 个 key 作为一个候选集合，Redis 会比较这 N 个 key 的 lru 字段，把 lru 字段值最小的数据从缓存中淘汰出去。

Redis 提供了一个配置参数 maxmemory-samples，这个参数就是 Redis 选出的数据个数 N。

CONFIG SET maxmemory-samples 100

当需要再次淘汰数据时，Redis 需要挑选 key 进入第一次淘汰时创建的候选集合。挑选标准是，能进入候选集合的key 的 lru 字段值必须小于候选集合中最小的 lru 值。当有新数据进入候选数据集后，如果候选数据集中的数据个数达到了 maxmemory-samples，Redis 就把候选数据集中 lru 字段值最小的数据淘汰出去

LFU

LFU 缓存策略是在 LRU 策略基础上，为每个数据增加了一个计数器，来统计这个数据的访问次数。

当使用 LFU 策略筛选淘汰数据时，首先会根据数据的访问次数进行筛选，把访问次数最低的数据淘汰出缓存。如果两个数据的访问次数相同，LFU 策略再比较这两个数据的访问时效性，把距离上一次访问时间更久的数据淘汰出缓存。

RedisObject lru 占 24bit 前 16 位用来记录最后访问时间戳，后 4 位用来记录访问次数。但是如果每次访问都 +1 的话空间是肯定不够的。

所以 Redis 并没有采用数据每被访问一次，就给对应的 counter 值加 1 的计数规则，而是采用了一个更优化的计数规则。每当数据被访问一次时，首先，用计数器当前的值乘以配置项 lfu_log_factor 再加 1，再取其倒数，得到一个 p 值；然后，把这个 p 值和一个取值范围在（0，1）间的随机数 r 值比大小，只有 p 值大于 r 值时，计数器才加

double r = (double)rand()/RAND_MAX;
...
double p = 1.0/(baseval*server.lfu_log_factor+1);
if (r < p) counter++;   

当 lfu_log_factor 取值为 1 时，实际访问次数为 100K 后，counter 值就达到 255 了，无法再区分实际访问次数更多的数据了。而当 lfu_log_factor 取值为 100 时，当实际访问次数为 10M 时，counter 值才达到 255，此时，实际访问次数小于 10M 的不同数据都可以通过 counter 值区分出来。一般可以将 lfu_log_factor 取值为 10。

LFU 策略使用衰减因子配置项 lfu_decay_time 来控制访问次数的衰减。LFU 策略会计算当前时间和数据最近一次访问时间的差值，并把这个差值换算成以分钟为单位。然后，LFU 策略再把这个差值除以 lfu_decay_time 值，所得的结果就是数据 counter 要衰减的值。

假设 lfu_decay_time 取值为 1，如果数据在 N 分钟内没有被访问，那么它的访问次数就要减 N。如果 lfu_decay_time 取值更大，那么相应的衰减值会变小，衰减效果也会减弱。所以，如果业务应用中有短时高频访问的数据的话，建议把 lfu_decay_time 值设置为 1，这样一来，LFU 策略在它们不再被访问后，会较快地衰减它们的访问次数，尽早把它们从缓存中淘汰出去，避免缓存污染。

总结

生产建议根据业务的需求来配置 Redis 的缓存淘汰策略，譬如:

1. 业务应用中的数据访问频率相差不大，没有明显的冷热数据区分，建议使用 allkeys-random 策略，随机选择淘汰的数据。
2. 业务中有置顶的需求，比如置顶新闻、置顶视频，那么，可以使用 volatile-lru/volatile-lfu 策略，同时不给这些置顶数据设置过期时间。这样一来，这些需要置顶的数据一直不会被删除，而其他数据会在过期时根据 LRU/LFU 规则进行筛选。
3. 一般情况下可以使用 allkeys-lru/allkeys-lfu 来淘汰。