乐趣区

关于lrucache: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 的淘汰策略

能够看出 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 分布式锁来解决线上历史业务问题的
退出移动版