ARC：Adaptive Replacement Cache（论文笔记）

1 分钟阅读

发布于：

论文：ARC: A Self-Tuning, Low Overhead Replacement Cache（Megiddo, Modha，FAST 2003）

ARC 是存储系统里非常经典的缓存替换算法之一（ZFS 采用）。它的核心价值不是“命中率比 LRU 高一点”，而是提供了一种更工程化的能力：在工作负载从 recency（近期性）切换到 frequency（频率性）时，缓存策略能够自适应调整，避免 LRU 在某些扫描/混合负载下被“拖垮”。

本文按“问题 → 结构 → 调参机制 → 复杂度/实现 → 观测与调优”做笔记，图用 ASCII，避免 Mermaid。

1. 背景：LRU 为什么会在扫描场景失效

LRU 假设“最近访问的未来更可能被访问”。这在许多负载成立，但在扫描（scan）场景会出现典型问题：

  • 大范围顺序扫描会把缓存全部替换掉（cache pollution）
  • 扫描结束后，原本的热数据已被逐出，命中率暴跌

同时，纯 LFU（按频率）又容易被“历史热点”绑架，对近期热点响应慢。

ARC 的目标：同时兼顾 recency 与 frequency，并能自动在两者间调节。

2. ARC 的数据结构：两条队列 + 两条幽灵队列

ARC 维护四个列表（通常按 LRU 顺序组织）：

  • T1：最近访问过一次的缓存条目（recency）
  • T2：最近访问过至少两次的缓存条目（frequency）
  • B1：T1 的幽灵条目（只保存 key，不保存数据）
  • B2：T2 的幽灵条目（只保存 key，不保存数据）

直观示意：

Cache (data):
  T1: [MRU ... LRU]   (seen once)
  T2: [MRU ... LRU]   (seen multiple times)

Ghost (keys only):
  B1: [MRU ... LRU]   (recently evicted from T1)
  B2: [MRU ... LRU]   (recently evicted from T2)

其中缓存容量为 (c)，ARC 维护一个自适应参数 (p)：

  • 目标：T1 的大小靠近 (p)，T2 的大小靠近 (c - p)
  • (p) 会根据命中在 B1/B2 的情况动态调整

3. 命中与插入规则（高层）

3.1 命中在缓存（T1/T2）

  • 命中 T1：说明“近期性”有效，同时该条目获得第二次访问 → 移到 T2 的 MRU
  • 命中 T2：继续保持在 T2 的 MRU
hit(T1): move to T2 MRU
hit(T2): move to T2 MRU

3.2 命中幽灵（B1/B2）：用于调参

命中幽灵的含义是“最近被逐出的东西又被访问了”，说明驱逐策略可能偏了：

  • 命中 B1：说明 T1（recency）不够大，应该提升 p（多给 recency 配额）
  • 命中 B2：说明 T2（frequency）不够大，应该降低 p（多给 frequency 配额）

调参直觉：

if hit(B1): p = min(c, p + delta)
if hit(B2): p = max(0, p - delta)

delta 通常与队列大小比例有关（论文中有更细的建议），关键是：调整幅度随工作负载变化自动收敛。

4. Replace()：统一的驱逐函数

ARC 的实现核心通常被归结为一个 replace()：

  • 当需要腾出空间时，根据当前 p 与 T1/T2 的大小决定从哪边驱逐

直觉规则（简化）：

if |T1| > p:
  evict from T1 LRU -> move key to B1 MRU
else:
  evict from T2 LRU -> move key to B2 MRU

含义：

  • 如果 recency（T1）超出目标 p，就从 T1 驱逐；
  • 否则从 frequency（T2）驱逐。

5. 为什么需要幽灵队列：让“失败模式”可观测、可反馈

没有幽灵队列时，很难知道“刚驱逐出去的东西是否马上又被需要”。

幽灵队列提供了一种低成本信号：

  • B1 命中：recency 被低估（需要更大的 T1）
  • B2 命中：frequency 被低估（需要更大的 T2）

这让 ARC 成为“自调参”算法，而不是固定策略。

6. 复杂度与工程实现要点

6.1 时间复杂度

ARC 的关键操作是：

  • 哈希查找 key 是否在 T1/T2/B1/B2
  • 从双向链表移动节点、从尾部驱逐

因此单次访问的摊还复杂度接近 O(1)。

6.2 空间开销

幽灵队列只存 key（或 key 的哈希/指纹），开销通常可控，但要注意：

  • key 很大时需做压缩存储
  • 幽灵队列大小一般与 cache 容量同量级（最多 2c 级别的 key 记录）

6.3 并发与锁

在存储系统（例如文件系统缓存）中，ARC 往往处于高并发路径：

  • 全局锁会成为瓶颈
  • 常见做法：分段锁、每 CPU/每 NUMA 局部队列 + 周期性平衡（实现更复杂）

7. 工作负载直觉：ARC 在哪里赢

7.1 扫描 + 热点混合

扫描会让 LRU 发生污染；ARC 会通过 B1/B2 的反馈把 p 调小（增加 T2），避免热点被挤掉。

7.2 热点迁移

热点从 A 切到 B：

  • 纯 LFU 容易被 A 的历史频率锁死
  • ARC 的 recency 侧（T1）允许新热点快速进入，并通过第二次命中晋升到 T2

8. 工程观测指标（建议）

若系统实现了 ARC（或类似机制），建议暴露以下指标用于诊断：

  • T1/T2/B1/B2 当前长度
  • 参数 p 的时间序列（收敛情况）
  • 命中率拆分：hit(T1), hit(T2), hit(B1), hit(B2)
  • replace() 驱逐来源：evict_from_T1 vs evict_from_T2
  • 负载维度：顺序读比例、随机读比例、热点 key 分布变化

通过这些指标，可以把“缓存策略是否被扫描拖垮”从现象变成可观测信号。

9. 与其他策略的关系（简表）

策略 优点 典型失败模式
LRU 简单、近期性强时效果好 扫描污染、混合负载下热数据被挤掉
LFU 频率性强时稳定 对热点迁移反应慢、历史热点绑架
2Q 通过两个队列降低扫描污染 参数依赖经验，适配性有限
ARC 自适应 recency vs frequency 实现更复杂，需要维护更多结构与指标

10. 小结

ARC 的经典性来自“可自适应”这一工程属性：用幽灵队列把策略偏差变成信号，再用参数 p 把信号反馈到驱逐决策里，从而在扫描/混合/迁移负载下比单纯 LRU 更稳。对于存储系统而言，这种“稳定性”往往比极限命中率更重要，因为它直接影响尾延迟与整体吞吐的可预测性。