侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

Redis 过期删除策略(三):通过 LRU 淘汰算法删除过期键

kaixindeken
2021-04-28 / 0 评论 / 0 点赞 / 102 阅读 / 3,568 字

引子

当 Redis 占用内存超过 redis.conf 配置文件中配置的内存上限,就会通过与之关联的淘汰策略清理 Redis 键。

与前两者策略不同的是,Redis 默认并没有配置内存上限,这种情况下,Redis 会一直占用内存资源直到耗尽所在机器的物理内存,进而触发内存与磁盘的交换(swap),我们知道磁盘 IO 的性能是极差的,这就会导致 Redis 性能急剧下降,所以在生产环境,强烈建议配置内存使用上限。

这样一来,当 Redis 占用内存触发内存上限,就会通过配置的淘汰策略清理 Redis 键,默认的淘汰策略是 noeviction,即可用内存不足以存放新写入数据时,新写入操作会报错,这不是我们所期望的行为,理想的状况是触发内存上限后,Redis 可以清理掉那些过期的,或者即将过期的,以及最近较少使用的键(冷数据),释放出宝贵的内存空间。

LRU 算法的基本实现

LRU 的全称是 Least Recently Used,中文译作最近最少使用,因此这个淘汰算法会淘汰最近最少使用的键。

关于 LRU 算法的基本实现我们在 MySQL 底层 Buffer Pool 缓存页刷新算法 中已经介绍过,只需要维护一个 LRU 链表即可:将最新访问的键放到链表头部,如果键已经位于链表,则将其移到链表头部,这样一来,一段时间后,最不常访问的键就会下沉到链表尾部,我们在清理元素时,只需要将链表尾部对应的键值从 Redis 中移除即可。

如果使用这样的常规 LRU 算法,维护这个 LRU 链表需要消耗大量的内存,这对寸土寸金的 Redis 来说有点奢侈,因此,Redis 底层采用的是一种近似 LRU 算法。

近似 LRU 算法

Redis 的近似 LRU 算法实现也很简单,就是不开辟额外的链表空间,而是在现有数据结构的基础上使用随机采样法来淘汰元素,为了实现这个近似 LRU 算法,Redis 为每个键维护了额外的小字段(24 bit),这个字段存储的是该键最后一次被访问的时间戳。

当 Redis 内存超过配置文件配置的内存上限后,如果配置的淘汰策略是基于 LRU 算法的(xxx-lru),就会执行一次近似 LRU 淘汰算法,这个算法的实现非常简单,就是随机获取 5 个键(可以通过 maxmemory-samples 配置项配置),然后淘汰掉上次访问时间距现在最长(即最近最不常使用)的键,如果淘汰后 Redis 内存还是超出内存上限,则再执行一次,以此类推,直到 Redis 内存小于内存上限。

4.0 版本优化后的近似 LRU 算法

如果你对比过 MySQL LRU 过期淘汰算法的实现和改良,很容易看到 Redis 的近似 LRU 算法也存在同样的问题,就是某个冷数据最近偶尔被访问了一次,但是按照现有策略却可能被保留下来,而将访问频率更高的热数据淘汰掉,这是不合理的。

为了优化这个问题,Redis 4.0 引入了基于 LFU 模式的 LRU 算法。

LFU 的全称是 Least Frequently Used,中文译作最近访问频率最低,相比上述近似 LRU 算法只是通过上次访问时间这个单一维度表示键的访问热度,LFU 模式可以更加精确地表示一个键的访问热度:它会追踪 Redis 键最近一段时间的访问频率,如果某个键只是偶然被访问一次是不足以被认为是热数据的,它需要在近期一段时间内被多次访问才有机会被认为是热数据。

有没有觉得这个优化思路和 MySQL 很像,其实,编程领域的基本算法和数据结构就那些,大家都是相互借鉴而已,和你参考别人思路编写业务代码本质上并没有什么不同。

为了实现全新的 LRU 算法,Redis 为每个键值对对象结构设置了一个 lru 字段:

typedef struct redisObject {
    unsigned type:4;  // 对象类型,string、list、set、hash 等
    unsigned encoding:4;  // 对象编码,ziplist、skiplist、intset、hashtable 等
    unsigned lru:LRU_BITS; // 存放 LRU 时间或者 LFU 数据
    int refcount;  // 引用计数
    void *ptr;     // 对象指针
} robj;

这个长度为 24 bit 的字段中存放了 LRU 时间或者 LFU 数据:

  • 在 LRU 模式下,存放的是 LRU 时钟,即该对象上次访问时间;
  • 在 LFU 模式下,低 8 位存放的是该对象的访问频次统计,高 16 位存放的也是时钟,但不是该对象上次访问时间。

下面我们具体看下新的 LRU 算法的底层实现。

LRU 模式

LRU 模式下,lru 存放的是 server.lruclock 时钟值,当某个键被访问一次,它的对象头的 lru 字段值就会被更新为当前的 server.lruclock,这是一个 24 bit 的整数,对应的值是 Unix 时间戳对 2^24 取模的结果。

默认 Redis 时钟值通过定时任务每毫秒更新一次,如果 server.lruclock 没有折返(取模操作迟早会折返),它就是一直递增的,这意味着 lru 字段值不会超过 server.lruclock 的值;如果超过了,说明 server.lruclock 折返了:

1.jpeg

通过这个逻辑就可以计算出 Redis 对象多长时间没有被访问,即对象的空闲时间,有了空闲时间,就可以通过比较不同 Redis 对象谁最近最少被访问,基于 LRU 模式的近似 LRU 算法就是以此为据来决定谁该被淘汰了(空闲时间越长,最近越少被访问)。

Redis 支持的基于 LRU 模式的 LRU 淘汰策略分别是 allkeys-lru 和 volatile-lru,前者不管该键是否有过期时间一视同仁,后者是专门针对配置了过期时间的键进行淘汰(我们在主动删除策略中提到过 Redis 会为配置了过期时间的键专门维护一个字典)。

LFU 模式

在 LFU 模式下,lru 字段的 24 个 bit 用来存储两个值,分别是高 16 位的 ldt(last decrement time)和低 8 位的 logc(logistic counter):

1.jpeg

也就是我们上面说的低 8 位存放访问频次,高 16 位存放 Redis 时钟,这个时钟值不再是该对象上次访问时间,而是 logc 的上次衰减时间。

8 位能存储的最大整数值是 255,这显然不够,所以 logc 这个字段实际存放的是对数值,这样一来最大能存放的数值就是 10000000。至于 ldt 字段,由于只有 16 位,如果仍然以秒为单位也不够用,所以存放的是分钟时间戳对 2^16 进行取模运算的结果,粒度相较于 server.lruclock 要粗一些,和 LRU 模式一样,这里也可以计算空闲时间,只不过是分钟级别的。

和 LRU 模式一样,logc 字段是在每次访问键时更新的,由于其中存放的是对数值,也不能加单执行 +1 操作,而是通过概率法递增。和 LRU 不同的是,ldt 字段不是在键被访问时更新的,而是在 LRU 淘汰算法执行时更新,淘汰算法会在 Redis 触及配置的内存上限时执行,每次淘汰也都采用随机策略,在随机获取的键中,更新每个键的 ldt 字段,同时衰减对应的 logc 字段(基于配置文件配置的衰减因子 lfu-decay-time 控制,默认值是 1,0 表示不衰减),然后淘汰掉热度(访问频率)最低的键。

对于新增的键,为了防止被立即淘汰,会将 logc 值初始化为 5。

所以 LFU 模式本质上也还是 LRU 淘汰算法,只是对数据热度的表达更加精确而已。

Redis 支持的基于 LFU 模式的 LRU 淘汰策略分别是 4.0 版本之后新增的 allkeys-lfu 和 volatile-lfu,含义和 LRU 模式一样,不再赘述了。

0

评论区