索引SST文件以获得更好的查找性能

对于Get()请求，RocksDB将遍历可变memtable、不可变memtables列表和SST文件来查找目标键。SST文件按级别组织。

在第0级，文件根据它们被刷新的时间进行排序。 它们的键范围(由 FileMetaData.smallest 和 FileMetaData.larges定义)大部分重叠在一起。 所以它需要查找每个L0文件。

压缩是定期计划的，以从上层获取文件并将它们与来自下层的文件合并。 因此，键/值从L0逐渐向下移动到LSM树。压缩对键/值进行排序并将它们拆分为文件。 从第1级及以下开始，SST文件将根据键进行排序。它们的键范围是相互排斥的。 RocksDB不是扫描每个SST文件并检查键是否在其范围内，而是基于FileMetaData执行二进制搜索。 最大，用于定位可能包含目标键的候选文件。这将复杂度从O(N)降低到O(log(N))。 然而，对于底层，log(N)仍然可能很大。对于fan-out为10%的情况，级别3可以有1000个文件。这需要10个比较来定位候选文件。 对于内存数据库来说，如果每秒可以处理几百万个get( https://github.com/facebook/rocksdb/wiki/RocksDB-In-Memory-Workload-Performance-Benchmarks )，那么这将是一个很大的开销。

对此问题的一个观察结果是: 在构建LSM树之后，SST文件在其级别中的位置是固定的。 此外，它相对于下一级文件的顺序也是固定的。基于这一思想( http://en.wikipedia.org/wiki/Fractional_cascading )，我们可以进行分数级联优化来缩小二值搜索范围。举个例子:

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

第1级有2个文件，第2级有8个文件。现在，我们要查找键80。基于二进制搜索的FileMetaData.largest 告诉你文件1是候选人。然后将key 80与它的FileMetaData.smallest 和 FileMetaData.largest进行比较。决定它是否属于这个范围。 比较显示 80小于FileMetaData.smallest(100)，因此文件1不可能包含键80。我们继续检查第2级。 通常，我们需要在级别2的所有8个文件中进行二叉搜索。但是，由于我们已经知道目标键80小于100，并且只有文件1到文件3可以包含小于100的键，所以我们可以安全地将其他文件排除在搜索之外。 因此，我们将搜索空间从8个文件减少到3个文件。

让我们看另一个例子。我们要得到230号键。第1级的二进制搜索定位到文件2(这也意味着键230大于文件1的FileMetaData.largest 200)。 与文件2的范围比较显示，目标键比文件2的FileMetaData.smallest 300 小。 尽管我们在第1级没有找到key，但是我们已经得到了目标key在200到300之间的提示。 级别2上任何不能与[200,300]重叠的文件都可以安全地排除。因此，我们只需要查看级别2上的文件5和文件6。

受此概念的启发，我们在第1级文件的压缩时间预构建指向第2级文件范围的指针。 例如，级别1的文件1指向左侧的文件3(级别2)和右侧的文件4。 文件2指向级别2文件6和7。在查询时，这些指针用于根据比较结果确定实际的二进制搜索范围。

我们的基准测试显示，对于这里提到的设置( https://github.com/facebook/rocksdb/wiki/RocksDB-In-Memory-Workload-Performance-Benchmarks )，这种优化将查找QPS提高了约5%。