【LRU】一文让你弄清 Redis LRU 页面置换算法
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 的淘汰策略
[图片上传失败...(image-4d8f53-1695553223072)]
可以看出 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 的值做成一样的
[图片上传失败...(image-549146-1695553223071)]
[图片上传失败...(image-ec13a8-1695553223071)]
插入 3,
链表容量已满，删除链表尾的数据，这个时候，就已经是发生了缺页，需要对数据进行置换，淘汰链表尾，hashmap 中删除链表为对应的数据，新增 3 这个节点的数据到 hashmap 中
[图片上传失败...(image-cef7db-1695553223071)]
[图片上传失败...(image-54d486-1695553223071)]
插入4,
链表容量已满，删除链表尾的数据，这个时候，就已经是发生了缺页，需要对数据进行置换，淘汰链表尾，hashmap 中删除链表为对应的数据，新增 4 这个节点的数据到 hashmap 中
[图片上传失败...(image-1c8afa-1695553223071)]
[图片上传失败...(image-24db5d-1695553223071)]
获取 3,
由于链表中已经有 3 ，因此会将 3 移动到链表头
[图片上传失败...(image-6e3ebf-1695553223071)]
[图片上传失败...(image-b6f2cf-1695553223071)]
从上述演示中，我们可以看到关于 LRU 的关键逻辑
-
实现基本的链表
-
插入的数据时，如果链表已满，那么链表尾部的数据直接删掉，即淘汰
-
查询数据的时候，若数据已经存在于链表中，则将该节点移动到头节点上
那么在实现的时候，只需要实现基本的链表以及其对应的基础方法 （头插法，尾插法，移动节点，查询节点等） ，以及使用 hashmap 来记录链表中具体的 key 和具体的节点
思想，以及 LRU 中链表数据变动的过程明白了，写代码都是很简单的事情，感兴趣的 xdm 可以查看我的 code 地址：https://github.com/qingconglaixueit/my_lru_lfu/blob/main/my_lru/lru.go
实现结果
链接中的代码，可以看到 main.go 实现如下
咱们可以将数据修改成文中的例子，
[图片上传失败...(image-2b2370-1695553223071)]
运行 main.go 之后，可以看到结果如下：
红色部分，表示发生了缺页中断， 向链表中追加的 key 是 0,1,2,3,4,3
[图片上传失败...(image-52a49a-1695553223071)]
感兴趣的话，还是将 代码下载下来，自己跑一下，多多感受一下 LRU 的思想和流程，很容易就可以理解😁😁
总结
这下对于 Redis 的淘汰策略，心中有个数了吧
对于 LRU的具体实现方式相信你可以可以很容易的看明白的，实践起来吧，源码地址为：https://github.com/qingconglaixueit/my_lru_lfu
感谢阅读，欢迎交流，点个赞，关注一波 再走吧
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
[图片上传失败...(image-66a267-1695553223071)]
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
文中提到的技术点，感兴趣的可以查看这些文章：
