50

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

 4 years ago
source link: http://threezj.com/2018/11/02/pebblesdb/?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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,又被写了一遍。

ZVFv6j2.png!web 如上图中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,在下一层也必须有。如下图。

UVBzAfA.png!web

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

qIj2Yzj.png!web

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。下图为测试结果。

RZn2Ibi.png!web

Reference

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


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK