传统的缓存淘汰算法 LRU(Least Recently Used 最近最少访问)以其简单有效性被广泛应用,LRU 的核心思想是淘汰掉未访问时间最长的缓存块,它对所有的数据做了一个简单假设:如果数据块被访问了一次,那么该数据块在接下来的一段时间中还会被再次访问。但是当 LRU 算法遇到下面场景时候存在一定的局限性:
LRU 不适用上面场景主要是因为只考虑了一个因素 Recency(翻译为 “新进度”,即最近最新访问),因此提出了 LIRS 算法。
LIRS 算法全称 Low Inter-reference Recency Set,LIRS 使用 IRR(Inter-Reference Recency)来表示记录数据块访问历史信息,IRR 表示最近连续访问同一个数据块之间访问其他不同数据块非重复个数:
Cache1 的 IRR=3,连续两次访问 Cache1 之间访问 2,3,4,3 虽然访问两次但这里只算一次。同时,一个数据块从上一次访问到当前时间访问其他不同数据块非重复个数称为这个数据块的 recency,如图 Cache1 的 R=2,LIRS 与 LRU 最大的不同就是在淘汰 Cache 时候不仅考虑 Recency,同时会将 IRR 纳入考量范围中。LIRS 动态维护两个集合:
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 状态之间的切换
表中字母标志 X
表示数据块在某个时间点被访问, 比如数据块 A 分别在时间点 1、6 和 8 被访问,在时间点 10 数据块 {A, B, C, D, E} 的 recency 和 IRR 分别为
由于 C 和 E 只被访问一次,这里将它们的 IRR 设置为为 inf
。这里我们假设 Llirs=2、Lhirs=1,因此在时间点 10 的时候:
由于 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进行比较,主要是基于两个原因:
根据上表举例说明下,如果在时间点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算法过程
LIR集合数据块都在缓存中,所以会百分百命中缓存,不会发生缓存淘汰置换,只需要将缓存块移动到栈顶即可,如果缓存块在栈底需要进行栈剪枝操作,所谓栈剪枝就是保证栈顶的数据库为LIR状态,这样如果访问一个resident-HIR就知道这个resident-HIR的新IRR一定小于栈底LIR的recency,直接互换它们状态。
resident-HIR数据块在缓存中,因此命中不会发生缓存淘汰置换,只需要对S和Q做调整(维护LIR和HIR),这里分两种情况:
数据块不在LIR和HIR中,肯定也不在缓存中,发生缓存淘汰置换,需要将Q头部的resident-HIR数据块进行淘汰,这里分两种情况:
nonresident-HIR不存在缓存中,发生缓存淘汰置换,需要将Q头部的resident-HIR数据块进行淘汰。
首先根据前面定义可以知道nonresident-HIR数据块一定在LIRS栈S中,当访问nonresident-HIR时候,首先将它移动到S栈顶并标记为LIR,并将栈底LIR转换为resident-HIR放入Q尾部,最后淘汰Q头部的resident-HIR
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。