【LRU】一文让你弄清 Redis LRU 页面置换算法

阿兵云原生 / 119 / 2023-09-24 19:16:06

ChatGPT 可用网址,仅供交流学习使用,如对您有所帮助,请收藏并推荐给需要的朋友。
https://ckai.xyz

Q:一天同事问,我放在 redis 中的 key,为什么有时候过一段时间数据就没有了,我并没有设置过期时间呀??😳😳

A:你的 redis 淘汰策略是什么样的,这个 key 可能是被 redis 自身的淘汰策略干掉了

一看 redis 的 config 文件 redis.conf

果然,你配置的是 maxmemory_policy allkey-lfu ,这个是 Redis 中的淘汰策略,是会从 redis 数据集中挑选使用频率最低的数据进行淘汰的

Q:不明觉厉,摸摸头👀👀

A:我给你简单说一下关于 redis 的淘汰策略吧

首先,redis 删除数据的策略目前来看有三种

  • 👀定时删除

见名知意,定时,自然就像我们定起床闹钟一样,此处是定一个删除 key 的闹钟,当我们对一个 key 设置过期时间的时候,会同时开启一个定时器,当时间到到的时候,就会删除这个 key

这种方式,需要我们额外开一个定时器,会消耗 CPU 资源

  • 👀惰性删除

惰性,一看就知道这种删除方式是被动的,若一个 key 过期了,redis 不会主动去删除他,而是当这个 key 再次被访问的时候,redis 看他有没有失效,若失效,则删除他

这种方式可以看出,如果一些过期的 key ,再没有被再次访问之前,就会一直存在内存中,非常浪费内存资源

  • 😁主动删除

顾名思义,这种方式是 redis 中会去设置各种策略,去按照不同的策略去删除一些不符合要求的数据,简单的,我们来看看 Redis 的淘汰策略,掌握主动权

Redis 的淘汰策略

可以看出 redis 的淘汰策略大体上有 5 种方式

  • LRU

<!---->

  • LFU

<!---->

  • RANDOM

会从数据集中随机选择数据进行删除,按照配置的策略不同 allkeys-random 则是将在所有数据集中进行随机 , volatile-random 是在已经设置了过期时间的数据中去随机淘汰

  • TTL

会从设置了过期时间的数据中,挑选要过期的数据进行淘汰

  • No-eviction (默认,不驱逐数据)

上述五种,看了后面三种都比较好理解,对于前面两种,我来详细给你说一下他的原理,便于你能够理解和记住,而不是去背诵他,面试的时候还可以手撸一下实现代码

前面两种方式,LRU 和 LFU 都是属于页面置换算法,其中还有一个最简单的页面置换算法是 FIFO,学过基本数据结构的对于 FIFO 先入先出的特性并不模式,因此就不在这里展开了,咱们本次主要聊聊 LRU ,很多时候很多同学还是不理解

LRU 的思想和实现

LRU 全称为:Least recently used

含义为:最近最少使用

思想是:如果数据最近被访问过,那么未来最近一段时间,这个数据未来被访问的几率也会更大

思想就是这么简单,不过他已经足够指导我们实践了

我们根据思想来分析一下 LRU 如何去实现它

首先,我们知道数据在内存中是用链表的方式来连接,此处我们可以使用双向链表

那么,对于链表来说,插入数据是很方便的,但是读取的数据的话,难道我们每一次都要去遍历一遍 key 吗?

自然不是,因此对于 LRU 中,还是用 hashmap 来存放 key 和链表上具体数据节点的关系

这样,当访问任何一个 key 的时候,就可以通过 hashmap 中取到节点,进而取到节点的值即可,这种方式的时间复杂度就可以从 O (n) 降低到 O(1)

那么对于去实现 最近最少使用 的思想,那就是结合 hashmap 和双向链表来进行实现

  • 插入数据使用头插法,若访问到链表中的某个数据,则将该数据移动到链表头

<!---->

  • 若插入数据时,链表容量已满,此时淘汰链表尾部的数据

✔举例时刻

举个例子,相信你就可以明白

例如,我们要插入这些数据 set(0,0),set(1,1),set(2,2),set(3,3),set(4,4),get(3) ,链表的容量为 3,来模拟一下 LRU 的处理过程

先插入 3 个数据到 链表中 0, 1, 2,

此处为了简单,咱们将 key 和 value 的值做成一样的

插入 3,

链表容量已满,删除链表尾的数据,这个时候,就已经是发生了缺页,需要对数据进行置换,淘汰链表尾,hashmap 中删除链表为对应的数据,新增 3 这个节点的数据到 hashmap 中

插入4,

链表容量已满,删除链表尾的数据,这个时候,就已经是发生了缺页,需要对数据进行置换,淘汰链表尾,hashmap 中删除链表为对应的数据,新增 4 这个节点的数据到 hashmap 中

获取 3,

由于链表中已经有 3 ,因此会将 3 移动到链表头

从上述演示中,我们可以看到关于 LRU 的关键逻辑

  1. 实现基本的链表

<!---->

  1. 插入的数据时,如果链表已满,那么链表尾部的数据直接删掉,即淘汰

<!---->

  1. 查询数据的时候,若数据已经存在于链表中,则将该节点移动到头节点上

那么在实现的时候,只需要实现基本的链表以及其对应的基础方法 (头插法,尾插法,移动节点,查询节点等) ,以及使用 hashmap 来记录链表中具体的 key 和具体的节点

思想,以及 LRU 中链表数据变动的过程明白了,写代码都是很简单的事情,感兴趣的 xdm 可以查看我的 code 地址:https://github.com/qingconglaixueit/my_lru_lfu/blob/main/my_lru/lru.go

实现结果

链接中的代码,可以看到 main.go 实现如下

咱们可以将数据修改成文中的例子,

运行 main.go 之后,可以看到结果如下:

红色部分,表示发生了缺页中断, 向链表中追加的 key 是 0,1,2,3,4,3

感兴趣的话,还是将 代码下载下来,自己跑一下,多多感受一下 LRU 的思想和流程,很容易就可以理解😁😁

总结

这下对于 Redis 的淘汰策略,心中有个数了吧

对于 LRU的具体实现方式相信你可以可以很容易的看明白的,实践起来吧,源码地址为:https://github.com/qingconglaixueit/my_lru_lfu

感谢阅读,欢迎交流,点个赞,关注一波 再走吧

欢迎点赞,关注,收藏

朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力

好了,本次就到这里

技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。

我是阿兵云原生,欢迎点赞关注收藏,下次见~

文中提到的技术点,感兴趣的可以查看这些文章:

<!---->

<!---->

<!---->

<!---->


【LRU】一文让你弄清 Redis LRU 页面置换算法
作者
阿兵云原生
许可协议
CC BY 4.0
发布于
2023-09-24
修改于
2024-06-18
Bonnie image
尚未登录