CacheLib 缓存引擎¶

标题：The CacheLib Caching Engine: Design and Experiences at Scale

日期：2020/11/04

作者：Benjamin Berg, Carnegie Mellon University; Daniel S. Berger, Carnegie Mellon University and Microsoft Research; Sara McAllister and Isaac Grosof, Carnegie Mellon University; Sathya Gunasekar, Jimmy Lu, Michael Uhlar, and Jim Carrig, Facebook; Nathan Beckmann, Mor Harchol-Balter, and Gregory R. Ganger, Carnegie Mellon University

链接：https://www.usenix.org/system/files/osdi20-berg.pdf

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

备注：通用还是专用的讨论。我看到 GitHub 还在更新，就顺便把多年前的文章翻译了。

摘要¶

Web服务在系统架构的几乎每一层都依赖于缓存。通常，每个缓存都由不同的团队独立实现和维护，并高度专用于其功能。例如，应用数据缓存与CDN缓存是独立的。然而，这种方法忽视了不同缓存系统共有的难题，大大增加了部署、维护和扩展每个缓存所需的总工作量。

本文提出了一种不同的缓存开发方法，已在Facebook成功应用，该方法从原本不相交的缓存系统中提取出一组共同的核心需求和功能。_CacheLib_是一个通用缓存引擎，基于Facebook一系列缓存用例的经验设计而成，它简化了缓存的开发和维护。CacheLib于2017年首次在Facebook部署，如今为超过70个服务提供支持，包括CDN、存储和应用数据缓存。

本文描述了我们从独立的专用缓存过渡到广泛采用CacheLib的经验。我们解释了Facebook生产工作负载和用例的特性如何驱动重要的设计决策。我们描述了Facebook的缓存如何随时间演变，包括部署CacheLib带来的显著好处。我们还讨论了我们的经验对未来缓存设计和研究的影响。

1. 引言¶

大型Web服务依赖缓存系统来实现高性能和高效率。例如，在Facebook，CDN缓存处理了70%的Web请求，将延迟降低了一个数量级。单个缓存服务器通过实现20倍更高的吞吐量和超过80%的命中率，可以替代数十个后端数据库服务器。

在Facebook，各种各样的缓存系统构成了系统架构不可或缺的一部分。Facebook的架构包括CDN缓存、键值应用缓存、社交图谱缓存和媒体缓存（图1）。缓存也在Amazon [26]、Twitter [42, 92]、Reddit [33, 89] 和许多其他大型Web服务中扮演着类似的角色。

Facebook的缓存系统。 历史上，Facebook的每个缓存系统都是单独实现的。例如，Facebook分别设计了CDN缓存 [86]、键值缓存 [72]、社交图谱缓存 [17]、存储缓存 [71]、数据库缓存 [2] 以及许多其他缓存。当时的信念是，每个高度专业化的系统都需要一个高度专业化的缓存，以实现复杂的一致性协议、利用自定义数据结构，并针对所需的硬件平台进行优化。

尽管这些缓存系统服务于不同的工作负载并需要不同的功能，但它们共享许多重要的工程和部署挑战（第2节）。所有这些系统每秒处理数百万次查询，缓存的工作集大到需要同时使用闪存和DRAM进行缓存，并且必须容忍由于应用程序更新而频繁重启，这在Facebook生产环境中很常见。随着Facebook缓存系统数量的增加，为每个系统维护独立的缓存实现变得不可持续。通过重复解决相同的艰难工程挑战，团队重复了彼此的努力并产生了冗余代码。此外，维护独立的缓存系统阻碍了性能优化带来的效率提升在系统间的共享。

因此，Facebook面临着通用性与专用性之间的权衡。一个更通用的缓存解决方案可能会失去针对个别系统的某些领域特定优化，但它可以减少开发开销并增加系统间的协同效率。平衡这种权衡的愿望催生了CacheLib，这个通用缓存引擎。

本文描述了Facebook的可扩展缓存部署解决方案：CacheLib。CacheLib是一个C++库，提供缓存功能的公共核心，包括缓存索引的高效实现、淘汰策略以及对DRAM和闪存缓存的稳定性优化。CacheLib通过一个简单的、线程安全的API暴露其功能，允许程序员轻松构建和定制可扩展的、高并发的缓存。CacheLib既用于构建独立的缓存系统，也用于向应用程序添加进程内缓存。Facebook的CDN、社交图谱缓存、应用旁路缓存和块存储系统都使用基于CacheLib构建和定制的缓存。

CacheLib自2017年以来已在生产环境中部署，如今为70多个不同的服务提供支持。图2显示了在此期间CacheLib的增长情况。最初，CacheLib取代了现有的缓存，但自2018年年中以来，它促进了整个Facebook缓存的爆炸性增长，显著减少了后端负载。

从CacheLib学到的经验教训¶

开发一个有效的通用缓存框架不仅需要理解Facebook内部常见的缓存用例，还需要理解缓存未来部署方式的更普遍趋势。本节描述了缓存方面的传统智慧与我们在Facebook生产环境中的经验不符的实例。

专用的缓存系统可以并且应该使用通用缓存引擎来构建。 在Facebook，CacheLib已经在几个主要服务中取代了现有的专用缓存，并刺激了许多新应用中缓存的采用。CacheLib提供了比任何单个专用缓存系统更广泛的功能集。拥有一个共同的功能核心节省了数万行冗余代码，提高了系统稳定性，并使开发人员能够轻松部署和调整新缓存。此外，CacheLib作为优化和最佳实践的聚合点。因此，基于CacheLib构建的系统在单个生产服务器上实现了每秒百万次请求的峰值吞吐量，命中率在60%到90%之间。为了实现这种性能，每个缓存系统都定制其缓存以使用他们所需的CacheLib功能子集。为了适应尽可能多的系统，CacheLib的功能集随着时间的推移而增长。因此，曾经证明构建专用缓存系统合理的功能现在可供任何基于CacheLib的系统使用。

生产工作负载需要大规模缓存。 先前对生产系统的工作负载研究 [4, 5] 没有共享键的流行度分布。因此，流行的基准测试工具 [24, 59] 和学术论文 [19, 36, 41, 49, 53, 65, 66, 68, 74, 90, 94] 假设形状参数 (\alpha\approx.9) 的Zipf流行度模型。这导致得出结论：基于DRAM的缓存在大多数情况下是足够的。我们提供了强有力的证据，表明先前的模型对生产工作负载的可缓存性过于乐观。

由于Facebook的工作负载比通常假设的可缓存性差，Facebook的缓存需要巨大的容量才能达到可接受的命中率。Facebook的缓存系统通常包含大型分布式系统，其中每个节点具有数百GB的缓存容量。这使得使用闪存进行缓存具有吸引力。然而，大多数缓存系统历史上针对DRAM，使用闪存无法达到可接受的性能。

缓存不是一个已解决的问题。 自2017年首次部署以来，随着新用例和功能需求的显现，CacheLib不断增加功能。这些新功能得到了现有CacheLib用户和使用CacheLib开发的新系统的迅速、广泛采用，因此CacheLib功能的公共核心随着时间的推移与应用程序一起增长。

弥合研究与生产缓存系统之间的差距¶

正如Facebook的开发人员历史上开发了专用的缓存系统一样，我们注意到缓存文献也常常针对专用的缓存系统。这给工业界采纳研究界的想法设置了障碍，因为专用研究系统所做的假设很少与生产环境的现实完全吻合。我们希望CacheLib可以通过提供一个平台来探索在Facebook外部开发的新想法，从而减少这些障碍。CacheLib和一部分Facebook工作负载将被开源¹。

脚注1：更多信息，请访问 www.cachelib.org

2. 动机：缓存用例¶

大型Web服务依赖数百个专门的服务，这些服务包含多样化的缓存用例。本节描述了Facebook六个生产系统样本的缓存需求。

分层和地理分布的缓存。 Facebook的CDN专注于从靠近用户的服务器提供静态媒体对象（如照片、音频和视频块）的HTTP请求。具体来说，部署在Facebook网络之外的CDN服务器的目标是减少通过广域网发送的字节数（字节缺失率）。Facebook数据中心内部也有CDN服务器；它们的目标是减少后端和存储查询的数量（对象缺失率）。每个CDN服务器使用一个本地缓存，跨越DRAM和闪存。

应用旁路缓存。 Web应用程序有广泛的缓存需求。例如，应用程序必须缓存数据库查询、用户数据和使用统计信息。为每个应用程序提供专门的缓存服务效率低下且难以维护。因此，应用程序使用RPC访问一组共享的缓存服务。每个缓存服务由一个大型的分布式缓存系统组成。

进程内缓存。 许多应用程序无法容忍远程缓存的RPC开销。CacheLib使这些应用程序能够轻松地包含与应用程序逻辑解耦的高性能进程内缓存。

例如，一些后端应用程序使用CacheLib缓存来存储用于对客户端进行速率限制的客户端会话信息。具体来说，这些应用程序缓存流量计数器，这些计数器会看到非常高的请求速率突发，但一旦流量减慢就可以被驱逐。在这种情况下，缓存的延迟和带宽要求使得远程缓存不可行。相反，应用程序实例化一个CacheLib缓存，它提供对缓存流量计数器的零拷贝访问。

机器学习模型服务系统。 面向用户的机器学习应用程序在多个地方受益于缓存。首先，模型通常使用基于用户如何与内容交互（例如，喜欢某条内容）的输入。因此，内容交互计数器被缓存，以便应用程序可以快速访问生成预测（例如，对内容进行排名）所需的输入。其次，因为基于相同输入重复生成预测在计算上是昂贵的，所以模型预测也被缓存。

存储后端缓存。 Facebook使用带有旋转磁盘的大型服务器集群来存储持久数据块。即使在块存储服务器前面有几个缓存层，有些块仍然足够流行，以至于超出了磁盘的目标IOPS。存储服务器使用闪存驱动器来缓存流行的块，并保护旋转磁盘免受负载影响。为了支持字节范围请求和追加操作，这些闪存缓存紧密集成在存储系统堆栈中。

数据库页缓冲区。 数据结构和小对象存储在各种数据库系统中。数据库系统使用页缓存来提高吞吐量和减少访问延迟。为了支持一致性和事务操作，页缓存与数据库逻辑紧密集成。

在整个Facebook，我们发现数百种不同的服务实现了缓存，或者其效率可以从缓存层中受益。这些用例跨越数据中心堆栈的所有层和管理域。关于缓存的研究涉及操作系统 [16, 52]、存储系统 [20, 58]、分布式系统 [8, 22, 66]、网络系统 [9, 65]、数据库 [30] 和计算机体系结构 [7, 56, 91]。

CacheLib通过提供一个组件_库_来处理这些多样化的用例，该库使得快速构建高性能缓存变得容易。在许多情况下，CacheLib缓存已经取代了Facebook高度专业化的缓存系统。CacheLib目前用于数十个生产系统，涵盖了上述六个例子中的五个。值得注意的是，CacheLib目前不用作数据库页缓冲区（见第6节）。因此，虽然CacheLib不会取代每一个专用的缓存系统，但我们已经看到了通用缓存引擎在Facebook的显著采用。

3. Facebook缓存系统面临的共同挑战¶

尽管缓存用例多种多样，但我们扩展和维护缓存系统的经验揭示了一组核心挑战，这些挑战经常在用例之间重叠。本节描述了Facebook的共同挑战。

本节中的数据是在2019年12月至2020年5月期间从各种缓存用例（第2节）的4个重要工作负载收集的。_Lookaside_和_SocialGraph_系统都来自应用数据缓存。_Lookaside_是一个为各种应用程序提供按需缓存的服务。_SocialGraph_专门用于缓存来自Facebook社交图谱的信息。_Storage_系统是一个存储后端缓存，_CDN_是Facebook CDN中的一个缓存。每个工作负载代表其各自服务中一台机器的流量。

巨大的工作集¶

Facebook的一个核心挑战是巨大的_工作集_。工作集描述了工作负载中足够流行以至于能从缓存中受益的对象集合。具有较大工作集的工作负载需要更大的缓存才能产生与较小工作集工作负载相同的命中率。

要测量工作集，必须考虑随时间看到的流行数据量以及数据流行度随时间的变化率。因此，我们同时呈现了Facebook的流行度分布和流失率。

流行度。 工作负载的流行度分布测量了采样跟踪中某个时间范围内每个键的频率。这些频率表示系统中不同对象的相对流行度。先前对CDN和Web工作负载的测量表明，高度偏斜的Zipf分布是一种常见的流行度分布 [5, 14, 24, 38, 41, 48, 83, 85]。非正式地说，在Zipf分布中，“最流行的20%的对象占请求的80%”。正式地说，在Zipf分布中，第(i)个最流行的对象具有(1/i^{\alpha})的相对频率。虽然一些研究表明(\alpha)低至0.56 [38, 40]，但大多数先前的测量表明(0.9<\alpha\leq 1)[5, 14, 24, 41, 48, 85]。这个参数范围已成为许多近期系统论文 [19, 36, 41, 49, 53, 65, 66, 68, 74, 90, 94] 的标准评估假设。

图3以对数-对数尺度显示了Facebook四个工作负载的流行度分布。在这个尺度上，Zipf分布将是一条斜率为负（(-\alpha)）的直线。Lookaside是四个系统中唯一流行度分布是Zipfian且(\alpha)接近1的系统。Storage的分布在头部要平坦得多，尽管尾部遵循Zipf分布。此外，虽然SocialGraph和CDN的分布是Zipfian，但分别表现出(\alpha=0.55)和(\alpha=0.7)。较低的(\alpha)意味着显著更高比例的请求流向流行度分布的尾部，这导致更大的工作集。

流失 (Churn)。_流失_指的是由于新键的引入和现有键的流行度随时间变化而导致的工作集变化。流行的YCSB [24] 工作负载生成器假设没有流失，即每个键在整个基准测试期间保持同等流行。这个基准测试和无流失假设广泛用于系统论文的评估 [19, 36, 49, 53, 65, 66, 68, 74, 90, 94]。

在Facebook的生产工作负载中，我们发现了高度的流失。我们将一个对象定义为_流行的_，如果它属于接收最多请求的前10%的对象。图4显示了流行对象集合随时间的变化情况。例如，(x=3)处的蓝色条表示3小时前流行的对象仍然处于前10%最常请求对象的概率。在所有工作负载中，给定小时内超过三分之二的流行对象在仅仅一小时后就不再处于前10%。如此高的流失率适用于我们用作基线的任何小时、不同的百分位数（例如，前25%）以及不同的时间粒度（例如，10分钟后，50%的流行对象不再流行）。这种高流失率增加了时间局部性的重要性，并使缓存策略更难基于过去的访问模式来估计对象流行度。

大小可变性¶

除了流行度和流失之外，对象大小在缓存性能中也起着关键作用。图5显示了四个大型用例的对象大小分布。对于Storage和CDN，我们发现64KB和128KB的块非常常见，这是将大对象分割成块的结果。对于Lookaside和SocialGraph，我们发现对象大小跨越了七个数量级以上。注意小对象的优势，它们来自图边/节点、RPC计算结果和负缓存（见第4.3节）。

这些发现限制了一个通用缓存系统的设计空间。例如，许多现有的缓存系统 [3, 32, 35, 37, 70, 75, 79, 87] 每个缓存行（64B）最多存储一个对象。对于像SocialGraph这样的系统，其中很大一部分对象在10B到20B之间，这种方法浪费空间。另一个挑战是用作闪存上对象索引的内存数据结构。现有系统的每个对象开销在8B到100B之间不等 [32, 37, 70, 79, 86, 87]。对于一个中位对象大小为100B的系统，例如Lookaside，这意味着需要80GB - 1TB的DRAM来索引1TB闪存驱动器上的对象。必须在限制内存和存储开销的同时处理高度可变的对象大小，这是至关重要的。

突发流量¶

另一个共同主题是Facebook的流量非常突发。图6显示了实际请求到达率与泊松到达序列的比较，后者常在系统评估中被假设 [53, 66, 73, 74, 84]。图6显示实际到达率的变化比泊松分布所暗示的要大得多。

这对于CDN尤其明显，它在相当稳定的请求速率之上有急剧的流量突发。可变的到达率使得很难为缓存系统配置足够的资源以在负载峰值期间维持低延迟。

资源管理¶

为了提高效率，缓存应该利用所有可用资源而不超出它们。这对于DRAM尤其重要。一个常见的部署场景包括CacheLib以及应用程序进程和内核，它们都消耗DRAM。随着工作负载组成或强度的变化，可用于缓存的内存可能会有很大差异。例如，处理可变大小对象的缓存通常具有不可预测的内存使用水平。因此，尝试将所有可用内存用于缓存可能导致内存过度使用，这是进程内缓存 [78] 的一个众所周知的挑战。具体来说，应用程序中的内存峰值可能导致缓存由于内核的内存不足（OOM）杀手而被丢弃。许多开源缓存系统没有OOM意识 [87]，导致重大的运营挑战 [77]。CacheLib动态分配和释放缓存使用的内存，以避免这些崩溃，同时不留太多未使用的内存。

计算成本高昂的空结果查询¶

缓存系统通常专注于跟踪和存储有效后端查询的结果。然而，一些用例经常发送具有空结果的查询，表明请求的对象不存在。这经常发生在跟踪用户之间关联的数据库系统中，用户可能会查询他们与另一个用户共同的熟人集合。这类查询通常对后端数据库计算成本高昂。例如，当查询社交图谱时，用户经常要求查看他们与另一个用户共享的关联集合，却发现这些关联不存在。因此，在SocialGraph的工作负载中，我们测量到55.6%的请求是针对不存在的键。其余44.4%的请求是请求有效对象，这些请求中的相应缓存命中率为86.5%。未能缓存空结果会显著降低缓存命中率。

更新缓存的数据结构¶

缓存应该有效地支持结构化数据。这对于直接与应用程序数据结构交互的进程内缓存尤其重要。例如，第2节中描述的速率限制器在单个缓存对象中存储多个字段。应用程序通常希望能够更新缓存数据结构中的特定字段，而无需反序列化、更新和重新序列化对象。

频繁重启¶

最后，生产缓存为了获取代码修复和更新而频繁重启。这是因为工程团队不仅需要能够快速推出新代码，还需要能够快速回滚更改。例如，75%的_Lookaside_缓存和95%的_CDN_缓存正常运行时间少于7天。即使是像_Storage_和_SocialGraph_这样平均正常运行时间较长的系统，也遵循定期的每月维护计划，这需要重启缓存进程。大多数缓存系统是瞬态的，意味着它们的内容在应用程序重启时会丢失 [37, 55]。瞬态性是有问题的，因为大型缓存需要很长时间来预热。在Facebook，瞬态缓存重启后，缓存命中率需要数小时甚至数天才能稳定下来。先前的工作建议在重启后预热缓存作为替代方案，但这需要将显式的预热阶段作为路由的一部分 [33, 72] 或需要缓慢的部署 [42]。

总结¶

虽然并非每个缓存用例都表现出上述所有挑战，但每个用例确实表现出多个这些挑战。我们将在第4节接下来描述CacheLib如何解决这些问题。使用通用缓存引擎来解决这些挑战的优势在于，所有使用CacheLib的应用程序都可以在需要时访问每一个CacheLib功能。

4. 设计与实现¶

CacheLib支持为广泛的用例构建快速、稳定的缓存。为了解决第2节和第3节描述的这些用例中的共同挑战，我们确定了以下功能作为通用缓存引擎的必要需求。

线程安全的缓存原语： 为了简化处理高突发流量应用程序的编程，CacheLib为读取、写入和删除提供了线程安全的API。此外，线程安全性简化了一致性和失效协议的实现。对CacheLib API的并发调用会使缓存处于有效状态，如果引用公共键则尊重线性一致性 [47]，并且产生最小的资源争用。

透明的混合缓存： 为了在缓存大工作集的同时实现高命中率，CacheLib支持由DRAM和闪存组成的缓存，称为_混合缓存_。混合缓存支持每个节点具有TB级缓存容量的大规模缓存部署。CacheLib通过提供相同的字节可寻址接口（第4.1节）向应用程序程序员隐藏了闪存缓存系统的复杂性，而与底层存储介质无关。这种透明性允许应用程序程序员忽略对象在不同存储介质间写入的时间和地点。它还增加了缓存应用程序的可移植性，允许应用程序在可用的新硬件配置上轻松运行。

低资源开销： CacheLib为广泛的工作负载（第2节）实现了高吞吐量和低内存及CPU使用率。这使得CacheLib适用于缓存必须与应用程序共享资源的进程内用例。低资源开销允许CacheLib支持具有许多小对象的用例。

结构化项 (Structured items)： CacheLib原生实现了数组和哈希映射，可以高效地缓存和变更，而不会产生任何序列化开销。缓存结构化数据使程序员能够轻松地将缓存与应用程序逻辑高效集成。

动态资源监控、分配和OOM保护： 为了防止系统内存使用临时激增导致的崩溃，CacheLib监控总系统内存使用情况。CacheLib动态分配和释放缓存使用的内存，以控制系统总内存使用量。

热重启 (Warm restarts)： 为了无缝处理代码更新，CacheLib可以执行保留缓存状态的_热重启_。这克服了每次重启都需要预热缓存的需求。

CacheLib API¶

CacheLib API的设计足够简单，允许应用程序程序员快速构建进程内缓存层，几乎不需要缓存调整和配置。同时，CacheLib必须能够扩展以支持复杂的应用级一致性协议，以及为高性能提供对数据的零拷贝访问。选择一个既简单又强大的API是CacheLib设计中的一个重要关注点。

API围绕Item的概念展开，Item是缓存对象的抽象表示。Item支持对底层对象的字节可寻址访问，无论对象存储在DRAM还是闪存上。对缓存Item的访问通过ItemHandle控制，它支持缓存Item的引用计数。当ItemHandle对象被构造或销毁时，相应Item的引用计数器分别递增或递减。除非其引用计数为0，否则Item不能被逐出缓存。如果具有非零引用计数的Item过期或被删除，现有的ItemHandle将保持有效，但不会为该Item发出新的ItemHandle。

图7显示了基本的CacheLib API。要将新对象插入缓存，allocate可能首先驱逐另一个Item（根据淘汰策略），只要没有引用它的未完成的ItemHandle。新的Item可以配置过期时间（TTL）。它在给定的内存“池”（见下文）中创建，每个池可以单独配置以提供强隔离保证。任何新Item只有在相应的ItemHandle上完成insertOrReplace操作后才变得可见。

要访问缓存的Item，find从一个键创建一个ItemHandle，之后getMemory允许对与Item关联的内存进行非同步、零拷贝访问。要原子地更新一个Item，需要为他们希望更新的键分配一个新的ItemHandle，使用getMemory执行更新，然后通过调用带有新ItemHandle的insertOrReplace使更新可见。因为CacheLib客户端为了性能而访问原始内存，CacheLib信任用户使用markNvmUnclean方法忠实地指示任何变更。最后，remove删除由键标识的Item，表示底层对象的失效或删除。

图8显示了CacheLib对结构化数据的原生支持的一个简单示例。结构化Item通过TypedHandle访问，它提供与ItemHandle相同的方法。TypedHandle支持对用户定义数据结构的低开销访问，这些数据结构可以像普通Item一样被缓存和驱逐。除了静态大小的数据结构，CacheLib还支持可变大小的数据结构；例如，CacheLib实现了一个支持范围查询的简单哈希映射、数组和可迭代缓冲区。

CacheLib在C++中实现了这些API，并绑定到其他语言，如Rust。

架构概述¶

CacheLib被设计成具有足够的可扩展性，以适应具有高度可变大小（第3.2节）的巨大工作集（第3.1节）。为了实现低的每个对象开销，单个CacheLib缓存由几个子系统组成，每个子系统都针对特定的存储介质和对象大小进行了定制。具体来说，CacheLib包含一个DRAM缓存和一个闪存缓存。闪存缓存由两个缓存组成：用于大小>2KB的Item的大对象缓存（LOC）和用于大小<2KB的Item的小对象缓存（SOC）。

allocate请求通过在DRAM中分配空间来满足，必要时从DRAM驱逐Item。被驱逐的Item要么被接纳到闪存缓存（可能导致另一次驱逐），要么被丢弃。find请求依次在DRAM、然后LOC、然后SOC中检查对象。这种查找顺序最小化了缓存的平均内存访问时间 [46]（见附录A）。find调用立即返回一个ItemHandle。如果请求的对象位于DRAM上，则此ItemHandle立即可用。如果请求的对象位于闪存上，则异步获取，一旦对象进入DRAM，ItemHandle就变得可用。返回一个空的ItemHandle表示缓存未命中。这些数据路径总结在图9中。

我们现在更详细地描述CacheLib的子系统。

DRAM缓存。 CacheLib的DRAM缓存使用链式哈希表执行查找。DRAM缓存可以划分为单独的_池_，每个池都有自己的淘汰策略。程序员在调用allocate时（见图7）选择一个特定的PoolId，允许在单个缓存实例内隔离不同类型的流量。

为了性能，缓存内存使用slab类 [6, 22, 37] 进行分配，这些slab类存储相似大小的对象。CacheLib使用4MB的slab并实现了自定义的slab分配器。每个slab需要7B的DRAM（3B内部元数据 + 4B用于标识slab中对象的大小）。因为CacheLib工作负载通常包括许多特定大小的对象（例如80B），所以每个slab类对应的大小是根据每个工作负载配置的，以最小化碎片。针对小于64B或大于4MB的对象的进一步优化在第4.3节中描述。

每个slab类维护自己的淘汰策略状态。CacheLib旨在支持新淘汰策略的持续开发，目前支持LRU、具有多个插入点的LRU、2Q [54, 93] 和TinyLFU [31]。这些淘汰策略在开销以及对近期性或频率的偏向上有所不同，因此也根据每个工作负载进行配置。为了近似全局淘汰策略，使用已知的重新平衡算法 [72] 在slab类之间重新平衡内存。为了支持这些策略以及其他功能，CacheLib为每个Item dedicates 31B的DRAM开销。表1描述了构成此DRAM开销的元数据。

为了保证原子元数据操作，CacheLib依赖于各种已知的优化技术 [35, 62, 64]，包括细粒度锁、用户空间互斥锁和C++原子操作。这对于淘汰策略尤其重要，因为幼稚的实现会导致锁争用并限制吞吐量 [6, 9, 10, 61]。例如，在LRU下，流行的Item经常竞争被重置到最近使用（MRU）的位置。由于我们的高请求速率（见图6），这在Facebook尤其常见。CacheLib采用一个简单的解决方案来减少争用：最近被重置到MRU位置的Item在一段时间(T)内不会被再次重置 [9, 87]。只要(T)比对象在LRU列表中渗透的时间（即驱逐年龄）短得多，这种简化在实践中不会影响命中率。CacheLib还使用高级锁定机制，如flat combining [45]，以减少资源争用。

闪存缓存。 当Item从DRAM缓存驱逐时，可以选择性地写入闪存缓存。由于高流行度流失（第3节），闪存上缓存的内容不断变化。因此，除了维持低的每个对象开销外，CacheLib还必须应对闪存单元有限的写入耐久性。

为了减少对闪存的写入速率，CacheLib选择性地将对象写入闪存缓存。如果一个对象存在于闪存上并且在DRAM中未被更改，则不会将其写回闪存。否则，CacheLib根据可配置的接纳策略将对象接纳到闪存。CacheLib的默认接纳策略是以固定概率(p)将对象接纳到闪存缓存 [57]。调整概率(p)允许对闪存的写入速率进行细粒度控制。第5节描述了我们对更复杂接纳策略的经验。

闪存耐久性的另一个考虑因素是_写入放大_，当写入设备的字节数大于插入缓存的字节数时就会发生。例如，CacheLib执行额外的写入来存储元数据，并且被迫以块粒度写入。我们区分应用级写入放大（当CacheLib本身写入闪存的字节数大于插入对象的大小时发生）和设备级写入放大（由闪存设备固件引起）。CacheLib的闪存缓存经过精心设计，以平衡这两种写入放大源和DRAM开销。

大对象缓存（LOC）用于在闪存上存储大于2KB的对象。因为LOC对象大于2KB，所以LOC中唯一对象的数量只会达到数百万。因此，在内存中保存LOC的索引是可行的。LOC在DRAM中使用分段B+树 [23, 34, 63] 来存储Item的闪存位置。Item与4KB闪存页对齐，因此闪存位置是一个4B、4KB对齐的地址。这允许LOC索引高达16TB的闪存存储空间。

LOC使用闪存来进一步限制DRAM索引的大小。键被哈希为8B。前4B标识B+树段，后4B用作树段内的键来查找闪存位置。DRAM索引中的哈希冲突将导致CacheLib认为它找到了对象的闪存位置。因此，LOC将每个对象完整键的副本作为对象元数据的一部分存储在闪存上，并在从闪存获取对象后验证键。每个闪存设备被划分为区域，每个区域存储不同大小范围的对象。因此，可以从对象在闪存上的位置推断出对象大小，而无需在DRAM中显式存储对象大小。然后，CacheLib可以通过单次闪存读取检索正确字节数的对象。为了减少存储在DRAM中的地址大小，每个4KB闪存页最多存储一个对象及其元数据。这是空间高效的，因为LOC只存储大于2KB的对象。大于4KB的对象可以跨越多个页。因为LOC在页级别进行读写，任何碎片也会导致应用级写入放大。

为了分摊闪存擦除的计算成本，LOC的缓存策略逐出整个区域而不是单个对象。（区域大小是可配置的，例如16MB。）默认情况下，使用FIFO，以便按严格顺序擦除区域 [60]。顺序写入提高了闪存转换层的性能，并大大降低了设备级写入放大（见第5.2节）。如果FIFO驱逐驱逐了一个流行对象，它可能会被重新接纳到缓存中 [86]。或者，LOC支持一种伪LRU策略，该策略在区域粒度上跟踪近期性。对区域中任何对象的请求在逻辑上将该区域重置到MRU位置。驱逐会擦除LRU位置的整个区域。

小对象缓存（SOC）用于在闪存上存储小于2KB的对象。因为数十亿个小对象可以容纳在单个1TB闪存设备上，所以精确的查找索引（带有相关的每个对象元数据）将使用不合理的大量DRAM [32]。因此，SOC使用一个与闪存页数量成比例的近似索引。

SOC将键哈希到集合 (sets) 中。每个集合标识一个用于存储多个对象的4KB闪存页。对象按FIFO顺序从集合中驱逐。这种设计的简单实现总是从闪存读取集合的页来确定它是否包含特定对象。作为优化，CacheLib在DRAM中为每个集合维护一个8B的布隆过滤器，每个有4个探针。该过滤器包含存储在集合闪存页上的键，并在超过90%的时间内防止不必要的读取 [11, 12]。图10显示了分配路径，图11显示了查找路径。

控制SOC中的写入放大尤其具有挑战性。将一个对象接纳到SOC需要写入整个4KB闪存页，因此是应用级写入放大的一个重要来源。这也适用于remove操作，该操作从闪存中移除对象。类似地，因为键被哈希到集合，将对象流接纳到SOC会导致随机写入，从而导致更高的设备级写入放大。此外，SOC只支持在命中时不需要状态更新的淘汰策略，例如FIFO，因为在命中时更新集合需要4KB的页写入。这些挑战凸显了高级接纳策略的重要性（见第5.2节）。

高级功能的实现¶

CacheLib支持许多要求苛刻的应用程序。为了有效地支持这些应用程序，CacheLib实现了几个高级功能，使它们在同一通用CacheLib API下可供所有基于CacheLib的服务使用。我们描述了四个重要功能的实现：结构化项、缓存大小对象、热重启和资源监控，对应于第3节已经讨论过的挑战。

结构化项。 因为CacheLib提供对缓存内存的原始访问，所以可以使用CacheLib API轻松缓存扁平数据结构。此外，CacheLib原生支持数组和映射。CacheLib支持固定大小对象的Array类型，对数组中的每个条目没有额外开销。Map类型支持可变对象大小，并提供有序和无序变体。每个Map条目的开销是4B用于存储其大小。

在DRAM中缓存大小对象。 为了存储大于4MB大小的对象，CacheLib将多个DRAM Item链接成一个逻辑上的大项。这种链接需要链中每个对象额外增加一个4B的next指针。大对象最常见的用例是存储结构化项。虽然单个逻辑对象大于4MB的情况不常见，但我们经常看到数组或映射总共包含超过4MB。

CacheLib还具有紧凑缓存 (compact caches)，这是一种设计用于缓存小于缓存行（通常为64B或128B）对象的DRAM缓存。紧凑缓存在单个缓存行中存储具有相同键大小和对象大小的对象 [18, 29, 46, 80]。紧凑缓存是组相联缓存，其中每个缓存行是一个由键的哈希索引的集合。LRU驱逐通过在每个集合内重新定位缓存行中的对象来完成。紧凑缓存没有每个对象开销。

使用紧凑缓存的一个突出例子是CacheLib对负缓存 (negative caching) 的支持。负缓存对象表明后端查询先前返回了空结果。负缓存对象是小的、固定大小的对象，只需要存储一个键来标识空查询。如第3.5节所讨论的，负缓存显著提高了SocialGraph中的命中率。负缓存不被Lookaside、Storage或CDN使用，但10个最大的基于CacheLib的系统中有4个使用了它。

这两个功能都强化了CacheLib的总体设计，即为不同大小的对象提供专门的解决方案，以保持低的每个对象开销。

动态资源使用和监控。 CacheLib监控总系统内存使用情况，并持续调整DRAM缓存大小以保持在指定界限以下。CacheLib暴露了几个参数来控制内存使用机制。如果系统空闲内存降至lowerLimitGB字节以下，CacheLib将迭代释放upperLimitGB和lowerLimitGB之间差值的percentPerIteration百分比，直到系统空闲内存升至upperLimitGB以上。此过程最多可以释放总缓存大小的maxLimitPercent，防止缓存变得太小。虽然释放内存可能导致驱逐，但此功能旨在防止 outright crashes，这对缓存命中率的影响要糟糕得多（见图15）。随着系统空闲内存的增加，CacheLib通过类似的过程回收内存。

热重启。 CacheLib通过使用POSIX共享内存 [76] 分配DRAM缓存空间来实现热重启。这允许缓存在关闭时将其缓存状态留在共享内存中。然后，新的缓存可以在启动时获取缓存状态的所有权。默认情况下，DRAM缓存将其索引永久保存在共享内存中。所有其他DRAM缓存状态在关闭期间被序列化到共享内存中。LOC B树索引和SOC布隆过滤器在关闭期间被序列化并写入闪存上的专用部分。

5. 评估¶

在评估CacheLib时，我们的目标是证明CacheLib的API和功能集足够灵活，可以在Facebook内部和外部实现常见用例。具体来说，我们展示了基于CacheLib的系统可以轻松实现与专用解决方案相竞争的性能，而无需对核心缓存引擎进行任何专门化。我们还展示了CacheLib的广泛采用如何对Facebook生产环境产生重大影响。

5.1. 系统比较¶

我们使用CacheBench（随CacheLib提供的缓存基准测试工具）驱动我们的实验。为了比较，我们扩展了CacheBench以 targeting 一个进程内版本的Memcached [37]，以及HTTP代理（CDN）缓存。

CacheBench通过从可配置的流行度、键大小和对象大小分布中采样，提供了一个模块化的请求生成器。为了模拟流失，CacheBench以可配置的速率持续引入新键。我们根据第3节中呈现的应用旁路和CDN用例的测量值来实例化这些参数。

应用旁路缓存。 在开发CacheLib之前，Facebook的几个团队使用Memcached的内部变体作为旁路缓存。然而，应用程序现在使用基于CacheLib的旁路缓存。因此，我们将CacheLib与一个改动最小的Memcached v1.6.6进行比较，这是最新版本，并包含了许多最近的优化。为了公平，我们将CacheLib和Memcached配置为都使用它们的LRU驱逐实现。为了实现旁路模式，CacheBench配置CacheLib将“set”实现为allocate后跟insertOrReplace，将“get”实现为find和随后对ItemHandle的getMemory方法的访问。

我们使用32个线程在不同缓存大小下评估CacheLib和Memcached。当缓存较小时，命中率较低，这会给驱逐代码路径（set操作）带来压力。当缓存较大时，命中率较高，这会给LRU头部更新代码路径（get操作）带来压力。

图12显示了缓存大小在8到144GB之间、典型工作集为1亿个对象时的命中率和吞吐量。Memcached和CacheLib实现了相似的命中率，但CacheLib的吞吐量比Memcached高得多。这种差异在较小的缓存大小下最为明显，此时驱逐操作占主导地位。CacheLib的驱逐代码路径比Memcached的更高效，因为CacheLib使用细粒度锁来减少争用。随着缓存大小的增加，命中率提高，LRU头部更新的争用成为瓶颈。CacheLib通过限制流行Item更新其LRU状态的速率来减少这种争用（见第4.2节）。Memcached没有实现类似的优化，因此在高命中率工作负载下吞吐量下降。

HTTP代理缓存。 接下来，我们将CacheLib与两个广泛部署的开源HTTP代理缓存Apache Traffic Server（ATS）[3, 44] 和NGINX [69] 进行比较。这些系统使用闪存来扩展其缓存容量。我们使用CacheBench来模拟CDN工作负载，对象大小从1KB到1MB不等。我们配置ATS和NGINX使用它们默认的闪存缓存配置。

图13显示了每个系统的吞吐量。对于大多数对象大小，CacheLib的吞吐量显著高于ATS和NGINX。对于小对象，ATS和NGINX的吞吐量受到其闪存缓存索引高DRAM开销的限制。对于大对象，ATS和NGINX的吞吐量受到其写入路径效率低下的限制。CacheLib通过其混合缓存设计（第4.2节）避免了这些问题。

与RocksDB的比较。 RocksDB [13] 是一个嵌入式键值存储，它使用日志结构合并树（LSM Tree）。我们调查了RocksDB是否可以通过在生产中部署RocksDB来缓存_SocialGraph_工作负载的数据，用作应用数据的混合旁路缓存。

RocksDB以更高的空间使用为代价来换取更低的写入和删除延迟，使用逻辑删除 (tombstones) 将删除操作推迟到压缩时 [13]。然而，大多数压缩方法计算成本高昂，必须谨慎进行。因此，使用RocksDB的Delete方法来执行对象的定向驱逐是不可行的，因为压缩发生的频率不足以通过删除来控制缓存的闪存占用空间。如果RocksDB填满了一个闪存设备，它就会开始使写入和删除操作失败。这在依赖删除来维护缓存一致性的_SocialGraph_系统中尤其成问题。如果_SocialGraph_缓存失败一定数量的删除，策略是执行冷启动（见图15）以恢复一致性。

作为替代方案，我们使用FIFO压缩测试了RocksDB，它只是在存储大小超过所需大小时简单地驱逐最旧的数据。这种压缩方法足够轻量，可以持续运行并有效限制RocksDB的闪存使用。驱逐最旧的数据往往会驱逐最近最少_更新_的对象，但这些通常与最近最少_使用_的对象不同。RocksDB没有提供跟踪哪些块包含最近使用对象的设施。由于其简单的驱逐策略，在使用生产_SocialGraph_工作负载测试时，RocksDB仅实现了53%的命中率，而CacheLib的命中率为76%。此外，FIFO压缩下的RocksDB遭受严重的读取放大，因此需要比CacheLib高50%的CPU利用率才能满足生产吞吐量水平。因此，尽管基于LSM树的解决方案的一些原理可以延续到闪存缓存的设计中，但我们得出结论，RocksDB本身不适合在Facebook进行缓存。

5.2. 生产环境中的CacheLib特性¶

我们通过考虑CacheLib引入的显著缓存改进来量化CacheLib对Facebook生产环境的影响。

DRAM开销。 根据设计，LOC和SOC的DRAM开销很小；在生产中我们测量分别小于0.1%和0.2%。DRAM缓存通常具有较低（<7%）的开销。DRAM开销有两个主要来源：slab类碎片和元数据开销（第4.2节）。调整CacheLib的slab类对于限制碎片至关重要。调整目前是手动进行的。如果不进行调整，许多集群中的碎片开销会增加一倍以上。不幸的是，我们不知道用于slab类边界自动调整的算法²。DRAM开销的详细分析见附录B。

脚注2：先前的工作考虑了如何在固定的slab类之间划分缓存空间 [22]，但没有考虑如何首先最优地定义边界。从概念上讲，这个问题类似于线上的设施放置问题 [15]，但我们不知道最优算法。

闪存耐久性。 CacheLib旨在限制对闪存的写入速率，以延长闪存设备的使用寿命（见第4.2节）。我们现在评估这种设计的有效性。

LOC由于使用4KB页和大小类而产生应用级写入放大。碎片通常很小，但Storage和CDN缓存分别有4.9%和7%的碎片开销。为了进一步减少写入放大，CacheLib最近引入了一项新功能，该功能在将区域刷新到磁盘之前缓冲所有写入。这允许应用程序以低至512字节的对齐大小进行写入，将CDN缓存中的碎片从7%减少到2%。

LOC使用FIFO驱逐而不是LRU，允许CacheLib顺序写入闪存。顺序写入将设备级写入放大从1.5倍降低到1.05倍，代价是应用级写入放大略有增加。净效果是每秒对闪存设备的NAND写入次数减少了15%。

SOC由于总是写入4KB（即使对象大小<2KB）而产生应用级写入放大。平均而言，我们测量这大约是插入字节数的6.5倍。SOC还由于写入随机的4KB页而产生显著的设备级写入放大 [43]。我们测量这种开销在1.1倍（对于Lookaside）到1.4倍（对于Storage）之间，具体取决于工作负载。

为了实现这些水平的设备级写入放大，闪存通常被过度配置50%。这种过度配置被SOC的空间效率和闪存相对于DRAM的低成本所抵消，但在保持当前性能水平的同时减少闪存过度配置是Facebook面临的一个开放挑战。

为了进一步限制写入闪存设备的字节数，CacheLib对闪存缓存使用接纳策略。默认的CacheLib接纳策略以固定概率接纳对象，延长了闪存设备的使用寿命，但也通过随机拒绝对象降低了命中率。CacheLib还包括拒绝优先 (reject first) 接纳策略，该策略在对象第一次从DRAM驱逐时拒绝它们。

最近，CacheLib更新为包含一个更高级的接纳策略，类似于 [32] 中提出的Flashield策略，该策略通过尝试预测对象的未来流行度来做出闪存接纳决策。Flashield的预测基于对象在DRAM期间接收到的命中次数。然而，在Facebook，许多对象在DRAM中停留的时间不够长，无法获得多次命中。因此，CacheLib实现了对对象请求频率的有效跟踪，超出了它们在DRAM缓存中的生存期。然后使用这些频率来预测如果对象被接纳到闪存将会接收到多少次命中。我们在附录C中详细描述了我们对这种高级接纳政策的经验。高级接纳策略在SocialGraph中将闪存的写入速率降低了44%，而没有降低命中率。

命中率。 CacheLib的DRAM缓存最初使用LRU驱逐策略的变体。当我们部署基于2Q的驱逐策略 [54] 时，系统的命中率出现了显著改善。例如，SocialGraph缓存的命中率提高了5个百分点，CDN缓存的命中率提高了9个百分点。

更大程度的命中率改善来自部署大容量混合DRAM-闪存缓存。需要巨大缓存容量的服务通常由两层层次结构组成，其中“L1”纯DRAM缓存将未命中转发到“L2”混合DRAM-闪存缓存。为了看到混合缓存带来的改进，我们将使用混合缓存的部署中的SocialGraph L2缓存与仍然使用纯DRAM缓存的部署中的SocialGraph L2缓存进行比较。SocialGraph的纯DRAM L2缓存目前实现了25%的命中率。混合缓存L2提供20倍以上的缓存容量，实现60%的命中率，并且成本比纯DRAM部署低25%。

图14显示了Lookaside、SocialGraph和CDN集群（一些最大的CacheLib部署）的L1和L2缓存的命中率分布。L1缓存实现了比L2缓存高得多的命中率，中位命中率范围从75%（CDN）到92%（SocialGraph），而L2缓存的中位命中率范围从67%（CDN）到75%（SocialGraph）。这些系统的综合命中率非常高：在95%到99%之间。

热重启的影响。 图15显示了在不执行热重启的情况下重启的L1和L2 SocialGraph缓存的命中率。如果未启用此功能，缓存重启会导致命中率下降，然后缓慢恢复正常。这在L2混合缓存中尤其具有破坏性，因为大容量缓存可能需要几天时间才能“预热”。这样的命中率下降可能转化为后端系统的临时过载，这些系统假设相对稳定的到达速率。

图14： 在典型的一天中，前四个CacheLib用户的服务器的命中率分布。

图15： 缓存重启期间SocialGraph L1缓存（左）和L2缓存（右）的命中率。当热重启被禁用时，命中率会受到影响。

6. 经验与讨论¶

Facebook使用CacheLib的经验揭示了关于现代缓存系统发展轨迹的大量信息。

新功能被许多系统采用。 人们可能期望许多CacheLib功能最终只适用于少数服务。然而，我们的经验显示了相反的趋势：为一个特定服务开发的功能经常被许多其他基于CacheLib的服务采用。 例如，混合缓存和高效的对象过期（TTL）都是在CacheLib初始部署后添加的。今天，混合缓存被五个大型CacheLib用例使用。对象过期最初是为了在旁路缓存中强制执行公平共享而添加的，但后来被需要定期刷新静态内容的CDN缓存采用。然而，并非每个功能都被每个系统使用。使用通用缓存引擎并不等同于开发单一的、一刀切的缓存方法。相反，我们的目标是从提取公共缓存功能中受益，同时仍然允许高度灵活的缓存定制。

性能改进有助于许多系统。 即使CacheLib的微小性能改进（见第5.2节）由于基于CacheLib的系统在Facebook的广泛部署也会产生巨大的影响。部署新功能通常涉及简单的代码更新或配置更改。进行集中改进的能力激励了持续优化CacheLib代码库的努力。例如，在撰写本文时，LOC索引实现（见第4节）改为使用新的稀疏哈希映射实现，在内存开销不变的情况下将CPU利用率降低了0.5%。虽然单个系统中0.5%的CPU降低可能不值得开发成本，但在Facebook所有混合缓存中降低0.5%相当于巨大的资源节省。这凸显了通用引擎相对于专门化的优势。

提高的稳定性。 通用缓存引擎的另一个好处是由于将先前 disjoint 的实现减少到一个成熟的、经过良好测试的平台而提高了稳定性。随着新系统的构建，使用CacheLib大大减少了必须引入生产环境的新代码行数。这降低了生产事故和中断的可能性。CacheLib还提供了明确的稳定性机制，这些机制基于多年在生产环境中部署缓存的经验。

没有单一的缓存系统占主导地位。 人们可能会问，将CacheLib工程工作的重点放在适应一小部分用例上，而不是广泛部署CacheLib，是否就足够了。为了回答这个问题，我们比较了每个系统使用的DRAM缓存总量³。图16显示，前十大用户占所有DRAM缓存使用量的89%，但没有单个服务占主导地位。例如，前两个服务分别仅占DRAM使用量的25%和20%。因此，除非CacheLib能够适应许多不同的用例，否则优化CacheLib的整体收益将是有限的。

图16：使用CacheLib构建的Facebook服务范围广泛。我们根据其总DRAM缓存大小来衡量服务的部署规模。没有一个服务拥有超过Facebook服务总缓存空间25%的份额。

闪存缓存标志着范式转变。 人们可能认为缓存命中率通常很高，因此期望从闪存提供的额外缓存容量中获益甚微。虽然在某些情况下确实如此，但高命中率并不总是意味着额外的缓存容量是徒劳的。具体来说，工程师配置缓存是为了使下一个字节DRAM的边际成本与随之而来的命中率增加的边际效益相等。闪存缓存改变了这种成本计算，将额外缓存容量的边际成本降低了一个数量级。这使得不仅值得大幅增加缓存容量，而且值得部署那些仅使用DRAM没有意义的新混合缓存。

此外，对于大多数系统来说，缓存命中的好处不再 strictly 是一个延迟问题。虽然经典的缓存观点认为，只有减少平均内存访问时间 [46] 时缓存才值得，但这忽略了缓存未命中带来的连锁效应，如增加网络拥塞、后端负载和后端功耗。从这个角度来看，闪存中的缓存命中与DRAM命中一样有价值，即使闪存比DRAM慢几个数量级。这再次使边际成本计算的天平倾向于部署闪存缓存。

CacheLib并不总是带来性能提升。 基于CacheLib的系统并非从一开始就总是优于它们所取代的专用系统。例如，基于CacheLib的CDN系统的第一个实现无法匹配原始CDN系统的性能，原始系统通过实现具有低闪存写入速率的高级驱逐策略来优化闪存缓存。在测试中，第一个基于CacheLib的CDN实现比专用系统实现了低10%的命中率和20%的更高闪存写入速率。

在部署基于CacheLib的CDN实现之前，向CacheLib添加了优化以改进混合缓存机制。LOC驱逐策略从纯FIFO驱逐扩展到包括重新接纳策略，该策略可以在频繁请求的对象被驱逐时重新接纳它们。在DRAM和闪存缓存之间还添加了写入缓冲区。这些缓冲区通过减少由于4KB对齐写入而产生的内部碎片来降低应用级写入放大。写入缓冲区还允许CacheLib向闪存发出更少、更大的写入，从而降低了设备级写入放大。

改进的LOC驱逐策略实现了接近专用系统的命中率，同时比专用系统少执行10%的闪存写入。这两种优化如果关闭，几乎不会增加任何开销，并且最终也改善了其他基于CacheLib的系统的性能。例如，在这些更改之后，Lookaside的P99闪存读取延迟减少了25%，闪存写入速率降低了2%。

CDN的例子说明了平衡通用化与专门化权衡的常见情况：CacheLib并不总是从一开始就满足每个用例的需求。然而，专用系统所需的功能通常与CacheLib的设计并非根本不相容。如果愿意花时间将必要的功能构建到CacheLib中，他们将获得访问CacheLib完整功能集的机会，同时将新的优化导出到Facebook其他缓存系统。

CacheLib并不适用于所有用例。 尽管CacheLib处理许多用例，但我们意识到一些限制阻止了某些用例采用CacheLib。例如，一些广告服务系统依赖于缓存嵌套数据结构。为了控制其内存使用并快速将Item从DRAM序列化到闪存，CacheLib只支持映射到扁平地址空间的数据结构。因此，这些广告服务系统无法采用CacheLib。

另一个例子是RocksDB，它希望使用CacheLib来实现其内部页缓冲区。CacheLib的C++ API利用对象构造函数和析构函数来执行itemHandle对象的引用计数。这最终阻止了程序员将CacheLib与RocksDB的C风格代码库集成。然而，自动引用计数的简便性导致了CacheLib在C++和基于Rust的用例中的广泛采用。

脚注3：并非所有服务都使用混合缓存，尤其是注重吞吐量的L1缓存。

7. 相关工作¶

有大量关于缓存系统的研究，包括对单个生产缓存的深入描述。我们回顾了在与Web和数据中心缓存相关的背景下，来自工业界和学术界的前期工作。

生产缓存系统。 缓存系统存在于许多主要的Web服务中。Akamai的地理分布式CDN [9, 28, 39, 67, 81, 85]、Microsoft的Web缓存系统 [8]、Amazon的聚合缓存使用 [26] 以及Facebook的许多独立缓存系统 [5, 48, 71, 72, 86] 都在文献中有记载。类似地，Twitter [42, 92] 和Reddit [33, 89] 经常讨论它们基于开源缓存系统的DRAM缓存。CacheLib解决了这些独立系统所面临挑战的超集，提供了一个单一的、通用的缓存引擎。

研究缓存系统。 学术研究考虑了优化缓存系统的许多不同方面。这些包括构建高度并发的系统 [6, 9, 35, 62, 64] 和提高命中率 [6, 9, 10, 21, 50, 51, 61, 88]。Facebook的目标是使用CacheLib作为一个平台，以便更容易地评估和部署基于这项研究的系统。

虽然文献主要关注DRAM缓存，但之前也有一些关于闪存缓存的工作 [32, 57, 60, 86]。CacheLib融合了 [86] 和 [60] 的思想，通过在闪存上进行FIFO驱逐来减少写入放大。同样，CacheLib包含了 [57] 的接纳策略和 [32] 的接纳策略的一个变体（见附录C）。

尽管在CacheLib中动态缓存分区是可能的，但现有缓存分区策略研究在Facebook的影响有限。分区可用于消除缓存命中率随大小变化的性能悬崖 [7, 22, 88]，但性能悬崖在Facebook不是主要问题。正如RobinHood [8] 的作者在他们的工作中指出的，当基础设施在不同后端系统之间共享时（Facebook就是这种情况），RobinHood分区方案受到限制。此外，检索存储在闪存上的对象大小的计算开销太高，无法在实践中使用大小感知分片 [27]。

8. 结论¶

缓存是现代数据中心应用程序的重要组成部分，本文仅触及了其许多挑战和机遇的表面。CacheLib表明，构建一个通用缓存引擎来解决各种各样的缓存用例是可行的。在分享我们构建和部署CacheLib的经验时，我们希望征求不断增长的缓存研究社区的想法和反馈，并鼓励其他生产系统分享他们的架构和工作负载。我们希望CacheLib将成为工业界和学术界最佳实践的聚合点，实现性能的持续改进，并促进缓存在许多新应用中的部署。未来的缓存系统有许多令人兴奋的方向值得探索，包括（i）更好的资源管理策略（例如，驱逐/接纳策略、内存管理）；（ii）新兴硬件平台（例如，FPGA加速、非易失性内存、分区命名空间SSD）；（iii）新颖的应用功能（例如，负缓存中看到的功能）。我们期待发展CacheLib以应对这些挑战和许多其他挑战。

附录A. 缓存查找顺序和延迟¶

CacheLib使用查找顺序 1) DRAM缓存, 2) LOC, 3) SOC。请注意，对象的大小是事先未知的。因此，在DRAM缓存未命中之后，CacheLib不知道对象是存储在LOC还是SOC中。因此，它必须先查询其中一个，如果未命中，再查询另一个。

CacheLib的查找顺序是由以下对平均查找惩罚（也称为平均内存访问时间，AMAT [46]）的分析所驱动的。我们将每个缓存组件的查找惩罚视为确定对象未缓存在该组件中所花费的时间。我们的关键假设是从DRAM读取比从闪存读取快几个数量级（例如，100ns对比16us [25]）。因此，DRAM缓存的查找惩罚是几次内存引用（假设为500ns）。

要计算LOC的惩罚，请回忆LOC为了减少DRAM元数据开销，既不在内存中存储对象的键，也不存储对象的确切大小。LOC通过4字节哈希分区的B树进行索引，每个B树使用4字节哈希来标识对象的偏移量。如果整个8字节哈希没有哈希冲突，那么LOC的查找惩罚包括几次内存引用（假设由于哈希操作需要1us）。如果存在哈希冲突，LOC需要一次闪存读取（16us）来比较对象键并确定未命中状态。假设最小的LOC对象大小（2KB）和1TB闪存，LOC中最多存储5.36亿个对象。因此，8字节哈希冲突的概率可以计算为小于百万分之一，LOC的平均查找惩罚略高于1us。

要计算SOC的惩罚，请回忆SOC不使用内存索引。SOC使用每页布隆过滤器（假设1us）来机会性地确定未命中状态。然而，由于这些布隆过滤器很小，它们的错误率是10%。如果发生布隆过滤器错误，SOC需要一次闪存读取（16us）来比较对象键。因此，SOC的平均查找惩罚是2.6us。

CacheLib使用默认顺序（1) DRAM缓存, (2) LOC, (3) SOC）的平均延迟（AMAT）如下，其中(L)表示查找延迟，(H)表示命中率：(L(\text{DRAM})+(1-H(\text{DRAM}))\times\left(L(\text{LOC})+(1-H(\text{LOC})) \times L(\text{SOC})\right))。如果SOC和LOC的顺序颠倒，平均延迟将增加几微秒，具体取决于LOC和SOC的命中率。因此CacheLib最后查询SOC。

附录B DRAM开销详情¶

DRAM缓存。 我们将CacheLib的DRAM缓存开销测量为其总内存占用与缓存的键和值大小之和的比率。我们进一步将开销分解为slab类碎片和元数据。在_Lookaside_、_Storage_和_SocialGraph_中，我们发现总开销在2.6%到7%之间，并且碎片和元数据平均分配。

\begin{tabular}{l c c c} & Lookaside & Storage & SocialGraph \ \hline 碎片 & 3.9% & 3% & 1.6% \ 元数据 & 3% & 4% & 1% \ \hline 总开销 & 6.9% & 7% & 2.6% \ \end{tabular}

大对象缓存。 回想一下，虽然LOC使用8字节哈希，但其中4字节用于分区B树，因此不需要计入。所以，LOC存储4字节用于键哈希，4字节用于闪存偏移量，以及每个Item平均2.5字节用于B树指针。对于小的LOC对象，这是0.61%。在生产系统中，这种开销很低，范围从0.01%（Storage）到0.1%（Lookaside）。

附录C 闪存的高级接纳策略¶

使用闪存进行缓存的一个重大挑战是尊重闪存设备有限的写入耐久性。如果混合缓存中所有从DRAM驱逐的对象都被接纳到闪存，我们观察到的写入速率将比允许闪存设备达到其目标寿命的速率高出50%。因此，闪存接纳策略在CacheLib的性能中扮演着重要角色。

Flashield [32] 是最近提出的一种闪存接纳策略。Flashield依赖于观察对象在穿越混合缓存的DRAM部分时的行为。当对象从DRAM驱逐时，Flashield根据对象在DRAM期间被访问的频率做出闪存接纳决策。

不幸的是，在Facebook，DRAM的生存时间太短，Flashield无法有效。有相当数量的对象如果存储在闪存上会足够流行以产生命中，但在DRAM缓存中并未接收到命中。事实上，对于一个L2 _Lookaside_缓存，只有14%的考虑进行闪存接纳的对象在DRAM期间接收到了一次读取或写入。

为了使Flashield背后的主要思想适应Facebook的环境，CacheLib明确地收集关于对象超出其DRAM缓存生存期的特征。我们使用布隆过滤器来记录过去六小时的访问⁴。此外，我们将接纳策略的预测指标从抽象的“闪存适合度”概念改为直接预测对象未来预期接收的读取次数。

脚注4：具体来说，我们使用6个布隆过滤器，每个设置为保存1小时的访问。每小时，最旧的布隆过滤器被重置并用于跟踪接下来的一小时。这些布隆过滤器在最大观测查询速率下配置为0.02%的误报率。布隆过滤器的空间效率对于避免使用过多DRAM是必要的——使用每个存储键8字节来存储历史记录空间开销太大。

我们的高级接纳策略针对_SocialGraph_进行了训练并在生产环境中部署。CacheLib闪存缓存的默认接纳策略是以固定概率接纳对象，该概率期望将闪存写入速率保持在目标速率以下。与这种默认接纳策略相比，高级接纳策略向闪存设备写入的字节数减少了44%，而没有降低缓存命中率。因此，虽然训练高级接纳策略所需的模型可能很麻烦，但该策略显著延长了生产环境中闪存设备的使用寿命。

致谢¶

这项工作得到了NSF-CMMI-1938909、NSF-CSR-1763701、NSF-XPS-1629444、2020年谷歌教师研究奖和Facebook研究生奖学金的支持。我们还要感谢PDL联盟（阿里巴巴、亚马逊、Dartium、Facebook、谷歌、HPE、日立、IBM、英特尔、微软、NetApp、甲骨文、Pure Storage、Salesforce、三星、希捷、Two Sigma和西部数据）的成员和公司以及VMware的兴趣、见解、反馈和支持。