Home未分类论文阅读: PebblesDB

论文阅读: PebblesDB

2009 年 7 月 26 日

总 第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倍。所以，其形状如同下图。

  • 下图显示了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次。

  • 读放大（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 解决写放大的思路

    1. 减少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的性质

      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文件。

    1. guard有个高度属性h

      • 高度>=h的guard数量，大约是高度>=h+1 guard数量的2倍。（如同skiplist）

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

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

    3. guard之间是有序的，无overlap的。

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

      5. 2.4.3 Compaction

      1. 除了bottommost层以外的compaction

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

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

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

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

    5. 在compaction到 bottommost层时， 需要全量合并

      6. 2.4.4 不合适的场景

      1. 数据可以全内存。

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

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

    6. 数据是顺序写入的

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

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

    7. 爆炸式写入后，紧接着进行大量小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. 《生命是什么》——薛定谔

        Related Posts

        About The Author

        fenny