乐趣区

关于lrucache:LRU一文让你弄清-Redis-LRU-页面置换算法

jiezi

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

感激浏览，欢送交换，点个赞，关注一波 再走吧

欢送点赞，关注，珍藏

敌人们，你的反对和激励，是我保持分享，提高质量的能源

好了，本次就到这里

技术是凋谢的，咱们的心态，更应是凋谢的。拥抱变动，背阴而生，致力向前行。

我是 阿兵云原生，欢送点赞关注珍藏，下次见~

文中提到的技术点，感兴趣的能够查看这些文章：

  • 什么是单点登录？什么又是 OAuth2.0？

<!—->

  • 什么是分布式锁？他解决了什么样的问题？

<!—->

  • 【Redis 系列】redis 存储构造原理 1

<!—->

  • 【Redis 系列】redis 存储构造原理 2

<!—->

  • 我是如何用 redis 分布式锁来解决线上历史业务问题的
退出移动版