LSM-Tree and LevelDB
Wisckey 是针对 LSM-Tree 在 SSD 存储下的优化。LSM-Tree 目前应用已经很广了，主要应用在日志系统和KeyValue存储引擎，比较著名的实现是LevelDB。LSM-Tree 利用了磁盘具有顺序读写比随机读写快的特点，提供了可持久化的高性能 KeyValue 存储。
LSM-Tree 主要有以下特点：
- 随机 IO 会转化为顺序 IO，降低了由于磁盘随机IO带来的延迟（latency）
- 每个层级满了之后，会往更高层级合并文件，会带来写的放大
- 对于新写入数据访问友好，但是访问一些冷数据的话会造成读放大
由于 LSM-Tree 存在读写放大的问题，首先会造成是性能损耗，还有一个会影响磁盘寿命。
WiscKey
WiscKey 针对读写放大的问题，主要采取了 Key-Value 分离的方案。
在 Key-Value 分离之后，首先 LSM-Tree 整体会缩小，即使往上层合并 SSTable 文件的时候，由于树的节点小了，造成的写放大规模也会相应的降低，那么相应地读放大问题也会相应减弱。
Key-Value 分离
在论文中提到的一个例子，假设一个 key 大小为 16-B，value 指针为 12-B，value 为 1-KB，那么当数据量为 100GB的时候，此时的 LSM-Tree 实际是2GB左右，能够轻易的缓存在内存里面。
挑战
Key-Value 分离当然也带来了很多的挑战：
- 并发范围查询（Range Query）
- 垃圾回收（Garbage Collection）
- 数据一致性（Consistency）
下面会继续讨论 WiscKey 是怎么解决这些问题的
并发范围查询
首先在一般的 HHD 硬盘，肯定随机访问的性能是不好的，那么对于 SSD 来说，在并发的情况下，随机读写性能也没有那么差。实际上WiscKey 就是针对 LSM-Tree 在 SSD 上的优化。
SSD中顺序IO和随机IO
如上图，那么我们控制好对 SSD 数据块的写入大小和写入频率，理论上随机读写能够得到接近顺序读写的性能。
垃圾回收
WiscKey 用了一种特殊的垃圾回收机制：在 tail 一块一块的读数据，找到有效的数据就插入 head ，无效就抛弃。虽然这样能够较好的收集磁盘空间，但是其实也是存在读写放大的问题，需要控制好垃圾回收的时机和频率。
image.png
数据一致性
由于 WiscKey 的 Key 和 Value 是分离的，很容易造成数据不一致。
WiscKey 提出了相应的解决方案，其实主要总结分位以下两种情况：
Key 有效 Value 无效
给用户返回 Value 不存在即可。但是这里Value无效其实有两种情况，一是未写入Value，二是Value不完整。后者可以通过一些磁盘校验位解决问题。
Key 不在 Value 有效
垃圾回收抛弃此 Value即可
参考文章：
网友评论