论文分类与总结

lsm structure

1. PebblesDB：SOSP 17

   关键词：optimization for write amplification，guards

   受到skiplist数据结构的启发，将LSM-Tree的每一个level中添加guard，每一个guard内的数据（SSTable）可以有overlapping，但是不同的guard之间没有overlapping，并且保证guard之间的order关系。这样在Li向Li+1进行compaction的时候，只需要移动Li层的数据即可，不需要再将Li+1层的相对应的数据进行rewrite，从而改善了write amplification，但是sacrifile read performance，especially range query。

2. SLM-DB：FAST 19

   关键词：persistent memory，B+-tree，single level lsm

   结合LSM-tree与B+-tree的优点，并且利用了addressable persistent memory这种新硬件，实现了一种 novel LSM-tree structure（single level merge -DB）。这样的实现既可以使用LSM-tree带来的write performance，并且大大减小了write amplification，并且带来的相对较好的read performance。

write amplification

read amplification

filter optimization

1. ElasticBF: Hotstorage 18

   关键词：Bloom filter

   将bloom filter分解成过个小的bloom filter unit，并且保证总的false positive的值不会发生变化；然后根据SSTable访问的频率选择载入哪些SSTable的bloom filter unit，以及剔除哪些访问频率不高或者过期的SSTable的bloom filter unit，从而使得整体的数据的false positive降到最低。文章中提出了一种形式化的数学方法来表示整体系统的false positive。