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）开始找。
对应代码如下：
代码语言：javascript复制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
题图故事
最近北京的天空，云彩总是很好看往期文章： 漫谈 LevelDB 数据结构（三）：LRU 缓存（ LRUCache） 漫谈 LevelDB 数据结构（二）：布隆过滤器（Bloom Filter） 漫谈 LevelDB 数据结构（一）：跳表（Skip List）
