Redis缓存淘汰策略

时间:2021-7-3 作者:qvyue

本文作为学习笔记,文章内容来自“极客时间”专栏《Redis核心技术与实战》,如有侵权,请告知,必即时删除。

1、淘汰策略

为了保证较高的性价比,缓存的空间容量必然要小于后端数据库的数据总量。不过,内存大小毕竟有限,随着要缓存的数据量越来越大,有限的缓存空间不可避免地会被写满。解决这个问题就涉及到缓存系统的一个重要机制,即缓存数据的淘汰机制。简单来说,数据淘汰机制包括两步:

  1. 根据一定的策略,筛选出对应用访问来说“不重要”的数据;
  2. 将这些数据从缓存中删除,为新来的数据腾出空间,

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

  • 不进行数据淘汰的策略,只有 noeviction 这一种。
  • 会进行淘汰的 7 种其他策略。

会进行淘汰的 7 种策略,我们可以再进一步根据淘汰候选数据集的范围把它们分成两类:

  • 在设置了过期时间的数据中进行淘汰,包括 volatile-random、volatile-ttl、volatile-lru、volatile-lfu(Redis 4.0 后新增)四种。
  • 在所有数据范围内进行淘汰,包括 allkeys-lru、allkeys-random、allkeys-lfu(Redis 4.0 后新增)三种。

    Redis缓存淘汰策略
    25.jpg

默认情况下,Redis 在使用的内存空间超过 maxmemory 值时,并不会淘汰数据,也就是设定的 noeviction 策略。对应到 Redis 缓存,也就是指,一旦缓存被写满了,再有写请求来时,Redis 不再提供服务,而是直接返回错误。

volatile-random、volatile-ttl、volatile-lru 和 volatile-lfu 这四种淘汰策略。它们筛选的候选数据范围,被限制在已经设置了过期时间的键值对上。也正因为此,即使缓存没有写满,这些数据如果过期了,也会被删除。

  • volatile-ttl 在筛选时,会针对设置了过期时间的键值对,根据过期时间的先后进行删除,越早过期的越先被删除。
  • volatile-random 就像它的名称一样,在设置了过期时间的键值对中,进行随机删除。
  • volatile-lru 会使用 LRU 算法筛选设置了过期时间的键值对。
  • volatile-lfu 会使用 LFU 算法选择设置了过期时间的键值对。

allkeys-lru、allkeys-random、allkeys-lfu 这三种淘汰策略的备选淘汰数据范围,就扩大到了所有键值对,无论这些键值对是否设置了过期时间。它们筛选数据进行淘汰的规则是:

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

ttl和random算法比较容易理解,就不多说了,下面重点说下Redis中的LRU和LFU算法

配置Redis的淘汰策略,redis.conf:

#设置Redis 内存大小的限制,我们可以设置maxmemory ,当数据达到限定大小后,会选择配置的策略淘汰数据
maxmemory 300mb

#设置Redis的淘汰策略。
maxmemory-policy volatile-lru

2、Redis中的LRU算法

在 Redis 中,LRU 算法被做了简化,以减轻数据淘汰对缓存性能的影响。具体来说,Redis 默认会记录每个数据的最近一次访问的时间戳(由键值对数据结构 RedisObject 中的 lru 字段记录)。然后,Redis 在决定淘汰的数据时,第一次会随机选出 N 个数据,把它们作为一个候选集合。接下来,Redis 会比较这 N 个数据的 lru 字段,把 lru 字段值最小的数据从缓存中淘汰出去。

Redis 提供了一个配置参数 maxmemory-samples,这个参数就是 Redis 选出的数据个数 N。例如,我们执行如下命令,可以让 Redis 选出 100 个数据作为候选数据集:

CONFIG SET maxmemory-samples 100

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

这样一来,Redis 缓存不用为所有的数据维护一个大链表,也不用在每次数据访问时都移动链表项,提升了缓存的性能。

LRU算法有一个问题就是,当应用对大量的数据进行一次全体读取,每个数据都会被读取,而且只会被读取一次。此时,因为这些被查询的数据刚刚被访问过,所以 lru 字段值都很大。而其他的热点数据就会被淘汰掉。

3、Redis中的LFU算法

Redis 从 4.0 版本开始增加了 LFU 淘汰策略。与 LRU 策略相比,LFU 策略中会从两个维度来筛选并淘汰数据:

  • 数据访问的时效性(访问时间离当前时间的远近);
  • 数据的被访问次数。

LFU 缓存策略是在 LRU 策略基础上,为每个数据增加了一个计数器,来统计这个数据的访问次数。当使用 LFU 策略筛选淘汰数据时,首先会根据数据的访问次数进行筛选,把访问次数最低的数据淘汰出缓存。如果两个数据的访问次数相同,LFU 策略再比较这两个数据的访问时效性,把距离上一次访问时间更久的数据淘汰出缓存。

应用对大量的数据进行一次全体读取,因为这些数据不会被再次访问,所以它们的访问次数不会再增加。因此,LFU 策略会优先把这些访问次数低的数据淘汰出缓存。就解决了上面提到的LRU存在的问题。

Redis 在实现 LFU 策略的时候,只是把原来 24bit 大小的 lru 字段,又进一步拆分成了两部分。

  1. ldt 值:lru 字段的前 16bit,表示数据的访问时间戳;
  2. counter 值:lru 字段的后 8bit,表示数据的访问次数。

总结一下:当 LFU 策略筛选数据时,Redis 会在候选集合中,根据数据 lru 字段的后 8bit 选择访问次数最少的数据进行淘汰。当访问次数相同时,再根据 lru 字段的前 16bit 值大小,选择访问时间最久远的数据进行淘汰。

但是8个bit只能表示0到255,对于Redis来说,肯定是不够用的。因此,在实现 LFU 策略时,Redis 并没有采用数据每被访问一次,就给对应的 counter 值加 1 的计数规则,而是采用了一个更优化的计数规则。

下面这段 Redis 的部分源码,显示了 LFU 策略增加计数器值的计算逻辑。其中,baseval 是计数器当前的值。计数器的初始值默认是 5(由代码中的 LFU_INIT_VAL 常量设置),而不是 0,这样可以避免数据刚被写入缓存,就因为访问次数少而被立即淘汰。

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

使用了这种计算规则后,我们可以通过设置不同的 lfu_log_factor 配置项,来控制计数器值增加的速度,避免 counter 值很快就到 255 了。为了更进一步说明 LFU 策略计数器递增的效果,你可以看下下面这张表。这是 Redis官网上提供的一张表,它记录了当 lfu_log_factor 取不同值时,在不同的实际访问次数情况下,计数器的值是如何变化的。

Redis缓存淘汰策略
26.jpg

可以看到,当 lfu_log_factor 取值为 1 时,实际访问次数为 100K 后,counter 值就达到 255 了,无法再区分实际访问次数更多的数据了。而当 lfu_log_factor 取值为 100 时,当实际访问次数为 10M 时,counter 值才达到 255,此时,实际访问次数小于 10M 的不同数据都可以通过 counter 值区分出来。正是因为使用了非线性递增的计数器方法,即使缓存数据的访问次数成千上万,LFU 策略也可以有效地区分不同的访问次数,从而进行合理的数据筛选。

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

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

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。