RocksDB/SST 过滤器

先排除不含目标键的 SST

RocksDB 可为 SST 配置 Bloom filter，在读取数据块前排除不可能包含目标键的文件，减少无效查询工作。

v9.7.3检索与计算核验 2026-10-08

工程问题#

LSM 数据分散在多个文件和层级；查询不存在的键时，逐个检查候选文件可能产生许多无效读取。

实际实现#

建表时根据键构造位数组；查询计算哈希并检查对应位。返回否可跳过该候选，返回可能存在仍须读取并核实。

处理流程#

创建 SST 时收集键并构建过滤器。
查询键计算哈希及探测位置。
过滤器返回否时跳过候选数据。
返回可能存在时继续真实键查找。

源码片段#

固定版本 · 原文摘录

table/block_based/filter_policy.ccv9.7.3 · L589–L596

查看原文件

589  bool MayMatch(const Slice& key) override {590    uint64_t h = GetSliceHash64(key);591    uint32_t byte_offset;592    FastLocalBloomImpl::PrepareHash(Lower32of64(h), len_bytes_, data_,593                                    /*out*/ &byte_offset);594    return FastLocalBloomImpl::HashMayMatchPrepared(Upper32of64(h), num_probes_,595                                                    data_ + byte_offset);596  }

FastLocalBloomBitsReader::MayMatch

先对键计算 64 位哈希，用低 32 位确定局部位区，再用高 32 位及 num_probes 检查探测位。返回 true 只是可能命中；false 的排除作用须结合完整键或前缀配置及表读取路径理解。

CPPGPLv2 / Apache-2.0 双许可；另有 LevelDB BSD-3-Clause 通知（文件头及许可文件已核验；未提供完整 SPDX 表达式）

完整单键 MayMatch 方法；位测试细节位于 FastLocalBloomImpl，过滤器创建和是否启用由外部选项决定。

收益与取舍#

工程分析

带来的收益

对未命中查询减少无效数据块读取。
每键位数可用于调整空间与误报率。

付出的代价

会误报存在，不能代替实际键查找。
构建、缓存过滤器需要内存和 CPU。

可比较的选择

不配置过滤器节省过滤器构建与缓存成本，但未命中查询可能访问更多候选文件。

版本与适用范围#

基线 9.7.3，适用于正确配置的 SST 过滤器；完整键与前缀过滤用途不同，无假阴性前提是构建、比较和查询语义一致。

参考来源#

源码、官方文档与原始论文

RocksDB 9.7.3 Bloom 实现

table/block_based/filter_policy.cc · NewBloomFilterPolicy; FastLocalBloomBitsReader::MayMatch

源码9.7.3

RocksDB 官方 Bloom filter 说明

wiki/RocksDB-Bloom-Filter · NewBloomFilterPolicy

官方文档官方 Wiki，2026-10-08 核验