SLM-DB：B+树索引和LSM架构结合的尝试

记得本科大三（20年初）通过Leveldb第一次接触到LSM的时候，就在思考是否可以将LSM结构与B+树索引相结合，毕竟一个是write-friendly，一个是read-friendly，但当时光想着写Leveldb的大作业，就把这个事情抛在脑后。最近读到了这篇文章SLM-DB: Single-Level Key-Value Store with Persistent Memory，算是对我当时想法的一种实现。

这篇文章仅仅作为读书笔记使用，有兴趣的同学最好还是去亲自看看论文，里面的一些idea确实非常精彩。

本文主要提出了一种新kv存储模型：Single-Level Merge DB（SLM-DB），它使用了最近较为新颖的PM（persistent memory）技术，并且同时汲取了B+树索引以及LSM-tree结构的优点，使得其有非常好的读写性能，并且在读写放大上也有良好的表现。SLM-DB基于LevelDB(1.20)开发，实验结果表明，SLM-DB相比LevelDB有着1.07-1.96倍的读性能以及1.56-2.22倍的写性能。

前情提要：

1. B+树索引

B+树索引是关系型数据库中常见的索引选择，利用它可以很快的定位一个tuple所在的table。但是它也有一个问题，就是维护起来的成本偏高，在使用过过程中通常伴随着多次少量的random write以及为了维护树平衡性而进行的写放大。

所以，B+树索引对于read有着非常良好的性能，但是在维护上（写上）的开销其实并不算小。

2. LSM树

LSM树结构被广泛地在键值对存储引擎中使用，比如bigtable，RocksDB，LevelDB等等。它有一个对于磁盘（或者说外存）来说非常好的特性：它的写永远是顺序的。所以它对于 write intensive的工作就非常地友好。 但是有得必有失，这个世界就是这么地平衡，这位老兄在读上的表现确实有点拉跨，因为它的读也是顺序的，这就导致它在读取数据时必须要一个文件一个文件地找。同时它的读写放大也非常严重（写放大最坏有50，读放大最坏可以来到340左右）。

SLM-DB的设计与实现

如上图所示，SLM-DB使用PM去存储LevelDB本身的memtable，Immutable部分，这样做的好处是可以省去WAL（write ahead log）的开销，同时对于系统崩溃有更好的容错能力。而sstable和manifest文件则和LevelDB设计的一样存储在磁盘中，但值得注意的是，正如它的名字Single-Level-Memory DB一样，这里的Level只有一层了。

另外视力正常的同学肯定还注意到在PM中还保存了一个叫compaction log和global B+Tree索引的东西。其中compaction log的主要功能是在用作compaction过程的容错，至于只有一层文件如何进行compaction，这个我们先按下不表；而B+树索引就很简单，他保存的是key值以及对于的指针（kv对所在的sstable的table id以及相应的offset），用来快速定位一个kv对。

介绍完了总体架构之后，我会从B+树index和LSM架构的结合使用，GC问题以及合并问题入手讲解SLM-DB的运行过程。

2. B+树与LSM

回忆LevelDB的Put()过程，首先kv对并不会直接被写入disk上的sstable中，而是被加入被称为memtable的buffer pool中。在SLM-DB中也是如此，只有当memtable满足了落盘条件时（比如说大小超过了规定的size)，它才会变成immutable table，然后其中的kv对才会被落盘。

只有当文件被刷盘后，key以及指针才会被加入到B+树索引中。

SLM-DB具体是这么做的，它启动了两个线程，一个负责数据落盘的线程A，另一个负责B+树索引维护的线程B。

线程A会创建一个文件，然后把imm中的kv不断地刷盘，在刷盘结束之后，它会把这个文件的所有kv信息写入到一个queue中，随后线程B就不断从这个queue中读取信息，然后用这些信息去维护B+树索引。注意我这里用的是维护而不是插入，因为这个kv对可能是新的kv，也可能是对旧kv对的更新（这是就要在B+树索引中修改此key对应的指针），也可能是删除操作（这时需要在B+树中删除相应叶子节点）。当queue为空时，说明整个flush过程结束，此时就可以将sstable的元信息append到MANIFEST文件中，随后便可以删除Immutable table。

3. Selective Compaction

现在问题来了，单层的sstable 文件怎么做compaction？

首先我们说一下我们为什么要做compaction。LSM结构是append only的，也就是说对于更新或者是删除操作来说，原先的数据并不会被删除，我们只是往其中加入新的数据并保证新的数据在旧的数据前面，这样新的数据会比原先数据更早地被搜索到，所以每次搜索都可以保证数据都是最新的（这也是为什么它的写非常块）。但是这样做时间一长，我们的sstable 文件中必然充满了大量的garbage（无用的信息），这对于提高磁盘空间利用率非常不利，我们就需要做Garbage collection（GC），这个过程在LevelDB中是由Compaction操作来完成的。其次就是我们对于range query性能的需求，如果数据的分布过于随机，那么我们在进行range query的时候的性能将非常接近于random read，这是不可以忍受的，所以我们需要适当地对数据进行compaction，保持其一定地局部有序性。

但在SLM中，只有一层，要怎么compaction呢？这里文章提出了一种成为selective compaction的策略。

具体的做法是在SLM中维护一个叫做CCL（compaction candidate list）的东西，里面包含了可能会进行compaction的sstable文件。当CCL里面的文件数太多，或者说对于某个sstable有了大量的访问，或是sstable 文件集群发生改变时（比如发生了flush），后台compaction线程就会启动，开始进行compaction操作。

这个后台compaction线程会选择CCL里面的一部分sstable（并不是全部，但是具体多少文章也没有说），对于里面的每一个sstable s，计算s和其他CCL中其他sstable 文件t的 overlapping ratio。计算公式如下

其中s的key range为[S1........Sp], t的key range为[T1......Tq].

然后这些s 会与其重合率最高的 t相合并，生成一个新的文件。整个合并过程也有上文中提到的两个线程AB来完成，线程A负责新文件的创建以及merge sort，完成之后把新文件地kv加入到一个queue中，随后去进行其他文件的compaction。而线程B则会不断地从这个queue中读取kv对，并对B+树进行相应的修改。

3. 1 CCL的入选条件

好了，有了compaction的操作过程之后，那么问题就是什么样的文件有资格被选入CCL？这是我认为整篇文章最为精彩的部分。文章中给出了三种入选的表中

• 有效key的比例

这一点非常容易理解，如果说一个sstable中有效的key的比例过低，那么说明里面的garbage过多，可以用compaction去free掉那些被占用的空间。SLM通过维护一个sstable的live key ratio值来做到这一点。

• 叶子节点扫描

这东西有一点抽象，但我认为非常精彩。具体来说就是这样的：

在一个后台compaction结束之后，都会唤醒一个scan操作，去扫描一定数量（具体多少文章没说）的B+树索引的叶子节点。在扫描过程中，我们记录出现的不同的sstable文件的数量，如果这个文件数量超过了某个值，我们就把这些文件加入到CCL中去。

这个设计非常巧妙：连续扫描B+树索引的叶子节点，说明这些Key应该是紧密相连的，如果扫描结束后出现的unique sstable文件数量较少，则在直觉上（文章没有给出数学证明）可以说明这些数据的连续性尚可，但是如果unique sstable的文件数量很大，则必然说明这些连续的key的连续性稀烂，则可以进行compaction来维护他们的连续性。

• range query的连续性

这个操作依然抽象，但也依然精彩，其实它和上面的叶子节点扫描有异曲同工之妙。具体操作如下：

在进行range query时，我们把range再切分成一个个sub range，每个sub range都含有相同数量的key。在进行query时，我们追踪每一个subquery，并保存每个sub query最终查询了多少个sstable，并取其中最大的那个，记为M。如果这个M大于一个给定的threshold，我们就把这些sstable加入到CCL中去。这对于提升SLM的range query非常有效。

SLM-DB的具体kv存储操作

put一个kv时，先写入内存中的memtable，此时B+树索引不需要有任何改动。随后再memtable满时进行刷盘，并将其中的kv对都在B+树索引中进行维护。

2. Get

首先在memtable中寻找这个key-value，如果找到，直接返回，如果没有找到，则利用B+树索引去sstable中寻找kv对。

3. range query

range query会遇到一个问题：range中的key可能部分存在在memtable，部分存在于sstable中。SLM-DB是这么做的：

使用两个iterator 并发的去遍历b+树索引以及memtable，最后把得到的结果进行一个merge作为最终结果返回个用户。