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

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

前面四页的改良方向是一致的：给淘汰决策补更多信息。CLOCK 补一位 bit，ARC 补两个 ghost 列表，W-TinyLFU 补一张频率草图。2023 与 2024 年的两个结果反着走——把链表也去掉，只留 FIFO 队列，命中率反而上去了。

1 · 队列便宜在哪

FIFO 队列与 LRU 链表的结构差别只有一条：队列不重排。命中时 LRU 要把结点摘下来挂到头部，FIFO 什么也不做。

这条差别在单线程下只是省了六次指针写，在多核下则是质变。LRU 的每次命中都要拿写锁——读操作在数据结构层面是写操作，缓存命中率越高，锁竞争越激烈。FIFO 的命中路径不碰共享结构，只读一次 hash 表；带一位标志的变体也只是一次单字节写，可以用原子指令甚至直接放松成非原子写（多写一次 1 无害）。

代价是 FIFO 的命中率确实低：实测 Zipf workload、容量 200 下 FIFO 56.0%，LRU 61.2%。这两个结果要做的事，就是在保住 FIFO 的命中路径的前提下把这 5 个百分点找回来，并且多找一些。

2 · S3-FIFO 的三条队列

S3-FIFO 的出发点是一项关于生产流量的观察：相当大一部分对象在整段观测期里只被访问一次。这些一次性对象在任何策略里都是纯粹的负担，它们进来一次、挤掉一个有用的对象、然后自己被挤掉。

S3-FIFO 把缓存切成两段，前面一段专门用来筛掉它们：

small FIFO $S$ ，占容量的 10%，新对象默认先进这一段
main FIFO $M$ ，占 90%，从 $S$ 里活下来的对象搬进它
ghost FIFO $G$ ，只存 key、大小等于 $M$

每个对象带一个 2 位计数器，命中时加一、封顶 3。淘汰时先看 $S$ 有没有超过它的份额：超过就从 $S$ 的队头取一个，计数大于 1 的搬进 $M$ （计数清零），否则淘汰它并把 key 记进 $G$ 。 $M$ 的淘汰是一轮 second-chance：队头对象计数大于 0 就减一并重新入队，等于 0 才真淘汰。

$G$ 的作用是给「被 $S$ 误杀的对象」一次翻案机会：一个 key 若在被 $S$ 淘汰后又被访问，说明它不是一次性对象，这次直接进 $M$ ，跳过 $S$ 的筛选。

图 2-1 · S3-FIFO 的三条队列。格内数字是 key，下方小字是 2 位计数器。可单步推进，观察对象如何从 small 搬进 main、或落进 ghost 又被捞回来。

10% 这个比例并不敏感，但方向是一致的：small 越大命中率越低。实测容量 200 的 Zipf workload 上，比例取 5% 得 68.4%、10% 得 67.9%、20% 得 67.2%、50% 得 64.6%。

这个 10% 是一个目标份额，不是硬上限。装填阶段所有新对象都进 $S$ ， $S$ 会一路涨到占满整个缓存；此后它只在有对象被提升进 $M$ 时才收缩一格。实测容量 200 的 Zipf、突发热点、热集叠加扫描三种 workload 末态都恰好收敛到 20 / 180，而纯循环扫描下 $S$ 始终是 200、 $M$ 一直是空的：没有任何对象被访问第二次，也就没有任何提升事件。这一点与 ARC 在同一条 workload 上退化成 $T_1$ 单表是同一回事。

3 · SIEVE 的一只手

SIEVE 更简单，简单到可以在一段里说完。

定义 3.1（SIEVE） 一条 FIFO 链表，新对象一律插入表头，每个对象带一位 visited。命中时把 visited 置 1，不移动对象。另有一个指针 hand，初始指向表尾（最旧处）。淘汰时从 hand 开始沿「由旧到新」的方向走：visited 为 1 的清零并继续走，走到表头则绕回表尾；遇到 visited 为 0 的对象就淘汰它，hand 停在它更新的那一侧。

和 CLOCK 的差别只有一处，却是关键的一处：CLOCK 是环形数组，被淘汰的槽位立刻被新对象填上，新对象因此落在 hand 刚走过的位置；SIEVE 是链表，新对象一律插到表头，离 hand 很远。

这一处差别带来两个后果。其一，活下来的老对象不会因为「被访问过」而回到队头，它们留在原地，hand 每一轮都从同一片老区域走过，留得下来的老对象由此形成一个稳定的核心。其二，新对象必须自己走完从表头到 hand 的全程才会被考察，这段路就是它证明自己的时间窗。

图 3-1 · SIEVE 的队列与 hand。绿底表示 visited 为 1，橙框是 hand 当前位置。可单步推进，观察 hand 如何沿队列清位、新对象如何从表头进入。

4 · 实测对照

容量 200、20000 次访问下的命中率与元数据写入量：

workload	FIFO	LRU	ARC	W-TinyLFU	S3-FIFO	SIEVE
Zipf	56.0%	61.2%	66.9%	68.5%	67.9%	67.7%
热集叠加扫描	26.3%	29.9%	40.2%	40.1%	39.6%	38.8%
突发热点	87.3%	89.1%	89.0%	88.7%	88.5%	87.6%
Zipf 上的写入 / 访问	0.000	3.674	5.940	8.225	0.171	0.085

前两行里 S3-FIFO 与 SIEVE 都把 LRU 甩开了六到十个百分点，与 ARC、W-TinyLFU 打成平手。第三行它们略输，差距在 0.5 到 1.5 个百分点。而最后一行的差距是六十到一百倍。

写入量这一栏里 SIEVE 比 CLOCK 还低（0.085 对 0.359），这一点起初看不明白：两者都是「命中置一位、淘汰走一圈」。拆开数才看清楚。Zipf workload 上 SIEVE 的 13544 次命中里只有 919 次真的写了 bit，其余 93% 撞上的都是已经置好的 1；CLOCK 的 12474 次命中里写了 3615 次。差别在于 bit 被清掉的频率：SIEVE 全程只清了 789 位，CLOCK 清了 3570 位。CLOCK 把新对象填进 hand 刚走过的位置，hand 下一轮很快又转回来，反复清同一批格子；SIEVE 的新对象落在表头，hand 要走很久才到得了那一端。这个解释是从计数反推的，论文没有这么讲。

图 4-1 · 全部策略在命中率与元数据写入量两个维度上的位置，横轴是对数刻度的写入量。左上角是「又准又便宜」。可切换 workload 与容量。

5 · 便宜的代价藏在尾部

平均值好看不等于没有代价，SIEVE 的代价在淘汰路径的长尾上。

实测 Zipf workload、容量 200 下，hand 平均每次淘汰只走 0.13 格，但最长的一次走了 125 格，超过容量的一半。突发热点 workload 下平均 0.37 格、最长 50 格。CLOCK 在同样条件下最长只走 8 格，因为它每淘汰一次就在 hand 后面留下一个 bit 为 0 的新对象，走不远。SIEVE 没有这个自限机制：当队列里大部分对象的 visited 都是 1 时，hand 要一路清过去。

这条长尾对吞吐无害（清位极便宜，且它同样是摊还的），对尾延迟则要看场景。真要卡 p99.9，可以给 hand 的单次行程设一个上限，超了就退化成淘汰当前项。

另一项代价是它们都不是 stack algorithm。容量加倍未必让命中率变好，实测随机小序列上 SIEVE 出现这种反常的比例比 FIFO 高两个数量级，见容量单调性与策略选型 §3。

6 · 参考文献

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.
Yang, J., Yue, Y., & Rashmi, K. V. (2020). A large scale analysis of hundreds of in-memory cache clusters at Twitter. OSDI 2020, 191–208.
Eytan, A., Manes, B., Einziger, G., & Friedman, R. (2020). It's time to revisit LRU vs. FIFO. HotStorage 2020.