Redis：代码实战之淘汰策略_如何模拟一个redis noeviction 淘汰策略

【关于作者】

关于作者，目前在蚂蚁金服搬砖任职，在支付宝营销投放领域工作了多年，目前在专注于内存数据库相关的应用学习，如果你有任何技术交流或大厂内推及面试咨询，都可以从我的个人博客（https://0522-isniceday.top/）联系我

redis作为旁路缓存时，不可能将所有的数据都存储在缓存中，并且数据存储具有“二八原则”，即80%的请求只会请求20%的数据，那么缓存的淘汰机制就必不可少

淘汰之前，我们得先了解设置容量的依据和方法

1.容量设置多大？

我会建议把缓存容量设置为总数据量的15%到30%，兼顾访问性能和内存空间开销。

redis如何设置：

对于Redis来说，一旦确定了缓存最大容量，比如4GB，你就可以使用下面这个命令来设定缓存的大小了：

CONFIG SET maxmemory 4gb
1

2.Redis缓存的淘汰策略

Redis 4.0之前一共实现了六中淘汰策略，4.0之后又新增了两种（allkeys-lfu、volatile-lfu），按照是否会数据淘汰分成了两类：

• 不进行数据淘汰的策略，只有noeviction这一种（默认策略）。
• 会进行淘汰的7种其他策略。

八种淘汰策略如下图：

• noeviction策略：缓存被写满时，再有写请求是这时redis不再提供服务，而是直接返回错误

无论是键值快要过期还是Redis的使用量达到了maxmemory阈值，都会触发redis进行数据淘汰

如下策略淘汰范围局限在设置了过期时间的键值对

• volatile-ttl：筛选时，按照过期时间的先后删除，越先越先删除
• volatile-random：在设置了过期的键值对中，随机进行删除
• volatile-lru：使用LRU算法筛选设置了过期时间的键值对
• volatile-lfu：使用LFU算法选择设置了过期时间的键值对

如下淘汰策略扩大到了所有键值对，无论这些键值对是否设置了过期时间

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

2.1.LRU算法

LRU(Least Recently Used)：最近最少原则

LRU会将数据组织成一个列表，两端分别为MRU端（最常被访问的数据），LRU端（最不常被访问的数据），当链表中元素被访问则置于MRU端。当元素满了需要淘汰的时候，就从LRU端开始淘汰

但是Redis使用链表的方式存在的缺陷就是，链表缓存所有的数据会带来额外开销，并且并发访问的时候会带来链表许多的移动操作，影响redis的性能

Redis中LRU的使用：

• redis会给每个记录加一个时间戳（键值对数据结构RedisObject中的lru字段记录），记录最近访问的时间。淘汰的时候会随机选出N（maxmemory-samples可配置）个数据，将其作为一个候选集合。接下来会比较N个数据的lru字段，把lru字段最小的数据淘汰出去。

• 再次淘汰时，再挑选数据入上一批的候选集合，补齐到N个数据，但是这里的挑选标注要求lru字段要小于目前集合中的lru最小值

  ，其中候选集合就是一个链表结构，但是redis无需用链表维护所有的键值对，只需维护候选集合。

2.2.LFU算法

redis在实现LFU策略的基础上，把原来24bit大小的lru字段，拆成了两部分

• ldt值：lru字段的前16bit，表示数据的访问时间戳（进度变为分钟级别，可能会产生一份内key的误差）
• counter值：lru字段的后8bit，表示数据的访问次数

对于counter值的计算：

由于counter只占用了8bit，最大只能表示255，明显过小，因此redis对于counter值的增长和减少有一套自己的计算方式：

LFU的计数器规则：p =（用计数器当前值 * 配置项lfu_log_factor ）+1 取倒数，再将p值与0~1之间的随机数r匹配，大于r计数器加一

计数器的初始默认值是5，防止刚写入缓存就被淘汰

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

使用了这种计算规则后，我们可以通过设置不同的lfu_log_factor配置项，来控制计数器值增加的速度，避免counter值很快就到255了。

redis官网提供，当lfu_log_factor取不同值时，在不同的实际访问次数情况下，计数器的值是如何变化：

当lfu_log_factor取值等于10时，不同访问量下的counter值就已经能够得到很好的区分，因此可以设置为10

为了避免短时间内大量访问但是后续有不再访问的缓存存在，LFU也针对计数器的衰减规则

LFU衰减规则：使用配置项lfu_decay_time作为衰减因子，LFU会计算当前时间和数据最近的一次访问时间的差值（单位：分钟），并拿当前差值 / 衰减因子lfu_decay_time，lfu_decay_time设置越大，衰减的越缓慢，数据淘汰的越慢

2.2.选择策略的建议

• 优先使用allkeys-lru策略：利用LRU的优势，将最常使用的数据存储在缓存中，如果数据有冷热的区分，则可以采取该策略。如果没有明显的冷热数据区分，采取allkeys-random即可
• 业务有置顶的需求，可使用volatile-lru，置顶数据不设置过期时间，则可以一直保留
• LRU策略更加关注数据的失效性，LFU更关注数据的访问频次。实际应用的负载具有较好的时间局部性，所以LRU策略的应用会更加广泛。但是，在扫描式查询的应用场景中，LFU策略就可以很好地应对缓存污染问题了，建议你优先使用

2.3.淘汰的数据如何处理

当数据被淘汰时候，脏数据写回数据库，干净数据直接删除即可。

脏数据：相较于数据库，被修改过的，如果不写回数据库则会导致数据丢失

干净数据：相较于数据库未被修改过，因此可以直接删除

但是redis的数据淘汰并不会回写数据库，因此只能够在代码中数据被修改时就写回数据库