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值的方式和例子。

[1503282787902_6617_1503282788500.jpg]

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块）。典型的一种情形如下：

[1503282798841_7119_1503282799435.jpg]

关于栈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的结构。

[1503282826724_8452_1503282827256.jpg]

2.5 算法效果测试

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

1）.从不重复访问（这个和第二个循环访问重合，所以将这种模式和第二种合并）

2）.循环访问

3）.集中性访问，每个block都会被集中访问。

4）.概率性访问（每个block都有固定概率）。

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

[1503282840126_5416_1503282840724.jpg]

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

[1503282852287_6981_1503282852838.png]

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

[1503282862502_1955_1503282863086.png]

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

[1503282873853_948_1503282874449.png]

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

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

[1503282887006_1745_1503282887547.png]

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

[1503282897188_8671_1503282897758.png]

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

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

[1503282909634_9892_1503282910177.png]

2.8 算法缺陷及解决方案

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

[1503282925542_6499_1503282926103.png]