摘要

我们介绍WiscKey ，这是一个基于LSMtree的持久化键值存储引擎，采用Key-Value分离的数据布局，以最大程度地减少I / O放大。WiscKey的设计是针对SSD的高度优化，充分利用了设备的顺序和随机性能特征。我们通过微基准测试和YCSB工作负载展示了WiscKey的优势。微基准结果表明WiscKey在loading database场景下是LevelDB的2.5X -11X和在随机查询场景下是LevelDB的1.6X -14X。在所有六个YCSB工作负载中，WiscKey比LevelDB和RocksDB都快。

1引言

持久键值存储在各种现代数据密集型应用程序中扮演关键角色，包括网页索引[16，48]，电子商务[24]，重复数据删除[7 ，22]，图片库[12]，云数据[32]，社会网络[9，25，51]，在线游戏[23]，消息[1 ，29]，软件库[2]和广告[20]。键值存储提供有效的插入，点查找和范围查询，可作为这一组不断增长的重要应用程序的基础。

对于写密集型工作负载，基于日志结构的合并树（LSM-tree）[43]的键值存储已成为最新技术。建立在LSM树上的各种分布式和本地存储引擎广泛部署在大规模生产环境中，例如Google的BigTable[16]和LevelDB[48]，Facebook的Cassandra[33 ]，HBase[29]和RocksDB[25]， Yahoo!的PNUTS [20]和Basho的Riak[4]。与其他索引结构（例如B树）相比，LSM树的主要优点是它们为写入保留顺序访问模式。

B树上的小更新可能涉及许多随机写入，因此在固态存储设备或硬盘驱动器上效率不高。为了提供高写入性能，LSM树将批处理键-值对并顺序写入。随后能够高效率地查找（对于单一键以及范围查询），LSM-树木连续读取，排序，并在后台写入键-值对，因此保持以排序的顺序的键和值。其结果是，在key的整个生命周期相同的数据被读出和写入多次; 如我们稍后（§2），此I / O扩增在典型LSM-树木可以达到的放大因子是50倍或更高[39，54]。

基于LSM的技术的成功与其在经典硬盘驱动器（HDD）上的使用紧密相关。在HHD硬盘上，随机I /O比顺序IO慢100倍[43]。因此，执行额外的顺序读和写操作以连续地对键进行排序并实现有效的查找是一个很好的权衡。

但是，存储格局正在快速变化，在许多重要的用例中，现代固态存储设备（SSD）都在取代HDD。与HDD相比，SSD在性能和可靠性方面有根本不同。在考虑键值存储系统设计时，我们认为以下三个差异至关重要。

首先，随机性能和顺序性能之间的差异不如硬盘驱动器大。因此LSM树执行大量顺序I / O以减少以后的随机I / O可能会造成不必要地带宽浪费。其次，SSD具有高度的内部并行性。构建在SSD之上的LSM tree必须精心设计以充分利用它的并行优势[53]。第三，固态硬盘可反复写入[34，40]; LSM tree中很高写放大会大大缩短器件寿命。正如我们将要示出了在论文（§ 4），这些因素的组合大大影响了SSD上LSM-树的性能，导致吞吐量下降90％，写入负载因数超过10. 虽然与HDD相比，在SSD下 LSM tree确实可以提高性能，而使用当前的LSM tree技术，SSD的真正潜力在很大程度上无法实现。

在本文中，我们介绍了WiscKey ，这是一种基于SSD的持久键值存储，它从流行的LSMtree实现LevelDB派生而来。WiscKey背后的核心思想是键值分离[42]；LSM树中只保留键的排序，而Value则存储在单独的日志中。换句话说，我们将WiscKey中的Key排序和垃圾回收解耦，而LevelDB将它们捆绑在一起。这个简单的技术可以通过避免在Key排序过程中Value的移动显著减少写放大。此外，LSM树的大小显着减小，从而导致更少的磁盘读取以及更好的缓存。WiscKey保留了LSMtree技术的优点，包括出色的插入和查找性能，但没有过多的I / O放大。

将键与值分开会带来许多挑战和优化机会。首先，范围查询（扫描）性能可能会受到影响，因为值不再按排序顺序存储。WiscKey通过使用SSD设备高效的内部并行性解决了这一难题。其次，WiscKey需要垃圾回收来回收无效值占用的磁盘空间。WiscKey提出了一个在线且轻量级的垃圾收集器，该垃圾收集器仅涉及顺序I/O，并且对前台工作负载的影响最小。第三，分离键和值给崩溃一致性带来了挑战性；WiscKey利用现代文件系统中一个有趣的属性，该属性不会在崩溃时添加垃圾数据。WiscKey提供与现代基于LSM的系统相同的一致性保证的同时，优化了性能。

我们将WiscKey与LevelDB[48]和RocksDB[25]（两种流行的LSMtree键值存储）的性能进行比较。对于大多数工作负载，WiscKey的性能要好得多。借助LevelDB自己的微基准测试，根据键值对的大小，WiscKey比LevelDB快2.5X–111X。在随机查找中，WiscKey速度是LevelDB的1.6X-14X。WiscKey的性能并不总是比标准LSM树好。如果以随机顺序写入较小的值，并且按顺序查询较大的数据集，则WiscKey的性能将比LevelDB差。但是，此工作负载不能反映实际的用例（主要使用较短范围的查询），并且可以通过日志重组来改善。在反映实际使用情况的YCSB宏基准[ 21 ]下，WiscKey在所有六个YCSB工作负载中都比LevelDB和RocksDB都快，并且遵循类似于负载和随机查找微基准的趋势。

本文的其余部分安排如下。我们首先在第二节描述部分的背景和动机。第3节说明WiscKey的设计，第4节分析其性能。我们将在第5节中简要描述相关工作，并在第6节中进行总结。

2背景与动机

在本节中，我们首先描述日志结构合并树（LSM-tree）的概念。然后，我们解释LevelDB的设计，LevelDB是基于LSM-tree技术的流行键值存储。我们分析LevelDB的读写放大。最后我们描述了现代存储硬件的特性。

2.1日志结构的合并树

LSM树是一种持久性结构，可为具有很高的插入和删除率的键值存储提供有效的索引[43]。它将数据写入延迟并分批处理成大块，以使用硬盘驱动器的高顺序带宽。由于随机写入比硬盘驱动器上的顺序写入慢将近两个数量级，因此LSM树比需要随机访问的传统B树提供更好的写入性能。

LSM树由大小从C0到Ck呈指数增长的许多组件组成，如图1所示。C0组件是驻留内存的就地更新排序树，而其他组件C1至Ck是驻留磁盘的Append-only B树。

LSM-树中的写入期间，插入的键值对被写入到磁盘上的顺序日志文件，以使在crash情况下恢复。然后，将键-值对添加到存储器Ç0，这是通过键排序; C0允许高效查找和扫描最近插入的键值对。一旦C0达到其大小限制，它将以与合并排序类似的方式与磁盘C1合并。此过程称为flush。新合并的树将顺序写入磁盘，从而替换旧版本的C1 。当每个Ci达到其大小限制时，磁盘上的组件也会发生Compaction（即合并排序）。注意，Compaction仅在相邻级别（Ci和Ci + 1）之间执行，并且它们可以在后台异步执行。

为了提供查找操作，LSM树可能需要搜索多个组件。请注意，C0包含最新数据，其后是C1 ，依此类推。因此，要检索键值对，LSM树以级联的方式从C0开始搜索组件，直到它在最小的组件Ci中找到所需的数据为止。与B树相比，LSM树可能需要多次读取才能进行点查找。因此，当插入比查找更常见时，LSM树最有用[43]。

2.2 LevelDB

LevelDB是受BigTable[16，48]启发的基于LSM树的广泛使用的键值存储。LevelDB支持范围查询，快照和其他在现代应用程序中有用的功能。在本节中，我们简要描述LevelDB的核心设计。

LevelDB的总体架构如图1所示。LevelDB的主数据结构包括一个磁盘日志文件（WAL），两个内存排序存储器skiplists（memTable和immutable memTable ），和七个水平（L 0到L 6 ）的持久化的排序字符串表（SSTable ）文件。LevelDB最初将插入的键值对存储在日志文件中，并在内存中存储内存表。一旦内存表已满，LevelDB就会切换到新的内存表和日志文件，以处理来自用户的进一步插入。在后台，将先前的内存表转换为不可变的内存表，然后flush线程将其刷新到磁盘，从而在Levele 0（L 0 ）生成一个新的SSTable文件（通常约为2 MB）；先前的日志文件将被丢弃。

在每个Level的所有文件的大小是有上限的，并按照10倍的因子逐级放大。例如，在L 1所有文件的大小限制是10 MB，而L 2为100 MB。为了保持大小限制，一旦级别L i的总大小超过其限制，Compaction线程将从L i中选择一个文件，与L i + 1的所有重叠文件合并排序，并生成新的L i + 1  SSTable文件。Compaction线程持续运行，直到所有Level都在其Size限制内。另外，在Compaction期间，LevelDB确保除L 0外，特定级别的所有文件在其键范围内不重叠；L 0文件中的键可以相互重叠，因为它们是直接从memtable中flush下来的。

为了进行查找操作，LevelDB首先搜索内存表，然后搜索不可变的内存表，然后依次搜索文件L 0至L 6 。定位随机key所需的文件搜索次数受最大级别数的限制，因为除了L 0以外，单个Level内文件之间的key不会重叠。由于L 0中的文件可以包含重叠key，因此查找可以搜索L 0中的多个文件。为了避免大量查找带来的延迟，如果L 0文件的数量超过八个LevelDB减慢写入流量，等待Compaction线程把一些文件从L0合并到L 1 。

2.3写和读放大

写和读放大是LSM树（例如LevelDB）中的主要问题。写（读）放大被定义为写入（读取）底层存储设备的数据量与用户请求的数据量之间的比率。在本节中，我们将分析LevelDB中的写入和读取放大。

为了实现大多数顺序的磁盘访问，LevelDB会写入比必要数量更多的数据（尽管仍然是顺序的），即LevelDB具有较高的写放大率。由于Li大小Li-1的10倍，当Compaction线程从Li-1到Li压缩过程中，最坏的情况下LevelDB可以从Li读取多达10个文件（这个地方论文表述有问题，应该是10倍的文件数量，而不是10 files），写排序后将这些文件返回给Li 。因此，跨两个Level移动文件的写放大可以达到10。对于大型数据集，由于任何新生成的表文件最终都可以通过一系列压缩步骤最终从L0迁移到L6 ，因此写放大可能会超过50（L1至L6之间的每个间隙为10）。

由于设计中的取舍，读取放大一直是LSM树的主要问题。LevelDB的读放大有两个来源。首先，要查找键值对，LevelDB可能需要检查多个Level。在最坏的情况下，LevelDB需要检查L0的八个文件，其余六个Level每个检查一个文件：总共14个文件。其次，要在SSTable文件中查找键值对，LevelDB需要读取文件中的多个元数据块。具体而言，实际读取的数据量由（索引块+布隆过滤器块+数据块）给出。例如，要查找1 KB的键值对，LevelDB需要读取16 KB的索引块，4 KB的布隆过滤器块和4 KB的数据块。总共24 KB。因此，考虑最坏情况下的14个SSTable文件，LevelDB的读取放大率为24 X 14 =336。较小的键值对将导致更高的读取放大率。

为了测量实际中LevelDB的放大率，我们执行以下实验。我们首先加载具有1-KB键值对的数据库，然后从数据库中查找100,000个条目；我们为初始负载使用两种不同的数据库大小，并从均匀分布中随机选择key。

图2显示了在加载阶段的写放大和在查找阶段的读放大。对于1GB数据库，写放大为3.1，而对于100GB数据库，写放大增加到14。读取放大遵循相同的趋势：1-GB数据库为8.2，100GB数据库为327。写放大随数据库大小增加而增加的原因很简单。随着将更多数据插入数据库，键值对将更有可能沿着层次进一步传播。换句话说，从低级别压缩到高级别时，LevelDB将多次写入数据。

但是，写放大不会达到先前预测的最坏情况，因为级别之间合并的文件平均数量通常小于最坏情况10。最坏情况是，读放大也随数据集大小而增加，因为对于小型数据库，所有索引SSTable文件中的块和Bloom筛选器可以缓存在内存中。但是，对于大型数据库，每次查找都可能会触摸不同的SSTable文件，从而付出了每次读取索引块和Bloom过滤器的代价。

应该注意的是，高读写放大是对硬盘驱动器的合理权衡。作为一个示例，对于给定一个具有10毫秒的寻道等待100-MB /秒的吞吐量的硬盘驱动器，随机访问1KB大小的数据块所需的大致时间是10毫秒，而顺序读取同样的块为耗时约10 μs,随机和顺序延迟比率为1000：1。因此，与需要随机写入的数据结构（如B树）相比，写入放大率小于1000的顺序写方案（LSMtree）在硬盘上的速度会更快[43，49]。另一方面，LSM树的读放大仍然与B树相当。例如，考虑一个高度为5且块大小为4 KB的B树，对1 KB键值对进行随机查找将需要访问6个块，从而导致读取放大为24。

2.4快速存储硬件

许多现代服务器都采用SSD设备来实现高性能。类似硬盘驱动器，由于SSD独特的擦除-写周期和昂贵的垃圾收集，随机写入在固态盘[10 ，31 ，34，40]上并不友好。尽管SSD设备的初始随机写入性能良好，但是在使用保留的块后，性能可能会大大下降。因此避免随机写入的LSM树特性在本质上适合SSD。许多SSD优化键值存储基于LSM tree[25，50，53，54]。

但是，与硬盘驱动器不同，随机读取（相对于顺序读取）的相对性能在SSD上要好得多。此外，当在SSD中同时发出随机读取时，总吞吐量可以与某些工作负载的顺序吞吐量相匹配[17]。例如，图3显示了规格500 GB Samsung 840 EVO SSD针对各种请求大小的顺序和随机读取性能。对于单个线程的随机读取，吞吐量随请求大小而增加，在256 KB时达到顺序吞吐量的一半。通过32个线程的并发随机读取，当大小大于16 KB时，总随机吞吐量与顺序吞吐量匹配。对于更高端的SSD，并发随机读取与顺序读取之间的差距要小得多[3，39]。

如本节所示，LSM树具有较高的读写放大率，这对于硬盘驱动器是可以接受的。在高性能SSD上使用LSM树可能会浪费过多的写入和读取操作，从而浪费大量设备带宽。在本文中，我们的目标是提高SSD设备上LSM树的性能，以有效利用设备带宽。

3 WiscKey

上一节解释了LSM树如何通过增加I/O放大来维护顺序I/O访问。尽管对于传统硬盘来说，在顺序I/O访问和I/O放大之间进行折衷是合理的，但对于使用SSD的现代硬件，它们并不是最佳选择。

在本节中，我们提出了设计WiscKey ，一个键值存储，在SSD上最小化I/O放大。为了实现SSD优化的键值存储，WiscKey包含四个关键构想。首先，WiscKey将键与值分开，仅将Key保留在LSM树中，而将Value保留在单独的日志文件中。其次，要处理未排序的Value（在范围查询期间需要随机访问），WiscKey使用SSD设备的并行随机读取特性。第三，WiscKey利用独特的崩溃一致性和垃圾收集技术来有效地管理值日志。最后，WiscKey通过在不牺牲一致性的情况下删除LSM树日志来优化性能，从而减少了写操作的系统调用开销。

3.1设计目标

WiscKey是派生自LevelDB的单机持久键值存储。可以将其作为关系数据库（例如MySQL）或分布式键值存储（例如MongoDB）的存储引擎。它提供与LevelDB相同的API ，包括Put，Get，Delete和Scan。WiscKey的设计遵循这些主要目标。

低写放大率。写放大会引入额外的不必要写操作。尽管与硬盘驱动器相比，SSD设备具有更高的带宽，但是较大的写放大会占用大部分写带宽（通常不超过90％），并且由于擦除周期有限，还会缩短SSD的使用寿命。因此，重要的是最小化写放大，以提高工作负载性能和SSD寿命。

低读放大。大的读取放大会导致两个问题。首先，通过为每个查询发出多次读取，大大降低了查询的吞吐量。其次，大量数据加载到内存中会降低缓存的效率。WiscKey的目标是进行较小的读取放大，以加快查找速度。

SSD优化。WiscKey通过将其I/O模式与SSD设备的性能特征进行匹配而针对SSD设备进行了优化。具体来说，有效利用顺序写入和并行随机读取，以便应用程序可以充分利用设备的带宽。

功能丰富的API.WiscKey旨在提供那些使得LSMtree变得被大众广泛使用的特性，如范围查询和快照。范围查询允许扫描键值对的连续序列。快照允许在特定时间捕获数据库的状态，然后对状态进行查找。

实际的键值大小。Key的size通常较小（例如，16 B）[7，8，11，22，35]，Value Size可变化的幅度较大（例如，100 B到大于4 KB）[6，11，22，28，32，49]。WiscKey旨在为这些场景的键值大小提供高性能。

3.2键值分离

LSM树的主要性能成本是Compaction过程，该过程不断对SSTable文件进行排序。在压缩期间，会将多个文件读入内存，进行排序和写回，这可能会严重影响前台工作负载的性能。但是，需要排序才能有效检索。通过排序范围查询（即Scan）将主要导致对多个文件的顺序访问，而点查询则需要在每个级别最多访问一个文件。

WiscKey的灵感来自一个简单的启示。压缩只需要对Key进行排序，而Value则可以单独管理[42]。由于Key size通常小于Value

size，因此仅压缩Key可以显着减少排序期间所需的数据量。在WiscKey中，仅使用Key将Value的位置存储在LSM树中，而将实际值以对SSD友好的方式存储在其他位置。通过这种设计，对于具有给定大小的数据库，WiscKey的LSM树的大小比LevelDB的小得多。对于值大小适中的现代工作负载，较小的LSM树可以显着减少写放大。例如，假设一个16-B Key，一个1KB Value，并且Key（在LSM树中）的写入放大率为10，对于值的写入放大为1，则WiscKey的有效写入放大率仅为（10 x 16 + 1024）/（16 + 1024）= 1.14。除了提高应用程序的写性能外，减少的写放大还通过减少擦除周期来提高SSD的使用寿命。

WiscKey较小的读取放大可提高查找性能。在查找过程中，WiscKey首先在LSM树中搜索Key和Value的位置。一旦找到，将发出另一次读取以检索该Value。读者可能会认为，由于其额外的I/O检索Value，WiscKey会比LevelDB查找性能慢。但是由于WiscKey的LSM树比LevelDB小得多（对于相同的数据库大小），查找可能会在LSM树中搜索较少级别的表文件，并且LSM树的很大一部分都可以轻松地缓存在内存中。因此，每次查找仅需要一次随机读取（用于检索Value），从而获得比LevelDB更好的查找性能。例如，假设使用16-B键和1KB值，如果整个键值数据集的大小为100 GB，则LSM树的大小仅约为2GB（假设对于一个值和大小），可以轻松地将其缓存在内存超过100 GB的现代服务器中。

WiscKey的架构如图4所示。Key存储在LSM树中，而Value存储在单独的值日志文件vLog中。与LSM-tree中的Key一起存储的人工值是vLog中实际Value的地址。当用户在WiscKey中插入键值对时，该Value首先附加到vLog ，然后将该键连同值的地址（< vLog-offset，value-size>）插入LSM树中。删除Key只是将其从LSM树中删除，而无需碰触vLog 。

vLog中的所有有效值在LSM树中都有对应的Key；vLog中的其他值无效，以后将被垃圾回收（第3.3.2节）。

当用户查询Key时，首先在LSM树中搜索该Key，如果找到该Key，则会检索相应Value的地址。然后，WiscKey从vLog读取值。请注意，此过程适用于点查询和范围查询。尽管键值分离背后的想法很简单，但它带来了以下小节中描述的许多挑战和优化机会。

3.3挑战

键和值的分离使范围查询需要随机I / O。此外，这种分离使垃圾收集和崩溃一致性都具有挑战性。现在，我们解释如何解决这些挑战。

3.3.1并行范围查询

范围查询是现代键值存储的重要功能，它允许用户扫描一系列键值对。关系数据库[26]，本地文件系统[30 ，46，50]，甚至分布式文件系统[37 ]使用键值存储作为其存储引擎，范围查询是在这些环境中所请求的核心API。

对于范围查询，LevelDB为用户提供基于迭代器的界面，该界面具有Seek（key），Next（），Prev （），Key（）和Value（）操作。扫描范围的关键值对，用户可以先Seek（）起始Key，然后调用Next（）或Prev（）逐个检索key。要检索Key或当前迭代器位置的Value，用户分别调用Key（）或Value（）。

在LevelDB中，由于键和值存储在一起并进行排序，因此范围查询可以从SSTable文件中顺序读取键-值对。但是由于在WiscKey中Key和Value分别存储，因此范围查询需要随机读取，因此效率不高。正如我们在看到图3 ，SSD上单个线程的随机读取性能无法比拟顺序读取性能。但是，请求大小相当的并行随机读取可以充分利用设备的内部并行性，从而获得与顺序读取类似的性能。

为了提高范围查询的效率，WiscKey利用SSD设备的并行I / O特性在范围查询期间从vLog中预取值。基本思想是，对于SSD，只有Key才需要有效检索。只要有效地检索Key，范围查询就可以使用并行随机读取来有效地检索值。

预取架构可以轻松适应范围查询接口。在当前接口中，如果用户请求范围查询，则将迭代器返回给用户。对于迭代器上请求的每个Next（）或Prev （），WiscKey都会跟踪范围查询的访问模式。一旦请求了一个连续的键-值对序列，WiscKey便开始从LSM树中顺序读取多个后续键。从LSM树中检索到的对应值地址将插入队列；多个线程将在后台同时从vLog中获取这些地址。

3.3.2垃圾收集

当键值对被删除或覆盖时，基于标准LSM树的键值存储不会立即回收可用空间。相反在压缩期间，如果找到与已删除或覆盖的键值对有关的数据，则将数据丢弃并回收空间。在WiscKey中，LSMtree压缩仅回收无效的Key。由于WiscKey不会Compaction Value，因此需要特殊的垃圾收集器来回收vLog中的可用空间。

由于我们仅将Value存储在vLog文件中（第3.2节），因此从vLog回收可用空间的一种简单方法是首先扫描LSM树以获取所有有效值地址；否则请执行以下步骤。然后vLog中所有没有LSM树的有效引用的值都可以视为无效并回收。但是，此方法过于繁重，仅可用于脱机垃圾收集。

WiscKey面向轻量级的在线垃圾收集器。为了使之成为可能，我们对WiscKey的基本数据布局进行了微小的更改：在将值存储在vLog中的同时，我们还将相应的键与值一起存储。新数据布局如图5所示：元组（Key size，Value size，Key，Value）存储在vLog中。

WiscKey的垃圾回收旨在将有效值（不对应于已删除的键）保留在vLog的连续范围内，如图5所示。此范围的一端（头部）始终对应于vLog的末尾，在该末尾将附加新值。此范围的另一端称为尾部，是每当垃圾收集被触发时便开始释放空间的地方。vLog头部和尾部之间的仅一部分包含有效值，并且将在查找期间进行搜索。

在垃圾回收期间，WiscKey首先从vLog的尾部读取一大堆键值对（例如，几个MB），然后通过查询LSM树来找到其中哪些值有效（尚未覆盖或删除）。然后WiscKey将有效值附加回vLog的头部。最后，它释放了块之前占用的空间，并相应地更新了尾部。

为了避免在垃圾回收过程中发生崩溃时丢失任何数据，WiscKey必须确保在实际释放空间之前，新附加的有效值和新尾部在设备上是持久的。

WiscKey使用以下步骤实现此目的。之后追加的有效值到VLOG ，垃圾收集调用的fsync （）的VLOG 。然后，将这些新值的地址和当前尾部以同步方式添加到LSMtree中。尾部以<' 'tail'，tail - vLog -offset>的形式存储在LSM树中。最后，将回收vLog中的可用空间。

可以将WiscKey配置为定期启动或继续垃圾收集，或者直到达到特定阈值为止。垃圾收集还可以脱机模式运行以进行维护。对于删除很少的工作负载以及存储空间过大的环境，垃圾收集很少触发。

3.3.3崩溃一致性

在系统崩溃时，LSM树实现通常保证插入的键值对的原子性和插入对的有序恢复。由于WiscKey的体系结构将值与LSM树分开存储，因此获得相同的崩溃保证似乎很复杂。但是，WiscKey通过使用现代文件系统的有趣属性（例如ext4，btrfs和xfs）来提供相同的崩溃保证期。考虑一个包含字节序列_b 1 b 2 b 3 ... b n _的文件，用户向其附加序列_b n + 1 b n + 2 b n + 3 ... b n + m _ 。如果发生崩溃，则在现代文件系统中恢复文件系统后，将观察到该文件包含字节序列_b 1 b 2 b 3 ... b n b n + 1 b n + 2 b n + 3 。 .. b N + X _ ∃ X <M，即，仅在所附的一些字节前缀将被添加文件系统恢复期间对文件的末尾[45]。随机字节或非前缀子集所附的字节不可能被添加到该文件。由于在WiscKey中将值顺序地附加到vLog文件的末尾，因此上述属性可以方便地进行如下转换：如果vLog中的ValueX在崩溃中丢失，则所有将来的值（在X之后插入）也将丢失。

当用户查询键值对，如果WiscKey找不到在LSM-tree的key，因为key在系统崩溃时丢失了，WiscKey行为像传统的LSM-树：即使value已经被写入vLog前崩溃，它将在以后被垃圾收集。如果可以在LSMtree中找到Key，但是，需要额外的步骤来保持一致性。

在这种情况下，WiscKey首先验证从LSM-tree检索到的值地址是否在vLog的当前有效范围内，然后验证找到的值是否对应于查询的Key。如果验证失败，WiscKey会假定该值在系统崩溃期间丢失了，然后从LSMtree中删除Key，并通知用户未找到该密钥。

由于添加到vLog的每个值都有一个包含相应键的标头，因此验证键和值是否直接匹配；如有必要，可以轻松地将魔数或校验和添加到标头。如果用户明确要求同步插入，则LSM树实现还可以保证系统崩溃后用户对键值对的持久性。WiscKey通过在flush LSM tree之前先Flush Vlog。

3.4优化

在WiscKey中将键与值分开可以为重新思考Value日志的更新方式以及LSMtree日志的必要性提供机会。现在，我们描述这些机会如何导致性能提高。

3.4.1 Value-Log Write缓冲区

对于每个Put（），WiscKey调用write（）系统调用Append value到VLOG中。然而对于一个插入密集型工作负荷，发出大量的小写入一个文件系统可以引入一个明显的开销，尤其是一种快速存储装置[15，44]。

图6显示了在ext4（Linux 3.14）中顺序写入10 GB文件的总时间。对于较小的写入，每个系统调用的开销会大量聚集，从而导致运行时间较长。通过大写操作（大于4 KB），可以充分利用设备的吞吐量。为了减少开销，WiscKey在用户空间缓冲区中缓冲值，并且仅在缓冲区大小超过阈值或用户请求同步插入时才刷新缓冲区。因此，WiscKey减少了write（）系统调用。对于查找，WiscKey首先搜索vLog缓冲区，如果在该缓冲区中找不到，则实际上从vLog读取。显然，这种机制可能会导致某些数据（缓冲的）在崩溃期间丢失；获得的崩溃一致性保证类似于LevelDB 。

3.4.2优化LSM-tree日志

如图1所示，LSM tree中通常使用一个日志文件。LSM树跟踪日志文件中插入的键值对，因此，如果用户请求同步插入而发生崩溃，则可以在重新启动后扫描日志并恢复插入的键值对。

在WiscKey中，LSM tree仅存储Key和Value地址。此外，vLog还记录插入的Key以支持垃圾回收，如上一节所述。因此，可以避免在不影响正确性的情况下写入LSM-tree日志文件。如果在LSM树中持久保留Key之前发生崩溃，则可以通过扫描vLog来恢复它们。

然而，一个简单的算法需要扫描整个vLog进行恢复。为了只需要扫描vLog的一小部分，WiscKey将vLog的头部周期性地记录在LSM树中，作为键值对<<‘‘head’’, head-vLog-offsett> 。打开数据库后，WiscKey从存储在LSM tree中的最新磁头位置开始扫描vLog，并继续扫描直到vLog结束。由于head存储在LSM树中，并且LSM树固有地保证插入到LSM树中的Key将按插入顺序进行恢复，因此此优化是崩溃一致的。因此去除LSM-树日志的WiscKey是安全的优化，并提高了性能尤其是当有许多小的插入。

3.5实施

WiscKey基于LevelDB1.18。WiscKey为VLOG创建一个新的数据库，以及管理Key和Value地址在LSM-tree。所述VLOG是内部由具有不同的多个组件访问的访问模式。例如，随机读取VLOG模式提供查找功能 ，而垃圾收集器顺序地从尾读取并追加到头部的的Vlog的文件。我们使用posix fadvise（）为不同情况下的vLog预先声明访问模式。

对于范围查询，WiscKey维护具有32个线程的后台线程池。这些线程在线程安全的队列中休眠，等待新的值地址到达。触发预取后，WiscKey将固定数量的值地址插入工作队列，然后唤醒所有睡眠线程。这些线程将开始并行读取值，并自动将它们缓存在缓冲区缓存中。

为了有效地垃圾收集vLog的可用空间，我们使用了现代文件系统的打洞功能fallocate （）。在文件中打洞可自由分配的物理空间，并允许WiscKey来弹性地使用存储空间。现代文件系统上的最大文件大小足以使WiscKey长时间运行而不会回卷到文件的开头。例如，最大文件大小在ext4上为64 TB ，在xfs上为8 EB，在btrfs上为16 EB。如有必要，vLog可以简单地改编成循环日志。

4评估

在本节中，我们提供评估结果，这些结果证明了WiscKey设计选择的好处。

所有实验均在装有两个Intel®Xeon®CPU E5-2667 v2 @ 3.30GHz处理器和64 GB内存的测试机上运行。操作系统是64位Linux 3.14，使用的文件系统是ext4。

使用的存储设备是500 GB的Samsung 840EVO SSD，它具有500 MB / s的顺序读取和400 MB / s的顺序写入最大性能。该设备的随机读取性能如图3所示。

4.1微基准

我们使用db_bench（LevelDB中的默认微基准）评估LevelDB和WiscKey。我们始终使用16B的Key大小，但是针对不同的值大小执行实验。我们禁用数据压缩是为了更容易理解和分析性能。

4.1.1负载性能

现在，我们描述顺序加载和随机加载微基准测试的结果。前者通过按顺序插入Key来构建100 GB数据库，而后者则以均匀分布的随机顺序插入Key。请注意，顺序加载基准测试不会在LevelDB或WiscKey中引起Compaction，而随机加载会导致Compaction。

图7显示了各种值大小的LevelDB和WiscKey的顺序加载吞吐量：两个存储的吞吐量都随值大小而增加。但是，即使考虑到最大值（256 KB），LevelDB的吞吐量也离设备带宽还很远。为了进一步分析这一点，图8显示了在LevelDB每次运行基准测试期间，不同组件所花费的时间的分布；时间花费在三个主要部分中：写入日志文件，插入到内存表以及等待将内存表刷新到设备。对于较小的键/值对，写入日志文件占总时间的百分比最大，原因如图6所示。对于较大的KeyValue对，日志写入和内存表排序效率更高，而内存表刷新则是瓶颈。与LevelDB不同，WiscKey可以在超过4 KB的值时达到完整的设备带宽。由于它不会写入LSM-tree日志，而是将缓冲区追加到vLog ，因此即使是较小的值也快3X。

图9显示了不同值大小的LevelDB和WiscKey的随机加载吞吐量。LevelDB的吞吐量范围仅从2 MB/s（64-B值大小）到4.1 MB/s（256-KB值大小），而WiscKey的吞吐量随着值大小的增加而增加，在值大小变大后达到峰值设备写入吞吐量超过4 KB。WiscKey的吞吐量在1-KB和4 KB Value大小分别是LevelDB吞吐的46X和111X。LevelDB的吞吐量很低，因为Compaction既消耗了设备带宽的很大一部分，又减慢了前台写入的速度（以避免超载LSM树的L 0 ，如第2.2节所述）。WiscKey中的Compaction只会带来很小的开销，从而导致有效利用整个设备的带宽。为了分析这个进一步，图10所示LevelDB和WiscKey的写入放大性，LevelDB的写入放大性总是超过12，而中WiscKey迅速下降至近1当值大小达到1 KB，因为的LSM-树WiscKey明显较小。

4.1.2查询性能

现在，我们比较LevelDB和WiscKey的随机查找（点查询）和范围查询性能。图11展示了在100 GB随机加载的数据库上进行100,000次操作的随机查找结果。即使在WiscKey中进行随机查找需要同时检查LSM树和vLog ，WiscKey的吞吐量仍然比LevelDB好得多：对于1 KB的值大小，WiscKey的吞吐量是LevelDB的12X 。对于较大的Value，WiscKey的吞吐量仅受设备的随机读取吞吐量限制，如图3所示。由于2.3节中提到的高读取放大，LevelDB具有低吞吐量。WiscKey的性能明显更好，因为较小的LSM树会导致读取放大率降低。WiscKey的更好的表现另一个原因是WiscKey的Compaction负载很低，因而避免了许多后台读取和写入操作。

图12示出了LevelDB和WiscKey 范围查询（扫描）性能。对于随机加载的数据库，LevelDB从不同级别读取多个文件，而WiscKey要求对vLog进行随机访问（但是WiscKey利用并行随机读取）。正如可从图中可以看出12，LevelDB的吞吐量最初随着两个数据库的值大小而增加。但是，除了4 KB的值大小之外，由于SSTable文件只能存储少量的键值对，因此通过打开许多SSTable文件并读取每个文件中的索引块和Bloom过滤器来控制开销。对于较大的键-值对，WiscKey可以提供该设备的连续带宽，比LevelDB性能提升达到8.4X。但是，由于设备对小请求量的并行随机读取吞吐量有限，WiscKey在64-B键值对上的性能比LevelDB差12X。WiscKey的相对性能在具有更高并行随机读取吞吐量的高端SSD上更好[3]。此外，这种工作负载代表了最坏的情况，即数据库被随机填充并且vLog中的数据未排序。

图12还显示了对数据进行排序时范围查询的性能，该数据对应于顺序加载的数据库。在这种情况下，LevelDB和WiscKey都可以顺序扫描数据。顺序加载的数据库的性能遵循与随机加载的数据库相同的趋势。对于64-B对，WiscKey是慢25％，因为WiscKey读取Keys和从Vlog中所在key的Value（因而浪费带宽），但是对于大键值对WiscKey快2.8X。因此小的键值对，日志重组（排序）为随机装载的数据库可以让WiscKey的范围，查询性能媲美于性LevelDB的性能。

4.1.3垃圾收集

现在，我们在后台进行垃圾收集时调查WiscKey的性能。该性能可以根据百分比可能变化的垃圾回收过程中发现的可用空间，因为这会影响写入的数据量和空间由垃圾收集线程释放量。

我们使用随机负载（受垃圾回收影响最大的工作负载）作为前台工作负载，并研究其在各种百分比的可用空间上的性能。我们的实验具体涉及三个步骤：首先使用随机加载创建数据库，然后删除所需的键值对百分比，最后运行随机加载工作负载并测量其吞吐量，同时后台进行垃圾收集地面。我们使用4 KB的键值大小，并将可用空间的百分比从25％更改为100％。

图13显示了结果：如果垃圾收集器读取的100％数据无效，则吞吐量仅降低10％。吞吐量仅略微降低，因为垃圾收集从vLog的尾部读取，并且仅将有效的键值对写入头部；如果读取的数据完全无效，则无需写入任何键值对。对于其他百分比的可用空间，由于垃圾回收线程执行其他写入操作，因此吞吐量下降约35％。请注意，在所有情况下，在进行垃圾收集时，WiscKey至少比LevelDB快70X。

4.1.4崩溃一致性

将键与值分开需要其他机制来保持崩溃的一致性。我们使用ALICE工具[45]来验证WiscKey的崩溃一致性机制。该工具选择并模拟一组全面的系统崩溃，这些崩溃很可能暴露出不一致性。我们使用一个测试用例来调用一些异步和同步的Put（）调用。当被配置成运行EXT4，测试XFS，和BTRFS ，ALICE检查超过3000 选择性系统崩溃，并且没有报告WiscKey引入任何一致性漏洞。

新的一致性机制也影响WiscKey的崩溃后恢复时间，我们设计一个实验来测量最坏情况下WiscKey和LevelDB的恢复时间 。LevelDB的恢复时间与崩溃后日志文件的大小成正比；即将将内存表写入磁盘之前，日志文件以其最大大小存在。WiscKey在恢复过程中，首先从LSM树中检索头指针，然后从头指针扫描vLog文件直到文件末尾。由于写入内存表时更新的头指针会保留在磁盘上，因此WiscKey最坏的恢复时间也对应于在此之前发生的崩溃。我们测量了迄今为止所描述情况导致的最坏情况下的恢复时间；对于1 KB值，崩溃后，LevelDB需要0.7秒来恢复数据库，而WiscKey需要2.6秒。请注意，可以将WiscKey配置为在必要时更持久地保留头指针。

4.1.5空间放大

在评估键值存储时，大多数以前的工作仅专注于读写放大。但是，空间放大对于闪存设备很重要，因为与硬盘驱动器相比，每GB的价格昂贵。空间放大是磁盘上数据库的实际大小和数据库逻辑大小的比率[5]。例如，如果1 KB的键值对占用磁盘上4 KB的空间，则空间放大率为4。压缩会减少空间放大，而多余的数据（垃圾，碎片或元数据）会增加空间放大。禁用压缩使讨论变得简单。对于顺序负载的工作负载，由于LSM树中的额外元数据最少，因此空间放大可以接近1。对于随机加载或覆盖的工作负载，当无效对没有足够快地进行垃圾收集时，空间放大通常大于1。

图14显示了随机加载100 GB数据集后的LevelDB和WiscKey的数据库大小（与图9相同的工作量）。LevelDB的空间开销是由无效的键值对引起的，这些无效的键值对在工作负荷完成时不会进行垃圾回收。所述的空间开销WiscKey包括无效键值对和额外的元数据（指针在LSMtree并在所述元组的Vlog如图5）。以后垃圾收集，数据库大小WiscKey是接近时，额外的元数据的逻辑数据库大小值相比较尺寸小。

没有键值存储可以同时最小化读取放大，写入放大和空间放大。这三个因素之间的权衡在各种系统中的平衡不同。在LevelDB中，排序和垃圾回收耦合在一起。LevelDB将较高的写放大率换成较低的空间放大率；但是，工作负载性能可能会受到严重影响。WiscKey在工作负荷运行时会占用更多空间以最小化I/O放大；由于排序和垃圾回收在WiscKey中是分离的，因此垃圾回收可以稍后进行，从而将其对前台性能的影响降至最低。

4.1.6 CPU使用率

现在，我们针对上一部分中显示的各种工作负载调查LevelDB和WiscKey的CPU使用率。

此处显示的CPU使用率包括应用程序和操作系统使用率。

如表1所示，对于顺序加载工作负载，LevelDB具有更高的CPU使用率。正如我们在图8中解释的那样，LevelDB花费大量时间将键值对写入日志文件。写入日志文件涉及对每个键值对进行编码，这会增加CPU成本。由于WiscKey作为优化删除了日志文件，因此WiscKey的CPU使用率低于LevelDB 。

对于范围查询工作量，WiscKey使用32个线程做预取; 因此WiscKey的CPU使用率比LevelDB高得多。我们发现在我们的设置中，CPU对于LevelDB和WiscKey都不是瓶颈。LevelDB的体系结构基于单写程序协议。后台Compaction也仅使用一个线程。RocksDB[25]探索了更好的多核并发设计。

4.2 YCSB基准

YCSB基准[21]提供了一个框架和一组标准的六个工作负载，用于评估键值存储的性能。我们使用YCSB在100 GB的数据库上比较LevelDB，RocksDB[25]和WiscKey。除了测量通常情况下的性能的WiscKey ，我们也跑WiscKey垃圾收集一直在后台发生的事情，以测量其最坏情况下的性能。RocksDB[25]是LevelDB的SSD优化版本，具有许多优化功能，包括多个内存表和用于压缩的后台线程。我们将RocksDB与默认配置参数一起使用。我们评估了关键值存储与两个不同的值的尺寸，1 KB和16 KB（数据压缩是禁用）。

WiscKey的性能明显优于LevelDB和RocksDB ，如图15所示。例如，在负载为1-KB值，WiscKey在通常情况下比其他数据库快50X，以及在最坏的情况下至少快45X（开启垃圾回收）;WiscKey在16 KB的Value，即使在最坏的情况下也能表现出104X的性能。

对于读取而言，大多数工作负载中使用的Zipf分发允许在不引起磁盘访问的情况下缓存和检索流行项目，从而降低了WiscKey与LevelDB和RocksDB相比的优势。因此，WiscKey的相对性能（与LevelDB和RocksDB相比）在Workload-A（50％读取）中比在Workload-B（95％读取）和Workload-C（100％读取）中更好。

但是，在任何这些工作负载中，RocksDB和LevelDB仍无法达到WiscKey的性能。WiscKey的最坏情况下的性能（即使对于只读工作负载，垃圾收集始终处于打开状态）优于LevelDB和RocksDB 。

但是，对于1KB和16 KB值，垃圾回收对性能的影响明显不同。垃圾收集反复选择并清除vLog的4MB块；如果值较小，则该块将包含许多键值对，因此垃圾回收会花费更多时间访问LSM树以验证每对的有效性。对于较大的值，垃圾收集花费的验证时间少，因此积极地写出已清理的块，影响前台吞吐量更多。请注意，如有必要，可以限制垃圾收集以减少其对前台的影响。

与先前考虑的微基准不同，Workload-E具有多个小范围查询，每个查询可检索1至100个键值对。由于工作负载涉及多个范围查询，因此访问每个范围中的第一个键都将解析为随机查找，这对WiscKey是有利的。因此，即使对于1KB的值，WiscKey的性能也比RocksDB和LevelDB好。