/

页面置换算法:LRU,LFU与ARC详解

该篇文章首发于boyn.top,转载请声明

什么是缓存

在软件开发的各个环节中,我们为了速度,通常都会使用一些缓存来使得执行速度加快,常见的有浏览器对页面的本地缓存,CDN,还有DNS中的缓存,这些是网络中的缓存,同样,计算机底层也有很多地方用到了缓存,根据速度的不同,将计算机的存储结构分为了多层,从而构成了大小不同,速度不一的缓存体系.

image-20200327180707988

页面置换算法

缓存是非常好用,并且可以节省大量的时间,但是我们要知道,为了将数据缓存下来,我们同样需要空间来对它们进行管理.但是任何计算机的空间都是有限的,并且缓存下来的内容同样会遵循28定律(80%的缓存内容只会被访问一次,20%的缓存内容会被多次访问)

所以为了不浪费存储空间,科学家提出了几种页面置换算法,它们的作用都是在有限的大小下,在不断有新内容进入缓存的情况下,执行不同的淘汰策略将之前的部分缓存内容删除,而不同的页面置换算法往往会有不同的淘汰策略和缓存加入策略.

最常见的页面置换算法有LRU,LFU和ARC算法,如图.在下面我们将会详细介绍这三种算法的区别

image-20200407211449110

LRU算法

LRU,即Least Recently Used的缩写,是指最近最少使用的意思.它的行为描述并不复杂,简单来说,当缓存的页面总数不超过其限制时,可以一直将页面缓存下来,而当页面数达到限制后,就会将最近最少使用的页面淘汰出去放入新的页面,从而将页面限制在一定数量内.

其实现并不难,我们可以这样来描述:LRU算法的底层数据结构是一张Map与一个双向链表,Map负责保存数据,而链表中则持有Map中的数据的引用.为什么要这样做呢?这个就和LRU中最近最少使用的这个特性有关了.我们为了在淘汰时选出最近最少使用的页面,可以使用一个双向链表来记录缓存被调用的顺序

我们来看看加入一个页面时的步骤

  1. 插入一个新的元素时,直接将其放入Map中,并将其插入到链表的头结点
  2. 插入后查看页面数量是否超过上限,如果超过了,将链表尾部的元素进行删除,并删除对应在Map中的数据
  3. 如果没有超过上限,则不用做什么操作

加入一个页面的步骤是十分简单的,我们将新加入的页面放在头结点中,而链表尾节点对应的就是最近最少使用的页面,但是这个页面是怎么变成最后一个页面的呢?我们来看看读取缓存的流程

  1. 传入一个Key,从Map中获取对应的值
  2. 将这个值的引用对应的链表节点移到头部
  3. 返回这个值

同样的,读取流程也并不复杂.在其中,有一个很关键的步骤在于会将访问到的值转移到链表的头部.这样一来,如果一个页面一直没有被访问到,就会逐渐地被移到链表的尾部,从而成为最近最少使用的页面

同时,这个算法也是十分高效的设计.Map中进行数据的插入,读取,删除都是O(1)的复杂度,同时,在双向链表进行头尾节点的插入和删除也是O(1)的复杂度.

LFU算法

相比起LRU以时间作为淘汰页面的标准,LFU是以使用频次作为淘汰标准的,每一次淘汰页面的时候,都会优先淘汰掉使用频次最少的页面.LFU算法的底层数据结构与LRU算法十分相似,都是一个Map与一个双向链表,Map同样用于保存数据,而不同的是,LFU算法中的双向链表保存的是一个复合结构,包含表示使用频率的int值和这个频次的页面引用

image-20200408113255455

同样,我们来看看LFU算法中,缓存的存取过程

当我们存放一个元素的时候:

  1. 将这个元素放入包含实际数据的Map中
  2. 检查元素个数是否大于限制个数,如果大于,则执行淘汰策略
  3. 淘汰时,从频次列表中的头节点开始遍历,其items中有节点为止,将遍历items将第一个元素删除
  4. 将元素的引用放入引用频次链表的头节点的items中,表示未被引用

而当我们取一个元素的时候:

  1. 将这个元素从Map中取出
  2. 获取到这个元素所在的listElement,并将这个元素在对应listElement中删除
  3. 获取到listElement的下一个Element,如不在则创建,表示引用频次+1,将元素放入其中

我们可以看到,LFU算法的核心在于引用频次的列表,他表示一个元素被取出的次数,以这个次数为依据,在数量过多的时候删除引用次数较少的页面.可能很多同学在实现的时候有一个误区,就是会使用数组或者纯双向链表,将所有元素排成有序的一列从而删除最末尾的元素,这样的实现思路效率比较低下,每一次插入和存取都要对这个线性结构维护,比如数据的插入,位置交换等等,这会带来很大的维护成本,并且仔细想想就知道我们其实不需要有序,我们只需要按频次分类,所以上图这样的双向链表+Map的组合是很高效的.

ARC算法

关于ARC算法,在网上的资料不太多,但是这并不妨碍它是一个优秀的缓存算法.ARC的全称是Adjustable Replacement Cache,自适应缓存替换算法.简单来说,他结合了LRU与LFU的优点,形成了一个可以根据业务需求动态调整缓存淘汰方式的缓存算法.

我们知道,LRU算法是应用比较广泛的缓存算法,但是他有一个缺点,就是无法对大面积的顺序读产生很好的缓存效果.当我们一次性地大量读取某些页面时,这些页面缓存下来时会占据很多空间,把之前的缓存结果淘汰掉,但是这些页面可能仅仅读了一次,而真正多次读取的页面被淘汰掉了,这是一种弊端.

而LFU的缺点在于其变化比较慢,当我们改变了访问模式时,它的适应能力并不高.

而为了补足这两者的缺点,就产生了ARC算法.由于ARC算法比较抽象,我同时将这个算法的介绍链接放在这里以免我说的不够清楚

我们先了解ARC中所用到的数据结构:

  • MRU与MFU列表:分别是Most Recently Used和Most Frequently Used.即最近使用和最常使用的缓存列表
  • Ghost MRU与MFU 列表:从MRU和MFU列表中淘汰的部分节点,它们的引用被转移到Ghost列表中.
  • Map:同样地,我们为了存储数据,同样要使用一个Map进行缓存数据的放置

那么我们现在来看看ARC算法的主要流程吧.

  1. 首先在刚刚开始的时候,我们设置Map的大小为8,4个列表的大小各为4

image-20200408134347844

  1. 读入了一个页面A,我们将其放入MRU列表中

image-20200408134423955

  1. 再次读入了一个页面B,我们仍然将其放入MRU中,由于这个页面B是新读的,所以他会处于MRU列表的头部

image-20200408134534935

  1. 假设在此时,我们再次读页面A,由于其已经在缓存中,所以可以快速地读到.同时,由于我们读入了两次页面A,所以认为这个页面”常常被读到”,所以将其引用放入MFU列表中.这样一来,虽然Cache中只有两个元素,但是页面A会有两次引用放在不同的列表中

image-20200408134845905

  1. 假设我们经过多次读入后,MRU和MFU列表,以及缓存Map都被填满了

image-20200408134921808

  1. 而当缓存满了之后,我们再次读入一个新的页面时,则会删除MRU列表中最后一个元素,将这个元素的数据放入GhostList中

image-20200408135108176

  1. 我们要注意,在此时,被淘汰的页面虽然已经不在缓存中,当时它的引用并没有消失,而是放在了MRU的GhostList中

image-20200408135205636

  1. 假设这个时候,我们读入了刚刚被淘汰的页面,会在GhostList中被命中.我们称其为”幽灵命中”,于是将其放回MRU列表中

image-20200408135944240

  1. 但是MRU列表只有4个,并不够放,所以我们将MRU扩大一格,同时为了总量一定,将MFU列表减少一格.同样地,MFU列表也有这样的行为来进行伸缩.

image-20200408140555350

从上面的流程我们看到,ARC算法可以有效地平衡两种模式,从而在不同的缓存读取模式下,进行性能的权衡.比如我们如果经常读取同样的页面,那么MRU列表的容量就相对比较小,MFU列表就相对比较大.而如果我们总会随机地读入数据且很少重复读取,那么MRU列表容量就会变得比较大.

关于图片和转载

知识共享许可协议
本作品采用知识共享署名 4.0 国际许可协议进行许可。 转载时请注明原文链接,图片在使用时请保留图片中的全部内容,可适当缩放并在引用处附上图片所在的文章链接,图片使用 Sketch 进行绘制,你可以在 技术文章配图指南 一文中找到画图的方法和素材。