Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >cache 淘汰算法:LIRS 算法

cache 淘汰算法:LIRS 算法

原创
作者头像
钱坤
修改于 2017-08-23 05:01:30
修改于 2017-08-23 05:01:30
8K3
举报
文章被收录于专栏:钱坤的专栏钱坤的专栏

导语

LIRS算法是非常优秀的cache淘汰算法,被用于mysql 5.1之后的版本,这篇文章主要来源于对LIRS的发表论文《LIRS: An Efficient Low Interreference Recency Set Replacement Policy to Improve Buffer Cache Performance》的翻译。

1.传统算法

LRU(Least Recently Used):算法起源可追溯到1965年(甚至更早),是最为经典的页面置换算法,算法思想为淘汰最长时间未被使用的页面。LRU最友好的数据模型为具有时间局部性的请求队列。但是由于未考虑频率因素,偶发性的、周期性的批量操作时效果较差,缓存污染严重。使用hashmap和双向链表实现,可以让时间复杂度降至O(1)。

LFU(Least Frequently Used),淘汰一定时期内被访问次数最少的页。

OPT(OPTimal replacement,最佳淘汰算法):根据未来实际使用情况将未来的近期里不用的页替换出去。这种算法是用来评价期它替换算法好坏的标准。不可能实现。所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面。

MRU(最近最频繁使用算法,Most Recently Used),最近最频繁使用算法和最近最少使用算法相反,它会首先丢弃最近最常使用的数据。

LRU-2,只有当数据的访问次数达到2次的时候,才将数据放入缓存。当需要淘汰数据时,LRU-2会淘汰第2次访问时间距当前时间最大的数据。可以拓展为LRU-K。

2Q(Two queues):LRU2的改进,不同点在于2Q将LRU-2算法中的访问历史队列改为一个FIFO缓存队列(即包含FIFO队列和LRU队列)。可拓展为MQ算法( Multi Queue)。

Clock算法(Not Recently Used, NRU):简单的CLOCK算法是给每一帧关联一个附加位,称为使用位。当某一页首次装入主存时,该帧的使用位设置为1;当该页随后再被访问到时,它的使用位也被置为1。当需要替换一页时,系统扫描缓冲区,以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时,操作系统就将该位重新置为0;如果在这个过程开始时,缓冲区中所有帧的使用位均为0,则选择遇到的第一个帧替换;如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周,把所有使用位都置为0。

2.LIRS算法

2.1算法概述

LIRS是针对LRU做优化的算法,在很多文章中被给予很高的评价,并且已经被应用在mysql 5.1之后的版本中。

传统的LRU算法有如下的问题:

1)对冷数据突发性访问抵抗能力差,可能会因此淘汰掉热的文件。好的算法里:热文件不应该被冷文件淘汰掉。

2)对于大量数据的循环访问抵抗能力查,极端情况下可能会出现命中率0%。好的算法里:这种情况miss rate应该约等于buffer space shortage ratio。

3)不能按照数据的访问概率进行淘汰。好的算法:能够按照数据的访问概率进行淘汰,只有高概率访问的文件才能在cache中长时间存活。一个例子如下:

一个B树,每个leaf node指向一个block,有20000个block。每个leaf node有20B,每个block有2000B。Cache的每一个page有4000B。所以20000个leaf node需要用100个page进行存储,20000个block需要用10000个page进行存储。而实际上这个时候我们的cache只有101个page,这个时候的最佳缓存策略为:cache中仅缓存leaf node,因为leaf node page的访问概率为0.005,而文件的page访问概率0.00005。而LRU并不能做到这一点。

2.2 算法涉及的基本概念介绍

LIRS算法使用两个参数来衡量一个cache 块,分别是IRR(Inter-Reference Recency)和R(Recency),IRR为一个页面最近两次的访问间隔,当第一次被访问时IRR的值为无穷大(inf)。R为页面最近一次访问到当前时间内有多少页面曾经被访问过(LRU数值)。下面两张图为计算IRR和R值的方式和例子。

LIRS算法将数据块分为LIR和HIR两级的方式:

1)LIR:热数据块,已经被访问两次的数据块。

2)HIR:冷数据块,还仅仅只被访问一次的数据块。任意HIR块的IRR值小于Rmax就可以转化为LIR块。所有R值小于Rmax的HIR块可以保留在栈S中。

LIRS算法会设置一个栈和一个FIFO队列,栈S负责热数据(LIR块)淘汰,队列Q中负责冷数据(HIR块)淘汰。在栈S中的HIR块索引分为两种情况:数据存在于cache中和数据已经被淘汰(HIR块)。典型的一种情形如下:

关于栈S和队列Q的基本使用原则如下:

1)栈S存储LIR块以及R值小于所有LIR块的Rmax的HIR块。

2)队列Q存储所有存在的HIR块。所以大小为Lhirs。

3)算法初始化之后新访问的块都被当作LIR块。当达到Llirs之后,新访问(或者访问过已经在栈S里被淘汰的)的转为HIR块。

4)当需要一个free block时,从队列Q移除一个HIR block,并将栈s中的这个block设置为non-resident。

5)确保栈S的底部为LIR块。

6)当有HIR块再次被访问,则将其升级为LIR块放于栈顶,并将栈s底部的LIR块降级为HIR块,并将其放至队列Q顶部。同时进行栈剪枝(stack push)。

Ps 栈剪枝的概念如下:

(1).栈底一定要是LIR块

(2).如果栈底的LIR块被移除,和上一个LIR块之间的HIR块也要被移除。

2.3 算法基本思路

当访问一个block时,可能会出现如下情况:

1.访问栈中的LIR块:将其移至栈顶,如果这个LIR原本在栈底,则进行剪枝。

2.访问栈S中的resident HIR块:有两种情况:

1)这个块已经在栈S中存在了,此时将其移至栈首,并将其从队列Q中删除,栈S底部的LIR块转为HIR块,并被移动至队列Q,接下来会进行剪枝操作。

2)这个块在栈S中不存在,我们将他设置为HIR块,并放至栈S顶和队Q尾。

3.访问栈S non-resident HIR块:队列Q的队首元素移除,并在cache中彻底删除它,并用于存储新数据块,并将其置于栈S顶部。接下来有两种情况:

1)如果这个块在栈S中,我们将其转化为LIR块并移动至栈顶,将栈S底部数据块转化为HIR块移至队列Q,然后对栈S剪枝。

2)如果这个块不在栈S中,则将其置入队列Q队尾。

2.4 算法练习

下面是来源于wiki的练习题,假设图a为初始状态,箭头标识此时对某个元素进行访问,箭头所指向的图为访问之后的栈S和队列Q的结构。

2.5 算法效果测试

论文中测试采用四种数据访问模式:

1).从不重复访问(这个和第二个循环访问重合,所以将这种模式和第二种合并)

2).循环访问

3).集中性访问,每个block都会被集中访问。

4).概率性访问(每个block都有固定概率)。

下图是在循环访问模式下,各个算法的命中率,可以看到,LRU的命中率在cache较小的时候命中率基本为0。而LIRS此时的miss rate约等于buffer space shortage ratio。

下图是在各个block概率性访问的访问模式下的性能分析,在cache size为50blocks的时候,LRU的命中率为9.3%,LIRS的命中率为55%,相差较大。

下图是在每个block集中访问的情况下的性能分析。如果将图像放大可以发现,LRU的命中率在cache size稍大的时候要优于LRU。因为此时访问序列具有时间局部性,当访问热点偏移会为LIRS带来一定性能退化(miss)。不过由于这种偏移并不频繁且热点访问较为集中,这种影响是有限的。

多种访问情况组合的性能分析如下,LIRS的性能明显较优:

2.6 算法参数Lhirs和冷热转化阈值的选定

通过下面调整Lhirs值的大小的实验分析,Lhirs的大小为L的1%为合适的,实验如下。

通过实验分析,HIR转为LIR的阈值在Rmax附近变化时,结果并无明显却区别,但是当调制550%Rmax时,命中率向LRU靠近。特别指出,LRU可以近似看作转化阈值为正无穷的LIRS。

2.7 算法时间和空间复杂度分析

复杂度分析:时间复杂度上,LIRS可以通过实现达到和LRU一样的O(1)。空间复杂度如下图,下图是Rmax(栈S大小)和L的比值,可以看到,在这种正常的访问模式下,栈S的大小会大于L,但是也是小于3.5倍的关系。

2.8 算法缺陷及解决方案

LIRS算法在空间使用上有一定缺陷,即为栈S的大小在极端情况下会变的无法预期的大,文中提供了一种简单的抑制方法,即超过大小限制之后移除栈最底部的HIR块。下面是对栈S大小限制的性能测试,LIRS后面的数字为sizeof(S)/L,可以看出对栈S的大小限制并不会对性能产生过为恶劣的影响。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

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

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

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

评论
登录后参与评论
3 条评论
热度
最新
栈S和队列Q的基本使用原则、算法基本思路、算法练习,几个部分内容存在重复,同时又存在矛盾的地方,看得一头雾水
栈S和队列Q的基本使用原则、算法基本思路、算法练习,几个部分内容存在重复,同时又存在矛盾的地方,看得一头雾水
回复回复点赞举报
半天也没把概念和定义说清楚,算法练习里的举例和前面的阐述矛盾
半天也没把概念和定义说清楚,算法练习里的举例和前面的阐述矛盾
回复回复点赞举报
请问您能不能提供一下LIRS算法的源码呢?我的邮箱是zsonkie@vip.qq.com
请问您能不能提供一下LIRS算法的源码呢?我的邮箱是zsonkie@vip.qq.com
回复回复点赞举报
推荐阅读
编辑精选文章
换一批
缓存淘汰算法LIRS原理与实现
传统的缓存淘汰算法 LRU(Least Recently Used 最近最少访问)以其简单有效性被广泛应用,LRU 的核心思想是淘汰掉未访问时间最长的缓存块,它对所有的数据做了一个简单假设:如果数据块被访问了一次,那么该数据块在接下来的一段时间中还会被再次访问。但是当 LRU 算法遇到下面场景时候存在一定的局限性:
saosir
2019/07/16
3.1K0
缓存淘汰算法LIRS原理与实现
服务器开发设计之算法宝典
作者:lynhlzou,腾讯 IEG 后台开发工程师 孙子云:“上兵伐谋,其次伐交,其次伐兵,其下攻城”,最上乘行军打仗的方式是运用谋略,下乘的方式才是与敌人进行惨烈的厮杀。同样的,在程序设计中,解决问题的办法有很多种,陷入到与逻辑进行贴身肉搏的境况实属下下之策,而能运用优秀合理的算法才是”伐谋”的上上之策。 算法的思想精髓是值得深入研究和细细品味的,本宝典总结了服务器开发设计过程中涉及到的一些常用算法,试图尽量以简洁的文字和图表来解释和说明其中的思想原理,希望能给大家带来一些思考和启示。 思维导图
腾讯技术工程官方号
2021/12/28
1.7K0
聊聊缓存淘汰算法-LRU 实现原理
我们常用缓存提升数据查询速度,由于缓存容量有限,当缓存容量到达上限,就需要删除部分数据挪出空间,这样新数据才可以添加进来。缓存数据不能随机删除,一般情况下我们需要根据某种算法删除缓存数据。常用淘汰算法有 LRU,LFU,FIFO,这篇文章我们聊聊 LRU 算法。
andyxh
2019/10/30
8090
聊聊缓存淘汰算法-LRU 实现原理
BP-Wrapper:无锁竞争的缓存替换算法系统框架
最近看了一个golang的高性能缓存ristretto,该缓存可以很好地实现如下功能:
charlieroro
2021/06/17
1.2K0
BP-Wrapper:无锁竞争的缓存替换算法系统框架
LevelDB 完全解析(5):Cache
在 LevelDB 中,block cache 和 table cache 都是基于 ShardedLRUCache 实现的。
linjinhe
2020/05/08
1K0
Buffer cache 的调整与优化(一)
Buffer Cache是SGA的重要组成部分,主要用于缓存数据块,其大小也直接影响系统的性能。当Buffer Cache过小的时候,将会造成更多的
Leshami
2018/08/07
1.1K0
浅入浅出Caffeine cache
本地缓存也就是我们适用内存缓存一些热点数据,使应用程序的程序处理的更加的快。以及保护我们的一些有磁盘/网络IO操作的函数/方法,以达到减小我们服务的响应时间的目的。
袁新栋-jeff.yuan
2021/12/07
5470
浅入浅出Caffeine cache
DB Cache
1 DB Cache 是以bock为单位组织的缓冲区,不同大小的BLOCK对应不同的缓冲区参数 2 DB Cache的命中率越高,访问性能就越好 3 Cache中的数据块通过散列算法实现 4 每个链上的buffers数量,最佳的情况是每个链上只有一个buffer 5 DBWR进程控制脏数据写入 6 在DB Cache,同一个数据块中可能存在多个版本的数据 7 大表的扫描,热块冲突都可能导致闩锁的争用 引入tch计数器,避免LRU链上频繁移动 LRU链上搜索达到最大深、LRU-W上没有足够的clean buf
用户1154259
2018/01/18
8970
分布式系统架构7:本地缓存
我们在开发时,用到缓存的情况,无非就是为了减少客户端对相同资源的重复请求,降低服务器的负载压力。引入缓存后,既有好处也有坏处
卷福同学
2025/01/15
1260
缓存淘汰算法与 python 中 lru_cache 装饰器的实现
此前的文章中,我们介绍过常见两种缓存架构 — 穿透型缓存与旁路型缓存。 常见缓存架构 — 穿透型缓存与旁路型缓存
用户3147702
2022/06/27
5550
缓存淘汰算法与 python 中 lru_cache 装饰器的实现
缓存之王Caffeine Cache,性能比Guava更强,命中率更高!
在项目开发中,为提升系统性能,减少 IO 开销,本地缓存是必不可少的。最常见的本地缓存是 Guava 和 Caffeine,本篇文章将为大家介绍 Caffeine。
用户2781897
2021/01/28
2.9K0
缓存之王Caffeine Cache,性能比Guava更强,命中率更高!
4-1.页面置换算法
① 判断置换算法好坏的标准: 具有较低的页面置换频率。 ② 内存抖动: 页面的频繁更换,导致整个系统效率急剧下降,这个现象称为内存抖动。 一、最佳置换算法 1.作用 其所选择的被淘汰页,
见贤思齊
2020/08/05
4K0
4-1.页面置换算法
缓存淘汰/读写/存在问题总结
实现思路也是很简单的, 套用消息队列思路, 每次新生成缓存标记放到队列尾部, 优先淘汰队列头部的数据.
用户2825413
2020/03/23
6740
Buffer cache 的调整与优化(二)
Buffer cache 实际上细分为多个不同的Buffer cache,如keep pool,recycle pool,default pool,下面描述不同buffer cache的使用。
Leshami
2018/08/07
8670
动手实现一个localcache - 设计篇
哈喽,大家好,我是asong。最近想动手写一个localcache练练手,工作这么久了,也看过很多同事实现的本地缓存,都各有所长,自己平时也在思考如何实现一个高性能的本地缓存,接下来我将基于自己的理解实现一版本地缓存,欢迎各位大佬们提出宝贵意见,我会根据意见不断完善的。
Golang梦工厂
2022/07/11
3840
动手实现一个localcache - 设计篇
你应该知道的缓存进化史!
本文是上周去技术沙龙听了一下爱奇艺的Java缓存之路有感写出来的。先简单介绍一下爱奇艺的java缓存道路的发展吧。
Java后端技术
2018/09/18
1.1K0
你应该知道的缓存进化史!
计算机组织结构(六) Cache
📚 文档目录 合集-数的二进制表示-定点运算-BCD 码-浮点数四则运算-内置存储器-Cache-外存-纠错-RAID-内存管理-总线-指令集: 特征- 指令集:寻址方式和指令格式 为什么需要 cac
Rikka
2022/01/11
1.2K0
计算机组织结构(六) Cache
CPU体系结构之cache小结
What is cache? CPU缓存(Cache Memory)位于CPU与内存之间的临时存储器,它的容量比内存小但交换速度快。在缓存中的数据是内存中的一小部分,但这一小部分是短时间内CPU即将访
刘盼
2022/07/21
1.3K0
CPU体系结构之cache小结
手写LRU缓存淘汰算法
在我们这个日益追求高效的世界,我们对任何事情的等待都显得十分的浮躁,网页页面刷新不出来,好烦,电脑打开运行程序慢,又是好烦!那怎么办,技术的产生不就是我们所服务么,今天我们就聊一聊缓存这个技术,并使用我们熟知的数据结构--用链表实现LRU缓存淘汰算法。
Simon郎
2021/03/01
7800
大话Queue、Buffer、Cache
队列用于两个模块(或者硬件模块,或者软件模块)之间传递消息,一般采用FIFO(先进先出)方式。下文中会解释这些消息里都是什么。在芯片内部,两个硬件模块(或者是CPU+固件,或者直接是组合逻辑电路)之间通常采用寄存器~寄存器对连的方式来传递数据/信号,但是寄存器对连的话,每次只能往寄存器里放一条数据,如果两端步调不一致,你处理快我处理慢的话,自然就有需求形成一个队列,那就是排布多个寄存器形成一列,然后再加上用于记录这一列寄存器中数据保存到什么位置的队列指针寄存器。生产者将消息从队列尾部入队,更新写指针,消费者从队列头部读走消息,更新读指针。有限的队列槽位形成一个虚拟的环形,不断生产消费,当写指针追赶上读指针时,队列满,有专门寄存器的控制位记录这个状态,有些设计还会产生一个中断来通知生产者。
冬瓜哥
2019/06/10
8910
相关推荐
缓存淘汰算法LIRS原理与实现
更多 >
LV.0
这个人很懒,什么都没有留下~
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档