社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
在LevelDB/RocksDB这种分层思路上，PebblesDB提出了一种减少写放大的思路，下面学习并总结，所述以论文为基础，也有个人 观点，客观论述请看原文。
虽然LSM的写放大最近被研究很多，但是就写放大本身而言，是一个很古老的问题。在计算机体系中，如果相邻两层的处理单元不一致或者应用对一致性等有特殊的需求，就很可能出现写放大问题。比如CPU cache和内存cell，文件系统block和磁盘扇区，数据库block和文件系统block，数据库redo/undo，文件系统journal等。文中对写放大给了一个明确的定义，就是用户写入数据和系统写入数据的反比，比如用户写了1M，系统在稳定之后一共向存储设备写出10M，那么放大系数就是10。
作者分析了LevelDB/RocksDB使用的分层结构，认为有一个关键问题导致了其写放大很严重，即L0层数据可能跟Lx层全range交叠。下图很好的说明了这个问题：
上图显示，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借鉴了思想，见下图：
上图确实很像一个skiplist，guard如果在上一层存在，那么下面所有层都存在；同层相邻guard之间无交叠（L0数据少，没有guard）。如前面分析，分层组织结构导致写放大的原因是Li在下推数据的时候跟整个Li+1是重叠的，所以导致所有Li和Li+1的数据都要重写，这显然增加了写放大。而这里将Li和Li+1分为多个guard，那么当Li层数据需要下推的时候，不再是整个Li一起下推，而是可以按照guard为单位来进行，那些基本没有数据变化的guard就不用下推了。在guard下推的过程中，另外一个属性进一步减少了写放大，那就是guard内文件之间不必有序，这样有些文件可能不需要读取，直接move过去就可以了。
参考文献：
[1]. PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
