重新审视 FIFO，这次多比较几种缓存算法

IBM Object Store 轨迹记录了 IBM 云对象存储服务上的真实请求，于 2019 年通过 SNIA 的 IOTTA 仓库公开发布。记录包括哪些对象被读取、写入或删除，以及范围读取请求访问了哪些字节。这里保存的是访问记录，而不是对象的内容。整个数据集包含 99 个租户各一周的活动。数据集说明。

这样的数据很适合做缓存实验。我们可以把读取请求依次送入模拟缓存，改变决定哪些数据留在内存中的规则，再统计后续读取有多少次能直接找到数据。每种策略处理相同的请求。本次实验使用的输入来自 110 个源文件，包含 418,002,964 次非空 GET 请求。

如果你要在对象存储前面加一层缓存，这个问题很实际。命中可以省去一次后端读取；未命中仍然要取回数据。命中率必须足够高，缓存才有用。但内存要花钱，记录哪些数据值得保留，也会消耗 CPU 时间和额外内存。

更复杂的替换策略，只有在节省的未命中或内存足以抵偿这些开销时才值得使用。因此，有用的比较是：达到同一个命中率目标，各策略需要多大的缓存，又给每次访问增加了多少工作。这也是本次实验要回答的问题。

Ohad Eytan、Danny Harnik、Effi Ofer、Roy Friedman 和 Ronen Kat 在 HotStorage 2020 的论文 It's Time to Revisit LRU vs. FIFO 中研究了同样的取舍。他们在不同容量下，分别用 LRU 和 FIFO 模拟 IBM 的租户轨迹，再把缓存管理开销纳入访问成本模型。LRU 的命中率优势经常不足以抵偿额外的维护工作，尤其是大缓存的元数据已经放不进 RAM 时。在他们建模的许多条件下，FIFO 更合算。因此，他们建议认真把 FIFO 作为这类缓存的比较基准。论文全文。

我在 IBM 轨迹上重新进行了 FIFO 与 LRU 的比较，并加入 ARC、LFU、S3-FIFO、SIEVE 和 W-TinyLFU。在这些运行中，较新的策略没有持续超越简单的基准策略，有些甚至需要多得多的内存，才能达到相同命中率。

模拟器用原生 C++ 实现。每次运行都从空缓存开始，把每个 GET 字节范围展开为对 4 KiB 页的访问。所有页缓存策略的运行都记录了 462,902,891,970 次页访问。命中率以这些访问为单位，因此长请求的权重大于短请求。它既不是整个 GET 都能由缓存满足的比例，也不是精确的字节命中率，因为请求可能只覆盖某页的一部分。

我们沿用了论文的问题，但模拟条件有所不同。原论文把大对象拆成 4 MB 块，较小请求按实际长度占用缓存。我们的实验使用 4 KiB（4,096 字节）页，也就是 ./cachesim 的默认页大小。原论文分别评估各租户轨迹；这里则让同一个缓存连续处理二进制输入中的全部记录。转换器通常按轨迹编号和分片编号拼接文件；二进制格式没有时间戳流和输入文件清单，因此无法据此确认跨租户的全局时间顺序。不同文件中的相同对象 ID 共享缓存状态。只有 GET 参与模拟，写入和删除不使缓存页失效。这些选择共同定义了本次比较的工作负载。原论文第 3 节。

各算法采用本地移植的 C++ 实现。这里的容量指存放缓存数据的空间。模拟器只保存标识和替换元数据，不分配对应的数据载荷，因此进程实际内存是另一个量。真正部署 RAM 缓存时，需要表中容量再加上元数据。

下面先解释各策略的行为，以及本次比较的限制。

FIFO——先进先出。 新页进入队列；空间不足时，最早进入的驻留页被淘汰，即使它刚被读取过。命中不改变淘汰顺序。因此 FIFO 很简单，但可能淘汰频繁使用的页，也不保证增加容量后命中率一定提高。

LRU——最近最少使用。 每次命中都把对应页移到最近使用的一端，淘汰时删除最久未访问的页。它能跟随应用读取对象的变化，但必须维护这个顺序。长时间的顺序扫描可能挤掉有用的页。我们的实现精确维护访问顺序，没有采用定期更新的近似方式。

LFU——最不经常使用。 页在驻留期间累计访问次数；淘汰时从最低频率桶中选择，同频率时按最近访问顺序决定。页被淘汰后，计数随之丢失；但仍然驻留的页，其计数从不衰减。因此，即使工作负载已经变化，早先热门的页也可能继续压过新进入的页。这里的结果描述的是这种不衰减计数的 LFU 实现；带有衰减或准入过滤的频率策略可能表现不同。

ARC——自适应替换缓存。 ARC 在近期访问的页与反复访问的页之间分配空间。它还用两个“幽灵”列表保留已淘汰页的标识，根据后续访问调整分配。幽灵条目占用元数据，但不保存缓存数据。这增加了自适应能力和列表管理工作，却不保证对某条轨迹一定更好。我们的 ARC 扫描止于 3 TiB。ARC 论文。

S3-FIFO。 它使用一个小 FIFO 队列筛选新页，一个主 FIFO 队列保留页面，再用幽灵队列记录最近从小队列淘汰的标识。命中只增加一个有上限的小计数器，不重新排列队列。淘汰时利用计数决定哪些页可以留下；命中幽灵历史的返回页直接进入主队列。我们的配置把数据容量的 10% 分给小队列，90% 分给主队列。幽灵历史随主队列容量增长。与普通 FIFO 相比，它增加了元数据和淘汰工作，但命中处理仍很轻。S3-FIFO 设计。

W-TinyLFU——Window TinyLFU。 新页先进入一个小 LRU 窗口。离开窗口时，近似频率估计器判断它是否比主缓存中的候选牺牲页更值得保留。主缓存又分为试用区和保护区。我们的窗口固定占总容量的 1%，保护区占主缓存的 80%。估计器使用本地实现的四行 8 位计数器摘要和 Bloom doorkeeper，扩容时会清空历史。这些参数会影响结果。这是固定参数的本地实现，并非对 Caffeine 自适应实现的测试。Caffeine 策略说明。

SIEVE。 页保持插入顺序，命中时设置访问标志。淘汰指针沿队列前进，遇到访问过的页就清除标志并保留，直到找到未访问的牺牲页。保留的页仍在原来的位置。这使命中路径很轻，把搜索工作移到了淘汰阶段。它没有幽灵历史。保存的曲线在容量增大时出现明显下降，仅凭汇总结果无法确定原因。因此，对这个实现较差表现的推广必须受到限制。SIEVE 设计。

结果中，FIFO、LRU、ARC 和 S3-FIFO 大致聚在一起，而 W-TinyLFU 和 SIEVE 的曲线明显靠右。LFU 在整个容量扫描中的命中率都低于 2%。在实际测过的 64 GiB 容量下，FIFO 命中率为 80.96%，LRU 为 81.92%，ARC 为 81.38%，S3-FIFO 为 81.09%。W-TinyLFU 为 49.01%，SIEVE 为 26.00%，LFU 为 0.0273%。

为缓存确定容量时，下面的表更实用。它给出达到 75%、82.5% 和 90% 页命中率所需的数据 RAM，单位为 GiB，由相邻测量点估算。1 GiB 等于 2³⁰ 字节，数值越低越好。

若目标 T 位于两个测量容量 C0、C1 对应的命中率 H0、H1 之间，计算为 C0 + (T − H0) / (H1 − H0) × (C1 − C0)。插值按字节数线性进行，即使图中横轴采用对数刻度。两位小数表示计算结果，不代表未测试容量处的测量精度。CSV 表包含每个估计所用的上下界测量。

估计取目标的首次向上穿越点。星号很重要：SIEVE 在 2 TiB 时达到 77.69%，3 TiB 时降到 67.70%，4 TiB 时又达到 91.03%。因此，首次穿过 75% 不代表所有更大的缓存都保持在 75% 以上。我们保留了这个下降，没有将它抹平。“未达到”表示保存的测量没有夹住目标，而不是对未测试容量的预测。

LRU 在中间目标上有实际优势。达到 82.5% 命中率时，它比 FIFO 少用约 9.10 GiB 的数据空间，节省 10.9%。在 75% 和 90% 目标上，估算的节省分别只有 1.7% 和 1.9%。ARC 在较高的两个目标上接近 FIFO，在 75% 时更差。S3-FIFO 在 75% 和 82.5% 时基本与 FIFO 相当，达到 90% 则需要多约 4.6% 的容量。它们都没有在这三个目标上持续、大幅优于 FIFO。

W-TinyLFU 和 SIEVE 的差距属于另一个量级。达到 90% 时，FIFO 需要约 359 GiB，W-TinyLFU 需要约 3.81 TiB，SIEVE 需要约 3.96 TiB，分别是 FIFO 数据容量的 10.9 倍和 11.3 倍。这些差距足以显著影响内存配置决策，但上面关于实现和工作负载的限制仍然适用。

本次实验中，LFU 的表现更差。它有 44 个测量点，与 FIFO 覆盖相同的 1 MiB 至 6 TiB 容量序列，最高命中率也只有 6 TiB 时的 1.68%。表中三个目标都未达到，因此这些单元格没有可由数据支持的容量估计。这个结果与不衰减旧热度的风险相符，但汇总命中计数不能证明原因。它们能确认的是：对这个输入，即使使用最大的测试容量，这个 LFU 实现带来的收益也很小。

完整扫描：0–100% 命中率及所有测量容量

剩下的问题是维护这些命中率需要付出什么代价。所有缓存都要查找请求的页。除此之外，FIFO 在命中时不更新替换顺序。LRU 通常要把页从列表中摘下再插入；LFU 更新频率桶；ARC 提升或重排条目，并维护幽灵列表；W-TinyLFU 除了维护 LRU 分区，还要把访问记录到频率估计器中，并定期衰减。FIFO 和 LRU 的操作都可以是常数时间，但实际工作量仍然不同。

S3-FIFO 和 SIEVE 应当区别对待。它们的命中路径只更新有上限的计数器或标志，避免了 LRU 通常在命中时进行的列表移动。额外工作主要发生在淘汰阶段，可能需要检查或保留多个候选页。因此，不能说它们必然比 LRU 消耗更多 CPU。本次比较中的问题在于：S3-FIFO 没有换来多少额外的缓存效果，而我们的 SIEVE 运行得到的效果差得多。

这些比较描述的是实现中的操作，不是实测吞吐排名。保存的运行时间包括轨迹处理，而且容量扫描中有许多进程同时运行。它们不能说明生产缓存每次命中花多少纳秒，也不能说明并发扩展能力。对于 RAM 缓存，相关成本包括元数据写入、内存流量和同步。LRU 在中间目标上节省的 9.10 GiB 是否值得这些开销，取决于部署环境。

对这个工作负载，我仍然会从 FIFO 开始。扩大算法范围后，原论文的实用建议依然成立：小幅或不稳定的命中率提升，需要足以证明额外维护工作的价值。这里 FIFO 的容量需求仍接近测得的最佳结果，淘汰规则简单，命中路径也不需要维护顺序。W-TinyLFU 和 SIEVE 高得多的 RAM 需求，以及 LFU 在整个容量扫描中的低命中率，都没有给出在这个输入上优先选择这些实现的理由。其他策略应当用目标工作负载上的实测收益证明自己的价值。

实验材料包包含保存的输出、CSV 表、绘图脚本和源码快照。原始绘图点、容量覆盖范围和输入清单也可以单独下载。输出记录没有构建哈希，因此源码快照记录的是文章准备时的实现，无法证明每条历史记录对应的确切二进制文件。本次修改只根据保存的数据重新生成图表，没有重新运行轨迹模拟。

参考文献

1. Ohad Eytan、Danny Harnik、Effi Ofer、Roy Friedman、Ronen Kat。IBM Object Store Traces (SNIA IOTTA Trace Set 36305)。载 Geoff Kuenning（编），SNIA IOTTA Trace Repository。Storage Networking Industry Association，2019 年 7 月。
2. Ohad Eytan、Danny Harnik、Effi Ofer、Roy Friedman、Ronen Kat。It's Time to Revisit LRU vs. FIFO。12th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 20)。USENIX Association，2020 年 7 月。