缓存算法 #04：ARC（自适应替换缓存）

ARC（Adaptive Replacement Cache）由 IBM 于 2003 年提出，通过同时维护"最近使用一次"和"最近使用多次"两条 LRU 链，并根据实际命中情况自动调整两者的比例，无需人工调参即可适配不同工作负载。ZFS、Oracle Database 均采用 ARC。

相关文章：LRU（最近最少使用） · LFU（最少使用频率） · W-TinyLFU 与 Caffeine

目录

LRU 与 LFU 的根本矛盾

工作负载 A（时间局部性强，如热点 Key 反复访问）：
  LRU 表现好：最近用的很快再用
  LFU 表现差：新热点需要积累频率才能保住缓存位

工作负载 B（频率局部性强，如稳定高频访问集合）：
  LRU 表现差：扫描操作污染缓存，驱逐高频页
  LFU 表现好：高频页稳固占据缓存

现实中工作负载会切换：
  先是工作集稳定访问（LFU 好），突然来一次顺序扫描（LRU 好）
  没有任何静态策略能同时应对两种场景

ARC 的解法：
  同时跑一个 LRU 链和一个 LFU 链
  用"ghost hit"（幽灵命中）信号自动感知当前工作负载特征
  动态调整两者的分配比例

四个链表的设计

ARC 维护四个链表，逻辑上排列如下：

← 回收端                                          活跃端 →
[  B1 (ghost)  |      T1 (recency)      ] [ T2 (frequency)  |  B2 (ghost)  ]
                ↑                                              ↑
             驱逐发生在 T1/T2 的边界                      T2 的活跃端有最频繁访问的页

T1（Target 1，近期只用过一次的页）：
  新加载的页进入 T1 头部
  T1 大小目标：p 个槽（p 是自适应参数）

T2（Target 2，近期用过多次的页）：
  从 T1 再次被命中的页升级到 T2 头部（相当于 LFU "频率>=2"）
  T2 大小目标：capacity-p 个槽

B1（Ghost of T1，T1 的幽灵链表）：
  从 T1 被驱逐出缓存的页，只保留 key（不保留 value）
  记忆"曾经加载过但被驱逐"的历史
  B1 大小 = |T1|（动态，最多 capacity 个）

B2（Ghost of T2，T2 的幽灵链表）：
  从 T2 被驱逐出缓存的页，只保留 key
  B2 大小 = |T2|（动态）

合并起来：
  缓存容量 c = |T1| + |T2|（真正存 value 的页数）
  额外幽灵容量：|B1| + |B2| ≤ c（纯 key，内存极少）
  自适应参数 p：0 ≤ p ≤ c，控制 T1 的目标大小

目标参数 p 的自适应

p 的含义：我希望 T1 占缓存的比例（p/c）
  p 大 → T1 大 → 偏向 LRU（时间局部性）
  p 小 → T2 大 → 偏向 LFU（频率局部性）

自适应规则（根据 ghost hit 调整）：

命中 B1（T1 的幽灵命中）：
  "这个页之前被驱逐出 T1 后又被访问了"
  → 说明 T1 太小，驱逐了不该驱逐的页
  → p 应该增大：偏向 LRU
  delta = max(1, |B2| / |B1|)
  p = min(p + delta, c)

命中 B2（T2 的幽灵命中）：
  "这个页之前被驱逐出 T2 后又被访问了"
  → 说明 T2 太小，频繁页被驱逐
  → p 应该减小：偏向 LFU
  delta = max(1, |B1| / |B2|)
  p = max(p - delta, 0)

直觉：哪个幽灵链表命中，说明哪类页被过早驱逐，
      就增大对应类的目标大小

完整伪代码

class ARCCache:
    c:  int    // 缓存容量
    p:  int    // T1 的目标大小，0 <= p <= c
    T1: LinkedHashMap   // 最近访问一次（按 LRU 顺序）
    T2: LinkedHashMap   // 最近访问多次（按 LRU 顺序）
    B1: LinkedHashSet   // T1 的幽灵（只存 key）
    B2: LinkedHashSet   // T2 的幽灵（只存 key）

replace(in_B2) — 找驱逐目标

// 从 T1 或 T2 中驱逐一个页，移入对应鬼链表
// in_B2: 当前请求的 key 是否在 B2 中（影响驱逐决策）
replace(in_B2):
    t1_size = len(T1)

    if t1_size >= 1 and (t1_size > p or (in_B2 and t1_size == p)):
        // 从 T1 的 LRU 端驱逐（T1 超出目标，或 T2 更需要空间）
        victim = T1.removeLRU()       // T1 尾部（最久未用）
        B1.addMRU(victim.key)         // 加入 B1 幽灵
    else:
        // 从 T2 的 LRU 端驱逐
        victim = T2.removeLRU()
        B2.addMRU(victim.key)

get(key)

get(key):
    if key in T1:
        // T1 命中：升级到 T2（用过多次了）
        node = T1.remove(key)
        T2.addMRU(node)
        return node.value

    if key in T2:
        // T2 命中：在 T2 内部移到 MRU 端
        T2.moveToMRU(key)
        return T2[key].value

    return -1    // 缓存未命中

put(key, value)

put(key, value):
    // 情况1：T1 或 T2 命中（更新 value 即可）
    if key in T1:
        node = T1.remove(key)
        node.value = value
        T2.addMRU(node)
        return

    if key in T2:
        T2[key].value = value
        T2.moveToMRU(key)
        return

    // 情况2：B1 幽灵命中（曾在 T1 被驱逐，现在重新访问）
    if key in B1:
        // 增大 p：T1 目标扩大
        delta = max(1, len(B2) // len(B1))   // 整除，防 len(B1)=0
        p = min(p + delta, c)
        replace(in_B2=False)
        B1.remove(key)
        T2.addMRU(Node(key, value))    // 直接进 T2（表示"上次就该留的"）
        return

    // 情况3：B2 幽灵命中（曾在 T2 被驱逐，现在重新访问）
    if key in B2:
        // 减小 p：T2 目标扩大
        delta = max(1, len(B1) // len(B2))
        p = max(p - delta, 0)
        replace(in_B2=True)
        B2.remove(key)
        T2.addMRU(Node(key, value))
        return

    // 情况4：全新 key（T1/T2/B1/B2 均无）
    total = len(T1) + len(B1)
    if total == c:
        if len(T1) < c:
            // B1 有幽灵：驱逐 B1 最旧的幽灵，腾出空间
            B1.removeLRU()
            replace(in_B2=False)
        else:
            // T1 已满（B1 为空）：直接驱逐 T1 最旧的
            T1.removeLRU()
    elif total < c and len(T1)+len(T2)+len(B1)+len(B2) >= c:
        if len(T1)+len(T2)+len(B1)+len(B2) >= 2*c:
            B2.removeLRU()    // 幽灵总量超限，清理 B2
        replace(in_B2=False)

    // 新页进入 T1
    T1.addMRU(Node(key, value))

执行追踪

capacity=4，初始 p=2，演示工作负载切换时 p 的变化：

阶段一：顺序扫描（页 1,2,3,4,5,6...，每页只访问一次）
  → 所有页只进 T1，T2 为空
  → 没有 B2 幽灵命中，p 不变（无需 T2）

阶段二：热点访问（页 1,2,1,2,1,2...，反复访问 1 和 2）
  → 页1、页2 进 T1 后被再次命中 → 升级到 T2
  → 但 T1 目标 p=2，T2 目标=2
  → T2 空间够用，缓存命中良好

阶段三：扫描 + 热点混合
  → 新扫描页进 T1，挤占热点页的位置
  → 热点页从 T2 被驱逐 → 进入 B2
  → 下次再访问热点页 → B2 命中！
  → p 减小，T2 目标扩大，为热点页留更多空间
  p: 2 → 1 → 0（偏向 LFU，保护高频热点）

阶段四：工作集改变（新的热点替换旧热点）
  → 新页进 T1，从 T1 被驱逐进 B1
  → 这些新页再次被访问 → B1 命中！
  → p 增大，T1 目标扩大
  p: 0 → 1 → 2（偏回 LRU，接纳新热点）

复杂度分析

异常场景

p 越界保护

p = min(p + delta, c)   // 上界 c
p = max(p - delta, 0)   // 下界 0

边界含义：
  p=0：完全偏向 LFU，T1 目标大小为 0
       但 T1 仍然接受新页（replace 时直接驱逐 T2）
  p=c：完全偏向 LRU，T2 目标为 0
       但 T2 仍然接受从 T1 升级的页（replace 时驱逐 T1）

B1/B2 长度为 0 时的 delta 计算

delta = max(1, |B2| // |B1|)  ← B1 命中时
若 |B1|=0（理论上不会进入 B1 命中分支，因为 B1 空则无幽灵）
安全处理：命中 B1 必然 |B1| >= 1，delta = max(1, |B2|/|B1|) 安全

缓存污染（大规模顺序扫描）

场景：扫描 10000 个页，c=100

ARC 行为：
  扫描页全进 T1，T1 满后驱逐 T1 最旧的进 B1
  B1 满后开始覆盖（B1 是循环的）
  T2 完全不受影响（扫描页从未被二次访问，不进 T2）
  
对比 LRU：LRU 的所有热点页都被扫描页驱逐
ARC 的优势：T2 中的高频热点得到保护（p 小，T1 驱逐压力在 T1 自身）

ARC 的局限与替代

主要问题：IBM 专利（US 6,996,676，2003年申请）
  → Linux 内核、OpenJDK 均无法直接使用 ARC
  → ZFS（Solaris/FreeBSD）因 CDDL 许可可用 ARC
  → Linux 的 ZFS 移植（ZFS on Linux）也用了 ARC（CDDL 绕开 GPL）

工程替代：
  Caffeine（W-TinyLFU）：不受专利限制，性能与 ARC 相当
  LIRS（Low Inter-reference Recency Set）：另一个专利外替代
  
详见 [W-TinyLFU 与 Caffeine](/posts/77)

参考资料

• Megiddo, N. & Modha, D. S. (2003). ARC: A Self-Tuning, Low Overhead Replacement Cache
• ZFS ARC 实现：https://github.com/openzfs/zfs/blob/master/module/zfs/arc.c
• 《Designing Data-Intensive Applications》Ch.3 — Caching