ARC 缓存替换算法

定义

ARC(Adaptive Replacement Cache,自适应替换缓存)是由 IBM 研究院的 Nimrod Megiddo 与 Dharmendra Modha 于 2003 年提出的缓存置换算法,能在「最近访问」和「频繁访问」两种倾向之间自动平衡。

原理

ARC 维护两条 LRU 链表:T1 存放只被访问过一次的条目(偏最近性),T2 存放被访问过至少两次的条目(偏频率);另设两条对应的「幽灵链表」B1、B2,只记录被淘汰条目的键。当请求命中幽灵链表时,说明当前分配比例不合理,算法据此动态调整 T1 与 T2 的目标大小,从而自适应工作负载变化。

优缺点

优点是无需调参、能抵抗顺序扫描造成的缓存污染,命中率在多数负载下优于 LRU;缺点是实现复杂度较高,且该算法曾受 IBM 专利保护,影响了部分开源项目的直接采用。

应用

ZFS 文件系统的内存缓存即以 ARC 为核心并做了扩展;PostgreSQL 早期版本也曾短暂使用过 ARC。