木鸟杂记

分布式系统,数据库,存储

RocksDB 优化小解(一):Indexing SST

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

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

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

作者:木鸟杂记 https://www.qtmuniao.com/2022/08/21/rocksdb-file-indexer 转载请注明出处

背景

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

leveldb.png

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

  1. 一个可变的 memtable
  2. 一系列不可变的 memtable
  3. 层级组织的一系列 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

indexing-sst.png

举个例子,如上图,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 是值得的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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, +∞)。仅考虑该文件搜索结束就要去下层搜索的情况,则有:

  1. 如果 x < smallest,则需要在下层中比 smallest 小的最右边那个文件(smallest_rb)找。
  2. 如果 x == smallest,即 smallest ≤ x ≤ smallest,则需要在下层比 smallest 大的最左边的文件(smallest_lb)开始找,到比 smallest 小的最右边的文件(smallest_rb)停止。
  3. 如果 smallest < x < largest,则需要在下层比 smallest 大的最左边的文件(smallest_lb)开始找,到比 largest 小的最右边的文件(largest_rb)停止。
  4. 如果 x == largest,即 largest ≤ x ≤ largest,则需要在下层比 largest 大的最左边的文件(largest_lb)开始找,到比 largest 小的最右边的文件(largest_rb)停止。
  5. 如果 x > largest,则需要在下层比 largest 大的最左边那个文件(largest_lb)开始找。

对应代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 的应用场景更泛化一些,比如你可以使用其往下层寻找所有等于给定值的结果。

下面,仍以之前例子,来使用图解释下:

create-indexing-sst.png

可以看出,当上层文件边界(如 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 将建立过程拆为了四趟,分别构建上述四种指针,逻辑封装在了两个函数中:CalculateLBCalculateRB

下面以 CalculateLB 代码为例,简单注释分析:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 计算 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 的四个字段赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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+ 树),容易理解。但对应到代码实现上,有诸多细节和边界情况需要处理,很容易出错。就像二分查找,能写出花来一样,无他,唯多练耳。

参考

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

我是青藤木鸟,一个喜欢摄影、专注大规模数据系统的程序员,欢迎关注我的公众号:“木鸟杂记”,有更多的分布式系统、存储和数据库相关的文章,欢迎关注。 关注公众号后,回复“资料”可以获取我总结一份分布式数据库学习资料。 回复“优惠券”可以获取我的大规模数据系统付费专栏《系统日知录》的八折优惠券。

我们还有相关的分布式系统和数据库的群,可以添加我的微信号:qtmuniao,我拉你入群。加我时记得备注:“分布式系统群”。 另外,如果你不想加群,还有一个分布式系统和数据库的论坛(点这里),欢迎来玩耍。

wx-distributed-system-s.jpg