RocksDB Full Filter Block全新布隆过滤器格式的原理、实现与使用指南【免费下载链接】rocksdbA library that provides an embeddable, persistent key-value store for fast storage.项目地址: https://gitcode.com/gh_mirrors/ro/rocksdb本篇技术指南围绕 RocksDB 官方博客《New Bloom Filter Format》所介绍的full filter全量过滤器展开讲解这种为 SST 文件内全部键生成单一大型布隆过滤器的新格式如何替代旧的 block-based filter简化查询流程并提升内存场景下的点查性能。阅读本文后你将掌握 full filter 与旧格式在数据结构、查询工作流上的本质差异学会通过BlockBasedTableOptions::filter_policy在 RocksDB 中启用与定制布隆过滤器并了解其构建期内存开销、partitioned filter 等后续演进对应源码见 filter_policy.h、full_filter_block.cc。引言为什么需要新的布隆过滤器格式在 2014-09-12 官方博客 中RocksDB 团队宣布为 block based table 引入一种名为full filter block的新布隆过滤器格式。其核心思想是为整个 SST 文件生成一个覆盖该文件中所有键的单一大型过滤器从而避免大量不必要的内存查找。按照原文档的描述在数据全部驻留内存文件存放于 tmpfs/ramfs的场景下这一改动能为键查询key query带来约40% 的性能提升。需要说明的是这一数字来自该场景下的基准测试结论具体提升幅度会随负载特征、数据分布和硬件环境而不同。什么是布隆过滤器布隆过滤器Bloom Filter本质上是一个为键集合生成的位数组它可以回答某个任意键是否可能存在于该集合中查询结果为否该键一定不存在查询结果为是该键可能存在存在一定误判率 false positive。在 RocksDB 中每个 SST 文件都会生成对应的布隆过滤器。当执行点查point lookup时流程大致如下先访问该 SST 文件的布隆过滤器块若过滤器判定键可能存在才进入数据块data block内真正查找若过滤器判定键一定不存在则直接返回跳过磁盘/内存中的数据块访问。因此布隆过滤器能大幅加速点查操作——尤其是对不存在的键往往可以在不触碰数据块的情况下直接判定不存在。相关的基础设施定义见 filter_policy.h 中的注释过滤器让每次DB::Get()的磁盘寻道从多次降到单次甚至零次。原始布隆过滤器格式block-based filter在 full filter 出现之前RocksDB 的布隆过滤器为 SST 文件中每一个数据块单独生成一个过滤器。这带来两个问题结构复杂过滤器块内部需要维护数据块 ID → 过滤器偏移的映射关系内存访问不连续一次查询需要多次跳转产生大量非相邻non-adjacent内存查找在内存驻留场景下尤为昂贵。原文档给出了旧格式下过滤器检查的完整工作流共三步给定目标键先访问index block得到该键可能所在的数据块 ID用数据块 ID 访问filter block取得对应过滤器的偏移量offset of filter根据偏移量跳转到实际过滤器执行布隆检查。也就是说旧格式一次查询至少需要经过 index block 与 filter block 两级间接寻址且 filter block 内部还有地址跳转。新格式Full Filter Block新格式不再按数据块拆分而是为SST 文件中的全部键生成一个单一过滤器命名为full filter。其数据结构极其简单就是一个大过滤器[ full filter ]对应地查询工作流被大幅简化给定目标键直接访问 filter block并执行过滤器检查。具体而言新格式不再检查 index blockfilter block内部也没有任何地址跳转。一次点查从索引 → 过滤器定位 → 过滤器检查的三级流水变为过滤器检查单步这正是内存驻留场景下获得显著加速的关键原因。值得注意的是虽然它是一个大过滤器但过滤器总大小与旧格式相同——布隆过滤器的大小只取决于键的数量与每键位数bits per key与是否按块拆分无关。源码中的数据结构印证从当前仓库源码看full filter 的实现完全符合原文档描述full_filter_block.h 中明确注释了 full filter block 的格式SST 文件中所有键的完整过滤器full filter for all keys in sst file过滤器末尾附带布隆过滤器使用的哈希函数个数num_probesFullFilterBlockBuilder负责在构建期收集全部键见 full_filter_block.cc 的Add调用filter_bits_builder_-AddKey/AddKeyAndAlt逐键加入并通过Finish一次性产出最终过滤器查询侧由FullFilterBlockReader承担其KeyMayMatch/PrefixMayMatch/MayMatchfull_filter_block.cc直接对整块过滤器执行检查命中与否分别累加bloom_sst_hit_count/bloom_sst_miss_count性能计数器可用PerfContext观测。一个已知的代价构建期内存开销原文档明确指出新格式的一个缺点构建 SST 文件时内存消耗更高。旧格式只需为每个小块缓冲少量键构建期内存占用低full filter 需要在生成过滤器前缓冲全部键的哈希当 SST 文件变大时这部分内存随之线性增长。这一代价在后续版本中催生了 partitioned filter见下文后续演进其目的正是在保留 full filter 查询优势的同时把构建期内存与过滤器块的体积控制在可预测范围内。HISTORY.md 中也有相应提示若 full filter 创建期临时内存占用成为问题可考虑使用 partitioned filters、更小的 SST 文件或设置reserve_table_builder_memorytrue见 HISTORY.md 7.0 发布记录。用法与定制原文档将详细用法指向 RocksDB 布隆过滤器文档。结合当前仓库源码我们给出可直接落地的完整说明。启用布隆过滤器FilterPolicy 与 filter_policy 选项布隆过滤器通过BlockBasedTableOptions::filter_policy启用。该字段默认值为nullptr即默认不生成过滤器注释见 table.h。使用内置布隆过滤器的最简 C 写法如下#include rocksdb/filter_policy.h #include rocksdb/table.h rocksdb::BlockBasedTableOptions table_options; // 每键约 9.9 bit对应约 1% 的假阳性率 table_options.filter_policy.reset( rocksdb::NewBloomFilterPolicy(9.9)); rocksdb::Options options; options.table_factory.reset( rocksdb::NewBlockBasedTableFactory(table_options));要点说明bits_per_key每键位数决定过滤器大小与假阳性率的平衡。官方建议取值9.9约对应1% 假阳性率见 filter_policy.h。小数位建议不超过三位如6.667取值边界bits_per_key 0.5会被归约为 0表示不生成过滤器0.5 ≤ bits_per_key 1.0会被归约为 1.0约 62% 假阳性率见 filter_policy.h自定义比较器注意若你使用了忽略键中部分字节的自定义 comparator则必须同时提供忽略相同部分的FilterPolicy否则过滤结果会不正确见 filter_policy.h。在 OPTIONS 文件 / SetOptions 中配置除 C API 外过滤器策略也可通过配置字符串指定。FilterPolicy::CreateFromString支持bloomfilter:[bits_per_key]形式例如bloomfilter:4等价于NewBloomFilterPolicy(4)见 filter_policy.h。在 OPTIONS 文件中可写作[TableOptions/BlockBasedTable] filter_policybloomfilter:10定制自己的 FilterPolicyFilterPolicy是一个可定制Customizable的抽象基类见 filter_policy.h用户可以通过继承它实现自定义过滤器策略GetBuilderWithContext(const FilterBuildingContext)在构建期返回一个FilterBitsBuilder用于向过滤器添加键可通过FilterBuildingContext包含压缩风格、LSM 层级数、列族名、建表原因等上下文见 filter_policy.h决定在不同场景下委托给哪个内置策略例如低层用 Ribbon、高层用 BloomGetFilterBitsReader(const Slice)在读取期解析磁盘上的过滤器内容CompatibilityName()返回用于识别磁盘过滤器是否可读的兼容族名内置 Bloom 与 Ribbon 共享一个族名可互读彼此的过滤器见 filter_policy.h。版本与兼容性提示当前仓库中NewBloomFilterPolicy的第二个参数use_block_based_builder已被标记为忽略自 RocksDB 7.0 起旧的 block-based filter 在公共 API 中已不可用启用它会静默转为 full filter见 filter_policy.h。HISTORY.md 也确认 7.0 移除了 block-based filter 的写入支持并在后续移除了读取支持旧库如需良好读性能建议做一次 full compaction见 HISTORY.md。深入原理从查询路径到性能计数器查询路径对比步骤旧格式block-based filter新格式full filter1访问 index block取数据块 ID直接访问 filter block2用数据块 ID 查 filter block取过滤器偏移直接对整块过滤器执行检查3跳转到实际过滤器执行检查——内存访问多次非相邻跳转单次、连续新格式同时支持整键过滤whole key filtering与前缀过滤prefix filteringAdd时若配置了前缀提取器prefix_extractor且whole_key_filtering开启则同时加入整键与前缀AddKeyAndAlt否则仅加入前缀见 full_filter_block.cc。查询侧KeyMayMatch/PrefixMayMatch分别对应两类检查。可观测性PerfContext 统计每次过滤器判定都会更新PerfContext中的bloom_sst_hit_count判定可能存在与bloom_sst_miss_count判定不存在计数器见 full_filter_block.cc。在启用了布隆过滤器的库上可通过db-GetPerfContext()对比两类计数评估过滤器命中率与误判率是否符合预期。后续演进与最佳实践full filter 是后续过滤器架构的基础当前仓库中可看到三条主要演进方向Partitioned filters分区过滤器当 SST 文件很大时单个 full filter 会占用大量块缓存并带来构建期内存压力。BlockBasedTableOptions::partition_filters默认false需配合kTwoLevelIndexSearch将过滤器切分为多个分区各自独立进块缓存见 table.h实现见 partitioned_filter_block.cc 的PartitionedFilterBlockBuilder按partition_size估算每分区键数keys_per_partition_并切割。原文档所述大过滤器的构建内存问题正是这类方案要解决的场景。Ribbon filter布隆过滤器的空间更优替代NewRibbonFilterPolicy(bloom_equivalent_bits_per_key, bloom_before_level)在同等假阳性率下约节省30% 空间代价是约 3–4 倍的构建 CPU 时间与 3 倍临时空间可通过bloom_before_level实现高层 Bloom 低层 Ribbon的混合配置见 filter_policy.h。格式版本与内存优化新布隆过滤器实现默认要求format_version 5当前仓库默认format_version 7见 table.hoptimize_filters_for_memory默认true在启用malloc_usable_size时通过调整过滤器尺寸减少内存内部碎片以 Jemalloc 为例约可节省 10% 过滤器内存占用见 table.h。实践建议点查密集、且能容忍约 1% 误判的应用直接使用NewBloomFilterPolicy(9.9)作为起点若 SST 文件体积大、块缓存紧张或构建内存受限评估partition_filters true关注 LSM 低层大而长命文件的空间占用时可考虑 Ribbon filter 的混合配置升级/降级过程中注意过滤器格式版本兼容性Ribbon 需 RocksDB ≥ 6.15见 filter_policy.h。总结Full filter block 通过一个 SST 文件一个整体布隆过滤器的设计将点查路径从索引 → 过滤器定位 → 过滤器检查压缩为直接检查消除了旧 block-based filter 的复杂结构与非相邻内存访问是 RocksDB 在内存驻留场景下提升点查性能的关键优化之一其代价是构建期需要缓冲全部键哈希、内存占用随 SST 文件增大而增长。理解这一设计是正确配置filter_policy、评估 partitioned filter 与 Ribbon filter 等现代演进方案的前提。【免费下载链接】rocksdbA library that provides an embeddable, persistent key-value store for fast storage.项目地址: https://gitcode.com/gh_mirrors/ro/rocksdb创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 RocksDB Full Filter Block：全新布隆过滤器格式的原理、实现与使用指南
RocksDB Full Filter Block全新布隆过滤器格式的原理、实现与使用指南【免费下载链接】rocksdbA library that provides an embeddable, persistent key-value store for fast storage.项目地址: https://gitcode.com/gh_mirrors/ro/rocksdb本篇技术指南围绕 RocksDB 官方博客《New Bloom Filter Format》所介绍的full filter全量过滤器展开讲解这种为 SST 文件内全部键生成单一大型布隆过滤器的新格式如何替代旧的 block-based filter简化查询流程并提升内存场景下的点查性能。阅读本文后你将掌握 full filter 与旧格式在数据结构、查询工作流上的本质差异学会通过BlockBasedTableOptions::filter_policy在 RocksDB 中启用与定制布隆过滤器并了解其构建期内存开销、partitioned filter 等后续演进对应源码见 filter_policy.h、full_filter_block.cc。引言为什么需要新的布隆过滤器格式在 2014-09-12 官方博客 中RocksDB 团队宣布为 block based table 引入一种名为full filter block的新布隆过滤器格式。其核心思想是为整个 SST 文件生成一个覆盖该文件中所有键的单一大型过滤器从而避免大量不必要的内存查找。按照原文档的描述在数据全部驻留内存文件存放于 tmpfs/ramfs的场景下这一改动能为键查询key query带来约40% 的性能提升。需要说明的是这一数字来自该场景下的基准测试结论具体提升幅度会随负载特征、数据分布和硬件环境而不同。什么是布隆过滤器布隆过滤器Bloom Filter本质上是一个为键集合生成的位数组它可以回答某个任意键是否可能存在于该集合中查询结果为否该键一定不存在查询结果为是该键可能存在存在一定误判率 false positive。在 RocksDB 中每个 SST 文件都会生成对应的布隆过滤器。当执行点查point lookup时流程大致如下先访问该 SST 文件的布隆过滤器块若过滤器判定键可能存在才进入数据块data block内真正查找若过滤器判定键一定不存在则直接返回跳过磁盘/内存中的数据块访问。因此布隆过滤器能大幅加速点查操作——尤其是对不存在的键往往可以在不触碰数据块的情况下直接判定不存在。相关的基础设施定义见 filter_policy.h 中的注释过滤器让每次DB::Get()的磁盘寻道从多次降到单次甚至零次。原始布隆过滤器格式block-based filter在 full filter 出现之前RocksDB 的布隆过滤器为 SST 文件中每一个数据块单独生成一个过滤器。这带来两个问题结构复杂过滤器块内部需要维护数据块 ID → 过滤器偏移的映射关系内存访问不连续一次查询需要多次跳转产生大量非相邻non-adjacent内存查找在内存驻留场景下尤为昂贵。原文档给出了旧格式下过滤器检查的完整工作流共三步给定目标键先访问index block得到该键可能所在的数据块 ID用数据块 ID 访问filter block取得对应过滤器的偏移量offset of filter根据偏移量跳转到实际过滤器执行布隆检查。也就是说旧格式一次查询至少需要经过 index block 与 filter block 两级间接寻址且 filter block 内部还有地址跳转。新格式Full Filter Block新格式不再按数据块拆分而是为SST 文件中的全部键生成一个单一过滤器命名为full filter。其数据结构极其简单就是一个大过滤器[ full filter ]对应地查询工作流被大幅简化给定目标键直接访问 filter block并执行过滤器检查。具体而言新格式不再检查 index blockfilter block内部也没有任何地址跳转。一次点查从索引 → 过滤器定位 → 过滤器检查的三级流水变为过滤器检查单步这正是内存驻留场景下获得显著加速的关键原因。值得注意的是虽然它是一个大过滤器但过滤器总大小与旧格式相同——布隆过滤器的大小只取决于键的数量与每键位数bits per key与是否按块拆分无关。源码中的数据结构印证从当前仓库源码看full filter 的实现完全符合原文档描述full_filter_block.h 中明确注释了 full filter block 的格式SST 文件中所有键的完整过滤器full filter for all keys in sst file过滤器末尾附带布隆过滤器使用的哈希函数个数num_probesFullFilterBlockBuilder负责在构建期收集全部键见 full_filter_block.cc 的Add调用filter_bits_builder_-AddKey/AddKeyAndAlt逐键加入并通过Finish一次性产出最终过滤器查询侧由FullFilterBlockReader承担其KeyMayMatch/PrefixMayMatch/MayMatchfull_filter_block.cc直接对整块过滤器执行检查命中与否分别累加bloom_sst_hit_count/bloom_sst_miss_count性能计数器可用PerfContext观测。一个已知的代价构建期内存开销原文档明确指出新格式的一个缺点构建 SST 文件时内存消耗更高。旧格式只需为每个小块缓冲少量键构建期内存占用低full filter 需要在生成过滤器前缓冲全部键的哈希当 SST 文件变大时这部分内存随之线性增长。这一代价在后续版本中催生了 partitioned filter见下文后续演进其目的正是在保留 full filter 查询优势的同时把构建期内存与过滤器块的体积控制在可预测范围内。HISTORY.md 中也有相应提示若 full filter 创建期临时内存占用成为问题可考虑使用 partitioned filters、更小的 SST 文件或设置reserve_table_builder_memorytrue见 HISTORY.md 7.0 发布记录。用法与定制原文档将详细用法指向 RocksDB 布隆过滤器文档。结合当前仓库源码我们给出可直接落地的完整说明。启用布隆过滤器FilterPolicy 与 filter_policy 选项布隆过滤器通过BlockBasedTableOptions::filter_policy启用。该字段默认值为nullptr即默认不生成过滤器注释见 table.h。使用内置布隆过滤器的最简 C 写法如下#include rocksdb/filter_policy.h #include rocksdb/table.h rocksdb::BlockBasedTableOptions table_options; // 每键约 9.9 bit对应约 1% 的假阳性率 table_options.filter_policy.reset( rocksdb::NewBloomFilterPolicy(9.9)); rocksdb::Options options; options.table_factory.reset( rocksdb::NewBlockBasedTableFactory(table_options));要点说明bits_per_key每键位数决定过滤器大小与假阳性率的平衡。官方建议取值9.9约对应1% 假阳性率见 filter_policy.h。小数位建议不超过三位如6.667取值边界bits_per_key 0.5会被归约为 0表示不生成过滤器0.5 ≤ bits_per_key 1.0会被归约为 1.0约 62% 假阳性率见 filter_policy.h自定义比较器注意若你使用了忽略键中部分字节的自定义 comparator则必须同时提供忽略相同部分的FilterPolicy否则过滤结果会不正确见 filter_policy.h。在 OPTIONS 文件 / SetOptions 中配置除 C API 外过滤器策略也可通过配置字符串指定。FilterPolicy::CreateFromString支持bloomfilter:[bits_per_key]形式例如bloomfilter:4等价于NewBloomFilterPolicy(4)见 filter_policy.h。在 OPTIONS 文件中可写作[TableOptions/BlockBasedTable] filter_policybloomfilter:10定制自己的 FilterPolicyFilterPolicy是一个可定制Customizable的抽象基类见 filter_policy.h用户可以通过继承它实现自定义过滤器策略GetBuilderWithContext(const FilterBuildingContext)在构建期返回一个FilterBitsBuilder用于向过滤器添加键可通过FilterBuildingContext包含压缩风格、LSM 层级数、列族名、建表原因等上下文见 filter_policy.h决定在不同场景下委托给哪个内置策略例如低层用 Ribbon、高层用 BloomGetFilterBitsReader(const Slice)在读取期解析磁盘上的过滤器内容CompatibilityName()返回用于识别磁盘过滤器是否可读的兼容族名内置 Bloom 与 Ribbon 共享一个族名可互读彼此的过滤器见 filter_policy.h。版本与兼容性提示当前仓库中NewBloomFilterPolicy的第二个参数use_block_based_builder已被标记为忽略自 RocksDB 7.0 起旧的 block-based filter 在公共 API 中已不可用启用它会静默转为 full filter见 filter_policy.h。HISTORY.md 也确认 7.0 移除了 block-based filter 的写入支持并在后续移除了读取支持旧库如需良好读性能建议做一次 full compaction见 HISTORY.md。深入原理从查询路径到性能计数器查询路径对比步骤旧格式block-based filter新格式full filter1访问 index block取数据块 ID直接访问 filter block2用数据块 ID 查 filter block取过滤器偏移直接对整块过滤器执行检查3跳转到实际过滤器执行检查——内存访问多次非相邻跳转单次、连续新格式同时支持整键过滤whole key filtering与前缀过滤prefix filteringAdd时若配置了前缀提取器prefix_extractor且whole_key_filtering开启则同时加入整键与前缀AddKeyAndAlt否则仅加入前缀见 full_filter_block.cc。查询侧KeyMayMatch/PrefixMayMatch分别对应两类检查。可观测性PerfContext 统计每次过滤器判定都会更新PerfContext中的bloom_sst_hit_count判定可能存在与bloom_sst_miss_count判定不存在计数器见 full_filter_block.cc。在启用了布隆过滤器的库上可通过db-GetPerfContext()对比两类计数评估过滤器命中率与误判率是否符合预期。后续演进与最佳实践full filter 是后续过滤器架构的基础当前仓库中可看到三条主要演进方向Partitioned filters分区过滤器当 SST 文件很大时单个 full filter 会占用大量块缓存并带来构建期内存压力。BlockBasedTableOptions::partition_filters默认false需配合kTwoLevelIndexSearch将过滤器切分为多个分区各自独立进块缓存见 table.h实现见 partitioned_filter_block.cc 的PartitionedFilterBlockBuilder按partition_size估算每分区键数keys_per_partition_并切割。原文档所述大过滤器的构建内存问题正是这类方案要解决的场景。Ribbon filter布隆过滤器的空间更优替代NewRibbonFilterPolicy(bloom_equivalent_bits_per_key, bloom_before_level)在同等假阳性率下约节省30% 空间代价是约 3–4 倍的构建 CPU 时间与 3 倍临时空间可通过bloom_before_level实现高层 Bloom 低层 Ribbon的混合配置见 filter_policy.h。格式版本与内存优化新布隆过滤器实现默认要求format_version 5当前仓库默认format_version 7见 table.hoptimize_filters_for_memory默认true在启用malloc_usable_size时通过调整过滤器尺寸减少内存内部碎片以 Jemalloc 为例约可节省 10% 过滤器内存占用见 table.h。实践建议点查密集、且能容忍约 1% 误判的应用直接使用NewBloomFilterPolicy(9.9)作为起点若 SST 文件体积大、块缓存紧张或构建内存受限评估partition_filters true关注 LSM 低层大而长命文件的空间占用时可考虑 Ribbon filter 的混合配置升级/降级过程中注意过滤器格式版本兼容性Ribbon 需 RocksDB ≥ 6.15见 filter_policy.h。总结Full filter block 通过一个 SST 文件一个整体布隆过滤器的设计将点查路径从索引 → 过滤器定位 → 过滤器检查压缩为直接检查消除了旧 block-based filter 的复杂结构与非相邻内存访问是 RocksDB 在内存驻留场景下提升点查性能的关键优化之一其代价是构建期需要缓冲全部键哈希、内存占用随 SST 文件增大而增长。理解这一设计是正确配置filter_policy、评估 partitioned filter 与 Ribbon filter 等现代演进方案的前提。【免费下载链接】rocksdbA library that provides an embeddable, persistent key-value store for fast storage.项目地址: https://gitcode.com/gh_mirrors/ro/rocksdb创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考