1. 背景

以 LevelDB 和 RocksDB 为代表的 LSM-tree key-value 存储，被广泛的应用，所以当前针对其优化的研究非常多，在最近几年的顶会上都有，这里将介绍 USENIX ATC 2018 的一篇文章 HashKV [2]，其是对 FAST 2016 中 WiscKey [1] 的优化。那么首先来介绍下 LSM-tree 和 WiscKey。

2. LSM-tree

LSM-tree 被应用在 Bigtable，HBase，Leveldb，RocksDb 等中，这里以 Leveldb 为例子，如下图：

其写入首先将数据以 append 的方式写入 log 中，然后写入内存中的 memtable，就可以返回，因为事先写入了 log，所以保证的持久性；memtable 到达一定的大小之后转变成不可写入的 immutable，然后在被持久化为 是stable 文件；sstable 的文件会定期的做 Compaction 合并到下一个 level 中，以便将老数据推到高层的 level 中，并实现删除 key-value 的回收，如上图所示：

优点：

• 通过将随机小写转变成顺序写，提高了写入的性能
• 由于数据的存储都是按照一定 key 的顺序存储的，所以，支持高效的 range scans

缺点：

缺点也很明显，就是 I/O 放大：

• read 放大（amplifications）： 最坏情况从内存，到盘中 level 逐级 read，直到 read 到数据
• write 放大：反复的 Compaction

文献 [1] LevelDB 和 RocksDB 的 write amplifications 达到 50X 之多，在顺序写和随机写相差 100X 甚至 1000X 的 HDD 时代，LSM-tree 的收益是明显的，反之在顺序写和随机写相差不大的 SDD 时候，尤其是 NVME SSD 和 Optane 设备的出现，进一步缩小了顺序写和随机写的差距（< 10X），所以人们开始思考对 LSM-tree 进行优化了。最近比较火的是 FAST 2016 的文章 WiscKey。

3. WiscKey

WiscKey 为了减少 read/write 的放大，决定将 key-value 分开，减少 LSM-tree 的 size，从而减少 Compaction 对 write amplifications，其大致的做法如上图，将 key-value 分离（其实和 bitcask[3] 的思路是类似的）：

key + meta data 存放在 LSM-tree 中，也就是 LevelDB 或者 RocksDB 中，这样 LSM-tree 中数据量很少，那么 Compaction 只有 LSM-tree 中的 key + meta data 在移动，而在 vLog 中 key+value 并不会动，自然造成的 write amplification 自然会小很多，实际上由于数据量少了，read 可能需要查询的 level 数也变少，所以对 read/write amplification 都有一定的效果

value 单独存放在 VLog 中，vLog append 的写入 key-value。为了释放 VLog 中被删除的 key-value，Wisckey 需要对 vLog 进行 GC，GC 是从 tail 读，然后去 LSM-tree 中查询有没有这个 key，如果没有，说明被删除了，否则，又 append 到 head，那么就会存在一定的写放大，实际上这里也有很多需要考量的问题，空间放大和写放大如何权衡 ？如何控制 Gc 保证其不影响正常的 I/O ？

Notes

上图的顺序好像是画反了，上图是官方在会议上 presentation 的 ppt，在论文中描述上好像也有错误 ？

First, the circular log maintains a strict GC order, as it always performs GC at the beginning of the log where the least recently written KV pairs are located. This can incur a large amount of unnecessary data relocation (e.g., when the least recently written KV pairs remain valid)

感觉这个错误优点低级，不知道是不是自己看错了，关系的小伙伴可以一起验证下。如果作者理解错了，那么上面这段话就扯了。

回到正题，虽然减少了 write amplification，但是 GC 可不是省油的灯，原文作者认为在空间有限，且 update-intensive workloads，其实就是不允许空间放大太多，且更新很频繁的系统中会存在以下问题：

1. 作者原文描述说严格的 gc 顺序，从 head -> tail，造成很多不必要的 write amplification （由于这里感觉作者描述是错的，如上 Notes，所以这点不成立）
2. gc 的时候需要去查询 LSM-tree 看这个 key-value 是否被删除，存在一次查询，开销也不容忽视
3. 
   

如上图，给出了空间放大有限，更新频繁的系统由于频繁的 Gc 造成 GC write amplification 非常严重。由此，作者给出了自己的解决方案 HashKV

3. HashKV

目标场景：

• 空间有限（空间放大控制得较为严格）
• update-intensive workloads

（虽然 update-intensive workloads 下，确实 GC 放大严重，但是作者硬生生的还加上空间放大容忍度低这一条，哈哈，，，）

Architecture

• idea

• （1）还是 key-value 分离，key & meta 放在 LSM-tree 中，这部分设计保持不变，保证 LSM-tree Compaction 不会移动数据，只是移动 key & meta data，减少 read/write amplification
• （2）Hash-based Data Grouping：通过 hash，将 key 放到 fixed size的 Partation 中，也就是分 group，然后根据统计信息来决定 group 的 gc 时机，以减少 gc 的 write amplification
• （3）Dynamic reserved space allocation：由于 Partation 是 fixed size，所以可能会存在空间不够的情况，但是可以允许从预留区中
• （4）Hotness awareness：通过区分 hot 和 cold 数据，将 hot 和 cold key-value 数据分别存放在不同的区域，从而使用不同的 GC 策略来减少 GC 的 write amplification
• （5）Selective KV separation：选择性的 key-value 分离，也就是当 value 比较小的时候，直接放在 LSM-tree 中，只有 value 大的才实行 key-value 分离

其实 key-value 分离思路简单，但是关键还是要看 storage management，如 Figure 3 的体系结构图。

一个 Partation 是由一个固定大小的 main segment 和 若干个 log segment 组成的 segment group，当一个写入的 key-value pair 时候，如果 main segment 中有空间，则 append 到未满的 main segment 中，否则动态的分配 log segment 来存放

GC

• 以 segment group 为单位，哪个 segment group 最近 update 越多，选谁，这个信息维护在内存中
• check k-v 的有效性：不需要查找 LSM-tree，segment group 中的 value 都是以 log-structed 形式存在的，那么从 tail 开始，最后面的某个 key 对应的肯定就是 lastest version，前面的就是旧的 可以删除的版本。那么扫描一遍这个 segment ，注意从后往前扫描，就可以获取所有有效的 value （这个和 WiscKey 相比，本来也需要扫描 vLog，然后再去 LSM-tree 查，只是 HashKV 先扫描一遍，这里其实也只是扫描 meta，并不会 scan 所有数据，扫描之后，内存中会维护一份，直到这个 Group gc 完成）
• 将 valid 的 value 写入到新的 segment 中；
• 更新 LSM-tree

当 LSM-tree 更新完毕之后，这个 segment group 的 gc 就算结束了，之前的 segment 也就可以删除掉了，read/write 就会到新的 segment 中。

gc 的过程中，并不会影响 read/write，read 还是走之前的 LSM-tree 读，write 写入 gc 新写入的 segment

Hotness Awareness

cold k-v with a taggted（Currently, we treat the KV pairs that are updated at least once since their last inserts as hot, or cold otherwise ），在 GC 的时候，hot kv 继续写到 segment 中，对于 cold 的 kv，仅仅把 key 和 meta 存在 segment 中，value 存放在 vlog 中，和 WiscKey 的方法一样进行回收

Selective KV Separation

可以选择 k-v 是否分开，在 value 小的情况的下直接存放在 LSM-tree 中，反之则执行 k-v 分离。

Range Scans

• 保留 LSM-tree for indexing 就是为了 range scans，因为在 LSM-tree 中 key 是按顺序排的，但是在当前的 k-v 分离的场景中， range scans value 的 read 会存在大量的随机 read。论文给出的思路是通过 read-ahead（预读），但是感觉效果不会太明显，毕竟在随机 read 中，read-ahead 不会有效果，因为 value 是按照 key 的 hash 打散到 Partation 中的，read-ahead 估计效果不会很大。
• Crash Consistency

4. 总结

参考文献

[1]. Arpaci-Dusseau R H, Arpaci-Dusseau R H, Arpaci-Dusseau R H, et al. WiscKey: Separating Keys from Values in SSD-Conscious Storage[J]. Acm Transactions on Storage, 2017, 13(1):5.

[2]. HashKV: Enabling Efficient Updates in KV Storage via Hashing. https://www.usenix.org/conference/atc18/presentation/chan

[3]. bitcask. http://downloads.basho.com/papers/bitcask-intro.pdf