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,其实就是不允许空间放大太多,且更新很频繁的系统中会存在以下问题:
- 作者原文描述说严格的 gc 顺序,从 head -> tail,造成很多不必要的 write amplification (由于这里感觉作者描述是错的,如上 Notes,所以这点不成立)
- gc 的时候需要去查询 LSM-tree 看这个 key-value 是否被删除,存在一次查询,开销也不容忽视
如上图,给出了空间放大有限,更新频繁的系统由于频繁的 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