Indexing-SST-Files-for-Better-Lookup-Performance¶

对于一个 Get() 请求，RocksDB 遍历可变 memtable，不可变 memtable 列表，以及 SST 文件，以查找目标 key。SST 文件被组织成许多层。

在 Level 0，文件基于他们落盘的时间进行排序。他们 key 范围（通过 FileMetaData.smallest 和 FileMetaData.largest 来定义）通常会相互交叉覆盖。所以他需要查找所有 L0 文件。

压缩会被周期性地调度起来，从上层捡取一些文件然后跟下层的一些文件合并他们。就结果而言，键值对会被从 L0 逐渐移动到在 LSM 树的下层。压缩会对键值对排序，然后把它们切分到文件中。从 level 1 开始往下，SST 文件根据 key 进行排序。他们的 key 范围互相无交集。为了检查一个 key 是否落在一个 SST 文件中，Rocksdb 不需要检查每个 SST 文件，只需要进行针对 FileMetaData.largest 进行一次二分搜索，就能定位到一个备选文件，该文件可能包含目标 key。这把复杂度从 O(N) 降低到 O(log(N))。然而，log(N) 对于最底层仍旧是非常大的。对于一个扇出比例为 10，层数为 3 的，可以有 1000 个文件。这需要 10 个比较来确定一个候选文件。对于一个需要每秒进行好几百万操作的内存数据库，这个开销是非常大的。

针对这个问题，一个可以观察到的事实是：在 LSM 树构建后，一个 SST 文件在某一层的位置是固定的。更进一步，他相对于下一层的位置，也是固定的。基于这个观点，我们可以实施分级层叠类的优化来降低二分搜索范围。这里是一个例子：

                                         file 1                                          file 2
                                      +----------+                                    +----------+
level 1:                              | 100, 200 |                                    | 300, 400 |
                                      +----------+                                    +----------+
           file 1     file 2      file 3      file 4       file 5       file 6       file 7       file 8
         +--------+ +--------+ +---------+ +----------+ +----------+ +----------+ +----------+ +----------+
level 2: | 40, 50 | | 60, 70 | | 95, 110 | | 150, 160 | | 210, 230 | | 290, 300 | | 310, 320 | | 410, 450 |
         +--------+ +--------+ +---------+ +----------+ +----------+ +----------+ +----------+

Level 1 有 2 个文件，level 2 有 8 个文件。现在，我们希望检索 key 80。一个基于 FileMetaData.largest 的二分搜索告诉你，文件 1 是候选者。然后 key 80 会与 FileMetaData.smallest 和 FileMetaData.largest 进行比较以确定他是不是在范围内。比较显示，80 小于文件的 FileMetaData.smallest（100），所以文件 1 不可能包含 key 80。我们继续检查 level 2。通常，我们需要在 level 2 的 8 个文件中做二分搜索。但是因为我们已经知道目标 key 80 小于 100，且只有一个文件 1 到文件 3 可以包含小于 100 的 key，我们可以在搜索的时候很安全地移除其他文件。就结果而言，我们把搜索空间从 8 个文件降低到了 3 个。

我们看看另一个例子。我们希望获得 key 230。一个 level 1 的二分搜索定位到文件 2（这也暗示着 key 230 大于文件 1 的 FileMetaData.largest 200）。一个与文件 2 的范围比较显示，目标 key 小于文件 2 的 FileMetaData.smallest 300。尽管，我们不能再 level 1 中找这个 key，但是我们得到了启示，key 在范围 200 和 300 之间。在 level 2 任何与 [200,300] 没有交集的文件都可以安全地被移除。就结果而言，我们只需要检索 level 2 的文件 5 和 6.

受这个概念启发，我们在压缩的时候预建立指针，从 level 1 的文件指向一个范围到 level 2.例如，level 1 的文件 1 指向文件 3（在 level 2）的左边，以及文件 4 的右边。文件 2 会指向 level 2 的文件 6 和文件 7.查询的时候，这些指针会被用于根据比对结果，决定实际的二分搜索范围。

我们的压力测试显示，这个优化对这里提到的设置，增加了大概 5% 左右的查询 QPS