缓存淘汰懂 FIFO 就行了

标题：FIFO Queues are All You Need for Cache Eviction

日期：2023/10/23

作者：Juncheng Yang, Yazhuo Zhang, Ziyue Qiu, Yao Yue, K. V. Rashmi

链接：https://dlnext.acm.org/doi/abs/10.1145/3600006.3613147

注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。

备注：没看先 mark，仓库链接在这里。

摘要

作为一种缓存淘汰算法，FIFO（先进先出）具有许多吸引人的特性，如简单、高速、可扩展和对闪存友好。然而，对FIFO最主要的批评是其效率低下（高未命中率）。

在本文中，我们展示了一种简单、可扩展、基于FIFO的算法，该算法使用三个静态队列（S3-FIFO）。通过对来自14个数据集的6594个缓存轨迹进行评估，我们表明S3-FIFO在所有轨迹上的未命中率都低于当前最先进的算法。此外，S3-FIFO的效率非常稳健——在14个数据集中，它在其中10个数据集上实现了最低的平均未命中率。FIFO队列使得S3-FIFO能够实现良好的可扩展性，在16个线程下，其吞吐量比优化的LRU（最近最少使用）高出6倍。

我们的洞见在于，有偏差的工作负载中的大多数对象只会在一个短窗口内被访问一次，因此尽早淘汰它们（也称为快速降级）至关重要。S3-FIFO的关键在于一个小的FIFO队列，它能过滤掉大多数对象，阻止它们进入主缓存，从而提供有保证的降级速度和高降级精度。

1. 引言

软件缓存，如Memcached和Linux页面缓存，如今被广泛部署以加速数据访问并避免重复计算。一个缓存应该具备以下特点：(1) 高效 (efficient)：它应该提供低未命中率，允许大多数请求能以短延迟从缓存中得到满足；(2) 高性能 (performant)：从缓存中提供数据应执行最少的操作并具有高吞吐量；以及 (3) 可扩展 (scalable)：它每秒可以服务的缓存命中数应随CPU核心数的增加而增长。

缓存的核心是其淘汰算法，它决定了缓存的效率、吞吐量和可扩展性。

许多研究工作已经探讨了高效淘汰算法的设计。因为LRU被认为比FIFO更有效，这些先进的算法通常是基于LRU的，在一个或多个LRU队列之上使用不同的技术和度量。然而，LRU存在两个问题：(1) 它需要为每个对象维护两个指针，这对于由小对象组成的工作负载来说是一个显著的存储开销；(2) 它的可扩展性不强，因为每次缓存命中都需要将被请求的对象提升到队列头部，而这个操作受到锁的保护。

随着缓存与后端之间延迟的缩短以及每个插槽CPU核心数的快速增长，缓存的吞吐量和可扩展性变得至关重要。近年来，越来越多的研究工作关注这一点。解决方案通常是通过使用简单的基于FIFO队列的淘汰算法来换取吞吐量和可扩展性。例如，MemC3、Tricache 使用CLOCK，而Segcache 使用FIFO-merge。与LRU相比，FIFO更简单、更具可扩展性，但缺点是效率较低。

本文探讨了仅使用FIFO队列构建一个简单、可扩展且高效的淘汰算法的可能性。缓存工作负载中的对象流行度通常是倾斜的，并遵循幂律（例如Zipf）分布。我们的洞见是，对于任何Zipf请求序列，只出现一次的对象（称为“一次性奇迹”，one-hit wonders）的比例在一个子序列中远高于在完整轨迹中的比例。因为一个大小为C的缓存在淘汰对象前只能观察到C个对象的短序列，所以在被淘汰时，大多数对象将是“一次性奇迹”（插入后没有再次请求），即使它们在整个轨迹中可能有更多的请求。我们在6594个生产环境轨迹上证实了这一观察。在考虑整个轨迹时，所有轨迹的中位数“一次性奇迹”比例为26%。然而，当关注于包含每个轨迹中10%的唯一对象的序列时，中位数“一次性奇迹”比例飙升至72%。

我们利用这一工作负载特性设计了S3-FIFO，这是一个由三个静态（固定大小）FIFO队列组成的简单、可扩展的淘汰算法。S3-FIFO使用一个小的试用FIFO队列来过滤掉“一次性奇迹”，阻止它们进入主FIFO队列，以便缓存空间可以用于更有价值的对象（这被称为早期淘汰或快速降级）。从小FIFO队列中淘汰的对象会进入主FIFO队列或幽灵FIFO队列，这取决于它是否被访问过。主FIFO队列在淘汰期间会重新插入一些热门对象。许多先前的工作已经探索了类似的想法，以快速降级某些对象，特别是在分层缓存中的扫描和流式工作负载模式中。然而，据我们所知，这是第一项证明即使在没有扫描和流式模式的情况下，快速降级对于缓存工作负载也至关重要的工作。此外，这项工作设计了第一个仅使用FIFO队列且比最先进算法更高效的算法。

S3-FIFO不仅简单而且高效。我们将S3-FIFO与12种淘汰算法在包含来自14个来源的6594个生产轨迹的大型数据集上进行了比较。这些轨迹总共包含在2007年至2023年间收集的8560亿次请求，涵盖了块、键值和对象缓存。虽然先进的算法可能在某些特定的工作负载上表现出色，但我们的评估表明，S3-FIFO在所有百分位数的轨迹上都实现了更好的效率（更低的未命中率），优于最先进的算法。此外，S3-FIFO的效率是稳健的。在使用轨迹中10%对象数量的缓存大小时，S3-FIFO在14个数据集中有10个是最高效的算法，并且在13个数据集中位列最高效的前三名。相比之下，次优的算法（LIRS）仅在2个数据集上获得最高效率。

S3-FIFO也更具可扩展性，因为FIFO队列支持无锁实现。我们在Cachelib中实现了一个原型，并表明S3-FIFO在16个核心上的吞吐量比高度优化的LRU实现高出6倍以上。与2Q和TinyLFU等先进淘汰算法相比，吞吐量的差距进一步扩大。

使用一个小的FIFO队列过滤对象能够实现比最先进技术更好的效率，这对闪存缓存的部署具有启示。如果小的FIFO队列在DRAM中，而主FIFO队列在闪存上，那么从DRAM中淘汰的大多数对象就不需要写入闪存。这既减少了闪存写入，也降低了未命中率。我们将这种FIFO过滤器与Flashield中的概率过滤器和基于机器学习模型的过滤器进行了比较。在两个开源CDN轨迹上评估，FIFO过滤器具有最低的未命中率和最少的闪存写入。此外，与需要大DRAM缓存（占总缓存大小的10%）来跟踪对象访问信息以做出良好决策的ML模型相比，即使DRAM缓存仅为总缓存大小的0.1%，小的FIFO过滤器也能表现出色。

这项工作做出了以下贡献：

  • 我们表明，对于具有倾斜流行度的缓存工作负载，大多数对象在淘汰时都是“一次性奇迹”。因此，快速降级对于缓存效率至关重要。

  • 利用这一观察，我们设计并实现了S3-FIFO，这是第一个仅使用FIFO队列且效率优于最先进技术的淘汰算法。

  • 我们在6594个轨迹上评估了S3-FIFO，并与12种最先进的淘汰算法进行了比较，结果表明S3-FIFO更高效，且其效率也更稳健。

  • 我们在Cachelib中的原型表明，FIFO队列使S3-FIFO具有可扩展性，其吞吐量比优化的LRU实现高出6倍。

2. 背景

软件缓存如今无处不在，例如在终端用户设备内部，在互联网的边缘，以及数据中心的系统堆栈中。虽然存储在不同类型缓存中的数据有不同的名称，例如块、页、对象和资产，但为便于讨论，我们统一使用术语“对象”。

2.1 缓存的度量标准

缓存的核心是其淘汰算法，它决定了在有限空间内存储哪些对象。

效率 (Efficiency)。一个更高效（有时被称为更“有效”）的淘汰算法会在缓存中保留更有用的对象，并提供更低的未命中率，该指标衡量了必须从后端获取的请求的比例。虽然请求未命中率是最常见的效率指标，但一些旨在减少带宽使用的缓存部署，例如代理缓存，也评估字节未命中率：即需要从源头获取的字节的比例。

吞吐量 (Throughput)。缓存的吞吐量衡量其每秒可以服务的请求数（QPS）。更高的吞吐量可以减少服务工作负载所需的CPU核心数。

可扩展性 (Scalability)。现代CPU拥有大量的核心。例如，AMD EPYC 9654P拥有192个核心。缓存的可扩展性衡量其吞吐量如何随CPU核心数的增加而增加。理想情况下，缓存的吞吐量应随CPU核心数线性扩展。然而，在许多淘汰算法中，读操作需要加锁更新元数据。因此，它们无法充分利用现代CPU的计算能力。

闪存写入 (Flash writes)。虽然DRAM是缓存最常用的存储介质，但如今许多系统也使用闪存，因为它具有更高的密度、更低的价格和更低的功耗。在使用闪存进行缓存时，闪存寿命成为一个关键指标，因为闪存只支持有限次数的写入。此外，对闪存的小规模随机写入会导致设备级的写放大，这不仅减少了闪存寿命，还增加了读写操作的尾部延迟。为了实现更可管理的闪存寿命，大多数生产闪存缓存系统，例如Apache Trafficserver、Memcached Extstore、Cachelib大对象缓存 和Google Colossus闪存缓存，都使用FIFO或FIFO-reinsertion。除了闪存淘汰算法，许多系统还采用准入算法，例如布隆过滤器或基于机器学习的算法，来选择“好”的数据写入闪存。

简单性和通用性 (Simplicity and generality)。缓存淘汰算法的复杂性和通用性是其采纳中起关键作用的另外两个因素。虽然复杂性通常与吞吐量和可扩展性成反比，但一个简单的设计可以带来超越性能指标的好处，例如更少的错误和更低的维护开销。Linux内核开发者曾表示：“预测哪些页面在不久的将来会被访问是一项棘手的任务。内核不仅经常出错，而且为了做出错误的选择还浪费了大量的CPU时间”。通用性出于类似的原因也至关重要。如果相同的数据结构和淘汰算法可以用于不同类型的缓存，它有助于减少开发和维护的开销。类似的论点也可以在Meta之前的研究工作中找到。

2.2 基于LRU的缓存的普遍性

缓存工作负载表现出时间局部性：最近访问的数据更可能被再次访问。因此，最近最少使用（LRU）算法比FIFO更高效，并被广泛用于DRAM缓存中。此外，为提高效率而设计的先进淘汰算法大多建立在LRU之上。例如，ARC、SLRU、2Q、EELRU、LIRS、TinyLFU、LeCaR 和 CACHEUS 都使用一个或多个LRU队列来对对象进行排序。

尽管高效，LRU和基于LRU的算法有三个问题。首先，LRU通常使用双向链表实现，每个对象需要两个指针，当对象很小时，这会成为一个巨大的开销。因此，Twitter和Meta为具有小对象的工作负载设计了专门的紧凑型缓存。

其次，LRU在每次缓存命中时都会将被访问对象提升到队列头部（称为提升），这个操作至少需要六次受锁保护的随机内存访问，显著限制了缓存的可扩展性。例如，RocksDB的开发者“承认”RocksDB中的LRU缓存是可扩展性的瓶颈。因此，在2022年，为了解决这个问题，实现了一个使用CLOCK 淘汰策略的新缓存。

第三，LRU对闪存不友好。LRU中的对象淘汰顺序与插入顺序不同，这会导致闪存上的随机写入，并减少闪存寿命。

3. 动机

虽然过去几十年的淘汰算法研究都围绕着LRU，但我们认为现代淘汰算法应该使用FIFO队列而不是LRU队列来设计。FIFO可以使用环形缓冲区实现，无需为每个对象维护指针元数据，并且它在每次缓存命中时不会提升对象，从而消除了可扩展性的瓶颈。

[图1已被忽略] 图1. 较短的序列具有较高的一次性奇迹比例。

然而，FIFO在效率上落后于LRU和最先进的淘汰算法。

FIFO需要什么？ FIFO的主要局限性在于其无法保留频繁访问的对象，因此最直接的改进是重新插入这些对象。FIFO-Reinsertion¹ 是一种跟踪对象访问并在淘汰期间重新插入被访问对象的算法。与LRU相比，FIFO-Reinsertion在缓存命中时产生的开销较小，对于对象的首次请求不需要操作或仅需一次原子设置。然而，仅靠重新插入是不够的，FIFO-Reinsertion在效率上仍然落后于最先进的淘汰算法（§5.2）。

我们的洞见是，缓存经历的“一次性奇迹”（插入后没有再次访问的对象）比通常的完整轨迹分析所显示的要多，这凸显了迅速移除大多数新对象的重要性。具体来说，我们观察到在6594个生产轨迹中，中位数的“一次性奇迹”比例为26%。然而，对于一个包含轨迹中10%唯一对象的随机请求序列，72%的对象在该序列中只有一个请求。

3.1 比预期更多的一次性奇迹

术语“一次性奇迹比例”衡量的是在轨迹中只被请求一次的对象的比例。由于其巨大的一次性奇迹比例，这个术语通常在内容分发网络（CDN）中使用。

尽管不同类型的缓存工作负载的一次性奇迹比例各不相同，我们发现较短的请求序列（包含较少唯一对象）通常具有较高的一次性奇迹比例。在后续分析中，我们使用唯一对象的数量来衡量序列长度。

图1用一个玩具示例说明了这一观察。该请求序列包含对五个对象的十七次请求，其中一个对象（E）只被访问了一次。因此，该序列的一次性奇迹比例为20%。考虑从第1次到第7次请求的较短序列，四个唯一对象中有两个（C, D）只被请求了一次，这导致了一次性奇迹比例为50%。同样，从第1次到第4次请求的较短序列的一次性奇迹比例为67%。更正式地，我们做出以下观察。

观察。假设一个请求序列的对象流行度遵循Zipf分布，其中最不受欢迎的… (此处省略了部分形式化描述)

¹ FIFO-Reinsertion、Second chance 和 CLOCK 是同一算法的不同实现。

[图2已被忽略] 图2. 左二图：对于合成的Zipf轨迹，一次性奇迹比例随序列长度（表示为完整序列中唯一对象的分数）的增加而减少。不同曲线显示了不同的偏度α。我们同时绘制了线性和对数尺度的X轴以便于阅读。右二图：生产轨迹显示了类似的观察结果。请注意，X轴显示的是轨迹中对象的分数，远小于后端可能对象的数量。因此，生产曲线捕捉了Zipf曲线的左侧区域。

… (此处省略了对图2和相关模拟的详细文字描述)

[图3已被忽略] 图3. 6594个轨迹上的一次性奇迹比例（表1）。须线显示P10和P90，三角形显示平均值。

… (此处省略了对图3和相关评估的详细文字描述)

因为缓存大小总是远小于轨迹足迹（轨迹中的对象数量），所以在遇到一个短请求序列后就开始进行淘汰。这一观察表明，如果缓存大小设置为轨迹足迹的10%或1%，那么大约72%和78%的对象在被淘汰前不会被重用。

我们通过缓存模拟进一步证实了这一观察。图4显示了淘汰时对象频率的分布。我们的轨迹分析（图2d）显示，Twitter轨迹对于10%长度的序列有26%的一次性奇迹比例。模拟显示了类似的结果：在缓存大小为轨迹足迹10%时，被LRU和Belady淘汰的对象中有26%和24%在插入后没有被再次请求。同样，MSR轨迹对于10%长度的序列表现出更高的75%的一次性奇迹比例（图2d），而图4显示，被LRU和Belady淘汰的对象中有82%和68%没有重用。这表明这些一次性奇迹通常是很好的淘汰候选者，可能不需要非常复杂的淘汰算法。

3.2 快速降级的必要性

基于以上观察，缓存应该过滤掉这些一次性奇迹，因为它们在占用空间的同时没有提供任何好处。在CDN中，使用布隆过滤器来拒绝一次性奇迹进入缓存是一种常见做法。然而，布隆过滤器拒绝对象的速度太快且缺乏精度，因为它拒绝了所有以前未见过的对象。这导致所有对象的第二次请求都成为缓存未命中，通常导致效率平平（§5.2）。

[图4已被忽略] 图4. 淘汰时对象的频率。

过滤一次性奇迹与设计抗扫描的缓存淘汰算法有些相似，因为在扫描过程中请求的对象通常是一次性奇迹。研究人员已经为存储工作负载开发了多种算法，可以避免由扫描请求引起的缓存污染和抖动，例如ARC、LRU-K、2Q、EELRU、LIRS、LeCaR、CACHEUS和LHD。然而，现有的算法不能保证一次性奇迹在被移除前在缓存中停留的最短和最长时间。我们发现这些算法有时淘汰得太快或太慢，并且它们的复杂性使得难以推断其行为（§6.1）。

这就提出了一个问题：我们能否简单地使用一个小的试用FIFO队列来保证一次性奇迹在插入固定数量的对象后被移除？

4. 设计与实现

如§2.1所述，缓存淘汰算法除了高效之外，还需要简单和可扩展。本节介绍S3-FIFO，一个由静态FIFO队列组成的简单且可扩展的淘汰算法。

我们首先定义LRU队列和FIFO队列。LRU队列在缓存命中时通过将被请求的对象提升到队列头部来更新对象顺序。FIFO队列在缓存命中时不更新顺序，对象按插入顺序被淘汰。然而，被淘汰的对象可能会被重新插入队列以保留热门对象。如§2.2所述，大多数淘汰算法是基于LRU队列构建的，只有少数算法，如FIFO-Reinsertion，使用FIFO队列，因为传统观点认为LRU队列可以提供更低的未命中率。

[图5已被忽略] 图5. S3-FIFO的图示。 插入：如果不在幽灵队列中，插入到小队列(1a)，否则插入到主队列(1b)。 淘汰(小队列)：如果未被访问，插入到幽灵队列(2a)，否则插入到主队列(2b)。 淘汰(主队列)：如果被访问过，插回队列(3a)，否则淘汰(3b)。

4.1 S3-FIFO设计

S3-FIFO使用三个FIFO队列：一个小的FIFO队列(S)，一个主FIFO队列(M)，和一个幽灵FIFO队列(G)。我们根据对10个轨迹的实验选择S使用10%的缓存空间，并发现10%的设置泛化性很好。M则使用90%的缓存空间。幽灵队列G存储与M相同数量的幽灵条目（无数据）。

缓存读取 (Cache read)。S3-FIFO为每个对象使用两位来跟踪其访问状态，类似于一个频率上限为3的带帽计数器。S3-FIFO中的缓存命中会原子地将计数器加一。请注意，对热门对象的大多数请求不需要更新。

缓存写入 (Cache write)。新对象如果不在G中，则插入到S中。否则，插入到M中。当S满时，队尾的对象如果被访问超过一次，则移至M，否则移至G。并且在移动过程中其访问位被清除。当G满时，它按FIFO顺序淘汰对象。M使用类似于FIFO-Reinsertion的算法，但使用两位来跟踪访问信息。至少被访问过一次的对象会被重新插入，并将一位设置为0（类似于频率减1）。我们在图5中图示了该算法，并在算法1中给出了伪代码。

算法1 S3-FIFO算法
输入：请求的对象x，小FIFO队列S，主FIFO队列M，幽灵FIFO队列G

1: function READ(x)
2:   if x in S or x in M then        // 缓存命中
3:     x.freq ← min(x.freq + 1, 3)   // 频率上限为3
4:   else                           // 缓存未命中
5:     INSERT(x)
6:     x.freq ← 0

7: function INSERT(x)
8:   while cache is full do
9:     EVICT()
10:  if x in G then
11:    insert x to head of M
12:  else
13:    insert x to head of S

14: function EVICT()
15:  if S.size ≥ 0.1 * cache size then
16:    evictS()
17:  else
18:    evictM()

19: function EVICTS()
20:  evicted ← false
21:  while not evicted and S.size > 0 do
22:    t ← tail of S
23:    if t.freq > 1 then
24:      insert t to M
25:      if M is full then
26:        evictM()
27:    else
28:      insert t to G
29:      evicted ← true
30:    remove t from S

31: function EVICTM()
32:  evicted ← false
33:  while not evicted and M.size > 0 do
34:    t ← tail of M
35:    if t.freq > 0 then
36:      Insert t to head of M
37:      t.freq ← t.freq - 1
38:    else
39:      remove t from M
40:      evicted ← true

处理不同的访问模式。我们在§3.1中确定的一个重要模式是由于有限的缓存空间，缓存会经历大量的一次性奇迹比例。小FIFO队列S可以快速淘汰这些一次性奇迹，使它们不会长时间占用缓存。这使得S3-FIFO能够为更有价值的对象节省宝贵的缓存空间。除了一次性奇迹，许多块缓存工作负载还有扫描和循环访问模式。像一次性奇迹一样，扫描期间访问的块会被迅速移除，以避免缓存污染和抖动。然而，扫描中混合的非扫描块在此过程中也会被移至G。尽管如此，当这些“好”块在不久的将来再次被请求时，它们将被插入到M中并停留更长时间。

4.2 实现

FIFO队列可以使用链表或环形缓冲区实现。基于链表的实现可以更容易地添加到现有的基于LRU的缓存中。然而，它有三个缺点。首先，每个对象使用两个指针。在具有微小对象的工作负载上，这会造成巨大的存储开销。其次，遍历队列需要随机内存访问。第三，基于链表的实现中的淘汰和插入需要昂贵的原子操作：比较并设置（compare-and-set），这会降低可扩展性。

相比之下，基于环形缓冲区的实现开销更小，可扩展性更强，但可能与现有的基于LRU的缓存系统不兼容。当使用环形缓冲区实现S3-FIFO时，环形缓冲区维持FIFO顺序，每个槽存储对象或指针。淘汰操作需要移动环形缓冲区中的尾指针。虽然可扩展性更强且存储开销更低，但当工作负载包含许多删除操作时，基于环形缓冲区的实现会浪费空间，因为已删除对象的空间在淘汰前无法重用。

尽管S3-FIFO有三个逻辑FIFO队列，但它也可以用一个或两个FIFO队列实现。因为从S淘汰的对象可能会进入M，它们可以用一个队列和一个指向10%位置的指针来实现。然而，合并S和M会降低可扩展性，因为从队列中间移除对象需要加锁。

幽灵FIFO队列G可以作为索引结构的一部分来实现。例如，我们可以在基于桶的哈希表中存储幽灵条目的对象指纹和插入时间。指纹是对象ID的4字节哈希值。插入时间是一个虚拟时间戳，计算迄今为止插入到G中的对象数量。让SG表示幽灵队列的大小。如果当前时间是N（即有N次插入到G），那么所有时间戳低于N - SG的条目就不再在G中。当对象被请求或在哈希冲突期间——当槽位需要存储另一个条目时，幽灵条目会从哈希表中移除。

4.3 开销分析

计算 (Computation)。S3-FIFO在对一个对象的第一次和第二次请求时执行一次原子写操作，无需加锁。在第二次请求之后没有操作。因为大多数请求是针对热门对象（超过两次请求），所以S3-FIFO在缓存命中时执行的元数据更新可以忽略不计。缓存未命中需要从S或M中淘汰一个对象。从S淘汰需要将尾部对象插入到M或G。而从M淘汰可能涉及将尾部对象重新插回M。然而，如果一个对象未被访问，它就不需要重新插入。因此，实际的重新插入次数远少于缓存命中次数。此外，移除尾部对象和在队列头部插入一个对象可以使用原子操作实现无锁。

存储 (Storage)。幽灵队列G存储与主队列相同数量的对象（无数据）。假设平均对象大小为4KB，对象ID使用4字节，那么G使用的缓存大小为0.09%。每个缓存对象使用两位来跟踪访问，消耗的缓存大小不到0.01%。此外，这两位通常可以附加在对象元数据的未使用位上。如果FIFO队列使用环形缓冲区实现，S3-FIFO可以移除两个LRU指针，为每个对象节省16字节，即0.4%的缓存大小。

5. 评估

在本节中，我们评估S3-FIFO以回答以下问题。

  • S3-FIFO的效率与最先进的淘汰算法相比如何？

  • S3-FIFO是否比最先进的算法更具可扩展性？

  • 从S3-FIFO学到的经验能否帮助闪存缓存设计？

5.1 评估设置

轨迹。我们使用来自14个数据集（包括11个开源和3个专有数据集）的6594个生产轨迹来评估S3-FIFO。这些轨迹的时间跨度从2007年到2023年，涵盖了键值、块和对象CDN缓存。总的来说，这些数据集包含对610亿个对象的8560亿次请求，总计21,088 TB流量，对应3,753 TB数据。因为许多大规模分布式缓存系统是多租户的，且轨迹代表了由多个服务器服务的工作负载，我们将四个数据集（CDN 1, CDN 2, Tencent CBS, 和 Alibaba）根据租户信息分割成每个租户的轨迹，以便对工作负载进行深入研究。关于数据集的更多细节可以在表1中找到。

[表1已被忽略] 表1. 本工作中使用的数据集，没有引用的为专有数据集。对于旧数据集，我们排除了请求少于100万的轨迹。用于测量一次性奇迹比例的轨迹长度是以轨迹中对象的分数来衡量的。

模拟器。我们在libCacheSim中实现了S3-FIFO和最先进的淘汰算法（在§5.2中描述）。我们参考并验证了多个开源模拟器实现的结果 [1, 3-5, 7, 8]。对于所有最先进的算法，我们使用了原始论文中描述的参数。LibCacheSim是为高吞吐量缓存模拟设计和优化的，在单个CPU核心上可以处理高达2000万次请求。

我们还实现了一个分布式容错计算平台，允许我们并行运行数千个模拟。该平台的设计不影响模拟精度，且超出了本文的范围。我们在另一篇博客文章²中对此进行了描述。

这个分布式计算平台和Cloudlab测试床 使我们能够在我们的大数据集（表1）上评估不同的算法和缓存大小。模拟过程以近100次遍历处理了这些数据集，使用了不同的算法、缓存大小和参数。我们估计，通过使用一百万个CPU核心小时处理了超过80,000万亿次请求。

除非另有说明，我们在模拟器中忽略了对象大小，因为大多数生产系统使用slab存储进行内存管理，其中淘汰操作在相同的slab类（大小相似的对象）内执行。然而，我们注意到，对于不使用基于slab内存管理的系统，支持对象大小并非易事。此外，我们不考虑不同算法中的元数据大小，尽管S3-FIFO通常比其他算法需要更少的元数据。我们在多个不同的缓存大小下评估了算法，并展示了一个使用轨迹足迹（轨迹中对象的数量）10%的大尺寸和一个使用0.1%的小尺寸。在0.1%的轨迹足迹下，某些轨迹的缓存大小可能太小，所以如果缓存大小小于1000，我们就忽略该轨迹。

² https://blog.jasony.me/random/tool/2023/08/01/distributed-computation

… (此处省略了评估设置的更多细节，包括原型实现和硬件配置)

5.2 效率（未命中率）

未命中率。基于FIFO的淘汰算法的主要批评是它们的效率，这是缓存最重要的指标。我们将S3-FIFO与过去几十年设计的顶尖淘汰算法进行比较。比较中使用的算法要么在生产中部署，要么在其他论文中常用。我们使用所有来自模拟的效率结果，因为它允许我们(1)研究不同类型的缓存工作负载，例如块、键值和对象，(2)专注于并隔离淘汰算法的影响，(3)需要较少的计算资源来扩展评估到庞大的数据集。图6显示了不同算法相对于FIFO的（请求）未命中率降低情况。在大缓存大小下，S3-FIFO在几乎所有百分位数上都具有最大的降低幅度。例如，S3-FIFO在10%的轨迹（P90）上将未命中率降低了超过32%，平均降低了14%。

TinyLFU 是最接近的竞争者。TinyLFU使用一个1%的LRU窗口来过滤不受欢迎的对象，并将大多数对象存储在SLRU缓存中。TinyLFU的良好性能证实了我们关于快速降级对效率至关重要的观察。然而，TinyLFU并非对所有轨迹都有效，在近20%的轨迹上，其未命中率低于FIFO（P10点低于-0.05，图中未显示）。当缓存大小较小时，这种现象更为明显，TinyLFU在近50%的轨迹上比FIFO差。

TinyLFU表现不佳有两个原因。首先，1%的窗口LRU太小，导致对象淘汰过快。因此，将窗口大小增加到缓存大小的10%（TinyLFU-0.1）显著提高了尾部（图底部）的效率。然而，增加窗口大小降低了其在表现最佳的轨迹上的改进（图6a）。其次，当缓存已满时，TinyLFU会比较窗口LRU和主SLRU中最近最少使用的条目，然后淘汰使用频率较低的那个。这使得TinyLFU能更好地适应不同的工作负载。然而，如果SLRU中的尾部对象恰好具有非常高的频率，它可能导致大量新的、可能很有用的对象被淘汰。

[图6已被忽略] 图6. 每种算法在所有轨迹的不同百分位数上的未命中率降低（相对于FIFO）。降低幅度越大越好。

LIRS 使用LRU栈（重用）距离作为选择淘汰候选者的度量。因为一次性奇迹没有重用距离，LIRS使用一个1%的队列来容纳它们。这个小队列执行快速降级，是LIRS高效率的秘密来源。与TinyLFU类似，这个队列太小，在某些缓存工作负载上表现不佳。然而，与TinyLFU相比，显示出比FIFO更高未命中率的轨迹更少，因为LIRS中的交互新近度（inter-recency）度量比TinyLFU中的频率更稳健。特别是，TinyLFU无法区分许多具有相同低频率（例如2）的对象，但这些对象将具有不同的交互新近度值。缺点是LIRS需要比TinyLFU更复杂的实现。

2Q 在设计上与S3-FIFO最相似。它使用25%的缓存空间作为FIFO队列，其余的作为LRU队列，并且还有一个幽灵队列。除了队列大小和类型的差异外，从小队列中淘汰的对象不会被插入到LRU队列中。拥有一个大的试用队列并且不将被访问的对象移动到LRU队列是2Q不如S3-FIFO的主要原因。此外，与S3-FIFO中的FIFO队列（带重新插入）相比，LRU队列没有提供可观察到的好处。

… (此处省略了对SLRU、ARC、近期算法和常见算法的详细比较)

S3-FIFO的对抗性工作负载。我们研究了S3-FIFO表现不佳的少数轨迹，并确定了一种模式。这些轨迹中的大多数对象只被访问两次，而第二次请求恰好在对象从小FIFO队列S中移出后发生，这导致对这些对象的第二次请求成为缓存未命中。我们注意到，这些工作负载对于大多数划分缓存空间的算法都是对抗性的，例如TinyLFU、LIRS、2Q和CACHEUS。因为用于新插入对象的分区小于缓存大小，所以第二次请求可能在LRU和FIFO中是缓存命中，但在这些高级算法中则不是。

… (此处省略了对每个数据集未命中率和字节未命中率的更详细讨论)

5.3 性能（吞吐量）

S3-FIFO仅由FIFO队列组成，在读或写上都无需加锁。相比之下，基于LRU的淘汰算法，如LRU、2Q和TinyLFU，在缓存命中和未命中时都需要加锁。我们在Cachelib中实现了S3-FIFO，以比较不同算法的吞吐量。由于原型实验运行时间更长且无法并行运行，我们仅使用类似于先前工作的合成Zipf轨迹进行评估。此外，我们验证了原型的未命中率结果与使用一些随机选择的轨迹的模拟器是一致的。Zipf工作负载包含100·nthread百万次对nthread百万个4KB对象的请求。图8显示，与基于LRU的淘汰算法相比，S3-FIFO在缓存命中期间执行的操作更少，单线程吞吐量更高。此外，无锁实现使其吞吐量能够随CPU核心数扩展。在小缓存和大缓存大小下，S3-FIFO在16个线程上比Cachelib中优化的LRU快6倍以上。

[图7已被忽略] 图7. 不同算法在每个数据集上的平均未命中率降低。TinyLFU在TencentPhoto数据集大尺寸下的值为-0.11，未显示。

[图8已被忽略] 图8. 在合成Zipf (α = 1.0) 轨迹上，吞吐量随CPU核心的扩展情况。

5.4 闪存友好性

在许多闪存缓存部署中，闪存存储所有缓存的对象，而DRAM用于存储热门对象（和索引）。然而，将所有数据写入闪存会降低其寿命。

使用一个小的FIFO队列来执行快速降级可以实现最先进的未命中率，这一惊人发现对闪存缓存设计具有启示。因为从S队列淘汰的大多数对象不值得保存在M队列中，我们可以将S放在DRAM中，将M放在闪存上。从DRAM淘汰的对象不会被写入闪存。只有在S和G中被请求的对象才会被写入闪存。这种设置既减少了闪存写入，也降低了未命中率。

… (此处省略了对闪存友好性实验的详细描述和图9的讨论)

6. 讨论

6.1 S3-FIFO为何有效？

S3-FIFO效率的关键是那个能够过滤掉一次性奇迹的小型试用FIFO队列S。移除低价值物品并非新概念。准入算法，如布隆过滤器、Adaptsize，都是为类似目的设计的。然而，它们拒绝对象过早，对大多数缓存工作负载表现出低效率。除了准入算法，许多为抗扫描设计的缓存淘汰算法，如ARC和2Q，也有类似的想法。它们将新对象和频繁访问的对象分成两个队列（用S和M表示），这样热门对象就不会受到扫描请求的影响。这项工作表明，一个小的静态FIFO队列，这种最简单的过滤低价值对象的设计之一，比许多更先进的替代方案效果更好。

[图9、图10和表2已被忽略]

但为什么呢？我们使用§3中的相同轨迹，通过更仔细地研究降级速度和精度来获得更深入的理解。归一化的快速降级速度衡量对象在被淘汰或移至M之前在S中停留的时间。我们使用LRU淘汰年龄作为基准… 快速降级精度衡量从S中淘汰的对象中有多少在短期内没有被重用…

一个既有更快降级速度又有更高降级精度的算法会展现出更低的未命中率。图10显示，ARC、TinyLFU和S3-FIFO能快速降级新对象，并且与LRU相比具有更低的未命中率（表2）。

… (此处省略了对ARC、TinyLFU和S3-FIFO在降级速度和精度上的详细比较)

总而言之，S3-FIFO保证了新插入的不受欢迎的对象在一个可预测的短时间内被淘汰。这种快速降级通常比现有方法更精确和稳健。这种组合使得S3-FIFO能够获得优于最先进技术的未命中率。

6.2 那么自适应淘汰算法呢？

队列大小是否敏感？ 我们根据十个轨迹的结果选择S使用10%的缓存大小，并发现它在6594个轨迹中具有很好的泛化性。图11显示了未命中率随S大小的变化情况。我们观察到，一个较小的S会导致更大的未命中率降低，证实了快速降级的重要性… 总体而言，效率和S大小之间的可预测性使得选择S的大小变得容易。而且对于大多数轨迹，如果S的大小在缓存大小的5%到20%之间，效率变化不大。

[图11已被忽略] 图11. 使用不同大小的小FIFO队列的未命中率降低百分位数。左图：大缓存；右图：小缓存。

使队列大小自适应！ 我们设计并实现了一种自适应改变FIFO队列大小的算法，我们称之为S3-FIFO-D… S3-FIFO-D在从S和M淘汰的对象上的边际命中之间保持平衡…

… (此处省略了对自适应算法S3-FIFO-D的详细描述、评估及其失败原因的讨论)

6.3 LRU还是FIFO？

S3-FIFO只使用FIFO队列，但LRU队列能提供更好的效率吗？我们通过用LRU队列替换小FIFO队列和主FIFO队列，试验了不同的队列类型组合。我们还试验了在缓存命中和淘汰期间将对象从S移动到M。由于空间限制，结果未显示，但我们观察到LRU队列并未提高效率。特别是，使用两个LRU队列，如ARC中那样，在大多数情况下比S3-FIFO差。总之，有了快速降级，队列类型就不那么重要了。

7. 相关工作

我们在§2和§5.2中已经讨论了许多相关工作。本节我们讨论其余部分。

面向效率的缓存设计。除了我们比较的淘汰算法，还有许多其他算法旨在提高缓存效率。S3-FIFO与现有算法的不同之处在于以下几点。首先，S3-FIFO仅使用FIFO队列，并且在缓存命中时不需要提升操作。其次，S3-FIFO明确保证了一次性奇迹在测试其流行度之前在缓存中停留的时间。第三，这项工作显示了为什么需要一个非常小的试用缓存，并使用了比大多数先前工作更小的试用队列。

… (此处省略了对其他相关工作的详细讨论，包括可扩展性设计、闪存耐久性等)

8. 结论

我们证明，缓存通常经历比普通完整轨迹分析更高的一次性奇迹比例。我们对6594个轨迹的研究揭示，快速移除一次性奇迹（快速降级）是许多先进算法的秘密武器。受此启发，我们设计了S3-FIFO，一个仅由静态FIFO队列组成的简单且可扩展的缓存淘汰算法。我们的评估表明，S3-FIFO实现了比最先进算法更好、更稳健的效率。同时，它比基于LRU的算法更具可扩展性。

可用性

本工作中使用的代码和数据在以下地址开源：https://github.com/TheSys-lab/sosp23-s3fifo。这包括模拟器、原型和我们的容错分布式计算平台。

我们还为不同编程语言开发了使用S3-FIFO的缓存库。更多信息可在https://s3fifo.com获得，该网站提供文档并跟踪S3-FIFO在生产系统中的采用情况。

致谢

(致谢部分内容已省略)

参考文献

[1~169] (参考文献列表的翻译已省略，以保留原始引用格式的准确性。)