前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >基于LRU、LRU-K算法的简单总结

基于LRU、LRU-K算法的简单总结

作者头像
友儿
发布2022-09-11 12:25:38
9990
发布2022-09-11 12:25:38
举报
文章被收录于专栏:友儿友儿

这篇文章中提到的LRU、LRU-K算法做一个附加介绍。

LRU-K模型设计

LRU算法介绍

  • Least recently used(LRU,最近最少使用):根据数据的历史访问记录淘汰数据。
  • 核心思想
代码语言:txt
复制
- 如果数据最近被访问过,那么将来被访问的几率更高。命中率
代码语言:txt
复制
- 当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。LRU算法模型
    - 新数据插入到链表头部;
    - 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
    - 当链表满的时候,将链表尾部的数据丢弃。
LRU-K算法设计
LRU-K中的K代表最近使用的次数。主要目的
代码语言:txt
复制
- 解决LRU算法“缓存污染”的问题。核心思想
代码语言:txt
复制
- “最近使用过1次”的判断标准扩展为“最近使用过K次”。命中率
代码语言:txt
复制
- LRU-K降低了“缓存污染”带来的问题,命中率比LRU要高。LRU-K模型数据第一次被访问,加入到访问历史记录表(简称记录表);在记录表中对应的K单元中设置最后访问时间=new(),且设置访问次数为1;如果数据访问次数没有达到K次,则访问次数+1。最后访问时间与当前时间间隔超过预设的值(如30秒),访问次数清0并加1;当数据访问计数超过(>=)K次后,则访问次数+1。将数据保存到LRU缓存队列中,缓存队列重新按照时间排序;LRU缓存队列中数据被再次访问后,重新排序;LRU缓存队列需要淘汰数据时,淘汰缓存队列中排在末尾的数据,即:淘汰“倒数第K次访问离现在最久”的数据。
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档