LIRS 缓存替换算法

定义

LIRS(Low Inter-reference Recency Set)是 Song Jiang 与 Xiaodong Zhang 于 2002 年提出的缓存置换算法,用「两次访问之间的重用距离」(IRR)代替单纯的最近访问时间来评估数据价值。

原理

LIRS 将缓存块分为两类:重用距离小的 LIR 块(常驻主体)和重用距离大或只访问一次的 HIR 块(仅占少量空间)。算法通过一个栈和一个队列维护状态,顺序扫描产生的一次性数据只能进入 HIR 区并很快被淘汰,不会冲刷掉真正的热数据。

优缺点

优点是对扫描、循环访问等 LRU 的弱点负载表现出色,且开销与 LRU 同量级;缺点是实现比 LRU 复杂,栈剪枝等细节容易出错。

应用

LIRS 及其思想影响了多种系统:MySQL InnoDB 的中点插入式 LRU、Linux 内核对页缓存的改进讨论,以及 Infinispan 等缓存库都借鉴了类似的抗扫描设计。