论文笔记 [SOSP '17] PebblesDB, Building Key-Value Stores using Fragmente...

PebblesDB为了减少写放大，同时又不影响读的效率，提出了一种类似于skiplist的方式来建立LSM-Tree，叫做Fragmented Log-Structured Merge Trees (FLSM)。与rocksdb相比，大概减少了2.4-3倍的写放大，以及6.7倍的write throughput。这篇的idea也比较好懂，用分区的方式来减少compaction，但又可以像skiplist那样来检索，读效率也很高。

Problems

目前的LSM-Tree存在的写放大在于，它会对每一层的sstable写多次。在每一次compaction的时候，需要将上下两层有overlap的sstable读到内存，进行排序，然后再输出。但是这个操作是多次的，频繁的。当上一层又满了之后，又需要重复一遍上述操作，第二层overlap的sstable，又被写了一遍。

如上图中level1的sstable被重复写了3次。这就是写放大的问题所在。而LSM很巧妙的解决了这个问题

Fragmented Log-Structured Merge Trees

这个名字也很直观。据作者说，本来这篇文章一开始投的是Eurosys，结果被拒了，后来重写了paper，才取了这个名字，写成所谓的数据结构创新，PebblesDB是基于FLSM，然后才被sosp接收了。

FLSM的思想就是将每一层的sstables划分逻辑上的区域(level0除外)，每个局域内sstable之间是可以重叠的。给这个区域取一个名字叫Guard。同时每个Guard有一个对应的key。假设有两个连续的Guard：G1:k1，G2:k2，那么G1内的sstable的key就在[k1, k2)这个范围内。

做了这样的划分之后，查找某个key，是先对整个level的Guards进行二分查找，找到某个Guard之后，再查这个Guard里的所有sstable（像level0那样）。是不是和skiplist很像？Guard的划分也是随机的，在插入的时候根据概率来确定是否需要开辟一个新的Guard。并且每一层的概率是不同的，上层稀疏，下层紧密。上一层已经有的Guard，在下一层也必须有。如下图。

那么FLSM是怎么解决写放大的呢？就在于compaction的时候，每一层的sstable的只需要写一次。上一层的sstable需要合并到下层的时候，只需要将上层的sstable做合并排序，然后根据下层Guard的key做划分，添加到不同的Guard中即可。当然这也有个例外，就是在最后一层的时候，因为没有更下层的Guard来添加，只能合并做重写。过程就如下图

EVALUATION

按照上述的结构，FLSM大量减少了写放大。读的时候需要查找单个Guard内的多个sstable（bloom filter优化），因为PebblesDB增加了单个sstable的大小，效果也不差。但是FLSM也有局限性，即在做range query的时候，读放大会很严重（所有level，每个guard中所有sstable）。但是Guard的数量是可以调整的，调成1的时候就和传统的LSM实现一样了。

还有一种情况就是在顺序插入的时候，在这种workload下，所有sstable就没有overlap，之前的LSM实现，可以直接将上层的sstable移到下层不需要做IO。而PebblesDB还是要按照下层Guard的key做划分之后写入，增加了IO。下图为测试结果。

Reference

[1] PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees. SOSP ‘17