cache 淘汰算法:LIRS 算法

导语

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的大小限制并不会对性能产生过为恶劣的影响。

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

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

编辑于

我来说两句

1 条评论
登录 后参与评论

相关文章

来自专栏祝威廉

让流动的数据结构化

结构化数据加上一个支持schema变更的存储,加上一个高效易用的支持SQL的数据处理和查询的引擎,简直无所不能和极度高效。

371
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

SSE图像算法优化系列四:图像转置的SSE优化(支持8位、24位、32位),提速4-6倍

一、前言       转置操作在很多算法上都有着广泛的应用,在数学上矩阵转置更有着特殊的意义。而在图像处理上,如果说图像数据本身的转置,除了显示外,本身并无特殊...

2619
来自专栏Jackson0714

Web性能探索之旅-1.无线网络基础

1122
来自专栏Jackson0714

Web性能探索之旅-1.无线网络基础

2626
来自专栏码匠的流水账

HashedWheelTimer算法详解

George Varghese 和 Tony Lauck 1996 年的论文:Hashed and Hierarchical Timing Wheels: da...

451
来自专栏翻译

路径查找器AI

问题源于我想建立一个游戏AI,它要能够定义一条从起点到终点的路径,同时避开路上的墙壁障碍物。为此,我写了一个C#库(path.dll),它允许定义一个二维空间(...

1947
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

解析opencv中Box Filter的实现并提出进一步加速的方案(源码共享)。

  说明:本文所有算法的涉及到的优化均指在PC上进行的,对于其他构架是否合适未知,请自行试验。       Box Filter,最经典的一种领域操作,在无数...

3677
来自专栏Soul Joy Hub

tensorflow架构

原文 : http://blog.csdn.net/stdcoutzyx/article/details/51645396 Basic Concepts 张量(...

3138
来自专栏SDNLAB

ONOS:负载均衡路由算法及应用开发(一)

一、应用介绍 当新流量发起时,本应用将为其选择一条路由路径,这条路径具有全局负载均衡意义上的最小权值(Weight/Cost)。 本应用即将开源在笔者的Gith...

3307
来自专栏机器学习从入门到成神

计算机系统的层次存储结构详解

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

651

扫码关注云+社区