布隆过滤器是数据库系统中实现高速成员检测的核心数据结构，其能够在仅消耗数个 CPU 周期的条件下判断某个元素是否「一定不在集合中」。尽管布隆过滤器会产生假阳性（将不在集合中的元素误判为存在），但永远不会产生假阴性，这一特性使其成为数据库存储引擎和哈希连接优化的利器。然而，传统单比特布隆过滤器在高 occupancy 场景下误判率会急剧上升，严重削弱其过滤效果。本文将深入探讨 Floe 工程团队如何通过双位计数技术将误判率降低 50%，并在可忽略的性能开销下实现 2 倍精度提升的完整工程实践。
布隆过滤器在数据库中的核心作用
在现代数据库引擎中，布隆过滤器通常部署在两个关键路径上。第一个场景是存储引擎的列式存储过滤：当执行表连接操作时，如果 probe 侧仅有 1% 的行能够匹配 build 侧，存储引擎可以在解压完整列数据之前先使用布隆过滤器进行第一遍过滤，直接跳过 99% 不可能匹配的行。Floe 团队的实测数据显示，无布隆过滤时需要执行约 100 亿次列解压操作，而使用布隆过滤后可降至 10.9 亿次，降幅达 9 倍之巨。第二个场景是哈希连接的 probe 阶段：在探测哈希桶之前先通过布隆过滤器排除必然不存在的键值，避免昂贵的哈希表查找开销。
Floe 最终选定 256KB 作为每个哈希连接的布隆过滤器大小。这一选择基于对内存占用与缓存效率的权衡：过大的过滤器会溢出 L2/L3 缓存导致缓存未命中剧增，过小的过滤器则因 occupancy 过高而失去实用价值。固定大小还带来了代码可预测性强、无动态分配、编译器优化充分以及支持无锁并发访问等工程优势，这对于追求极致性能的数据库引擎尤为关键。
单比特方案面临的精度瓶颈
布隆过滤器的误判率由公式 (1 - e^(-kn/m))^k 精确描述，其中 k 为哈希函数数量，m 为比特数组长度，n 为已插入元素数量。当插入元素逐渐增多时，越来越多的比特被置为 1，过滤器逐渐饱和，随机查询命全部 k 个比特位的概率显著上升，导致误判率飙升。在 Floe 的实际配置下（k=1，单哈希函数，n=256K 元素，m=2M 比特），传统单比特方案的误判率高达 11.68%，这意味着近八分之一的「通过」结果实际上是虚假匹配。在处理数十亿行的大表扫描时，这意味着大量无意义的解压和计算资源被浪费。
问题的根源在于单比特设计无法区分「该位置被少数元素设置」与「该位置已被大量元素饱和」。当过滤器 occupancy 超过临界点后，误判率的增长是非线性的，这使得传统的固定大小方案在面对不同数据规模时难以保持稳定的过滤效率。
双位计数技术的实现原理
Floe 提出的解决方案是在单个 32 位无符号整数中存储两个独立的比特位，而非使用两个独立的单比特数组。具体实现利用了一个哈希值的不同比特段来计算三个关键信息：数组索引（高 16 位）、第一个比特的位置（次高 5 位）、第二个比特的位置（第三组 5 位），剩余 6 位保留未用。这种设计的核心优势在于将两次内存访问合并为一次：插入操作只需读取目标 uint32、计算两个比特位的掩码、执行一次原子 OR 操作即可同时设置两个比特；查询操作同样只需一次内存读取即可获取两个比特位的状态进行联合判断。
从内存访问模式的角度看，单次 32 位读取在现代 CPU 上恰好符合缓存行对齐要求，能够充分利用向量化加载指令。而两套独立的单比特数组无论如何排列都至少需要两次非连续的内存访问，开销远高于单次读取加上额外的位运算成本。原子操作方面，32 位原子 OR 在 x86 架构上对应单条指令，无锁并发写入的实现复杂度与单比特方案相当。
代码实现高度简洁。插入函数计算目标数组索引和双比特掩码后执行原子 OR：uint32_t mask = (1u << bitLoc1 (h)) | (1u << bitLoc2 (h)); __sync_fetch_and_or (mBuf + idx, mask); 查询函数则读取对应 uint32 并验证两个比特位是否均被设置：return (data & mask) == mask; 相比原有实现，仅增加了生成第二比特掩码的位移操作和一次额外的位 OR 运算，这些在 CPU 流水线中几乎可以忽略不计。
性能实测与精度验证
Floe 团队在真实硬件上进行了严格的性能基准测试。插入操作的吞吐量从单比特的 9.12 周期 / 操作小幅上升至 9.70 周期 / 操作，涨幅约 6%；查询操作从 1.97 周期 / 操作增至 3.16 周期 / 操作，表面上增长了 60%，但绝对值仅增加了 1.2 个 CPU 周期，换算成时间仅为约 0.5 纳秒。这一性能损失在数据库查询的宏观时间尺度上可以忽略不计 —— 毕竟一次函数调用的开销就足以覆盖数十次这样的操作。
然而精度提升才是真正的亮点：误判率从 11.68% 骤降至 5.69%，降幅接近 50%。在实际的 T 级别大表扫描场景中，这意味着可以避免约 60GB 的不必要数据解压。按照 Floe 的生动描述：「我们在每一行上多花一纳秒，换来的是少读取数十 GB 数据，这笔交易每天都做。」
工程落地的关键参数与监控建议
对于希望在自身系统中复这一优化的团队，以下是经过验证的关键工程参数。数组大小配置方面，推荐采用 2M 比特（约 256KB）作为单比特方案的基准，对应双比特方案同样使用 256KB 数组但存储容量翻倍。哈希函数数量在双比特方案中可维持在 k=1，因为双比特已经提供了足够的碰撞冗余度，无需增加额外的哈希计算开销。索引掩码设计方面，16 位索引可覆盖 65536 个 uint32 条目，配合 5 位比特位移（2^5=32）恰好遍历单个 uint32 的全部 32 个比特位。
在实际部署中，建议对布隆过滤器建立两项核心监控指标。第一是 occupancy 比率，即已设置比特数与总比特数的比例，当超过 50% 时应考虑扩容或清理过滤器；第二是实际误判率，通过采样查询结果进行交叉验证，阈值设定为超过 8% 时应触发告警。双比特方案相较于单比特的额外收益在于：即使在 50%–60% 的高 occupancy 区间，仍能维持低于 6% 的误判率，而单比特方案在此区间往往已超过 15%。
在进一步扩展性方面，Floe 团队已实现 SIMD 版本可同时批量检查 8 个元素，适用场景为需要极高吞吐量的扫描路径。进阶方案还可考虑 Cuckoo 过滤器或 XOR 过滤器，但这些方案需要动态扩容逻辑，与 Floe 追求的固定大小、无锁并发、确定性缓存行为的设计目标存在冲突。
资料来源：本文技术细节主要参考 Floe 工程博客《Two Bits Are Better Than One: making bloom filters 2x more accurate》（2026 年 2 月 16 日）。