ARC：ghost 列表给出的反事实信号

淘汰策略是在猜未来 §4 给出的两个失效场景是对称的：扫描打死 LRU，热点迁移打死 LFU。一个显然的想法是把两者各留一半容量。但一半是多少，取决于当前流量长什么样，而流量会变。

ARC 的回答是：不要预设这个比例，让缓存自己测出来。

1 · 先把缓存切成两段

ARC 把缓存内容分成两个 LRU 列表：

• $T_1$ 装「进来之后只被访问过一次」的 key
• $T_2$ 装「进来之后被访问过两次或更多」的 key

新 key 一律先进 $T_1$。$T_1$ 里的 key 再被访问一次就升进 $T_2$；$T_2$ 里的 key 被访问只是挪到 $T_2$ 的最新端。两个列表各自按 LRU 排序，合起来的大小不超过容量 $c$。

这个切分本身已经解决了扫描问题：扫描带进来的一次性 key 全部堆在 $T_1$，它们相互挤，挤不到 $T_2$ 去。2Q 与 LRU-2 走的都是这条路。剩下的问题是 $T_1$ 应该多大——留太小则突发的新热点还没来得及升级就被冲掉，留太大则扫描又能把 $T_2$ 压缩到没有。

2 · 两个只存 key 的 ghost 列表

ARC 多做的一步是记住刚被淘汰的是谁：$T_1$ 淘汰掉的 key 进 $B_1$，$T_2$ 淘汰掉的进 $B_2$，这两个只存 key、不存 value 的列表叫 ghost 列表。它们不占缓存容量，只占一点元数据空间：$|B_1| + |B_2| \le c$。

一个参数 $p$ 表示 $T_1$ 的目标大小，$T_2$ 的目标大小就是 $c - p$。淘汰时按 $p$ 决定从哪一边取：$|T_1| > p$ 就淘汰 $T_1$ 的最旧项，否则淘汰 $T_2$ 的最旧项。

3 · ghost 命中提供的是反事实信号

在 $B_1$ 里命中意味着一件很具体的事：这个 key 曾经在缓存里，是从 $T_1$ 被淘汰出去的，而现在它又被访问了。换句话说，若当初 $T_1$ 再大一点，这次访问就会是命中。这是一条反事实证据，而不是一个启发式猜测——它直接量出了「上一次的切分点定错了」。

ARC 据此调整：

• $B_1$ 命中，说明 recency 那一侧吃亏了，$p$ 增大，增幅是 $\max(1, |B_2| / |B_1|)$
• $B_2$ 命中，说明 frequency 那一侧吃亏了，$p$ 减小，减幅是 $\max(1, |B_1| / |B_2|)$

增减幅度里的那个比值是配平项：ghost 列表短的一侧，每一次命中携带的信息更强，所以挪得更多。命中之后这个 key 从 ghost 移进 $T_2$（它至少被访问过两次了），并按新的 $p$ 淘汰一项腾出位置。

整套规则不需要任何关于 workload 的先验，也没有需要人调的参数。这是 ARC 在 2003 年被视为突破的原因：此前的自适应方案都要一个衰减系数或一个窗口长度。

4 · p 的轨迹

实测四种 workload（容量 200、20000 次访问）里 $p$ 的行为差别很大：

前两行 $p$ 一路探到六十上下又回落到近零：ARC 试过给 recency 更多容量，$B_2$ 的命中把它推了回去，最终几乎整个缓存都给了 $T_2$。第三行相反，热点每 3000 次访问整批换一次，新 key 源源不断，$p$ 稳定在 93——接近对半开。第四行最干净：纯循环扫描下没有任何 key 被访问第二次，$T_2$ 始终为空，两个 ghost 列表一次也没命中过，ARC 退化成 $T_1$ 一条队列的 FIFO。

5 · 代价：没有便宜的路径

ARC 的命中率在四种 workload 上都不低于 LRU 与 LFU 中较好的那一个，代价写在元数据写入量上。实测 Zipf、混合、突发热点三种 workload 下 ARC 的写入量都是每次访问 5.94 次，三位有效数字完全一致。

这个巧合有原因。ARC 的每一次操作都要动链表：命中要把 key 挪到 $T_2$ 的最新端，miss 要在 REPLACE 里把一项从 $T$ 挪进 ghost。没有 CLOCK 那种「置位就完事」的便宜路径，也没有 FIFO 那种「什么都不做」的路径。于是写入量恒等于 $6 \times (\text{访问次数} - \varepsilon) / n \approx 5.94$，与命中率无关。只有纯循环扫描是例外，那种情形下 ARC 走的是一条不含 REPLACE 的特殊分支，写入量为 0。

另有两项工程上的代价：ghost 列表要为额外 $c$ 个已被淘汰的 key 保存 hash 表项与链表结点；四个列表加一个 $p$ 的状态机，实现复杂度显著高于 CLOCK。ZFS 用了 ARC，PostgreSQL 曾经用过又换回了 clock sweep，公开的理由是专利风险。CAR 是同一批作者给出的 CLOCK 版 ARC，把链表换成两个环，命中路径只置位。

6 · 参考文献

1. Megiddo, N., & Modha, D. S. (2003). ARC: a self-tuning, low overhead replacement cache. FAST 2003, 115–130.
2. Megiddo, N., & Modha, D. S. (2004). Outperforming LRU with an adaptive replacement cache algorithm. Computer, 37(4), 58–65.
3. Bansal, S., & Modha, D. S. (2004). CAR: Clock with Adaptive Replacement. FAST 2004, 187–200.
4. Johnson, T., & Shasha, D. (1994). 2Q: a low overhead high performance buffer management replacement algorithm. VLDB 1994, 439–450.