缓存淘汰算法LIRS原理与实现

问题背景

传统的缓存淘汰算法 LRU（Least Recently Used 最近最少访问）以其简单有效性被广泛应用，LRU 的核心思想是淘汰掉未访问时间最长的缓存块，它对所有的数据做了一个简单假设：如果数据块被访问了一次，那么该数据块在接下来的一段时间中还会被再次访问。但是当 LRU 算法遇到下面场景时候存在一定的局限性：

1. 数据块可能被访问一次之后不会再被访问，大量的对这种数据块访问会频繁地淘汰掉经常访问且已在缓存中的数据块（缓存污染）
2. 循环访问一部分数据块，且这部分数据块数刚好大于缓存块总数的话，那么每次数据块在下一次循环访问之前都会被淘汰掉
3. 无法区分缓存块访问频率高低，如查询数据库每次都要查询索引然后再得到数据记录，索引缓存的访问频率高于数据记录的缓存，但是在 LRU 中可能出现索引的缓存数和数据记录的缓存数一样多情况

LRU 不适用上面场景主要是因为只考虑了一个因素 Recency（翻译为 “新进度”，即最近最新访问），因此提出了 LIRS 算法。

LIRS 缓存算法原理

LIRS 算法全称 Low Inter-reference Recency Set，LIRS 使用 IRR（Inter-Reference Recency）来表示记录数据块访问历史信息，IRR 表示最近连续访问同一个数据块之间访问其他不同数据块非重复个数：

LIRS-IRR.png

Cache1 的 IRR=3，连续两次访问 Cache1 之间访问 2,3,4，3 虽然访问两次但这里只算一次。同时，一个数据块从上一次访问到当前时间访问其他不同数据块非重复个数称为这个数据块的 recency，如图 Cache1 的 R=2，LIRS 与 LRU 最大的不同就是在淘汰 Cache 时候不仅考虑 Recency，同时会将 IRR 纳入考量范围中。LIRS 动态维护两个集合：

• LIR（low IRR block set）具有较小 IRR 的数据块集合，可以将这部分数据块理解为热数据，因为 IRR 低说明访问的频次高
• HIR（high IRR block set）具有较高 IRR 的数据块集合，可以将这部分数据块理解为冷数据。同时，在 HIR 集合中有部分数据块不在缓存中，但我们记录了它们的历史信息并标记为未驻留在缓存中，我们称这部分数据块为 nonresident-HIR，另外一部分驻留在缓存中的数据块称为 resident-HIR。

LIRS 会限制 LIR 集合大小，保证所有的 LIR 数据块在缓存中，当发生缓存块淘汰时候，只会淘汰 HIR 集合中的数据块，这里用变量 Llirs 表示 LIR 集合大小，Lhirs 表示 HIR 集合中驻留在内存的数据块（resident-HIR）大小，用 L 表示驻留在缓存中的数据块总数：

L = Llirs + Lhirs

因为 LIR 集合在缓存中，所以访问 LIR 集合的数据块是百分百命中缓存的，而 HIR 集合分为 resident-HIR 和 nonresident-HIR 两部分，所以会遇到未命中情况。当发生缓存未命中需要置换缓存块时候，会选择优先淘汰置换 resident-HIR。如果 HIR 集合的数据块 IRR 经过更新比 LIR 集合中的小，那么 LIR 集合数据块就会被 HIR 集合中 IRR 小的数据块挤出并转换为 HIR。

下面通过举例解释一下 LIRS 算法是如何淘汰缓存数据块以及 LIR 和 HIR 状态之间的切换

LIRS-table.png

表中字母标志 X 表示数据块在某个时间点被访问, 比如数据块 A 分别在时间点 1、6 和 8 被访问，在时间点 10 数据块 {A, B, C, D, E} 的 recency 和 IRR 分别为

• recency={1, 3, 4, 2, 0}
• IRR={1, 1, inf, 3, inf}

由于 C 和 E 只被访问一次，这里将它们的 IRR 设置为为 inf。这里我们假设 Llirs=2、Lhirs=1，因此在时间点 10 的时候:

• LIR={A, B} 表示 A 和 B 在 LIR 集合中
• HIR={C, D, E} 表示剩余的数据块在 HIR 集合中

由于 Lhirs=1, 而且数据块 E 最后一次被访问的时间点离时间点 10 最近，因此在 HIR 集合中 resident-HIR={E}，nonresident-HIR={C, D}

当访问 LIR 集合时候，由于数据块在缓存中，因此不需要修改 LIR 集合。如果访问的是 HIR 集合的数据块，那么这个数据块会重新获得一个新的 IRR ，这个 IRR 等于这个数据块当前的 recency，使用这个新的 IRR 与 LIR 集合中数据块中最大的 recency 进行比较，如果小于的话那么就交换这个HIR数据块和LIR中recency最大的数据块状态，进行冷热切换。

上面进行冷热切换的依据是使用HIR中被访问数据块新生成的IRR和LIR中最大的recency进行比较，而不是和LIR中最大的IRR进行比较，主要是基于两个原因：

1. IRR是基于recency生成，它们都是基于上一次被访问的时间点生成，因此LIR中的IRR是过期的
2. 如果HIR中新的IRR小于LIR中的recency，那么他肯定小于这个LIR数据块的下一个IRR值，因为这个LIR数据块下一个 IRR 就是它被访问时刻的 recency

根据上表举例说明下，如果在时间点10对数据块D进行访问，那么就会发生一次不命中（数据块D为nonresident-HIR），这个时候resident-HIR数据块E会被淘汰置换而不是数据块B，如果要是LRU算法的话，那么数据B就会被淘汰，因为它的recency是最大的。同时，因为数据块D被访问，它的IRR值会更新为2，小于LIR中的数据块B的recency=3（数据块B的下一个IRR一定会大于3），所以将数据块D由HIR切换为LIR，数据块B变为HIR，现在数据块B是唯一存在于缓存中的HIR块。如果在时间点10访问是C而不是D的话，那么就不会发生状态的转换，但是数据块E还是会被淘汰置换。通过这种方法，就能够动态的维持LIR块集和HIR块集。

LIRS 算法实现

下面介绍LIRS算法的具体实现，并演示缓存淘汰置换步骤，这里可以通过两个数据结构来实现LIRS算法

• LIRS栈S：用于保存数据块的历史记录，动态调整LIR和HIR集合，这个和LRU算法的实现基本一样，只是他的大小会变化，越靠近栈顶recency越小
• 链表Q：保存resident-HIR集合，大小固定为Lhirs，即Q用于保存冷数据缓存块

LIRS算法主要分几种情况：

• 访问LIR
• 访问resident-HIR
• 访问不在LIR和HIR中的数据块
• 访问nonresident-HIR

下面用几张图来说明LIRS算法过程

访问LIR

LIR集合数据块都在缓存中，所以会百分百命中缓存，不会发生缓存淘汰置换，只需要将缓存块移动到栈顶即可，如果缓存块在栈底需要进行栈剪枝操作，所谓栈剪枝就是保证栈顶的数据库为LIR状态，这样如果访问一个resident-HIR就知道这个resident-HIR的新IRR一定小于栈底LIR的recency，直接互换它们状态。

LIRS-accessLIR.png

• 访问LIR数据块5，直接将数据块4移动到Q栈顶，由于栈底为LIR数据块，不需要进行栈剪枝
• 访问LIR数据块3，将数据块3移动到Q栈顶，并进行栈剪枝操作，将HIR数据块8、9移除出S

访问resident-HIR

resident-HIR数据块在缓存中，因此命中不会发生缓存淘汰置换，只需要对S和Q做调整（维护LIR和HIR），这里分两种情况：

1. resident-HIR在LIRS栈S中
2. resident-HIR不在LIRS栈S中

LIRS-accessResidentHIR.png

• 访问在S中的resident-HIR数据块3，新生成的IRR一定比栈底的LIR小：
  • 数据块3移到S栈顶并转换为LIR，然后从Q中移除它
  • S栈底的LIR转换为HIR，放入Q尾部
  • 对S进行栈剪枝
• 访问不在S中的resident-HIR数据块6，HIR状态属性不变，将数据块6放入S栈顶，同时在Q中把它移动到尾部

访问不存在LIR和HIR的数据块

数据块不在LIR和HIR中，肯定也不在缓存中，发生缓存淘汰置换，需要将Q头部的resident-HIR数据块进行淘汰，这里分两种情况：

1. 淘汰的resident-HIR在LIRS栈S中
2. 淘汰的resident-HIR不在LIRS栈S中

LIRS-accessNotExist.png

• 访问数据块8，将数据块8作为resident-HIR放入S栈顶和Q尾部，同时淘汰Q中的resident-HIR数据块1，数据块1不在S中，可以直接移除
• 访问数据块5，将数据块5作为resident-HIR放入S栈顶和Q尾部，同时淘汰Q中的resident-HIR数据块4，数据块4在S中，不需要从S中移除，直接将数据块4标记为noresident-HIR即可，仍然保留数据块4在S中是为了维护S栈中的recency信息

访问noresident-HIR

nonresident-HIR不存在缓存中，发生缓存淘汰置换，需要将Q头部的resident-HIR数据块进行淘汰。

首先根据前面定义可以知道nonresident-HIR数据块一定在LIRS栈S中，当访问nonresident-HIR时候，首先将它移动到S栈顶并标记为LIR，并将栈底LIR转换为resident-HIR放入Q尾部，最后淘汰Q头部的resident-HIR

LIRS-accessNonResidentHIR.png

• 访问nonresident-HIR数据块4：
  • 数据块4移到S栈顶并转换为LIR
  • 将S栈底的LIR数据块3转换为resident-HIR放入Q尾部，并进行一次栈剪枝（此处不需要，因为3之上的数据块7为LIR）
  • 淘汰Q头部的resident-HIR数据块8
• 访问nonresident-HIR数据块9：
  • 将数据块9移到S栈顶并转换为LIR
  • 将S栈底的LIR数据块7转换为resident-HIR放入Q尾部，并进行一次栈剪枝（此处不需要，因为3之上的数据块2为LIR）
  • 淘汰Q头部的resident-HIR数据块5，由于数据块5在S中，将它标记为nonresident-HIR

参考

• http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-02-6.pdf
• https://en.wikipedia.org/wiki/LIRS_caching_algorithm
• http://km.oa.com/group/11879/articles/show/299675?kmref=search&from_page=1&no=1
• http://xiadejun.blogspot.com/2013/01/lirs.html
• https://github.com/wuyu201321060203/wuyu201321060203.github.io/blob/master/_posts/2014-07-25-LIRS.md