LSM-Tree的优势在于借鉴LFS的思想，将大块的内存连续的写出到磁盘，减少磁盘seek的时间。同时输出的格式又是连续的，查找的速度也比较快。但是LSM-Tree的结构，也带来了写放大和读放大的问题。这些影响在hdd上是值得的，但是在ssd上并不友好。WiscKey提出了一种面向ssd的，将key和value分开存储的方法。

Write and Read Amplification

写放大主要在于compaction的，每次两层之间做compact时，都需要将多个sstable读出做排序（读放大），再写到磁盘。而读放大方面，LSM-Tree需要查找多个数据结构，memtable->imutable->level files，假设不存在这个key的，便要把每一层做二分查找搜一遍。特别是第0层，有overlap，需要每个文件都看，虽然有bloom filter，但也影响效率。当value比较大的时候，问题就很明显了，compaction时sstable的读入和写出，都是将key和value一起读一起写的，当value变长时，效率会很低。这些放大的影响在hdd，来换取磁盘seek的消耗还是值得，但是在SSD上就不一样了，SSD随机读写要快的多，并且有并行随机读取的特性可以利用。


WiscKey

key idea就是将key和value分开存储，LSM-Tree里只存key加一个value地址的偏移量，value放到另一个log文件中。之所以可以做是因为，compaction的时候，其实并不需要value的参与，需要排序的只有key而已。idea很简单，但是设计细节还是很复杂。有如下几个问题需要解决。

  1. 因为key和value分开存储，原先read的时候key和value是一起读上的，现在多了一次seek。
  2. value的log文件怎么样做垃圾回收？
  3. key和value分开在两个地方写，怎么保证一致性。

Parallel Range Query

WiscKey很好的利用了SSD的特性，当key和value分开存储读取和写入时，可以在后台开启多个线程并行读取value log，但是这里有个不足，是需要value足够大，根据实验数据当value大于4KB时，WiscKey的读性能才能展现出来。

Garbage Collection

删除key的时候，只是在LSM-Tree删除，并不会涉及到value log，所以需要定期的清除无效的value。这里比较有趣的是，为了方便做垃圾回事和一致性，value log，存的不仅是value，还有key。如下图

垃圾回收的步骤如下

  1. 从tail开始数据
  2. 检测key是否被删除，或者修改了。（查找LSM-Tree）
  3. 将依然有效的数据顺序添加到head
  4. free 直接的space

这个垃圾回收工作不需要实时做，可以离线，效率还是很高的。

Crash Consistency

WiscKey无论是key丢失，还是value丢失都很好处理。

  1. 若是key丢失了，value还在，就和key被删除的情况一样。
  2. 若是key在，value丢失。因为value log也存了key，只要比较一下key是否相同即可，反之则删除key。

还有一步可以优化的则是，可以去掉原来的WAL， 因为value log里存了所有可以用来recovery的信息。

Conclusion

WiscKey这种key与value分离的设计有如下优点。

  • 减少写放大和读放大，compaction时只涉及到key，显著减少数据量
  • LSM-Tree的层高和sstable的数量会明显减少。树变小还可以更好的利用cache

但也有不足

  • 对小value不友好

Reference

[1] WiscKey: Separating Keys from Values in SSD-conscious Storage. FAST ‘16