WiscKey Separating Keys from Values in SSD conscious Storage

论文下载地址

摘要

针对 SSD 硬盘,在 LSM-tree 的基础上优化了写放大问题,获得了更好的顺序和随机读写性能,思路就是在 LSM-tree 上把 key 和 value 的分离存储。最后吹了一下牛逼 WiscKey is 2.5×–111× faster than LevelDB for load-ing a database and 1.6×–14× faster for random lookups.WiscKey is faster than both LevelDB and RocksDB in all six YCSB workloads.

1 简介

现在 key-value 类型数据库在对写性能要求比较高的场景中扮演越来越重要的角色,为了获得更好的写入性能,一般采用Log-Structured Merge-Tree (LSM-tree)。我们知道 LSM-tree 是一种基于硬盘的数据结构,与 B+ tree 相比,能显著地减少硬盘磁盘寻道开销,并能在较长的时间提供对文件的高速插入(删除)。然而 LSM-tree 在某些情况下,特别是在查询需要快速响应时性能不佳。 B+ tree 最大的性能题问是会发生大批的随机 I/O,随着新数据的插入,叶子节点会发生分裂,逻辑上连续的叶子点节在物理上往往不连续,甚至分离的很远,范围查询时,会发生大量随机读。对于大量的随机写也一样,比如:插入 key 跨度很大 7->1000->3->2000 … 新插入的数据存储在磁盘上相隔很远,会发生大量的随机写 I/O。所以 B+ tree 无论是在 SSD 还是 HDD 上都很难获得高性能。既然随机写是性能杀手,所以 LSM-tree 的核心思想就是将写入推迟(Defer)并转换为批量(Batch)写,首先将大量写入缓存在内存,当积累到一定程度后,将他们批量写入文件中,只要一次 I/O 就可以进行多条数据的写入,充分利用每一次 I/O。

Unfortunately, standard disk-based index structures such as the B-tree will effectively double the I/O cost of the transaction to maintain an index such as this in real time, increasing the total system cost up to fifty percent.

The Log-Structured Merge-tree (LSM-tree) is a disk-based data structure designed to provide low-cost indexing for a file experiencing a high rate of record inserts (and deletes) over an extended period.

为了保证写性能,LSM-tree 会不停的批量把 key-value pairs 写入文件;为了保证读性能,LSM-tree 还需要不停的做后台 compaction,把这些文件合并成单个按 Key 有序的文件。这就导致了相同的数据在它的生命期中被反复读写。 LSM-tree 系统中数据的 I/O 放大系数可能会达到50倍以上。

由于 LSM-tree 在设计的时候主要针对的是 HDD 硬盘,在 HDD 上随机 I/O 比顺序 I/O 慢 100 倍。但在 SSD上就有了很大的区别:

  1. 顺序 I/O 和随机 I/O 的差别没那么大,这让 LSM-tree 为了减少随机 I/O 而付出的额外的 I/O 变得不再必要。
  2. SSD 可以承受高并发的 I/O,而 LSM-tree 利用的并不好。
  3. 长期大量的重复写会影响 SSD 的性能和寿命。

综合以上原因 LSM-tree 在 SSD 上会损失90%的吞吐,并增加10倍的写负载

WiscKey 针对 SSD 存储改进了 LSM-Tree,其核心思想是分离 key 和 value,只在 LSM-tree 中维护 key,把 value 放在 log 中。这样 key 的排序和 value 的 GC 就分开了,在排序时避免了 value 的写放大,整个LSM-tree 更小,cache 效率更高。

分离 key 和 value 带来的挑战:

  1. key value 分离,scan 操作从顺序读变成了顺序读加多次随机读,从而变得低效。解决办法:利用 SSD 并行 I/O 的能力 using the abundant internal parallelism of SSD devices
  2. 垃圾回收。Compaction 过程需要被删除的数据由于只是删除了key,value还保留在分开的日志中,这就需要异步的回收。解决办法:采用在线轻量 GC,减少对前台负载的影响。WiscKey proposes an online and lightweight garbage collector which only involves sequential I/Os and impacts the foreground workload minimally
  3. crash 数据一致性。解决办法:是在启动时对 key, value 进行检查:1. key 成功写入,value 没有,则从 LSM-tree 中删除 key,并返回不存在。2. key 没有成功写入,value 写入,返回不存在,并在后续的垃圾回收中清除 value。WiscKey leverages an interesting property in modern file systems, that appends never result in garbage data on a crash

通过对 SSD 的优化 WiscKey 获得了远超 LevelDB 和 RocksDB 的性能,除了大范围的扫描情况下的小数据随机写。

We compare the performance of WiscKey with LevelDB and RocksDB , two popular LSM-tree key-value stores. For most workloads, WiscKey performs significantly better. With LevelDB’s own microbenchmark, WiscKey is 2.5×–111× faster than LevelDB for loading a database, depending on the size of the key-value pairs; for random lookups, WiscKey is 1.6×–14× faster than LevelDB. WiscKey’s performance is not always better than standard LSM-trees; if small values are written in random order, and a large dataset is range-queried sequentially, WiscKey performs worse than LevelDB.

2 背景与动机

2.1 Log-Structured Merge-Tree

LSM-tree 作为 key-value 存储引擎的主流数据结构,在写入和删除上很好的性能表现。我们可以看到在 LSM-tree 中插入一个 key-value 对至少需要5步:

  1. 写入日志文件
  2. 写入 memtable
  3. 写入 immutable memtable
  4. 写入 SSTable L0
  5. compacted to further levels

LSM-tree 用多次的顺序 I/O 来避免随机 I/O,从而在 HDD 磁盘上获得比 B+ 树高得多的写性能。读的时候,LSM-tree 需要在所有可能包含这个 key 的 memtable 和文件中查找, 与 B+ 树相比,多了很多 I/O。因此LSM-tree 适合于写多读少的场景。

2.2 LevelDB

LevelDB 的架构如下:

LevelDB 中主要由以下几个重要的部件构成:

memtable

之前提到,LevelDB 的一次写入操作并不是直接将数据刷新到磁盘文件,而是首先写入到内存中作为代替,memtable就是一个在内存中进行数据组织与维护的结构。memtable 中,所有的数据按用户定义的排序方法排序之后按序存储,等到其存储内容的容量达到阈值时(默认为4MB),便将其转换成一个不可修改的memtable,与此同时创建一个新的 memtable,供用户继续进行读写操作。memtable 底层使用了一种跳表数据结构,这种数据结构效率可以比拟二叉查找树,绝大多数操作的时间复杂度为O(log n)。

immutable memtable

memtable 的容量到达阈值时,便会转换成一个不可修改的 memtable,也称为 immutable memtable。这两者的结构定义完全一样,区别只是 immutable memtable是只读的。当一个 immutable memtable 被创建时,LevelDB 的后台压缩进程便会将利用其中的内容,创建一个 sstable,持久化到磁盘文件中。

log

LevelDB 的写操作并不是直接写入磁盘的,而是首先写入到内存。假设写入到内存的数据还未来得及持久化,leveldb进程发生了异常,抑或是宿主机器发生了宕机,会造成用户的写入发生丢失。因此 LevelDB 在写内存之前会首先将所有的写操作写到日志文件中,也就是 log 文件。当以下异常情况发生时,均可以通过日志文件进行恢复:

  1. 写 log 期间进程异常;
  2. 写 log 完成,写内存未完成;
  3. write 动作完成(即 log、内存写入都完成)后,进程异常;
  4. Immutable memtable 持久化过程中进程异常;
  5. 其他压缩异常;

当第一类情况发生时,数据库重启读取 log 时,发现异常日志数据,抛弃该条日志数据,即视作这次用户写入失败,保障了数据库的一致性;

当第二类,第三类,第四类情况发生了,均可以通过 redo 日志文件中记录的写入操作完成数据库的恢复。

每次日志的写操作都是一次顺序写,因此写效率高,整体写入性能较好。

此外,LevelDB 的用户写操作的原子性同样通过日志来实现。

sstable

虽然 LevelDB 采用了先写内存的方式来提高写入效率,但是内存中数据不可能无限增长,且日志中记录的写入操作过多,会导致异常发生时,恢复时间过长。因此内存中的数据达到一定容量,就需要将数据持久化到磁盘中。除了某些元数据文件,LevelDB 的数据主要都是通过 sstable 来进行存储。

虽然在内存中,所有的数据都是按序排列的,但是当多个 memetable 数据持久化到磁盘后,对应的不同的sstable 之间是存在交集的,在读操作时,需要对所有的 sstable 文件进行遍历,严重影响了读取效率。因此LevelDB 后台会定期整合这些 sstable 文件,该过程也称为 compaction。随着 compaction 的进行,sstable 文件在逻辑上被分成若干层,由内存数据直接 dump 出来的文件称为 level 0 层文件,后期整合而成的文件为level i 层文件,这也是 LevelDB 这个名字的由来。注意,所有的 sstable 文件本身的内容是不可修改的,这种设计哲学为 LevelDB 带来了许多优势,简化了很多设计

2.3 读写放大

读写放大是采用 LSM-tree 结构作为存储引擎的主要问题。接下来我们将分析 LevelDB 中的读写放大问题。

写放大:文件从$L_{i-1}$到$L_i$的过程中,因为两层的 size limit 差10倍,因此这次 Compaction 的放大系数最大可以到10。这样从L0到L6的放大系数可以达到50(L1-L6每层10)。

读放大:假设L0有8个文件,那么查找时最多需要读14个文件(L1-L6每层最多1个文件);假设要读1KB的数据,那么每个文件最多要读24KB的数据(index block + bloom-filter blocks + data block)。这么算下来读的放大系数就是14*24=336。如果要读的数据更小,这个系数会更大。

LSM-tree 的这种设计是为了在 HDD 磁盘上获得更好的性能。HDD 磁盘的一组典型数据是寻址10ms,吞吐100MB/s,而顺序读下一个 Block 的数据可能只要10us,与寻址相比延时是1:1000,因此只要 LSM-tree 的写放大系数不超过1000,就能获得比 B+ 树更好的性能。而 B+ 树的读放大也不低,比如读1KB的数据,B树可能要读6个4KB的 Block,那么读放大系数是24,没有完全拉开和 LSM-tree 的差距。

2.4 快速存储设备

SSD 上仍然不推荐随机写,因为 SSD 的整块擦除再写以及代价高昂的回收机制,当SSD上预留的 Block 用光时,它的写性能会急剧下降。LSM-tree 的最大化顺序写的特性很适合 SSD。但与 HDD 非常不同的是,SSD 的随机读性能非常好,且支持高并发。

3 WiscKey

WickKey 的设计出发点就是如何利用上 SSD 的新特性:

  1. key 与 value分离,key 由 LSM-tree 维护,而 value 则写入单独的日志文件。
  2. 鉴于 value 不再排序,WiscKey 在读的时候会并发随机读。
  3. WiscKey 在 value log 的管理上有自己的一致性和回收机制。
  4. WiscKey 去掉 LSM-tree 的 logfile 后仍然能保证一致性,并且能够优化小文件写入的性能。

3.1 设计目标

WiscKey 源自于 LevelDB,可以作为关系型数据库(MySQL..)和分布式KV数据库(MongoDB…)的存储引擎,并且兼容LevelDB 的API。

设计目标:

  1. 低写放大:既为了写性能,也为了SSD的寿命。
  2. 低读放大:读放大会降低读的吞吐,同时还降低了cache 效率。
  3. SSD 优化。
  4. 丰富的 API。
  5. 针对实际的 key-value 大小设计。

3.2 key value 分离

既然排序的只是 key,value 完全可以另行处理。通常 key 要比 value 小很多,那么排序 key 的开销也就比 value要小很多。WiscKey 中 key 放在一起的只是 value 的 offset( <vLog-offset, value-size> ),value 本身存放在其它地方。

查找的时候,WiscKey 先在 LSM-tree 中查找 key,再根据 key 中 valu e的 offset 查找 value。因为WiscKey 中的 LSM-tree 比 LevelDB 中的小很多,前面的查找会快很多,大部分情况下直接命中 cache,这样整个开销就是一次随机查找。而 SSD 的随机查找性能又这么好,因此 WiscKey 的读性能就比 LevelDB 好很多。

插入 key value 时,WiscKey 先把 value 写入 vLog,然后再把 key 插入到 LSM-tree 中。删除 key 则只从 LSM-tree 中删除它,不需要删除 vLog。

3.3 挑战

3.3.1 并发范围查找

LevelDB 中 key 和 value 存放在一起,seek 一遍然后底层就只有顺序I/O。WiscKey 中 key 和 value 分开存储范围查找带来大量随机读,严重影响性能。WiscKey 对 range query 进行了并发读的优化,具体的做法是:

  1. 对于 range query,同时取出多个 ke y的元数据信息<key, address>
  2. 将这些<key,address>信息放入队列,并唤醒预读线程(默认32个)
  3. 预读线程开始读数据

从上图可以看到在读取数据量达到16kb以上的时候,32线程的随机读吞吐量=顺序读,基本把 SSD 的带宽跑满。

3.3.2 垃圾回收

LevelDB 等之类 LSM-tree 的存储系统对于对象的删除只是追加删除标记,延期至 sstable compaction 的时候回收那些无效数据。对于 WiscKey 的设计,由于元数据和数据分离,回收涉及两个方面:元数据的回收和数据回收:

  1. 元数据回收与 LevelDB 类似
  2. 对象数据回收

一个办法是扫描 LSM-tree,每个 key 对应的 value就是有效的,没有 key 对应的 value 就是无效的。这么做效率太低。WiscKey 的做法是每次写入 value 时也写入对应的 key。

head 总是指向 vLog 的尾部,新数据写到这里。而 tail 会随着 GC 的进行向后移动。所有有效数据都在tail~head 区间中,每次 GC 都从 tail 开始,也只有 GC 线程可以修改 tail。

GC 时 WiscKey 每次从 tail 开始读若干MB的数据,然后再查找对应的 Key,看这个 Key 现在对应的 value 还是不是 log 中的 value,如果是,再把数据追加到 head 处。最终,vLog 中的无效数据就都被清理掉了。

为了避免 GC 时 crash 导致丢数据,WiscKey 要保证在真正回收空间前先把新追加的数据和新的 tail 持久化:

  1. 追加数据;
  2. GC 线程调用 fsync() 将新数据写下去;
  3. 向 LSM-tree 中同步写一条记录:<'tail', tail-vlog-offset>
  4. 回收空间。

WiscKey 的 GC 是可配置的,由于垃圾回收涉及IO(先读后写),如果 key 的删除和更新都很少发生,就不需要怎么做 GC。

3.3.3 崩溃时的一致性

WiscKey 为了保证系统崩溃时的一致性,使用了现代文件系统(ext4/btrfs/xfs等)的一个特性:追加写不会产生垃圾,只可能在尾部缺少一些数据。在 WiscKey 中这个特性意味着:如果 value x 在一次 crash 后从vLog 中丢失了,那么所有 x 后面写入的 value 就都丢了。

crash 中丢失的 key 是没办法被发现的,这个 key 对应的 value 会被当作无效数据 GC 掉。如果查找时发现key 存在,但对应的 value 不在 vLog 中,就说明这个 value 丢失了,WiscKey 会将这个 key 从 LSM-tree 中删除,并返回 “key不存在”。如果用户配置了sync,WiscKey 会在每次写完 vLog 后,写 LSM-tree 前,调用一次 fsync。总之 WiscKey 保证了与 LevelDB 相同的一致性。

3.4 优化

3.4.1 vLog的写缓冲

WiscKey 不会每笔写入都调用一次 vLog 的 write,这样效率太低。WiscKey 为 vLog 准备了一个 buffer,所有写都写进 buffer,当写满或者有 sync 请求时再 write 写到 vLog 中。读取的时候优先读取 buffer。缺点是在crash丢的数据会多一些,这点与 LevelDB 类似。

3.4.2 优化 LSM-tree 的 log

WiscKey 中LSM-tree 只用于存储 key,而 vLog 中也存储了 key,那么就没必要再写一遍 LSM-tree 的log了。

WiscKey 在 LSM-tree 中存储了一条记录<'head', head-vlog-offset>,在打开一个 DB 时就可以从head-vlog-offset处开始恢复数据。将 head 保存在 LSM-tree 中也保证了一致性不低于 LevelDB,因此整体的一致性仍然不低于 LevelDB。

3.5 实现

vLog会被两种方式访问:

  1. 读取时会随机访问 vLog。
  2. 写入时会顺序写入vLog。

WiscKey 用pthread_fadvise()在不同场景声明不同的访问模式。

WiscKey 为RangeQuery准备了一个32个线程的背景线程池来随机读 vLog。

为了有效地从 vLog 中回收空间,WiscKey 利用了现代文件系统的另一个特性:可以给文件打洞(fallocate)。现代文件系统允许的最大文件大小足够 WiscKey 用了(ext4允许64TB,xfs允许8EB,btrfs允许16EB),这样就不需要考虑 vLog 的切换了。

4. 评价

主要是针对Load、Query、垃圾回收、崩溃时的一致性、空间放大、CPU 使用率做基准测试与 YCSB 测试。

机器配置:

  1. CPU:Intel(R) Xeon(R) CPU E5-2667 v2 @ 3.30GHz * 2;
  2. 内存:64GB;
  3. OS:64-bit Linux 3.14;
  4. 文件系统:ext4;
  5. SSD:500-GB Samsung 840 EVO SSD,顺序读500MB/s,顺序写400MB/s。

4.1 基准测试

  1. 工具:db_bench;
  2. DB:LevelDB/WiscKey;
  3. Key:16B;
  4. Value:各种大小;
  5. 压缩:关闭。

4.1.1 Load

第一轮:顺序插入100GB的数据。第二轮:uniform 随机写。注意第一轮顺序写不会导致 LevelDB 和WiscKey 做 compaction。

WiscKey 远远超过 LevelDB

4.1.2 Query

第一轮:在100GB随机生成的DB上做100000次随机查找。第二轮:在100GB随机生成的DB上做4GB的范围查找。

ValueSize 超过4KB 后,LevelDB 生成的 SSTable 文件变多,吞吐变差。此时WiscKey吞吐是LevelDB的8.4倍。而在 ValueSize 为 64B 时,受限于 SSD 的随机读能力,LevelDB 的吞吐是 WiscKey 的12倍。如果换一块支持更高并发的盘,这里的性能差距会变小一些。

但如果数据是顺序插入的,那么 WiscKey 的 vLog 也会被顺序访问,差距就没有这么大。64B时 LevelDB 是WiscKey 的1.3倍,而大 value时 WiscKey 是 LevelDB 的2.8倍。

4.1.3 垃圾回收

测试内容:1. 随机生成 DB;2. 删掉一定比例的 kv;3. 随机插入数据同时后台做 GC。作者固定 Key+Value 为4KB,但第二步删除的 kv 的比例从25%-100%不等。

100%删除时,GC 扫过的都是无效的 value,也就不会写数据,因此只降低了10%的吞吐。后面的场景GC都会把有效的 value 再写进 vLog,因此降低了35%的吞吐。

无论哪个场景,WiscKey 都比 LevelDB 快至少70倍。

4.1.4 崩溃时的一致性

作者一边做异步和同步的 Put(),一边用 ALICE 工具来模拟多种系统崩溃场景。ALICE 模拟了3000种系统崩溃场景,没有发现 WiscKey 引入的一致性问题。(不比LevelDB差)

WiscKey在恢复时要做的工作比 LevelDB 多一点,但都与 LSM 最后一次持久化 memtable 到崩溃发生之间写入的数据量成正比。在一个最坏的场景中,ValueSize 为1KB,LevelDB 恢复花了0.7秒,而 WiscKey 花了2.6秒。

WiscKey可以通过加快LSM中head记录的持久化频率来降低恢复时间。

4.1.5 空间放大

我们在评估一个 kv 系统时,往往只看它的读写性能。但在 SSD上,它的空间放大也很重要,因为单GB的成本变高了。所谓空间放大就是 kv 系统实际占用的磁盘空间除以用户写入的数据大小。压缩能降低空间放大,而垃圾、碎片、元数据则在增加空间放大。作者关掉了压缩,简化讨论。

完全顺序写入的场景,空间放大系数很接近1。而对于随机写入,或是有更新的场景,空间放大系数就会大于1了。

LevelDB多出来的空间主要是在加载结束时还没来得及回收掉的无效 kv 对。WiscKey 多出来的空间包括了无效的数据、元数据(LSM中的Value索引,ValueLog中的Key)。在GC后无效数据就没有了,而元数据又非常少,因此整个DB的大小非常接近原始数据大小。

KV 存储没办法兼顾写放大、读放大、空间放大,只能从中做取舍。LevelDB 中 GC 和排序是在一起的,它选择了高的写放大来换取低的空间放大,但与此同时在线请求就会受影响。WiscKey 则用更多的空间来换取更低的 IO 放大,因为 GC 和排序被解耦了,GC 可以晚一点做,对在线请求的影响就会小很多。

4.1.6 CPU 使用率

可以看到除了顺序写入之外,LevelDB 的 CPU 使用率都要比 WiscKey 低。

顺序写入场景 LevelDB 要把 kv 都写进 log,还要编码 kv,占了很多 CPU。WiscKey 写的 log 更少,因此CPU消耗更低。

范围读场景 WiscKey 要用32个读线程做背景的随机读,必然用多得多的CPU。

LevelDB 不是一个面向高并发的 DB,因此 CPU 不是瓶颈,这点 RocksDB 做得更好。

4.2 YCSB 测试