Flashield: a Hybrid Key-value Cache that Controls Flash Write Amplification

摘要：

随着每比特价格的下降，SSD越来越成为云应用数据库中热数据的默认存储介质。尽管SSD的每位价格低于10倍，并且与DRAM相比，它提供了足够的性能（当通过网络访问时），但闪存的耐用性限制了其在大量使用情况下的应用，例如键值缓存。这是因为键值缓存需要经常插入，更新和逐出小对象。这会导致闪存存储器的写入和擦除过多，从而大大缩短闪存的使用寿命。我们介绍Flashield，一种混合键值缓存，它使用DRAM作为“过滤器”来控制和限制对SSD的写入。Flashield执行轻量级机器学习准入控制，以预测哪些对象可能经常被读取而无需更新; 这些对象，哪些是存储在SSD上的主要候选者，顺序地以大块写入SSD。我们描述了Flashield的设计和实现，并使用广泛使用的缓存服务Memcachier对实际痕迹进行评估。我们为存储在闪存中的可变大小的对象设计了一种新颖的内存索引，在DRAM中每个对象只需要4个字节。与具有2.5倍或更高写入放大率的最先进系统相比，Flashield保持0.5倍的中值写入放大率（因为许多滤波对象根本不会写入闪存），而没有任何命中率损失或吞吐量。

背景：

与DRAM相比，Flash的每比特成本要低一个数量级。因此，对于需要高吞吐量和低延迟的热数据，它已经成为首选的存储介质。例如，谷歌[36]和Face-book[30]使用它存储照片，而像Lev-elDB[5]和RocksDB[9]这样的数据库部署在flash之上。

键值缓存是现代web规模应用程序中的一个重要层，几乎被所有web服务(包括Facebook、Twitter和Airbnb)广泛使用。大型web服务提供者运行自己的键值缓存集群，而较小的提供者通常使用缓存即服务的功能，如Amazon ElastiCache[1]和Memcachier[7]。

然而，由于它在写操作下的持久性有限，flash通常不用于像memcached[6]和Redis[8]这样的键值缓存。这就更加令人困惑了，因为这些缓存通常部署在一个专用的remote集群[31]或远程数据中心[1,7]中，或者使用客户端批处理[31]。因此，客户端观察到的访问时间可以是数百微秒到毫秒，因此与使用DRAM相比，flash只会增加一小部分延迟。

此外，由于缓存的性能主要是由它们提供的内存容量决定的[13,14]，而且SSD的每比特成本比DRAM低10多美元，与DRAM相比，flash有望带来显著的经济效益。表1显示，只有DRAM缓存和混合缓存(都具有4.25 TB的容量)之间的成本差异大于10。由于电力成本的原因，总拥有成本(TCO)的差异将会更大，因为flash消耗的电力比DRAM要少得多，而且可以在请求更少时关闭，而不需要重新预热缓存。

flash没有被广泛用作键值缓存的原因是缓存工作负载会很快耗尽闪存驱动器。这些工作负载通常由小对象组成，其中一些对象需要经常更新[10,31]。但是，ssd内的现代闪存芯片在其生命周期中只能在每个位置写入几千次。

此外，ssd还受到写放大(WA)的影响。也就是说，对于应用程序所写的每个字节(例如键值缓存)，在设备级别上还要向flash写入几个字节。WA的发生是因为flash页面被物理地分组在大块中。在覆盖页面之前，必须先删除它们，但这只能在块的粒度中完成。结果是，随着时间的推移，这些大块通常包含有效页面和无效页面的混合。在删除一个块之前，必须将任何有效的页面复制到其他flash块。这个垃圾收集过程创建了设备级写放大(DLWA)，它可以将写入flash的数据量增加几个数量级。现代ssd通过将许多flash块分割在一起(512 MB或更多)来提高顺序写性能(x2.1，[38])，从而加剧了这种情况。

为了最小化闪存写入的数量，SSD存储系统被限制为以大的连续块写入数据。这就强制了一种二阶写放大，这是缓存特有的，我们称之为缓存级写放大(CLWA)。当缓存被迫重新定位对象以避免DLWA时，就会发生CLWA。例如，当一个热对象占用了与许多准备清除的项相同的flash块时，缓存将面临一个选择。它可以用冷对象驱逐热对象，也可以将热对象重写为新的大型写入的一部分。因此，在现有的SSD缓存设计中，对象被多次重写到flash中。

为了解决这个问题，最新的RIPQ[38]系统建议，在flash中，通过将热对象和冷对象插入到不同的物理区域来存储它们。然而，flash上有效的数据放置并不足以对抗高CLWA，事实上，在某些情况下可能会进一步增加CLWA。例如，考虑一个应用程序，其中大量对象不常被访问(或频繁更新)。因为RIPQ将所有对象(热对象和冷对象)都包含在flash中，所以不经常访问的对象将被插入到“冷”插入点中，并且在再次访问之前，类型很容易被删除。因此，可以多次插入和删除这些对象。我们展示了在这样的工作负载下，RIPQ的CLWA高达150 (x5)，这意味着对于许多应用程序来说，它将很快耗尽flash设备。

随着时间的推移，闪速可靠性问题将变得更加严重，因为随着闪速密度的增加，其耐久性将继续降低[20]。特别是，下一代flash技术(QLC)可以比现有技术(TLC)少忍受30次写入[3,29,32]。

我们提出了一种新的混合键值缓存Flashield，它同时使用DRAM和ssd。我们的贡献是一种新的缓存策略，它显著延长了ssd的生命周期，通过控制和最小化对flash的写操作数量，它可以与DRAM相媲美。我们的主要观察是，并非所有进入缓存的对象都适合放置在SSD中。特别是，缓存应该避免将对象写入flash，这些对象将在不久的将来被更新或不会被读取。然而，当对象第一次进入缓存时，它不知道哪些对象适合SSD，哪些不适合。

因此，Flashield设计的一个关键思想是，插入到缓存中的对象总是要在DRAM中花费一段时间，在此期间，缓存知道它们是否适合闪存。如果他们真的证明自己是值得闪光的，Flashield会把他们变成闪光。如果没有，它们将永远不会移动到flash中，这将减少结果写入放大。由于flash层比DRAM大得多(例如，比DRAM大10个)，移动到flash中的对象在缓存中的平均停留时间要比那些留在DRAM中的对象长得多。

为了动态地确定哪些对象是适合在变化工作负载下使用flash的对象，我们使用基于机器学习的支持向量机(SVM)分类实现了允许控制算法。我们为缓存中的每个应用程序训练一个不同的分类器。为了训练分类器，我们设计了一种轻量级的采样技术，它可以随着时间的推移对对象进行一致采样，收集关于过去读取和更新次数的统计信息。分类器预测一个对象在未来是否会被读取n次以上而不被更新，用来确定它是否适合存储在flash上。我们称这种度量为闪光。

Flashield设计的第二个主要思想是，它为存储在flash上的可变长度对象提供了新颖的基于戏剧的查找索引，每个对象只需要不到4字节的DRAM。这比RIPQ小5个多，后者每个对象包含22个字节。由于flash层比DRAM的容量要大得多,一个na¨ıve查找索引的对象存储在闪存将消耗整个DRAM的能力。由于没有存储对象的位置及其对应的键，我们的索引消耗的内存相对较少。相反,为每一个对象存储在闪存上,该指数包含一个指针指向一个地区的flash对象存储,它存储一个额外的4位指定对象上的一个哈希函数关键指示对象的插入点在其地区闪光。索引利用bloom过滤器来指示对象是否驻留在flash上，而不需要在DRAM中存储完整的键。平均而言，Flashield的查找索引只需要从SSD读取1.03个数据就可以返回存储在其中的对象。

我们在C语言中实现Flashield，并在一组使用memcachier[7](一种流行的基于云的缓存服务)的实际应用程序上评估它的性能。我们表明，与RIPQ[38]相比，Flashield在保持相同的平均命中率的同时，将写入放大中值降低了5，平均降低了16，索引大小降低了5以上。我们表明，当对象从SSD读取时，Flashield的读取延迟和吞吐量接近SSD的延迟和吞吐量，当对象写到缓存或从DRAM读取时，它的延迟和吞吐量类似于基于戏剧的缓存，比如Memcached。

本文的主要贡献有三:

1. Flashield是第一个明确使用DRAM作为允许控制过滤器来决定将哪些对象插入flash的SSD存储系统。

2. Flashield的新颖闪存内存查找索引在DRAM中每个对象占用不到4个字节，同时又不牺牲闪存的写入和读取功能。

3.Flashield是第一个使用基于机器学习的承认控制算法和轻量级时间采样来预测哪些对象将是flash的良好候选对象的键值缓存。

由于新一代flash技术可以容忍更少的写操作[3,20,29,32]，我们对flash的动态允许控制可以扩展到缓存之外的其他系统，比如flash数据库和文件系统。

表一：组合容量为4.25 TB的混合缓存服务器的成本，与具有相同聚合容量的多个仅供dramonly缓存服务器的成本相比。SSD每比特的优势成本使得混合缓存服务器的总拥有成本降低了10。

图1:使用不同的写入大小连续写入4 TB后的设备级写入放大。

问题：

设计基于ssd的高速缓存需要解决两个控制问题。ssd的性能很差，并且很快就会耗尽，除非写操作很大而且是连续的。这与缓存工作负载的特性有关。缓存存储具有高度可变生存期的小对象;这使得缓存更倾向于使用小的随机I/O进行写操作，这将很快耗尽闪存驱动器。

SSD的生命周期由闪存设备制造商定义为，在设备产生不可纠正的读取错误(例如，遇到损坏位的概率为10 - 15)之前的时间量。SSD的生命周期取决于几个因素，包括写和擦除的数量(称为程序擦除周期)、SSD单元刷新周期之间的平均时间、单元技术、错误纠正代码等等。闪存电池的典型寿命是3-5年，平均每天写3-5次。

器件磨损的关键指标是写入放大。许多写模式迫使SSD对flash执行额外的写操作，以便重新组织数据。写入放大是指写入闪存芯片的字节数与应用程序发送到SSD的字节数之比。写入放大为1表示应用程序写入的每个字节导致一个字节写入到flash。写入放大10表示应用程序写入的每个字节会导致额外的9字节数据被重新组织并写入flash。

设备级的写放大：

设备级写放大(DLWA)是由SSD内部重组引起的写放大。DLWA的主要来源是flash重用单元的大小。Flash是读和写在小(˜8 KB)页面。然而，如果不先擦除，就不能重写页面。擦除发生在几页称为组块的粒度(˜256 KB)。当设备处于高利用率时，页面大小(或对象大小)与擦除单元大小之间的不匹配会导致写入放大。

例如，当应用程序覆盖页面的内容时，SSD将其写入一个不同的新块，并维护一个名为Flash Translation Layer (FTL)的重新定位映射。原始块还不能被删除，因为同一块中的其他页可能仍然是活动的。当闪存芯片完全被占用时，SSD必须删除块，以便为新写的页面腾出空间。如果没有一个块中所有的页面都被最近编写的数据所遍历，那么来自多个块的活动页面必须合并到一个flash块中。

这种整合或垃圾收集是DLWA的来源。如果一个设备的占用率达到90%，它的DLWA可能会非常高。图1显示了顺序写入和random写入下的DLWA。测量是在一台480 GB的英特尔535系列SSD上进行的，使用的是一种用于监控设备内部结构的智能系统。对于每个数据点，随机生成的4tb数据被随机或顺序地写入具有不同缓冲区大小的设备的原始逻辑块地址。具体来说，在随机工作负载中，逻辑块空间被划分为相邻的固定缓冲区大小的区域;每次写操作都会随机地用随机数据的完整缓冲区覆盖其中一个区域。顺序工作负载是循环的;区域在其逻辑块地址的顺序中被覆盖，根据需要循环回到设备的开始。对于这两种模式，我们通过将写限制在逻辑块地址的较小部分来改变设备空间的利用率。

结果表明，随机排列的1mb闪存写入体验接近8个DLWA。这是令人惊讶的，因为闪存擦除块小于1 MB。这种写放大的原因是因为ssd越来越优化高写带宽。SSD内的每个闪存包都是通过一个相对较慢的链接访问的(目前为50- 90mb /s);ssd在多个flash包中并行条带大顺序写，以获得高的写带宽。这有效地将多个包中的擦除块融合到一个逻辑擦除块中。一个1mb的随机写标记了一个大区域的页面已经准备好被擦除，但是这个区域是跨几个仍然包含大部分活动页面的擦除单元分段的。其他人也证实了这一效应。

有两种方法可以对抗这种影响。第一个是用bw的单位写其中B是擦除块的大小w是SSD条带写过的块数。我们的结果表明，为了消除DLWA，缓存必须以512 MB的块写入。第二种方法是按顺序编写设备，始终按fifo顺序编写。这是可行的，因为每个写的bw产生一个完全空的bw单元，即使写的单元小于bw。图1显示了8mb的顺序写入也消除了DLWA。

这意味着我们的缓存在如何向flash写入数据方面受到了极大的限制。为了最小化DLWA，缓存必须以大块或顺序写入对象。在这两种情况下，缓存几乎无法精确控制应该在flash上替换哪些对象。

缓存级写入放大：

在大段(连续的数据块)中写入闪存是对总体写入放大进行微型化的必要条件，但不是充分条件。大分段写入的主要副作用是缓存级写入放大(CLWA)。当从SSD中删除的对象被缓存清除策略重写到它时，就会发生CLWA。如果段的大小(MBs)明显大于对象的大小(字节或KBs)，则很难保证缓存中的高级对象总是与低级别对象或包含旧值的对象在物理上分开存储。因此，当从缓存中删除具有许多低级别对象的段时，它也可能无意中删除一些高级别对象。

表2给出了Memcachier(一个商业Memcached服务提供者)长达一周的跟踪的一般统计数据[13,14]，图2给出了在跟踪中编写的对象大小的分布。图中显示对象大小差异很大，而且通常非常小:写入缓存的对象的平均大小为257字节，80.67%的对象小于1 KB。因此，即使使用顺序写入的段大小为8mb(这是不会导致额外写入放大的最小段大小)，每个段平均也将包含32,000多个惟一对象。

此外，60.6%的写操作(和5.8%的所有请求)是未读的写操作，这意味着它们在被写之后永远不会被读，0.5%的请求是更新。未读写和更新都有助于写放大。理想情况下，未读的写不应该写入缓存。在更新的情况下，为了在对象更新之后回收该对象的空间，缓存需要擦除并重写该对象。

RIPQ[38]代表了将CLWA最小化的最新技术;它是一个基于ssd的照片缓存，通过插入在过去一起读取k次的对象来最小化CLWA。当对象第一次插入缓存时，它们被缓冲在内存中，并定期与其他读取相同次数的对象一起作为段移动到flash中。这个想法是，在过去被读取k次的对象可能在未来具有类似的清除级别。例如，一个读取过一次的对象与其他读取过一次的对象存储在同一段flash中。包含读取次数较少的对象的段将比读取次数较多的对象的段更快地被清除。

RIPQ适用于较大且不可变的照片，但它在web缓存工作负载中会失效，因为在web缓存工作负载中，值较小且更新更频繁。为了说明这一点，我们使用Memcachier跟踪模拟了RIPQ的CLWA (RIPQ实现是不可公开使用的)，使用一个带有8个队列的分段LRU。我们还用受害者缓存策略相比,SSD的natıve方法只是作为L2高速缓存(即。，从DRAM中移除的每个对象都写入SSD)。Facebook的图形数据存储TAO[11]使用了这种策略，它利用有限的flash作为存储在DRAM中的数据的受害者缓存。仿真为跟踪中的每个应用程序分配相同的内存，DRAM与SSD的比例为1:7。

结果如表3所示，虽然RIPQ对受害者缓存有了很大的改进，但它仍然从一个非常高的CLWA开始使用。请注意，受害者缓存将受到更大的总WA的影响，因为它还受到DLWA的影响(因为它没有在大的段中写入flash)。RIPQ患有CLWA有两个原因。首先，RIPQ没有允许策略，它将所有传入的对象都写入flash;甚至是未读的对象或快速更新的对象。其次，当某个对象的读取频率发生变化时，它会创建额外的写操作。例如，如果一个对象在写完之后的一段时间内被读了两次，那么它将与在flash上读了两次的其他对象分组。但是，如果它被读了5次以上，那么RIPQ需要重写它，将它与其他级别更高的对象分组。由于对象比段大小小得多，而且跟踪中写入的比例相对较高，所以RIPQ很难保证在同一时间读取的对象存储在同一段中。

这些结果提供了两条线索，说明缓存应该如何以不同的方式利用DRAM来最小化web缓存工作负载的CLWA。首先，并不是应用程序插入缓存的每个对象都适合存储在SSD上。例如，对象在第一次写入后不久就会更新，或者对象在将来被读取的可能性很低。然而，这些对象的出现在不同的应用程序中有很大的差异。例如，在Memcachier跟踪的一些应用程序中，超过一半的已写对象将不再读取，而在一些应用程序中，绝大多数对象将被多次读取，并且应该写入缓存。其次，由于段大小和对象大小之间的差异，很难保证被驱逐策略排序相似的对象将存储在SSD上物理上相邻的区域。

这两种观点都激发了Flashield，一个成功地在没有DWLA的情况下最小化CLWA的缓存。

设计：

Flashield的设计目标是最小化缓存级和设备级的写放大，同时保持正常的命中率。Flashield设计的关键观点是使用DRAM作为过滤器，它可以防止将对象移动到flash中，而flash很快就会被删除或更新，并保持高效的内存索引，从而保持低的写和读放大。

图3说明了Flashield中对象的生存期。对象总是首先写入DRAM。第一次读取对象之后，Flashield开始收集描述其性能的特性。这些包含关于对象何时以及多少次被读取和更新的信息。对象可以通过Flashield的清除算法从DRAM中清除。

Flashield会周期性地将一个由许多DRAM对象组成的段(如512 MB)移动到flash中。Flashield使用机器学习分类器根据对象的特征对其进行排序。如果一个对象通过了一个等级阈值，它将被认为是移动到flash的候选对象。然后根据他们的分数对flash的候选人进行排名，这决定了他们被Flashield移动到flash中的顺序。这一顺序非常重要，当有更多的华而不实的候选人，超过可以容纳在一个单一的部分。当对象被移动到flash后，它将在缓存中驻留相对较长的时间。一旦它的段按FIFO顺序从flash中删除，它就会被移出flash。此时，如果对象的回收优先级较低，那么它将被回收;如果对象的回收优先级较高，那么它将被重新插入DRAM。一旦对象被重新插入到DRAM中，它必须再次证明自己具有flash的价值，然后再将其重写到flash中。有关详细信息，请参见x4.3。

在Flashield中，DRAM有三个用途。首先，它被用作一个过滤器来决定应该将哪些对象插入SSD。其次，它存储用于在flash上查找和删除对象的元数据。第三，在对象转移到SSD之前，它充当对象的缓存层，并为不适合SSD的对象提供缓存层。

DRAM作为过滤器：

在Flashield中，DRAM是将物体移动到flash中的试验场。当对象首次被写入DRAM时，Flashield并不知道它们是否适合flash。此外，应用程序具有独特的工作负载，因此需要单独学习它们的访问模式。

判断哪些对象值得闪速的稻草人方法是根据简单的指标(如频率或频率)对它们进行排序，就像标准的缓存替换策略(如LRU或LFU)所做的那样。然而，很难为flash设置一个适用于所有应用程序的正弦阈值。例如，系统可以定义一个基于频率的阈值，要求对象在进入flash之前被读取多次。然而，对于某些应用程序，这种阈值被证明过于严格，因为访问模式很长，并且由于过早的清除而降低了命中率。对于其他应用程序，它也可能过于宽松，因为在这些应用程序中，对象将被不必要地写入flash。即使对于单个应用程序，这样的阈值也是一种启发式，必须手动调优(参见下面描述的示例和表4中描述的示例)。

机器学习不是使用一种放之四海而皆准的方法，而是可以作为一种动态学习方法，来了解哪些对象适合每个应用程序的flash。

Flashiness：

我们将flashiness定义为一个指标，它可以预测一个对象是否适合flash。flashiness得分高的对象是满足两个条件的对象。首先，它是一个在不久的将来将被访问n次的对象(其中n是一个可配置参数)。这保证了它不会被缓存的清除函数清除。其次，它需要在不久的将来是不可变的，因为更新SSD中的对象需要额外的写操作

系统可以使用阈值n(一个对象在未来被读取的次数)来表示写放大的敏感度。如果系统对写入放大非常敏感，它可以将n设置为一个相对较高的数字，这将确保Flashield只会将其预测将在未来多次读取的对象移动到flash中。另一方面，如果系统对命中率更敏感，则将n设置为一个较低的数字。此外，Flashield允许操作员对flash写速率设置一个固定的限制，以保持一定的目标生存期。

通过预测一个对象在不久的将来将被读取的次数(例如，一个小时)，以及省略预测在这个preiod期间将被更新的对象，可以捕获上述两个flash标准。Flashield通过收集两个特征(1)过去的读取次数和(2)过去的更新次数，使用支持向量机(SVM)的二元分类器来预测闪度。图4提供了与Memcachier跟踪不同应用程序的分类器的准确性，其值为变量n。准确度定义为，其中tp为真阳性，tn为真阴性，fp为假阳性，fn为假阴性。分类器使用一个小时的训练时间来预测一个对象在未来是否会被至少n次访问而不被更新。

由于不同的应用程序的工作负载不同，预测的准确性也不同(从75%到99%)。此外，随着n个折痕的增加，精度通常会降低。这是因为随着n的增加，分类器试图预测更罕见的事件，其中观察到的训练数据点更少。例如，在接下来的一个小时内，被阅读超过一次的对象比被阅读超过五次的对象要多。

要演示为什么机器学习比使用固定的阈值来确定flash的过去访问次数更有效，请考虑下面的示例。我们在跟踪的应用程序之间训练了一个简单的分类器，该分类器使用深度为1的决策树，利用单个特性(过去读取的次数)，尝试用n = 5预测闪度。表4给出了决策树根据其训练样本为每个应用程序选择的阈值，该阈值将提供最高的预测精度。结果表明，没有一个单一的静态阈值对所有应用程序都是最优的。这也表明很难预先确定这个阈值是多少。例如，对于应用程序d，过去仅发生两次读取就足以预测将来它将被读取5次或更多。

Flashiness设计的讨论：

我们尝试了几个与读取和更新的数量和频率相关的不同特性。我们发现，在预测和捕获读取和更新的过去信息时，唯一有效的特性是:(1)读取的过去次数和(2)更新的过去次数。

令我们惊讶的是，我们发现，在我们测量的所有应用程序中，与最近时间相关的特性(例如，两次读取之间的时间，上次读取之后的时间)对预测没有正面影响，而且事实上，在某些情况下，分类器的准确性降低了。这支持我们的设计选择，将flashiness度量(基于过去访问的数量和类型)与驱逐令策略(通常基于最近)解耦(例如，LRU或其衍生物之一，请参见x3.4)。

此外，我们还尝试了几种不同的分类算法。最初，我们尝试使用逻辑回归直接预测这个数字。我们在Memcachier trace上运行了这个分类器，发现预测非常不准确。尝试不同的特性和分类后,我们发现很难准确预测到底多少次访问一个对象将在未来,这就是为什么我们使用二进制分类、预测未来的读取次数是否超过n。我们也试着用一个不同的二元分类器,决策树,它提供了非常相似的支持向量机的精度。我们决定使用SVM，因为它提供了一个连续的分数，用来为对象提供一个全局的Flashiness等级。对于决策树，分数的范围仅限于叶子的数量。

DRAM作为Flash的索引：

与日志结构的合并树(LSM)不同，Flashield将索引存储在DRAM中(对于DRAM中的对象和flash中的对象)。这允许Flashield以更低的延迟服务请求，因为索引是从DRAM读取的。更重要的是，将索引存储在flash上需要LSMs在对象更新时不断更新索引，这将创建大量的写操作[24,27,39]。当索引在DRAM上时，更新它很简单。然而，由于Flashield也使用DRAM作为一个允许控制层，我们必须确保索引将在DRAM上占用最少的空间。

与Memcached类似，Flashield将索引存储在散列表中，以启用有效的查找。本机索引将包含存储在flash中的键的标识、值的位置以及它们在清除队列中的位置。然而，这样一个指数的成本将高得令人望而却步。如果我们把一个6结核病闪存设备平均对象大小257字节(等于平均对象大小Memcachier跟踪前20名的应用程序),为每一个对象存储一个散列的关键,避免碰撞至少需要8个字节,每个对象存储的确切位置是43位,并保持一个指向队列中的位置将4 - 8个字节。在DRAM上为每个对象存储17个字节将需要406gb的DRAM。这将占用(或超过)高端服务器的所有DRAM。例如，在RIPQ中，每个内存索引条目都是22字节。我们为可变大小的对象设计了一种新的内存查找索引，每个对象使用不到4个字节，不会引起额外的闪存写入放大。

身份的钥匙。Flashield没有在索引中存储键的标识，而是将它们作为对象元数据的一部分保存在flash设备中。为了在查找哈希表中识别哈希冲突，Flashield比较了flash中的键。为了限制键查找期间的flash读取次数并避免复杂的表扩展，Flashield使用了一个没有链的多选择哈希表。在查找过程中，将逐个使用预定义的散列函数，这样，如果没有找到键，就使用下一个散列函数。使用所有散列函数，但仍未找到密钥，Flashield返回一个误操作。类似地，如果在插入期间发生冲突，则使用下一个散列函数重新散列密钥，以将其映射到查找表中的另一个条目。如果使用了所有散列函数，并且仍然存在冲突，则将删除最后一个冲突对象，以便为新键腾出空间。

为了减少在出现哈希冲突时从flash中读取的多余数据，Flashield为每个段使用内存中的bloom过滤器，该过滤器指示键是否存储在该段中。我们决定为每个段使用一个bloom过滤器，而不是全局bloom过滤器，以消除bloom过滤器支持删除的需要(因为每个段都是不可变的)。我们使用bloom过滤器，假阳性率为1%。对于Memcachier跟踪，这将转换为平均每点击一次flash，就有1.03次对flash的访问，每个条目的额外内存开销为10位。

对象的位置。索引不直接存储SSD对象的位置，而是包含两个单独的字段:段号和预定义散列函数的ID。段号表示flash中存储对象的连续段。使用预定义的散列函数散列对象的键可以提供对象在段中的偏移量。使用哈希函数来指示段中的对象位置可能会降低闪存的利用率，因为它限制了在段中放置对象的可能位置的数量。注意，这些哈希函数与用于哈希表查找的哈希函数是正交的。我们选择使用16个预定义的哈希函数(即。由于增加了哈希函数的数量，使得flash的使用性能得到了显著的改善。我们将在x5.3中探讨flash的使用。注意，由于数据是按顺序写入flash的，因此8 MB或更大的段大小可以实现最小的DLWA。为了减少索引开销，我们使用512 MB的段。

拆迁政策。为了避免维护由双链点列表组成的完整回收队列的开销，Flashield使用时钟算法[16]，类似于其他内存键值缓存[18]。CLOCK近似于LRU策略，因此为了评估它的影响，我们在模拟中运行了Memcachier跟踪中的前5个应用程序，并比较了CLOCK和LRU之间的结果。结果表明，对于时钟时间戳，每个对象只保留2位，与LRU相比，平均命中率仅下降0.1%。

图5总结了Flashield的查找过程。首先对查找键进行散列，以在lookup散列表中找到对应的条目ID，该散列表提供了段ID。然后，Flashield在段的bloom过滤器中执行键查找。如果在bloom过滤器中找到键，Flashield将从flash上的段读取对象。由于bloom过滤器可能导致假阳性，如果从flash中读取的对象与正在查找的对象没有相同的键，那么将再次散列该键，Flashield将在查找散列表中再次查找该键。类似地，如果在bloom过滤器中没有找到键，则再次散列键，Flashield在lookup散列表中执行另一个查找。Flashield将尝试使用所有配置的哈希函数(默认为16)查找对象，直到找到对象为止。如果在所有尝试之后都没有找到该对象，则该对象在flash中不存在，Flashield返回一个miss。

图6总结了哈希表条目格式。索引包含一个额外的位(ghost)，它指示对象是否计划从flash中删除。我们在x4.3中描述了这个标志的用途。

实现：

本节介绍Flashield的实现。我们在C语言中从头开始实现Flashield，除了传输、分派、请求处理和DRAM对象的哈希表，这些都是从Memcached 1.4.15借来的。Flashield有四个主要功能:读取、写入、将数据移动到flash和删除。图7描述了Flashield架构的高级组件。它支持通用的Memcached协议，因此部署Memcached的应用程序可以透明地使用Flashield。

对于读取，Flashield首先检查DRAM对象的哈希表中是否存在对象，该对象基于memcached的哈希表。如果没有，它将使用一个单独的哈希表来检查对象是否仍然存在于flash中。如果对象存在于DRAM或flash中，Flashield将返回该对象，否则该请求将被视为一个错误。传入的写和更新总是首先存储在DRAM中。对于更新，更新后的对象存储在DRAM中，旧版本无效。Flashield总是在DRAM中为传入的写保持一个段大小的空闲空间。

Flashield使用大量可配置的工作线程并行处理客户机请求。为了在DRAM上保持足够的空闲空间，Flashield使用了一个专用的干净线程，它在后台工作，并且不在正常请求(读/写)处理的关键路径上。此外，Flashield让操作人员配置一个flash写限制，以确保一定的目标生存期。当DRAM上的空闲空间下降到段大小以下时，如果有足够多的对象达到了flash评分的阈值，并且没有达到flash写速率限制，那么清理器将它们复制到段缓冲区中。当缓冲区被填满时，清理器将段写入flash，然后释放对象在DRAM中占用的空间。根据对象的flashiness评分，将对象按顺序移动到flash。当SSD已满时，清洁器将根据FIFO顺序从flash中删除最后一个段。

Flashield对所有对象保持全局优先级，无论它们是存储在DRAM或flash中。基于这个全局优先级，对象被从Flashield中驱逐。默认情况下，优先级是使用时钟的LRU的近似值。如果下一个被驱逐的对象是在DRAM中，Flashield只会驱逐它。如果下一个要清除的对象在flash中，Flashield将它标记为ghost对象，当它的段从flash中删除时，它将被清除。注意，将数据从DRAM移动到flash是与清除解耦的。它们是并行进行的，并使用不同的度量对对象进行排序。在flash和DRAM之间移动的对象总是保持它们的全局优先级排序。当DRAM中没有足够的对象达到flash评分的阈值，或者flash写入速度达到极限时，清理器将从DRAM中删除条目，以保持足够的空闲空间。

本节的其余部分将详细描述Flashield如何将对象移动到flash中，以及Flashield分类器和清除算法的实现。

向Flash写入对象：

Flashield在DRAM中构建了一个flash绑定段，通过一个接一个地为段中的对象寻找空间。预先确定的哈希函数的输出位为每个对象在段中提供不同的可能插入点。Flashield首先根据对象的flashiness组合一组需要移动到flash的对象。然后，它尝试根据对象的大小从这个组中插入对象。首先是大对象，因为它们比小对象需要更多的连续空间。在这个过程中，一些对象在段中没有可用的空间。Flashield跳过这些对象，并试图在下次创建新段时再次插入它们。我们在x 5.3中评估结果段的利用率。

分类器的实现：

Flashield的flashiness评分是根据每个对象的两个特性计算的。由于这些特性依赖于跨多个对象访问的信息，因此对象的特性仅在至少读取一次对象之后生成。如果一个对象从未被读取过，那么它的flashiness值将自动等于零。

Flashield定期为每个应用程序训练一个单独的分类器。对于我们使用的商业跟踪，我们发现在跟踪开始时一个小时的培训时间就足够了。训练分类器的原始方法是在每次访问DRAM时更新特性。但是，这种方法可能会过度使用某些对象，从而导致分类器不平衡。例如，如果一个小的对象集占所有访问的99%，那么将为这些对象创建多个特性集，并且flash估计将偏向于流行对象。

为了解决这个问题，我们实现了一种抽样技术，该技术为每个对象生成一个单独的抽样，在训练期间对其所有访问进行统一选择。Flashield没有在每次对象访问时更新特性，而是只以1n的概率进行更新，其中n是到目前为止读取和更新对象的次数。

要演示这种抽样技术，请考虑下面的示例。假设一个对象是第一次写的，然后读取。其特征向量为:1;0(过去的读取次数，过去的更新次数)。由于读取和更新的次数等于1，因此第一次读取生成的特征向量将是我们用于训练的特征，概率为1。更新对象时(特征向量为:1;1)， Flashield保留第二组特性的概率为12，因为读取和更新的次数等于2。这等于从第一次或第二次访问中均匀采样特性。每次后续访问的采样概率都是1n，之前访问的采样概率也是相同的。

在收集了一个小时的样本后，我们测量了在接下来的一个小时内每个物体被击中的次数。这个数字作为训练的目标函数。经过这两个阶段后，Flashield使用这些训练样本和标签训练分类器。

Eviction：

Flashield使用时钟算法对要驱逐的对象进行排序。每个对象的哈希表条目中只有两个表示优先级的时钟位，而不是保持精确的优先级排序。为了近似LRU，当读取对象时，它的位都设置为1。MFU(最常用)的近似方法是每次读取时将位增加1。

当set操作将对象插入缓存时，可能会触发驱逐。在清除时，Flashield循环遍历索引中的每个对象条目，将其时钟值递减1。当它到达一个时钟值为零的条目时，它停止行走。这个物体是choo -sen作为下一个被驱逐的受害者。如果受害者对象在DRAM中，那么它的空间将被释放，并且可以为即将到来的值重用。如果在释放受害者之后有足够的空间，驱逐就会停止，否则这个过程会根据需要重复。如果对象在flash中，Flashield不能立即从flash中删除它，因为对SSD的细粒度写入会导致高DLWA。相反，条目被标记为一个ghost对象，它充当flash清理过程的提示。稍后，当对象所在的on-flash段即将被覆盖时，ghost对象将不会被预先服务，从而有效地将存储释放出来，作为批量flash清理过程的一部分。即便如此，如果ghost对象是与特定键关联的最当前值，那么它仍然是可访问的，只要flash清理过程还没有覆盖它在flash上的段。在某种意义上，ghost对象接近全局清除级别的底部(包括两个flash)和DRAM);非鬼对象，被认为是在全球驱逐排名的顶端，我们称之为热对象。

Flashield在分配一个新段并准备将其从DRAM移动到flash时触发段删除，前提是flash已满且未超过配置的写速率限制。清洁器按FIFO顺序从flash中删除最后一个段。在段擦除期间，它的ghost对象将从缓存中删除，而热对象将重新插入DRAM。图8总结了这个过程。

将对象从flash移动回DRAM将触发驱逐;如果不选中此选项，将会产生两个问题。首先，如果过早地将对象从DRAM中删除，而没有证明它们是华丽的，那么命中率可能会受到影响。其次，如果清除了太多花哨的对象，就会导致写入放大。Flashield通过一个热数据阈值(HDT)来防止这种情况发生，它确保在有限的时间内可以丢弃足够多的对象，从而在flash上释放足够的空间，而不会对清除造成太大的压力。在没有HDT的情况下，清理器可以重新分配低级别对象，以牺牲驻留在DRAM中的高级别对象为代价。

HDT定义为DRAM + SSD hot，其中DRAM是DRAM中可用的对象存储，SSD是SSD的总大小，hot是分配给热对象的SSD的百分比。Flashield努力维护HDT，即使传入的对象在DRAM中有足够的空间。为此，每当热数据量超过HDT时，Flashield就会触发一个新的清除，如果其他对象驻留在flash上，则会将其标记为ghost。默认情况下，hot是70%，所以flash上大约30%的对象是ghost对象。

Ghost对象被标记为Ghost之后仍然可以访问，因为它们不会立即从flash中删除。如果访问了ghost对象，它就不再被认为是ghost, Flashield将其标记为热对象(ghost位设置为零)。由于Flashield总是维护HDT，所以将ghost对象从ghost切换到hot可能会触发驱逐。为了避免不必要的DRAM清除，在这种情况下，Flashield不会从DRAM中驱逐低等级的对象，而只是遍历flash对象来将对象标记为幽灵。

尽管清理器负责在DRAM中维护足够的空闲空间(通过向flash分配新段)，但在极少数情况下，DRAM可能没有足够的空闲空间来容纳传入的写。当flash写入速率达到极限时，或者当flash -ss得分超过阈值的对象数量不足以形成一个新的段时，可能会发生这种情况。在这种情况下，Flashield将触发一个特殊的清除，它将只遍历DRAM对象，并将从DRAM中驱逐低级别对象以容纳传入的写。

图9展示了一个set操作向缓存插入新对象时Flashield的流程图。

Flashield中的删除操作不会引起对flash的写操作。如果对象在DRAM中，则只删除它。如果它驻留在flash中，则不会立即从flash中删除它，因为这会导致DLWA。它也没有被标记为ghost，因为ghost对象仍然可以被访问。相反，Flashield删除对象的查找条目。在段删除期间，清理过程通过将其对应的查找条目中的段ID与被删除的段ID进行比较来标识已删除的对象，并且不会保存它们。在此基础上，Flashield将更新操作处理为删除操作，然后进行新的插入。

Evaluation：

在本节中，我们评估了与现有系统相比，Flashield的端到端性能。不幸的是，据我们所知，没有大规模键值缓存的公共踪迹。我们使用Memcachier提供的整个星期的实际跟踪，Memcachier是一个广泛使用的memcached服务提供商。由于Memcachier跟踪在请求率方面相当稀疏，所以我们运行了一组合成的微基准测试来强调系统的性能，以度量它的吞吐量和延迟。

端到端性能：

通过从Memcachier跟踪中重新运行实际应用程序，我们比较了Flashield到RIPQ和受害者缓存策略的端到端命中率和写入放大。由于RIPQ没有公开的[38]实现，我们不得不运行并比较这三个系统的仿真。每个策略都使用Memcachier跟踪中分配的相同数量的内存，DRAM和SSD的比例为1:7。我们运行Flashield，其阈值为一个未来读取。换句话说，预测未来至少有一次读取的对象被认为是足够闪速的。由于Flashield为每个应用程序使用一个单独的SVM，我们比较了单个应用程序的结果。要用8个插入点运行RIPQ，并且在flash上至少运行8个不同的段，我们只运行Memcachier分配了足够内存的应用程序。

表5给出了Flashield和RIPQ的比较结果。结果表明，Flashield的CLWA明显低于RIPQ和受害者缓存。Flashield的CLWA中值为0.54,RIPQ中值为2.85，而受害者缓存的中值为3.67。即使Flashield对将来读取的flash使用一个较低的阈值，它仍然阻止了大量不适合SSD的写操作被写入到flash中。Flashield和RIPQ有着几乎相同的命中率。两者的命中率都比vic-tim缓存低，但是受害者缓存的CLWA要高得多(因为它不处理DLWA，所以总体写放大也要高得多)。

表6比较了不同闪度预判阈值下的Flashield。不同应用的结果不同，一般来说，阈值越高，CLWA越低，命中率越低。注意，在一些应用程序中，例如在应用程序a中，这种权衡并不适用，因为我们在每个应用程序上分别训练分类器，并且每个应用程序的执行方式不同。

表7描述了在保持每个应用程序的内存总量不变的情况下，改变DRAM和SSD的比例时的结果。结果表明，如果我们过多地减少DRAM的数量，系统的命中率就会下降。这是因为，当DRAM较低时，对象没有足够的时间证明自己足够华丽，可以在从DRAM中移除之前移动到SSD。注意，我们在这些运行中使用了更小的段大小，以便能够以1:15的DRAM比例显示结果。

Microbenchmarks：

我们使用微基准来驱动Flashield的实现，以强调系统的性能，并使用Memcached来减少它的延迟和吞吐量。我们使用4核3.4 GHz Intel Xeon E3-1230 v5(共8个硬件线程)，32 GB的DDR4 DRAM (2133 MHz)和480 GB Intel 535系列SSD。所有实验都是使用Debian 8.4 AMD64上的标准内核、编译器和库编译和运行的。微基准测试请求基于随机键，平均对象大小为257字节，这是Memcachier跟踪中前20个应用程序的平均对象大小。我们禁用了操作系统缓冲区缓存，以确保SSD读取被直接路由到SSD驱动器。由于SSD和DRAM的性能相差一个数量级，我们分别测量了SSD和DRAM命中。最后，我们测量了Memcached 1.4.15的延迟和吞吐量作为基线。

表8给出了microbenchmark实验的吞吐量和延迟。注意，对于Memcachier和Facebook, Memcached都不是CPU绑定的，而是内存容量绑定的[14,15]。Flashield中DRAM hits的延迟和吞吐量与Memcached的延迟和吞吐量非常相似。虽然SSD点击率的平均延迟显著高于DRAM，但是当在网络上部署时，它们的延迟变得相似(网络访问时间通常为100秒或更长)。Flashield的miss延时与DRAM hits的延时相似，因为Flashield的所有查找索引都存储在DRAM中，只有当内存中的bloom过滤器之一返回false positive时，Flashield才需要在miss中访问flash。Flashield的写吞吐量和延迟与Memcached相同，因为写总是进入Flashield的DRAM。

Utilization on Flash：

当将数据从DRAM移动到flash时，Flashield试图使用预定义的哈希函数为flash段中不同可能的插入点分配对象空间。如果没有插入点引用对象的足够连续自由空间，Flashield将跳过对象，并尝试在下一个段分配期间插入它。

图10描述了Flashield的flash分配算法的使用情况。为了测量内存利用率，我们在Memcachier跟踪上运行Flashield分配算法，在512 MB的段大小上使用不同数量的哈希函数，分配贪婪地试图分配空间给更多的数据，并测量结果的利用率。注意，当段的利用率达到60%左右时，段的利用率曲线梯度下降，因为当Flashield试图分配对象时，段中与其他前辅助对象发生碰撞的概率更高。使用16个散列函数，大约需要1gb的对象才能达到99%的利用率，平均每个对象需要散列8.2次，直到找到一个具有足够空间的插入点。

总结：

SSD在采用键值缓存用例方面面临着独特的挑战，因为较小的对象大小和频繁的清除和更新速度会导致过多的写操作和擦除操作。Flashield是第一个使用DRAM作为对象筛选器的键值缓存，这些对象不适合SSD。Flashield使用轻量级机器学习配置对象，并动态学习和预测哪些对象最适合flash。它为可变大小的对象引入了一种新的内存索引，每个对象的开销小于4字节，同时又不牺牲闪存的写和读放大。

本文的思想可以扩展到其他用例。例如，非易失性内存(NVM)也面临持久性方面的挑战，特别是在用作DRAM的替代品时，可能还需要一个允许策略[17]。这在多层存储系统中也是如此，在多层存储系统中，更便宜的存储层以性能下降为代价提供更多的容量。最后，随着flash的密度增加(其容忍写操作的能力降低)，如何处理flash的持久性成为一个越来越紧迫的问题。

Flashield: a Hybrid Key-value Cache that Controls Flash Write Amplification