【SOSP 2017】PebblesDB 技术解读

2019-12-20 10:34:29

1. Background

以 LevelDB 和 RocksDB 为代表的 LSM-tree key-value 存储引擎在生产环境中被广泛应用，所以当前针对其优化的研究也非常多，在近几年的会议上也是热门的话题，本篇就是阅读 sosp 2017 《PebblesDB : building key-value stores using fragmented log-structured merge trees》之后，觉得其通过借鉴 Skip List 的设计理念，触类旁通的应用到 LSM-tree 的 sstable 管理的 idea 非常精妙，所以写在这里分享给大家。

1.1 Basic Introduction

PebblesDB 主要还是针对 LSM-tree 的老问题，write amplification 做优化。关于 LSM-tree 的基本原理和存在的问题，可以参见之前一篇【FAST 2016】Wisckey-Separating Keys from Values 的章节。这里就只简单的给一组不同 LSM-tree 实现的 write amplification 数据：

作者受 Skiplist 的启发，设计了一种 Fragmented Log-Structured Merge Trees data structure （FLSM-tree），并开发开发出了一个 key-value 单机存储原型 PebblesDB，由 Figure.1 可以看出， PebblesDB 的 write amplification 远小于 leveldb 和 rocksdb。

1.2. Write Amplifcation Root Cause

在介绍 FLSM-tree 之前，先来分析下 LSM-tree write amplification 的根本原因，一句话描述就是：一些 key-value 在某一层中反复的 compaction ，从而造成反复的 rewrite。下面将通过一个例子着手来解释，如下图：

我们知道 level n 往 level n+1 挪动的时候，是通过 Compaction，其大致的过程是，这里假定 level n 中的 sstable A 要通过 Compaction merge 到 level n+1，那么就会在 level n+1 找到所有和 level A 有 [min key, max, key] 有交集的 sstable 做归并排序合并成 level n+1 新的 sstable，（1）例如 Figure 2. 的 t2 时刻， level 0 的 sstable [20, 210] 与 level 1 的两个 sstable 合并，这个 1，10 ，100 和 200，210，400 被重写了遍；（2）然后在 t4 时刻，发生第二次 Compaction，由于 level 0 的 sstable 和 level 1 的两个 sstable 又都有交集，这个时候 1，10 ，100 和 200，210，400 又被重写了第二遍；（3）在 t6 时刻，同理由于由于 level 0 的 sstable 和 level 1 的两个 sstable 又都有交集，这个时候 1，10 ，100 和 200，210，400 又被重写了一遍，这个时候已经被重写了第三遍了。

由上面的例子可见一斑，Compaction 造成了一些 key-value 反复的 rewrite，从而造成了 LSM-tree 的 write amplification，如果有什么方法可以控制一个 key-value 在某一层被 rewrite 的次数那就完美了，那么结合 LSM-tree 的层数限制，每个 key-value 坏情况的 write amplification 都将是有上界的。这也正是后面要介绍 FLSM-tree 能做到的。

PebblesDB 受 Skiplist 的启发，设计了 FLSM-tree，其可以保证 so ensures that data is written exactly once in most levels，是不是很牛。

2. PebblesDB

2.1. Skiplist

既然受 Skiplist 的启发，那么我们先来看看 Skiplist 的，在刚开始接触 Skiplist 的时候，并没有很好的理解 Skiplist 的精妙之处，实际上 Skiplist 有一个很精妙的东西叫 Guard，如下图，给出了一个逻辑的 Skiplist：

其中低层的 level 1 都是所有的数据，保持有序，上面的 level 2 和 level 3 上的所有节点其实都是 Guard，那什么是 Guard 呢？其实就是高速通道，也就是索引层，实际上和 B+ tree 索引类似，其基本结构是一样的，只是节点插入和删除的时候，索引的层的选择有一些差异，Skiplist 是基于一定的随机选择策略来选择索引 Guard，而 B+ 则是一棵有序的搜索树，通过旋转，节点的合并和分列来维护树的平衡，但是本质上是一样的。

2.2. FLSM-tree

FLSM-tree 借鉴 Skiplist 的 Guard 思想，给 LSM-tree 的每个 level 加了一些 Guard 数据，通过 Guard 来组织数据，尽管很简单，但是思路很巧妙，下面通过一个例子来说明:

level n 有数据 {1， 20， 45，101， 245}

level n+1有三个guard分别为：1、40、200

那么 level n 往level n+1 Compaction 的时候不会去和其他的 sstable 合并，而是将自己的 sstable 按照 guard 切分成多个 sstable（被称为 fragement），合并到 level n+1之后就变成了：

level n+1:

guard: |     1     |      40       |    200      |

       | { 1,20 }  |  { 45,101 }   |   {245}     |

3. Summary

PebblesDB 借鉴 Skiplist 的思路非常的巧妙，虽然简单，但是结合 1.2. 的例子可以看到其明显的可以减少 Write amplification，而 write amplification 的减少，将直接提升 write 的性能和稳定性。当然还有更多这里没有介绍，感兴趣的可以详细的阅读论文，这里不再详细的描述：

guard 的选择，对 skiplist 来说，guard 的选择是很关键，它是每个 level 的 fragement 是否均衡的关键，而 fragement 的均衡性将大大的影响到 read 的性能
数据是动态的在不同的 level 之间迁移的，那么 guard 肯定也不是一层不变的，如何 insert/delete 也是一个非常重要问题，而且一旦 guard 发生变化，那么相应的 fragement 的数据将产生大量的移动和 rewrite，是一笔不小的开销，处理起来也是相当的不容易
read 的性能问题，由于 Compaction 的时候，sstable 只是简单地被切分到不同的 fragement ，那么意味不同的 fragement 的数据被分散在不同的 sstable 文件中，而且这些 sstable 文件相互之间是可能有交集，那么自然对读的性能是有影响？这其实也是第1、2 个问题需要考虑的
PebblesDB 尽管核心 idea 有点意思，但是还是存在很多问题需要克服，具体工程的意义其实很难说。如果想希望工程借鉴意义更大的优化可以参考 Fast 2016 的 WiscKey [3]，其 key-value 分离的策略可能更加简单有效，目前也已经被一些公司实践过，例如 TiDB 的新存储引擎 Tian [4]，自己公司内部其实很早就有类似的优化思路的产品，并且大规模的在线上环境使用过。

后，参考文献 [2] 有个观点觉得非常赞同：系统对序的要求越强烈，写放大越严重。

Notes

限于作者水平，难免有理解和描述上有疏漏或者错误的地方，欢迎共同交流；部分参考已经在正文和参考文献列表中注明，但仍有可能有遗漏的地方，有任何侵权或者不明确的地方，欢迎指出，必定及时更正或者删除；文章仅供于学习交流，转载注明出处。

References
[1]. PebblesDB building key-value stores using fragmented log-structured merge tree. http://www.cs.utexas.edu/~vijay/papers/sosp17-pebblesdb.pdf
[2]. PebblesDB读后感. https://zhuanlan.zhihu.com/p/32225460
[3]. 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.