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

9次阅读

共计 2101 个字符,预计需要花费 6 分钟才能阅读完成。

上一次,置信大家曾经晓得对于 LRU 页面置换算法的思维和实现了,这里能够一键中转:

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

Redis 的淘汰策略中,对于 LFU 页面置换算法 ,明天咱们来捋一捋到底 思维是啥,能够如何去实现它

这就让咱们进入状态吧

✔LFU 的思维和实现

LFU 全称为:Least frequently used

含意为:应用频次起码的,即为 最不常常应用的

思维是:如果 数据在一段时间被拜访的次数较少,那么在将来的一段时间,这段数据被拜访的几率就会更小

能够看到 LRU 和 LFU 思维上的区别是非常明显的

  • LRU 强调最近起码应用,关注的是最近有没有应用过

<!—->

  • LFU 强调的是一段时间的应用次数,关注的是频次

实际上,LRU 和 LFU 在实现上也是挺类似的,都要应用到双向链表和 hashmap,只不过,咱们须要思考如何很好的解决好频次这个数据

LRU 查问数据的时候,为了将工夫复杂度从 O(n) 升高到 O(1),抉择了应用 hashmap 来寄存具体的 key 和对应的 数据节点

那么 LFU 中,也能够如法炮制,能够应用 hashmap 寄存 频次 和 对应的该频次的节点组成的链表

👀👀简略来看

  • LRU 的实现时用一个双向链表,插入数据应用头插法,从尾部淘汰数据

<!—->

  • 那么 LFU 的实现实际上是 应用了 2 个 hashmap 和 多个 双向链表,插入数据应用尾插法,淘汰数据从链表头淘汰

✔举例时刻

还是同样的办法,咱们举个例子,就能很好的明确这个思维了

例如,咱们还是要插入这些数据

set(0,0),set(1,1),set(2,2),set(3,3),set(4,4),get(3) ,set(5,5),链表的 容量为 3

来模仿一下 LFU 的处理过程😁

同理,

先插入后面 3 个节点 数据

0, 1, 2,此处 LFU 是应用的 尾插法,此处对于首次插入的数据,频次都是 1,因而会默认放到频次为 1 的对应的链表上

插入 3,

因为 LFU 容量为 3,曾经满了,以后产生了缺页,须要置换数据

淘汰 频次(最低的)为 1 的链表的头结点,且删除 hashmap 中的数据,同时将 3 这个节点的数据退出到 hashmap 中

插入 4,

因为 LFU 容量为 3,曾经满了,以后产生了缺页,须要置换数据

淘汰 频次(最低的)为 1 的链表的头结点,且删除 hashmap 中的数据,同时将 4 这个节点的数据退出到 hashmap 中

获取 3,

key 为 3 的节点在 LFU 中,更新 3 节点的频次,从频次 1 更新到 频次 2

相当于在频次为 1 对应得的链表中,删除 3 这个节点,让 2 节点和 4 节点进行相连,再将 3 这个节点退出到频次为 2 的链表中,同时更新 hashmap 中 key 为 3 的值

插入 5,

因为 LFU 容量为 3,曾经满了,以后产生了缺页,须要置换数据

淘汰 频次(最低的)以后频次为 1 的链表的头结点,且删除 hashmap 中的数据,同时将 5 这个节点的数据退出到 hashmap 中

从上述演示中,咱们能够看到 对于 LRU 的要害逻辑

  1. 实现根本的链表,应用一个 hashmap 来寄存 key 和对应的节点 应用另外一个 hashmap 来寄存频次和其对应的链表

<!—->

  1. 插入的数据时,如果 LFU 容量已满,那么找到频次最低的那条链表,删除链表头,并插入数据到链表尾部

<!—->

  1. 查问数据的时候,若数据曾经存在于链表中,则将该节点的频次 +1,且放到对应频次的链表尾部

那么在实现的时候,只须要实现根本的链表以及对于两个 hashmap 的联动即可实现咱们的 LFU

LFU 绝对 LRU 的实现来说,会多保护一个 hashmap,只不过这个 hashmap 是 key 为 频次,value 为链表,即上图中的 hashmap_freq

晓得 LFU 的思维,以及 LFU 中数据变动的过程明确了,写代码都是很简略的事件,感兴趣的 xdm 能够查看我的 code 地址:https://github.com/qingconglaixueit/my_lru_lfu/blob/main/my_lfu/lfu.go

代码案例后果

仓库地址中 main.go 代码实现和 LRU 的统一,只不过, 咱们的句柄和具体实现换成了 LFU 的

代码运行成果如下:

总结

至此,咱们将 Redis 淘汰策略中的 LRU 和 LFU 页面置换算法的思维,演示,以及具体实现都聊了一下,如果有偏差,还请提出,兄弟们不吝赐教哦

感兴趣的,随时能够下载源码,在你的机器上运行哦,仓库地址如下:

https://github.com/qingconglaixueit/my_lru_lfu

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

欢送点赞,关注,珍藏

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

好了,本次就到这里

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

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

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

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

<!—->

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

<!—->

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

<!—->

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

<!—->

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

<!—->

  • 我是如何用 redis 分布式锁来解决线上历史业务问题的
正文完
 0