论文阅读: PebblesDB

总 第16篇

2019年 第12篇

1 简介

本文是论文《PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees》的总结和感悟

PebblesDB的基本目标是减小写入放大,降低高吞吐写入时对磁盘的io压力。

PebblesDB使用了一种叫做FLSM-tree的外存数据结构。这种数据结构可以看做是skiplist+LSM-tree的联合。

PebblesDB的基本思想是:弱化数据有序性,减少不必要的数据overlap,从而在整体上减少数据参与compaction次数。

1.1 Skiplist

Skiplist是一种与平衡树等效的数据结构,它等于在有序LinkList的元素节点上维护一个高度。同一层高度的元素间有链表的指向。

他的插入,删除和查询效率与平衡树基本相等。

skiplist的优点是较平衡树简单,这尤其体现在对树的平衡性调整上,skiplist元素有个关键属性是高度h。

  1. 平衡树有严格的左旋右旋调平办法,如AVL树,红黑树

  2. skiplist的插入新元素,该元素高度h是概率性的。概率通常设置为1/4。初始高度是1

    • skiplist的每个InsertNode操作,其高度由一个,n次随机试验(每次试验是伯努利试验)决定,每次试验有1/4概率把高度抬高1。(这个实验是几何分布的)

    • 若高度被抬高,则继续以同样的概率(1/4)进行随机试验,直到命中不抬高或达到最高,则结束试验。

    • 从统计概率角度看。高度>=h的元素个数是高度>=(h+1)的元素个数的2倍。所以,其形状如同下图。

  3. 下图显示了skiplist

    • a b c d 显示了从有序linklist到skiplist的发生过程(这是理想情况)

    • e 则是实践中最有可能的出现的(那种类型的)情况

1.2 LSM-Tree

LSM-Tree名字为 log-structured merge tree,我以为可以直接视为带有优先级的森林。

LSM-Tree,由n颗树组成,分别叫做c0树,c1树,...,c(n-1)树。每一个c(i)结构是个有序结构,这个结果可以是tree,也可以是tree-like结构。

skiplist由于的实现简便性,以及良好的性能,广泛应用于levedb family的引擎中,作为内存c0树的实现。

在实践中,实现LSM-Tree为了优化写入性能,把C0树,也拆成了森林。

  • leveldb的c0树有两棵树,memtable和immutable memtable

  • rocksdb的c0树则可以更多

c1树,通常也是个森林。这是内存直接dump到磁盘上的。这就是 leveldb,rocksdb的level-0层数据。

  • leveldb的默认参数:level-0最多可以有12个。这意味着可以有12颗这样的树(12个文件)。

  • 树的数量太多,影响读延迟,故不希望leveldb,rocksdb的level-0文件过多。默认设置为4个文件则compaction

c2及其以上

  • 从level-2开始的高层,可以看做一颗2层的m叉树。其根节点(即metadata)持久化在manifest文件中,运行过程中,缓存在内存

  • 中,这个m叉树的叶子节点就是一个sst文件

LSM-Tree解决了B树系列结构的写入吞吐问题,即把大量随机写入,转化成顺序写入,大大提高了写入吞吐,但是其遗留下来的问题是读放大。

读放大,系统必须按照优先级顺序检索树,直到首次读到想要的数据,或者首次读到删除数据(kTypeDeletion),或者最终确认数据不存在。

  • 这个过程,读延迟与系统中的树结构的数量正相关。

  • 为了缓解读放大带来的延迟,LSM-Tree使用compaction的方法,来减少整个森林中,树结构的数量。

  • 同时,为了快速判定 NotFound的情况,减少延迟,sst文件中会保存bloom filter信息,open file时,该信息直接缓存在内存。

  • 为了优化读速度,内存data cache当然也是有的。

1.3 名词说明

下列名词,未找到权威定义,只用自己的理解稍加解释。 恐不确切

  1. 写放大(Write Amplification)

    • 用户写数据请求,写入存储系统落盘一次(从内存flush到磁盘),则无写入放大。

    • 当今流行的LSM-tree实现的存储引擎,因为优化读放大,需要不断compaction,这个过程会把数据合并重写。其结果是数据又被重复写过n次。

  2. 读放大(Read Amplification)

    • 用户读数据请求,读一次磁盘拿到数据, 则读 无放大。

    • 当今流行的使用LSM-Tree实现的存储引擎,需要按合并树的优先级顺序,依次读文件。其最坏io次数为 O(合并树个数)

  3. 空间放大(Space Amplification)

    • 因为LSM-tree本身的特性,空删除,重复key写入,实际删除,陈旧数据不能立即删除,导致空间占用增多

    • 以上这些情况,只有发送compaction到最高层时才能执行有效合并,减小实际空间。

  4. 最高层:level-0,按照rocksdb和文中统一的观点是level-0。

  5. 最底层:bottommost,是level-n(如果level-n上有数据,level-n+1及更大level上没有数据的话)

2 PebblesDB

2.1 写放大倍数

作者测试了 用户写入数据45GB时,各个存储引擎的写入放大情况。

  • pebblesdb最少,17倍放大

  • leveldb其次,27倍放大

  • HyperLeveldb,40倍

  • rocksdb,42倍

当然,减小写放大,最简单的做法是,不进行compaction。这样的结果是,读放大和空间放大都很严重。

2.2 写放大倍数

因为LSM-tree是严格保序的,所以,对一个sst的compaction,必须严格的选择所有相关的overlap进行compaction。

如下图所示,展现了一种worst-case。内存中flush到level-0的文件数据理论范围是所有。即,它有可能和level-1中的所有文件产生overlap这样,他的compaction就要重写level-1。

  • 在t1时刻,level-0文件compaction,把level-1的两个文件重写一遍。

  • 在t3时刻,level-0文件compaction,又把level-1的两个文件重写一遍。

  • t5时刻亦然。

2.3 解决写放大的思路

  1. 减少LSM-tree的大小,即一个引擎中存储数据要限制。这相当于一个小的object存储系统。

    • LSM-tree中只记录object的meta信息,而把value存到一个log-structured文件中

    • 传统做法:想办法限制一个LSM-tree的大小

    • Wisckey做法:把实际数据的大value替换成小value(offset),大value数据存放在别的data文件中。

  2. 弱化全局严格有序的思路,这就是pebblesdb的做法

2.4 FLSM

FLSM,即fragment log-structured merge tree。在LSM-tree基础上,增加了一个guard的数据组织单位。如图所示:

2.4.1 Guard的概念

guard是FLSM-tree的核心组织结构,他是由一些符合一定key范围的各层sst构成的集合。guard的关键属性,[guard start key,guard end key),guard end key在每一个level上可能是不同的,如上。

一个sst文件属于一个guard,在sst所在level上的guard范围是 [guardstartkey,guardendkey),sst需要满足

    • sst文件不是level-0的

    • 在sst所在level上,且sst的 startkey >= guardstartkey, 并且 endkey < guardendkey

2.4.2 FLSM-trees的性质

  1. level-0层无guard

  2. level-1以及底层(level-2, level-3...)开头有个默认的标兵guard(sentinel),这个guard的作用是start_key为空。

    • 每一层都有一个标兵guard,他表示start key为空(min key)

    • 每个guard有个start key,表明guard的起点,用来分割key范围。 这个start key代表guard name

    • 这样每个guard 代表一个[start key, end key)范围的sst文件。

  3. guard有个高度属性h

    • 高度>=h的guard数量,大约是高度>=h+1 guard数量的2倍。(如同skiplist)

    • 上图若不计sentinel guard,则 h>=1 数量为4,h>=2数量为2,h>=3数量是1

  4. 若在level-n上 存在guard k,则在高度level-n+1也存在 guard k(level-n不是bottommost)

  5. guard之间是有序的,无overlap的。

  6. guard内部sst之间是有overlap的。

2.4.3 Compaction

  1. 除了bottommost层以外的compaction

    • 这种情况,是减少写放大的关键。

    • 在除了 bottommost 进行compaction的case中,这个情况发生最多。

    • 若sst范围在 下一层的guard中,则直接move到下一层的guard里。 这里不产生数据IO

    • 若sst范围跨 下一层的两个guard,则sst分裂成两个sst,分别进入对应的guard里,这里有数据的IO。

  2. 在compaction到 bottommost层时, 需要全量合并

2.4.4 不合适的场景

  1. 数据可以全内存。

    • pebblesdb需要额外计算寻找定位guard,从而增加read和range query的延迟

    • 调优方式,max sstables per_guard = 1, 使之 近似等于 LSM

  2. 数据是顺序写入的

    • 因为各个生产的sst之间,没有overlap。LSM实现可以直接move到上层。仅存在修改manifest的IO,没有数据IO

    • pebblesdb实现,可能产生sst的分裂。这里存在数据IO

  3. 爆炸式写入后,紧接着进行大量小range query

    • pebbesdb不是好的选择,经验上 额外开销是LSM的30%

2.5 实现

Pebblesdb的实现,基于HyperLeveldb。HyperLeveldb是leveldb的一个变种。作者说,之所以不选择rocksdb,是因为rocksdb过于复杂

2.5.1 guard的操作

  • InsertGuard:

    • 原理是:当数据写入时,新写入的数据的(k,v),有可能产生一个新 guard k。

    • 代码位置:git commit hash: 703bd01bba47c586fc3fd07273452528826cd38e

    • src/db/write_batch.cc: class GuardInserter : Put(key, value)

  • DeleteGuard :  没有实现这个操作。作者认为,这种empty guard不影响系统。

  • UpdateGuard:  没有这个操作

2.5.2 数据操作API

Get

一次读memtable,immutable memtable,这个与原来一样 若没读到则读各层sst文件 level-0层。level-1层,先找到所在guard 然后,找到guard中所有sst文件。依次读取(在ssd设备上,可以优化成并发归并),获得数据。这里似乎表明,guard sst文件,有优先级的先后顺序。Get的开销比原来大了。

Scan

leveldb 的 scan是个使用Iterator模式,实现的经典的深层次的多路归并。在pebblesdb中,scan到guard的Iterator是个使用sst iterator实现的多路归并 显然,scan也比原来的开销大。

Put&Write:

WriteBatch内部处理,会设置是否产生新Guard。产生新Guard则写入一条特殊数据kTypeGuard (这种数据与kTypeValue,kTypeValue平行) 如上图InsertGuard代码所示,其他流程相同。

2.6 代价和优化

2.6.1 资源

更多的cpu消耗 因为额外的guard逻辑处理 更具复杂性的compaction 更多的memory消耗 元数据信息的增加 bloom filter机器构建 (HyperLeveldb,似乎没有使用bloom filter)

2.6.2 读延迟增加

点查询get/read 因为guard内部sst之间的overlap,所以它在PickGuard后,可能读更多的sst文件 在同样的情况下,这要低于LSM的Get 范围查询scan/range query 在guard内多了一层Iterator的 归并排序

2.6.3 读延迟优化

调整参数,按照情况,使得guard中的sst数量不太多。例如<=4个 如果使用ssd设备,使用ssd的并行通道,进行多线程加速 block index,block cache和bloom filter调优

3 总结

愿意借用热力学熵的概念对Pebblesdb的优化思路做一个类比性总结。

热力学熵, 是度量系统分子运动混乱程度的物理量;类比地,它也可以定性描述一个系统(如宇宙、社会、小屋里、生物体。。。)的混乱程度。

熵增定律,显示了它非凡又深刻的哲学含义,几乎可以安排在我们周围相当多的场景。

熵增定律,它显示了一种系统内部不可逆的单向性。若要对抗这种单向性,需要不断从外部系统汲取负熵。

  • 薛定谔说:生命以负熵为生,靠汲取序来维持组织[5]。对我们来说,负熵就是食物(植物的光合作用的微观世界,是最精彩和神奇的)

  • 社会组织,需要不断的道德、法律、教育、以及公共事业建设,这种建设的努力就是负熵。

LSM-tree为了严格有序性,在写入方面做了大量工作,这些工作就可以认作负熵。而Pebblesdb为了缓解写入放大问题,减少了一些工作,这就是吸取负熵减少,负熵的减少就是Pebblesdb的目标。

但是从LSM到FLSM,系统内部的严格有序性被破坏了,即该系统的熵(guard内部有overlap,存在一定的无序性)增加了,这导致增大了读放大,导致了点读和顺序读延迟的变差。负熵减少引起的别的变化)

这种解决方案,它适合的场景:所面临的的应用需求场景。有这样的应用(例如,冷备(冷备当然可以选择更合适的方案))

  • 希望成本降低

  • 希望设备寿命足够长

  • 希望设备的运行有很低的功耗

  • 非常关注写可用性

  • 同时,读请求量较少,对读延迟容忍性很高,甚至无要求

Pebblesdb的FLSM-tree是LSM-tree的一种泛化形式,它保持了一种按照需求弹性调节的能力,他也可以通过配置退化到LSM(令guard中的文件个数=1)

参考文献:

  1. 《PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees》sosp-2017

  2. 《The Log-Structured Merge-Tree (LSM-Tree)》

  3. 《Skip Lists: A Probabilistic Alternative to Balanced Trees》

  4. 《WiscKey: Separating Keys from Values in SSD-Conscious Storage》 FAST-2016

  5. 《生命是什么》——薛定谔

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章