LIRS算法是非常优秀的cache淘汰算法,被用于mysql 5.1之后的版本,这篇文章主要来源于对LIRS的发表论文《LIRS: An Efficient Low Interreference Recency Set Replacement Policy to Improve Buffer Cache Performance》的翻译。
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。
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并不能做到这一点。
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块也要被移除。
当访问一个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队尾。
下面是来源于wiki的练习题,假设图a为初始状态,箭头标识此时对某个元素进行访问,箭头所指向的图为访问之后的栈S和队列Q的结构。
论文中测试采用四种数据访问模式:
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的性能明显较优:
通过下面调整Lhirs值的大小的实验分析,Lhirs的大小为L的1%为合适的,实验如下。
通过实验分析,HIR转为LIR的阈值在Rmax附近变化时,结果并无明显却区别,但是当调制550%Rmax时,命中率向LRU靠近。特别指出,LRU可以近似看作转化阈值为正无穷的LIRS。
复杂度分析:时间复杂度上,LIRS可以通过实现达到和LRU一样的O(1)。空间复杂度如下图,下图是Rmax(栈S大小)和L的比值,可以看到,在这种正常的访问模式下,栈S的大小会大于L,但是也是小于3.5倍的关系。
LIRS算法在空间使用上有一定缺陷,即为栈S的大小在极端情况下会变的无法预期的大,文中提供了一种简单的抑制方法,即超过大小限制之后移除栈最底部的HIR块。下面是对栈S大小限制的性能测试,LIRS后面的数字为sizeof(S)/L,可以看出对栈S的大小限制并不会对性能产生过为恶劣的影响。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。