WiscKey -- Separating Keys from Values in SSD-conscious Storage

WiscKey: Separating Keys from Values in SSD-conscious Storage

0x00 引言

这篇Paper将的都是如何解决LSM-Tree的写放大的问题。Wisckey的基本思路其实很简单，使用的方法就是将Key和Value分开保存的方式，对于读取Value时造成的随机读写问题，Wisckey则认为这个在SSD上的问题能得到缓解，也使用了预取，并行读等的一些优化方式。在SOSP‘17上面的PebblesDB则对LSM-Tree的结构进行了比较好的改进，个人认为这个是一种更加好的方式。WiscKey的设计目标是为随机性能比较好的SSD优化的，因为它的设计会导致比较多的随机读，它在测试数据中实现了,

  We demonstrate the advantages of WiscKey with both microbenchmarks and YCSB workloads. Microbenchmark results show that WiscKey is 2.5×–111× faster than LevelDB for loading a database and 1.6×–14× faster for random lookups. WiscKey is faster than both LevelDB and RocksDB in all six YCSB workloads.

0x01 Key-Value Separation

WiscKey的核心思路基本就是将Key-Value分开保存了。在LSM-Tree中，每次merge的操作会造成写放大的问题，但如果将里面的Value拿出来分开保存，直接保存在LSM-Tree的数据就减小很多，因为一般情况下，Key的尺寸远小于Value的尺寸。直接在LSM-Tree就只需要保存Value的地址信息。这个思路和bitcask的思路很相似。不同点：bitcask的索引结构一般为hash table，当然使用skip list之类的数据结构也完全是可以的；另外一个不同点就是bitcask的索引都是全部保存在内存里面的，也会定期的持久化到磁盘上面。

wisckey-layout

如上图所示，Key Values-Address的pair保存在LSM-Tree里面，而Value本身就保存在类似Log的结构里面。由于Key Value之间很大的尺寸差异，这样LSM-Tree里面实际保存的数据就会大大减小，也就能很大程度上解决写入放大的问题:

For example, assuming a 16-B key, a 1KB value, and a write amplification of 10 for keys (in the LSM-tree) and 1 for values, the effective write amplification of WiscKey is only (10 × 16 + 1024) / (16 + 1024) = 1.14. In addition to improving the write performance of applications, the reduced write amplification also improves an SSD’s lifetime by requiring fewer erase cycles.

0x02 要解决的问题

Parallel Range Query，这是WiscKey要处理的一个最主要的问题，范围查询对于LevelDB之类的将Key和Value放在一起的设计来说，这个做起来就很简单。对于WiscKey来说，这就因为着会产生大量的随机读操作，当然就会影响到性能。这里WiscKey的拒绝办法是利用SSD设备的并行IO的能力，对于范围查询，WiscKey对Next() or Prev() 的请求，会分析访问的模式，一旦一个发现是一个连续的顺序访问，WiscKey就会读取画面的若干的Key，然后并发的使用这些Key信息去取回Value。
Garbage Collection，一般的LSM-Tree的设计垃圾回收是在compaction的时候进行的，对于WiscKey来说，这里要处理的问题是，直接扫描Value Log(vLog)处理的方式是不好的，会带来太大的overhead。未来解决这个问题，这里处理的方式是对WiscKey的Data Layout进行少许的修改，在vLog里面不仅仅是保存了数据，而是以这样的方式保存(key size, value size, key, value) 。WiscKey的垃圾回收的一个目标就是将有效的Value保存在一个连续的范围之内。如下面的图所示，在vLog里面，有一个head代表了写入的位置，一个tail代表了垃圾回收要处理的开始的位置。垃圾回收的是，WsicKey先读区几个MB的数据，检查里面合法的数据，然后将这些数据写入到head。
```
To avoid losing any data if a crash happens during garbage collection, WiscKey has to make sure that the newly appended valid values and the new tail are persistent on the device before actually freeing space.
```
Crash Consistency，即使这里Key Value是分开保存的，WiscKey依然可以提供Crash Consistency。在系统崩溃的时候可能出现只有一部分的数据被append的vLog的后面，也可以保存如果Value X在carsh中丢失了，后面的数据也都会丢失，不会出现随机的一些bytes or 不是Value前缀的数据被添加进去。当查询是，WiscKey如果发现一个Key在LSM-Tree中发现不了，就会认为这个数据在Carsh中丢失了。如果能在LSM-Tree中被发现，则会检查数据的合法性，如果检查不通过，就会认为这个Value在Crash中被丢失了，
```
In this case, WiscKey first verifies whether the value address retrieved from the LSM-tree falls within the current valid range of the vLog, and then whether the value found corresponds to the queried key. If the verifications fail, WiscKey assumes that the value was lost during a system crash, deletes the key from the LSM- tree, and informs the user that the key was not found.
```

wisckey-gc

0x03 优化

Value-Log Write Buffer，这个优化是一个显而易见的优化，资额vLog的时候最好就是积攒了一些数据之后在写入到文件里面。添加了这个write buffer之后，要添加的一个处理就是查找的时候要先查找这个buffer里面的数据，因为这里的数据还是在内存里面的。

Optimizing the LSM-tree Log，这也是一个很好的优化，前面提到的在vLog里面的数据是既有Value也有Key的，这样的话就不用在额外使用Log了。为了加快Crash之后的恢复的速度，WiscKey周期性的在vLog的head里面添加一个<‘‘head’’, head-vLog-offset>，这个就类似于一个checkpoint的机制，

 WiscKey records the head of the vLog periodically in the LSM-tree, as a key-value pair <‘‘head’’, head-vLog-offset>. When a database is opened, WiscKey starts the vLog scan from the most recent head position stored in the LSM-tree, and continues scanning until the end of the vLog. Since the head is stored in the LSM-tree, and the LSM-tree inherently guarantees that keys inserted into the LSM-tree will be recovered in the inserted order, this optimization is crash consistent. 

0x04 评估

基本的性能数据(详细的数据参看论文):

wisckey-performance

0x05 总结

这个在一些随机性能非常好的SSD上面是一种非常有效的办法。对于现在的很多NVMe的SSD来说，4K的随机性能以及是几十万的基本了。这个办法的优势在于它的简单，而且很有效。另外，咸鱼觉得这里的写入和垃圾回收还是可以有优化的空间的，emmmmm。

参考

WiscKey: Separating Keys from Values in SSD-conscious Storage, FAST ’16.
PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees, SOSP 2017.