reference bit · second-chance · 写放大

CLOCK：一个 bit 换掉一条链表

LRU 的语义没有问题，问题在实现。把最近访问的挪到链表头，这个动作发生在命中路径上，而命中是缓存最频繁的操作。

1 · 代价落在命中路径上

一条双向链表的「摘下再挂到头部」要改六个指针：被摘结点的前驱与后继各一个，重新挂上时自身的两个指针加上原头结点与 head sentinel 各一个。这六次写入本身不贵，贵的是它们发生在哪里：

命中路径。缓存的命中率越高，这段代码跑得越频繁
共享结构。多线程下每次命中都要拿写锁，读操作变成了写操作
随机访存。链表结点散在堆上，六次指针写往往落在六条不同的 cache line 上

第三点在现代硬件上分量最重。本系列统计的 metaWrites 就是按「一次字段或指针写」计价的，LRU 的一次命中记 6，实测 Zipf workload、容量 200 下平均每次访问写 3.67 次；换成突发热点 workload（命中率 89.1%）则是 5.34 次。

2 · 环形数组与一位 reference bit

CLOCK 的想法是把「谁最近被用过」这个信息从链表的位置里挪到每一项自带的一位标志上，这一位叫 reference bit。

定义 2.1（CLOCK） 容量 $c$ 的环形数组，每格存一个 key 与一位 reference bit，另有一个指针 hand。命中时把该格的 bit 置 1，不移动任何东西。淘汰时从 hand 处开始：若当前格的 bit 为 1，清零并前进一格；直到遇到 bit 为 0 的格，淘汰它、把新 key 写入该格并置 bit 为 0，hand 前进一格。

bit 为 1 的格子被放过一轮，代价只是丢掉它的 bit，这就是这套机制又叫 second-chance 的原因。全部 bit 都是 0 时，hand 一格不走，CLOCK 退化成 FIFO；全部 bit 都是 1 时，hand 走满一圈把所有 bit 清零，再淘汰起点那一格——最坏一次淘汰要走 $c$ 格，但走过的每一格都把一个 bit 清成了 0，所以连续两次淘汰不可能都走满一圈。摊还下来每次淘汰的走针步数是常数。

图 2-1 · 十二格环形数组上的 CLOCK。外圈是 key 与它的 reference bit，指针停在下一个候选格。可单步推进访问序列，观察命中如何置位、淘汰时 hand 走过几格。

实测把摊还这件事量化了。Zipf workload、容量 200、20000 次访问下共发生 7326 次淘汰，其中清掉的 bit 一共 3570 个：平均每次淘汰只走 0.49 格，最长的一次走了 8 格。突发热点 workload 下平均 0.50 格、最长 30 格。 $c = 200$ 的理论最坏值一次都没出现过。

3 · 实测：近似出来的东西未必更差

CLOCK 通常被介绍成「LRU 的近似」，读起来像是一个用精度换成本的妥协。实测不支持这个说法。

workload	FIFO	CLOCK	LRU	CLOCK 写入	LRU 写入
Zipf	56.0%	62.4%	61.2%	0.36	3.67
突发热点	87.3%	89.0%	89.1%	0.10	5.34
热集叠加扫描	26.3%	31.1%	29.9%	0.21	1.79
纯循环扫描	0.0%	0.0%	0.0%	0.00	0.00

四种 workload 里 CLOCK 有两种高于 LRU、一种低 0.1 个百分点、一种打平，而元数据写入量少了 8.6 到 52 倍。这个结果一开始是当作 bug 查的：既然是近似，怎么会比被近似的东西还准。查下来它不是 bug，是「近似」这个词用得不准——CLOCK 并不在逼近 LRU 的排序，它执行的是另一条规则：一次访问买一轮免死。

两条规则的偏好不同。LRU 按时刻严格排序，一个刚被访问过的 key 无条件排在所有旧 key 前面，哪怕那些旧 key 每一个都被访问过一百次。CLOCK 的 bit 不记次数也不记时刻，只记「上一圈之内有没有被碰过」，于是它对「稳定的老热点」比 LRU 宽容。热集叠加扫描的 workload 上这一点值 1.2 个百分点，且这个差值在容量 50 到 800 的范围里稳定在 1.1–1.2 个百分点之间。

图 3-1 · FIFO、CLOCK、LRU 三者的命中率与元数据写入量。左侧柱是命中率，右侧柱是每次访问的写入次数（对数刻度）。可切换 workload 与容量。

4 · reference bit 的两个代价

CLOCK 便宜是有条件的，条件写在两处。

第一处是缓存内容不能重排。环形数组的槽位固定，新 key 只能填进被淘汰者留下的那个坑，位置由 hand 当时停在哪决定。这让淘汰顺序带上了一点插入顺序的痕迹，也让 CLOCK 不再是 stack algorithm：容量变大反而命中率下降的情形在 CLOCK 上确实存在，见容量单调性与策略选型 §3。

第二处是 bit 太少。一位只能表达「碰过 / 没碰过」，无法区分碰过一次和碰过一千次。CLOCK-Pro 的改法是给每一项加一个冷热标记与一个 test period：新页进来先算冷页，若在它的 test period 内被再次访问就升为热页。三只手分别负责淘汰冷页、降级热页、以及回收过期的 test period 记录。Linux 的页面回收走的是另一条路——两条 LRU 链表加 PG_referenced 与 PG_active 两位标志，本质上是 CLOCK 思路在链表上的变体。

5 · 参考文献

Corbató, F. J. (1968). A paging experiment with the Multics system. MIT Project MAC Report MAC-M-384.
Jiang, S., Chen, F., & Zhang, X. (2005). CLOCK-Pro: an effective improvement of the CLOCK replacement. USENIX ATC 2005, 323–336.
Jiang, S., & Zhang, X. (2002). LIRS: an efficient low inter-reference recency set replacement policy. SIGMETRICS 2002, 31–42.
Bansal, S., & Modha, D. S. (2004). CAR: Clock with Adaptive Replacement. FAST 2004, 187–200.