PebblesDB读后感

SOSP2017[1]于10月底在上海举办,因为离得比较近,笔者也去参加学习了一下。会议上的大部分文章都相当的务实,有的甚至可以直接辅助工程实践,比如将要分享的PebblesDB[2]。

10年前Google发表BigTable[3]的论文,推动了基于LSM的KV系统架构的流行,而随着KV系统的应用面超越NoSQL数据库走向越来越广阔的领域,LSM的写放大问题也越来越成为系统稳定的一个阻碍。在LevelDB/RocksDB这种分层思路上,PebblesDB提出了一种减少写放大的思路,下面学习并总结,所述以论文为基础,也有个人观点,客观论述请看原文。

虽然LSM的写放大最近被研究很多,但是就写放大本身而言,是一个很古老的问题。在计算机体系中,如果相邻两层的处理单元不一致或者应用对一致性等有特殊的需求,就很可能出现写放大问题。比如CPU cache和内存cell,文件系统block和磁盘扇区,数据库block和文件系统block,数据库redo/undo,文件系统journal等。文中对写放大给了一个明确的定义,就是用户写入数据和系统写入数据的反比,比如用户写了1M,系统在稳定之后一共向存储设备写出10M,那么放大系数就是10。一些熟知的系统,其放大系数可能超越我们的想象,见下图1(如无特殊说明,图片均来自论文[2])

图1 几款流行KV的放大系数对比

RocksDB放大系数高达42倍,LevelDB也高达27倍,不看绝对数字,只看趋势的话,还是符合直觉的,毕竟RocksDB做了不少加速compaction的功能优化。本文的PebblesDB做的不错,但是仍然超过了10。写放大意味着更多的读写,会造成系统波动,对比如SSD来说会加速寿命衰减,从成本角度说也更加耗电,所以解决写放大就成了一个很重要的问题。我们看这张图的时候,理解放大很严重就可以了,具体数字不必计较,现实中当然有很多针对具体业务的办法把放大控制在一定范围。

作者分析了LevelDB/RocksDB使用的分层结构,认为有一个关键问题导致了其写放大很严重,即L0层数据可能跟Lx层全range交叠。图2很好的说明了这个问题。

图2 解释传统分层模型写放大的原因

图2显示,L0文件里面包含的key同时在L1层的多个文件(甚至全部文件)被包含,所以如果想把L0下推到L1,那么就需要将整个L0/L1文件内的key读出来重新排序写入到L1。典型情况下,L0数据量是L1的1/10,为了这么点数据量重写所有数据显然不划算。L1...Ln道理类似。

思考问题的本质有助于判断终极解决方案,放大问题的本质是一个系统对“随时全局有序"的需求有多么的强烈。所谓随时,就是任何的写入都不能导致系统无序;所谓全局,即系统内任意元单位之间都要保持有序。B-Tree系列是随时全局有序的典型代表,而Fractal tree打破了全局的约束,允许局部无序,提升了随机写能力;LSM系列进一步打破了随时的约束,允许通过后台的compaction来整理排序。在LSM这种依靠后台整理来保序的系统里面,系统对序的要求越强烈,写放大越严重。

PebblesDB针对写放大提出的解决方案是弱化全局有序的约束,其将每一层进行分段,每个段称为一个guard,guard之间没有重叠的key,且每层的guard之间要求保序,但是guard内部可以无序。这个跟skiplist的思路非常像,所以作者说是从skip list借鉴了思想,见图3。

图3 PebblesDB 关键思路

图3看起来确实很像一个skiplist,guard如果在上一层存在,那么下面所有层都存在;同层相邻guard之间无交叠(L0数据少,没有guard)。如前面分析,分层组织结构导致写放大的原因是Li在下推数据的时候跟整个Li+1是重叠的,所以导致所有Li和Li+1的数据都要重写,这显然增加了写放大。而这里将Li和Li+1分为多个guard,那么当Li层数据需要下推的时候,不再是整个Li一起下推,而是可以按照guard为单位来进行,那些基本没有数据变化的guard就不用下推了。在guard下推的过程中,另外一个属性进一步减少了写放大,那就是guard内文件之间不必有序,这样有些文件可能不需要读取,直接move过去就可以了。很奇妙!结果当然也不错,显著减少了写放大,见图4。

图4 PebblesDB 基于guard的思路减少写放大

图4显示,在三个级别的数据规模上,PebblesDB都获得了较低的放大系数,典型对比甚至降低一倍以上。文中还有非常多方面的对比,学术论文的考虑周全、测试严谨是非常值得学习的。

通读全文来看,该思路减少写放大还是比较容易理解的,因为削弱了全局序。当然代价就是scan的时候变差了,因为scan天生对序有强烈的依赖,作者提到可以通过提高IO并发等缓解scan性能的下降。文字还提到了guard带来的其他好处,比如compaction的并行度变大了,每个guard所代表的相邻层可以独立进行compaction以及guard的选择、空guard的处理问题。

[1]. SOSP2017: https://www.sigops.org/sosp/sosp17/program.html

[2]. PebblesDB: Building Key-Value Stores usingFragmented Log-Structured Merge Trees

[3]. BigTable: http://research.google.com/archive/bigtable-osdi06.pdf

[4]. LevelDB: https://github.com/google/leveldb

[5]. RocksDB: https://github.com/facebook/rocksdb/

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20171221G0G95H00?refer=cp_1026

扫码关注云+社区