算法与数据结构 / 缓存淘汰 · 从 Bélády 上界到 SIEVE 待审核 7 页

缓存淘汰 · 从 Bélády 上界到 SIEVE

缓存的容量总是小于数据量, 于是每次 miss 都要回答一个问题: 踢掉谁。这个决定要预测未来 —— 踢掉的应当是最久才会被再次用到的那一个。未来不可知, 于是所有在线策略都在拿过去的两个信号做外推: recency (这个 key 多久没被用过) 与 frequency (它一共被用过几次)。两个信号各有各的失效场景, 一次全表扫描能把 LRU 的命中率打到 0, 一批过气的历史高频 key 能把 LFU 的缓存占满。

本系列的口径是统一的: 同一条访问序列、同一容量下比命中率, 并且总把 Bélády 的离线最优画在同一张图上作参照。实测的四种 workload 里, 最好的在线策略只拿到最优值的 88.7% (Zipf) 到 99.0% (纯循环扫描)。

路线是: 先建立评测口径与上界, 再看两条改良 LRU 的经典路线 (CLOCK 的 reference bit、ARC 的 ghost 列表), 然后是准入判定这条新思路 (W-TinyLFU 的频率草图), 接着是 2023–2024 年那两个反直觉的结果 —— 只用 FIFO 队列的 S3-FIFO 与 SIEVE 在实测里常常赢过 LRU 一族, 最后是 Redis 的工程取舍与容量单调性。

口径: 上界与两个信号

Bélády 1966 给出的 MIN 是同容量下任何 demand paging 策略的命中率上界, 它需要完整的未来访问序列, 因而只能离线跑 —— 但正因如此它是唯一可靠的参照线。有了它, 「某策略命中率 68%」这句话才有意义: 68% 是最优值的多少。

Bélády 上界 · recency 与 frequency

淘汰策略是在猜未来

命中率的上界是 Bélády 的离线最优，任何在线策略都在拿过去外推未来。本页建立全系列的评测口径：同一条访问序列、同一容量下比命中率，并把最优值画在同一张图上。

「抗扫描」这句话要看是哪种扫描

「LRU 被扫描冲垮, FIFO 抗扫描」是一句流传很广、但经不起实测的话。纯循环扫描 (key 空间 500、容量 200) 下 FIFO、LRU、LFU、CLOCK、ARC、S3-FIFO、SIEVE 的命中率全是 0.0% —— 每个 key 在下一轮回到它之前必定已被淘汰, 与淘汰谁无关。同一条序列上 Bélády 拿到 39.0%: 它锁死 199 个 key 不动, 只让一个槽位轮转。 真正能区分这些策略的是热集与扫描的混合: 同一批热 key 反复访问, 另有一条扫描流不断灌进新 key。此时 LRU 掉到 29.9%、FIFO 更低 (26.3%), 而 SIEVE 38.8%、S3-FIFO 39.6%、ARC 40.2%。抗扫描的不是 FIFO 这个结构, 是「新来的对象要先证明自己」这条规则。

上界与经典策略 · 延伸阅读

改良 LRU 的两条经典路线

LRU 的两个毛病是: 每次命中都要动链表 (锁竞争与写放大), 以及一次扫描就能把它冲垮。CLOCK 用每项一个 reference bit 解决前者, ARC 用两个 ghost 列表记住「刚被淘汰的是谁」, 靠这条反事实信号自适应地在 recency 与 frequency 之间调配容量。

reference bit · second-chance · 写放大

CLOCK：一个 bit 换掉一条链表

LRU 每次命中都要摘挂链表，在多核上就是一次抢锁。CLOCK 把链表换成环形数组加每项一个 reference bit，命中只置位、淘汰才走针，实测写入量降到 LRU 的十分之一而命中率不降反升。

 T1 与 T2 · B1 与 B2 · 自适应 p

ARC：ghost 列表给出的反事实信号

把缓存切成「只用过一次」与「用过多次」两段，再各配一个只存 key 的 ghost 列表。ghost 命中说明这一段当初不该那么小，于是目标切分点 p 往那边挪一格，recency 与 frequency 的配比由此自己找平衡。

ARC 与自适应 · 延伸阅读

准入: 先问该不该进来

此前所有策略都在回答「该踢谁」, W-TinyLFU 换了个问题: 新来的这个 key 凭什么进来。它用一个 Count-Min sketch 估计全体 key 的访问频率, 新来者必须比将被淘汰者更热才准入; 计数器周期性减半, 老化由此而来。

Count-Min sketch · 减半老化 · window 加 SLRU

W-TinyLFU：准入判定与频率草图

前面几种策略都在回答「该踢谁」，W-TinyLFU 换成问「新来的凭什么进」。一个两千字节的 Count-Min sketch 估出全体 key 的频率，新来者必须比将被淘汰者更热才准入，计数器周期性减半实现老化。

频率草图与准入 · 延伸阅读

FIFO 家族与工程取舍

2023–2024 年的两个结果把方向掰回了简单: S3-FIFO 与 SIEVE 都只用 FIFO 队列, 命中路径几乎不写元数据, 实测命中率却常常高于 LRU。Redis 的取舍在另一个维度上 —— 它宁可用随机采样近似 LRU, 也不肯为每个对象多存两个指针。

三条 FIFO · 一只 hand · 无锁友好

S3-FIFO 与 SIEVE：更简单反而更准

两个新结果都放弃 LRU 链表、只用 FIFO 队列：S3-FIFO 用一条小 FIFO 过滤一次性对象，SIEVE 在单条 FIFO 上加一只 hand 与一位 visited。实测命中率与 ARC 相当，写入量低六十倍以上。

 maxmemory-policy · 近似 LRU · 8 位对数计数器

Redis：宁可采样也不要全局链表

Redis 的淘汰不维护任何全局顺序结构：LRU 是随机采样若干 key 取最旧，LFU 是每对象一个 8 位对数计数器加按分钟衰减。本页量化这套近似的质量，并说明它为何比精确 LRU 划算。

 stack property · Bélády 异常 · 实测总表

容量单调性与策略选型

加内存不一定提高命中率。LRU 与 Bélády 有 stack property 因而单调不降，FIFO 有反例，带 bit 的新策略出现反常的频率比 FIFO 高两个数量级。末尾是全部策略的实测总表与选型判据。

选型先看写入量, 再看命中率

实测 Zipf workload、容量 200 下, 各策略每次访问平均写入的元数据字段数差了两个数量级: W-TinyLFU 8.23、ARC 5.94、LRU 3.67、Redis 近似 LRU 0.61、CLOCK 0.36、S3-FIFO 0.17、SIEVE 0.09、FIFO 0.00。而命中率的跨度只有 56.0%–68.5%。 这两个数量级的差距决定了选型: 单机、无并发、命中率贵过一切 (CDN 边缘、数据库 buffer pool) 就上 W-TinyLFU 或 ARC; 多核高并发下每次命中都要抢锁 (KV 缓存、对象存储元数据) 就上 SIEVE 或 S3-FIFO —— 它们的命中率与 ARC 相当, 写入量却低 60 倍以上。至于 FIFO, 它的 0 写入是以命中率垫底换来的。

FIFO 家族与 Redis · 延伸阅读