[论文笔记]Arc: A Self-Tuning, Low Overhead Replacement Cache

Arc 是一种 LRU 改进算法，在很多负载环境中性能优于常用的 LRU 算法。

基本思想 #

我们需要先了解一下什么是 recency，什么是 frequency。recency 是最近访问时间，frequency 是访问频率。LRU 只基于了 recency，LFU 基于 frequency。所以这两个算法都没有同时利用好 frequency 和 recency，所以在面对不同 workload 的时候性能会有所下降。ARC 其实就是结合了 recency 和 frequency。

DBL #

作者在论文中先引入 DBL 这个算法。 DBL 提出用两个 LRU 来缓存。一个为 L1，用来存放首次访问的数据，另外一个为 L2，用来存放至少访问了两次的数据。如果一个 LRU 的大小是 c，则总的缓存大小是 2c。

Fig.1 是 DBL 的算法。

也就是说，如果 x 在 L1 或 L2 中，则将 x 移到 L2 的 MRU 端。如果都不在，分为两种情况：第一种是 L1 有 c 个缓存项了。则需要删掉 L1 中的一个页面，然后将 x 放到 L1 的 MRU 端。第二种情况是L1 少于 c 个缓存项，但是如果总的缓存项等于 2c，则需要删掉 L2 LRU 端的项来存放 x。如果小于 2c，则直接插入 L1 的 MRU。（不清楚 LRU 和 MRU 分别指什么的可以看 Fig 2）