当前位置：首页 > news >正文

深入解析RocksDB的MVCC和LSM Tree level

news 2025/7/30 13:43:40

`Version`

Version 是 RocksDB 多版本并发控制（MVCC）机制的核心，理解它对于理解 RocksDB 的读写流程、压缩机制以及数据一致性至关重要。

在 RocksDB 中，一个 Version 对象可以被理解为在某一特定时间点，一个列族（Column Family）中所有数据文件的信息的不可变快照。它精确地描述了 LSM-Tree 的每一层有哪些 SST 文件，以及这些文件的元数据（如文件大小、key 的范围等）。

不可变性 (Immutability): Version 对象一旦创建，其内容就不会再被修改。任何对 LSM-Tree 结构的改变（如 MemTable flush 或 Compaction）都会产生一个新的 VersionEdit，然后通过将这个 VersionEdit 应用于当前的 Version 来创建一个新的 Version 对象。
一致性视图 (Consistent View): 当一个读操作（如 Get 或 NewIterator）开始时，它会获取并“持有”当前的 Version。只要这个读操作没有结束，它就会一直在这个 Version 的快照上进行，不受后续发生的 Compaction 或 Flush 的影响。这保证了读操作的一致性。

`Version` 与相关类的关系

Version 并非孤立存在，它与 VersionSet 和 VersionEdit 紧密协作，共同管理着数据库的元数据状态。

version_set.h

// ... existing code ...
// The representation of a DBImpl consists of a set of Versions.  The
// newest version is called "current".  Older versions may be kept
// around to provide a consistent view to live iterators.
//
// Each Version keeps track of a set of table files per level, as well as a
// set of blob files. The entire set of versions is maintained in a
// VersionSet.
// ... existing code ...
class VersionSet;
// ... existing code ...
// A column family's version consists of the table and blob files owned by
// the column family at a certain point in time.
class Version {
// ... existing code ...
};// ... existing code ...
// The state of a DB at any given time is referred to as a Version.
// Any modification to the Version is considered a Version Edit. A Version is
// constructed by joining a sequence of Version Edits. Version Edits are written
// to the MANIFEST file.
class VersionEdit {
// ... existing code ...
};// VersionSet is the collection of versions of all the column families of the
// database. Each database owns one VersionSet. A VersionSet has access to all
// column families via ColumnFamilySet, i.e. set of the column families.
class VersionSet {
// ... existing code ...
};

VersionSet: 这是一个全局管理者。
- 它管理着一个数据库实例中所有列族的 Version。
- 每个列族在 VersionSet 中都有一个 Version 的双向链表。链表头是 "current" 版本，即最新版本。旧版本为了服务于尚未结束的读操作而被保留在链表中。
- 它负责将 VersionEdit 应用到当前 Version 以生成新 Version，并将变更记录到 MANIFEST 文件中（通过 LogAndApply 方法）。
VersionEdit: 这是一个增量描述对象。
- 它不代表一个完整的状态，而是记录了从一个 Version 到下一个 Version 的变化。例如，"在 Level-1 新增了文件 A，删除了文件 B 和 C" 或者 "更新了下一次 Compaction 的指针位置"。
- Compaction 和 MemTable Flush 的结果就是生成一个 VersionEdit。

三者协作流程：

当 Compaction 或 Flush 完成后，会产生一个 VersionEdit 来描述文件变动。
VersionSet 调用 VersionBuilder，将这个 VersionEdit 应用到当前 Version 上。
VersionBuilder 根据基础 Version 和 VersionEdit 的内容，创建一个全新的 Version 对象。
VersionSet 将这个新 Version 安装为 "current" 版本，并更新 MANIFEST 文件。旧的 "current" 版本就成了历史版本，等待其引用计数归零后被回收。

关键数据成员

Version 内部的成员变量精确地定义了一个快照所包含的所有信息。

// ... existing code ...
class Version {
// ... existing code ...private:
// ... existing code ...ColumnFamilyData* cfd_;  // ColumnFamilyData to which this Version belongs
// ... existing code ...VersionStorageInfo storage_info_;VersionSet* vset_;  // VersionSet to which this Version belongsVersion* next_;     // Next version in linked listVersion* prev_;     // Previous version in linked listint refs_;          // Number of live refs to this version
// ... existing code ...// A version number that uniquely represents this version. This is// used for debugging and logging purposes only.uint64_t version_number_;
// ... existing code ...
};

storage_info_ (VersionStorageInfo): 这是 Version 的核心数据载体，它包含了 LSM-Tree 的完整结构信息，例如：
- files_ (std::vector<FileMetaData*>*): 一个指针数组，files_[i] 指向一个 vector，其中包含了 Level i 的所有 FileMetaData（SST 文件元数据）指针。这些文件在各自的 Level 内按 key 的范围排序。
- num_levels_: LSM-Tree 的总层数。
- compaction_style_: 当前列族的压缩策略（Leveled, Universal 等）。
- blob_files_: 如果使用了 BlobDB，这里存储了所有关联的 blob 文件元数据。
cfd_ (ColumnFamilyData*): 指向该 Version 所属的列族对象。
vset_ (VersionSet*): 指回管理它的 VersionSet。
next_ / prev_: 用于构建 VersionSet 中的双向链表。next_ 指向更旧的版本，prev_ 指向更新的版本。
refs_: 引用计数。这是 Version 生命周期管理的核心。
- 当一个读操作（Get 或 Iterator）开始时，会调用 Ref() 使 refs_ 加一。
- 当操作结束时，调用 Unref() 使 refs_ 减一。
- 只有当 refs_ 降为 0 时，这个 Version 对象才会被析构，其所引用的、且不再被任何新 Version 引用的 SST 文件才能被安全删除。
version_number_: 一个唯一的数字ID，主要用于调试和日志记录，方便追踪 Version 的演进。

`Version` 的关键成员函数

Version 的公有接口主要服务于读操作和元数据查询。

// ... existing code ...
class Version {public:
// ... existing code ...void AddIterators(const ReadOptions& read_options,const FileOptions& soptions,MergeIteratorBuilder* merger_iter_builder,bool allow_unprepared_value);// ... existing code ...void Get(const ReadOptions&, const LookupKey& key, PinnableSlice* value,PinnableWideColumns* columns, std::string* timestamp, Status* status,MergeContext* merge_context,SequenceNumber* max_covering_tombstone_seq,PinnedIteratorsManager* pinned_iters_mgr,bool* value_found = nullptr, bool* key_exists = nullptr,SequenceNumber* seq = nullptr, ReadCallback* callback = nullptr,bool* is_blob = nullptr, bool do_merge = true);
// ... existing code ...void PrepareAppend(const ReadOptions& read_options, bool update_stats);// Reference count management (so Versions do not disappear out from// under live iterators)void Ref();// Decrease reference count. Delete the object if no reference left// and return true. Otherwise, return false.bool Unref();// ... existing code ...std::string DebugString(bool hex = false, bool print_stats = false) const;uint64_t GetVersionNumber() const { return version_number_; }
// ... existing code ...
};

Get(...): 这是执行点查（Point Lookup）的核心函数。它会按照 LSM-Tree 的查找顺序，在此 Version 所包含的文件中查找指定的 key：
1. 从 Level 0 开始查找。由于 L0 文件之间 key 范围可能重叠，需要依次查找所有 L0 文件。
2. 如果在 L0 没找到，则去 Level 1 查找。由于 L1 及更高层级的文件 key 范围不重叠，可以通过二分查找快速定位到可能包含该 key 的唯一文件。
3. 逐层向下查找，直到找到 key 或者查完所有层级。
AddIterators(...): 这是范围查询（Range Scan）和迭代器的基础。它会为当前 Version 中所有层级的所有 SST 文件创建对应的迭代器，然后 MergeIteratorBuilder 会将这些迭代器合并成一个 MergingIterator，从而提供一个统一的、有序的数据库视图。
Ref() 和 Unref(): 控制引用计数，管理 Version 的生命周期，是保证并发读写安全的关键。
PrepareAppend(...): 在一个新创建的 Version 被正式安装到 VersionSet 之前调用。它会做一些准备工作，比如根据文件元数据更新 Version 内的累计统计信息（UpdateAccumulatedStats），或者生成用于快速文件定位的索引（GenerateFileIndexer），以优化后续的读性能和压缩决策。
DebugString(...): 生成一个可读的字符串，详细描述该 Version 中每一层的文件列表和状态，是调试 RocksDB 问题的重要工具。

总结

Version 是 RocksDB 设计哲学中一个优雅且高效的实现。它通过“不可变快照 + 引用计数”的方式，实现了以下目标：

高并发读写：读操作在旧的 Version 上进行，完全不阻塞新的写入和 Compaction。
数据一致性：每个读操作都工作在一个固定的数据快照上，保证了可重复读。
高效的垃圾回收：通过引用计数，可以安全地识别出哪些 Version 已不再被使用，从而可以安全地删除其对应的、不再需要的旧 SST 文件。

理解了 Version，就等于掌握了 RocksDB 如何组织数据文件、如何响应读请求以及如何维护数据一致性的核心逻辑。

`Version::Get`

这个函数是 RocksDB 执行点查询（Point Lookup）的核心，理解它的工作流程对于理解 RocksDB 的读路径至关重要。

Version::Get 的主要职责是：在一个固定的数据库版本（Version）快照中，查找一个特定 key 对应的值。

我们首先来分析这个函数的参数，每个参数都有其明确的用途：

void Get(const ReadOptions&, const LookupKey& key, PinnableSlice* value,PinnableWideColumns* columns, std::string* timestamp, Status* status,MergeContext* merge_context,SequenceNumber* max_covering_tombstone_seq,PinnedIteratorsManager* pinned_iters_mgr,bool* value_found = nullptr, bool* key_exists = nullptr,SequenceNumber* seq = nullptr, ReadCallback* callback = nullptr,bool* is_blob = nullptr, bool do_merge = true);

const ReadOptions& read_options: 读操作的配置项。例如，它可以指定要读取的快照（snapshot）、是否校验 checksum（verify_checksums）、读取哪个层级的数据（read_tier）等。
const LookupKey& k: 要查找的键。LookupKey 是一个内部结构，它将用户提供的 user_key 与查找所需的序列号（Sequence Number）和值类型（Value Type）打包在一起，构成了在 SST 文件中查找的内部键（Internal Key）。
PinnableSlice* value: 输出参数，用于存放找到的值。PinnableSlice 是一个特殊的 Slice，它可以“钉住”（pin）其指向的内存块（通常在 Block Cache 中），从而避免不必要的数据拷贝，提升性能。
PinnableWideColumns* columns: 输出参数，用于支持宽列（Wide Columns）特性，当一个键对应多个值时使用。
std::string* timestamp: 输出参数，如果数据库开启了时间戳（Timestamp）功能，这里会返回找到的键值对的时间戳。
Status* status: 输入/输出参数，用于传递和返回操作的状态。如果输入时是 MergeInProgress，表示这是一个合并操作的延续。最终会返回 OK(), NotFound(), Corruption() 等状态。
MergeContext* merge_context: 用于处理 Merge 操作。当遇到一个 Merge 类型的记录时，其操作数（operand）会被收集到 merge_context 中。
SequenceNumber* max_covering_tombstone_seq: 一个用于范围删除（Range Deletion）优化的重要参数。如果在查找过程中遇到了一个可以覆盖当前 key 的范围删除标记，这个值会被更新。后续在更老的文件中查找时，如果文件的序列号小于此值，就可以直接跳过，因为里面的数据肯定被覆盖了。
PinnedIteratorsManager* pinned_iters_mgr: 用于管理内存块的固定（pinning），尤其是在 Merge 操作中，需要确保所有合并操作数所在的内存块在合并完成前都保持有效。
bool* value_found, bool* key_exists, SequenceNumber* seq: 几个可选的输出参数，提供更详细的查找结果。key_exists 即使在键被删除时（返回 NotFound）也会是 true。
bool* is_blob: 输出参数，如果找到的值是一个 Blob 索引，这个标志位会被设为 true。
bool do_merge: 控制是否执行合并。如果为 false，函数只会收集 Merge 操作数到 merge_context 中，而不会真正执行合并计算。

核心逻辑分步解析

Version::Get 的执行过程可以看作是一场在 LSM-Tree 中的精确寻宝之旅。

第 1 步：初始化与准备

// ... existing code ...bool is_blob_index = false;bool* const is_blob_to_use = is_blob ? is_blob : &is_blob_index;BlobFetcher blob_fetcher(this, read_options);assert(pinned_iters_mgr);GetContext get_context(user_comparator(), merge_operator_, info_log_, db_statistics_,status->ok() ? GetContext::kNotFound : GetContext::kMerge, user_key,do_merge ? value : nullptr, do_merge ? columns : nullptr,do_merge ? timestamp : nullptr, value_found, merge_context, do_merge,max_covering_tombstone_seq, clock_, seq,merge_operator_ ? pinned_iters_mgr : nullptr, callback, is_blob_to_use,tracing_get_id, &blob_fetcher);// Pin blocks that we read to hold merge operandsif (merge_operator_) {pinned_iters_mgr->StartPinning();}
// ... existing code ...

创建 GetContext: 这是整个 Get 操作的状态机和上下文管理器。它被传递到下层的 TableCache 和 TableReader。当在 SST 文件中找到数据时，TableReader 会更新 GetContext 的状态（例如，从 kNotFound 变为 kFound 或 kMerge）并保存结果。
启动 Pinning: 如果数据库配置了 merge_operator，就调用 pinned_iters_mgr->StartPinning()，准备好在查找过程中固定住包含合并操作数的内存块。

第 2 步：文件选择 (`FilePicker`)

// ... existing code ...FilePicker fp(user_key, ikey, &storage_info_.level_files_brief_,storage_info_.num_non_empty_levels_,&storage_info_.file_indexer_, user_comparator(),internal_comparator());FdWithKeyRange* f = fp.GetNextFile();
// ... existing code ...

FilePicker 是一个智能文件选择器。它的任务是按照正确的查找顺序，高效地找出所有可能包含目标 key 的 SST 文件。
查找顺序: 从 L0 层开始，然后是 L1, L2, ...
查找逻辑:
- 在 L0，由于文件间的 key 范围可能重叠，FilePicker 会返回所有 key 范围覆盖了目标 key 的文件。
- 在 L1 及以上层级，文件间的 key 范围互不重叠。FilePicker 会利用 storage_info_.file_indexer_（一个预先构建好的文件索引）进行二分查找，快速定位到唯一可能包含目标 key 的文件。
fp.GetNextFile() 会依次返回下一个需要被搜索的文件。

第 3 步：遍历文件并查找 (`while` 循环)

这是函数的主体部分，循环遍历 FilePicker 找到的每一个候选文件。

// ... existing code ...while (f != nullptr) {if (*max_covering_tombstone_seq > 0) {// The remaining files we look at will only contain covered keys, so we// stop here.break;}
// ... existing code ...*status = table_cache_->Get(read_options, *internal_comparator(), *f->file_metadata, ikey,&get_context, mutable_cf_options_,
// ... existing code ...);
// ... existing code ...switch (get_context.State()) {case GetContext::kNotFound:// Keep searching in other filesbreak;case GetContext::kMerge:// TODO: update per-level perfcontext user_key_return_count for kMergebreak;case GetContext::kFound:
// ... existing code ...return;case GetContext::kDeleted:// Use empty error message for speed*status = Status::NotFound();return;
// ... existing code ...}f = fp.GetNextFile();}
// ... existing code ...

范围删除优化: 循环开始时检查 max_covering_tombstone_seq，如果发现当前 key 已经被一个范围删除覆盖，就提前终止循环。
调用 table_cache_->Get(): 这是实际在单个 SST 文件中进行查找的地方。TableCache 负责管理 SST 文件的打开和缓存。它会找到或创建一个 TableReader 对象，然后调用其 Get 方法。TableReader::Get 的内部流程大致是：
1. 检查文件的 Bloom Filter。如果 Bloom Filter 判断 key 肯定不存在，则直接返回，避免了昂贵的 I/O。
2. 如果 Bloom Filter 通过，则查找文件的 Index Block，定位到可能包含 key 的 Data Block。
3. 从 Block Cache 或磁盘读取该 Data Block。
4. 在 Data Block 内部进行二分查找，寻找 ikey。
5. 根据找到的条目类型（Put, Delete, Merge 等），更新传入的 get_context 的状态。
处理查找结果 (switch 语句):
- kNotFound: 在当前文件中没找到。循环继续，从 FilePicker 获取下一个候选文件。
- kFound: 找到了！ 记录统计信息，然后直接 return。如果找到的是 Blob 索引 (is_blob_index 为 true)，则会进一步调用 GetBlob 从 Blob 文件中读取真实数据，然后返回。
- kDeleted: 找到了一个删除标记（Tombstone）。这意味着这个 key 在这个版本中被视为已删除。函数立即设置状态为 Status::NotFound() 并返回。
- kMerge: 找到了一个合并操作数。GetContext 会将其保存起来。循环继续，因为需要去更老的文件中寻找基础值（base value）或其他合并操作数。
- kCorrupt 等：遇到错误，直接返回。

第 4 步：收尾工作 (处理 Merge 和最终的 NotFound)

处理 Merge: 如果 while 循环正常结束（即搜遍了所有相关文件），而 get_context 的状态是 kMerge，说明我们找到了一个或多个合并操作数，但没有找到基础值。此时，需要调用 MergeHelper::TimedFullMerge 来对所有收集到的操作数进行合并，计算出最终结果。
最终的 NotFound: 如果循环结束，状态依然是 kNotFound，说明在整个 Version 中都没有找到这个 key。函数设置状态为 Status::NotFound() 并返回。

总结

Version::Get 是一个设计精良、高度优化的函数，它体现了 LSM-Tree 读操作的精髓：

分层查找: 严格按照 L0 -> L1 -> ... 的顺序，保证了能找到最新版本的数据。
高效过滤: 通过 Bloom Filter 快速排除不含目标 key 的文件，大大减少了 I/O。
索引加速: 在 L1+ 层级利用文件索引快速定位，避免了无谓的文件扫描。
状态机模式: 使用 GetContext 对象清晰地管理查找过程中的各种状态和结果，解耦了各层级的逻辑。
零拷贝读取: 通过 PinnableSlice 尽可能地避免了从 Block Cache 到用户缓冲区的内存拷贝。
集成多种特性: 无缝地处理了删除、合并、Blob、时间戳等复杂逻辑。

`FilePicker`

FilePicker 的核心职责是在执行 Version::Get 点查询时，智能地、按顺序地挑选出可能包含目标 key 的 SST 文件。它是 Get 操作能够高效执行的关键组件之一，通过一系列优化策略避免了对整个数据库文件的无效扫描。

FilePicker 是一个生命周期很短的栈上对象，仅在单次 Version::Get 调用期间存在。

// ... (anonymous namespace)
// Class to help choose the next file to search for the particular key.
// Searches and returns files level by level.
// We can search level-by-level since entries never hop across
// levels. Therefore we are guaranteed that if we find data
// in a smaller level, later levels are irrelevant (unless we
// are MergeInProgress).
class FilePicker {public:FilePicker(const Slice& user_key, const Slice& ikey,autovector<LevelFilesBrief>* file_levels, unsigned int num_levels,FileIndexer* file_indexer, const Comparator* user_comparator,const InternalKeyComparator* internal_comparator): num_levels_(num_levels),curr_level_(static_cast<unsigned int>(-1)),// ... (member initialization)internal_comparator_(internal_comparator) {// Setup member variables to search first level.search_ended_ = !PrepareNextLevel();if (!search_ended_) {// Prefetch Level 0 table data to avoid cache miss if possible.for (unsigned int i = 0; i < (*level_files_brief_)[0].num_files; ++i) {auto* r = (*level_files_brief_)[0].files[i].fd.table_reader;if (r) {r->Prepare(ikey);}}}}
// ...
};

在构造函数中，它接收了执行查找所需的所有上下文信息：

user_key 和 ikey: 用户键和内部键。
file_levels: VersionStorageInfo 中存储的各层级文件元数据摘要 (LevelFilesBrief)。
num_levels: LSM-Tree 的总层数。
file_indexer: 一个预先构建好的索引，用于在 L1+ 层级中进行快速文件定位（“分数阶级联”优化）。
user_comparator 和 internal_comparator: 键比较器。

构造函数的核心动作是调用 PrepareNextLevel() 来准备搜索 L0，并对 L0 的文件执行 Prepare() 操作，这可以触发 TableReader 的预取逻辑，尝试将可能需要的数据提前加载到缓存中。

`GetNextFile()`

这是 FilePicker 对外提供的主要接口。每次调用，它会返回下一个需要被检查的文件的元数据 (FdWithKeyRange*)。如果所有可能的文件都已返回，则返回 nullptr。

其内部实现是一个双重循环：外层循环遍历 LSM 的层级（Level），内层循环遍历当前层级中的文件。

// ... existing code ...FdWithKeyRange* GetNextFile() {while (!search_ended_) {  // Loops over different levels.while (curr_index_in_curr_level_ < curr_file_level_->num_files) {// Loops over all files in current level.FdWithKeyRange* f = &curr_file_level_->files[curr_index_in_curr_level_];
// ... existing code ...if (num_levels_ > 1 || curr_file_level_->num_files > 3) {// Check if key is within a file's range.
// ... existing code ...int cmp_smallest = user_comparator_->CompareWithoutTimestamp(user_key_, ExtractUserKey(f->smallest_key));if (cmp_smallest >= 0) {cmp_largest = user_comparator_->CompareWithoutTimestamp(user_key_, ExtractUserKey(f->largest_key));}// Setup file search bound for the next level based on the// comparison resultsif (curr_level_ > 0) {file_indexer_->GetNextLevelIndex(curr_level_, curr_index_in_curr_level_, cmp_smallest,cmp_largest, &search_left_bound_, &search_right_bound_);}// Key falls out of current file's rangeif (cmp_smallest < 0 || cmp_largest > 0) {if (curr_level_ == 0) {++curr_index_in_curr_level_;continue;} else {// Search next level.break;}}}returned_file_level_ = curr_level_;if (curr_level_ > 0 && cmp_largest < 0) {// No more files to search in this level.search_ended_ = !PrepareNextLevel();} else {++curr_index_in_curr_level_;}return f;}// Start searching next level.search_ended_ = !PrepareNextLevel();}// Search ended.return nullptr;}
// ... existing code ...

关键逻辑点：

范围过滤: 在检查一个文件之前，会先判断 user_key 是否落在该文件的 [smallest_key, largest_key] 范围内。
- cmp_smallest = user_comparator_->CompareWithoutTimestamp(user_key_, ExtractUserKey(f->smallest_key));
- cmp_largest = user_comparator_->CompareWithoutTimestamp(user_key_, ExtractUserKey(f->largest_key));
分层处理:
- 对于 L0: 文件间的 key 范围可能重叠。如果 user_key 不在当前文件范围内 (cmp_smallest < 0 || cmp_largest > 0)，它只会 continue 内层循环，继续检查 L0 的下一个文件。
- 对于 L1+: 文件间的 key 范围不重叠且有序。如果 user_key 不在当前文件范围内（这个文件是二分查找得到的候选文件），意味着它也不可能在当前层级的任何后续文件中。因此，它会 break 内层循环，直接跳到下一层级进行搜索。
分数阶级联 (Fractional Cascading) 优化:
- file_indexer_->GetNextLevelIndex(...) 是这个优化的体现。当在 L1+ 的某个文件 f 中进行范围比较后，无论 user_key 是否在 f 的范围内，比较结果 (cmp_smallest, cmp_largest) 都会被用来缩小下一层级的搜索范围 (search_left_bound_, search_right_bound_)。
- 这避免了在下一层级中进行完整的二分查找，而是只在一个更小的、预先确定的范围内查找，显著提升了跨层级搜索的效率。
返回文件: 如果一个文件通过了范围检查，它就被认为是候选文件，GetNextFile 会返回其指针，并递增文件索引 curr_index_in_curr_level_，为下一次调用做准备。

`PrepareNextLevel()`

当一个层级的所有候选文件都被检查完毕后，GetNextFile 会调用 PrepareNextLevel 来切换到下一层级。

// ... existing code ...// Setup local variables to search next level.// Returns false if there are no more levels to search.bool PrepareNextLevel() {curr_level_++;while (curr_level_ < num_levels_) {curr_file_level_ = &(*level_files_brief_)[curr_level_];if (curr_file_level_->num_files == 0) {// ... (handle empty level)curr_level_++;continue;}int32_t start_index;if (curr_level_ == 0) {// On Level-0, we read through all files to check for overlap.start_index = 0;} else {// On Level-n (n>=1), 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.if (search_left_bound_ <= search_right_bound_) {// ... (adjust search_right_bound_)start_index =FindFileInRange(*internal_comparator_, *curr_file_level_, ikey_,static_cast<uint32_t>(search_left_bound_),static_cast<uint32_t>(search_right_bound_) + 1);if (start_index == search_right_bound_ + 1) {// ... (key not in this level, skip to next)continue;}} else {// ... (search bounds invalid, skip to next level)continue;}}start_index_in_curr_level_ = start_index;curr_index_in_curr_level_ = start_index;return true;}// curr_level_ = num_levels_. So, no more levels to search.return false;}
// ... existing code ...

关键逻辑点：

层级切换: curr_level_++。
确定起始搜索点 (start_index):
- 对于 L0: 文件无序，必须从第一个文件开始线性扫描。start_index = 0;
- 对于 L1+: 文件有序。利用上一层级传递下来的搜索范围 [search_left_bound_, search_right_bound_]，调用 FindFileInRange (内部是 std::lower_bound 二分查找) 来快速定位第一个可能包含 ikey 的文件。
设置状态: 将 curr_index_in_curr_level_ 设置为计算出的 start_index，为 GetNextFile 的内层循环做好准备。
空层级/无效范围处理: 如果当前层级为空，或者上一层传递的搜索范围无效 (search_left_bound > search_right_bound)，则直接跳到下一层。

总结

FilePicker 的工作流程可以概括为：

从 L0 开始，逐层向下 (PrepareNextLevel)。
在 L0，线性扫描所有文件，返回所有 key 范围覆盖了目标 user_key 的文件。
在 L1+，利用上一层级传递的搜索范围和二分查找，快速定位到第一个可能包含 ikey 的文件 (PrepareNextLevel)。
从该起始点开始，逐个检查文件 (GetNextFile)。
对于每个文件，进行精确的 key 范围比较。
比较结果被用来更新下一层级的搜索范围（分数阶级联优化）。
如果 key 不在当前文件范围，则立即跳到下一层级（因为 L1+ 文件有序）。
如果 key 在范围内，则返回该文件，并准备检查同一层级的下一个文件。
当所有层级都检查完毕，返回 nullptr，表示搜索结束。

通过这种结合了线性扫描、二分查找和分数阶级联的混合策略，FilePicker 实现了在多层级、部分有序的 LSM-Tree 结构中进行高效的文件定位，是 RocksDB 点查询性能的基石。

`FileIndexer`

FileIndexer 的核心目标，正如其头文件注释所说，是利用已有的键比较结果，为下一层的二分查找极大地收窄搜索范围。

数据结构：`IndexUnit` 和 `IndexLevel`

FileIndexer 的核心是 IndexUnit 结构体。对于 L(i) 层的每一个文件，都会有一个对应的 IndexUnit。

file_indexer.h

// ... existing code ...struct IndexUnit {IndexUnit(): smallest_lb(0), largest_lb(0), smallest_rb(-1), largest_rb(-1) {}
// ... existing code ...// 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)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)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)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)int32_t largest_rb;};// Data structure to store IndexUnits in a whole levelstruct IndexLevel {
// ... existing code ...IndexUnit* index_units;
// ... existing code ...};autovector<IndexLevel> next_level_index_;
// ... existing code ...

IndexUnit: 这个结构体包含四个关键的整数索引：smallest_lb, largest_lb, smallest_rb, largest_rb。
- lb 代表 Left Bound（左边界）。
- rb 代表 Right Bound（右边界）。
- smallest_lb 的含义是：如果一个 key 大于当前文件（上层文件）的 smallest_key，那么在下一层，它最早可能出现在哪个文件里？这个 smallest_lb 就存储了那个下层文件的索引。
- 其他三个字段以此类推，分别对应不同的比较情况，共同为下一层的搜索框定了一个 [左边界, 右边界] 的范围。
IndexLevel: 存储了一整层的所有 IndexUnit。
next_level_index_: 一个 autovector，next_level_index_[i] 存储了 L(i) 层到 L(i+1) 层的完整索引信息。

这个数据结构本身就证明了其预计算的本质。这些 lb 和 rb 值不是在查询时计算的，而是预先存储好的。

索引构建：`UpdateIndex`

FileIndexer::UpdateIndex 是构建索引的入口。它在 Version 构建的最后阶段被调用。

// ... existing code ...
void FileIndexer::UpdateIndex(Arena* arena, const size_t num_levels,std::vector<FileMetaData*>* const files) {
// ... existing code ...// L1 - Ln-1for (size_t level = 1; level < num_levels_ - 1; ++level) {const auto& upper_files = files[level];
// ... existing code ...const auto& lower_files = files[level + 1];
// ... existing code ...IndexLevel& index_level = next_level_index_[level];
// ... existing code ...index_level.index_units = new (mem) IndexUnit[upper_size];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(
// ... existing code ...[](IndexUnit* index, int32_t f_idx) { index->largest_lb = f_idx; });CalculateRB(
// ... existing code ...[](IndexUnit* index, int32_t f_idx) { index->smallest_rb = f_idx; });CalculateRB(
// ... existing code ...[](IndexUnit* index, int32_t f_idx) { index->largest_rb = f_idx; });}
// ... existing code ...
}

它遍历 L1 到倒数第二层。
对于每一层 level，它会调用四次 CalculateLB 或 CalculateRB，来填充 index_units 数组中每个 IndexUnit 的四个字段。

我们来看 CalculateLB 的实现：

// ... existing code ...
void FileIndexer::CalculateLB(const std::vector<FileMetaData*>& upper_files,const std::vector<FileMetaData*>& lower_files, 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) {int cmp = cmp_op(upper_files[upper_idx], lower_files[lower_idx]);if (cmp > 0) {// Lower level's file (largest) is smaller, a key won't hit in that// file. Move to next lower file++lower_idx;} else {// Lower level's file becomes larger, update the index, and// move to the next upper fileset_index(&index[upper_idx], lower_idx);++upper_idx;}}
// ... existing code ...
}

这是一个非常高效的双指针算法（类似归并排序的合并步骤）。它同时遍历上层文件列表和下层文件列表，通过一次线性扫描（O(N+M)），就计算出了所有上层文件在下层对应的左边界。CalculateRB 也是类似的逻辑。

这证明了索引的计算成本并不高，它不是嵌套循环，而是一次性的线性扫描。这个成本在 Version 构建时支付，然后被后续无数次 Get 操作共享。

索引使用：`GetNextLevelIndex`

这是“魔法”发生的地方。当 FilePicker 在 L(i) 层检查完一个文件后，它会调用此函数来获取 L(i+1) 层的搜索范围。

// ... existing code ...
void FileIndexer::GetNextLevelIndex(const size_t level, const size_t file_index,const int cmp_smallest,const int cmp_largest, int32_t* left_bound,int32_t* right_bound) const {
// ... existing code ...const IndexUnit* index_units = next_level_index_[level].index_units;const auto& index = index_units[file_index];if (cmp_smallest < 0) {*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_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 { // cmp_largest > 0*left_bound = index.largest_lb;*right_bound = level_rb_[level + 1];}
// ... existing code ...
}

O(1) 复杂度：这个函数的核心操作是 const auto& index = index_units[file_index];，这是一个数组索引操作，其时间复杂度是 O(1)。
利用比较结果：函数根据传入的 cmp_smallest 和 cmp_largest（即 user_key 和当前文件边界的比较结果）进入不同的 if-else 分支。
直接赋值：在每个分支中，它直接从预先计算好的 index（也就是 IndexUnit）中取出对应的 lb 和 rb 值，赋给输出参数 left_bound 和 right_bound。

这个函数完美地证明了：它利用预计算的索引，在 O(1) 时间内，根据上一次的比较结果，为下一次的二分查找提供了极度缩小的范围。 这就是分数阶级联优化的精髓所在。

结论

通过对 FileIndexer 的数据结构、构建过程和使用方式的分析，我们可以清晰地看到：

RocksDB 通过 IndexUnit 结构预先存储了层与层之间的文件重叠信息。
这个索引的构建过程 UpdateIndex 是高效的，采用线性扫描的双指针算法。
在查询时，GetNextLevelIndex 函数通过 O(1) 的数组访问，直接获取下一层的搜索边界，从而避免了在下一层进行全局的二分查找。

这套机制有效地将多层查找的复杂度从多个 log(N) 之和，优化为一次 log(N) 加上多次在极小范围内的查找，极大地提升了点查询的性能。

`VersionSet`

在 RocksDB 中，Version 代表了数据库在某个时间点的完整快照，包含了 LSM-Tree 所有层级的文件元数据。然而，数据库的状态是不断变化的（写入、删除、Compaction），会产生新的 Version。

VersionSet 正是管理所有这些 Version 的核心中枢。可以把它想象成数据库的“元数据大脑”，它负责：

维护版本链：管理当前（current）的 Version 以及所有正在被旧的读操作或迭代器使用的“历史” Version，形成一个双向链表。
持久化元数据：将数据库结构的变更（如 Compaction、Flush）记录到 MANIFEST 文件中，并在数据库启动时从 MANIFEST 文件恢复状态。
协调状态变更：提供 LogAndApply 方法，原子性地应用变更（VersionEdit）、持久化并切换到新的 Version。
全局资源管理：作为文件编号（File Number）、序列号（Sequence Number）等全局唯一资源的分配中心。

下面我们按照 VersionSet 的职责，对其功能进行分块解析。

构造、析构与恢复 (Lifecycle & Recovery)

这是 VersionSet 生命周期的起点和终点，主要负责从持久化存储中加载数据库状态。

VersionSet(...) (构造函数):
- 初始化 VersionSet 对象，接收数据库名、配置项、缓存等全局对象。
- 此时它只是一个空壳，真正的数据库状态需要通过 Recover 来加载。
~VersionSet() (析构函数):
- 清理资源，如关闭打开的 MANIFEST 日志写入器 (descriptor_log_)。
Status Recover(...):
- 核心功能：这是数据库启动时的关键步骤。它负责读取 MANIFEST 文件，重放（replay）其中记录的所有 VersionEdit，从而在内存中重建出数据库关闭前的最后一个 Version 状态。
- 流程：
  1. 找到 CURRENT 文件，它指向最新的 MANIFEST 文件。
  2. 创建一个 VersionEditHandler (内部实现)，逐条读取 MANIFEST 中的 VersionEdit 记录。
  3. 对每一条 VersionEdit，调用 VersionBuilder 将其应用到对应的列族（Column Family）上，逐步构建出每个列族的 LSM-Tree 结构。
  4. 恢复 next_file_number_, last_sequence_ 等全局元数据。
  5. 将最终构建好的 Version 设置为 current 版本。
Status TryRecover(...) / TryRecoverFromOneManifest(...):
- 这是 Recover 的更健壮版本，用于 best_efforts_recovery 模式。如果最新的 MANIFEST 损坏，它会尝试从旧的 MANIFEST 文件中恢复，尽力恢复到最近一个一致的状态点。

状态变更的核心：`LogAndApply`

这是 VersionSet 最核心、最繁忙的函数。数据库的所有结构性变化，最终都会通过这个函数来生效。

Status LogAndApply(...):
- 输入：一个或多个 VersionEdit。VersionEdit 是一个描述“变化”的数据结构，例如：“在 L1 层增加文件 A，在 L2 层删除文件 B 和 C，并更新 Compaction 指针”。Flush 和 Compaction 的结果都会被编码成 VersionEdit。
- 核心流程（原子性操作）：
  1. 加锁：获取数据库的全局互斥锁（InstrumentedMutex* mu），保证同一时间只有一个线程能修改 VersionSet。
  2. 构建新版本：创建一个 VersionBuilder，在当前 current 版本的基础上，应用传入的 VersionEdit，计算出一个全新的 Version 对象。
  3. 持久化到 MANIFEST：将这个 VersionEdit 序列化并写入到 MANIFEST 日志文件中。这是一个预写日志（WAL），保证了即使在写入过程中宕机，重启时也能通过 Recover 恢复。
  4. 安装新版本：MANIFEST 写入成功后，在内存中将新生成的 Version 设置为 current 版本，并更新版本链表的指针。
  5. 解锁：释放全局锁。
这个“先写日志，再改内存”的流程，是保证数据库元数据一致性的关键。

全局资源分配 (Resource Management)

VersionSet 作为全局管理者，负责分配和跟踪一些关键的唯一标识符。

uint64_t NewFileNumber() / FetchAddFileNumber(n):
- 当需要创建新的 SST 文件或 WAL 文件时，调用此函数获取一个全局唯一的、原子递增的文件编号。内部使用 std::atomic<uint64_t> next_file_number_ 实现线程安全。
uint64_t LastSequence() / SetLastSequence(s):
- 获取和设置数据库中已经提交并可见的最大序列号。序列号用于实现快照读和 MVCC。这些操作同样是原子的，以应对高并发的读写请求。
void MarkFileNumberUsed(uint64_t number):
- 在恢复期间，如果发现一个文件编号已经被使用，通过此函数更新 next_file_number_，确保之后不会再分配出重复的编号。

文件与 Compaction 管理 (File & Compaction)

虽然 Compaction 的决策和执行在其他模块（如 CompactionPicker），但其结果的记录和最终文件的生命周期管理由 VersionSet 负责。

void AddLiveFiles(...) / RemoveLiveFiles(...) (在 Version 类中):
- VersionSet 通过其管理的 Version 链表，可以追踪到所有“存活”的（被一个或多个 Version 引用的）SST 文件。这对于垃圾回收（删除不再被任何 Version 引用的旧文件）至关重要。当一个 Version 的引用计数变为 0 时，它所“独占”的文件就可以被安全地删除了。
Status GetLiveFilesChecksumInfo(...):
- 提供一个获取所有存活文件校验和信息的功能，用于数据库一致性检查或备份。

信息查询与调试 (Querying & Debugging)

VersionSet 提供了一系列接口，用于查询当前数据库的状态。

ColumnFamilySet* GetColumnFamilySet():
- 返回其管理的 ColumnFamilySet，这是访问所有列族数据的入口。
std::string DebugString(...) (在 Version 类中):
- VersionSet 通常会调用 current_version->DebugString() 来打印出当前 LSM-Tree 的详细结构，是调试的利器。
Status DumpManifest(...):
- 一个工具函数，可以将 MANIFEST 文件的内容以可读的方式打印出来，用于诊断和分析。

总结

VersionSet 在 RocksDB 中扮演着“管家”和“史官”的双重角色：

作为管家，它管理着数据库当前和历史的所有版本快照，分配全局资源，并确保所有对数据库结构的修改都是原子和持久的。
作为史官，它通过 MANIFEST 文件，忠实地记录下数据库从创建之初到当前状态的每一次结构变迁，并能在需要时（如重启恢复）重现这段历史。

对 VersionSet，特别是 LogAndApply 和 Recover 两个函数的理解，是掌握 RocksDB 核心工作原理的关键。

`VersionSet::LogAndApply`

通过一个类似于**两阶段提交（Two-Phase Commit）的机制，并结合预写日志（Write-Ahead Logging, WAL）**的思想来保证写入的原子性和持久性。这里的“日志”就是 MANIFEST 文件。

整个过程可以分解为以下几个关键步骤，我们结合代码来看：

1. 串行化写入：通过锁和队列保证顺序

在高并发场景下，多个线程（例如，多个 Compaction 任务）可能同时希望修改数据库的元数据。RocksDB 通过一个生产者-消费者队列 (manifest_writers_) 和数据库互斥锁 (mu) 来确保所有元数据变更都是串行处理的。

version_set.cc

// ... existing code ...
Status VersionSet::LogAndApply(const autovector<ColumnFamilyData*>& column_family_datas,
// ... (other parameters)) {mu->AssertHeld(); // 1. 确认调用者已经持有锁// ...// 2. 为当前请求创建一个或多个 ManifestWriter，并加入队列末尾for (int i = 0; i < num_cfds; ++i) {// ...writers.emplace_back(mu, column_family_datas[i], edit_lists[i], wcb);manifest_writers_.push_back(&writers[i]);}// 3. 循环等待，直到自己成为队列的头部，成为“领导者”while (!first_writer.done && &first_writer != manifest_writers_.front()) {first_writer.cv.Wait();}// ... 如果轮到自己，则调用 ProcessManifestWritesreturn ProcessManifestWrites(writers, mu, dir_contains_current_file,new_descriptor_log, new_cf_options,read_options, write_options);
}

第1步：函数要求调用时必须持有数据库全局锁 mu。
第2、3步：将写入请求封装成 ManifestWriter 对象放入队列。然后通过条件变量 cv.Wait() 等待，直到自己成为队列的头部（此时释放了全局锁）。这确保了同一时间只有一个线程（领导者）可以执行写入 MANIFEST 的操作，避免了竞争和交错写入。

2. 阶段一：持久化日志（Log）

这是保证持久性的核心。在真正修改内存中的 Version 之前，LogAndApply 会先将描述本次变更的 VersionEdit 写入 MANIFEST 文件并刷盘。

这个过程在 ProcessManifestWrites 函数中，并且为了不阻塞其他线程，它会临时释放锁。

// ... existing code ...// Unlock during manifest writemu->Unlock();// ... (准备写入记录)if (!skip_manifest_write) {// ...for (auto& e : batch_edits) {// ...// 4. 将 VersionEdit 序列化后写入 MANIFEST 文件io_s = raw_desc_log_ptr->AddRecord(write_options, record);if (!io_s.ok()) {// ... (出错处理)break;}}if (s.ok()) {// 5. 调用 fsync，确保 MANIFEST 的内容被强制刷到磁盘io_s =SyncManifest(db_options_, write_options, raw_desc_log_ptr->file());// ...}// ...}// ... (如果需要，更新 CURRENT 文件指向新的 MANIFEST)// 6. 操作完成，重新获取锁mu->Lock();
}

第4、5步：将所有变更写入 MANIFEST 文件，然后调用 SyncManifest（内部是 fsync）确保日志落盘。
关键点：如果在第4、5步之间或之后，但在第6步之前发生宕机，数据库的状态是不确定的吗？不是。因为此时内存中的 current 版本尚未改变。当数据库重启时，Recover 过程会读取 MANIFEST 文件，重放这些已经持久化的 VersionEdit，从而将数据库恢复到正确状态。

3. 阶段二：应用变更（Apply）

只有当 MANIFEST 成功写入并刷盘后，才会进行内存状态的变更。

// ... existing code ...// Install the new versionsif (s.ok()) { // 7. 只有在前面所有IO操作都成功的情况下// ... (处理列族增删)else {// ... (更新列族的 log number 等元数据)// 8. 将新生成的 Version 安装到 VersionSet 中，使其成为 current 版本for (int i = 0; i < static_cast<int>(versions.size()); ++i) {ColumnFamilyData* cfd = versions[i]->cfd_;AppendVersion(cfd, versions[i]);}}// 9. 更新内存中的 manifest 文件编号、大小、序列号等元数据if (!skip_manifest_write) {assert(max_last_sequence >= descriptor_last_sequence_);descriptor_last_sequence_ = max_last_sequence;manifest_file_number_ = pending_manifest_file_number_;// ...}} else {// 10. 如果失败，则回滚，删除新生成的 Version 对象for (auto v : versions) {delete v;}// ... (其他清理工作)}
// ... existing code ...

第7步：检查状态 s，确保前面的持久化操作都成功了。
第8、9步：原子地更新内存状态，将新的 Version 设为 current，并更新相关元数据。这个过程因为有锁的保护，所以是线程安全的。
第10步：如果持久化失败，则直接放弃本次变更，清理掉为新版本创建的内存对象，数据库的内存状态保持不变。

总结

LogAndApply 通过以下机制保证了一致性：

原子性（Atomicity）：通过“先写日志，再改内存”的两阶段流程。一次变更要么全部成功（日志落盘 + 内存更新），要么全部失败（内存状态不变）。即使中途宕机，Recover 机制也能保证恢复到一致的状态。
持久性（Durability）：通过 SyncManifest 将变更强制刷入磁盘，确保一旦函数成功返回，变更就不会因系统掉电而丢失。
隔离性（Isolation）：通过全局锁和写入队列，将所有元数据变更操作串行化，避免了并发修改带来的冲突。

`MANIFEST`

简单来说：

在磁盘上，MANIFEST 是一个日志文件 (Log File)，记录了数据库版本（Version）的每一次增量变更 (Delta)。
在内存中，这些增量变更被应用后，形成一个完整的、可直接查询的快照 (Snapshot)，主要由 Version 和 VersionSet 对象来表示。

1. MANIFEST 的磁盘表示 (On-Disk Representation)

MANIFEST 文件本身是一个二进制日志文件。它的内容不是一个巨大的、描述数据库全貌的结构体，而是一条接一条的变更记录。

基本单元：VersionEdit 这个变更记录在代码中由 VersionEdit 类表示。每一次 Flush 或 Compaction 完成后，都会生成一个或多个 VersionEdit，描述这次操作对 LSM-Tree 文件布局的改变。一个 VersionEdit 对象包含的信息有：
- new_files_: 本次操作新增了哪些 SST 文件（FileMetaData），以及它们被放在了哪个 level。
- deleted_files_: 本次操作删除了哪些 SST 文件。
- compact_pointers_: 更新某个 level 的 compaction 指针。
- log_number_, next_file_number_, last_sequence_: 更新一些全局元数据。
- 列族（Column Family）的增删改信息。
文件结构：Append-Only Log MANIFEST 是一个只追加 (Append-Only) 的日志。当有新的 VersionEdit 产生时，它会被序列化成二进制数据，追加到当前 MANIFEST 文件的末尾。
文件滚动 (Rollover) 当 MANIFEST 文件大小超过 ImmutableDBOptions::max_manifest_file_size 时，RocksDB 会创建一个新的 MANIFEST 文件。新的 MANIFEST 文件会首先写入一条包含当前所有文件信息的“快照”式 VersionEdit，然后后续的变更再追加到这个新文件后面。数据库目录下的 CURRENT 文件会更新，指向这个新的 MANIFEST。

代码证据：

在 db/version_set.cc 的 Recover 函数中，使用 log::Reader 来读取 MANIFEST 文件，这表明了其日志文件结构。
在 db/version_edit_handler.cc 的 Iterate 函数中，循环调用 reader.ReadRecord(&record, &scratch)，然后用 edit.DecodeFrom(record) 来解码每一条记录，这证实了其内容是由一条条 VersionEdit 记录组成的。

2. MANIFEST 的内存表示 (In-Memory Representation)

当 RocksDB 启动时，它会读取 MANIFEST 文件，并在内存中重建数据库的元数据视图。这个内存视图并不是 VersionEdit 列表，而是应用了所有 VersionEdit 之后的最终结果。

核心类：VersionSet 和 Version 内存中的表示主要由 VersionSet 和 Version 这两个类构成。
- VersionSet: 这是一个全局管理器，每个数据库实例只有一个。它存储了从 MANIFEST 中恢复的全局信息，例如：
  - manifest_file_number_: 当前 MANIFEST 的文件编号。
  - next_file_number_: 下一个将要被分配的文件编号。
  - last_sequence_: 已分配的最后一个序列号。
  - log_number_: 当前 WAL 文件的编号。
  - 最重要的是，它管理着所有列族的 current 版本（Version 对象）。
- Version: 每个列族都有一个 current 的 Version 对象，它代表了该列族当前时刻的完整文件快照。它不关心是如何变成这个状态的，只关心现在是什么状态。 Version 对象通过其成员 VersionStorageInfo storage_info_ 来持有具体的文件列表。
- VersionStorageInfo: 这是最核心的数据结构，它包含了：
  - std::vector<FileMetaData*> files_[num_levels_]: 一个二维向量，精确地存储了 LSM-Tree 每一层有哪些 SST 文件。FileMetaData 包含了文件的编号、大小、key 的范围等所有元信息。
  - blob_files_: 所有关联的 Blob 文件列表。
  - 各种用于选择 Compaction 的得分和状态。

从磁盘到内存的转换过程 (Recover):

RocksDB 创建一个临时的 VersionBuilder 对象。
VersionEditHandler 开始逐条读取 MANIFEST 中的 VersionEdit 记录。
每读取一条 edit，就将其应用（Apply）到 VersionBuilder 上。VersionBuilder 内部维护着一个临时的文件列表，根据 edit 的内容进行增删。
当所有 edit 都被应用后，VersionBuilder 就包含了数据库的最终文件布局。
最后，调用 VersionBuilder::SaveTo(Version* v)，用 Builder 中的最终结果来填充并创建一个全新的 Version 对象。
这个新创建的 Version 对象被设置为 VersionSet 中的 current 版本。

几个问题

`VersionSet` 是怎么维护多个 `Version` 的？

VersionSet 并不直接维护一个 Version 列表，而是通过它管理的 ColumnFamilySet 来间接实现。每个列族（ColumnFamilyData）内部都维护着一个属于自己的 Version 链表。

这个关系可以这样理解： VersionSet -> ColumnFamilySet -> (多个)ColumnFamilyData -> (每个CFD都有一个)Version双向链表

这个双向链表是核心数据结构。我们可以在 version_set.h 中找到它的定义：

version_set.h

// ... existing code ...
class Version {
// ... existing code ...Version* next_;     // Next version in linked listVersion* prev_;     // Previous version in linked listint refs_;          // Number of live refs to this version
// ... existing code ...
};

工作机制如下：

双向链表结构：对于每一个列族，所有的 Version 对象通过 next_ 和 prev_ 指针形成一个双向链表。ColumnFamilyData 中有一个 dummy_versions_ 的头节点，它指向链表的头部和尾部。
current 版本：链表的头部（dummy_versions_->next_）始终是最新的、当前的 Version。任何新的读请求（如 Get 或创建新的迭代器）都会从这个 current 版本开始。
新版本的产生：当发生 Flush 或 Compaction 时，LogAndApply 会创建一个新的 Version 对象。这个新对象会被插入到链表的头部，成为新的 current 版本。旧的 current 版本就变成了链表中的第二个节点。

我们可以用一个简单的图来表示这个过程：

// 初始状态，只有一个版本 V1
[CFD dummy_head] <--> [V1 (current, refs=2)]// 发生一次 Compaction，生成新版本 V2
// V2 被插入到链表头部，成为新的 current
[CFD dummy_head] <--> [V2 (current, refs=1)] <--> [V1 (refs=2)]// 又发生一次 Flush，生成新版本 V3
[CFD dummy_head] <--> [V3 (current, refs=1)] <--> [V2 (refs=1)] <--> [V1 (refs=2)]

通过这种方式，VersionSet 为每个列族都维护了一个版本历史链，current 版本代表了数据库的最新状态，而链表中的旧版本则服务于那些在旧状态上创建的、尚未结束的读操作。

多个 `Version` 什么时候会删除？

Version 的生命周期由引用计数（Reference Counting）机制来管理。这就是 Version 类中 int refs_; 成员变量的作用。

删除过程如下：

增加引用 (Ref())：当一个操作需要一个稳定的数据视图时，它会“持有”一个 Version 的引用，将其 refs_ 加一。典型的场景包括：
- 创建一个新的迭代器（Iterator）。
- 创建一个快照（Snapshot）。
- 执行一次 Get 操作（在 Get 的生命周期内持有引用）。
- Version 自身作为链表的一部分，也会持有对其前一个 Version 的引用。
减少引用 (Unref())：当操作完成，不再需要那个数据视图时，它会“释放”对 Version 的引用，将其 refs_ 减一。例如：
- 迭代器被销毁。
- 快照被释放。
- Get 操作完成。
触发删除：当一个 Version 的 refs_ 减到 0 时，意味着没有任何操作还在使用这个版本了。此时，Unref() 函数会触发删除逻辑：
- 将该 Version 从双向链表中移除。
- 释放该 Version 对象自身占用的内存。
- 关键：检查这个 Version 独占了哪些 SST 文件（即这些文件没有被其他任何 Version 引用）。将这些独占的文件标记为“过时文件”（Obsolete Files），放入 obsolete_files_ 列表中，等待后台任务进行物理删除。

所以，一个旧 Version 不会被立即删除，而是会一直存活，直到所有依赖它的读操作全部完成。这正是 RocksDB 实现 MVCC（多版本并发控制）和提供一致性快照读的基础。

`Version` 保存的是增量还是全量数据？

这是一个非常关键的区别：

VersionEdit 保存的是增量（Incremental）： VersionEdit 是一个描述“变化”的对象。它非常轻量，只记录了本次操作导致的变化，例如：“在 L1 层增加了文件 A，在 L2 层删除了文件 B 和 C”。VersionEdit 会被序列化后写入 MANIFEST 文件。
Version 保存的是全量（Full）元数据： Version 对象代表了数据库在某一个特定时间点的完整快照。它包含了该时间点 LSM-Tree 的全部元数据信息，包括：
- 每一层（Level）有哪些 SST 文件。
- 每个文件的元数据（大小、key 的范围等）。
- 下一次 Compaction 的起始点（compaction_pointer）。
- 所有相关的 Blob 文件信息。

为什么 Version 必须是全量的？

因为这样效率最高。当一个读请求发生时，RocksDB 可以直接使用 Version 对象中完整的 LSM-Tree 视图来查找数据，而不需要从一个基础版本开始，然后依次应用一长串的增量 VersionEdit 来计算出当前的状态。那样做会非常缓慢和复杂。

可以这样比喻：

VersionEdit 就像是 Git 的一次 commit，它只记录了文件的 diff（增量）。
Version 就像是执行 git checkout <commit_hash> 后，你工作目录下所有文件的完整状态（全量）。

LogAndApply 的过程就是：基于旧的 Version（旧的全量状态），应用一个 VersionEdit（增量变化），从而计算出一个新的 Version（新的全量状态）。

磁盘上的 `VersionEdit`：增量的变更日志

RocksDB 不会把庞大的 Version 对象直接序列化写到磁盘。这样做效率极低，因为每次 Flush 或 Compaction 都只改变了少数几个文件，如果每次都重写所有文件的元数据，会造成巨大的写放大。

因此，RocksDB 采用了增量日志的方式。

“增量”体现在：VersionEdit 对象只记录相对于上一个版本的变化。比如：
- AddFile(): 在某个 level 增加了哪个 SST 文件。
- DeleteFile(): 在某个 level 删除了哪个 SST 文件。
- SetLogNumber(): 更新当前的 WAL 文件号。
- ...等等。
version_edit.h 中的 Tag 枚举就定义了所有可能的增量变更类型。
version_edit.h
```
// ... existing code ...
enum Tag : uint32_t {kComparator = 1,kLogNumber = 2,kNextFileNumber = 3,kLastSequence = 4,kCompactCursor = 5,kDeletedFile = 6,kNewFile = 7,// 8 was used for large value refskPrevLogNumber = 9,kMinLogNumberToKeep = 10,
// ... existing code ...
```
作用：
- 持久化：VersionEdit 被序列化后追加写入到 MANIFEST 文件中。这是一种高效、紧凑的持久化方式。
- 恢复：当数据库重启时，通过按顺序重放（Replay）MANIFEST 文件中的所有 VersionEdit，就可以在内存中重建出那个最终的全量 Version。

LogAndApply 函数正是这个机制的核心实现。它的名字已经说明了它的两大职责：

Log (记录日志)：将描述本次变更的 VersionEdit 写入 MANIFEST 文件。这是增量持久化的过程。
Apply (应用变更)：基于当前的 Version 和这个 VersionEdit，在内存中创建一个新的、全量的 Version 对象，并将其设置为 current 版本，同时通过链表与旧 Version 连接起来。

我们来看LogAndApply 函数声明：

// ... existing code ...// Apply *edit to the current version to form a new descriptor that// is both saved to persistent state and installed as the new// current version.  Will release *mu while actually writing to the file.// column_family_options has to be set if edit is column family add.// REQUIRES: *mu is held on entry.// REQUIRES: no other thread concurrently calls LogAndApply()Status LogAndApply(ColumnFamilyData* column_family_data, const ReadOptions& read_options,const WriteOptions& write_options, VersionEdit* edit,InstrumentedMutex* mu, FSDirectory* dir_contains_current_file,bool new_descriptor_log = false,const ColumnFamilyOptions* column_family_options = nullptr,const std::function<void(const Status&)>& manifest_wcb = {},const std::function<Status()>& pre_cb = {}) {
// ... existing code ...

它的输入参数是一个 VersionEdit* edit，这正是一个增量的变更。函数内部会完成以下工作流：

创建一个 VersionBuilder，用当前的 Version 初始化它。
调用 builder->Apply(edit)，将增量变更应用到 builder 上。
将 edit 序列化并写入 MANIFEST 文件（Log）。
调用 builder->SaveTo(new_version)，生成一个新的全量 Version。
调用 AppendVersion(new_version)，将新的全量 Version 安装为当前版本（Apply）。

总结

全量 Version 是一个内存概念，它代表了某个时间点的完整数据库元数据快照，用于服务读请求和 Compaction 决策。
增量 VersionEdit 是一个持久化概念，它以日志的形式记录状态变更，被写入 MANIFEST 文件，用于高效地持久化和故障恢复。
LogAndApply 是将一个增量变更应用到当前的全量状态上，从而生成一个新的全量状态，并同时将这个增量变更持久化到磁盘的过程。

这种“内存全量，磁盘增量”的设计，兼顾了运行时的高性能读取和低延迟的元数据持久化，是许多高性能存储引擎的通用设计模式。

重启后Version变化

Version* next_ 和 refs_（引用计数）是纯粹的内存概念。

Version 链表：存在于内存中，用于支持 MVCC（多版本并发控制）。当有新的 Flush 或 Compaction 完成时，会创建一个新的 Version 对象并链入链表头部。
引用计数 refs_：当一个操作（如迭代器或快照）需要一个稳定的数据视图时，它会持有对应 Version 的引用，使其 refs_ 加一。操作结束后，refs_ 减一。
运行时的删除：当一个 Version 的 refs_ 降为 0 时，说明没有任何正在进行中的操作需要它了。此时，这个 Version 对象会被从内存中删除，并且它所独占的 SST 文件会被识别出来，加入到一个“待删除列表” (obsolete_files_) 中，由后台线程进行物理删除。

当关闭程序时，所有内存中的状态都会丢失。

引用计数归零：整个 Version 链表，包括所有的 Version 对象和它们的引用计数，都会随着进程的退出而烟消云散。引用计数本身不会以任何形式被保存到磁盘。
MANIFEST 是唯一真相：RocksDB 唯一依赖的、用来恢复元数据状态的，是 MANIFEST 文件。这个文件记录了构成数据库最新、最一致状态所需要的所有 SST 文件的信息（哪个文件在哪一层等等）。它描述的是最终的、被提交的那个 Version 的样子，而不是整个 Version 历史链。

当 RocksDB 再次启动时，它会执行 Recover 流程：

重建最新 Version：RocksDB 会找到并读取 MANIFEST 文件，根据其中的记录，在内存中重新构建出一个代表数据库最新状态的 Version 对象。注意，它只构建这一个 Version，而不是关闭前的整个历史链。
扫描物理文件：RocksDB 会列出数据目录下所有存在的 .sst 文件。
对比和清理：这是最重要的环节。RocksDB 会拿第 2 步中找到的所有物理文件列表，与第 1 步中根据 MANIFEST 重建的最新 Version 所需的文件列表进行对比。
- 如果一个 SST 文件存在于物理磁盘上，但不在最新 Version 所需的列表里，那么这个文件就被认为是过时的、无用的垃圾文件。
- 这些垃圾文件会被识别出来，并被安全地删除。

可以这样理解：

Version 链表和引用计数：就像是一位建筑师脑海中的多个设计草稿。只要有工人在参照某个草稿施工（迭代器/快照），这份草稿就不能扔。
MANIFEST 文件：是最终被审批通过、存档的最终设计蓝图。
关闭程序：建筑师下班回家了，他脑海里的所有草稿（Version 链表）都消失了。
再次启动程序：第二天，一位新的建筑师来上班。他不会去想昨天的草稿，而是直接拿出档案室里的最终设计蓝图 (MANIFEST)。他根据蓝图清点工地上现有的建材（SST 文件），发现多出来一堆废料（不在蓝图上的文件），于是叫人把这些废料全部清理掉。

所以，对于程序关闭前未被删除的旧 Version 所关联的 SST 文件，它们的最终命运是在下一次数据库启动的恢复过程中被识别并删除。这保证了即使程序异常崩溃，RocksDB 也能在重启后将存储空间清理到一致的状态。

`VersionSet::Recover`

这个函数的实现逻辑，正是“重启后每个列族只创建一个 Version”这一行为的直接代码体现。

下面是 version_set.cc 中 Recover 函数的核心逻辑分解：

// ... existing code ...
Status VersionSet::Recover(const std::vector<ColumnFamilyDescriptor>& column_families, bool read_only,std::string* db_id, bool no_error_if_files_missing, bool is_retry,Status* log_status) {const ReadOptions read_options(Env::IOActivity::kDBOpen);// 步骤 1: 找到 "CURRENT" 文件，并从中解析出当前 MANIFEST 文件的路径和编号。// 这是恢复的入口，确定从哪个文件开始读取元数据。std::string manifest_path;Status s = GetCurrentManifestPath(dbname_, fs_.get(), is_retry,&manifest_path, &manifest_file_number_);if (!s.ok()) {return s;}ROCKS_LOG_INFO(db_options_->info_log, "Recovering from manifest file: %s\n",manifest_path.c_str());// 步骤 2: 创建一个文件读取器，准备读取 MANIFEST 文件。std::unique_ptr<SequentialFileReader> manifest_file_reader;{std::unique_ptr<FSSequentialFile> manifest_file;s = fs_->NewSequentialFile(manifest_path,fs_->OptimizeForManifestRead(file_options_),&manifest_file, nullptr);if (!s.ok()) {return s;}manifest_file_reader.reset(new SequentialFileReader(std::move(manifest_file), manifest_path,db_options_->log_readahead_size, io_tracer_, db_options_->listeners,/*rate_limiter=*/nullptr, is_retry));}TEST_SYNC_POINT("VersionSet::Recover:StartManifestRead");uint64_t current_manifest_file_size = 0;uint64_t log_number = 0;{VersionSet::LogReporter reporter;Status log_read_status;reporter.status = &log_read_status;// 步骤 3: 创建一个 log::Reader，它能够解析 MANIFEST 文件中一条条的记录（VersionEdit）。log::Reader reader(nullptr, std::move(manifest_file_reader), &reporter,true /* checksum */, 0 /* log_number */);// 步骤 4: 【核心】创建一个 VersionEditHandler。// 这个 handler 是整个恢复过程的大脑。它会接收所有的 VersionEdit，// 并在内部为每个列族维护一个 VersionBuilder，不断累积变更。VersionEditHandler handler(read_only, column_families, const_cast<VersionSet*>(this),/*track_found_and_missing_files=*/false, no_error_if_files_missing,io_tracer_, read_options, /*allow_incomplete_valid_version=*/false,EpochNumberRequirement::kMightMissing);// 步骤 5: 【核心】调用 Iterate，遍历 MANIFEST 中的所有记录，并交由 handler 处理。// handler 在内部会调用 VersionBuilder::Apply() 来应用每一个 edit。handler.Iterate(reader, &log_read_status);s = handler.status();// 步骤 6: 当 Iterate 完成后，handler 内部的 VersionBuilder 已经构建好了// 所有列族的最终状态。handler 的析构函数或其内部逻辑会调用// VersionBuilder::SaveTo() 来创建最终的、全新的 Version 对象，// 并调用 VersionSet::AppendVersion() 将其安装为 current 版本。if (s.ok()) {log_number = handler.GetVersionEditParams().GetLogNumber();current_manifest_file_size = reader.GetReadOffset();assert(current_manifest_file_size != 0);handler.GetDbId(db_id);}
// ... existing code ...

总结分析

没有循环创建 Version：可以看到，整个 Recover 流程中，并没有一个循环来创建多个 Version 对象并把它们组成链表。
VersionEditHandler 是关键：整个恢复过程被委托给了 VersionEditHandler。它的设计目标就是：读取一系列的增量 VersionEdit，然后在内存中构建出一个最终的全量状态。
结果是唯一的 Version：当 handler.Iterate 执行完毕后，它已经完成了所有计算，并为每个列族生成了一个代表数据库最新状态的 Version 对象，然后将这个对象设置为了 current 版本。

所以，这段代码完美地证明了之前的结论：RocksDB 重启时，并不会恢复内存中的 Version 历史链，而是通过读取 MANIFEST，重新计算并构建出唯一一个代表最新状态的 Version。

`VersionEditHandlerBase::Iterate`

这个函数是所有 VersionEditHandler 子类（如 VersionEditHandler 和 VersionEditHandlerPointInTime）的公共基类方法。它的主要职责是：从 log::Reader 中循环读取 MANIFEST 的每一条记录，解码成 VersionEdit，然后调用子类实现的虚函数 ApplyVersionEdit 来处理这些变更。

我们来逐行解析它的核心逻辑：

void VersionEditHandlerBase::Iterate(log::Reader& reader,Status* log_read_status) {Slice record;std::string scratch;assert(log_read_status);assert(log_read_status->ok());[[maybe_unused]] size_t recovered_edits = 0;// 1. 调用虚函数 Initialize()，允许子类进行一些准备工作。//    对于 VersionEditHandler，它会在这里创建默认列族的 VersionBuilder。Status s = Initialize();// 2. 核心循环：只要没读到 MANIFEST 末尾，并且状态正常，就一直读取。while (reader.LastRecordEnd() < max_manifest_read_size_ && s.ok() &&reader.ReadRecord(&record, &scratch) && log_read_status->ok()) {VersionEdit edit;// 3. 将从 MANIFEST 中读取的一条二进制记录 (record) 解码成一个 VersionEdit 对象。s = edit.DecodeFrom(record);if (s.ok()) {// 4. 将解码后的 edit 添加到 read_buffer_。这个 buffer 主要用于处理原子写入组。s = read_buffer_.AddEdit(&edit);}if (s.ok()) {ColumnFamilyData* cfd = nullptr;if (edit.IsInAtomicGroup()) {// 4a. 如果 edit 属于一个原子组，并且 buffer 满了，就批量处理 buffer 中的所有 edits。if (read_buffer_.IsFull()) {s = OnAtomicGroupReplayBegin();for (size_t i = 0; s.ok() && i < read_buffer_.replay_buffer().size();i++) {auto& e = read_buffer_.replay_buffer()[i];// 5. 【关键】对原子组中的每一条 edit，调用虚函数 ApplyVersionEdit。//    这个函数由子类实现，真正执行将变更应用到 VersionBuilder 的逻辑。s = ApplyVersionEdit(e, &cfd);if (s.ok()) {recovered_edits++;}}if (s.ok()) {read_buffer_.Clear();s = OnAtomicGroupReplayEnd();}}} else {// 4b. 如果 edit 是一个普通操作（非原子组），直接处理。// 5. 【关键】调用虚函数 ApplyVersionEdit。s = ApplyVersionEdit(edit, &cfd);if (s.ok()) {recovered_edits++;}}}}// ... 省略了错误处理和收尾工作 ...// 6. 调用虚函数 CheckIterationResult，允许子类在循环结束后进行最终处理。//    对于 VersionEditHandler，它会在这里检查 MANIFEST 的完整性，//    并最终创建 Version 对象并安装。CheckIterationResult(reader, &s);// ... 省略了详细的错误状态包装 ...status_ = s;
}

关键逻辑解读

循环读取（While Loop）: 这是整个恢复过程的引擎。它不断地从 MANIFEST 文件中拉取一条条的变更记录。
解码（edit.DecodeFrom(record)）: MANIFEST 中存储的是二进制的 VersionEdit。这一步将其反序列化为内存中的 VersionEdit 对象，这样我们就可以访问它的内容了（比如新增了哪个文件，删除了哪个文件等）。
分发（ApplyVersionEdit）: 这是整个设计的精髓所在，体现了模板方法模式。Iterate 函数本身定义了“读取-解码-应用”这个通用的算法骨架，但它并不知道如何具体“应用”一个 VersionEdit。它通过调用虚函数 ApplyVersionEdit，将这个具体的应用逻辑委托给子类去实现。
- 在 VersionEditHandler::ApplyVersionEdit 中，它会根据 edit 的类型（是增加/删除列族，还是文件变更），找到对应的 ColumnFamilyData 和 VersionBuilder，然后调用 builder->Apply(&edit)，将变更累积到 VersionBuilder 中。
收尾（CheckIterationResult）: 当所有 VersionEdit 都被应用到 VersionBuilder 之后，这个虚函数被调用。在 VersionEditHandler::CheckIterationResult 的实现中，它会：
- 检查 MANIFEST 是否包含所有必要的信息（如 next_file_number）。
- 遍历所有 builders_，调用 LoadTables 来预加载SST文件的元数据。
- 最终，VersionBuilder 会被用来构建出那个唯一的、全新的 Version 对象，并由 VersionSet 安装为 current 版本。（这一步的调用链比较深，最终会触发 VersionBuilder::SaveTo 和 VersionSet::AppendVersion）。

总结

VersionEditHandlerBase::Iterate 函数本身并不直接创建 Version。它的角色是一个驱动器和分发器。它负责从 MANIFEST 中读取变更历史，然后将这些变更一条条地“喂”给子类实现的 ApplyVersionEdit 方法。

真正的状态累积发生在 VersionBuilder 中，而最终 Version 对象的创建和安装则发生在 CheckIterationResult 的收尾阶段。整个过程清晰地表明，RocksDB 是通过重放所有历史变更来重新计算出数据库的最终状态，而不是直接从磁盘加载一个现成的 Version 对象。

`VersionEditHandler::CheckIterationResult`

这个函数在 Iterate 循环成功读取并应用了 MANIFEST 中所有的 VersionEdit 之后被调用。它的核心职责是：进行最终一致性检查，加载SST元数据，创建并安装新的 Version，最后更新 VersionSet 的全局状态。

下面是该函数的逻辑分解，将重点标注出与我们讨论相关的部分：

version_edit_handler.cc

void VersionEditHandler::CheckIterationResult(const log::Reader& reader,Status* s) {assert(s != nullptr);// 步骤 1: 检查 MANIFEST 的完整性。// 确保像 next_file_number, last_sequence 这样的关键元信息都已从 MANIFEST 中读到。// 如果缺失，说明 MANIFEST 文件损坏，恢复失败。if (!s->ok()) {// Do nothing here.} else if (!version_edit_params_.HasLogNumber() ||!version_edit_params_.HasNextFile() ||!version_edit_params_.HasLastSequence()) {// ... 构造 Corruption 错误信息 ...*s = Status::Corruption(msg);}// ... 其他检查，比如是否所有列族都被正确打开 ...// ...// 步骤 2: 加载 SST 文件元数据。// 遍历所有未被删除的列族。if (s->ok()) {for (auto* cfd : *(version_set_->GetColumnFamilySet())) {if (cfd->IsDropped()) {continue;}// ...// 调用 LoadTables，它会使用 VersionBuilder 去打开并读取每个 SST 文件的// 索引块和过滤器块，将元数据加载到内存（TableCache）中。// 这是为后续的读操作做准备。*s = LoadTables(cfd, /*prefetch_index_and_filter_in_cache=*/false,/*is_initial_load=*/true);if (!s->ok()) {// ... 错误处理 ...break;}}}// 步骤 3: 【核心】创建并安装新的 Version。// 再次遍历所有未被删除的列族。if (s->ok()) {for (auto* cfd : *(version_set_->column_family_set_)) {if (cfd->IsDropped()) {continue;}assert(cfd->initialized());VersionEdit edit; // 传入一个空的 edit// 调用 MaybeCreateVersionBeforeApplyEdit，并强制创建 Version。// 这个函数内部会：// 1. new Version(...) 创建一个全新的 Version 对象。// 2. builder->SaveTo(...) 将 VersionBuilder 中累积的所有文件信息保存到新 Version 中。// 3. version_set_->AppendVersion(...) 将这个新 Version 安装为列族的 current 版本。*s = MaybeCreateVersionBeforeApplyEdit(edit, cfd,/*force_create_version=*/true);if (!s->ok()) {break;}}}// 步骤 4: 更新 VersionSet 的全局状态。// 将从 MANIFEST 中恢复的各种全局计数器（如下一个文件号、最后一个序列号等）// 设置到 VersionSet 对象中。if (s->ok()) {version_set_->manifest_file_size_ = reader.GetReadOffset();assert(version_set_->manifest_file_size_ > 0);version_set_->next_file_number_.store(version_edit_params_.GetNextFile() +1);SequenceNumber last_seq = version_edit_params_.GetLastSequence();// ... 更新 last_allocated_sequence_, last_published_sequence_, last_sequence_ ...}
}

关键代码解读与验证

MaybeCreateVersionBeforeApplyEdit(..., force_create_version=true): 这是整个流程的图穷匕见之处。

force_create_version=true 这个参数是关键。它告诉函数，无论如何都要创建一个新的 Version。

我们深入看一下 MaybeCreateVersionBeforeApplyEdit 的实现：

// ... existing code ...
Status VersionEditHandler::MaybeCreateVersionBeforeApplyEdit(const VersionEdit& edit, ColumnFamilyData* cfd, bool force_create_version) {// ...auto* builder = builder_iter->second->version_builder();if (force_create_version) {// 1. 创建一个全新的、空的 Version 对象auto* v = new Version(cfd, version_set_, version_set_->file_options_,cfd->GetLatestMutableCFOptions(), io_tracer_,version_set_->current_version_number_++,epoch_number_requirement_);// 2. 将 builder 中累积的所有文件元数据保存到这个新 Version 中s = builder->SaveTo(v->storage_info());if (s.ok()) {// 3. 准备并安装这个 Versionv->PrepareAppend(read_options_,!(version_set_->db_options_->skip_stats_update_on_db_open));version_set_->AppendVersion(cfd, v);} else {delete v;}}// 4. 应用传入的 edit (在 CheckIterationResult 调用时，这是一个空 edit)s = builder->Apply(&edit);return s;
}

这段代码清晰地展示了：new Version -> builder->SaveTo -> version_set_->AppendVersion 这个完整的创建和安装流程。

循环的上下文: CheckIterationResult 中的循环是遍历所有列族，为每一个列族执行一次上述的创建和安装流程。

VersionEditHandler::CheckIterationResult 函数的分析，为我们之前的讨论提供了最终且决定性的证据。它清楚地表明：

在 MANIFEST 文件被完全解析、所有变更都被累积到 VersionBuilder 之后，程序会进入这个收尾函数。
在这个函数中，会为每个列族显式地 new 一个 Version 对象。
然后调用 builder->SaveTo()，将恢复的元数据全量填充到这个新 Version 中。
最后通过 version_set_->AppendVersion() 将其安装为当前活动版本。

这整个流程下来，结果就是在数据库启动恢复完成后，内存中的每个列族都拥有一个且仅有一个 Version 对象，这个对象精确地代表了 MANIFEST 文件所描述的数据库状态。

`ReactiveVersionSet`

ReactiveVersionSet 的名字中的 "Reactive"（反应式）是理解其功能的关键。与主动管理和写入 MANIFEST 的标准 VersionSet 不同，ReactiveVersionSet 是被动地、反应式地消费 MANIFEST 文件中的变更。

它的主要应用场景是 RocksDB 的从库（Secondary Instance）。

想象一个主从复制的场景：

主库（Primary Instance）：使用标准的 VersionSet，正常处理写入、Flush、Compaction，并将这些元数据变更写入 MANIFEST 文件。
从库（Secondary Instance）：与主库共享（或通过网络文件系统访问）同一个数据库目录。它不会自己发起任何结构性变更，而是通过持续地“追赶”（tailing）MANIFEST 文件，读取主库写入的 VersionEdit，然后在自己的内存中重放（replay）这些变更，从而与主库的 LSM-Tree 结构保持同步。

ReactiveVersionSet 就是为从库这种“只读+追赶”模式量身定做的。

我们通过分析它重写（override）和禁用的函数来理解其核心行为。

1. 禁用的核心写入功能：`LogAndApply`

这是 ReactiveVersionSet 与 VersionSet 最根本的区别。

// ... existing code ...
private:std::unique_ptr<ManifestTailer> manifest_tailer_;// TODO: plumb Env::IOActivity, Env::IOPriorityconst ReadOptions read_options_;using VersionSet::LogAndApply;using VersionSet::Recover;Status LogAndApply(const autovector<ColumnFamilyData*>& /*cfds*/,const ReadOptions& /* read_options */,const WriteOptions& /* write_options */,const autovector<autovector<VersionEdit*>>& /*edit_lists*/,InstrumentedMutex* /*mu*/, FSDirectory* /*dir_contains_current_file*/,bool /*new_descriptor_log*/, const ColumnFamilyOptions* /*new_cf_option*/,const std::vector<std::function<void(const Status&)>>& /*manifest_wcbs*/,const std::function<Status()>& /*pre_cb*/) override {return Status::NotSupported("not supported in reactive mode");}// No copy allowedReactiveVersionSet(const ReactiveVersionSet&);ReactiveVersionSet& operator=(const ReactiveVersionSet&);
};

可以看到，ReactiveVersionSet 将其父类的 LogAndApply 方法重写，并直接返回 Status::NotSupported。这明确地表明：ReactiveVersionSet 不具备主动将变更写入 MANIFEST 的能力。它是一个纯粹的消费者，而不是生产者。

2. 核心功能：`ReadAndApply` 和 `Recover`

ReactiveVersionSet 的核心逻辑体现在它自己定义的 ReadAndApply 方法和它对 Recover 的特殊使用上。

Status Recover(...):
- 在从库实例启动时，ReactiveVersionSet 会调用 Recover。这个过程和主库类似，都是完整地读取一遍 MANIFEST 文件，在内存中建立起数据库在某个时间点的完整 Version 视图。
- 但与主库不同的是，恢复完成后，它会初始化一个 ManifestTailer 对象，准备开始“追赶”模式。
Status ReadAndApply(...):
- 这是从库在运行期间的核心函数。它会被周期性地调用，用来检查 MANIFEST 文件是否有新的内容。
- 它利用 manifest_tailer_ 读取从上次读取点之后新增的所有 VersionEdit 记录。
- 对于每一条新的 VersionEdit，它会调用内部的 ApplyOneVersionEditToBuilder 方法，将其应用到当前内存中的 Version 上，生成一个新的 Version 并设置为 current。
- 这个过程本质上就是在内存中模拟主库的 LogAndApply 的后半部分（Apply 阶段），从而实现状态同步。

3. 对原子写入组（Atomic Group）的处理

MANIFEST 中的 VersionEdit 可能被标记为原子写入组的一部分。这意味着一组 VersionEdit 必须全部成功应用，才算一个完整的操作。ReactiveVersionSet 在 ReadAndApply 时必须正确处理这种情况。

从相关的测试文件 version_set_test.cc 中可以看到大量针对 ReactiveVersionSet 处理原子组的测试用例，例如：

HandleIncompleteTrailingAtomicGroupWithReactiveVersionSetReadAndApply
HandleValidAtomicGroupWithReactiveVersionSetRecover

这些测试表明，ReactiveVersionSet 内部有逻辑来处理不完整的原子组。如果它在追赶 MANIFEST 时，读到了一个原子组的开头但没有读到结尾（可能主库还没写完），它会把这些 VersionEdit 暂存在 replay_buffer_ 中，直到读到原子组的最后一个 edit 后，再将整个组一次性地应用。

// ... existing code ...
#ifndef NDEBUGuint64_t TEST_read_edits_in_atomic_group() const;
#endif  //! NDEBUGstd::vector<VersionEdit>& replay_buffer();protected:
// ... existing code ...

replay_buffer() 这个接口的存在也印证了上述的缓冲机制。

总结

ReactiveVersionSet 是 VersionSet 的一个高度特化的子类，其设计哲学和行为模式与父类截然不同：

特性	VersionSet (主库)	ReactiveVersionSet (从库)
角色	生产者 & 消费者	纯消费者
核心操作	LogAndApply	ReadAndApply
数据流	主动将内存变更写入 MANIFEST	被动从 MANIFEST 读取变更并更新内存
状态来源	自身产生的操作 (Flush, Compaction)	外部（主库）写入的 MANIFEST
适用场景	主数据库实例 (Primary DB)	从数据库实例 (Secondary DB)

通过这种主从分离的设计，RocksDB 实现了高效的只读复制能力。从库不需要承担 Compaction 等重负载任务，只需轻量级地追赶 MANIFEST 日志，就能提供与主库几乎实时同步的读服务。

`VersionStorageInfo`

Version 类代表了数据库在某个时间点的快照。VersionStorageInfo 则是 Version 的一个核心组成部分，它被专门设计用来封装和管理与一个 Version 相关的所有存储层信息。

通过将这部分逻辑分离到 VersionStorageInfo 中，Version 类本身可以更专注于提供数据访问接口（如 Get, AddIterators）和生命周期管理（Ref, Unref），使得代码结构更清晰。

`VersionStorageInfo` 的角色和定位

VersionStorageInfo 可以被看作是 Version 的“数据核心”或“存储状态容器”。它包含了LSM-Tree的完整拓扑结构、参与压缩决策所需的所有元数据和统计信息。

在 Version 类中，它被作为一个成员变量持有：

// ... existing code ...
class Version {
// ... existing code ...private:
// ... existing code ...VersionStorageInfo storage_info_;
// ... existing code ...
};

这意味着每个 Version 对象都有一个与之对应的 VersionStorageInfo 实例，共同构成一个完整的数据库快照。

核心数据成员分析

VersionStorageInfo 的成员变量详细描述了一个版本所包含的所有SST文件、Blob文件以及用于优化和决策的派生数据。

// ... existing code ...
class VersionStorageInfo {
// ... existing code ...private:
// ... existing code ...const InternalKeyComparator* internal_comparator_;const Comparator* user_comparator_;int num_levels_;            // Number of levelsint num_non_empty_levels_;  // Number of levels. Any level larger than it// is guaranteed to be empty.
// ... existing code ...CompactionStyle compaction_style_;// List of files per level, files in each level are arranged// in increasing order of keysstd::vector<FileMetaData*>* files_;// Map of all table files in version. Maps file number to (level, position on// level).using FileLocations = UnorderedMap<uint64_t, FileLocation>;FileLocations file_locations_;// Vector of blob files in version sorted by blob file number.BlobFiles blob_files_;
// ... existing code ...// A list for the same set of files that are stored in files_,// but files in each level are now sorted based on file// size. The file with the largest size is at the front.// This vector stores the index of the file from files_.std::vector<std::vector<int>> files_by_compaction_pri_;// An index into files_by_compaction_pri_ that specifies the first// file that is not yet compactedstd::vector<int> next_file_to_compact_by_size_;// This vector contains list of files marked for compaction and also not// currently being compacted. It is protected by DB mutex. It is calculated in// ComputeCompactionScore(). Used by Leveled and Universal Compaction.autovector<std::pair<int, FileMetaData*>> files_marked_for_compaction_;autovector<std::pair<int, FileMetaData*>> expired_ttl_files_;autovector<std::pair<int, FileMetaData*>>files_marked_for_periodic_compaction_;
// ... existing code ...// Level that should be compacted next and its compaction score.// Score < 1 means compaction is not strictly needed.  These fields// are initialized by ComputeCompactionScore.// The most critical level to be compacted is listed first// These are used to pick the best compaction levelstd::vector<double> compaction_score_;std::vector<int> compaction_level_;
// ... existing code ...// Estimated bytes needed to be compacted until all levels' size is down to// target sizes.uint64_t estimated_compaction_needed_bytes_;// ... existing code ...bool finalized_;
// ... existing code ...
};

我们可以将这些成员分为几类：

LSM-Tree 结构:
- files_: 一个指针数组，files_[i] 指向一个 vector，其中包含了 Level i 的所有 FileMetaData 指针。这是LSM-Tree结构最核心的表示。
- file_locations_: 一个从文件编号（file_number）到其位置（FileLocation，即层级和在层内数组的索引）的哈希表。这是一个为了快速查找而生成的索引，避免了遍历 files_。
- blob_files_: 存储了所有关联的 Blob 文件元数据，用于支持 BlobDB。
- num_levels_, num_non_empty_levels_: LSM-Tree的层级信息。
Compaction 决策相关:
- compaction_score_ 和 compaction_level_: 这两个 vector 存储了每个层级的压缩得分和对应的层级编号，并按得分高低排序。RocksDB通过它们来决定下一个应该在哪个层级执行压缩。
- files_by_compaction_pri_: 这是一个重要的优化。它并不直接存储 FileMetaData，而是存储 files_ 数组的索引。在每个层级内部，这些索引按照文件的压缩优先级（例如文件大小）排序。这使得挑选压缩文件时无需再次排序。
- next_file_to_compact_by_size_: 用于在某些压缩策略（如Leveled Compaction）中实现轮询（round-robin）选择起始文件，避免总是从同一位置开始压缩，有助于分摊写入放大。
- files_marked_for_compaction_, expired_ttl_files_, bottommost_files_marked_for_compaction_ 等：这些 autovector 存储了被识别为需要特殊处理的文件。例如，因为TTL过期、需要进行垃圾回收等原因而被标记出来，等待被压缩任务处理。
统计与状态:
- accumulated_* 系列成员：如 accumulated_raw_key_size_，这些是从SST文件的属性中累加得到的统计信息，用于各种估算，如平均value大小等。
- estimated_compaction_needed_bytes_: 估算还需要多少字节的数据需要被压缩才能达到目标大小，可用于监控和流控。
- finalized_: 一个布尔标记，非常重要。它指示该 VersionStorageInfo 对象是否已经完成了所有准备工作并且处于只读的最终状态。

关键成员函数与生命周期

VersionStorageInfo 的生命周期和其成员函数体现了“构建”和“使用”分离的模式。

构建阶段:
- 当一个新的 Version 被创建时（通常是基于前一个 Version 和一个 VersionEdit），一个新的 VersionStorageInfo 也会被创建。
- VersionBuilder 会调用 AddFile() 等函数，将 VersionEdit 中描述的文件增删变化应用到新的 VersionStorageInfo 实例上。
准备与最终化 (Finalization) 阶段:
- 在 VersionStorageInfo 被正式用于 Version 之前，必须调用 PrepareForVersionAppend()。这个函数会计算所有派生数据，例如：
  - GenerateFileIndexer(): 创建用于快速文件查找的 file_indexer_。
  - GenerateFileLocationIndex(): 填充 file_locations_ 哈希表。
  - GenerateLevelFilesBrief(): 生成一个更紧凑的文件元数据摘要，用于快速范围重叠判断。
  - UpdateFilesByCompactionPri(): 根据文件大小等信息填充 files_by_compaction_pri_。
- 完成准备后，调用 SetFinalized() 将 finalized_ 标志设为 true。此后，该对象被视为不可变。许多访问函数（如 NumLevelFiles）内部都有 assert(finalized_)，以确保不会访问一个尚未准备好的对象。
使用阶段:
- 压缩决策: ComputeCompactionScore() 是核心。它在DB互斥锁保护下被调用，遍历所有层级，根据配置的压缩策略计算得分，并填充 compaction_score_ 和 compaction_level_。它还会调用 ComputeFilesMarkedForCompaction 等辅助函数来识别需要特殊处理的文件。
- 文件查找: GetOverlappingInputs() 被压缩任务用来查找指定层级中与给定key范围重叠的SST文件，作为下一次压缩的输入。
- 元数据查询: GetFileMetaDataByNumber() 和 GetBlobFileMetaData() 等函数提供了高效的元数据访问接口，供读路径和其它内部逻辑使用。

这个生命周期模式（构建 -> 最终化 -> 使用）是一种优化，它将所有昂贵的计算（如排序、建立索引）都集中在 Version 创建时一次性完成，从而使得后续频繁的读操作和压缩决策过程更加高效。

总结

VersionStorageInfo 是 RocksDB MVCC 机制中一个精心设计的组件。它不是一个简单的数据结构，而是一个包含了复杂逻辑的状态机：

封装性: 它将所有与LSM-Tree物理存储结构相关的状态和逻辑（文件列表、压缩状态、统计数据）都封装在一起，与 Version 的逻辑视图接口解耦。
性能优化: 通过 finalized_ 状态和 PrepareForVersionAppend 机制，它将派生数据的计算提前进行，避免了在读路径或压缩决策时的重复计算，提升了系统性能。
压缩的核心: 它是压缩选择器（Compaction Picker）的主要工作对象。压缩选择器通过分析 VersionStorageInfo 中的数据来决定何时、何地以及如何进行压缩。

理解 VersionStorageInfo 的内部结构和工作流程，对于深入理解 RocksDB 的压缩机制、空间放大控制以及性能调优至关重要。

查看全文

http://www.lryc.cn/news/604048.html