ARC

Author: lorixyu
IconCreated: 2026-01-17
IconUpdated: 2026-01-17

ARC算法

ARC

ARC（Adaptive Replacement Cache，自适应替换缓存）是一种高效的缓存替换算法，由IBM的Nimrod Megiddo和Dharmendra S. Modha在2003年提出。它巧妙地结合了LRU（最近最少使用）和LFU（最少使用频率）两种算法的优点，能够自适应地调整策略以适应不同的访问模式。

核心思想

ARC的核心在于维护两个LRU列表：

  • T1：存储只被访问过一次的页面（最近性）
  • T2：存储被访问过至少两次的页面（频率性）

同时，ARC还维护两个”幽灵”列表：

  • B1：记录最近从T1中淘汰的页面
  • B2：记录最近从T2中淘汰的页面

这四个列表共同工作，其中T1和T2包含实际缓存的数据，而B1和B2只保存元数据（不占用实际缓存空间），用于指导缓存策略的调整。

自适应机制

ARC最精妙的设计是引入了一个目标参数p，它动态地划分T1和T2的大小：

  • T1的目标大小为p
  • T2的目标大小为c-p（c是总缓存大小）

当发生缓存未命中时：

  • 如果未命中的页面在B1中（说明最近性数据被过早淘汰），增加p值，给T1更多空间
  • 如果未命中的页面在B2中（说明频率性数据被过早淘汰），减少p值，给T2更多空间

这种机制使得ARC能够根据工作负载自动调整，在偏重最近性和偏重频率性之间找到最佳平衡点。

算法流程

缓存命中

  1. 如果页面在T1中，将其移到T2的MRU端（表示访问频率增加）
  2. 如果页面在T2中，将其移到T2的MRU端

缓存未命中

情况1：页面在B1中

  • 增加p值：p = min(p + max(|B2|/|B1|, 1), c)
  • 从T1或T2中淘汰一个页面（根据当前大小）
  • 将新页面加入T2的MRU端

情况2：页面在B2中

  • 减少p值：p = max(p - max(|B1|/|B2|, 1), 0)
  • 从T1或T2中淘汰一个页面
  • 将新页面加入T2的MRU端

情况3：页面既不在T1、T2，也不在B1、B2中

  • 如果T1+B1已满，从B1中删除LRU页面；如果T1+B1+T2+B2已满，从B2中删除LRU页面
  • 从T1或T2中淘汰一个页面
  • 将新页面加入T1的MRU端

优势特点

  1. 自适应性强：无需人工调参，能自动适应不同的访问模式（顺序扫描、循环访问、随机访问等）
  2. 性能稳定：在各种工作负载下都能保持接近最优的性能
  3. 扫描抵抗：通过幽灵列表机制，能有效处理大文件扫描等场景，避免缓存污染
  4. 竞争比优秀：理论上可以证明ARC的竞争比不超过2倍最优离线算法

应用

ARC算法已被广泛应用于：

  • ZFS文件系统：Oracle的ZFS使用ARC作为主要的缓存管理策略
  • PostgreSQL：部分实现中使用了类似ARC的思想
  • 各种存储系统：数据库、CDN、操作系统页面缓存等

与其他算法的比较

  • vs LRU：ARC在存在频繁访问的热点数据时表现更好
  • vs LFU：ARC能更快地适应访问模式的变化
  • vs LIRS：两者性能接近，但ARC实现相对简单，LIRS在某些场景下略优
Icon
Credits
This work is published by lorixyu at 2026-01-17 14:43:28
Link: ARC
This work is licensed under CC BY-NC-SA 4.0. Please indicate lorixyu when reprinting.
Logo