Kangaroo: Caching Billions of Tiny Objects on Flash

摘要

许多社交媒体和物联网服务都有非常大的工作集，由数十亿个微小(100 B)对象组成。大型的、基于闪存的缓存对于以可接受的货币成本为这些工作集提供服务非常重要。然而，在flash上缓存微小的对象是有挑战性的，原因有两个:(i) ssd只能在比单个对象大得多的多kb页面中读写数据，这强调了flash可以写入的次数有限;(ii)在不失去闪存的成本优势的情况下，每个缓存对象可以在DRAM中保存很少的比特。不幸的是，现有的闪存缓存设计未能解决这些挑战:写优化设计需要太多的DRAM，而DRAM优化设计需要太多的闪存写。

我们介绍Kangaroo，一个新的闪存缓存设计，优化了DRAM使用和闪存写入，以最大化缓存性能，同时最小化成本。Kangaroo结合了一个大的，集合关联的缓存和一个小的，日志结构的缓存。集合关联的缓存只需要最少的DRAM，而日志结构的缓存则将Kangaroo的闪存写操作最小化。使用Facebook和Twitter的跟踪数据进行的实验表明，Kangaroo的DRAM使用接近于最佳的事先DRAM优化设计，闪存写入接近于最佳的事先写优化设计，且漏写率比两者都好。Kangaroo的设计是帕累托最优的范围内允许写率，DRAM大小和闪存大小，减少了29%的失误比目前的先进水平。Kangaroo的设计是帕累托最优的范围内允许写率，DRAM大小和闪存大小，减少了29%的失误比目前的先进水平。 这些结果在Facebook的一个生产闪存的测试部署中得到了证实。

1、介绍

许多web服务需要快速、廉价地访问数十亿个微小对象，每个对象只有几百字节或更少。例如社交网络，如Facebook或LinkedIn；微博服务，如Twitter；电子商务；以及物联网中的新兴传感应用。考虑到这些应用程序的社会重要性，对于高性能和低成本(即资金和操作费用)的缓存微型对象有很强的需求。

在现有的内存和存储技术中，闪存是目前性价比最高的。DRAM和非易失性存储器(nvm)具有出色的性能，但两者的价格都比闪存高一个数量级。因此，使用大量的闪存和最小的DRAM的成本争论。

Flash的主要挑战是它的写入耐力有限;也就是说，flash在磨损之前只能被写入一定次数。磨损对于小对象来说尤其是个问题，因为flash只能在多kb的粒度下进行读写。例如，写一个100b的对象可能需要写一个4kb的flash页面，将写入的字节增加40倍，并迅速耗尽flash设备。因此，最大限度地减少写入闪存的多余字节也是成本问题。

这个问题。以前的闪存缓存设计要么使用了太多的DRAM，要么写了太多的闪存。日志结构的缓存顺序地写对象到闪存，并保持一个索引(通常在DRAM中)，跟踪对象在闪存中的位置[20,35,47,63,64,67]。通过顺序地写入对象，并批处理许多插入到每个闪存写入中，日志结构的缓存大大减少了写入闪存的多余字节。然而，跟踪数十亿个微小的对象需要一个大的索引，甚至一个高度优化的索引也需要大量的DRAM[35]。集合关联缓存通过哈希对象键到不同的集合进行操作，很像CPU缓存[16,25,55]。这些设计不需要DRAM索引，因为一个对象的可能位置是由它的键暗示的。然而，集合关联缓存会将许多多余的字节写入闪存。将单个小对象写入缓存需要重写整个对象集，这大大增加了写入闪存设备的字节数。

我们的解决方案:袋鼠。我们将介绍袋鼠，一种新的闪存缓存设计，可用于数十亿个小对象。关键的观点是，现有的缓存设计都解决了问题的一半，它们可以结合在一起，克服彼此的缺点，同时放大它们的优点。

袋鼠采用了层次化的设计来达到日志结构和集合关联缓存的最佳效果(图1a)。为了避免大的DRAM索引，袋鼠将大量的缓存容量组织成一个集合关联的缓存，称为KSet。为了减少写闪存，袋鼠在KSet前面放了一个小的(例如5%的闪存)日志结构的缓存，称为KLog。KLog缓冲了许多对象，在KSet中寻找映射到同一集合的对象(例如，哈希冲突)，这样每次写入KSet的闪存都可以插入多个对象。我们的见解是，即使是一个小的日志也会产生许多哈希冲突，所以只需要少量的额外DRAM(用于KLog的索引)就可以显著减少闪存写入(在KSet中)。

在“袋鼠”的设计中，各层相互补充，以最大限度地提高命中率，同时降低闪存和DRAM的系统成本。袋鼠算法引入了三种技术，有效地实现了其分层设计，提高了其有效性。首先，袋鼠的分区索引可以在使用最少的DRAM的情况下，高效地找到KLog中映射到KSet中同一集合的所有对象。其次，由于袋鼠是一个缓存，而不是键值存储，它可以自由删除对象，而不是将它们招收进KSet。袋鼠的阈值允许策略利用了这种自由，只在有足够的哈希冲突时才允许对象从KLog到KSet，也就是说，只有在闪存写操作被充分摊平的情况下。第三，袋鼠的RRIParoo逐出策略通过支持KSet中的智能逐出来提高命中率，尽管KSet缺乏跟踪逐出元数据的传统DRAM索引。

总结的结果。我们实现袋鼠作为一个模块在CacheLib[16](可在cachelib.org)。我们通过在真实系统和模拟灵敏度研究中重现生产轨迹来评估袋鼠。先前的设计受到DRAM使用量或闪存写入速率的限制，而袋鼠则针对这两个限制条件进行了优化。例如，在典型的DRAM和闪存写预算下，《袋鼠》在Facebook的生产跟踪中降低了29%的遗漏率(图1b)，将遗漏率从0.29降低到0.20。此外，在仿真中，我们表明袋鼠可以很好地扩展闪存容量，在不同的DRAM和闪存写预算下也能很好地执行，并能很好地处理不同的访问模式。我们将详细分析袋鼠的技术，看看每个技术的贡献有多大。最后，我们通过在Facebook的一个测试部署，展示了袋鼠在现实世界中的优势。

贡献。本文的主要贡献如下:问题:我们表明，对于微小的对象，先前的缓存设计要么需要太多的DRAM(日志结构的缓存)，要么需要太多的闪存写(集合关联的缓存)。关键思想:我们展示了如何结合日志结构和集关联设计以低成本在flash上缓存微小对象，并给出了这个设计的理论依据。袋鼠式设计,实现:袋鼠引入了三种技术来实现和改进基本设计:它的分区索引、阈值准入和RRIParoo驱逐。这些技术提高了命中率，同时保持DRAM使用、闪存写入和低运行开销。结果:我们显示，不像以前的高速缓存，袋鼠的设计可以处理不同的DRAM和闪存写预算。因此，袋鼠是帕累托最优的范围内的约束和不同的工作负载。

2、背景和相关工作

本节讨论依赖数十亿个微小对象的重要应用程序，为什么需要flash来缓存它们，flash带来的挑战，以及现有的flash-cache设计的缺点。g

2.1微型对象是重要且数量众多的

在许多大型系统中，小对象非常普遍:

在Facebook，小对象普遍存在于社交图中。例如，社会图的平均边缘大小小于100 B。通过边缘、节点和其他对象，平均对象大小小于700 B[16,25]。这导致了针对小对象[16]的专用闪存缓存系统的开发。

在Twitter上，tweet被限制在280b，并且tweet的平均长度小于33个[57]字符。由于大量且不断增长的tweet, Twitter寻求一种经济有效的缓存解决方案[76]。

在微软Azure，一个日益增长的用例是处理来自传感器数据的更新，比如来自Azure流分析中的物联网设备。在处理一个更新(例如，触发一个实时操作)之前，服务器必须获取平均大小为300b的元数据(传感器的测量单位、地理位置、所有者等)。为了提高效率和可用性，服务器缓存最流行的元数据[38]。另一个用例出现在搜索广告中，Azure缓存预测和其他结果[48,49]。

每个系统都访问数十亿个对象，每个对象都大大低于块存储设备的最小写粒度4 KB。 例如，Facebook每天记录15亿用户的[9]，单是好友连接，每个用户就有数百到数千条边[25,68]。 Twitter每天有超过5亿条新推文，每天有超过1.9亿的用户。 虽然物联网更新频率和广告印象并不公开，但据估计，在2020年[33]，连接设备的数量在上超过了500亿，而且据估计，早在2007年，平均每人每天就会看到5000个广告[65]。  

2.2在flash中缓存微小的对象是困难的

虽然上述应用程序中的各个对象都很小，但各个服务器上的应用程序工作集的数据总量仍然高达tb。为了降低后端数据管理系统的吞吐量需求，应用程序依赖于大规模、经济高效的缓存，因为一个缓存服务器可以取代数十个后端服务器[16]。不幸的是，正如下面所述，当前的缓存系统对于小对象的效率很低。因此，需要为大量的小对象优化缓存系统。

为什么不使用内存呢?DRAM是昂贵的，无论是在采集和每位的功率成本方面。这使得传统的DRAM缓存难以扩展，特别是当数据大小呈指数级增长时。由于运营方面的考虑，DRAM容量也经常受到限制。数据中心运营商通常提供数量有限的服务器配置，以降低管理复杂性。在一些实际的部署中，为了缓存而调整服务器配置是不可能的[66]。此外，DRAM通常需求量很大，因此所有的应用程序都被鼓励尽量减少DRAM的使用。例如，最近几年Facebook的趋势是减少内存，增加每台服务器的闪存[16,66]。

为什么不使用闪存呢?目前，在内存和存储技术中，Flash提供了性能和成本的最佳组合，因此是大多数大规模缓存的选择技术[16,22,23,35,64]。它比DRAM持久、便宜、节能，而且比机械磁盘快得多。虽然基于闪存的缓存确实使用DRAM来处理元数据和“热”对象，但缓存的大部分容量都是闪存，以降低端到端的系统成本。

flash缓存的挑战。Flash出现了许多DRAM缓存中不存在的问题。一个很大的问题是flash的写持久性是有限的，这意味着在flash设备磨损并必须更换之前，写入的次数是有限制的[24,42,46]。如果不小心，缓存会很快磨损闪存设备，因为它们快速地接收和删除对象[16,35]。因此，许多现有的闪存缓存会过度供应容量，为了减缓耗尽速度而遭受更多的遗漏[16,23]。新的闪存技术，如多层QLC(4位/ cell)和PLC(5位/ cell)[28]，提高了容量，降低了成本，但显著降低了写耐力。

闪存驱动器的写入放大问题加剧了耐力问题。写入放大发生在写入底层闪存的字节数超过最初写入数据的字节数时。写放大表示为写入字节数的乘数，因此1×的值是最小的，表明没有额外的写操作。Flash设备同时存在设备级写放大和应用程序级写放大[42]。

设备级写放大(dlwa)[35, 47, 67]发生在flash转换层(FTL)写的flash页面超过存储应用程序(例如，文件系统、数据库或缓存)的要求时。当前的闪存驱动器实现了古老的块存储接口，其中主机在数值逻辑块地址(LBA)命名空间中读写逻辑块。一般来说，内部的flash页面大小和外部的逻辑块大小是相同的，4kb是常见的，即使闪存设备只能擦除更大的页面(例如，256mb)“擦除块”。大多数dlwa是由清理活动引起的，该活动在清除擦除块之前将活动页面复制到其他地方。

一般来说，随着更多的原始闪存容量被利用，以及访问模式包含更多的小的、随机的写操作，dlwa会恶化。减少dlwa的一种常见方法是过度供应，也就是说，在LBA命名空间中只暴露一小部分原始闪存容量，因此清理往往会在坏的擦除块中发现更少的活动页面[16,23]。图2显示了对1.9 TB闪存驱动器进行随机4 KB写操作时的dlwa和使用的容量。如预期的那样，随着过度供应的减少，dlwa显著增加，从50%利用率时的≈1×增加到100%利用率时的≈10×。

当存储应用程序作为存储管理的一部分重写一些自己的数据时，应用程序级写放大(alwa)发生。其中一种形式类似于FTL清理，例如日志结构文件系统中的清理[46,59]或日志结构合并树中的压缩[6,8]。另一种形式是由于必须编写整个逻辑块而引起的。要写入少量的数据，应用程序必须读取块，安装新数据，然后写入整个块[54]。例如，将1 KB的新数据安装到4 KB的逻辑块中需要重写其他3 KB的数据，从而得到4×的alwa。理想情况下，块中未修改的数据不会被重写。

为什么缓存小对象是困难的。小对象的大小使得在flash中缓存它们具有挑战性。在大型存储设备中单独跟踪数十亿个微小对象可能需要庞大的元数据结构[35]，这要么需要大量的DRAM，要么需要额外的闪存写入(如果索引存在于闪存上)，或者两者都需要。为了分摊跟踪元数据，可以将许多小对象分组为一个更大的、长期存在的“元对象”。但是，如果元对象中的各个对象以完全不同的模式访问，那么这样做的效率可能会很低。

微小对象也是写入放大的主要挑战。传统的缓存设计(例如，DRAM缓存)可以自由地重写对象，导致小的、随机的写入;也就是说，设备级写放大的最坏情况。由于小对象比逻辑块小得多，在适当的位置重写它们将额外地涉及大量的应用程序级写放大——对于一个100b的对象在一个4kb的逻辑块中是40倍——这与设备级写放大是乘法。如上所述，将小对象分组为较大的元对象，可以将应用程序级写放大从逻辑块转移到元对象，但并不能解决这个问题。

2.3目前的方法和相关工作

本节讨论现有的flash缓存解决方案以及它们在缓存小型对象时的缺点。键值存储:高效的键值存储已经被开发和演示[8,34,50,58,72]，当需要缓存时，考虑它们是很诱人的。但是键值存储通常假设删除很少，并且存储的值必须保留，直到被告知其他情况。相比之下，缓存会频繁地删除项，并且可以自行决定(即每次删除一个项时)。随着频繁的删除，键-值存储会经历严重的写放大、更低的有效容量，或者两者兼备[15,23,35,67,72]。

作为一个具体的例子，以SILT[50]为例，它是一个键值存储库，在高级设计上与袋鼠最接近。和袋鼠一样，SILT使用多层闪存设计来平衡内存索引大小和写入放大。不幸的是，SILT的设计不适合缓存。例如，SILT的两个主要层保存了>99%的条目，它们是不可变的。因为这些层是不可变的，所以删除操作会被记录下来，并且不会立即回收空间。因此，在下一次压缩(合并和重新排序)发生之前，缓存驱逐会导致漏洞(即缓存容量减少)。可以使用更频繁的压缩来减少缓存容量的丢失，但会对性能和应用程序级写放大造成很大的损失。

类似的删除问题也会影响大多数键值存储，通常在压缩频率和不可变数据结构中的空洞之间进行权衡。也许可以通过协调驱逐和压缩操作来减少这些开销，但这并不是微不足道的，也不是这些系统的设计方式。例如，Netflix使用RocksDB[8]作为flash缓存，由于[23]问题，不得不超额供应67%。一些键-值存储通过降低读取效率来减少应用程序级写放大[51,58,72]，但不能回避删除容量浪费的根本挑战。相比之下，flash缓存具有结构和策略的自由，因此删除是有效的，浪费的空间最小。

日志结构的缓存:为了减少写放大，许多闪存缓存在闪存上使用一个日志结构，在DRAM中有一个索引来跟踪对象的位置[20,35,47,63,64,67]。虽然这种解决方案通常适用于较大的对象，但对于较小的对象，它需要大量的DRAM，因为索引必须为每个对象保留一个条目。索引可以溢出到flash上[72]，但是溢出会增加查找时的flash读操作，以及在对象被允许或被驱逐时更新索引时的flash写操作。

即使是最近为小对象设计的日志结构缓存的flashshield[35]，对于更大的闪存设备也面临DRAM问题。在优化其DRAM使用后，Flashield需要每个对象20位的索引加上大约10位的Bloom过滤器每个对象。因此，flashshield需要75gb的DRAM来跟踪100b的2tb对象。事实上，flasheld的DRAM使用量要比这个高得多，因为它依赖于内存中的缓存来决定哪些对象要写入闪存。DRAM缓存必须随着闪存容量的增长而增长，否则预测的准确性将受到影响，从而导致更多的失误。

因此，日志结构缓存所需的总DRAM可能很快超过可用的数量，并显著增加系统成本和功率。随着时间的推移，技术趋势将使这些问题变得更糟，因为与DRAM相比，每比特成本的下降速度更快[28,73]。

集合关联flash缓存:通过限制对象的可能位置[55]，可以减少在flash上定位对象的元数据。Facebook的CacheLib[16]为小对象(小于2 KB)实现了这样的设计，例如社交图[25]中的项目。CacheLib的“小对象缓存”(SOC)是一个具有可变大小对象的集关联缓存，使用哈希函数将每个对象映射到一个特定的4 KB的集合(即一个flash页面)。在这种方案中，SOC不需要索引，对于每个设置的Bloom滤波器，每个对象只需要≈3比特的DRAM。

虽然集关联设计具有更强的dram效率，但它的写入速率过高。在集合中插入一个新对象意味着重写整个flash页面，其中大部分内容没有改变，如上所述，100b对象和4kb页面的应用程序级写放大幅度为40倍。此外，闪存写是设备级写放大的最坏情况:小而随机(图2)。应用程序级写放大和设备级写放大的乘法特性对设备寿命造成了有害影响。

集合关联闪存缓存通过两种主要技术限制其闪存写速率。为了减少设备级的写放大，集合关联的闪存缓存经常被大量地过度供应。例如，CacheLib的SOC在生产环境中运行时，闪存设备的一半以上[16]为空。也就是说，缓存需要物理闪存的两倍以上才能提供给定的缓存容量。此外，为了限制应用级写放大，CacheLib的SOC采用了预闪存接纳策略[16,35]，在对象被写入闪存之前拒绝一部分对象。不幸的是，这两种技术都降低了缓存的可实现命中率。

摘要:之前的工作没有充分解决如何在flash中以低成本缓存微小对象的问题。日志结构的缓存需要太多的DRAM，而集关联的缓存增加了太多的写放大。

3、概述和动机

袋鼠是一种新的闪存缓存设计，可用于数十亿个小对象。袋鼠的目标是最大化命中率，同时最小化DRAM使用和闪存写入。像一些键值存储[27,50,52]一样，袋鼠采用了分层设计，在内存和闪存之间进行了分割。图3描述了袋鼠的两层设计:(i) KLog，一个日志结构的flash缓存;(ii) KSet，一个集合关联的flash缓存;以及位于袋鼠前面的DRAM缓存。

基本操作。袋鼠是分裂的DRAM和闪存。如图3a所示，1查找首先检查DRAM缓存，它是非常小的(小于1%的容量)。2如果没有找到请求的密钥，请再次检查KLog(≈容量的5%)。KLog维护一个DRAM索引来跟踪存储在flash上的循环日志中的对象。3如果在KLog的索引中没有找到key，请求检查KSet(≈容量的95%)。KSet没有DRAM指数;相反，袋鼠将请求的键散列以找到可能保存该对象的集合(即闪存上的LBA)。3a如果请求的键不在一个小的，每个设置的Bloom过滤器中，则请求失败。否则，对象可能在flash上，所以请求读取给定集合的LBA(s)，并扫描请求的键。

插入与读取的过程类似，如图3b所示。1新插入的数据首先写入DRAM缓存。这可能会将一些对象从DRAM缓存中挤出，在这里，它们要么是2a被KLog的预闪存承认策略删除，要么是2b被添加到KLog的DRAM索引，2c被添加到KLog的闪存日志(在DRAM缓存后，将许多插入批处理到单个闪存写中)。同样地，向KLog插入对象将把其他对象从KLog中推出去，这些对象要么被另一个准入策略删除3a，要么被插入到KSet中。插入到KSet的操作与传统缓存中的操作有些不同。对于任何从KLog移动到KSet的对象，袋鼠会将KLog中所有映射到同一集合到KSet的对象移动，不管它们在日志中的什么位置。这样做可以在KSet中平摊flash写操作，显著减少袋鼠的alwa。

设计的基本原理。袋鼠的效率和性能依赖于它的互补层。在较高的水平上，KSet最小化了DRAM的使用，KLog最小化了闪存的写入。与之前的集合关联缓存一样，KSet通过哈希对象的键来限制它们在闪存上可能的位置，从而消除了DRAM索引。但是仅KSet本身就承受了太多的写放大，因为每个小对象在被允许时都要写一个4 KB的页面。KLog解决了这个问题，它在KSet前面充当一个写效率高的暂存区，袋鼠用它来摊销KSet的写操作。

在这个基本的设计之上，袋鼠介绍了三种技术来最小化DRAM的使用，最小化闪存写，和减少缓存丢失。(i)袋鼠的KLog分区索引可以高效地找到KLog中映射到KSet中同一集合的所有对象，并被分割成许多独立的分区，以最小化DRAM的使用。(ii)袋鼠式的KLog和KSet之间的阈值准入策略，只有当KLog中至少有푛对象映射到同一个集合时，才允许对象进入KSet，总减少≥푛×。(iii)袋鼠的“RRIParoo”eviction通过近似RRIP[43]提高了KSet中的命中率，这是一种最先进的eviction策略，而每个对象只使用一个bit的DRAM。

理论基础。我们开发了袋鼠的基本设计的马尔可夫模型，包括阈值允许(详细描述在附录a中)。这个模型严格地证明了袋鼠可以大大减少总是比仅集设计，而没有任何增加漏检率。(事实上，RRIParoo没有被建模，它显著提高了miss ratio，对alwa的影响可以忽略不计。)

形式上，我们假设常用的独立参考模型[11,17,31,32,40,44]，其中对象被独立引用，每个对象的概率固定。然而，我们并不假设对象的流行度分布，所以定理1适用于任何流行度分布(uniform, Zipfian等)。假设KLog包含q个对象;KSet包含s个集合，每个集合包含w个对象;物体允许以푝的概率闪烁;并且对象只有在至少푛的新对象被插入时才被允许进入KSet。

定理1。袋鼠的应用级写放大是

4、设计与实现

介绍KLog和KSet中降低DRAM、flash写和漏写的技术。

4.1预flash进入KLog

像以前的闪存缓存一样，袋鼠可能不允许所有从DRAM缓存中逐出的对象[16,29,30,35 - 37]。它有一个预闪存接收策略，可以配置为随机接收对象到KLog的概率푝，减少袋鼠的写入速率成比例而不增加DRAM开销。与之前的设计相比，袋鼠可以允许更大比例的对象闪存比之前的闪存缓存，因为它的低alwa;事实上，除了非常低的编写预算，袋鼠几乎允许所有的对象KLog。

4.2 KLog

KLog的作用是在不需要太多DRAM的情况下最小化闪存缓存。为此，它必须支持三个主要操作:查找、插入和Enumerate-Set。Enumerate-Set允许KLog在KSet中找到映射到同一集合的所有对象。查找和插入操作类似于传统的日志结构缓存，具有近似索引。但是，底层的数据结构被设计成Enumerate-Set是有效的，并且几乎没有误报。

操作。和其他日志结构的缓存一样，KLog将对象大量写入flash上的循环缓冲区，并通过存储在DRAM中的索引跟踪对象。为了有效地支持Enumerate-Set, KLog的索引使用单独的链接实现为一个哈希表。每个索引条目包含一个用于在flash日志中定位对象的偏移量、一个标记(对象键的部分哈希值)、指向链中下一个条目的next-pointer(用于冲突解决)、强制策略元数据(在第4.4节中描述)和一个有效位。

查找:为了查找一个键(图4a)， 1 KLog通过计算KSet中的对象集来确定它属于哪个bucket。2个KLog遍历这个bucket中的索引项，忽略无效的项，直到标签匹配到键的哈希值为止。如果没有匹配的标记，KLog返回错误。3 KLog在日志的偏移处读取flash页面。在确认一个完整的键匹配之后，KLog返回数据并更新驱逐策略元数据。

插入:为了插入一个对象(图4b)， 1klog创建一个索引条目，将其添加到对应于KSet中键集的桶中，并将该对象追加到一个内存缓冲区中。闪存循环日志被分解成许多段，其中一个段一次被缓冲到DRAM中。一旦段缓冲区被填满，它就被写入flash。

Enumerate-Set: Enumerate-Set(푥)操作返回当前KLog中所有对象的列表，这些对象映射到KSet中与对象푥相同的集合。这个操作是有效的，因为按照构造，所有这些对象都将位于KLog索引的同一个桶中。也就是说，KLog有意利用其索引中的散列冲突，以便它可以通过迭代一个索引桶中的所有条目来枚举一个集合。

内部KLog结构。如图4所示，KLog内部结构为多个分区。每个分区是一个独立的日志结构的缓存，具有自己的闪存日志和DRAM索引。此外，每个分区的索引被分成多个表，每个表都是一个独立的哈希表。

这种分区结构减少了DRAM的使用，但在其他方面对KLog的操作改变很少。表和分区是从KSet中的对象集推断出来的。因此，同一集合中的所有对象都属于同一个分区、表和桶;操作在每个表中按照上面描述的方式工作。

减少KLog中DRAM的使用。表1将Kangaroo的每个对象的DRAM使用量与naïve日志结构的设计进行了对比，前者是独立缓存(“Naïve Log-Only”)，后者是KLog的替代(“Naïve Kangaroo”)。

flash偏移量必须足够大，以确定flash日志中哪个页面包含该对象，这需要log2(퐿표푔푆푖푧푒/4 KB)位。通过将日志分割成64个分区，KLog将퐿표푔푆푖푧푒减少64×，并节省6个b的指针。

标签大小决定了索引中的误报率;也就是说，更小的标签导致更高的读放大。KLog将索引分为2的20次方个表。因为表是从键推断出来的，所以一个表中的所有键有效地共享20 b的信息，KLog可以使用一个小得多的标记来实现与naïve设计相同的误报率。

KLog的结构也减少了下一个指针的大小。我们只需要知道分配给对象索引表的内存的偏移量。因此，不使用通用的内存指针，我们可以存储16b的偏移量，这允许每个表最多有2的16次方个条目。因此，KLog可以索引2的36次方个参数化的项目(12.5 TB的闪存和200 B对象)，可以通过将索引分割成更多的表来增加索引。

在使用LRU eviction的naïve缓存中，每个条目保持一个指向LRU列表中相邻条目的指针。这需要2·log2(퐿표푔푆푖푧푒/푂푏푗푒푐푡푆푖푧푒)位。相反，袋鼠的RRIParoo策略(第4.4节)是基于RRIP[43]的，在KLog中每个对象只需要3个b(在KSet中甚至更少)。

最后，KLog索引中的每个桶都需要一个指向链头的指针。在naïve日志中，这是一个64b指针。在KLog中，它是到表内存的16b偏移量。KLog在KSet中大约为每个集合分配一个桶。对于4kb的集合和200b的对象，每个对象的DRAM开销是3.1 B (Naïve)或0.8 B (KLog)每个对象。

总的来说，KLog的分区结构将每个对象的元数据从190b减少到48b，与naïve设计相比节省了3.96倍。与以前的索引设计相比，KLog的索引在每个对象上使用的DRAM比最先进的(在Flashield[35]中每个对象使用30b)略多一些，但它支持Enumerate-Set，而且误报更少。最重要的是，KLog只跟踪袋鼠中约5%的对象，所以索引的开销仅为每个对象3.2 b。加上KSet的DRAM开销，每个对象的总开销为7.0 b，比最先进的技术提高了4.3倍。

4.3 KLog→KSet:最小化flash写操作

写放大在KLog中不是一个重要的问题，因为它总是接近1×，并以大段写入数据，使dlwa最小化。然而，由于集合关联设计，KSet的写入放大有潜在的问题。袋鼠通过使用KLog来大大减少KSet中的alwa来解决这个问题:也就是说，通过在多个被允许的对象之间摊销KSet中的每个flash写操作。

将对象从KLog移动到KSet。后台线程在每个日志分区中保持一个空闲段。该线程以FIFO顺序从on-flash日志中刷新片段，将对象从KLog移动到KSet，如图4c所示。对于刷新段中的每个受害对象，线程1调用Enumerate-Set来查找KLog中应该随其移动的所有其他对象;2a如果没有足够的物体可以移动(见下文)，受害物体将被丢弃，或者，如果受欢迎，则重新被KLog接纳;2b否则，受害者对象和Enumerate-Set返回的所有其他对象将在一次闪存写操作中从KLog移动到KSet。

不是一次冲一个段，而是可以填满整个日志，然后完全冲掉。但这样一来，平均而言，原木只剩一半是空的。每次清洗一个段，可以使KLog的容量利用率保持在较高水平，经验值为80-95%。增量刷新还增加了KSet中平摊写的可能性，因为每个对象在KLog中花费的时间大约是它的两倍，因此在刷新时更有可能在同一集中找到另一个对象。

进入KSet的阈值。袋鼠平摊在KSet中通过将同一集合中的所有对象刷新到一起来写入，但不可避免地，当刷新时，某些对象将是它们集合中唯一的对象。将这些对象移动到KSet将导致与naïve集关联缓存一样的过度缓存。因此，袋鼠在KLog和KSet之间添加了一个准入策略，该策略设置了一个阈值푛，用于在KSet中写一个集合所需的对象。如果Enumerate-Set(푥)返回少于푛对象，则푥不允许KSet。

图5显示了阈值对alwa和KSet在不同对象大小下使用定理1的接纳概率的影响，KLog保持在缓存大小的5%。如果没有阈值(n = 1)，则没有对象被拒绝;但随着阈值的增加，更多的对象被拒绝(图5a)。此外，当对象较小时，KLog中容纳的对象越多，越小的对象被接纳的可能性就越大。阈值显著降低了总值(图5b)。重要的是，总比被拒绝的物体的比例要大，不像纯粹的概率承认。例如，对于100个B对象，阈值푛= 2可以容纳44.4%的对象，但其写速率仅为阈值푛= 1时的写速率的22.8%。

当从KLog移动到KSet时，为了避免对不满足阈值的流行对象的不必要的遗漏，袋鼠将在KLog中接收到命中的任何对象返回到日志的头部。这让袋鼠保留了流行的对象，而只略微增加了总体的写放大(由于KLog的最小alwa)。

4.4 KSet

KSet的作用是最小化缓存的总体DRAM开销。KSet采用了类似于CacheLib的小对象缓存[16]的集合关联缓存设计。这种设计将缓存分割成多个集合，每个集合包含多个对象;默认情况下，每个设置为4kb，匹配flash的读写粒度。KSet通过哈希键将一个对象映射为一个集合。由于每个对象被限制在少量的位置(即，一个集合)，所以不需要索引。相反，为了查找一个键，KSet只需要读取整个set flash并扫描它以找到请求的键。

为了减少不必要的闪存读取，KSet在DRAM中保留了一个小型Bloom过滤器，该过滤器由集合中的所有键构建。这些Bloom过滤器的大小可以达到约10%的假阳性率。每当写入一个集合时，Bloom过滤器就会被重建以反映集合的内容。

RRIParoo:没有DRAM索引的基于使用的驱逐。基于使用的驱逐策略可以显著提高失误率，有效地将缓存大小翻倍(或更多)，而无需实际添加任何资源[12,20,21,43,64]。不幸的是，在集合关联的flash缓存上实现这些策略是困难的，因为这些策略涉及每个对象的元数据，每次访问对象时都必须更新这些元数据。由于KSet没有存储元数据的DRAM索引，并且不能在不恶化alwa的情况下更新闪存元数据，因此如何实现基于使用的驱逐策略并不明显。由于这些原因，大多数flash缓存使用FIFO eviction[2,5,7,8,16,26,38,41,62,69]，这不会保持每个对象的状态。不幸的是，FIFO显著增加了遗漏率，因为流行对象不断地从缓存中循环出来。

袋鼠引入了RRIParoo，这是一种新技术，可以有效地支持基于使用的闪存缓存的驱逐策略。具体来说，RRIParoo实现了RRIP[43]，这是一种最先进的驱逐策略，最初是为处理器缓存提出的，而每个对象只使用≈1位的DRAM，并且没有任何额外的闪存写入。
背景:RRIP的工作原理。RRIP本质上是一种多比特时钟算法:RRIP将少量比特与每个对象相关联(袋鼠语为3比特)，这些比特代表了从接近重用(000)到远重用(111)的重用预测。物体只有到达很远的地方才会被驱逐。如果在必须驱逐某个对象时没有远对象，那么所有对象的预测都会增加，直到至少有一个远对象。对象被访问时提升到接近(000)。最后，RRIP在长时间(110)插入新对象，因此如果它们不再被访问，它们将很快被驱逐，但不会立即被驱逐。这个插入策略处理的扫描可能会降低LRU的性能。

RRIParoo的主要思想。在KSet中支持RRIP有两个想法。首先，RRIParoo不是在DRAM索引中跟踪所有RRIP的预测，而是将逐出元数据存储在闪存中，并在DRAM中只保留一小部分。其次，为了将DRAM元数据减少到一个位，我们观察到RRIP只在逐出时更新预测(向远处增加预测)和当一个对象被访问时(向附近提升)。我们的观点是，只要KSet跟踪哪些对象被访问，提升就可以推迟到驱逐时间，所以所有对闪光RRIParoo元数据的更新都只在驱逐时进行，无论如何，当集合被重写时。因此，由于KSet可以跟踪一个对象是否仅在DRAM中使用了单个位来访问，因此KSet以1 / 3的DRAM使用量达到了最先进的逐出策略的命中率(1 b对3 b)。

RRIParoo操作。RRIParoo分配足够的元数据，平均每个对象保持一个DRAM位元数据;例如，40b用于4kb的集合和100b的对象。对象使用与其在集合中的位置对应的位(例如，第푖个对象使用第푖位)，因此不需要索引。如果有太多的对象，RRIParoo不会跟踪最近的对象，因为它们最不可能被驱逐。

袋鼠也使用RRIP从KLog合并对象。在KLog中跟踪命中是很简单的，因为它已经有了一个DRAM索引。对象在长时间预测时(像往常一样)被插入到KLog中，它们的预测在每次后续访问时逐渐减少。然后，当将对象从KLog移动到KSet时，KSet将对象从近到远排序，并按照这个顺序填满集合，直到没有空间，打破了这种关系，取而代之的是KSet中已经存在的对象。

示例:图6说明了这个过程，显示了一个集合是如何用KSet重写的。1当KLog刷新一个包含对象F的段时，它映射到KSet中的一个集合。KLog在日志的其他地方找到第二个对象E，它也映射到这个集合。同时，该集合包含对象A, B, C和D与RRIP预测显示在flash上，并且B已经收到了打击，因为该集合最后被重写，由DRAM中的位表示。2 B收到打击后，我们将其RRIP预测提升到接近并清除DRAM中的位元。由于没有物体在远处，我们将所有物体的预测值增加3，因此物体A到达了远处。4最后，我们按照预测顺序合并DRAM和flash中的对象来填满这个集合，直到集合填满。集合现在包含B, F, D和C;A被驱逐，而E暂时留在KLog中，因为它的KLog段没有被刷新。

DRAM的使用。如表1所示，KSet需要每个对象最多4位的DRAM:一个用于RRIParoo，三个用于Bloom过滤器。再加上含有约5%物体的KLog的DRAM使用量，袋鼠每件物体需要≈7.0 b，比flashshield[35]少4.3×。此外，RRIParoo每个对象的1b内存开销可以通过在每个集合中跟踪更少的对象来降低。在极端情况下，这将导致驱逐策略衰减到FIFO，但它允许袋鼠适应使用更少的DRAM，如果需要的话。

6结论

袋鼠是一种用于数十亿个微小对象的闪存缓存，可以处理各种DRAM和闪存写预算。袋鼠利用了之前的日志结构和集合关联设计，以及新的技术，以实现这两种设计的最佳效果。使用Facebook和Twitter的跟踪数据进行的实验表明，DRAM的使用接近于之前最好的DRAM优化设计，闪存写入接近于之前最好的写优化设计，且漏写率比两者都好。袋鼠已经在CacheLib[16]中实现，并将开放源代码供社区使用。袋鼠表明，闪存缓存可以支持微小的对象，对DRAM的使用和写放大不利的工作负载，同时保持闪存的成本优势。