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

分享好友

×
取消 复制
【FAST 2016】Wisckey-Separating Keys from Values
2019-12-23 10:37:12


1. 背景

以 LevelDB 和 RocksDB 为代表的 LSM-tree key-value 存储,被广泛的应用,所以当前针对其优化的研究非常多,在近几年的顶会上也是常有的话题,这里将介绍 USENIX FAST 2016 的一篇文章 《WiscKey: Separating Keys from Values in SSD-Conscious Storage》 [1],其类似 bitcask 的思路,通过将 key-value separation 的策略来降低传统 LSM-tree 的读写放大的问题。


2. LSM-tree

首先简单介绍下 LSM-tree,然后分析作者论文的优化动机,解决的基本问题。

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


LSM-tree 大体都首先将数据以 append 的方式写入 log 中(保证落盘,可配置),然后写入内存中的 mutable memtable,就可以返回,因为事先写入了 log,所以保证的持久性;mutable memtable 到达一定的大小之后转变成不可写入的 immutable,然后由后端线程将其持久化为为 sstable 文件;sstable 的文件会定期的做 Compaction 合并到下一个 level 中,以便将老数据推到高层的 level 中,与此同时实现删除或者覆盖写的 key-value 回收,基本的层次结构如上图所示。


优点:

  • 通过将随机小写转变成顺序写 log,提高了写入的性能,immutable 也是顺序批量的写入,总体而言就是 LSM-tree 的基本出发点,批量、随机转顺序(有利于削峰)
  • 由于数据的存储都是按照一定 key 的顺序存储的,所以,支持高效的 range scans
  • 分层的结构,逐层分级缓存(从内存,到 stable 的 level 0、1、2、3、4、5、6 层),越新访问的数据,越在上层,这样有利于 read


缺点:

缺点也很明显,就是 I/O 放大:

  • read 放大(amplifications): 坏情况从内存,到盘中 level 逐级 read,直到 read 到数据(当然现在的大多会采用 BloomFilter 进行优化)
  • write 放大:反复的 Compaction,尤其是在 value 比较大的情况,因为 LSM-tree 的通常实现,如 Leveldb,每个 level 的数据都有一个基准的阈值(文件数量和数据量),超过这个阈值的时候,就会更快的触发向下一个 level 的 Compaction,也就是 Compaction 就会更加的频繁

这里给一组论文给出的数据,实际上之前也有实际的测试过,发现读写放大都到几十倍。这里先来看看论文的数据吧。



如上图,可以看出,随着数据量的变多,LevelDB 的 read/write amplification 都显著的增加,尤其是 write 的写入都到 327 X 了。

当然 LSM-tree 有它产生的时代背景,那个年代,HDD 顺序写和随机写相差 100X 甚至 1000X ,LSM-tree 的收益是明显的,而且相比于 B+ 树存储引擎,其的写入性能,让其火了起来。然后随着近几年硬件的发展,SSD 在顺序和随机 read/write 差异已经大大缩小,尤其是 NVME SSD 、Optane 以及 NVM (如 Intel 3DXPoint 技术)设备的出现,进一步缩小了顺序和随机 read/write 的差距(< 10X),自然需要开始思考对 LSM-tree 进行优化了。


3. WiscKey

文献 [1] 提出的 WiscKey 就是通过将 key-value 分离的思路。基本结构如下图所示:


  • key,addr 作为 meta 还是存放在 LSM-tree,value 单独存放在 Value log 中

优点很明显,

1)就是 key,addr 作为 meta 单独存放,那么 LSM-tree 的数据量将大大减少,read/write 的放大都将大大减少(如 Figure 2),而且对于 read 来说,实际上这部分 key,addr meta 完全可以加载到内存中;

2)至于对于写,由于 value 单独存放,所以 Compaction 并不会移动 value,所以由于 Compaction 造成的 write amplification 也将急剧的变小,这个收益将在 value size / key size 比比较大的时候尤为的明显;

3)value 部分直接写 VLog,不会存在 double write


4. Challenges

天下没有免费的午餐,key-value seperation 看上去很美妙,但也不是没有缺点的。下面将一一解读,当然论文作者也一一给出了相应的解决方案

4.1. Range scan

在开始我们介绍了,LSM-tree 由于按照 key 顺序存放的原因,所以其具有良好的 range scan 性能,而 key-value separation 将 value 是无序的存放在 VLog 中的,自然相比原先的 range scan 的顺序 read,现在变成了随机 read,自然性能不好。那么如何解决呢 ?

ssd 具有良好的随机 read/write 能力,这是 SSD 的特性,尽管顺序和随机 read/write 的性能还有差距,但是这种差距已经比较小了

ssd 具有良好的并发性能,因为 ssd 的底层都是多通道,在多线程的表现下会比较好,所以可以通过提高并发来弥补随机 read 给 range scan 带来的性能损失,所以作者给出了 Parallel Range Query 的方案,也就是并发 read。作者还给了 ssd 在多线程下的表现,数据下图:


4.2. Garbage Collection

在 LevelDB 中通过 Compaction 来实现删除数据合并,实现垃圾回收。WiscKey 将 value 单独的存放在 VLog 上,如何进行垃圾回收呢 ?Wisckey 给出了一个简单在 online garbage collection 方案,这里将 VLog 分为 head 和 tail,head 用于新的 value append 写入,垃圾回收就会从 tail 开始,为了保证垃圾回收的时候用于足够的元数据信息,实际 VLog 一个 value tuple 包含了 (key size, value size, key, value)等信息,其大致的回收步骤如下:

  • 从 tail 中读取一个 value tuple
  • 从 LSM-tree 中查看对应的 key 是否已经被删除或者 overwrite,如果是,那这个 value tuple 直接删除,否则,append 到 VLog head
  • 并修改 LSM-tree 上地址 addr

(Notes 为了保证一致性,上面的顺序不能调换)

实际上垃圾回收也同样存在 write amplification 的问题,这里垃圾回收的频率需要控制好,也是空间放大和写放大的一个权衡。

4.3. Crash Consistency

由于 key-value separation,所以 key,addr meta 和 value 的写入是两个不同位置的写入,所以原本 LSM-tree 的atomic 性将会成为一个问题。处理分两种情况:

key,addr 在,但是 value 在 VLog 中没有找到,那么会认为 key-value 没有写入成功,删掉相应的 key 并返回用户 key 不存在

key,add 不在,value 在,那么在垃圾回收的时候会发现直接抛弃此 key-value


5. 总结

key-value 分离在 value 比较大的情况下确实是可行的,实际上在早几年就有公司这么做了。不过这也算是一个公开的方案可供学习和参考。


Notes

水平和时间有限,论文很多细节没看那么细,难免有错误和理解不到位的地方,欢迎指出和交流~


参考文献

[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.

分享好友

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

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

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

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

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

栈主、嘉宾

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

小栈成员

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