RocksDB 优化小解（一）：Indexing SST-阿里云开发者社区

Google LevelDB 是一个 LSM-Tree 的实现典范。但在开源出来后，为了保持轻量、简洁的风格，除了修修 Bug 之外，一直没有做太大的更新迭代。为了让其能够满足工业环境中多样性的负载， Facebook（Meta）在 Fork 了 LevelDB 之后，做了多方面的优化。硬件方面，可以更有效地利用现代硬件，如闪存和快速磁盘、多核 CPU等；软件方面，针对读写路径、Compaction 也做了大量优化，如 SST 索引、索引分片、前缀 Bloom Filter、列族等。

本系列文章，依据 RocksDB 系列博客，结合源码和一些使用经验，分享一些有趣的优化点，希望能对大家有所启发。水平所限，不当之处，欢迎留言讨论。

本篇是 RocksDB 优化系列第一篇，为了优化深层查询性能，将不同层级的 SST 通过一定方式索引起来。

作者：木鸟杂记，转载请注明出处：https://zhuanlan.zhihu.com/p/556113577

背景

首先，上个之前文章中画的 LevelDB 架构图。

LevelDB 架构图

其中，LevelDB 中一个 Get() 的请求路径，会先后经过：

一个可变的 memtable
一系列不可变的 memtable
层级组织的一系列 SST 文件

其中，0 层中的 SST 文件是由不可变的 memtable 直接刷盘而来的，其键范围（key range，由FileMetaData.smallest and FileMetaData.largest 界定）大部分都互相交叠。因此，在 0 层中要对所有 SST 文件逐个查找。

其他层的 SST 则由上层 SST 不断压实（ Compaction）而来，由此将数据从上层到下层不断沉降。Compaction 过程会将多个 SST 合并在一块，挤出“水分”（重复的 key），然后分裂成多个 SST 文件，因此在 1 层之下，所有的 SST 文件键范围各不相交，且有序。这种组织方式，可以让我们在层内查找时，进行二分查找（O(log(N)) 复杂度），而非线性查找（O(N) 复杂度）。

具体查找方法为，以待查找值 x 为目标，以每个文件的 FileMetaData.largest 组成的数组作为二分对象，不断缩小查找范围，确定目标 SST 文件。如果没有找到包含 x 的 key range 对应的 SST 文件或者对应 SST 文件中没有 x，则向下层继续搜索。

但在大数据量情况下，下层的文件数仍然非常多，对于高频的 Get 操作，即使是二分查找，每层的比较次数，也会线性增长。比如对于 10 的扇出因子（fan-out ration），即下层 SST 文件数量是紧邻上层的十倍，则第 3 层会有将近 1000 的文件数量，最坏情况下需要进行 10 次左右的比较。乍看起来不多，但在百万级别的 QPS 下，这是相当可观的开销。

优化

分析

可以观察到，在 LevelDB 的版本机制下，每个版本（VersionSet，由 Manifest 文件保存）内的 SST 文件数量是定死的、位置也是定死的，则不同层 SST 文件的相对位置也是确定的。

则，我们在每一层进行查找时，其实不用从头开始二分，上层已经二分出的一些位置信息可以进行复用。因此，可以再增加一些类似查找树（如 B+ 树）的层级间的索引结构，以减小底层的二分范围。这种思想称为 Fractional cascading。

Untitled SST Indexing 后查找示意图

举个例子，如上图，1 层有 2 个 SST 文件，2 层有 8 个 SST 文件。假设现在我们想要查找 80，首先在第一层中所有文件的 FileMetaData.largest 中搜索，可以得到候选文件 file 1，但通过与其上下界比较发现小于其下界。于是继续向 2 层搜索，如果 SST 上没有索引，我们需要对所有八个候选文件进行二分，但如果有索引，如上图，我们只需要对前三个文件进行二分。由此，每层搜索的比较次数可以做到常数级别 N（扇出因子，即 RocksDB 中 max_bytes_for_level_multiplier 配置项），不会随着层次的加深而线性增加（ log(N^L) = N*L）。

实现

RocksDB 中的版本是在每次 compaction 后确定的，只有 compaction 才会改变 SST。因此可以在 compaction 构建 SST 时构建相邻层间的 SST 索引。构建时，每个 SST 文件上下界各对应一个指针。那么如何确定每个指针的指向位置呢？与查找过程类似，拿着上界或者下界对应的 key，在下层所有 SST 文件的 FileMetaData.largest 构成的数组中进行搜索，将其指向下层文件该值对应的右界文件。这么选择原因在于，可以通过该指针（如 100 的指针），将下一层中指向的文件（如 file3）右边的文件（file4，file5，…）全部砍掉，从而减小搜索范围。

举个例子，如上图中的 1 层中 file1 的上下界分别为 100 和 200 。对于 100，搜索后落到 2 层中的 file 3 中，则其指向 file 3；对于 200 ，搜索后落到 210 左边，则指向 file 4。

代码

但在 RocksDB 实际代码中（该功能自 3.0 引入），对于任意一个上层文件，实际上是记下了四个索引。通过细分界定范围，可以进一步减小搜索范围。其基本思想是构建 FileIndexer 的时候多花一倍时间、多算一倍的边界，在查找时，就可以更进一步缩小查找范围。鉴于 SST 都是一次构建，多次查询，这种 tradeoff 是值得的。

struct IndexUnit {
    IndexUnit()
      : smallest_lb(0), largest_lb(0), smallest_rb(-1), largest_rb(-1) {}
    // Point to a left most file in a lower level that may contain a key,
    // which compares greater than smallest of a FileMetaData (upper level)
    // 下层文件中比 FileMetaData.smallest 大的第一个文件下标。 
    // target > FileMetaData.smallest 时搜索用。
    int32_t smallest_lb;
    // Point to a left most file in a lower level that may contain a key,
    // which compares greater than largest of a FileMetaData (upper level)
    // 下层文件中比 FileMetaData.largest 大的第一个文件下标。 
    // target > FileMetaData.largest 时搜索用。
    int32_t largest_lb;
    // Point to a right most file in a lower level that may contain a key,
    // which compares smaller than smallest of a FileMetaData (upper level)
    // 下层文件中比 FileMetaData.smallest 小的最后一个文件下标。 
    // target < FileMetaData.smallest 时搜索用。
    int32_t smallest_rb;
    // Point to a right most file in a lower level that may contain a key,
    // which compares smaller than largest of a FileMetaData (upper level)
    // 下层文件中比 FileMetaData.largest 小的最后一个文件下标。 
    // target < FileMetaData.largest 时搜索用。
    int32_t largest_rb;
  };

上面注释看起来比较拗口，但是从如何对其使用入手，就能比较容易理解了。假设我们现在要查找的值为 x，待比较的某个上层文件上下界为[smallest, largest] ，则该上下界将键空间切分为五个区间：(-∞, smallest), smallest, (smallest, largest), largest, (largest, +∞)。仅考虑该文件搜索结束就要去下层搜索的情况，则有：

如果 x < smallest，则需要在下层中比 smallest 小的最右边那个文件（smallest_rb）找。
如果 x == smallest，即 smallest ≤ x ≤ smallest，则需要在下层比 smallest 大的最左边的文件（smallest_lb）开始找，到比 smallest 小的最右边的文件（smallest_rb）停止。
如果 smallest < x < largest，则需要在下层比 smallest 大的最左边的文件（smallest_lb）开始找，到比 largest 小的最右边的文件（largest_rb）停止。
如果 x == largest，即 largest ≤ x ≤ largest，则需要在下层比 largest 大的最左边的文件（largest_lb）开始找，到比 largest 小的最右边的文件（largest_rb）停止。
如果 x > largest，则需要在下层比 largest 大的最左边那个文件（largest_lb）开始找。

对应代码如下：

if (cmp_smallest < 0) { // target < smallest，使用 smallest_rb 作为右界
  *left_bound = (level > 0 && file_index > 0)
                    ? index_units[file_index - 1].largest_lb
                    : 0;
  *right_bound = index.smallest_rb;
} else if (cmp_smallest == 0) {
  *left_bound = index.smallest_lb;
  *right_bound = index.smallest_rb;
} else if (cmp_smallest > 0 && cmp_largest < 0) {
  *left_bound = index.smallest_lb;
  *right_bound = index.largest_rb;
} else if (cmp_largest == 0) {
  *left_bound = index.largest_lb;
  *right_bound = index.largest_rb;
} else if (cmp_largest > 0) {
  *left_bound = index.largest_lb;
  *right_bound = level_rb_[level + 1];
} else {
  assert(false);
}

注：当 x == smallest 或者 x == largest 时，对于 RocksDB 使用场景来说，上层已经找到了，无须再往查找下层。但该 FileIndexer 的应用场景更泛化一些，比如你可以使用其往下层寻找所有等于给定值的结果。

下面，仍以之前例子，来使用图解释下：

RocksDB 中 SST 建立索引

可以看出，当上层文件边界（如 100）落到下层文件内（如 file 3 [95, 110]）时，该边界 lb 和 rb 指针指向相同，蜕化为单指针；当文件边界（如 400）落到下层文件空隙内（如 file 7 和 file 8 之间），lb 和 rb 才指向不同，从而在搜索时，相对单指针，总体上减少一个待扫描文件。

另一方面，注意到，当上层文件边界值（如 400）落在下层文件空隙内时（即该值在下层肯定不存在），有 largest_rb < largest_lb ，如果搜索值是 400，则利用此指针直接导致 left_bound > right_bound，搜索结束。

在具体实现时， RocksDB 使用了双指针比较法，一个指针迭代上层，一个指针迭代下层，一次迭代即可为所有文件建立一种索引。为减少代码中的分支判断，使逻辑清晰，RocksDB 将建立过程拆为了四趟，分别构建上述四种指针，逻辑封装在了两个函数中：CalculateLB 和 CalculateRB。

下面以 CalculateLB 代码为例，简单注释分析：

// 计算 lower_files 中比某值大的最左（从左到右第一个）文件下标
void FileIndexer::CalculateLB(
    const std::vector<FileMetaData*>& upper_files, // 上层 SST 文件
    const std::vector<FileMetaData*>& lower_files, // 下层 SST 文件
    IndexLevel* index_level,
    std::function<int(const FileMetaData*, const FileMetaData*)> cmp_op,
    std::function<void(IndexUnit*, int32_t)> set_index) {
  const int32_t upper_size = static_cast<int32_t>(upper_files.size());
  const int32_t lower_size = static_cast<int32_t>(lower_files.size());
  int32_t upper_idx = 0;
  int32_t lower_idx = 0;
  IndexUnit* index = index_level->index_units;
  while (upper_idx < upper_size && lower_idx < lower_size) { // 双指针比较法
    // 总是跟 lower_files[lower_idx].largest 比较
    int cmp = cmp_op(upper_files[upper_idx], lower_files[lower_idx]);
    if (cmp == 0) {
      set_index(&index[upper_idx], lower_idx);
      ++upper_idx;
    } else if (cmp > 0) {
      // 下层 lower_idx 处文件的最大值比给定值小，则不满足条件
      ++lower_idx;
    } else {
      // 下层 lower_idx 处文件的最大值相对给定值第一次变大，满足条件，设置索引
      set_index(&index[upper_idx], lower_idx);
      ++upper_idx;
    }
  }
  while (upper_idx < upper_size) {
    // 下层文件用完了，表示现在所有余下的上层文件比所有下层文件都大
    // 于是让他们都指向 lower_size，即不存在（下层文件下标为 0~lower_size-1）。
    set_index(&index[upper_idx], lower_size);
    ++upper_idx;
  }
  // 如果是上层文件用完了，不做额外处理。因为函数作用是为上层文件设置索引，
  // 上层文件用完了，说明已经为所有上层文件设置了索引。
}

四趟调用，分别为上层每一个文件索引项 IndexUnit 的四个字段赋值。

CalculateLB(
    upper_files, lower_files, &index_level,
    [this](const FileMetaData* a, const FileMetaData* b) -> int {
      return ucmp_->CompareWithoutTimestamp(a->smallest.user_key(),
                                            b->largest.user_key());
    },
    [](IndexUnit* index, int32_t f_idx) { index->smallest_lb = f_idx; });
CalculateLB(
    upper_files, lower_files, &index_level,
    [this](const FileMetaData* a, const FileMetaData* b) -> int {
      return ucmp_->CompareWithoutTimestamp(a->largest.user_key(),
                                            b->largest.user_key());
    },
    [](IndexUnit* index, int32_t f_idx) { index->largest_lb = f_idx; });
CalculateRB(
    upper_files, lower_files, &index_level,
    [this](const FileMetaData* a, const FileMetaData* b) -> int {
      return ucmp_->CompareWithoutTimestamp(a->smallest.user_key(),
                                            b->smallest.user_key());
    },
    [](IndexUnit* index, int32_t f_idx) { index->smallest_rb = f_idx; });
CalculateRB(
    upper_files, lower_files, &index_level,
    [this](const FileMetaData* a, const FileMetaData* b) -> int {
      return ucmp_->CompareWithoutTimestamp(a->largest.user_key(),
                                            b->smallest.user_key());
    },
    [](IndexUnit* index, int32_t f_idx) { index->largest_rb = f_idx; });

小结

对 SST 建立索引的方法比较直观（可以类比 B+ 树），容易理解。但对应到代码实现上，有诸多细节和边界情况需要处理，很容易出错。就像二分查找，能写出花来一样，无他，唯多练耳。

参考

RocksDB 博客，Indexing SST Files for Better Lookup Performance， http://rocksdb.org/blog/2014/04/21/indexing-sst-files-for-better-lookup-performance.html
维基百科，分散级联， Fractional cascading，https://en.wikipedia.org/wiki/Fractional_cascading
RocksDB github FileIndexer：https://github.com/facebook/rocksdb/blob/3.0.fb.branch/db/file_indexer.cc

RocksDB 优化小解（一）：Indexing SST

背景

优化

分析

实现

代码

小结

参考

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

RocksDB 优化小解（一）：Indexing SST

背景

优化

分析

实现

代码

小结

参考

热门文章

最新文章

相关电子书