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