Kangaroo：针对微小对象优化的闪存缓存 (2021)
Kangaroo：一种针对微小对象的新型优化闪存缓存
研究内容：
Kangaroo 是一种新型的闪存缓存，它能够更有效地缓存微小对象（大约 100 字节或更小的对象），并克服现有闪存缓存设计带来的挑战。由于 Kangaroo 是在 CacheLib（Facebook 的开源缓存引擎）中实现的，因此开发人员可以通过 CacheLib 的 API 使用 Kangaroo 来构建自己的定制缓存服务。
我们与卡内基梅隆大学 (CMU) 合作进行了这项研究。由此产生的论文在 2021 年的 Symposium on Operating Systems Principles (SOSP) 会议上荣获最佳论文奖。
CacheLib 的 API 允许开发人员构建和定制并发缓存。
Kangaroo 针对微小对象进行了优化，最大限度地减少了动态随机存取存储器 (DRAM) 的使用和写入次数，并引入了一种新的缓存驱逐策略，该策略以最小的 DRAM 开销减少了缓存未命中，进一步降低了后端存储系统的负载。
Kangaroo 的 CacheLib 实现还允许我们的研究人员快速评估 Kangaroo 的设计对真实生产工作负载的影响。我们使用来自 Facebook 和 Twitter 的生产社交图缓存工作负载的跟踪数据评估了 Kangaroo。我们的实验表明，与之前的最先进的闪存缓存设计相比，在实际系统约束（DRAM 和写入速率约束）下，Kangaroo 将未命中率降低了 29%。这些结果通过在影子生产设置中对 Kangaroo 进行的测试部署得到了证实。
在为期七天的 Facebook 跟踪中，所有三个系统的未命中率。与集合关联 (SA) 缓存相比，Kangaroo 将缓存未命中率降低了 29%，与日志结构 (LS) 缓存相比降低了 56%。
工作原理：
当前的闪存缓存主要分为两类：集合关联缓存和日志结构缓存。集合关联缓存写入的字节数远远超过必要的字节数，因为它们必须为每个对象写入一个 4 KB 的闪存页（最小写入粒度）。对于大小约为 100 字节或更小的微小对象，这会导致显着的写入放大（即，集合关联缓存写入的字节数比严格意义上必要的字节数多约 40 倍）。
日志结构缓存具有很大的 DRAM 开销，因为它们必须为每个闪存对象保留一个索引条目。因此，集合关联闪存缓存和日志结构闪存缓存都不能很好地设计用于微小对象闪存缓存。
Kangaroo 结合了日志结构缓存和集合关联缓存，以减少 DRAM 和闪存写入开销。Kangaroo 有两个主要部分：KLog（一个小的日志结构闪存缓存）和 KSet（一个大的集合关联闪存缓存）。
查找首先检查 DRAM 缓存 (1)。如果对象不在 DRAM 缓存中，则请求检查 KLog 的索引 (2a)，然后在索引中找到该对象时从闪存中读取该对象 (2b)。请求最终检查 KSet 中每个集合的 Bloom filter (3a)，如果对象可能在 KSet 中，则读取该集合 (3b)。
对于插入，Kangaroo 首先将对象插入到 DRAM 缓存中 (1)。从 DRAM 缓存中驱逐的对象要么被 preflash 准入策略删除 (2a)，要么被添加到 KLog 的 DRAM 索引 (2b) 并附加到 KLog 的闪存日志 (2c)。从 Klog 中驱逐的对象要么被另一个准入策略删除 (3a)，要么被插入到 KSet (3b)。
Kangaroo 的一项创新在于它如何将对象从 KLog 移动到 KSet。Kangaroo 使用 KLog 查找映射到 KSet 中同一集合的多个对象，例如上面显示的粉色和黄色对象。每当对象从 KLog 中驱逐时，Kangaroo 都会主动从 KLog 中驱逐对象，以最大限度地减少 KSet 中的写入放大。
由于无论插入的对象数量如何，写入集合始终需要写入 4 KB，因此写入两个对象而不是一个对象会将每个对象的写入开销减半。因此，Kangaroo 可以将对 KSet 的写入分摊到多个对象上，从而减少写入闪存的字节总数。KLog 使用小容量（约占闪存的 5%）来实现此目标，因此 Kangaroo 只需要少量 DRAM 即可为 KLog 的整个容量建立索引。因此，Kangaroo 解决了在闪存上缓存微小对象的 DRAM 和闪存写入开销。
除了这个基本设计之外，Kangaroo 还引入了其他技术来实现其分层设计并提高其有效性。特别是，由于 Kangaroo 是一个缓存而不是键值存储，因此它可以驱逐对象以最大限度地减少写入。Kangaroo 通过添加阈值准入策略来利用此机会，如果从 KLog 插入的对象少于 n 个，则该策略会驱逐对象而不是将其添加到 KSet。此准入策略允许 Kangaroo 保证将对象移动到 KSet 的写入开销将远低于集合关联缓存。Kangaroo 提供了进一步的优化，以减少 DRAM 开销并减少未命中，如我们的 SOSP 2021 paper 中所述。
总而言之，这些优化使 Kangaroo 能够克服日志结构缓存和集合关联缓存的局限性，从而创建一个闪存缓存，实现高效缓存微小对象的目标。
重要性：
缓存通过允许更快地访问数据并降低数据库和其他后端系统的负载，在大型系统中发挥着重要作用。对于大型缓存，使用闪存比使用 DRAM 效率更高。但是，在缓存微小对象时，闪存缓存会变得不足。闪存缓存要么需要太多的 DRAM，这会降低闪存的效率优势，要么需要太多的写入，这会过快地耗尽闪存设备。在任何一种情况下，闪存缓存都无法充分发挥其作为高效、大型微小对象缓存的潜力，最终导致缓存更小，后端系统的负载更大。
许多社交媒体和 IoT 服务都有大量的微小对象，每个对象几百字节或更少。例如，Facebook 社交图中的边，需要连接朋友、帖子和图像等内容，平均低于 100 字节。在闪存上高效地缓存这些对象可以快速大规模地检索它们，并最大限度地减少后端存储服务的负载。Kangaroo 通过具有低 DRAM 和写入开销来实现微小对象的大规模闪存缓存，从而降低大型闪存缓存中的未命中率。
阅读完整论文：
Kangaroo: Caching billions of tiny objects on flash
鸣谢：
作者要感谢 Sara McAllister 领导该项目并帮助我们起草这篇博文，以及 CMU Parallel Data Lab 的成员，感谢他们在指导研究以及与 Facebook 合作方面提供的意见。