当LSM遇上SSD

女主宣言

背景介绍

近年来，以LevelDB和Rocksdb为代表的LSM（Log-Structured Merge-Tree）存储引擎凭借其优异的写性能及不俗的读性能成为众多分布式组件的存储基石，包括360私有云团队近两年开发的类Redis大容量存储Pika和分布式KV存储Zeppelin。

在享受LSM的高效的同时也开始逐渐体会到它的不足，比如它在大Value场景下的差强人意以及对磁盘的反复擦写。LevelDB最大的优势便是将磁盘的随机写转化为顺序写，但随着在系统中越来越多的使用SSD，这种设计是否仍然能带来如此大的收益，在SSD统治的世界里是否有更合理的存储结构。

2016年，FAST会议发表了论文WiscKey: Separating Keys from Valuesin SSD-conscious Storage，阐述了一种对SSD更友好的基于LSM的引擎设计方案。

问题

LSM Tree是一种对写优化的系统，将随机写转化为顺序写，从而获得非常优秀的写性能，但一定的LSM也损失了一些东西作为交换，这个损失就是写放大，即实际的磁盘写跟用户请求写的比值，就是说：

LSM Tree 将随机写转化为顺序写，而作为代价带来了大量的重复写入

那么这种交换是否值得呢，先来看损失，以LevelDB为例，在最坏的情况下：

这个写放大的系数大概在几十到几百之间。那么收获的呢，通过下表中针对不同存储介质的写入测试数据，可以看出在传统的机械盘上顺序写的性能远远好于其随机写性能，这个性能差异接近一千倍。用数十倍的磁盘带宽损失换取近千倍的性能提升，在写入敏感的场景下这种交换的效果毋庸置疑。

但不同的是，SSD盘相对具有较高的随机写能力，与顺序写的差距本身只有十倍左右，并且还可以通过并行IO进一步提升，因此这种交换就显得有些得不偿失。同时，由于反复的写入会带来SSD的磨损从而降低寿命。

思路

回顾上面的问题，当LSM中数据的长度很大时，这个问题变得尤为突出，这是因为：

LSM需要的其实是key的有序，而跟value无关。所以自然而然的思路是：

Key Value 分离存储

仅将Key值存储在LSM中，而将Value区分存储在Log中，数据访问就变成了：

这样带来显而易见的好处：

挑战

这种思路是否可行呢，分析可知，Key Value分开存储会导致以下三种问题，如果能解决或者容忍，那么这种设计就是成功的。

Key Value分离带来的Range操作的低效

由于Key Value的分离，Range操作从顺序读变成了顺序度加多次随机读，从而变得低效。利用SSD并行IO的能力，可以将这种损失尽量抵消，这正是得益于SSD较强的随机访问性能。

被用户删除或者过期版本的Value的空间回收

Compaction过程需要被删除的数据由于只是删除了Key，Value还保留在分开的Log中，这就需要异步的回收。

LSM本身的Compaction其实也是垃圾回收的思路，所以通过良好设计的Value回收方式其实并不会过多的增加系统的额外负担。离线回收比较简单，扫描整个LSM对Value Log进行mark and sweep，但这相当于给系统带来了负载带来了陡峭的波峰，WiscKey论文又提出来了巧妙的在线回收方式：

其中head的位置是新的Block插入的位置，tail是Value回收操作的开始位置，垃圾回收过程被触发后，顺序从Tail开始读取Block，将有效的Block插入到Head。删除空间并后移Tail。

这里的回收方式由于需要将有效的数据重新Append，其实也带来了写放大，这就需要很好的权衡空间放大和写放大了，WiscKey建议系统根据删除修改请求的多少决定触发垃圾回收的时机。

Crash Consistency

正式由于Key，Value的分离带来了不可避免的在程序Crash发生时不一致的情况，WiscKey需要像标准的LSM一样提供如下保证：

WicsKey给出的解决方案，是在启动时对Key， Value进行检查：

优化