RocksDB 读路径（四）：MemTable 查找全流程与源码级实现剖析

数据库KV存储嵌入式数据库存储【免费下载链接】rocksdbA library that provides an embeddable, persistent key-value store for fast storage.项目地址https://gitcode.com/gh_mirrors/ro/rocksdb点击查看免费下载导读本文聚焦 RocksDB 点查询读路径中至关重要的第一站——MemTable内存表查找系统讲解MemTable::Get()的多阶段流水线、SaveValue()回调的类型分派、跨不可变 MemTable 的搜索策略以及 MemTable Bloom 过滤器的配置与取舍。读完本文你将掌握 memtable 点查询的完整调用链从空检查、Range Tombstone 检查、Bloom 过滤到 skiplist 定位理解 merge 操作如何在内存层累积并能依据 include/rocksdb/advanced_options.h 中的选项参数正确调优 memtable 级别的读路径。一、为什么要研究 MemTable 查找在 RocksDB 的 LSM 树结构中一次点查询Get会按最新数据优先的顺序逐层搜索活跃/不可变 MemTable → SST 文件L0 → L1 → …。MemTable 是数据写入后最先落地、也最可能命中数据的一层因此它的查找效率直接决定读路径的延迟下限。本文对应的核心实现位于db/memtable.ccMemTable::Get()、GetFromTable()与静态回调SaveValue()db/memtable.hMemTable/ReadOnlyMemTable类声明db/memtable_list.ccMemTableListVersion::Get()、GetFromList()跨 memtable 搜索db/memtable_list.hmemtable 列表与版本管理下面先给出整体脉络再逐一深入每个环节。二、MemTable::Get() 多阶段查找流水线MemTable::Get()db/memtable.cc#L1576对每个查找 key 执行一个多阶段流水线。其完整签名如下bool MemTable::Get(const LookupKey key, std::string* value, PinnableWideColumns* columns, std::string* timestamp, Status* s, MergeContext* merge_context, SequenceNumber* max_covering_tombstone_seq, SequenceNumber* seq, const ReadOptions read_opts, bool immutable_memtable, ReadCallback* callback, bool* is_blob_index, bool do_merge, const BlobFetcher* blob_fetcher);各输出参数的作用参数作用value/columns/timestamp返回值普通值 / 宽列实体 / 时间戳merge_context累积 merge 操作数的上下文max_covering_tombstone_seq覆盖该 key 的 range tombstone 最高 seq向下层传递seq找到的 key 对应序列号供上层DBImpl记录s返回状态NotFound / MergeInProgress / OK 等is_blob_index标记命中的是否为 blob 索引Step 1空表快速返回// db/memtable.cc#L1585 if (IsEmpty()) { // Avoiding recording stats for speed. return false; }IsEmpty()通过first_seqno_ 0判断 memtable 是否完全没有条目从源码注释可知 memtable 的第一个 seq 从 1 开始0 表示空。空表直接返回 false未找到且刻意跳过统计打点以避免热路径开销。Step 2Range Tombstone 覆盖检查// db/memtable.cc#L1616-L1631 std::unique_ptrFragmentedRangeTombstoneIterator range_del_iter( NewRangeTombstoneIterator(read_opts, range_del_read_seq, immutable_memtable)); if (range_del_iter ! nullptr) { SequenceNumber covering_seq range_del_iter-MaxCoveringTombstoneSeqnum(key.user_key()); if (covering_seq *max_covering_tombstone_seq) { *max_covering_tombstone_seq covering_seq; ... } }这一阶段不会立即判定删除而是先创建范围删除Range Tombstone迭代器查询覆盖该 key 的最高 tombstone 序列号将其记录到max_covering_tombstone_seq供后续SaveValue()中与条目的 seq 比较。也就是说range tombstone 与点删除point tombstone在 memtable 层通过序列号比较来判定谁生效。值得注意的细节db/memtable.cc#L1592-L1615当带有ReadCallback如带 snapshot 的读取或 secondary 读取时metadata 读取会加宽读取 seq 去发现更新的 range tombstone但常规的掩码迭代器仍停留在用户 snapshot seq 上从而保证这类 tombstone 只记录元数据、不会遮蔽 snapshot 可见的值。Step 3Bloom 过滤器检查如果 memtable 启用了 bloom filter则在此拦截肯定不存在的查找// db/memtable.cc#L1638-L1652 if (bloom_filter_) { // when both memtable_whole_key_filtering and prefix_extractor_ are set, // only do whole key filtering for Get() to save CPU if (moptions_.memtable_whole_key_filtering) { may_contain bloom_filter_-MayContain(user_key_without_ts); bloom_checked true; } else { assert(prefix_extractor_); if (prefix_extractor_-InDomain(user_key_without_ts)) { may_contain bloom_filter_-MayContain( prefix_extractor_-Transform(user_key_without_ts)); bloom_checked true; } } } if (bloom_filter_ !may_contain) { // iter is null if prefix bloom says the key does not exist PERF_COUNTER_ADD(bloom_memtable_miss_count, 1); *seq kMaxSequenceNumber; } else { if (bloom_checked) { PERF_COUNTER_ADD(bloom_memtable_hit_count, 1); } GetFromTable(...); }whole-key 模式用去掉时间戳后的完整 user key 做MayContain前缀模式先用prefix_extractor提取前缀再对前缀做MayContain当memtable_whole_key_filtering与prefix_extractor同时设置时Get()只使用 whole-key 过滤以节省 CPU——这是源码中明确注释并实现的取舍db/memtable.cc#L1639-L1640Bloom 判肯定不存在时直接跳过整个 skiplist 搜索返回 false并累加bloom_memtable_miss_count性能计数命中可能包含则累加bloom_memtable_hit_count并进入 skiplist 搜索。这两个计数可在PERF_CONTEXT/ 统计中观察 memtable bloom 的实际拦截效果。Step 4Skiplist 搜索通过GetFromTable()db/memtable.cc#L1680调用MemTableRep::Get()。skiplist 会定位到第一个匹配 user key 的条目并对每个匹配条目调用SaveValue()回调// db/memtable.cc#L1712-L1724 if (!moptions_.paranoid_memory_checks !moptions_.memtable_verify_per_key_checksum_on_seek) { table_-Get(key, saver, SaveValue); } else { Status check_s table_-GetAndValidate( key, saver, SaveValue, moptions_.allow_data_in_errors, moptions_.paranoid_memory_checks, key_validation_callback_); ... }这里可以看到两个与数据保护相关的选项paranoid_memory_checks与memtable_verify_per_key_checksum_on_seek。当开启时会走GetAndValidate()对每个条目做逐 key 校验和验证发现损坏即向上返回Status::Corruption并中止 LSM 下层的继续搜索found_final_value true。Saver结构db/memtable.cc#L1687-L1710携带了查找所需的一切上下文查找 key、输出缓冲、merge 上下文、max_covering_tombstone_seq、统计、时钟、ReadCallback、是否 blob 索引、protection_bytes_per_key等是SaveValue与调用方之间的参数打包。三、SaveValue() 回调逐条处理 skiplist 条目SaveValue()db/memtable.cc#L1321是静态回调其核心逻辑可分解为以下几个步骤。Step 1解析条目编码memtable 条目按varint key 长度 key 8 字节 tagseq type 打包 varint value 长度 value编码。SaveValue首先解析出key_length进而切出user_key_slicekey 去掉尾部 8 字节 tag// db/memtable.cc#L1336-L1339 uint32_t key_length 0; const char* key_ptr GetVarint32Ptr(entry, entry 5, key_length); assert(key_length 8); Slice user_key_slice Slice(key_ptr, key_length - 8);Step 2User key 匹配// db/memtable.cc#L1347 if (user_comparator-EqualWithoutTimestamp(user_key_slice, s-key-user_key())) {通过EqualWithoutTimestamp忽略时间戳比较条目 user key 与查找 key。不匹配则返回 true 继续迭代下一条目匹配则进入后续处理。Step 3Snapshot 可见性检查// db/memtable.cc#L1377-L1380 // If the value is not in the snapshot, skip it if (!s-CheckCallback(seq)) { return true; // to continue to the next seq }CheckCallback(seq)由ReadCallback如 snapshot 检查器判定该序列号的条目对当前读取是否可见不可见则跳过继续迭代。这保证了带 snapshot 的读取只会看到 snapshot 之前提交的数据。Step 4Range Tombstone 集成关键合并点// db/memtable.cc#L1411-L1417 if ((type kTypeValue || type kTypeMerge || type kTypeBlobIndex || type kTypeWideColumnEntity || type kTypeDeletion || type kTypeSingleDeletion || type kTypeDeletionWithTimestamp || type kTypeValuePreferredSeqno) max_covering_tombstone_seq seq) { type kTypeRangeDeletion; }这是整个 memtable 查找中最精妙的一步当max_covering_tombstone_seq seq即存在一个序列号更高的 range tombstone 覆盖了当前条目时将任何类型的条目改写为kTypeRangeDeletion使其按删除处理。这样 range tombstone 无需物理删除 skiplist 中的条目而是在读取时通过 seq 比较逻辑上生效保持了 memtable 的写入效率。注意seq 记录逻辑db/memtable.cc#L1382-L1396中若s-seq kMaxSequenceNumber首次记录且s-seq max_covering_tombstone_seq则保留条目自身 seq否则对齐到max_covering_tombstone_seq。同时带时间戳列族会在此同步更新timestamp输出。Step 5按值类型分派处理完上述通用逻辑后switch (type)根据值类型分派db/memtable.cc#L1418-L1569类型动作返回值语义kTypeValue返回 value查找完成found_final_value true返回 false 停止迭代kTypeValuePreferredSeqno解析打包值ParsePackedValueForValue后返回查找完成同上kTypeDeletion/kTypeDeletionWithTimestamp/kTypeSingleDeletion/kTypeRangeDeletion调用HandleTypeDeletion返回 NotFound同上kTypeMerge操作数压入MergeContext若 merge 未终结则继续迭代HandleTypeMerge决定found_final_value未终结时返回 true 继续kTypeBlobIndex返回 blob 引用原始字节后续由 BlobDB 层解析真实值found_final_value true*is_blob_index truekTypeWideColumnEntity返回宽列实体或默认列值found_final_value truedefault返回Status::Corruption未识别的值类型中止几个值得展开的实现细节kTypeBlobIndexdb/memtable.cc#L1419-L1457要求is_blob_index输出指针存在否则返回NotSupported。若调用方是栈式 BlobDB则把序列化后的 blob 索引字节直接交给上层由 BlobDB 负责后续检索真实 blob 值。kTypeWideColumnEntitydb/memtable.cc#L1473-L1535区分三种情形——!do_mergeGetMergeOperands保留原始操作数、merge_in_progress与宽列 base value 合并、普通读取提取默认列的值。宽列是 RocksDB 宽列 API 在 memtable 层的落点。kTypeValue走ReadOnlyMemTable::HandleTypeValue完成merge_in_progress时用TimedFullMerge合并 base value 与已累积操作数否则直接返回。校验和增强db/memtable.cc#L1356-L1365当protection_bytes_per_key 0时SaveValue会先调用VerifyEntryChecksum验证条目完整性损坏则报 Corruption 并停止搜索——对应memtable_protection_bytes_per_key选项见 include/rocksdb/advanced_options.h。四、MemTable 内的 Merge 处理当在 skiplist 中遇到kTypeMerge条目时db/memtable.cc#L1547-L1555case kTypeMerge: { Slice v GetLengthPrefixedSlice(key_ptr key_length); *(s-merge_in_progress) true; *(s-found_final_value) ReadOnlyMemTable::HandleTypeMerge( s-key-user_key(), v, s-inplace_update_support false, s-do_merge, merge_context, s-merge_operator, s-clock, s-statistics, s-logger, s-status, s-value, s-columns); return !*(s-found_final_value); }merge 操作数被压入MergeContext搜索继续向下进行直到遇到下列三种终止条件之一找到 base valuekTypeValue触发TimedFullMerge()用 base value 全部操作数执行合并算子遇到删除触发无 base value 的TimedFullMerge()把删除视为base 不存在memtable 搜索结束仍未终结将merge_in_progress状态继续传给下一层不可变 memtable 或 SST 文件由外层继续累积操作数。max_successive_merges/strict_max_successive_merges见 include/rocksdb/advanced_options.h等选项限制单次合并的最大连续操作数可在一定程度上控制 merge 路径的开销。从 db/memtable.cc#L1669-L1675 可以看到若未找到最终值且 merge 在进行中Get()会返回Status::MergeInProgress()由上层决定继续还是中止。五、不可变 MemTable 搜索MemTableListVersion::Get()当活跃 memtable 未命中或命中 merge 需继续累积时查询进入不可变 memtable 列表。MemTableListVersion::Get()db/memtable_list.cc#L178委托给GetFromList()db/memtable_list.cc#L230遍历memlist_。// db/memtable_list.cc#L239-L267 for (auto memtable : *list) { assert(memtable-IsFragmentedRangeTombstonesConstructed()); SequenceNumber current_seq kMaxSequenceNumber; bool done memtable-Get(key, value, columns, timestamp, s, merge_context, max_covering_tombstone_seq, current_seq, read_opts, true /* immutable_memtable */, callback, is_blob_index, true /* do_merge */, blob_fetcher); if (*seq kMaxSequenceNumber) { // 记录跨 memtable 找到的第一个序列号最新变更 *seq current_seq; } if (done) { return true; // 找到最终结果提前终止 } if (!s-ok() !s-IsMergeInProgress() !s-IsNotFound()) { return false; // 遇到真实错误停止 } }核心搜索策略对每个不可变 memtable 调用与活跃 memtable 完全相同的MemTable::Get()SaveValue()逻辑新到旧顺序遍历memlist_通过push_frontdb/memtable_list.cc#L112维护最新在前的顺序——新 flush 产生的不可变 memtable 总是插入链表头部早停一旦done true找到 Put 或 Delete 等最终结果立即返回这正是最新版本先被找到带来的性能收益merge 继续若merge_in_progress继续遍历下一个更旧的memtable 累积操作数seq 追踪仅记录跨所有 memtable 找到的第一个最新序列号到*seq供上层做版本/缓存相关处理。此外db/memtable_list.cc#L219 的GetFromHistory()与 db/memtable_list.cc#L203 的GetMergeOperands()是另外两条变体路径前者针对 memtable 历史列表不携带ReadCallback后者专门收集 merge 操作数do_merge false。还有MultiGet()db/memtable_list.cc#L191对一批 key 做批量查找命中后从 range 中移除全部命中即提前返回。六、MemTable Bloom Filter配置、构建与取舍memtable 级 bloom filter 与 SST 文件 bloom filter 是两套独立机制理解其差异有助于正确调优维度MemTable BloomSST Bloom配置项memtable_prefix_bloom_size_ratio、memtable_whole_key_filteringblock_based_table_factory下的 bloom 相关参数构建方式随条目插入增量构建db/memtable.cc#L246 的bloom_filter_.reset(...)写入 SST 时静态生成持久化不持久化每个 memtable 重建随 SST 文件持久化前缀来源prefix_extractor相同配置项与取值范围两个配置项定义在 include/rocksdb/advanced_options.h#L422-L445// Should really be called memtable_bloom_size_ratio. Enables a dynamic // Bloom filter in memtable to optimize many queries that must go beyond // the memtable. The size in bytes of the filter is // write_buffer_size * memtable_prefix_bloom_size_ratio. // * If prefix_extractor is set, the filter includes prefixes. // * If memtable_whole_key_filtering, the filter includes whole keys. // * If both, the filter includes both. // * If neither, the feature is disabled. // // If this value is larger than 0.25, it is sanitized to 0.25. // // Default: 0 (disabled) // // Dynamically changeable through SetOptions() API double memtable_prefix_bloom_size_ratio 0.0; // Enable whole key bloom filter in memtable. Note this will only take effect // if memtable_prefix_bloom_size_ratio is not 0. Enabling whole key filtering // can potentially reduce CPU usage for point-look-ups. // // Default: false (disabled) // // Dynamically changeable through SetOptions() API bool memtable_whole_key_filtering false;要点memtable_prefix_bloom_size_ratio占write_buffer_size的比例默认0.0关闭超过 0.25 会被 sanitize 到 0.25。filter 的 bit 数在 db/memtable.cc#L117-L121 中计算write_buffer_size * ratio * 8字节转 bitmemtable_whole_key_filtering默认false仅当memtable_prefix_bloom_size_ratio ! 0时才生效组合规则只有 prefix_extractor、只有 whole-key、两者都有filter 同时包含前缀和整键、两者都没有功能关闭两个选项都支持运行时通过SetOptions()动态修改使用时需要注意prefix_extractor需在 DB 生命周期内保持一致memtable bloom 不持久化、每次重建prefix extractor 变更会导致重建后的 filter 无法匹配旧前缀语义。命中与误报的工程语义源码 db/memtable.cc#L1654-L1665 明确体现了 bloom 的语义保证误报false positivebloom 说可能存在但实际不存在 → 只会引发一次多余的 skiplist 搜索结果仍然正确返回 NotFound漏报false negative正确实现的 bloom filter不会出现——只要 bloom 说不存在就必然不存在因此可以安全跳过整个 skiplist 搜索。从工程上看这正是 memtable bloom 的核心价值对于大量在 memtable 中 miss 的点查询key 已在更早 flush 的 SST 中跳过 skiplist 搜索可以省掉一次完整的内存遍历同时由于它不持久化、按 memtable 增量构建非常适合 write_buffer_size 较大、miss 率高的场景。开启memtable_whole_key_filtering还能进一步节省Get()路径上的 CPU省去前缀提取与比较。七、读取路径全景回顾把本系列docs/components/read_flow/的视角串起来memtable 查找在整条读路径中的位置是MemTable 查找本文空检查 → range tombstone 检查 → bloom 过滤 → skiplist 搜索 →SaveValue()类型分派若 memtable 层未找到最终值尤其 merge 未终结MergeInProgress状态沿MemTableListVersion::GetFromList()→ 上层DBImpl::GetImpl一路传递最终落到 SST 文件层继续搜索涉及 block cache、index/filter 等机制。理解这一层的关键在于memtable 查找的最终目的不是读磁盘而是尽量在内存中以最低成本给出确定答案命中 / 删除 / merge 状态其中 bloom 过滤负责拦截肯定不存在的查找range tombstone 通过 seq 比较实现逻辑删除merge 通过跨层累积操作数保证合并语义的一致性。八、进一步阅读db/memtable.ccMemTable 完整实现写入Add()、读取Get()/MultiGet()、bloom 构建db/memtable_list.cc不可变 memtable 列表与版本化搜索include/rocksdb/advanced_options.hmemtable_prefix_bloom_size_ratio、memtable_whole_key_filtering等全部 memtable 相关选项db/db_impl/db_impl.ccGetImpl()中跨 memtable/SST 的完整调度逻辑本系列其他文档主题测试参考db/memtable_list_test.cc、db/db_basic_test.cc 覆盖了 memtable 查找的可见性、删除与 merge 语义赞分享数据库KV存储嵌入式数据库存储【免费下载链接】rocksdbA library that provides an embeddable, persistent key-value store for fast storage.项目地址https://gitcode.com/gh_mirrors/ro/rocksdb点击查看免费下载相关推荐Pixel Launcher Extended终极个性化Android启动器完全指南Pixel Launcher Extended终极个性化Android启动器完全指南 Pixel Launcher Extended是一款由TeamFiles移动开发RocksDB 点查核心链路解析从 Version::Get() 到 SST 文件查找的完整流程RocksDB 点查核心链路解析从 Version::Get 到 SST 文件查找的完整流程 导读 本文深入剖析 RocksDB 读取路径Read Path数据库KV存储嵌入式数据库存储WinUI XAML 资源解析机制深度剖析{StaticResource} 与 {ThemeResource} 的查找、优先级与源码实现WinUI XAML 资源解析机制深度剖析{StaticResource} 与 {ThemeResource} 的查找、优先级与源码实现 本文是 WinUI前端UI组件桌面应用创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考