WiscKey intro

基于 LSM 树（Log-Structured Merge-Trees）的键值存储已经广泛应用，其特点是保持了数据的顺序写入和存储，利用磁盘的顺序 IO 得到了很高的性能（在 HDD 上尤其显著）。但是同一份数据会在生命周期中写入多次，随之带来高额的写放大。

以 LevelDB 为例，数据写入的整个流程为：

数据首先会被写入 memtable 和 WAL
当 memtable 达到上限后，会转换为 immutable memtable，之后持久化到 L0（称为 flush），L0 中每个文件都是一个持久化的 immutable memtable，多个文件间可以有相互重叠的 Key
当 L0 中的文件达到一定数量时，便会和 L1 中的文件进行合并（称为 compaction）
自 L1 开始所有文件都不会再有相互重叠的 Key，并且每个文件都会按照 Key 的顺序存储。每一层通常是上一层大小的 10 倍，当一层的大小超过限制时，就会挑选一部分文件合并到下一层

这样，就存在读放大和写放大的问题

WiscKey 的核心思想是将数据中的 Key 和 Value 分离，只在 LSM-Tree 中有序存储 Key，而将 Value 存放在单独的 Log 中。这样带来了两点好处：

####实现

在 LSM-Tree 的基础上，WiscKey 引入了一个额外的存储用于存储分离出的值，称为 Value Log。整体的读写路径为：

当用户添加一个 KV 时，WiscKey 会先将 Value 写入到 Value-Log 中（顺序写），然后将 Key 和 Value 在 Value Log 中的地址写入 LSM-Tree
当用户删除一个 Key 时，仅在 LSM-Tree 中删除 Key 的记录，之后通过 GC 清理掉 Value Log 中的数据
当用户查询一个 Key 时，会先从 LSM-Tree 中查询到 Value 的地址，再根据地址将 Value 真正从 Value-Log 中读取出来（随机读）

范围查询的问题：

WiscKey 内部会有一个 32 线程的线程池，当用户使用迭代器迭代一行时，迭代器会预先取出多个 Key，并放入到一个队列中，线程池会从队列中读取 Key 并行的查找对应的 Value。通过pre-fetch的功能，减少下一次读取，

GC的问题

通过维护一个 Value Log 的有效区间（由 head 和 tail 两个地址组成），通过不断地搬运有效数据来达到淘汰无效数据。整个流程为：

对于 Value-Log 中的每个值，需要额外存储 Key，为了方便从 LSM-Tree 中进行反查（相对 Value，Key 会比较小，所以写入放大不会增加太多）
从 tail 的位置读取 KV，通过 Key 在 LSM-Tree 中查询 Value 是否还在被引用
如果 Value 还在被引用，则将 Value 写入到 head，并将新的 Value 地址写回 LSM-Tree 中
如果 Value 已经没有被引用，则跳过这行数据，接着读取下一个 KV
当已经确认数据写入 head 之后，就可以将 tail 之后的数据都删除掉了

LRU的一个变种，感觉上，从tail进行遍历，发现有使用就放入head，同时更新LSM-Tree中value的地址

因为需要重新写入一次 Value，并且需要将 Key 回填到 LSM-Tree 中，所以这个 GC 策略会造成额外的写放大。并且即使不做 GC，也只会影响到空间放大（删除的数据没有真正清理），所以感觉可以配置一些策略：

利用write buffer进行批量写入

value-log作为WAL，减少WAL的写放大

####Titan的实现

和 WiscKey 的主要区别在于：Titan 在 flush/compaction 时才开始分离键值，并且用于存储分离后 Value 的文件（BlobFile）会按照 Key 的顺序存储，而不是写入的顺序（其实在这个阶段，已经没有写入顺序了)

GC调优：

通过需要合并的blobFile，不断产生新的blobFile来进行，不用写入一条完整的value log
由 LSM-Tree 的 compaction 触发，compaction 时，如果遍历到的值已经是一个 BlobIndex（代表值已经写入了某个 BlobFile），依旧将其读出来重新写入新的 BlobFile，也就是说每次 compaction 都会生成一批与新的 SST 完全对应的 BlobFile