论文笔记：[FAST'03] ARC: A Self-Tuning, Low Overhead Replacement Cache

发表于 更新于 分类于

ARC是一种缓存替换算法，在很多种负载环境的表现优于常用的LRU算法，并且实现难度和算法复杂度与LRU近似。

ARC算法具有以下优良特性：

  1. 在recency和frequency之间持续的进行动态（在线）调整

  2. 无需事先指定特别的参数（先验知识）

  3. 具有全局优化策略（意译，不确定翻译的对不对，原文empirically universal，note说明该词出自LZ77的论文）

  4. 可以（在某种程度上）抵抗线性扫描（scan-resistant）

原论文中花费了很多篇幅介绍之前人们试图提出比LRU更好的算法的一些工作，并进行了一番对比，本文限于篇幅和精力略过这部分内容。

基本思想

LRU的问题在于其只考虑了recency而完全没有考虑frequency。一般而言，保存freqency信息的代价又比较大。ARC的最根本的思路（以下称为DBL）在于使用2个LRU，其中一个$L_1$存放最近被访问1次的数据（也就是传统的LRU），另一个$L_2$存放最近被访问2次及以上的数据。这一近似减少了维护frequency的成本。最终目标是尽可能维持$|L_1| = |L_2| = c$，但是论文中并没有解释为什么要这么做。（总是能保持$|L_1| + |L_2| = 2c$，如果$|L_1| < c$时会优先淘汰$L_2$中的内容给$L_1$腾地儿）

我们把整个Cache分为以下2个部分：

  1. Cache Directory

  2. Cache Item

其中Cache Directory用于进行索引，Cache Item真正表示在缓存中的内容。对于传统LRU算法而言，以上2者的大小是一样的（Directory索引的项的数量和真正在缓存中的内容的数量）。对于上面提到的DBL而言，以上2者的大小也是一样的，为$|L_1| + |L_2| = 2c$。特别的，在DBL中，$L_1$就是一个传统的LRU，其大小为$c$。

上面提到的DBL算法的问题是使用了2倍于LRU的空间，其效果比LRU好是显然的，能不能使用和LRU一样多的空间得到更好的效果呢？一个直接的想法是使用$2c$的Cache Directory但是只保留$c$个Cache Item常驻内存，那么在这$2c$个索引项中如何取舍就是一个问题。如[figure-1]所示，我们将$L_1$和$L_2$分别拆分为$T_1, B_1, T_2, B_2$。直觉上，$T_1$比$B_1$更有价值，$T_2$比$B_2$更有价值，如果我们能够维持$|T_1| + |T_2| \le c$，则应当将$T_1 \cup T_2$中的元素保留在Cache中。

ARC

剩下的问题，在于如何在$L_1 \cup L_2$中调节$T_1 \cup T_2$的位置（即调节$|B_1|$和$|B_2|$），以及如何在$T_1 \cup T_2$中调节两者的大小分配。特别的，当$|L_1| = |T_1| = c$时，该算法等价于LRU，也就是说如果调节得当的话，该算法至少能做到和LRU一样好。

ARC算法

由于我们要求保持性质$|L_1| = |L_2| = c$，因此当调节$T_1$和$T_2$的关系时，实际上就调节了$T_1 \cup T_2$在$L_1 \cup L_2$中的位置。直觉上相当于在$L_1$和$L_2$中间的地方有一个固定大小的滑块，我们在调节这个滑块的位置。不妨令$|T_1| = p$，则$|B_1| = |T_2| = c - p$且$|B_2| = p$。

接下来，我们需要思考一下$B_1$和$B_2$对我们而言意味着什么。回想上面提到的DBL，$L_1$意味着最近只命中了1次的缓存项索引，其中$T_1$是我们保留在缓存中的内容，$B_1$是我们没有保留在缓存中的内容。因此，如果查询请求命中了$B_1$，意味着我们应当把这次命中当作命中了$L_1$来看，并且相应的，说明我们的$|T_1|$可能小了，没能将这次命中的数据存起来。论文中，当$|B_1| \gt |B_2|$时，$p$增加1，当$|B_1| < |B_2|$时，$p$增加$|B_2| / |B_1|$，但是论文中没有解释为什么这么设计。

完整的ARC算法如[figure-2]所示，其中Case I-III对应于DBL命中的情况，Case IV对应于DBL未命中的情况。

ARC Algorithm

问题回顾

之前提到了一些问题，在此继续探讨一下。

$L_1$和$L_2$的大小是否可以调整

在目前的设计中，$|L_1| = |L_2| = c$，由于我们最多只保留$|T_1| + |T_2| = c$项内容，在极端情况下$|L_1| = |T_1| = c$，此时进一步增大$L_1$也不能再进行什么调整了（受限于Cache大小），从这个角度来看在$L_1$和$L_2$之间进行调整可能是没什么意义的。

但是在论文中特别提到了 E. Extra History，讨论了这样一个问题：

An interesting question is whether we can incorporate more history information in ARC to further improve it.

论文中给出了一种利用额外的空间的方法，似乎暗示了这么做是有用的，但是没有论证对比这一方法的效果如何。

$p$的调整为什么不是固定的

推测是因为当$B_1$小的时候命中$B_1$是比较困难的，要对此做一个加成。但是为什么这么做论文并没有给出一个解释，也没有什么对比。

Scan-Resistant

直觉上ARC是可以抵御扫描Pattern的请求的，因为ARC不仅考虑了recency，还考虑了frequency。具体而言，有以下2个原因：

  1. 扫描会刷新$L_1$的内容，但是不会影响$L_2$的内容

  2. 扫描会更多的命中$B_2$（相较于$B_1$），因此会进一步减小$|T_1|$，进而使得扫描造成的影响比单纯考虑第1点更小

不总结总觉得少点什么

总的来说，ARC算法通过一种比较巧妙的方法，在不显著增加实现成本和算法时间复杂的情况下，较为显著的改进了LRU算法。使用LRU来承载最近遇到2次以上的数据来近似捕获frequency信息是一大亮点。动态平衡的方案直觉上有效，但是细节上缺乏有力的论证，不确定是不是一个最优的算法。对于动态变化的数据而言，动态平衡的算法优于静态的算法是可以预期的。

References

  • [1] MEGIDDO N, MODHA D S. ARC: A Self-Tuning, Low Overhead Replacement Cache[C]//CHASE J. Proceedings of the {FAST} ’03 Conference on File and Storage Technologies, March 31 - April 2, 2003, Cathedral Hill Hotel, San Francisco, California, {USA}. USENIX, 2003.

  • [2] NIMROD MEGIDDO, MODHA D S. one up on LRU[J]. ;Login:, 2003, 28(4).