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