这篇技术文档的中文翻译如下：

摘要 本文提出了一种基于频率的缓存准入策略，以提高受访问分布偏差影响的缓存的有效性。给定一个新访问的项目和缓存中的一个驱逐候选项，我们的方案基于最近的访问历史来决定，是否值得以驱逐候选项为代价将新项目纳入缓存。 实现这一概念是通过一种新颖的近似LFU（最近最少使用）结构，称为TinyLFU，它维护了一个最近访问的大样本项目的访问频率的近似表示。TinyLFU非常紧凑和轻量级，因为它建立在布隆过滤器理论之上。 我们通过模拟合成工作负载以及多个来源的多个真实跟踪来研究TinyLFU的属性。这些模拟展示了通过增强各种替换策略与TinyLFU驱逐策略所获得的性能提升。此外，还介绍了一种新的组合替换和驱逐策略方案，昵称为W-TinyLFU。W-TinyLFU被证明在这些跟踪上获得等于或优于其他最先进替换策略的命中率。它是唯一在所有跟踪上都能获得如此好结果的方案。

说明：

  • “cache admission policy” 指的是缓存准入策略，即决定哪些数据可以被存储在缓存中的规则。
  • “eviction candidate” 指的是可能被从缓存中移除的数据项。
  • “access history” 指的是数据访问的历史记录。
  • “LFU” 指的是最近最少使用算法，一种缓存替换算法。
  • “TinyLFU” 是一种近似的LFU算法，它使用布隆过滤器（Bloom filter）理论来近似地表示数据的访问频率。
  • “Bloom filter” 是一种空间效率很高的数据结构，用于测试一个元素是否是一个集合的成员。
  • “synthetic workloads” 指的是人工合成的工作负载，通常用于模拟真实世界的情况。
  • “real traces” 指的是从实际系统中收集的数据。
  • “hit-ratios” 指的是命中率，即缓存中成功找到请求数据的比率。

希望这个翻译对你有所帮助。如果需要更详细的解释或有其他问题，请随时告知。

1 引言

缓存是计算机科学中最基本和有效的方法之一，用于提升多个领域系统的性能。通过在一个更快速或更接近应用程序的内存中保留一小部分数据项来实现。当整个数据域无法适应这个快速的近端内存时，就会采取这种方式。缓存有效的直觉原因是计算机科学的许多领域中的数据访问展现出相当程度的“局部性”。更正式地捕捉这种“局部性”的方式是通过概率分布表征所有可能的数据项的访问频率，并注意在计算机科学的许多有趣的领域中，概率分布是高度偏斜的，意味着少数对象比其他对象更有可能被访问。此外，在许多工作负载中，访问模式以及相应的概率分布会随时间改变。这种现象也被称为“时间局部性”。

当一个数据项被访问时，如果它已经存在于缓存中，我们称之为缓存命中；否则，它是缓存未命中。缓存命中率是缓存命中次数与总数据访问次数之比。因此，如果缓存中的项对应于最常访问的项，那么缓存可能会产生更高的命中率[33]。

鉴于缓存大小通常是有限的，缓存设计者面临如何选择存储在缓存中的项的困境。特别是当为缓存保留的内存变满时，决定哪些项应该从缓存中删除。显然，应该高效地做出驱逐决策，以避免计算和空间开销超过使用缓存的好处。用于决定哪些项应该插入到缓存中，哪些项应该被驱逐的缓存机制使用的空间被称为缓存的元数据。在许多缓存方案中，操作元数据的时间复杂性以及元数据的大小与存储在缓存中的项的数量成比例。

当数据访问模式的概率分布随时间保持不变时，可以容易地显示最少使用（LFU）产生最高的缓存命中率[8, 51]。根据LFU，在大小为n的项的缓存中，每时每刻都保留迄今为止使用最频繁的n个项。然而，LFU有两个重大局限性。首先，已知的LFU实现需要维护大型和复杂的元数据。其次，在大多数实际工作负载中，访问频率会随时间发生剧烈变化。例如，考虑一个视频缓存服务；在某一天非常受欢迎的视频片段可能几天后就不再被访问了。因此，一旦其受欢迎程度下降，就没有必要继续保留该项在缓存中。

因此，已开发了LFU的各种替代方案。其中许多包括老化机制和/或专注于最近W次访问的有限大小窗口。这种老化旨在限制元数据的大小，并调整缓存和驱逐决策以适应项目的更近期的受欢迎程度。一个著名的例子是称为窗口LFU（WLFU）[38]的方案，如下所述。此外，在绝大多数情况下，新访问的项总是被插入到缓存中，缓存方案仅专注于其驱逐策略，即决定哪个项应该被驱逐。这是因为维护不在缓存中的对象的元数据被认为是不切实际的。

值得注意的是，由于维护所有曾经遇到的对象的频率直方图的成本极高，实施LFU方案的已发表作品仅维护缓存中的项目的频率直方图[48]。因此，我们通过称前者为完美LFU（PLFU）和后者为内存LFU来区分它们。由于WLFU优于内存LFU[8]（以更大的元数据为代价），因此我们只讨论WLFU和PLFU。

一个依赖于“时间局部性”属性的LFU的流行替代方案称为最近最少使用（LRU）[33]，其中最后访问的项总是被插入到缓存中，最近最少访问的项在缓存满时被驱逐。

与LFU相比，LRU的实现要高效得多，并自动适应数据访问模式的时间变化和工作负载的突发性。

然而，在许多工作负载下，为了获得相同的命中率，LRU需要比LFU更大的缓存（requires much larger caches）。

PS: 这个需要更大的缓存，应该是值需要内存占用更大，来存储对应的数据。

2 相关工作

2.1 缓存替换

如引言中所示，当访问分布是静态的时，PLFU是一个最优的策略，但维护所有曾经访问过的数据项的完整频率直方图的成本非常高，而且PLFU不能适应分布中的动态变化[38, 3, 2]。

因此，提出了几种替代方案。

内存中的LFU仅维护已经在缓存中的数据项的访问频率，并始终将最近访问的项插入到缓存中，如果需要的话，将缓存中最不经常访问的项驱逐出去[48]。通常使用堆来维护内存中的LFU。直到最近，管理LFU堆的时间复杂性被认为是O(log(N))，在[40]中展示了一个O(1)的构造方法。然而，即使有了这一改进，内存中的LFU仍然对频率分布的变化反应缓慢，其性能在静态分布中明显落后于PLFU，因为它不维护不再在缓存中的项的任何频率统计信息[48]。

在[3]中引入了老化机制，以改善内存中的LFU对变化的反应能力。通过限制缓存项的最大频率计数以及偶尔将缓存项的频率计数除以给定的因子来实现。确定何时以及以多大比例除以计数器是有技巧的，并需要精细调整[2]。

如上所述，WLFU只维护最后W次请求的访问频率[38]。为了维护这个窗口，机制需要跟踪请求的顺序，这增加了开销。然而，与PLFU相比，WLFU对访问分布中的动态变化适应得更好。

ARC [44, 45]通过在两个LRU列表中维护元数据来结合最近性和频率。第一个反映了只被访问一次的项目，而第二个对应于最近历史中至少被访问两次的项目。ARC通过根据它们的命中率从两个列表中平衡其缓存内容源来调整自己以适应工作负载的特性。为了做到这一点，ARC监控了最近从缓存中驱逐的项目的访问数据。如果从LRU列表中驱逐的项目再次命中，ARC扩展此列表，并更像LRU。如果最近从第二个LFU列表中驱逐的项目被命中，ARC扩展LFU列表的大小，并行为更类似于LFU。监控最近从缓存中驱逐的项目的技术称为幽灵条目，在最先进的缓存策略中已经变得非常常见。

LIRS [36]（低间接参考时效集）是一个页面替换算法，试图直接预测项目的下一个出现，使用一个名为重用距离的指标。为此，LIRS监控了过去在缓存中和从缓存中驱逐的许多过去项目的到达时间。因此，LIRS也维护了大量的幽灵条目。

分段LRU（SLRU）[39]策略通过在短窗口内区分时间上受欢迎的项目（在此期间至少被访问两次）和仅在此期间被访问一次的项目来捕获最近的流行度。这种区分是通过通过两个固定大小的LRU段管理缓存来完成的，即试用段（A1）和受保护段（A2）。新项目总是插入到试用段。当试用段中已有的项目再次被访问时，它被移到受保护段。如果试用段变满，插入到其中导致根据LRU策略驱逐（并遗忘）其项目。同样，任何插入到满的受保护段都会导致驱逐其LRU受害者。然而，在这种情况下，受害者被重新插入到试用段，而不是完全遗忘。这样，达到受保护段的时间上受欢迎的项目将在缓存中停留得比不太受欢迎的项目长。

2Q [37]是一个操作系统的页面替换策略，管理两个FIFO队列，A1和A2。A1分为两个子队列，A1in（驻留）和A1out（非驻留）。当首次访问项目时，它被输入到A1in，并在根据FIFO策略驱逐它之前一直保持在那里。然而，当项目从A1in或A2中被驱逐时，它被插入到A1out。如果访问的项目既不在A1in也不在A2，但它出现在A1out中，则将其插入到A2。

LRU-K [47]也结合了LRU和LFU的思想。在此策略中，每个元素的最后K次出现都被记住。使用这些数据，LRU-K统计估计项目的瞬时频率，以保持内存中最频繁的页面。

Web缓存方案通常还考虑对象的大小。例如，SIZE [56]建议首先简单地删除最大的项目，而相同大小的项目按LRU排序。LRU-SP [11]在选择缓存受害者时权衡项目的大小和频率。

GDSF [13]是一个混合Web缓存策略，它在其决策中结合了最后访问的新颖性、将对象带到缓存的成本、对象大小和其频率。它是贪婪双算法[57]的改进，只考虑大小和成本。在[4]中，当数据是分层的，即为了获取子项目必须首先获取其前身项目时，还考虑了延迟。

与我们相关的方法在[53]中引入，该方法建议使用热列表来增强已知的缓存算法。这个列表使用某种衰减机制指示最受欢迎的项目。热列表中的项目在驱逐策略中优先于其他项目。然而，是否驱逐缓存中的项目的决定并不取决于这个项目的相对频率与当前访问的项目的频率。此外，必须维护n个项目的显式列表。这种方法在[53]中被证明可以在显著的元数据开销的代价下提高各种缓存建议的命中率。

总结而言，TinyLFU与上述建议有关，因为它是一个机制，可以通过在大历史上增强近似统计信息来增强其他缓存策略，同时提供快速访问时间和低元数据开销。

2.2 近似计数架构

近似计数技术在许多网络应用中被广泛使用。近似计数最初是为了维护每个流的网络统计信息而开发的。这些构造对缓存也很有吸引力，因为它们提供非常快速的更新并且占用紧凑的大小。

采样方法[16, 35, 25]提供了较小的内存占用，但需要显式表示键。此外，它们通常遇到相对较大的误差界限。因此，我们选择不使用它们，因为在我们的上下文中，键的大小是总体成本的一个重要部分。

其他方法，如Counter Braids [42]，减少了元数据大小，但需要长时间的解码操作，因此不适用于缓存。另一种方法是压缩计数器表示本身[52, 34, 54, 20]。在TinyLFU中，我们设法使用短计数器来表示直方图，因此这些方法对我们没有帮助。

多哈希草图，如Spectral Bloom Filters (SBF) [17] 和 Count Min Sketch (CMSketch) [18] 在我们的上下文中很有吸引力。由于这些草图隐式地关联键和计数器，因此不需要在频率直方图中存储键。然而，它们对我们的情况并不是最优的。特别是，SBF包括一个复杂的实现，旨在实现可变大小的计数器。在我们的情况下，不需要这样复杂的实现，因为我们只需要小的计数器。另一方面，CM-Sketch提供了一个简单的实现，但相对不准确，因此比Counting Bloom Filter [27]占用更多的空间。

当所有增量都是正数时，最小增量方案，也称为保守更新，已被提议作为提高Counting Bloom Filters准确性的一种方法[17, 26, 23]。这种技术在几个领域成功地被使用了[46, 50, 5, 32, 7, 6, 41, 31, 30]。

2.3 有趣的缓存应用

数据缓存可以用作云服务[14, 15]。MemcacheD [28]允许内存中缓存数据库查询及其相关项，并被许多实际服务广泛部署，包括Facebook和Wikipedia。

缓存也被应用在数据中心的网络级别，内部路由器使用一种称为网络内缓存的技术[49, 10]。这种技术允许明确命名内容，并允许数据中心的路由器缓存数据以增加网络容量。在点对点系统中，TinyLFU也被用于加速Kademlia查找过程[24]，有效地增加了容量并减少了延迟。

TinyLFU可以集成到上述所有示例中。对于网络内缓存，TinyLFU很有吸引力，因为它需要非常小的内存开销，并且可以有效地在硬件中实现。至于MemcacheD和云缓存服务，[28, 15]的驱逐策略是LRU的变体，没有准入策略。正如我们在本文中所展示的，为基于LRU的驱逐策略添加基于TinyLFU的准入策略大大提高了其性能。

3 TinyLFU架构

3.1 TinyLFU 概述

TinyLFU的架构如图1所示。在这里，缓存淘汰策略选择一个缓存受害者，而TinyLFU则决定用新项替换缓存受害者是否预期能提高命中率。

为了实现这一点，TinyLFU维护了近期历史上项的频率统计信息。存储这些统计信息在实际实现中被认为是成本过高的，因此TinyLFU以高效的方式近似它们。

接下来，我们描述了我们为TinyLFU采用的技术，其中一些是已知的近似计数技术的适应，而其他一些是专为缓存上下文而创建的新想法。

我们要强调的是，我们面临两个主要挑战。第一个是维护一个新鲜度机制，以保持历史的新鲜，并删除旧事件。

第二个是内存消耗的开销，这应该得到显著的改进，以被认为是一种实用的缓存管理技术。

tiny-LFU

3.2 近似计数概述

计数Bloom过滤器是一个Bloom过滤器，其中向量中的每个条目都是一个计数器而不是一个单一的位。因此，与设置与过滤器的哈希函数对应的索引的位不同，这些条目在插入/添加操作上增加。

最小增量CBF是一个增强的计数Bloom过滤器，支持两种方法：Add和Estimate。Estimate方法通过计算键的k个不同的哈希值来执行。每个哈希值被视为一个索引，并读取该索引处的计数器。这些计数器的最小值是返回的值。Add方法也为键计算k个不同的哈希值。但是，它读取所有k个计数器，只增加最小计数器。例如，假设我们使用如图2所示的3个哈希函数。在项目到达时，读取3个计数器。假设我们读取{2, 2, 5}，Add操作只增加从2到3的两个左侧计数器，而第三个计数器保持不变。直观地说，这个Add操作防止不必要地增加大计数器，并为高频项提供更好的估计，因为这些计数器不太可能被大多数低频项增加。它不支持减少，但已经证明在高频计数中减少错误[17]。

其他近似计数方案：如上所述，CM-Sketch是另一种流行的近似计数方案[18]。它在空间换精度上提供了稍低的准确性。然而，人们普遍认为它更快。

我们下面描述的空间优化和老化机制同样可以应用于CM-Sketch。

TinyLFU的描述不考虑选择Counting Bloom Filter和CM-Sketch之间的选择。

3.3 新鲜度机制

据我们所知，保持近似草图的新鲜度只在[19]中被研究过，该研究通过维护m个不同草图的有序列表来获得滑动样本。新项目被插入到第一个草图中，并在一定数量的插入后清除最后一个草图，并移动到列表的头部。这样，旧事件就被遗忘了。

[19]的方法不太吸引人作为频率直方图，有两个原因：首先，为了评估一个项目的频率，需要读取m个不同的近似草图，导致大量的内存访问和哈希计算。其次，这种方法增加了空间消耗，因为我们需要在m个不同的草图中存储相同的项目，并且每个项目都分配更多的计数器。

相反，我们提出了一种新颖的方法来保持草图的新鲜度，即下面描述的重置方法。重置操作很简单。每次我们向近似草图添加一个项目时，我们增加一个计数器。一旦这个计数器达到样本大小(W)，我们将它和近似草图中的所有其他计数器除以2。这种除法有两个有趣的优点。首先，它不需要太多的额外空间，因为它唯一增加的内存成本是一个Log(W)位的单个计数器。其次，这种方法提高了高频项的准确性，我们通过分析和实验都证明了这一点。由于近似草图的准确性总是可以通过使用更多的空间来增加的，我们证明重置方法实际上减少了总空间成本，因为我们为相同的空间得到了一个显著更准确的草图。

这个操作的缺点是一个昂贵的不频繁的操作，它遍历近似方案中的所有计数器，并将它们除以2。然而，除以2可以在硬件中使用移位寄存器有效地实现。同样，在软件中，移位和掩码操作允许一次为多个（小）计数器执行此操作。最后，它的摊销复杂性是常数，使得它对于许多应用都是可行的。

在以下的子部分中，我们证明了重置操作的正确性并评估了它的截断误差。截断误差是由于我们使用整数除法引起的，因此显示3的计数器将被重置为1，而不是1.5。

3.3.1 重置正确性

在本节中，我们在计数基础设施工作准确的假设下分析TinyLFU操作。在结果部分，我们将探讨为保持性能与准确计数技术相同所需的空间量。

定义：记W为样本大小，fi为项目i的频率，hi为TinyLFU中i的估计。

引理3.1 在恒定分布下，在每个样本结束时（即在每次重置操作之前），直方图中i的预期频率为E(hi) = fi·W。

IEEE证明 通过对执行的重置操作次数r进行归纳。

基础：对于r = 0，条件显然成立。我们在恒定分布下连续采样W个项目。根据定义，项目i的频率为fi。因此，直方图的预期高度是E(hi) = fi·W。

步骤：假设r < j时正确性成立，并证明r = j时成立。根据归纳假设，直到第j-1次重置操作发生，E(hi) = fi·W。因此，在第j-1次重置操作后，E(hi) = fi·W/2。在下一次重置操作之前，恰好有W/2个样本，因此预期E(hi)将增加fi·W/2次。由于期望是可加的，我们得出结论，在第j次重置操作之前，E(hi) = fi·W。

上述引理证明了在恒定分布下TinyLFU收敛到正确的频率。为了证明TinyLFU能够适应变化，我们证明了一个略微更强的引理，即在恒定分布下，最终TinyLFU无论其初始值如何，都会收敛到正确的频率。 引理3.2 在恒定分布下，最终E(hi) = fi·W。

IEEE证明 考虑重置操作之前hi的初始值。我们将此值写为fi·W + σ，其中σ是误差。例如，如果hi = 10但fi·W = 8，那么σ = 2。执行重置操作后，hi将为：hi = fi·W/2 + σ/2。下一个重置操作计划在W/2事件内发生，平均来说，下一个重置操作之前的hi将增加fi·W/2。因此，其新值将为hi = fi·W/2 + σ/2 + fi·W/2 = fi·W + σ/2。我们可以重复此过程k次，并得到在k次更多样本后，hi的值将是：hi = fi·W/2 + σ/2k + fi·W/2 = fi·W + σ/2k。因此，如果我们取k趋于无穷大，我们得到：

lim(k→∞)(fi·W + σ/2k) = fi·W

在实践中，由于我们使用整数除法，初始误差在log2(σ)样本后被消除。然而，在这种情况下，还存在截断误差，如下所述。

3.3.2 重置截断误差

由于我们的重置操作使用整数除法，它引入了截断误差。

也就是说，在重置操作后，计数器的值可以比浮点计数器低高达0.5。

如果我们需要再次重置，在上次重置操作的截断误差被减少到0.25，但我们积累了一个新的截断误差0.5，导致总误差为0.75。很容易看出，最坏情况的截断误差收敛至比项目的准确率低不超过一个点。

因此，截断误差在重置操作后影响项目的记录发生率多达2/W。这意味着样本大小越大，截断误差越小。

3.4 空间优化 Space Reduction

我们通过两个独立的维度获得空间优化：首先，我们减小了逼近草图中每个计数器的大小。其次，我们减少了草图分配的计数器总数。以下详细介绍这些空间节省的优化。

3.4.1 小计数器 Small Counters

天真地实现逼近草图需要使用长计数器。如果一个草图包含 W 个唯一请求，那么需要允许计数器计数到 W（因为原则上一个项目在这样的样本中可能被访问 W 次），每个计数器的大小为 Log(W) 位，这可能成本高昂。

幸运的是，重置操作和以下观察的结合显著减少了计数器的大小。

具体来说，频率直方图只需要知道已在缓存中的潜在替换受害者是否比当前正在访问的项目更受欢迎。但是，频率直方图无需确定缓存中所有项目之间的确切顺序。

此外，对于大小为 C 的缓存，所有访问频率高于 1/C 的项目都应该在缓存中（在合理的假设下，正在访问的项目总数大于 C）。因此，对于给定的样本大小 W，我们可以安全地将计数器限制为 W/C。

注意，这种优化是可能的，因为我们的“老化”机制基于重置操作，而不是滑动窗口。对于滑动窗口，在某个项目 i 在 W/C 个连续访问和随后的 W/C + 1 次访问其他项目之间交替的访问模式中，i 可能会被驱逐，即使 i 是缓存中最频繁访问的项目。

为了感受计数器大小，当 W/C = 8 时，每个计数器只需要 3 位，因为样本比缓存本身大 8 倍。作为比较，如果我们考虑一个小型的 2K 项目缓存，样本大小为 16K 项目，而且我们不使用小计数器优化，那么所需的计数器大小是 14 位。

3.4.2 门卫机制 Doorkeeper

在许多工作负载中，尤其是在重尾分布的工作负载中，不受欢迎的项目占据了所有访问的相当大一部分。这种现象意味着如果我们计算样本中每个唯一项目出现的次数，大多数计数器被分配给不太可能在样本内出现超过一次的项目。因此，为了进一步减小计数器的大小，我们开发了门卫机制，使我们能够避免为大多数尾部对象分配多位计数器。

门卫是一个普通的布隆过滤器，放在逼近计数方案的前面。在项目到达时，我们首先检查项目是否包含在门卫内。如果项目不包含在门卫内（如预期的第一次访问者和尾部项目），则将项目插入到门卫中，否则，它将插入到主结构中。在查询项目时，我们同时使用门卫和主结构。也就是说，如果项目包含在门卫中，TinyLFU 估计此项目的频率为主结构中的估计值加 1。否则，TinyLFU 只从主结构返回估计值。

在执行重置操作时，我们除了将主结构中的所有计数器减半外，还清除了门卫。这样做使我们能够删除有关第一次访问者的所有信息。

不幸的是，清除门卫也将每个项目的估计值降低了 1，这也增加了截断误差 1。

  • F3&F4 Figure 4: TinyLFU vs unoptimized approximate frequency histogram

F4

内存方面，尽管门卫机制需要额外的空间，但它允许主结构更小，因为它限制了插入主结构的唯一项的数量。

特别是，大多数尾部项目只分配了1位计数器（在门卫机制中）。

因此，在许多偏斜的工作负载中，这种优化显著降低了TinyLFU的内存消耗。TinyLFU和门卫机制在图3中有所说明。

我们注意到，之前在网络安全的背景下曾提出过类似的技术[9]。

3.5 测试案例：TinyLFU 对比一种简单模型

为了推动TinyLFU的设计，我们将其与一种简单模型进行了比较。这种简单模型等同于仅使用现有的近似计数建议构建频率直方图。

为了保持项目的新鲜度，简单模型使用了在[19]中提出的滑动窗口近似。也就是说，简单模型使用了10个不同的近似计数草图以模仿滑动窗口。此外，简单模型没有门卫机制或计数器上的限制，因此需要允许其计数器增长到最大窗口大小。

我们的测试案例是一个由1K项缓存扩展的9K项频率直方图。对于这个工作负载，TinyLFU需要其计数器计数到9。

这个计数是通过使用能够计数到8的3位完整计数器以及可以计数到1的门卫机制来获得的。简单模型使用了10个每个有900项的近似计数草图，其计数器大小为10位。在这个示例中，我们考虑了一个Zipf 0.9分布，这是许多有趣的实际工作负载的特征，例如[8, 51, 29]。

我们在图4中总结了两种频率直方图的存储需求。可以观察到，在这个工作负载中，由于TinyLFU使用单一的大草图而不是10个小草图，所以需要存储的独特值大约减少了10%。

此外，在这个实验中，绝大多数项目仅使用了1位的小计数器。在这个样本中出现超过一次的频繁项由于小计数器优化而分配了额外的3位计数器。

总体而言，对于这个工作负载，我们注意到TinyLFU将简单模型的内存消耗减少了约89%。

3.6 将TinyLFU连接到缓存

将TinyLFU连接到LRU和随机缓存并将缓存视为黑箱是微不足道的。

然而，由于TinyLFU使用一个将项目频率减半的重置，我们被迫修改LFU缓存的实现，以便与TinyLFU正确连接。

特别是，我们需要同步TinyLFU的重置操作与缓存，并同样重置缓存项目的频率。

4 W-TinyLFU 优化

TinyLFU已经被整合到开源的高性能Java缓存库Caffeine [43]中。通过使用这个库进行的广泛基准测试，我们发现虽然TinyLFU在来源于互联网服务和人工Zipf-like跟踪的情况下表现良好，但在与最先进的缓存策略相比，仍有一些工作负载中TinyLFU的表现不佳。这主要发生在包含对同一对象的“稀疏突发”跟踪中，这在存储服务器中很常见。也就是说，在这些情况下，属于新突发的项目在被驱逐之前无法建立足够的频率以保持在缓存中，导致重复的未命中。

我们在Caffeine的整合中通过设计一个名为Window Tiny LFU（W-TinyLFU）的策略来解决这个问题，该策略由两个缓存区域组成。

  • F5

F5

主缓存采用SLRU驱逐策略和TinyLFU入场策略，而窗口缓存采用无入场策略的LRU驱逐策略。主缓存中SLRU策略的A1和A2区域静态地划分，使80%的空间分配给热门项目（A2），并从20%的非热门项目（A1）中选择受害者。

任何到达的项目总是被允许进入窗口缓存，并且窗口缓存的受害者有机会被允许进入主缓存。如果被允许，那么W-TinyLFU的受害者是主缓存的受害者，否则是窗口缓存的受害者。W-TinyLFU方案在图5中进行了说明。

在当前版本的Caffeine（2.0）中，窗口缓存的大小是总缓存大小的1%，主缓存的大小是99%。W-TinyLFU的动机是在LFU工作负载中使方案的行为像TinyLFU，同时还能够利用LRU模式，如突发。因为99%的缓存分配给了主缓存（使用TinyLFU），所以对LFU工作负载的性能影响可以忽略不计。另一方面，某些工作负载允许利用LRU友好模式。

在这些工作负载中，W-TinyLFU比TinyLFU更好。正如我们在下面的第5节中报告的，对于Caffeine的需求，W-TinyLFU是更多工作负载的首选替代方案，因此增加的复杂性是合理的。

TinyLFU作为后来者被添加到Caffeine项目中。这样做的经验为TinyLFU与其他最先进的方案相比提供了几个定性的优点。如我们上面提到的，后者通常维护ghost条目，这增加了实现的复杂性。此外，它们涉及更高的内存开销。W-TinyLFU在Caffeine中的总体空间开销为每个缓存条目的8字节，这比ARC和LIRS的开销明显低。

同时，TinyLFU（和W-TinyLFU）的开发时间也明显更快，因为该策略的侵入性较小，无需重新设计主要的驱逐方案来考虑污染其他数据结构的ghost条目。

5 实验结果

5.1 方法论

在这一部分，我们检查TinyLFU作为一个实用的缓存入场策略的效用。我们的评估分为三部分：首先，在第5.2节中，我们检查使用TinyLFU入场策略增强三种基线驱逐策略（即LRU、Random和LFU）的影响。这部分是使用一个可以根据给定的缓存大小（以存储的项目数量为单位）、包含访问跟踪的文件以及上述任一缓存管理方案来实例化的Java原型进行的。原型然后使用所有在第1节中描述的优化的Counting Bloom Filter消耗文件，为每次访问返回是否根据所选管理方案和缓存大小它将是命中还是未命中，以及整体统计数据。

我们的第二组评估，报告在第5.3节中，是使用实际的Caffeine实现[43]进行的。在当前版本的Caffeine（2.0）中，TinyLFU直方图维护一个是缓存大小10倍的样本。此外，Caffeine使用CM-Sketch（带有我们的空间优化和老化机制）而不是Counting Bloom Filters，因为即使使用CM-Sketch，这样大的样本也只需要每个缓存项8字节，另一方面Caffeine的任务是高吞吐量。我们已经比较了大量缓存管理策略的命中率。然而，为了简洁起见，我们只报告表现最佳的那些。在第三组测量中，报告在第5.4节中，我们探讨了TinyLFU的各种机制累积的各种错误以及总错误。

对于评估，我们使用Zipf 0.7和Zipf 0.94的恒定分布，以及一个类似SPC1的合成跟踪[44]（以下标记为SPC1-like）以及真实跟踪。在合成的Zipf跟踪中，根据来自100万对象集的相应分布选择项目。此外，缓存被给予了长时间的预热时间（样本大小的20倍），我们将它们展示为最高的命中率。SPC1-like跟踪包含长时间的顺序扫描以及随机访问，并且页面大小为4 K字节[44]。在真实跟踪中，缓存没有预热；由于分布随时间逐渐变化，所以不需要预热。

我们的真实工作负载来自各种来源，并代表多种类型的应用程序，如下所述： • YouTube：一个YouTube跟踪是从一个YouTube数据集[12]生成的。具体来说，[12]中的跟踪包括每个视频的每周访问次数的周总结，而不是连续的请求时间线。因此，对于每个报告的周，我们计算了相应的近似访问分布，并且每周基于这个分布生成了合成访问。 • Wikipedia：一个包含10%流量的Wikipedia跟踪，在2007年9月开始的两个月[55]。 • DS1：从[44]中取得的数据库跟踪。 • S3：从[44]中取得的搜索引擎跟踪。 • OLTP：一个OLTP服务器的文件系统跟踪[44]。值得注意的是，在典型的OLTP服务器中，大多数操作都是在内存中已有的对象上执行的，因此对磁盘访问没有直接反映。因此，大多数磁盘访问是写入事务日志的结果。也就是说，跟踪主要包括顺序块访问的上升列表，其中散布了由于偶尔的写入重播或内存缓存未命中导致的少量随机访问。 • P8和P12：来自[44]的两个Windows服务器跟踪。 • Glimpse：描述执行分析查询的Glimpse系统的跟踪[36]。这个跟踪的主要特点是一个下划线循环，以及其他类型的访问。 3 总元数据大小更大，因为LRU策略被维护为一个带有前向和后向指针的队列，每个内存项都添加了两个指针。 4我们已经尝试了几种其他偏斜分布，并获得了非常相似的定性结果。

• F1 和 F2：从两家大型金融机构运行的应用程序的跟踪，取自Umass跟踪存储库[1]。由于上述相同的原因，这些在结构上与OLTP跟踪相当相似。 • WS1、WS2 和 WS3：三个额外的搜索引擎跟踪，同样取自Umass存储库[1]。

注意，DS1、OLTP、P8、P12 和 S3 的跟踪由ARC的作者[44]提供，并代表潜在的ARC应用程序。SPC1-like合成跟踪也是由ARC的作者[44]提供的。类似地，Glimpse跟踪是由LIRS的作者[36]提供的。

我们还使用了YouTube工作负载来测量分布动态对性能的影响。为此，我们没有播放一周的所有观看量，而是只播放了每周的几个样本。这些测试模拟了工作负载非常动态时缓存的行为。

在我们的图中，LRU和Random指的是驱逐策略，而TLRU和TRandom分别指的是增强了TinyLFU的LRU和Random缓存。对于LFU缓存驱逐，我们测试了两个选项：使用准确的滑动窗口实现的LFU驱逐策略和LFU入场策略的WLFU。TLFU是我们为增强了TinyLFU的LFU缓存命名的。此外，ARC代表ARC，LIRS代表LIRS，而W-TinyLFU代表W-TinyLFU方案（1% LRU窗口缓存和99%主缓存使用TinyLFU入场策略以及SLRU驱逐策略管理）。在我们探索W-TinyLFU的不同窗口缓存大小的图表中，窗口大小写在括号中，例如，W-TinyLFU(20%)代表一个占总缓存大小20%的窗口缓存。

5.2 使用TinyLFU增强缓存的结果

  • F6

F6

图6显示了在常数偏斜分布下TinyLFU入场策略对几种上述驱逐策略性能的影响。如图所示，在常数分布下，所有增强了TinyLFU的缓存行为都相似。令人惊讶的是，LFU缓存驱逐仅比TinyLFU增强的LRU和Random技术带来了微小的好处。我们注意到，在这种偏斜分布中，无论其大小如何，最大的缓存命中率在理论上都是有限的。直观地说，对于分布函数fi，这个边界可以通过对max(0, fi − 1)（因为第一次出现总是一个未命中）进行积分除以对fi的积分来大致计算。

我们得出结论，对于常数偏斜分布，TinyLFU缓存入场策略是一种有吸引力的增强。尽管增强内存中的LFU会带来稍微更高的命中率，但内存中的LFU的开销可能会证明使用更简单的缓存驱逐策略是合理的。特别是，LRU甚至Random提供了低开销和可比较的命中率。

我们进行的第二个实验是在动态分布上测试增强的缓存。为此，我们使用了一个描述从2008年4月16日开始的21周内161K新创建的YouTube视频的流行度的数据集[12]。我们每周评估每个视频的近似频率，并创建代表每周的分布。因此，我们的实验在这些分布之间交换每给定数量的请求。

我们测量了两个指标：第一个是我们可以多快地改变分布，即我们从每周分布中执行的样本数对TinyLFU增强的缓存的命中率的影响是什么。第二个是缓存大小在分布改变速度由跟踪确定时所达到的命中率的影响。

这个实验的结果显示在图7中。可以看到，TinyLFU有效地增强了任意缓存，即使在动态工作负载中也是如此。进一步地，当分布变化更慢时，这种好处更大，这是所有LFU缓存所预期的。然而，在这个工作负载中，增强的Random缓存和增强的LRU缓存与真正的LFU缓存之间的差异更为显著。因此，在动态工作负载中选择正确的缓存受害者似乎比在静态工作负载中更重要。

我们进行的第三项测量是在Wikipedia访问跟踪上运行实验。我们首先研究了跟踪中不同点的连续100百万请求上的样本大小和缓存大小之间所需的比率。其次，我们使用找到的最佳比率，并在不同的缓存大小上进行测试。这些结果显示在图8中。与静态工作负载不同，真实的工作负载随着时间逐渐改变。因此，使用非常大的样本甚至可能降低获得的命中率，因为它减慢了缓存调整到工作负载的速度。

我们注意到，尽管WLFU和TLFU实现了几乎相同的命中率，但WLFU和TLFU之间的主要区别在于它们的元数据成本。例如，在我们使用的YouTube工作负载中，每个样本元素只使用了0.57字节。由于TinyLFU的统计信息维护了一个比缓存大小大9倍的样本，TinyLFU的总元数据成本是9 * 0.57 = 5.

13字节每个缓存条目。如果我们考虑每个缓存条目应该包含一个视频ID，需要11字节，我们得出TinyLFU能够用比仅存储所有缓存项目的键所需的空间开销少地记住一个大9倍的历史。

为了比较，WLFU 需要记住一个比缓存内容大9倍的显式历史。即使在最空间高效的实现中，维护这个历史预计每个缓存条目的成本是99字节。

此外，为了快速操作，需要维护这些项的显式摘要，因为在窗口上迭代并计算缓存项和替换候选项的频率非常慢。

即使我们忽略这些额外的内存开销，WLFU的入场策略仍然需要几乎比TinyLFU多20倍的空间。

5.3 Caffeine实验

5.3.1 比较分析

数据库 图9和图10展示了TLRU和W-TinyLFU相对于Glimpse [36]和DS1 [44]跟踪上的最先进方案ARC和LIRS的命中率。在两个跟踪中，TLRU和W-TinyLFU都提供了非常好的结果。在Glimpse跟踪中，它们与LIRS相当；而在DS1跟踪中，TLRU和W-TinyLFU都优于所有其他策略。这表明TinyLFU方法是各种类型数据库的可行选项。

Windows文件系统 图11和图12显示了windows工作站跟踪P8和P12 [44]的结果。在这些跟踪中，我们评估了W-TinyLFU，分别使用1%窗口缓存和20%窗口缓存。如图所示，两者都实现了非常有吸引力的命中率，并在所有但最大的数据点上优于其他策略。在图12中，20%窗口缓存和1%窗口缓存的图形相互交叉两次。这表明能够自适应改变窗口缓存大小可能有潜在的好处。

OLTP系统中的磁盘访问 在图13中显示的OLTP跟踪中，由于在5.1节中报告的跟踪的特殊性，TinyLFU的表现很差。也就是说，顺序块访问的逐渐列表，其中散布有由于偶尔的写回放或内存缓存未命中的几次随机访问。因此，TLRU比其他任何策略都差。图14和图15显示了两个来自运行金融应用程序的服务器的其他OLTP跟踪的结果[1]，暴露了类似的现象，但强度较低。也就是说，在这两个最后的图中，所有方案之间的差异都小得多。

可以看出，在所有OLTP跟踪中，W-TinyLFU的性能与最先进的技术相当。W-TinyLFU在所有三个跟踪中都优于LRU和LIRS。与ARC相比，W-TinyLFU在OLTP和F2跟踪中略好，而在F1跟踪中，它只在较小的缓存大小中优于ARC，它们之间的差异微不足道。

我们在此只展示W-TinyLFU(20%)，因为在这些跟踪上，它稍微优于W-TinyLFU(1%)，这样做可以减少图中的干扰。5.3.2节下面探讨了W-TinyLFU中窗口缓存大小对命中率的影响，其中显示OLTP跟踪需要20%的窗口缓存以获得最佳结果。不幸的是，增加窗口缓存大小会降低W-TinyLFU在其他跟踪上的性能。因此，在Caffeine的当前版本(2.0)的默认配置中，窗口缓存大小被固定为总缓存大小的1%，以避免为用户带来额外的配置参数负担。

SPC1-like 图16显示了我们在从[44]中获取的SPC1-like跟踪上的结果。可以观察到，TLRU和W-TinyLFU在那个跟踪上也优于所有其他策略。

搜索引擎查询 图17、图18、图19和图20展示了W-TinyLFU和TLRU在各种搜索引擎跟踪上的行为，这些跟踪来自[44, 1]。可以观察到，对于ARC和LIRS，ARC在小缓存中似乎更好，而LIRS在大缓存中更好。然而，TLRU和W-TinyLFU在整个过程中都优于它们。

5.3.2 调整W-TinyLFU中的窗口缓存大小

如上所述，对于大多数跟踪，窗口缓存大小为总缓存的1%的W-TinyLFU优于（或与）所有其他方案相当。相反，在OLTP、F1和F2中，TinyLFU通常表现不佳，而1%的窗口缓存大小提高了命中率，但仍不是最佳表现者。在这些跟踪中，需要更大的窗口缓存。图21探索了在这三个跟踪：OLTP、F1和F2下，窗口缓存与主缓存之间的缓存分配对W-TinyLFU命中率的影响。对于OLTP，我们测试了1,000项的总缓存大小，而对于F1和F2，总缓存大小为2,500项。如图所示，20%到40%的窗口缓存大小在这些跟踪上表现得最好。

5.4 不准确性的来源

TinyLFU中最明显的不准确性来源是由假阳性引入的近似精度。然而，也存在由于在复位操作中执行整数除法而非实数（浮点数）除法导致的截断误差。对于静态分布，也可以测量采样误差，即TinyLFU能够多好地理解基础分布。所有这些因素共同可以解释TinyLFU的（不）准确性。

我们定义采样误差为具有浮点计数器的准确TinyLFU与在常数分布下可实现的理想命中率之间的差异。通过使用更大的样本大小，可以降低静态分布的采样误差。

接下来，截断误差是准确TinyLFU（无门卫和无假阳性）与浮点计数器之间的命中率之间的变化。这两种实现之间唯一的区别是在复位操作中执行的除法类型。通过允许计数器具有更高的计数（每个计数器更多的比特），可以降低截断误差。

最后，近似误差是我们通过使用TinyLFU的近似版本（如本文所述）而非准确版本获得的命中率差异。这意味着使用计数Bloom过滤器而不是哈希表。命中率的差异是由可能扭曲采样并使不频繁的项目看似频繁的假阳性引起的。

静态Zipf 0.9分布的结果显示在图22中。如图所示，直到每个样本项约1.25字节，近似误差根本不出现。也就是说，TinyLFU的近似版本提供了与准确版本相同的命中率。如预期的，对于小样本大小，截断误差较小，因此在9k项样本中，它比在17k项样本中更为主导。在17k样本中，截断误差几乎可以忽略不计。

采样误差是最棘手的，因为增加样本大小只有对于静态分布有所帮助。采样误差随着设置的样本大小的增加而减小。这种行为显然不适用于实际工作负载，其中样本大小应根据经验试错过程选择。

还要记住，实现在Caffeine中的TinyLFU使用CM-Sketch而不是计数Bloom过滤器。在其默认配置中，它为每个缓存条目分配8字节，并维护一个是缓存大小10倍的样本大小。换句话说，它使用0.8字节每个元素。通过将分配的空间加倍到每个条目16字节，获得的命中率增加了大约0.5%。换句话说，Caffeine的当前配置大约带有0.5%的近似误差。

6 结论

我们介绍了TinyLFU，这是一种基于近似频率的缓存准入策略。我们展示了TinyLFU可以增强任意驱逐策略的缓存，并显著提高其性能。我们还使用已知的近似计数技术的适应性，结合特定的新技术，以实现缓存的低内存占用，优化了TinyLFU的内存消耗。

与之前将幽灵缓存条目合并到驱逐策略考虑因素中的方案不同，在TinyLFU中，准入策略与驱逐策略是正交的。这种解耦遵循了关注点分离原则，简化了设计和实现，并允许独立优化每一个。

特别是，使用近似草图技术作为准入策略可以在只消耗少量元数据的同时，维护一个相对大的样本的统计数据。

TinyLFU及其变体W-TinyLFU的性能已通过使用合成跟踪以及来自多个不同来源的多个真实世界跟踪的模拟进行了探索和验证。如前所述，TinyLFU作为Caffeine Java缓存项目的一部分在开源中免费提供[43]。展望未来，我们将考虑基于简洁哈希表设计[22, 21]的改进实现。

拓展阅读

淘汰算法，除了 FIFO/LRU/LFU/tinyLFU 还有其他算法吗？

当然，除了常见的FIFO（先进先出）、LRU（最近最少使用）、LFU（最少使用）、TinyLFU外，还有其他一些淘汰算法和策略。以下是一些其他常用的淘汰算法：

  1. MRU（最近最多使用）：与LRU相反，MRU算法会选择最近使用的项目进行淘汰。

  2. Random（随机）：这种算法随机选择一个缓存条目进行淘汰，不考虑该条目的访问频率或时间。

  3. Clock（时钟）：这是一种改进的FIFO算法，使用一个“时钟”指针来维护项目的访问状态。当需要淘汰项目时，它会检查指针指向的项目，如果该项目的访问位是0，则选择淘汰它；如果访问位是1，则将其重置为0并继续检查下一个项目，直到找到一个可淘汰的项目。

  4. 2Q（双队列）：这种算法使用两个队列来维护缓存，一个是LFU队列，另一个是LRU队列。新访问的项目首先进入LRU队列，然后根据其访问频率从LRU队列移动到LFU队列。这种方法结合了LFU和LRU的优点。

  5. ARC（自适应替换缓存）：ARC算法结合了LRU和LFU的特性，通过动态调整LRU和LFU的大小，以适应访问模式的变化。

  6. LIRS（最低最近使用）：LIRS算法是LIRS缓存算法的扩展，它尝试维护两种LRU链表，一种是最近最少使用的（LIR），另一种是最长非最近使用的（HIR）。这种方法试图减少LRU算法的缺点。

这些算法各有优点和缺点，适合不同的应用和工作负载。选择哪种算法取决于具体的应用需求和性能目标。

参考资料

https://arxiv.org/pdf/1512.00727.pdf