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 using Fragmented 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/
