容量单调性与策略选型
「命中率不够就加内存」是一条几乎不会被质疑的经验。它对某些策略成立、对另一些不成立，而不成立的那一批里包含本系列后半部分推荐的几个。
1 · stack property
定义 1.1（stack algorithm） 一个淘汰策略具有 stack property，若对任意访问序列与任意容量 ，容量 的缓存内容始终是容量 的缓存内容的子集。
这个包含关系直接推出单调性：容量 命中的每一次访问，容量 也必然命中，故命中率随容量单调不降。
定理 1.2 LRU 具有 stack property。
证明 对访问次数归纳。容量 的 LRU 缓存恰好是「到目前为止最近访问过的 个不同 key」，这个刻画不依赖任何历史决策，只依赖访问序列本身。最近 个显然是最近 个的子集。∎
Bélády 的 MIN 同样具有这个性质，证明要复杂一些（见 Mattson 等 1970 的原始论文）。LFU 在计数永久保存的理想形态下也是 stack algorithm，但真实实现里 key 被淘汰后计数归零，这一条就不再成立。
实测 400 条长度 30、key 空间 8 的随机序列，容量从 2 扫到 8：LRU 与 Bélády 出现「容量变大命中率下降」的次数都是 0。
2 · FIFO 的反例
FIFO 没有这个性质，最有名的反例只有 12 次访问：
1 2 3 4 1 2 5 1 2 3 4 5
| 容量 | FIFO 命中 | LRU 命中 | Bélády 命中 |
|---|---|---|---|
| 2 | 0 | 0 | 3 |
| 3 | 3 | 2 | 5 |
| 4 | 2 | 4 | 6 |
| 5 | 7 | 7 | 7 |
容量从 3 加到 4，FIFO 的命中数从 3 掉到 2。这就是 Bélády 异常，1969 年由 Bélády、Nelson 与 Shedler 给出。
原因在于 FIFO 的缓存内容不是访问序列的函数，而依赖历史上每一次淘汰的时机。容量 3 时第 7 次访问 5 淘汰的是 3，此后 1 与 2 都还在；容量 4 时同一次访问淘汰的是 1，把马上要用的 key 踢掉了。多出来的那一格改变了整条淘汰链的相位。
3 · 异常在各策略上的出现率
FIFO 是这个现象的教科书代表，但它并不是最容易出现异常的策略。实测 1000 条长度 30、key 空间 8 的随机序列，容量从 2 扫到 8，统计有多少条序列上出现过下凹：
| 策略 | 出现下凹的序列比例 |
|---|---|
| Bélády | 0.0% |
| LRU | 0.0% |
| FIFO | 0.1% |
| LFU | 0.5% |
| W-TinyLFU | 2.3% |
| Redis 近似 LRU | 4.3% |
| ARC | 4.5% |
| CLOCK | 5.6% |
| S3-FIFO | 8.6% |
| SIEVE | 10.4% |
| Redis LFU | 23.4% |
这个排序与直觉相反。原先预期 FIFO 会名列前茅，毕竟它是这个反例的招牌；实测它只有 0.1%，比除 LRU 与 Bélády 之外的所有策略都低。原因是均匀随机序列上 FIFO 的相位很难错开到坏处，而 reference bit、visited bit、2 位计数器这些状态一进来，缓存内容就更强地依赖历史路径，多一格容量能改变的东西更多。Redis LFU 那 23.4% 里还叠了采样的随机性。
换成本系列的四种合成 workload、容量从 10 扫到 400（步长 10），下凹仍然存在但幅度很小：突发热点上 SIEVE 有 9 处、最大跌 0.85 个百分点，S3-FIFO 有 2 处、最大 0.51；混合 workload 上 Redis LFU 有 3 处、最大 0.14。FIFO、LRU、CLOCK、LFU 在这四条 workload 的全部 40 档容量上单调不降。换一套容量档位，被采到的下凹处数目会变，因为下凹是逐点比较的结果而不是曲线的固有属性。
警示 · 这条性质影响的是容量规划的方法，不是策略选型。0.85 个百分点的反常不足以让人放弃 SIEVE，但它意味着「加 10% 内存，命中率至少不会更差」这句话在非 stack 策略上没有保证。要判断加内存值不值，只能拿真实 trace 在目标容量附近实测，不能靠单点外推。
4 · 实测总表
容量 200、20000 次访问、四种合成 workload 下的命中率（口径见 淘汰策略是在猜未来 §5）：
| 策略 | Zipf | 纯循环扫描 | 突发热点 | 热集叠加扫描 |
|---|---|---|---|---|
| Bélády（上界） | 77.2% | 39.0% | 91.7% | 45.1% |
| FIFO | 56.0% | 0.0% | 87.3% | 26.3% |
| LRU | 61.2% | 0.0% | 89.1% | 29.9% |
| CLOCK | 62.4% | 0.0% | 89.0% | 31.1% |
| LFU | 66.8% | 0.0% | 51.2% | 38.8% |
| ARC | 66.9% | 0.0% | 89.0% | 40.2% |
| SIEVE | 67.7% | 0.0% | 87.6% | 38.8% |
| S3-FIFO | 67.9% | 0.0% | 88.5% | 39.6% |
| W-TinyLFU | 68.5% | 38.6% | 88.7% | 40.1% |
| Redis 近似 LRU | 60.7% | 0.0% | 89.0% | 29.6% |
| Redis LFU | 64.3% | 17.0% | 88.6% | 34.9% |
同一组配置下每次访问的元数据写入次数：
| 策略 | Zipf | 突发热点 | 热集叠加扫描 |
|---|---|---|---|
| FIFO | 0.000 | 0.000 | 0.000 |
| SIEVE | 0.085 | 0.087 | 0.024 |
| Redis LFU | 0.082 | 0.083 | 0.042 |
| S3-FIFO | 0.171 | 0.101 | 0.063 |
| CLOCK | 0.359 | 0.103 | 0.209 |
| Redis 近似 LRU | 0.607 | 0.890 | 0.296 |
| LRU | 3.674 | 5.344 | 1.795 |
| LFU | 4.007 | 3.075 | 2.326 |
| ARC | 5.940 | 5.940 | 5.940 |
| W-TinyLFU | 8.225 | 9.393 | 6.423 |
5 · 判据
两张表读下来，选型的判据基本落在三个问题上。
第一个问题是写入量能不能接受。命中率的跨度是十几个百分点，写入量的跨度是两个数量级。多核高并发下每次命中都要抢锁的场景（KV 缓存、对象存储的元数据层），这一条排在最前，答案是 SIEVE 或 S3-FIFO：它们的命中率与 ARC 相当，写入量低六十倍以上。
第二个问题是流量里有没有扫描。有扫描就必须用带准入或带分段的策略。混合 workload 上 SIEVE 比 LRU 高 8.9 个百分点、比 CLOCK 高 7.7 个百分点，这个差距远大于 LRU 与 CLOCK 彼此之间的 1.2 个百分点。
第三个问题是热点会不会整批迁移。会的话就不能用无老化的 LFU：突发热点 workload 上 LFU 只有 51.2%，比 FIFO 还低 36 个百分点。带减半的 W-TinyLFU 与带衰减的 Redis LFU 都不受这一条影响。
三条之外还有一条不在表里：实现复杂度。SIEVE 是一条链表加一位 bit 加一个指针，ARC 是四个列表加一个自适应状态机。两者命中率相差不到 2 个百分点时，这一项的分量不小。
最后是本系列的适用边界。四种 workload 都是合成的，参数由本系列自己选定，因此上面所有名次都只在这套参数下成立。S3-FIFO 与 SIEVE 的论文各自在数千条生产 trace 上做过对照，那才是选型该依据的证据；本系列能提供的是机制上的理解与一套可复现的对照口径。
6 · 参考文献
- Bélády, L. A., Nelson, R. A., & Shedler, G. S. (1969). An anomaly in space-time characteristics of certain programs running in a paging machine. Communications of the ACM, 12(6), 349–353.
- Mattson, R. L., Gecsei, J., Slutz, D. R., & Traiger, I. L. (1970). Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2), 78–117.
- Yang, J., Zhang, Y., Qiu, Z., Yue, Y., & Vinayak, R. (2023). FIFO queues are all you need for cache eviction. SOSP 2023, 130–149.
- Zhang, Y., Yang, J., Yue, Y., Vigfusson, Y., & Rashmi, K. V. (2024). SIEVE is simpler than LRU: an efficient turn-key eviction algorithm for web caches. NSDI 2024, 1229–1246.