前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >cache 淘汰算法:LIRS 算法

cache 淘汰算法:LIRS 算法

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

导语

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 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 导语
  • 1.传统算法
  • 2.LIRS算法
    • 2.1算法概述
      • 2.2 算法涉及的基本概念介绍
        • 2.3 算法基本思路
          • 2.4 算法练习
            • 2.5 算法效果测试
              • 2.6 算法参数Lhirs和冷热转化阈值的选定
                • 2.7 算法时间和空间复杂度分析
                  • 2.8 算法缺陷及解决方案
                  领券
                  问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档