RocksDB SST 文件索引优化借助 Fractional Cascading 思想加速点查询【免费下载链接】rocksdbA library that provides an embeddable, persistent key-value store for fast storage.项目地址: https://gitcode.com/gh_mirrors/ro/rocksdb导读本文围绕 RocksDB 中Get()点查询的完整查找路径展开数据依次经过 mutable memtable、immutable memtable 列表与各级 SST 文件最终在 LSM 树的深层级中定位目标 key。面对底层海量 SST 文件带来的二分查找开销RocksDB 借鉴 Fractional Cascading分数级联思想在文件元数据FileMetaData比较结果的基础上预构建层间索引将下层文件的搜索范围从整层收窄到与上层文件实际重叠的少数文件。读完本文你将理解这一优化背后的两个关键不变量、FileIndexer的数据结构与构建/查询流程以及它在源码中的落地位置与实测收益。一次 Get 的完整旅程从 memtable 到 SST 文件在 RocksDB 中一次Get()请求的目标 key 会按照由新到旧的顺序在以下结构中依次查找mutable memtable当前正在写入的内存表immutable memtable 列表已被冻结、等待 flush 到磁盘的只读内存表各级 SST 文件落盘后的排序字符串表Sorted String Table按 Level 0、Level 1、Level 2……逐层组织。其中 Level 0L0与其他层级的行为有本质区别L0 的文件是按照flush 的时间顺序排列的它们的 key 范围由每个文件元数据中的FileMetaData.smallest与FileMetaData.largest定义彼此高度重叠因此一次查找必须遍历 L0 的全部文件逐一判断目标 key 是否落在其范围内。这正是FilePicker在PrepareNextLevel()中对 L0 采用“start_index 0、逐个检查”策略的原因见 db/version_set.cc。Compaction 会周期性触发把上层文件挑选出来与下层文件合并将键值数据从 L0 逐步向下搬运。Compaction 过程对键值排序并切分成新的文件。从 Level 1 开始SST 文件按照 key 排序且同层文件之间的 key 范围互不重叠mutually exclusive——正是这个有序性让 L1 及以下层级的查找不再需要全层扫描。有序层级的二分查找O(N) 到 O(log(N)) 的跃迁对于 L1 及以下层级由于文件按 key 有序且范围互斥RocksDB 不再逐个遍历文件判断范围而是基于FileMetaData.largest执行二分查找定位一个可能包含目标 key 的候选文件这使复杂度从 O(N) 降为 O(log(N))。在源码层面这一步体现在VersionStorageInfo构建的LevelFilesBrief上PrepareNextLevel()中通过FindFileInRange()在受限范围内二分查找“largest ikey 的最早文件”例如 db/version_set.cc// On Level-n (n1), files are sorted. Binary search to find the // earliest file whose largest key ikey. Search left bound and // right bound are used to narrow the range. start_index FindFileInRange(*internal_comparator_, *curr_file_level_, ikey_, static_castuint32_t(search_left_bound_), static_castuint32_t(search_right_bound_) 1);然而log(N) 在底层依旧可能很大。假设层级间的 fan-out 比例为 10Level 3 就可能有 1000 个文件定位一个候选文件需要约 10 次比较。对于追求每秒钟数百万次 Get 的内存型工作负载而言这 10 次比较是一笔不可忽视的固定开销。核心观察LSM 树中文件位置的两个不变量针对上述开销这篇技术文章的核心观察在于LSM 树构建完成后SST 文件在其所属层级内的位置是固定的同时它相对于下一层文件的顺序也是固定的。这两个不变量非常重要因为它们意味着上层文件与下层文件的“相对位置关系”可以在一次 Compaction或 Version 构建完成后一次性计算出来并在后续无数次查询中反复复用。这正是 Fractional Cascading 一类优化的前提——把本来需要在每一层重复进行的比较预先折叠进层间的索引结构里。下面用一个两层的小例子说明收益来源。下图为 Level 1 与 Level 2 的 SST 文件及其 key 范围示意图中 Level 1 有 2 个文件Level 2 有 8 个文件。接下来以文档中的两个查找为例看比较结果如何被“级联”到下一层。例子 1查找 key 80对 Level 1 按FileMetaData.largest二分查找定位到 file 1。随后将 key 80 与 file 1 的smallest、largest比较发现80 小于FileMetaData.smallest100因此 file 1 不可能包含 key 80需要转向 Level 2。按朴素做法接下来要在 Level 2 的 8 个文件上重新做一次完整二分查找。但由于我们已经知道目标 key 80 100而 Level 2 中只有 file 1 到 file 3 的 key 才可能小于 100file 3 的 key 范围为 95–110其余文件的 smallest 均大于等于 150因此其余文件可以被安全排除。搜索空间从 8 个文件收窄到3 个文件。例子 2查找 key 230对 Level 1 二分查找定位到 file 2这同时意味着 key 230 大于 file 1 的largest200。将 key 230 与 file 2 的范围比较发现它小于 file 2 的smallest300。虽然 Level 1 上没找到 key但我们推导出了 hint目标 key 落在区间 [200, 300] 内。Level 2 上任何无法与 [200, 300] 相交的文件都可以安全排除。结果只需要检查 Level 2 的 file 5 和 file 6搜索范围从 8 个文件收窄到2 个文件。实现Compaction 时预构建层间指针受此思想启发RocksDB 在 Compaction更准确地说是每次构建新的Version时为上层文件预构建指向下层文件范围的指针。沿用文档例子Level 1 的 file 1 在左侧指向 Level 2 的 file 3、右侧指向 file 4file 2 指向 Level 2 的 file 6 与 file 7。查询时根据当前文件比较结果选择左/右指针即可确定下一层实际二分查找的边界。FileIndexer 的数据结构该优化在源码中的实现主体是 db/file_indexer.h 中的FileIndexer类。其头文件注释清晰地总结了复用比较结果的三种情形(1) key 小于文件的 smallest说明它也小于 largest可用基于 “smallest smallest” 预计算的索引提供右边界(2) key 位于 smallest 与 largest 之间可用 “smallest largest” 提供左边界、用 “largest smallest” 提供右边界(3) key 大于文件的 largest说明它也大于 smallest可用基于 “largest largest” 预计算的索引提供左边界。对应地每个上层文件在下一层都维护四个边界值即 db/file_indexer.h 中的IndexUnitstruct IndexUnit { // 下层中可能包含“大于 smallest 的 key”的最左文件 int32_t smallest_lb; // 下层中可能包含“大于 largest 的 key”的最左文件 int32_t largest_lb; // 下层中可能包含“小于 smallest 的 key”的最右文件 int32_t smallest_rb; // 下层中可能包含“小于 largest 的 key”的最右文件 int32_t largest_rb; };所有IndexUnit按层组织在autovectorIndexLevel next_level_index_中并由level_rb_记录每层文件的右边界。构建过程UpdateIndex索引的构建入口是FileIndexer::UpdateIndex()db/file_indexer.cc它针对 L1 到 Ln-1 的每一层用上层文件与下层文件各跑四遍线性扫描两次CalculateLB()left bound分别用“上层的 smallest/largest 与下层的 largest 比较”得到smallest_lb与largest_lb两次CalculateRB()right bound分别用“上层的 smallest/largest 与下层的 smallest 比较”得到smallest_rb与largest_rb。CalculateLB/CalculateRB采用双指针线性推进db/file_indexer.cc每步仅做一次比较器调用复杂度为 O(上层文件数 下层文件数)构建成本可控。内存则在VersionStorageInfo持有的Arena中统一分配。触发时机Version 构建时在版本管理层面VersionStorageInfo::PrepareForVersionAppend()在每次生成新 Version 时调用GenerateFileIndexer()见 db/version_set.cc进而触发file_indexer_.UpdateIndex(arena_, num_non_empty_levels_, files_)见 db/version_set.h。由于每次 Compaction / Flush 后文件集合都会变化索引也会随之整体重建而两次 Compaction 之间的大量查询则可以零成本复用这套预计算结果。查询路径FilePicker 与 GetNextLevelIndex查询时FilePickerdb/version_set.cc在GetNextFile()中逐层推进。对每个当前层文件它先用用户比较器算出cmp_smallest与cmp_largest两个比较结果然后调用 db/version_set.cc 中的file_indexer_-GetNextLevelIndex( curr_level_, curr_index_in_curr_level_, cmp_smallest, cmp_largest, search_left_bound_, search_right_bound_);GetNextLevelIndex()db/file_indexer.cc根据cmp_smallest/cmp_largest的符号分五种情况返回下一层的[left_bound, right_bound]搜索区间——这正是头文件注释中三种比较情形的直接编码。拿到收窄后的边界后PrepareNextLevel()中的FindFileInRange()只在[search_left_bound_, search_right_bound_ 1)区间内做二分而不是全层二分。若上层推导出的区间为空left_bound right_bound则直接跳过该层并重置为全范围搜索下一层db/version_set.cc避免无效比较。值得一提的还有边界情况当某一层文件数不超过 3 时FilePicker会跳过 key range 过滤与级联逻辑直接逐个查询db/version_set.cc因为此时过滤的开销可能高于直接查找——这说明该优化针对的是文件数量众多的深层级场景。正确性验证file_indexer_test.ccdb/file_indexer_test.cc 为FileIndexer提供了系统性的单元测试覆盖了所有典型几何关系Empty空版本0 层下的安全构建no_overlap_left/no_overlap_right上层文件整体位于下层文件左侧/右侧验证极端排除场景下边界正确回退到[0, -1]或全范围empty_L2中间层为空时索引尺寸为 0查询正确退化为全范围搜索mixed多层文件交错重叠的混合场景逐一断言GetNextLevelIndex()在不同cmp_smallest/cmp_largest组合下返回的左右边界例如 Level 1 的 file 1 在(cmp_smallest1, cmp_largest1)时返回[1, 4]db/file_indexer_test.cc。测试中的IntComparator与IntKey()构造了精确可控的整数 key 范围直观验证了“比较结果级联到下一层搜索边界”这一核心语义。实测收益作者在博客中报告在与 RocksDB In-Memory Workload Performance Benchmarks 类似配置下的基准测试表明该优化将点查询 QPS 提升了约5%。考虑到深层级每次查找可节省约 8–10 次文件级比较对应文中的 fan-out 10、L3 千文件场景这个数字在内存型高吞吐工作负载下是相当可观的——尤其是当这些比较发生在每次 Get 的热路径上时。总结RocksDB 对 SST 文件查找的这套优化可以概括为三步① 利用 LSM 树文件位置固定的两个不变量② 在 Version 构建时用线性扫描预计算上层文件对下层文件的左右边界③ 查询时用当前文件的两三次比较结果直接确定下一层的二分范围。从复杂度上看原本在 Level L 上需要检查 O(N^L) 量级的文件现在只需检查约 N即max_bytes_for_level_multiplier对应的重叠文件数个文件。这项设计与FileIndexer类、FilePicker查询器一起完整落地于 db/file_indexer.h、db/file_indexer.cc 与 db/version_set.cc 中并以 db/file_indexer_test.cc 的边界用例保证了各场景下的正确性是理解 RocksDB 点查询性能优化的一个绝佳入口。【免费下载链接】rocksdbA library that provides an embeddable, persistent key-value store for fast storage.项目地址: https://gitcode.com/gh_mirrors/ro/rocksdb创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 RocksDB SST 文件索引优化：借助 Fractional Cascading 思想加速点查询
RocksDB SST 文件索引优化借助 Fractional Cascading 思想加速点查询【免费下载链接】rocksdbA library that provides an embeddable, persistent key-value store for fast storage.项目地址: https://gitcode.com/gh_mirrors/ro/rocksdb导读本文围绕 RocksDB 中Get()点查询的完整查找路径展开数据依次经过 mutable memtable、immutable memtable 列表与各级 SST 文件最终在 LSM 树的深层级中定位目标 key。面对底层海量 SST 文件带来的二分查找开销RocksDB 借鉴 Fractional Cascading分数级联思想在文件元数据FileMetaData比较结果的基础上预构建层间索引将下层文件的搜索范围从整层收窄到与上层文件实际重叠的少数文件。读完本文你将理解这一优化背后的两个关键不变量、FileIndexer的数据结构与构建/查询流程以及它在源码中的落地位置与实测收益。一次 Get 的完整旅程从 memtable 到 SST 文件在 RocksDB 中一次Get()请求的目标 key 会按照由新到旧的顺序在以下结构中依次查找mutable memtable当前正在写入的内存表immutable memtable 列表已被冻结、等待 flush 到磁盘的只读内存表各级 SST 文件落盘后的排序字符串表Sorted String Table按 Level 0、Level 1、Level 2……逐层组织。其中 Level 0L0与其他层级的行为有本质区别L0 的文件是按照flush 的时间顺序排列的它们的 key 范围由每个文件元数据中的FileMetaData.smallest与FileMetaData.largest定义彼此高度重叠因此一次查找必须遍历 L0 的全部文件逐一判断目标 key 是否落在其范围内。这正是FilePicker在PrepareNextLevel()中对 L0 采用“start_index 0、逐个检查”策略的原因见 db/version_set.cc。Compaction 会周期性触发把上层文件挑选出来与下层文件合并将键值数据从 L0 逐步向下搬运。Compaction 过程对键值排序并切分成新的文件。从 Level 1 开始SST 文件按照 key 排序且同层文件之间的 key 范围互不重叠mutually exclusive——正是这个有序性让 L1 及以下层级的查找不再需要全层扫描。有序层级的二分查找O(N) 到 O(log(N)) 的跃迁对于 L1 及以下层级由于文件按 key 有序且范围互斥RocksDB 不再逐个遍历文件判断范围而是基于FileMetaData.largest执行二分查找定位一个可能包含目标 key 的候选文件这使复杂度从 O(N) 降为 O(log(N))。在源码层面这一步体现在VersionStorageInfo构建的LevelFilesBrief上PrepareNextLevel()中通过FindFileInRange()在受限范围内二分查找“largest ikey 的最早文件”例如 db/version_set.cc// On Level-n (n1), files are sorted. Binary search to find the // earliest file whose largest key ikey. Search left bound and // right bound are used to narrow the range. start_index FindFileInRange(*internal_comparator_, *curr_file_level_, ikey_, static_castuint32_t(search_left_bound_), static_castuint32_t(search_right_bound_) 1);然而log(N) 在底层依旧可能很大。假设层级间的 fan-out 比例为 10Level 3 就可能有 1000 个文件定位一个候选文件需要约 10 次比较。对于追求每秒钟数百万次 Get 的内存型工作负载而言这 10 次比较是一笔不可忽视的固定开销。核心观察LSM 树中文件位置的两个不变量针对上述开销这篇技术文章的核心观察在于LSM 树构建完成后SST 文件在其所属层级内的位置是固定的同时它相对于下一层文件的顺序也是固定的。这两个不变量非常重要因为它们意味着上层文件与下层文件的“相对位置关系”可以在一次 Compaction或 Version 构建完成后一次性计算出来并在后续无数次查询中反复复用。这正是 Fractional Cascading 一类优化的前提——把本来需要在每一层重复进行的比较预先折叠进层间的索引结构里。下面用一个两层的小例子说明收益来源。下图为 Level 1 与 Level 2 的 SST 文件及其 key 范围示意图中 Level 1 有 2 个文件Level 2 有 8 个文件。接下来以文档中的两个查找为例看比较结果如何被“级联”到下一层。例子 1查找 key 80对 Level 1 按FileMetaData.largest二分查找定位到 file 1。随后将 key 80 与 file 1 的smallest、largest比较发现80 小于FileMetaData.smallest100因此 file 1 不可能包含 key 80需要转向 Level 2。按朴素做法接下来要在 Level 2 的 8 个文件上重新做一次完整二分查找。但由于我们已经知道目标 key 80 100而 Level 2 中只有 file 1 到 file 3 的 key 才可能小于 100file 3 的 key 范围为 95–110其余文件的 smallest 均大于等于 150因此其余文件可以被安全排除。搜索空间从 8 个文件收窄到3 个文件。例子 2查找 key 230对 Level 1 二分查找定位到 file 2这同时意味着 key 230 大于 file 1 的largest200。将 key 230 与 file 2 的范围比较发现它小于 file 2 的smallest300。虽然 Level 1 上没找到 key但我们推导出了 hint目标 key 落在区间 [200, 300] 内。Level 2 上任何无法与 [200, 300] 相交的文件都可以安全排除。结果只需要检查 Level 2 的 file 5 和 file 6搜索范围从 8 个文件收窄到2 个文件。实现Compaction 时预构建层间指针受此思想启发RocksDB 在 Compaction更准确地说是每次构建新的Version时为上层文件预构建指向下层文件范围的指针。沿用文档例子Level 1 的 file 1 在左侧指向 Level 2 的 file 3、右侧指向 file 4file 2 指向 Level 2 的 file 6 与 file 7。查询时根据当前文件比较结果选择左/右指针即可确定下一层实际二分查找的边界。FileIndexer 的数据结构该优化在源码中的实现主体是 db/file_indexer.h 中的FileIndexer类。其头文件注释清晰地总结了复用比较结果的三种情形(1) key 小于文件的 smallest说明它也小于 largest可用基于 “smallest smallest” 预计算的索引提供右边界(2) key 位于 smallest 与 largest 之间可用 “smallest largest” 提供左边界、用 “largest smallest” 提供右边界(3) key 大于文件的 largest说明它也大于 smallest可用基于 “largest largest” 预计算的索引提供左边界。对应地每个上层文件在下一层都维护四个边界值即 db/file_indexer.h 中的IndexUnitstruct IndexUnit { // 下层中可能包含“大于 smallest 的 key”的最左文件 int32_t smallest_lb; // 下层中可能包含“大于 largest 的 key”的最左文件 int32_t largest_lb; // 下层中可能包含“小于 smallest 的 key”的最右文件 int32_t smallest_rb; // 下层中可能包含“小于 largest 的 key”的最右文件 int32_t largest_rb; };所有IndexUnit按层组织在autovectorIndexLevel next_level_index_中并由level_rb_记录每层文件的右边界。构建过程UpdateIndex索引的构建入口是FileIndexer::UpdateIndex()db/file_indexer.cc它针对 L1 到 Ln-1 的每一层用上层文件与下层文件各跑四遍线性扫描两次CalculateLB()left bound分别用“上层的 smallest/largest 与下层的 largest 比较”得到smallest_lb与largest_lb两次CalculateRB()right bound分别用“上层的 smallest/largest 与下层的 smallest 比较”得到smallest_rb与largest_rb。CalculateLB/CalculateRB采用双指针线性推进db/file_indexer.cc每步仅做一次比较器调用复杂度为 O(上层文件数 下层文件数)构建成本可控。内存则在VersionStorageInfo持有的Arena中统一分配。触发时机Version 构建时在版本管理层面VersionStorageInfo::PrepareForVersionAppend()在每次生成新 Version 时调用GenerateFileIndexer()见 db/version_set.cc进而触发file_indexer_.UpdateIndex(arena_, num_non_empty_levels_, files_)见 db/version_set.h。由于每次 Compaction / Flush 后文件集合都会变化索引也会随之整体重建而两次 Compaction 之间的大量查询则可以零成本复用这套预计算结果。查询路径FilePicker 与 GetNextLevelIndex查询时FilePickerdb/version_set.cc在GetNextFile()中逐层推进。对每个当前层文件它先用用户比较器算出cmp_smallest与cmp_largest两个比较结果然后调用 db/version_set.cc 中的file_indexer_-GetNextLevelIndex( curr_level_, curr_index_in_curr_level_, cmp_smallest, cmp_largest, search_left_bound_, search_right_bound_);GetNextLevelIndex()db/file_indexer.cc根据cmp_smallest/cmp_largest的符号分五种情况返回下一层的[left_bound, right_bound]搜索区间——这正是头文件注释中三种比较情形的直接编码。拿到收窄后的边界后PrepareNextLevel()中的FindFileInRange()只在[search_left_bound_, search_right_bound_ 1)区间内做二分而不是全层二分。若上层推导出的区间为空left_bound right_bound则直接跳过该层并重置为全范围搜索下一层db/version_set.cc避免无效比较。值得一提的还有边界情况当某一层文件数不超过 3 时FilePicker会跳过 key range 过滤与级联逻辑直接逐个查询db/version_set.cc因为此时过滤的开销可能高于直接查找——这说明该优化针对的是文件数量众多的深层级场景。正确性验证file_indexer_test.ccdb/file_indexer_test.cc 为FileIndexer提供了系统性的单元测试覆盖了所有典型几何关系Empty空版本0 层下的安全构建no_overlap_left/no_overlap_right上层文件整体位于下层文件左侧/右侧验证极端排除场景下边界正确回退到[0, -1]或全范围empty_L2中间层为空时索引尺寸为 0查询正确退化为全范围搜索mixed多层文件交错重叠的混合场景逐一断言GetNextLevelIndex()在不同cmp_smallest/cmp_largest组合下返回的左右边界例如 Level 1 的 file 1 在(cmp_smallest1, cmp_largest1)时返回[1, 4]db/file_indexer_test.cc。测试中的IntComparator与IntKey()构造了精确可控的整数 key 范围直观验证了“比较结果级联到下一层搜索边界”这一核心语义。实测收益作者在博客中报告在与 RocksDB In-Memory Workload Performance Benchmarks 类似配置下的基准测试表明该优化将点查询 QPS 提升了约5%。考虑到深层级每次查找可节省约 8–10 次文件级比较对应文中的 fan-out 10、L3 千文件场景这个数字在内存型高吞吐工作负载下是相当可观的——尤其是当这些比较发生在每次 Get 的热路径上时。总结RocksDB 对 SST 文件查找的这套优化可以概括为三步① 利用 LSM 树文件位置固定的两个不变量② 在 Version 构建时用线性扫描预计算上层文件对下层文件的左右边界③ 查询时用当前文件的两三次比较结果直接确定下一层的二分范围。从复杂度上看原本在 Level L 上需要检查 O(N^L) 量级的文件现在只需检查约 N即max_bytes_for_level_multiplier对应的重叠文件数个文件。这项设计与FileIndexer类、FilePicker查询器一起完整落地于 db/file_indexer.h、db/file_indexer.cc 与 db/version_set.cc 中并以 db/file_indexer_test.cc 的边界用例保证了各场景下的正确性是理解 RocksDB 点查询性能优化的一个绝佳入口。【免费下载链接】rocksdbA library that provides an embeddable, persistent key-value store for fast storage.项目地址: https://gitcode.com/gh_mirrors/ro/rocksdb创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考