论文阅读: 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。
-
平衡树有严格的左旋右旋调平办法,如AVL树,红黑树
-
skiplist的插入新元素,该元素高度h是概率性的。概率通常设置为1/4。初始高度是1
-
skiplist的每个InsertNode操作,其高度由一个,n次随机试验(每次试验是伯努利试验)决定,每次试验有1/4概率把高度抬高1。(这个实验是几何分布的)
-
若高度被抬高,则继续以同样的概率(1/4)进行随机试验,直到命中不抬高或达到最高,则结束试验。
-
从统计概率角度看。高度>=h的元素个数是高度>=(h+1)的元素个数的2倍。所以,其形状如同下图。
下图显示了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 名词说明
下列名词,未找到权威定义,只用自己的理解稍加解释。 恐不确切
-
写放大(Write Amplification)
-
用户写数据请求,写入存储系统落盘一次(从内存flush到磁盘),则无写入放大。
-
当今流行的LSM-tree实现的存储引擎,因为优化读放大,需要不断compaction,这个过程会把数据合并重写。其结果是数据又被重复写过n次。
读放大(Read Amplification)
-
用户读数据请求,读一次磁盘拿到数据, 则读 无放大。
-
当今流行的使用LSM-Tree实现的存储引擎,需要按合并树的优先级顺序,依次读文件。其最坏io次数为 O(合并树个数)
空间放大(Space Amplification)
-
因为LSM-tree本身的特性,空删除,重复key写入,实际删除,陈旧数据不能立即删除,导致空间占用增多
-
以上这些情况,只有发送compaction到最高层时才能执行有效合并,减小实际空间。
最高层:level-0,按照rocksdb和文中统一的观点是level-0。
最底层: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 解决写放大的思路
-
减少LSM-tree的大小,即一个引擎中存储数据要限制。这相当于一个小的object存储系统。
-
LSM-tree中只记录object的meta信息,而把value存到一个log-structured文件中
-
传统做法:想办法限制一个LSM-tree的大小
-
Wisckey做法:把实际数据的大value替换成小value(offset),大value数据存放在别的data文件中。
弱化全局严格有序的思路,这就是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的性质
-
level-0层无guard
-
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文件。
guard有个高度属性h
-
高度>=h的guard数量,大约是高度>=h+1 guard数量的2倍。(如同skiplist)
-
上图若不计sentinel guard,则 h>=1 数量为4,h>=2数量为2,h>=3数量是1
若在level-n上 存在guard k,则在高度level-n+1也存在 guard k(level-n不是bottommost)
guard之间是有序的,无overlap的。
guard内部sst之间是有overlap的。
2.4.3 Compaction
-
除了bottommost层以外的compaction
-
这种情况,是减少写放大的关键。
-
在除了 bottommost 进行compaction的case中,这个情况发生最多。
-
若sst范围在 下一层的guard中,则直接move到下一层的guard里。 这里不产生数据IO
-
若sst范围跨 下一层的两个guard,则sst分裂成两个sst,分别进入对应的guard里,这里有数据的IO。
在compaction到 bottommost层时, 需要全量合并
2.4.4 不合适的场景
-
数据可以全内存。
-
pebblesdb需要额外计算寻找定位guard,从而增加read和range query的延迟
-
调优方式,max sstables per_guard = 1, 使之 近似等于 LSM
数据是顺序写入的
-
因为各个生产的sst之间,没有overlap。LSM实现可以直接move到上层。仅存在修改manifest的IO,没有数据IO
-
pebblesdb实现,可能产生sst的分裂。这里存在数据IO
爆炸式写入后,紧接着进行大量小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)
参考文献:
-
《PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees》sosp-2017
-
《The Log-Structured Merge-Tree (LSM-Tree)》
-
《Skip Lists: A Probabilistic Alternative to Balanced Trees》
-
《WiscKey: Separating Keys from Values in SSD-Conscious Storage》 FAST-2016
-
《生命是什么》——薛定谔