算法 从 LRU 到 LIRS

early · 2019年05月13日 · 最后由 BlockMa 回复于 2019年07月08日 · 2237 次阅读
本帖已被设为精华帖!

LRU

LRU(Least Recently Used)是一种使用广泛的缓存数据替换策略,目的是在有限的内存空间中尽可能保留最有价值的缓存数据。 其核心本意是,在资源出现不足时,剔除掉最近最少使用的数据,为新数据提供存放空间。

LRU的使用场景非常之多,以最为常见的MySQL为例。由于磁盘IO的读取效率远远低于内存操作,这使得数据库倾向于将大量数据直接加载在内存中进行操作,极力减少磁盘读取的次数。

MySQL中的BufferPool就是为此设计,但是内存的容量是远远小于磁盘容量,这使得只能加载部分数据到内存中,当BufferPool没有空闲的空间来缓冲新的数据时,就需要剔除部分数据,将空间让给看起来更有价值的数据。

而什么是更有价值的数据,该剔除哪些数据? LRU的理念就是剔除掉最近使用最少使用的数据。 如果某份数据刚被使用,那么就认为它近期还可能被使用,且使用概率大于相对旧的数据,这和计算机的时间局部性内涵一致。最近最少使用的数据,应该为最近较多使用的数据让出空间。

概括来讲,LRU是在资源有限的情况下,高效使用资源的一种策略,而这个策略的根基就是局部性原理

LRU实现

LRU基于时间局部性进行数据淘汰,它用一个链表来追踪数据的时间局部性,当一份数据当下被访问了,就将该数据移动到链表的头部,链表从头到尾的顺序,相当于按照最近的访问时间对数据排序。当需要淘汰数据时,就将链表尾部的数据直接剔除,将需要新加入的数据插入链表的头部。

一个双向链表+HashMap可以让LRU只有O(1)的时间复杂度,非常简单粗暴。而简单粗暴往往不能适应复杂的场景。

常规的数据访问规律可以分为以下几种:

  • 顺序访问。所有的块一个接一个被访问,几乎不存在重访问。
  • 循环访问。所有块都按照一定的间隔重复访问。
  • 时间密集访问。最近被访问的块在将来可能被连续重复访问。
  • 概率访问。所有块都有固定的访问概率,所有块都互相独立地根据概率被访问。

真实的环境是多种规律混杂,好的缓存替换算法需要有良好的适应性,LRU在连续重复访问的模式下表现很好,但其他场景则较差,回到上文MySQL的场景。

当数据库对某个表进行一次全表扫描时,假设这个表的大小和BufferPool一样大,按照LRU的粗暴,表中的数据会顶掉其他数据,占满BufferPool。 如果扫描是偶发性的,那么BufferPool中相当于缓存的是无用的数据,被顶替掉的可能还是正在被高频访问的数据。

从上可以看出LRU的核心缺陷是: 冷数据可以顶掉热数据,数据的替换策略并未考虑数据的冷热程度,只按照新近访问时间作为淘汰依据。在偶发性的扫描场景下,会让冷数据污染缓冲区,使得效率下降。

针对LRU的这种缺点,LFU(Least Frequently Used)算法会追踪数据的访问频率,选择访问次数最低的进行淘汰,这种想法很好的考虑了数据真实的局部性,如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小,这种淘汰策略更加贴近真实的使用场景。不过这种策略不能够即时的跟上新的热点变化,老数据占的坑不能快速地移交给新的热点,在适应性上较差。

随之而来的是2Q算法,它其实是LRU-K的改良,能较好的解决上面LRU的问题。2Q有一个FIFO队列用于放冷数据,一个LRU用来放热数据,将冷热数据区分对待,思想类似分代GC将新老对象区别处理。 2Q将第一次访问的冷数据放在FIFO队列中,当队列数据被再次访问(在FIFO中命中)时,将其视为热数据,放到LRU队列中进行管理。相当于用一个FIFO队列作为前置缓冲过滤掉突发性的冷数据,这样便解决了LRU的问题。不过随之而来的问题是FIFO队列的大小问题,如果太小则有些数据来不及提升为热数据就可能被移除FIFO,如果太大则会过多占用有限的空间,其比例需要根据情况进行配置。

LIRS则尝试在解决LRU问题基础上,让解决方案可能简单高效,同时具有较强的适应性。

LIRS

LIRS继承了LRU根据时间局部性对冷热数据进行预测,在此之上LIRS引入了两个衡量数据块的指标:

  • IRR(Inter-Reference Recency) 页面最近连续两次块访问之间访问其他块的个数
  • R (Recency)页面最近一次访问到当前时间内访问其他块的个数,也就是LRU的维护的数据

在图上的访问时间区间中:

  • 数据1: IRR=3(重复的块不算),R=2
  • 数据5: IRR=2,R=0
  • 而只访问了一次的4: IRR为无穷大,R=4

可以看出IRR是由R值计算而来,是历史信息的产物,在上图current时刻命中了一次“5“,其当前时刻的R=0,IRR=上一时刻的R-当前时刻的R = 1 。

IRR可以衡量数据当前访问的频度,IRR越高说明在某个时间区间中,该数据的热度较低。而LIRS假设如果当前一个块的IRR比较大,那么该块的下一个IRR也会比较大,在进行数据淘汰时会优先选择IRR大的进行。

根据IRR值,LIRS将数据块分为两种:

  • LIR,低IRR值,热数据
  • HIR,高IRR值,冷数据,接下来有可能成为热数据

LIRS要做的就是用简单的方式动态地维护IRR和R值,让冷数据有机会成为热数据,而将变冷的热数据剔除出缓存,同时要避免LRU的弊端。

LIRS通过一个栈S和一个队列Q来实现:

  • 当缓存空间还没满时,所有的数据块都为LIR,直接写入S(S的初始化)
  • 当LIR数据块在S中被命中时,将块移动到S的顶部(维护R值)
  • 当LIR的数量到达上限时,新加入的数据块为HIR,同时写入S和Q的头部(R值为0)
  • 当Q的空间不足时,则剔除Q尾部的数据,如果数据在S中,则将数据块设为非驻留HIR块,如果不在S中,则将数据测地剔除
  • HIR被命中时,将其提升为LIR并移动到S顶部,如果存在于Q中,则将其从Q中剔除。将S底部的LIR剔除出S(需要进行栈剪枝),降级为非驻留HIR,写入Q的头部(如果没能及时被再次访问会被彻底剔除)。

数据块在S中的位置就是R值,新数据和被命中的LIR块写入S头部就是为了动态维护R值,当一个HIR块提升为LIR时,需要淘汰一个LIR块,上文说了淘汰的策略是对比IRR值,当某个HIR的IRR值小于某个LIR的IRR值时,则将这两个数据块的状态互换。LIRS抽象的点在于并没有看到IRR被维护,也就无法进行对比,这也是其设计的巧妙之处。

IRR是由R值计算得出,具体的计算方式上文有提及: 上一个R值 - 命中时的R值(0),当一个块被命中时,其IRR值也就立即刷新。 要对比IRR值其实可以通过对比R值来实现,如果一个HIR块的R值小于某个LIR块的R值,那么当这个HIR块被命中时,其IRR值肯定小于这个LIR块的下一个IRR值。所以剔除LIR时简单的比较R值就行,这也是上面剔除逻辑中,直接剔除S底部的LIR的原因,因为S底部的LIR其R值最大。

当剔除S底部的LIR(或底部LIR命中后移动到S顶部)后,S底部的数据块可能是HIR块,在LIRS的设定中要将底部的HIR块也移除出S,保持S底部始终是LIR,这被称为栈剪枝。 进行栈剪枝的目的在我看来是为了维护HIR块和LIR块之间IRR值比较的环境, 用热的HIR去顶掉最老的LIR,S底部的HIR显得突兀需要移除,其IRR本身也很大,且因为没有LIR可比较,没有机会变成LIR。

从数据访问的角度来描述以下算法细节:

  1. 数据块不存在于缓存中。 为该数据分配空间,并写入Q的头部,写入S的头部。如果Q空间满了,则剔除掉Q尾部的数据块,如果数据块也在S中,则将其状态改为非驻留HIR,不然彻底移出缓存。如果S的空间到达上限,则移除S底部的HIR,写入Q的头部。

  2. 如果访问的是LIR,则将LIR块移动到S头部,如果LIR位于S底部,则需要栈剪枝

  3. 如果访问的是HIR,则分为几种情况:

    • 如果HIR同时存在于S和Q中,则将HIR块提升为LIR,从Q中移除,将S底部的LIR降级为HIR,写入Q的头部,需要栈剪枝
    • 如果HIR只在于Q中,则将保持其HIR状态,并写入S顶部,移到Q头部
    • 如果HIR只位于S中,则将其提升为LIR,移入S顶部,将S底部LIR剔除,移入Q顶部,需要栈剪枝

LIRS中没有对S的大小进行限制,这在极端情况下会导致S大小不可控,弥补措施是给一个最大数量限制,当超过限制时,往S中写入一个数据之前要先剔除一个S底部的HIR块。

深感水平有限,未能以让自己满意的程度完成本文,后续待恶补。 LIRS的难度适中,实现的过程充满乐趣,如果你正在繁琐的搬砖开发中陷入枯燥迷惘,根据论文实现一遍LIRS是个不错的选择。

参考资料

共收到 2 条回复
jasl 将本帖设为了精华贴 05月15日 01:25

调研过相关知识。没有引入 LFRU 和 ARC 直接总结 LIRS 感觉有些突兀。

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册