绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
【ATC 2018】HashKV
2019-12-24 16:30:55


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 是否被删除,存在一次查询,开销也不容忽视


如上图,给出了空间放大有限,更新频繁的系统由于频繁的 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


分享好友

分享这个小栈给你的朋友们,一起进步吧。

分布式存储笔记
创建时间:2019-12-13 16:59:52
分布式与存储技术
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • 暗淡了乌云
    栈主

小栈成员

查看更多
  • bluetooth
  • 栈栈
  • ?
  • R-B
戳我,来吐槽~