Bélády 上界 · recency 与 frequency

淘汰策略是在猜未来

缓存的容量总小于数据量，每次 miss 都要回答同一个问题：踢掉谁。这个决定的正确答案取决于未来：应当踢掉的是最久之后才会被再次访问的那一个。未来不可知，所有在线策略都只是在拿过去的痕迹外推。

本系列的第一件事不是介绍策略，而是把「怎么算好」这件事定下来。没有统一口径与参照线，「某策略命中率 68%」这句话不含信息。

1 · 淘汰决策的目标函数

固定容量 $c$ ，一条访问序列 $r_1, r_2, \dots, r_n$ 。每次访问要么命中，要么 miss；miss 时把 $r_i$ 装进缓存，若已满则先淘汰一个。这套规矩叫 demand paging：只在真的被请求时才装入，不预取、不旁路。命中率是 $h = (\text{命中次数}) / n$ 。

淘汰策略就是一个函数：给定当前缓存内容与到目前为止的访问历史，输出要踢掉的那个 key。它看不到 $r_{i+1}$ 及以后。

值得先说清一件事：命中率不是唯一的目标函数。一次命中省下的是一次后端访问，而维护策略本身也要成本。每次命中都改一次链表指针，在多核上就是一次抢锁。本系列因此同时统计第二个量：每次访问平均写入的元数据字段数。到 FIFO 家族与工程取舍会看到，这两个量在各策略间的跨度差了两个数量级，而命中率的跨度只有十几个百分点。

2 · MIN 与命中率的上界

Bélády 1966 年给出的 MIN 算法只有一句规则：淘汰下一次访问最晚的那个 key（永不再访问的排在最晚）。它需要完整的 $r_{i+1}, \dots, r_n$ ，所以只能离线跑。

定理 2.1 在固定容量的 demand paging 模型下，MIN 的 miss 次数不超过任何其他策略的 miss 次数。

证明设策略 $A$ 与 MIN 在前 $i$ 次访问上决策相同、此后首次分歧。构造 $A'$ ：前 $i$ 次照抄 $A$ ，第 $i$ 次改用 MIN 的选择，之后逐步把两者的缓存内容对齐：每当 $A$ 淘汰某个 key 而 $A'$ 缓存里没有它时， $A'$ 就淘汰那个「多出来的」key。由 MIN 的选择在所有候选里下一次访问最晚，对齐过程中 $A'$ 至多在这一处多一次 miss、而在那个被 MIN 保留的 key 下次被访问时少一次 miss，故 $A'$ 的 miss 数不多于 $A$ 。对每一处分歧重复此交换，即得 MIN 不劣于 $A$ 。∎

这条定理让 MIN 成为整个系列唯一可靠的参照线。教科书那条 12 次访问的序列 1 2 3 4 1 2 5 1 2 3 4 5，容量 3 时 MIN 只 miss 7 次、命中 5 次；同一条序列上 LRU 命中 2 次、FIFO 命中 3 次。

图 2-1 · MIN 与 LRU 在同一条序列上逐次的淘汰决策。格下的数字是该 key 下一次被访问的位置，MIN 每次踢掉这个数字最大的。可切换序列并单步推进。

MIN 的差距有多大，取决于序列本身。实测四种 workload（容量 200、20000 次访问，参数见 §5）里最好的在线策略拿到最优值的比例：Zipf 88.7%、突发热点 97.2%、热集叠加扫描 89.2%、纯循环扫描 99.0%。最后一个数字看着漂亮，但它对应的绝对命中率只有 38.6%——最优值本身就低到 39.0%。

3 · recency 与 frequency

在线策略能用的历史信息，实践中被压缩成两个标量。

recency 是「这个 key 上次被访问距今多久」。它的假设是时间局部性：刚被用过的东西马上还会被用。LRU 只看这一个信号，把缓存内容按最近一次访问时刻排序，踢掉排在末尾的。

frequency 是「这个 key 一共被访问过几次」。它的假设是访问分布稳定：历史上热的东西未来还热。LFU 只看这一个信号。本仓库的 LFU Cache · O(1) 的频率淘汰讲的是如何把它做到 $O(1)$ ，本页只关心它作为信号好不好用。

两个信号都是有损压缩。LRU 丢掉了「被访问过多少次」，一个访问了一千次的 key 与一个刚被装入的新 key 在它眼里地位相同。LFU 丢掉了时间，一个上周的热点与今天的热点在它眼里地位相同。本系列此后的每一个策略，都可以读作对「如何同时保留两个信号」这个问题的一种回答。

4 · 两个信号各自的失效场景

两个信号各有一个能把它打到地板的 workload，而且这两个 workload 在生产里都常见。

打死 LRU 的是扫描：一批 key 依次被访问一遍，此后再不用。它们按 recency 全部排在最前，把真正的热数据挤出去。数据库里的一次全表扫描、备份任务的一次全量读取都是这样。抵抗这类流量的能力叫 scan resistance。

打死 LFU 的是热点迁移：昨天的热 key 攒下了极高的计数，今天已经没人访问，但它的计数依然压着所有新 key。这叫 cache pollution，解法只能是给计数器加老化。

实测数字（容量 200、20000 次访问）：

workload	Bélády	LRU	LFU	SIEVE
热集叠加扫描	45.1%	29.9%	38.8%	38.8%
突发热点	91.7%	89.1%	51.2%	87.6%

这两行是对称的：扫描场景里 LFU 比 LRU 高 8.9 个百分点，热点迁移场景里 LRU 比 LFU 高 37.9 个百分点。跑完之后去看缓存内容更直观。热点迁移 workload 跑完时，LFU 缓存里的 200 个 key 有 168 个已不属于当前热集，而 LRU 缓存里是 0 个。

图 4-1 · 两个信号各自的失效曲线。左侧随扫描流量占比上升，右侧随热点迁移频率上升。可切换场景并调参数观察 LRU 与 LFU 交换位置。

警示 · 「FIFO 抗扫描而 LRU 不抗」是一句流传很广但经不起实测的话。纯循环扫描（key 空间 500、容量 200）下 FIFO、LRU、LFU、CLOCK、ARC、S3-FIFO、SIEVE 的命中率全是 0.0%：每个 key 在扫描回到它之前必定已被淘汰，与淘汰谁无关。同一条序列上 Bélády 拿到 39.0%，办法是锁死 199 个 key 不动、只让一个槽位轮转——任何不带准入判定的在线策略都做不到这件事。真正区分诸策略的是热集与扫描的混合，见 §5 的第四种 workload。

5 · 本系列的评测口径

全系列的数字都按同一套参数跑出来，实现见 core/evict.ts：

序列长度 $n = 20000$ ，容量 $c = 200$ ，随机数发生器是固定 seed 的 LCG，同一 seed 必然给出同一条序列与同一串命中数
zipf：key 空间 2000，权重 $w_i \propto (i+1)^{-s}$ ，默认 $s = 1.0$
loop：key 空间 500 的纯循环扫描，容量小于它时在线策略必定零命中
burst：key 空间 2000，每 3000 次访问整批换掉热集，90% 流量打在当前热集上
mixed：一个 500 个 key 的 Zipf 热集叠加一条在另外 3500 个 key 上推进的循环扫描，默认各占一半流量

四种 workload 都是合成的，不是真实 trace。合成的好处是参数可调、结论可复现；代价是它不能替代生产数据做选型。S3-FIFO 与 SIEVE 的论文各自在数千条真实 trace 上做过对照，那些结论本系列只引用、不冒充自己的实测。

图 5-1 · 同一条序列上十种在线策略的命中率，虚线是 Bélády 的最优值。可切换 workload、调容量与 Zipf 偏斜度，右侧一列是每次访问的元数据写入量。

有一处坑值得记下来。写 MIN 的时候，「永不再访问」这个 sentinel 值本来取的是 Number.MAX_SAFE_INTEGER，而存放它的数组是 Int32Array——写进去被截成 -1，「永不再用」于是变成了「马上就用」，MIN 一路踢掉正要被访问的 key。测出来的最优命中率比 LRU 还低，四种 workload 的上界断言全线失败。改成用序列长度 $n$ 当 sentinel 才对。这个 bug 只有靠「上界必须成立」这条外部真值才抓得住，靠肉眼看命中率数字是发现不了的。

6 · 参考文献

Bélády, L. A. (1966). A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2), 78–101.
Mattson, R. L., Gecsei, J., Slutz, D. R., & Traiger, I. L. (1970). Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2), 78–117.
O'Neil, E. J., O'Neil, P. E., & Weikum, G. (1993). The LRU-K page replacement algorithm for database disk buffering. SIGMOD Record, 22(2), 297–306.
Megiddo, N., & Modha, D. S. (2003). ARC: a self-tuning, low overhead replacement cache. FAST 2003, 115–130.