WiscKey介绍WiscKey是一篇发表于存储领域顶尖学术会议 FAST 16 的里程碑式论文WiscKey: Separating Keys from Values in SSD-Conscious Key-Value Stores由威斯康星大学麦迪逊分校UW-Madison的 ADSL 实验室提出。LSM-Tree的局限LSM-Tree 诞生于HDD时代HDD 的随机读写比顺序读写慢 100 倍以上因此用多次顺序读写来换取后续高效查询的代价是划算的。这会带来IO放大现代 SSD 具有随机与顺序性能差距小、内部并行度高以及有擦写寿命限制的特点。继续采用传统 LSM-Tree 架构会导致 SSD 吞吐量下降高达 90%无法释放SSD的真正性能。WiscKeyWiscKey将 Key 和 Value 分离存储Key 依然在 LSM-Tree 中排序管理而 Value 提取出来单独保存在日志文件中。通过避免排序过程中不必要的值移动显著降低写放大效应同时 LSM 树的规模明显减小从而减少磁盘读取次数提升查询时的缓存效率。键值分离后带来了新的难题WiscKey 提出了对应的优化方案范围查询变慢因为 Value 不再按 Key 的顺序物理存储。解法充分利用现代 SSD 强大的内部并发读取能力来提升 Scan 性能。空间回收无效/旧版本的 Value 需要被清理。解法设计轻量级的在线 GC 机制全过程仅包含顺序 I/O对前台读写性能影响极小。崩溃一致性分离存储后如何保证crash时数据一致性保证。解法利用现代文件系统追加写入在crash的时候不会产生垃圾的特性提供与 LevelDB 完全相同的强一致性保证。性能提升LevelDB的Microbenchmarks加载数据库比 LevelDB 快 2.5× – 111×随机查询比LevelDB块1.6×–14×随机写入小 Value和大型数据集顺序scan比LevelDB性能差YCSBWiscKey在全部六种 YCSB 工作负载中均优于LevelDB和RocksDB读放大和写放大写读放大率定义为写入从底层存储设备的数据量与用户请求的数据量之比。写放大写放大来源在 Compaction过程中需要读取一个LiL_iLi的SSTable和最多10个Li1L_{i1}Li1的SSTable。数据每跨越一层写放大最高可达 10 倍。对于有很多数据的db新生成的SSTable最终都会通过一系列 Compaction 从L0L_0L0一步步迁移至L6L_6L6。在这个过程中写放大逐层累加总写放大可以超过 50 倍。在图2中1 GB数据量下写放大为 3.1100GB时写放大为14。原因分析数据量变大后数据更有可能从低层级一步步向下压缩迁移至高层级从而被反复重写多次。读放大读放大的来源为了查找一个 Key-Value 对LevelDB 可能需要检索多个Level的文件。SSTable内部LevelDB 无法直接精准读取数据块必须同时读取多个元数据块Index BlockBloom Filter BlockData Block\text{Index Block} \text{Bloom Filter Block} \text{Data Block}Index BlockBloom Filter BlockData Block。例如查找一个1KB的键值对时LevelDB需读取16KB的索引块、4KB的布隆过滤器块和4KB的数据块总计24KB。因此在最坏情况下考虑全部14个SSTable文件时LevelDB的读取放大量为24×14336。对于较小的键值对读取放大效应会更为显著。在图2中1 GB数据量下读放大为8.2100GB时读放大为327。原因分析对于小数据量Index Block 和 Bloom Filter 可以完全被内存 Cache 缓存但对于 100 GB 的大数据量内存装不下全部索引每次查询都会去读取不同 SSTable 文件的 Index Block 和 Bloom Filter导致读放大扩大。SSD和LSM-Tree与机械硬盘类似出于其独特的“先擦除再写入”循环以及高昂的垃圾回收GC开销随机写入在 SSD 中同样会导致性能下降。这就使得LSM-Tree同样很适合用在SSD上。但是与 HDD 不同SSD 拥有极佳的随机读性能和内部高并发能力。单线程随机读只要请求粒度变大如 256 KB吞吐量即可达到顺序读的一半。多线程并发随机读通过多线程如 32 线程并发发起随机读当请求大小≥\ge≥16 KB 时吞吐量可以完全媲美顺序读。WiscKey方案设计设计目标WiscKey是从Leveldb派生而来的单机持久化kv存储。提供和Leveldb一样的APIPutGetDeleteScan。WiscKey的设计目标有下面几个降低写放大严重的写放大会导致如下问题消耗大部分SSD带宽资源同时因为SSD擦除次数有限写放大同样会缩短固态硬盘的使用寿命。降低读放大较高的读放大会导致如下问题每次查询都需要执行多次读取操作导致查询吞吐量显著降低其次大量数据被加载到内存中会降低缓存的使用效率。针对 SSD 进行优化WiscKey 通过将其 I/O 模式与 SSD 设备的性能特性相匹配针对 SSD 设备进行了深度优化。它有效地利用了顺序写入和并发随机读取从而能够充分利用SSD的带宽。丰富的API支持WiscKey 旨在支持使 LSM-Tree 流行起来的那些现代特性例如范围查询和快照。更好支持实际场景key-value大小在现代工作负载中Key 的大小通常较小例如 16 字节而 Value 的尺寸差异很大例如从 100 字节到大于 4 KB 不等。WiscKey 旨在针对这种贴近实际应用的键值尺寸组合提供出色的性能。kv分离方案引入kv分离的原因LSM-Tree的性能开销主要是在compaction过程。compaction需要对多个SSTable进行排序多个SSTable的内容会读入到内存中排序后在写入SSTable。这会占用很多的磁盘带宽。但是这个排序对于检索kv很重要不能去掉。WiscKey的解决方案来源于识别到compaction只要求对key进行排序但是value可以进行单独的存储管理。这其实需要基于一个数据模型是key比vlaue小很多如果key比value大很多的话就没必要进行kv分离了。WiscKey的kv分离存储WiscKey 只在 LSM-Tree 中存放 Key 和 Value 的物理地址而将真实的 Value 追加保存在单独的日志文件vLog。数据操作流程写入value先写入vLog中然后将key和value的addrvLog-offset, value-size)写入LSM-Tree中。删除删除直接再LSM-Tree中删除对应的key不会操作vLog中的value。没有LSM-Tree中的key引用的vLog数据是无效的后续通过GC处理。查询先查询LSM-Tree然后根据addr查询对应的valuekv分离带来的好处显著降低LSM-Tree的大小。降低LSM-Tree的写放大。假设 Key 为16 B16\text{ B}16BValue 为1 KB1\text{ KB}1KB(1024 B1024\text{ B}1024B) LSM-Tree的写放大为 10而vLog追加写 Value的写放大为 1WiscKey 的有效写放大10×161024161024≈1.14\text{WiscKey 的有效写放大} \frac{10 \times 16 1024}{16 1024} \approx \mathbf{1.14}WiscKey的有效写放大16102410×161024≈1.14。写放大降低后可以有效提高SSD的寿命。kv分离对点查的影响对于一次读需要先读取LSM-Tree获取到value的addr然后再根据addr的地址从VLog读取value。这比Leveldb多一次磁盘IO这会导致读比Leveldb慢。但是因为LSM-Tree中只存储了value的addr这会降低LSM-Tree的大小可以使得LSM-Tree的数据都缓存到内存中那么WiscKey的读取只需要一次磁盘IO这就比Leveldb的读取操作要快了。kv分离场景下的扫描应该是比Leveldb要慢的因为value是无序的状态。kv分离带来的挑战kv分流带来了以下挑战范围查询需要随机IO需要引入垃圾回收需要处理崩溃恢复时的数据一致性范围查询范围查询的问题在LevelDB中键值被共同存储并排序范围查询可顺序从SSTable文件中读取键值对。然而由于WiscKey中键值是分别存储的范围查询需要随机读取数据这会降低范围查询的速度。在SSD中单线程的随机读取性能时比不上顺序读取性能的但是对于请求数据较大的并行随机读取性能时能媲美顺序读取性能的。解决方案并发从SSD中进行预读。范围查询时一次获取多个key和key对应的addr然后并发的获取多个addr对应的value来提高范围查询的性能。针对预读的API改造识别到用户需要连续读取数据后Next()或Prev()操作从LSM-Tree中顺序读取多个key-addr然后将addr写入到队列中后台多线程并发读取队列中的addr对应的value写入缓存中。GC引入GC原因基于标准 LSM 树的键值存储结构在删除或覆盖键值对时并不会立即释放空闲空间。而是在compaction过程中如果发现与已删除或被覆盖的键值对相关的数据则该数据将被丢弃并释放空间。在WiscKey中compaction只会对key进行回收但是value在compaction的过程中不会回收。所以需要一个单独的GC来对vLog中的无效空间进行回收。解决方案一种简单的回收vLog中空闲空间的方法是首先扫描 LSM 树获取所有有效的值地址随后将vLog中未被 LSM 树引用的value视为无效并予以回收。但是该方法耗时过长仅适用于离线垃圾回收场景。WiscKey的解决方法在将值存储于vLog时同时会一并存储对应的key。vLog的存储格式如下图WiskSec的GC的目标是将有效值保留在vLog的连续范围内。该范围的一端称为head始终对应vLog的末尾位置新的数据值将被追加在这个地方另一端称为tail则是垃圾回收机制触发时开始释放空间的位置。只有位于头部与尾部之间的vLog段包含有效数据并会在查询过程中被检索。GC流程WiscKey的GC流程从vLog的tail读取一大块键值对例如数兆字节通过查询LSM-Tree来找出其中有效的key-value对将有效的key-value对搬移到head更新tail释放空间为了防止数据丢失WiscKey必须确保新添加的有效值及新的尾部数据在实际释放空间之前均能持久保存于磁盘上。WiscKey通过下面的手动来保证数据不丢失在将有效值写入到vLog后对vLog调用fsync()函数进行落盘将新的vlaue address和tailtail格式‘‘tail’’, tail-vLog-offset.以同步方式记录到LSM-Tree中。最后再释放空间GC执行时机WiscKey 可以配置为定期启动并持续执行GC或者达到特定阈值时触发。垃圾回收也可以在离线维护模式下运行。崩溃恢复时的数据一致性背景在系统崩溃时 LSM 树实现机制通常能保证插入的键值对具有原子性并确保插入对能够按顺序恢复。由于WiscKey架构将数值与 LSM 树分开存储要实现相同的崩溃保障机制可能会较为复杂键值对的原子性很难保证。WiscKey通过利用现代文件系统如ext4、btrfs和xfs的一个重要特性来提供相同的保障若vLog中的某个值X在崩溃时丢失则所有后续插入的值也会一同丢失。数据一致性的实现用户查询kv对时的数据一致性保证如果无法在 LSM 树中找到该key则其行为与传统 LSM 树完全一致。如果value已经写入到vLog中了对应的value会再GC中进行回收如果能在 LSM 树中找到该键则需额外步骤以确保数据一致性WiscKey首先验证从 LSM 树获取的值地址是否处于vLog当前有效范围内。确认所得值是否与查询键一致通过vLog中保存的key和LSM-Tree中的key进行对比。如果不一致那么就从LSM-Tree中删除key。LSM 树还支持用户明确请求同步插入操作来保证数据持久性。WiscKey通过在向 LSM 树执行同步插入前flush vLog到磁盘上来实现这一功能。优化vLog写缓存对于每次Put()操作WiscKey都需要通过write()系统调用将数据值追加到vLog中。然而在以插入操作为主的业务场景下向文件系统发起大量小数据写入会带来显著的系统开销。为降低系统开销WiscKey会在用户空间缓冲区中缓存数据值仅当缓冲区大小超过阈值或用户请求同步写入时才将缓存区的数据刷入磁盘中。在数据查询时WiscKey首先会在vLog缓冲区中查找。这种机制可能导致部分缓存的数据在系统崩溃时丢失。缓存区要预分配vLog的offest保证缓存按照顺序写入vLog。LSM-Tree WAL日志优化在WiscKey中 vLog会记录已插入的kv以支持垃圾回收机制。因此 LSM-Tree的WAL日志就可以无损去除了。crash后可以通过扫描vLog来进行恢复。为了减少扫描vLog的范围WiscKey会定期将vLog的head作为键值对‘’head‘’head-vLog-offset记录在 LSM 树中。当数据库启动或重新打开时WiscKey 从 LSM-Tree 中记录的最新head位置开始向后顺序扫描vLog直到vLog文件的末尾恢复出其中的kv对。由于 LSM-Tree 本身能够保证其中记录的 Key 恢复时严格满足按插入顺序恢复的特性因此基于 LSM-Tree 中的 head 结合 vLog 扫描来进行恢复是可以保证数据一致性的。这个会导致db recover的时间变长因为再kv分离的场景下vLog的存储包括valueWAL中只包括key和value的addr读取的空间会比WAL日志的大。实现WiskKey基于LevelDB 1.18版本开发。WiskSec在创建新数据库时创建vLog并在LSM-Tree中管理key和value的addr。vLog 在内部会被具有不同访问模式的多个组件同时访问。例如查询操作通过随机读取 vLog来完成而GC则是从 vLog 文件的tail顺序读取并追加写入到head。我们使用posix_fadvise()来预先声明对 vLog的访问模式。对于范围查询WiscKey 维护了一个包含 32 个线程的后台线程池。这些线程在一个线程安全的队列上休眠等待新的 Value 地址到来。当预读被触发时WiscKey 会将固定数量的 Value 地址插入到工作队列中并唤醒所有休眠的线程。这些线程随后开始并行读取 Value并将它们缓存到 Buffer Cache中。为了高效地回收vLog 释放出的空间我们使用了现代文件系统的打孔Hole-punching功能通过fallocate()系统调用实现。可以在不改变文件总体偏移量的前提下把vLog头部被 GC 掉的无效数据区的物理磁盘块释放掉还给操作系统。现代文件系统支持的最大单文件体积足够大足以让 WiscKey 运行很长时间而无需回绕至文件开头例如ext4 的最大文件大小为 64 TBxfs 为 8 EBbtrfs 为 16 EB。如果有需要vLog也很容易改编为循环日志的形式。性能评估所有实验均在一台测试机器上运行该机器配备了两颗 Intel® Xeon® CPU E5-2667 v2 3.30GHz 处理器和 64 GB 内存。操作系统为 64 位 Linux 3.14使用的文件系统是 ext4。所用的存储设备为一块 500 GB 的三星 840 EVO SSD其顺序读取和顺序写入的最大性能分别为 500 MB/s 和 400 MB/s。Microbenchmarks我们使用db_benchLevelDB 中默认的微基准测试工具来评估 LevelDB 和 WiscKey 的性能。在所有实验中我们统一将 Key 的大小设为 16 字节但针对不同的 Value 大小进行了多组实验。为了更便于理解和分析性能我们禁用了数据压缩功能。写入性能下面是顺序写入和随机写入微基准测试的结果。前者通过按顺序插入 Key 来构建一个 100 GB 的数据库而后者则以均匀分布的随机顺序插入 Key。需要注意的是顺序写入在 LevelDB 或和WiscKey 中都不会触发 Compaction而随机写入则会触发。顺序写入性能Figure 7显示顺序写的场景下LevelDB和WhisKey的吞吐量均随数据值大小的增加而提升。但是在最大的value大小下LevelDB的吞吐量也没有达到磁盘的带宽。Figure 8显示了LevelDB中各组件所耗时间的分布情况。时间主要消耗在三个主要环节向日志文件写入数据、向内存表插入数据以及等待memtable刷盘到SSTable。对于小value而言写入日志文件所占总耗时比例最高对于大value等待memtable刷盘到SSTable则是性能瓶颈。与LevelDB不同WiscKey在处理超过4KB的数据量时可充分利用磁盘的全部带宽。由于它既不写 LSM-Tree日志同时在写vLog时使用Buffer缓存因此即使处理较小的value时速度也提升至原来的3倍。随机写入性能图9展示了LevelDB和WiscKey在不同value大小下的随机写入吞吐量。LevelDB的吞吐量范围从仅2 MB/s64字节值大小到4.1 MB/s256 KB值大小。WiskSec的吞吐量随value大小增加而提升在数据值大于4 KB时达到磁盘写入瓶颈。WiskSec的吞吐量是LevelD的 46倍到111倍。LevelDB的吞吐量较低是因为compaction不仅会消耗很大一部分磁盘带宽还会减慢前台写入操作以控制LSM-Tree L0层的增长速度compaction成为系统瓶颈。图10对比了LevelDB和WhisKey在随机写入下的写放大。LevelDB的写放大始终大于12而当value的大小达到1KB时WiscKey的写放大迅速降至接近1。查询性能下面将比较LevelDB与WiscKey在随机查找和范围查询方面的性能表现。随机查找性能运行负载在随机写入100GB的数据后进行100000次随机查询。结果分析对于1 KB的valueWiscKey的吞吐量是LevelDB的12倍而对于较大的valueWiscKey的吞吐量仅受限于磁盘的随机读取吞吐量如图 3 所示。LevelDB的吞吐量较低这是由于其较高的读放大和compaction占用磁盘带宽所导致的。范围查询性能随机写入的场景LevelDB会从不同层级读取多个文件而WiscKey则需要对vLog进行随机访问但WiscKey利用了并行随机读取技术。LevelDB的吞吐量最初随数据库值大小的增加而提升。然而当value超过4 KB时由于SSTable文件仅能存储少量键值对其开销主要源于需要打开多个SSTable文件并读取每个文件中的索引块和布隆过滤器。WiscKey分析。对于较大的valueWiscKey可以达到磁盘的顺序读取带宽最高可达LevelDB的8.4倍。然而在64字节的value下WiscKey的性能比LevelDB差12倍这是由于达到了SSD并发请求的上限。顺序写入的场景其性能表现与随机写入的场景呈现相同趋势。64字节的value大小下WiscKey的速度比其他value大小慢25%原因是WiscKey需要同时从LSM-Tree和vLog中读取数据。但对于大valueWiscKey的速度则快2.8倍。因此对于小value通过对vLog排序可使WiscKey的范围查询性能达到与LevelDB相当的水平。GC下面开发分析在后台执行垃圾回收时WiscKey的性能表现。性能会受到空闲空间百分比的影响因为这会影响GC线程写入的数据量以及释放的空间量。性能测试步骤和负载性能测试具体包含三个步骤我们通过随机写创建一个数据库删除所需比例的kv对运行随机写负载程序并且在后台GC的同时测量其吞吐量使用 4 KB 的键值对大小并将空闲空间百分比从 25% 到 100% 进行变动。性能结果与原因100% 空闲空间吞吐量仅下降 10%。原因GC 只需从 vLog 尾部顺序读取无需向头部重写任何有效数据写开销为 0。其他比例25%~75%吞吐量下降约 35%。原因GC 线程需要把未被删除的有效数据重新写回 vLog head抢占了部分写入带宽。崩溃恢复时的一致性验证和耗时一致性验证背景与工具由于键值分离机制增加了维护一致性的难度论文使用了专业的崩溃验证工具ALICE进行了系统性测试。测试方法在 ext4、xfs 和 btrfs 文件系统上运行异步和同步的 Put() 请求同时通过ALICE 模拟了超过 3000 种可能触发数据不一致的系统崩溃场景。结果ALICE 未发现由 WiscKey 引入的任何一致性漏洞证明其一致性机制安全可靠。崩溃恢复耗时1 KB Value 场景下LevelDB 的恢复时间为 0.7 秒。WiscKey 的恢复时间为 2.6 秒比 LevelDB 稍慢。%% 随着value变大需要读取的vLog也会变大那么WiscKey的恢复时间会变的更长 %%。空间放大空间放大是指磁盘上存储的实际大小与用户写入的数据大小之比。压缩可降低空间放大而额外数据如垃圾数据、碎片或元数据则会加大空间放大。为简化讨论本文未启用压缩功能。对于顺序写入场景空间放大倍数可接近1因为 LSM-Tree中额外的元数据量极小。对于随机写入和覆盖写入当无效kv未能被快速地回收时空间放大倍数通常大于1。LevelDB空间放大来源来自于尚未被Compaction清理的旧/无效 Key-Value 键值对。WiscKey空间放大来源包含两部分vLog 中未被 GC 清理的无效 KV。键值分离带来的额外元数据开销即 LSM-Tree 中存储的 Value 指针/Offset以及 vLog中记录的 Header 元数据。当存入的 Value 相对较大时元数据占比微乎其微经过 GC 后的 WiscKey 磁盘存储容量非常接近真实有效数据的逻辑大小。没有任何键值存储系统能够同时最小化读放大、写放大和空间放大。不同的系统只是在三者之间做出了不同的取舍LevelDB牺牲了更高的写放大后台频繁读写排序换取更低的空间放大及时清理无效数据但这极大影响了前台写入性能。WiscKey容忍更高的空间放大来将 写放大降到最低。由于 GC 可以延迟到后台空闲时再做从而最大程度减少了对前台写入性能的干扰。CPU使用率顺序写入LevelDB 消耗 CPU 更高因为 LevelDB 在将键值对写入 WAL 日志文件时需要进行复杂的编码处理CPU 开销较大。WiscKey 消耗 CPU 更低WiscKey 移除了 WAL 日志优化省去了这部分编码计算。范围查询WiscKey 消耗 CPU 显著增高因为 WiscKey 启用了 32 个后台线程进行预取数据的并行读取多线程并发导致 CPU 利用率上升。实验表明在测试环境下CPU 并不是 LevelDB 或 WiscKey 的性能瓶颈瓶颈依然在 I/O 和磁盘上。LevelDB的写入和compaction都是单线程的所以CPU消耗不高。YCSB 基准测试数据与参数数据库规模为 100 GB关闭数据压缩选取 1 KB 和 16 KB 两种 Value 大小。数据写入1 KB ValueWiscKey 速度是 LevelDB/RocksDB 的 50 倍以上最坏情况下仍快 45 倍。16 KB Value即使在最坏情况下WiscKey 也比其他两者快 104 倍。读密集型负载Workload A / B / CZipf倾斜分布热点缓存由于高频访问的热点 Key 被内存缓存减少了实际磁盘访问这一定程度缩小了 WiscKey 对比 LevelDB/RocksDB 的优势差距。读比例与优势WiscKey 在 50% 读取的 Workload-A 中优势更明显而在 95%~100% 读取的 Workload-B/C 中优势有所收窄。但在所有场景下RocksDB 和 LevelDB 的性能仍全面落后于 WiscKey。小范围查询负载Workload E该负载包含大量检索 1~100 个 KV 的小范围查询。查询每个范围的首个 Key 本质上是一次随机查找而这正是 WiscKey 的强项。因此即使在 1 KB 小 Value 场景下WiscKey 依然显著优于 RocksDB 和 LevelDB。即使常驻后台 GC最坏情况WiscKey 的整体表现依然好于 LevelDB 和 RocksDB。但 GC 机制对不同 Value 的影响侧重不同小 Value1 KB一个 4 MB 的 vLog块包含极多 Key-ValueGC 线程需要频繁查 LSM-Tree 验证每个键值对是否有效索引验证耗时开销较大。大 Value16 KB单个块内 KV 数量少验证耗时极短GC 线程会更快地向磁盘重写清理后的数据从而更直接地抢占前台写入的磁盘 I/O 吞吐。 _(注若有需要可通过限流来削弱 GC 对前台性能的影响)相关工作基于哈希表的 SSD 键值存储相关系统FAWN、FlashStore、SkimpyStash、BufferHash、SILT。技术特点采用追加写日志Log-Structure存数据在内存中构建哈希表做索引。与 WiscKey 对比虽然 WiscKey 借鉴了其追加写日志的数据布局但哈希表索引无法高效支持范围查询和快照而 WiskKey专注于开发一款功能丰富的键值存储库可适用于多种场景。LSM-Tree 的优化与演进相关系统bLSM优化 Merge 调度以稳定写入延迟VT-tree通过间接指针层规避 Compaction 中对已有序数据的重复排序LOCS暴露闪存内部通道以实现并行 CompactionAtlas分布式架构将 Key 和 Value 分开存放在不同硬盘LSM-trie使用 Trie 树组织 Key 以提升合并效率但牺牲了范围查询RocksDB做了大量多线程和内存优化但底层依然是传统 LSM-Tree 架构。与 WiscKey 对比之前的很多优化如 RocksDB与 WiscKey 的设计是正交互不冲突、可叠加的。WiscKey 采用直接的键值分离从根本上极大地降低了写放大。类似键值分离理念的混合/文件系统相关系统Walnut大对象存文件系统、IndexFS元数据用 LSM-Tree 存、Purity索引排序元数据按时间存。与 WiscKey 对比虽然思路相似但 WiscKey 的解决方案更加通用和完整并且专门针对 SSD 设备在各种复杂工作负载下的“加载”和“查找”性能做了深度优化。基于其他数据结构的键值存储相关系统TokuDB分形树/Fractal-Tree、ForestDBHB±trie 树、NVMKV结合 FTL 原生特性、Vector Interfaces批量向量接口。与 WiscKey 对比这些系统都是基于不同的数据结构它们在性能方面各自存在不同的权衡而 WiscKey 致力于直接改进应用最广泛的传统 LSM-Tree 结构。纯内存键值存储优化相关系统Masstree、MemC3、MICA、cLSM 等主要解决内存中的并发与扩展瓶颈。未来展望这些纯内存系统的并发与伸缩技术可以无缝引入并结合到 WiscKey 中以进一步提升性能。总结键值存储已经成为数据密集型应用中不可或缺的基石。在本文中我们提出了 WiscKey——一种全新的基于 LSM-Tree 的键值存储系统它通过将 Key键与 Value值分离来最小化写放大和读放大。WiscKey 的数据布局与 I/O 模式针对 SSD 设备进行了深度优化。我们的实验结果表明WiscKey 能显著提升绝大多数工作负载下的性能。我们希望 WiscKey 中的键值分离技术及各项优化手段能为下一代高性能键值存储系统的设计带来启发。
WiscKey介绍WiscKey是一篇发表于存储领域顶尖学术会议 FAST 16 的里程碑式论文WiscKey: Separating Keys from Values in SSD-Conscious Key-Value Stores由威斯康星大学麦迪逊分校UW-Madison的 ADSL 实验室提出。LSM-Tree的局限LSM-Tree 诞生于HDD时代HDD 的随机读写比顺序读写慢 100 倍以上因此用多次顺序读写来换取后续高效查询的代价是划算的。这会带来IO放大现代 SSD 具有随机与顺序性能差距小、内部并行度高以及有擦写寿命限制的特点。继续采用传统 LSM-Tree 架构会导致 SSD 吞吐量下降高达 90%无法释放SSD的真正性能。WiscKeyWiscKey将 Key 和 Value 分离存储Key 依然在 LSM-Tree 中排序管理而 Value 提取出来单独保存在日志文件中。通过避免排序过程中不必要的值移动显著降低写放大效应同时 LSM 树的规模明显减小从而减少磁盘读取次数提升查询时的缓存效率。键值分离后带来了新的难题WiscKey 提出了对应的优化方案范围查询变慢因为 Value 不再按 Key 的顺序物理存储。解法充分利用现代 SSD 强大的内部并发读取能力来提升 Scan 性能。空间回收无效/旧版本的 Value 需要被清理。解法设计轻量级的在线 GC 机制全过程仅包含顺序 I/O对前台读写性能影响极小。崩溃一致性分离存储后如何保证crash时数据一致性保证。解法利用现代文件系统追加写入在crash的时候不会产生垃圾的特性提供与 LevelDB 完全相同的强一致性保证。性能提升LevelDB的Microbenchmarks加载数据库比 LevelDB 快 2.5× – 111×随机查询比LevelDB块1.6×–14×随机写入小 Value和大型数据集顺序scan比LevelDB性能差YCSBWiscKey在全部六种 YCSB 工作负载中均优于LevelDB和RocksDB读放大和写放大写读放大率定义为写入从底层存储设备的数据量与用户请求的数据量之比。写放大写放大来源在 Compaction过程中需要读取一个LiL_iLi的SSTable和最多10个Li1L_{i1}Li1的SSTable。数据每跨越一层写放大最高可达 10 倍。对于有很多数据的db新生成的SSTable最终都会通过一系列 Compaction 从L0L_0L0一步步迁移至L6L_6L6。在这个过程中写放大逐层累加总写放大可以超过 50 倍。在图2中1 GB数据量下写放大为 3.1100GB时写放大为14。原因分析数据量变大后数据更有可能从低层级一步步向下压缩迁移至高层级从而被反复重写多次。读放大读放大的来源为了查找一个 Key-Value 对LevelDB 可能需要检索多个Level的文件。SSTable内部LevelDB 无法直接精准读取数据块必须同时读取多个元数据块Index BlockBloom Filter BlockData Block\text{Index Block} \text{Bloom Filter Block} \text{Data Block}Index BlockBloom Filter BlockData Block。例如查找一个1KB的键值对时LevelDB需读取16KB的索引块、4KB的布隆过滤器块和4KB的数据块总计24KB。因此在最坏情况下考虑全部14个SSTable文件时LevelDB的读取放大量为24×14336。对于较小的键值对读取放大效应会更为显著。在图2中1 GB数据量下读放大为8.2100GB时读放大为327。原因分析对于小数据量Index Block 和 Bloom Filter 可以完全被内存 Cache 缓存但对于 100 GB 的大数据量内存装不下全部索引每次查询都会去读取不同 SSTable 文件的 Index Block 和 Bloom Filter导致读放大扩大。SSD和LSM-Tree与机械硬盘类似出于其独特的“先擦除再写入”循环以及高昂的垃圾回收GC开销随机写入在 SSD 中同样会导致性能下降。这就使得LSM-Tree同样很适合用在SSD上。但是与 HDD 不同SSD 拥有极佳的随机读性能和内部高并发能力。单线程随机读只要请求粒度变大如 256 KB吞吐量即可达到顺序读的一半。多线程并发随机读通过多线程如 32 线程并发发起随机读当请求大小≥\ge≥16 KB 时吞吐量可以完全媲美顺序读。WiscKey方案设计设计目标WiscKey是从Leveldb派生而来的单机持久化kv存储。提供和Leveldb一样的APIPutGetDeleteScan。WiscKey的设计目标有下面几个降低写放大严重的写放大会导致如下问题消耗大部分SSD带宽资源同时因为SSD擦除次数有限写放大同样会缩短固态硬盘的使用寿命。降低读放大较高的读放大会导致如下问题每次查询都需要执行多次读取操作导致查询吞吐量显著降低其次大量数据被加载到内存中会降低缓存的使用效率。针对 SSD 进行优化WiscKey 通过将其 I/O 模式与 SSD 设备的性能特性相匹配针对 SSD 设备进行了深度优化。它有效地利用了顺序写入和并发随机读取从而能够充分利用SSD的带宽。丰富的API支持WiscKey 旨在支持使 LSM-Tree 流行起来的那些现代特性例如范围查询和快照。更好支持实际场景key-value大小在现代工作负载中Key 的大小通常较小例如 16 字节而 Value 的尺寸差异很大例如从 100 字节到大于 4 KB 不等。WiscKey 旨在针对这种贴近实际应用的键值尺寸组合提供出色的性能。kv分离方案引入kv分离的原因LSM-Tree的性能开销主要是在compaction过程。compaction需要对多个SSTable进行排序多个SSTable的内容会读入到内存中排序后在写入SSTable。这会占用很多的磁盘带宽。但是这个排序对于检索kv很重要不能去掉。WiscKey的解决方案来源于识别到compaction只要求对key进行排序但是value可以进行单独的存储管理。这其实需要基于一个数据模型是key比vlaue小很多如果key比value大很多的话就没必要进行kv分离了。WiscKey的kv分离存储WiscKey 只在 LSM-Tree 中存放 Key 和 Value 的物理地址而将真实的 Value 追加保存在单独的日志文件vLog。数据操作流程写入value先写入vLog中然后将key和value的addrvLog-offset, value-size)写入LSM-Tree中。删除删除直接再LSM-Tree中删除对应的key不会操作vLog中的value。没有LSM-Tree中的key引用的vLog数据是无效的后续通过GC处理。查询先查询LSM-Tree然后根据addr查询对应的valuekv分离带来的好处显著降低LSM-Tree的大小。降低LSM-Tree的写放大。假设 Key 为16 B16\text{ B}16BValue 为1 KB1\text{ KB}1KB(1024 B1024\text{ B}1024B) LSM-Tree的写放大为 10而vLog追加写 Value的写放大为 1WiscKey 的有效写放大10×161024161024≈1.14\text{WiscKey 的有效写放大} \frac{10 \times 16 1024}{16 1024} \approx \mathbf{1.14}WiscKey的有效写放大16102410×161024≈1.14。写放大降低后可以有效提高SSD的寿命。kv分离对点查的影响对于一次读需要先读取LSM-Tree获取到value的addr然后再根据addr的地址从VLog读取value。这比Leveldb多一次磁盘IO这会导致读比Leveldb慢。但是因为LSM-Tree中只存储了value的addr这会降低LSM-Tree的大小可以使得LSM-Tree的数据都缓存到内存中那么WiscKey的读取只需要一次磁盘IO这就比Leveldb的读取操作要快了。kv分离场景下的扫描应该是比Leveldb要慢的因为value是无序的状态。kv分离带来的挑战kv分流带来了以下挑战范围查询需要随机IO需要引入垃圾回收需要处理崩溃恢复时的数据一致性范围查询范围查询的问题在LevelDB中键值被共同存储并排序范围查询可顺序从SSTable文件中读取键值对。然而由于WiscKey中键值是分别存储的范围查询需要随机读取数据这会降低范围查询的速度。在SSD中单线程的随机读取性能时比不上顺序读取性能的但是对于请求数据较大的并行随机读取性能时能媲美顺序读取性能的。解决方案并发从SSD中进行预读。范围查询时一次获取多个key和key对应的addr然后并发的获取多个addr对应的value来提高范围查询的性能。针对预读的API改造识别到用户需要连续读取数据后Next()或Prev()操作从LSM-Tree中顺序读取多个key-addr然后将addr写入到队列中后台多线程并发读取队列中的addr对应的value写入缓存中。GC引入GC原因基于标准 LSM 树的键值存储结构在删除或覆盖键值对时并不会立即释放空闲空间。而是在compaction过程中如果发现与已删除或被覆盖的键值对相关的数据则该数据将被丢弃并释放空间。在WiscKey中compaction只会对key进行回收但是value在compaction的过程中不会回收。所以需要一个单独的GC来对vLog中的无效空间进行回收。解决方案一种简单的回收vLog中空闲空间的方法是首先扫描 LSM 树获取所有有效的值地址随后将vLog中未被 LSM 树引用的value视为无效并予以回收。但是该方法耗时过长仅适用于离线垃圾回收场景。WiscKey的解决方法在将值存储于vLog时同时会一并存储对应的key。vLog的存储格式如下图WiskSec的GC的目标是将有效值保留在vLog的连续范围内。该范围的一端称为head始终对应vLog的末尾位置新的数据值将被追加在这个地方另一端称为tail则是垃圾回收机制触发时开始释放空间的位置。只有位于头部与尾部之间的vLog段包含有效数据并会在查询过程中被检索。GC流程WiscKey的GC流程从vLog的tail读取一大块键值对例如数兆字节通过查询LSM-Tree来找出其中有效的key-value对将有效的key-value对搬移到head更新tail释放空间为了防止数据丢失WiscKey必须确保新添加的有效值及新的尾部数据在实际释放空间之前均能持久保存于磁盘上。WiscKey通过下面的手动来保证数据不丢失在将有效值写入到vLog后对vLog调用fsync()函数进行落盘将新的vlaue address和tailtail格式‘‘tail’’, tail-vLog-offset.以同步方式记录到LSM-Tree中。最后再释放空间GC执行时机WiscKey 可以配置为定期启动并持续执行GC或者达到特定阈值时触发。垃圾回收也可以在离线维护模式下运行。崩溃恢复时的数据一致性背景在系统崩溃时 LSM 树实现机制通常能保证插入的键值对具有原子性并确保插入对能够按顺序恢复。由于WiscKey架构将数值与 LSM 树分开存储要实现相同的崩溃保障机制可能会较为复杂键值对的原子性很难保证。WiscKey通过利用现代文件系统如ext4、btrfs和xfs的一个重要特性来提供相同的保障若vLog中的某个值X在崩溃时丢失则所有后续插入的值也会一同丢失。数据一致性的实现用户查询kv对时的数据一致性保证如果无法在 LSM 树中找到该key则其行为与传统 LSM 树完全一致。如果value已经写入到vLog中了对应的value会再GC中进行回收如果能在 LSM 树中找到该键则需额外步骤以确保数据一致性WiscKey首先验证从 LSM 树获取的值地址是否处于vLog当前有效范围内。确认所得值是否与查询键一致通过vLog中保存的key和LSM-Tree中的key进行对比。如果不一致那么就从LSM-Tree中删除key。LSM 树还支持用户明确请求同步插入操作来保证数据持久性。WiscKey通过在向 LSM 树执行同步插入前flush vLog到磁盘上来实现这一功能。优化vLog写缓存对于每次Put()操作WiscKey都需要通过write()系统调用将数据值追加到vLog中。然而在以插入操作为主的业务场景下向文件系统发起大量小数据写入会带来显著的系统开销。为降低系统开销WiscKey会在用户空间缓冲区中缓存数据值仅当缓冲区大小超过阈值或用户请求同步写入时才将缓存区的数据刷入磁盘中。在数据查询时WiscKey首先会在vLog缓冲区中查找。这种机制可能导致部分缓存的数据在系统崩溃时丢失。缓存区要预分配vLog的offest保证缓存按照顺序写入vLog。LSM-Tree WAL日志优化在WiscKey中 vLog会记录已插入的kv以支持垃圾回收机制。因此 LSM-Tree的WAL日志就可以无损去除了。crash后可以通过扫描vLog来进行恢复。为了减少扫描vLog的范围WiscKey会定期将vLog的head作为键值对‘’head‘’head-vLog-offset记录在 LSM 树中。当数据库启动或重新打开时WiscKey 从 LSM-Tree 中记录的最新head位置开始向后顺序扫描vLog直到vLog文件的末尾恢复出其中的kv对。由于 LSM-Tree 本身能够保证其中记录的 Key 恢复时严格满足按插入顺序恢复的特性因此基于 LSM-Tree 中的 head 结合 vLog 扫描来进行恢复是可以保证数据一致性的。这个会导致db recover的时间变长因为再kv分离的场景下vLog的存储包括valueWAL中只包括key和value的addr读取的空间会比WAL日志的大。实现WiskKey基于LevelDB 1.18版本开发。WiskSec在创建新数据库时创建vLog并在LSM-Tree中管理key和value的addr。vLog 在内部会被具有不同访问模式的多个组件同时访问。例如查询操作通过随机读取 vLog来完成而GC则是从 vLog 文件的tail顺序读取并追加写入到head。我们使用posix_fadvise()来预先声明对 vLog的访问模式。对于范围查询WiscKey 维护了一个包含 32 个线程的后台线程池。这些线程在一个线程安全的队列上休眠等待新的 Value 地址到来。当预读被触发时WiscKey 会将固定数量的 Value 地址插入到工作队列中并唤醒所有休眠的线程。这些线程随后开始并行读取 Value并将它们缓存到 Buffer Cache中。为了高效地回收vLog 释放出的空间我们使用了现代文件系统的打孔Hole-punching功能通过fallocate()系统调用实现。可以在不改变文件总体偏移量的前提下把vLog头部被 GC 掉的无效数据区的物理磁盘块释放掉还给操作系统。现代文件系统支持的最大单文件体积足够大足以让 WiscKey 运行很长时间而无需回绕至文件开头例如ext4 的最大文件大小为 64 TBxfs 为 8 EBbtrfs 为 16 EB。如果有需要vLog也很容易改编为循环日志的形式。性能评估所有实验均在一台测试机器上运行该机器配备了两颗 Intel® Xeon® CPU E5-2667 v2 3.30GHz 处理器和 64 GB 内存。操作系统为 64 位 Linux 3.14使用的文件系统是 ext4。所用的存储设备为一块 500 GB 的三星 840 EVO SSD其顺序读取和顺序写入的最大性能分别为 500 MB/s 和 400 MB/s。Microbenchmarks我们使用db_benchLevelDB 中默认的微基准测试工具来评估 LevelDB 和 WiscKey 的性能。在所有实验中我们统一将 Key 的大小设为 16 字节但针对不同的 Value 大小进行了多组实验。为了更便于理解和分析性能我们禁用了数据压缩功能。写入性能下面是顺序写入和随机写入微基准测试的结果。前者通过按顺序插入 Key 来构建一个 100 GB 的数据库而后者则以均匀分布的随机顺序插入 Key。需要注意的是顺序写入在 LevelDB 或和WiscKey 中都不会触发 Compaction而随机写入则会触发。顺序写入性能Figure 7显示顺序写的场景下LevelDB和WhisKey的吞吐量均随数据值大小的增加而提升。但是在最大的value大小下LevelDB的吞吐量也没有达到磁盘的带宽。Figure 8显示了LevelDB中各组件所耗时间的分布情况。时间主要消耗在三个主要环节向日志文件写入数据、向内存表插入数据以及等待memtable刷盘到SSTable。对于小value而言写入日志文件所占总耗时比例最高对于大value等待memtable刷盘到SSTable则是性能瓶颈。与LevelDB不同WiscKey在处理超过4KB的数据量时可充分利用磁盘的全部带宽。由于它既不写 LSM-Tree日志同时在写vLog时使用Buffer缓存因此即使处理较小的value时速度也提升至原来的3倍。随机写入性能图9展示了LevelDB和WiscKey在不同value大小下的随机写入吞吐量。LevelDB的吞吐量范围从仅2 MB/s64字节值大小到4.1 MB/s256 KB值大小。WiskSec的吞吐量随value大小增加而提升在数据值大于4 KB时达到磁盘写入瓶颈。WiskSec的吞吐量是LevelD的 46倍到111倍。LevelDB的吞吐量较低是因为compaction不仅会消耗很大一部分磁盘带宽还会减慢前台写入操作以控制LSM-Tree L0层的增长速度compaction成为系统瓶颈。图10对比了LevelDB和WhisKey在随机写入下的写放大。LevelDB的写放大始终大于12而当value的大小达到1KB时WiscKey的写放大迅速降至接近1。查询性能下面将比较LevelDB与WiscKey在随机查找和范围查询方面的性能表现。随机查找性能运行负载在随机写入100GB的数据后进行100000次随机查询。结果分析对于1 KB的valueWiscKey的吞吐量是LevelDB的12倍而对于较大的valueWiscKey的吞吐量仅受限于磁盘的随机读取吞吐量如图 3 所示。LevelDB的吞吐量较低这是由于其较高的读放大和compaction占用磁盘带宽所导致的。范围查询性能随机写入的场景LevelDB会从不同层级读取多个文件而WiscKey则需要对vLog进行随机访问但WiscKey利用了并行随机读取技术。LevelDB的吞吐量最初随数据库值大小的增加而提升。然而当value超过4 KB时由于SSTable文件仅能存储少量键值对其开销主要源于需要打开多个SSTable文件并读取每个文件中的索引块和布隆过滤器。WiscKey分析。对于较大的valueWiscKey可以达到磁盘的顺序读取带宽最高可达LevelDB的8.4倍。然而在64字节的value下WiscKey的性能比LevelDB差12倍这是由于达到了SSD并发请求的上限。顺序写入的场景其性能表现与随机写入的场景呈现相同趋势。64字节的value大小下WiscKey的速度比其他value大小慢25%原因是WiscKey需要同时从LSM-Tree和vLog中读取数据。但对于大valueWiscKey的速度则快2.8倍。因此对于小value通过对vLog排序可使WiscKey的范围查询性能达到与LevelDB相当的水平。GC下面开发分析在后台执行垃圾回收时WiscKey的性能表现。性能会受到空闲空间百分比的影响因为这会影响GC线程写入的数据量以及释放的空间量。性能测试步骤和负载性能测试具体包含三个步骤我们通过随机写创建一个数据库删除所需比例的kv对运行随机写负载程序并且在后台GC的同时测量其吞吐量使用 4 KB 的键值对大小并将空闲空间百分比从 25% 到 100% 进行变动。性能结果与原因100% 空闲空间吞吐量仅下降 10%。原因GC 只需从 vLog 尾部顺序读取无需向头部重写任何有效数据写开销为 0。其他比例25%~75%吞吐量下降约 35%。原因GC 线程需要把未被删除的有效数据重新写回 vLog head抢占了部分写入带宽。崩溃恢复时的一致性验证和耗时一致性验证背景与工具由于键值分离机制增加了维护一致性的难度论文使用了专业的崩溃验证工具ALICE进行了系统性测试。测试方法在 ext4、xfs 和 btrfs 文件系统上运行异步和同步的 Put() 请求同时通过ALICE 模拟了超过 3000 种可能触发数据不一致的系统崩溃场景。结果ALICE 未发现由 WiscKey 引入的任何一致性漏洞证明其一致性机制安全可靠。崩溃恢复耗时1 KB Value 场景下LevelDB 的恢复时间为 0.7 秒。WiscKey 的恢复时间为 2.6 秒比 LevelDB 稍慢。%% 随着value变大需要读取的vLog也会变大那么WiscKey的恢复时间会变的更长 %%。空间放大空间放大是指磁盘上存储的实际大小与用户写入的数据大小之比。压缩可降低空间放大而额外数据如垃圾数据、碎片或元数据则会加大空间放大。为简化讨论本文未启用压缩功能。对于顺序写入场景空间放大倍数可接近1因为 LSM-Tree中额外的元数据量极小。对于随机写入和覆盖写入当无效kv未能被快速地回收时空间放大倍数通常大于1。LevelDB空间放大来源来自于尚未被Compaction清理的旧/无效 Key-Value 键值对。WiscKey空间放大来源包含两部分vLog 中未被 GC 清理的无效 KV。键值分离带来的额外元数据开销即 LSM-Tree 中存储的 Value 指针/Offset以及 vLog中记录的 Header 元数据。当存入的 Value 相对较大时元数据占比微乎其微经过 GC 后的 WiscKey 磁盘存储容量非常接近真实有效数据的逻辑大小。没有任何键值存储系统能够同时最小化读放大、写放大和空间放大。不同的系统只是在三者之间做出了不同的取舍LevelDB牺牲了更高的写放大后台频繁读写排序换取更低的空间放大及时清理无效数据但这极大影响了前台写入性能。WiscKey容忍更高的空间放大来将 写放大降到最低。由于 GC 可以延迟到后台空闲时再做从而最大程度减少了对前台写入性能的干扰。CPU使用率顺序写入LevelDB 消耗 CPU 更高因为 LevelDB 在将键值对写入 WAL 日志文件时需要进行复杂的编码处理CPU 开销较大。WiscKey 消耗 CPU 更低WiscKey 移除了 WAL 日志优化省去了这部分编码计算。范围查询WiscKey 消耗 CPU 显著增高因为 WiscKey 启用了 32 个后台线程进行预取数据的并行读取多线程并发导致 CPU 利用率上升。实验表明在测试环境下CPU 并不是 LevelDB 或 WiscKey 的性能瓶颈瓶颈依然在 I/O 和磁盘上。LevelDB的写入和compaction都是单线程的所以CPU消耗不高。YCSB 基准测试数据与参数数据库规模为 100 GB关闭数据压缩选取 1 KB 和 16 KB 两种 Value 大小。数据写入1 KB ValueWiscKey 速度是 LevelDB/RocksDB 的 50 倍以上最坏情况下仍快 45 倍。16 KB Value即使在最坏情况下WiscKey 也比其他两者快 104 倍。读密集型负载Workload A / B / CZipf倾斜分布热点缓存由于高频访问的热点 Key 被内存缓存减少了实际磁盘访问这一定程度缩小了 WiscKey 对比 LevelDB/RocksDB 的优势差距。读比例与优势WiscKey 在 50% 读取的 Workload-A 中优势更明显而在 95%~100% 读取的 Workload-B/C 中优势有所收窄。但在所有场景下RocksDB 和 LevelDB 的性能仍全面落后于 WiscKey。小范围查询负载Workload E该负载包含大量检索 1~100 个 KV 的小范围查询。查询每个范围的首个 Key 本质上是一次随机查找而这正是 WiscKey 的强项。因此即使在 1 KB 小 Value 场景下WiscKey 依然显著优于 RocksDB 和 LevelDB。即使常驻后台 GC最坏情况WiscKey 的整体表现依然好于 LevelDB 和 RocksDB。但 GC 机制对不同 Value 的影响侧重不同小 Value1 KB一个 4 MB 的 vLog块包含极多 Key-ValueGC 线程需要频繁查 LSM-Tree 验证每个键值对是否有效索引验证耗时开销较大。大 Value16 KB单个块内 KV 数量少验证耗时极短GC 线程会更快地向磁盘重写清理后的数据从而更直接地抢占前台写入的磁盘 I/O 吞吐。 _(注若有需要可通过限流来削弱 GC 对前台性能的影响)相关工作基于哈希表的 SSD 键值存储相关系统FAWN、FlashStore、SkimpyStash、BufferHash、SILT。技术特点采用追加写日志Log-Structure存数据在内存中构建哈希表做索引。与 WiscKey 对比虽然 WiscKey 借鉴了其追加写日志的数据布局但哈希表索引无法高效支持范围查询和快照而 WiskKey专注于开发一款功能丰富的键值存储库可适用于多种场景。LSM-Tree 的优化与演进相关系统bLSM优化 Merge 调度以稳定写入延迟VT-tree通过间接指针层规避 Compaction 中对已有序数据的重复排序LOCS暴露闪存内部通道以实现并行 CompactionAtlas分布式架构将 Key 和 Value 分开存放在不同硬盘LSM-trie使用 Trie 树组织 Key 以提升合并效率但牺牲了范围查询RocksDB做了大量多线程和内存优化但底层依然是传统 LSM-Tree 架构。与 WiscKey 对比之前的很多优化如 RocksDB与 WiscKey 的设计是正交互不冲突、可叠加的。WiscKey 采用直接的键值分离从根本上极大地降低了写放大。类似键值分离理念的混合/文件系统相关系统Walnut大对象存文件系统、IndexFS元数据用 LSM-Tree 存、Purity索引排序元数据按时间存。与 WiscKey 对比虽然思路相似但 WiscKey 的解决方案更加通用和完整并且专门针对 SSD 设备在各种复杂工作负载下的“加载”和“查找”性能做了深度优化。基于其他数据结构的键值存储相关系统TokuDB分形树/Fractal-Tree、ForestDBHB±trie 树、NVMKV结合 FTL 原生特性、Vector Interfaces批量向量接口。与 WiscKey 对比这些系统都是基于不同的数据结构它们在性能方面各自存在不同的权衡而 WiscKey 致力于直接改进应用最广泛的传统 LSM-Tree 结构。纯内存键值存储优化相关系统Masstree、MemC3、MICA、cLSM 等主要解决内存中的并发与扩展瓶颈。未来展望这些纯内存系统的并发与伸缩技术可以无缝引入并结合到 WiscKey 中以进一步提升性能。总结键值存储已经成为数据密集型应用中不可或缺的基石。在本文中我们提出了 WiscKey——一种全新的基于 LSM-Tree 的键值存储系统它通过将 Key键与 Value值分离来最小化写放大和读放大。WiscKey 的数据布局与 I/O 模式针对 SSD 设备进行了深度优化。我们的实验结果表明WiscKey 能显著提升绝大多数工作负载下的性能。我们希望 WiscKey 中的键值分离技术及各项优化手段能为下一代高性能键值存储系统的设计带来启发。
在AI编程中的实践与优化)
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
