布隆过滤器是数据库领域常用的概率型数据结构，其核心优势在于极快的查询速度 —— 每个查找仅需数次 CPU 周期，比一次函数调用更快。然而，传统布隆过滤器采用单比特位存储，当插入元素过多时会出现严重的假阳性问题。本文介绍一种将比特单元扩展为 2 比特的优化方案，在相同空间占用下实现假阳性率降低约 50% 的效果。
传统布隆过滤器的局限性
标准布隆过滤器由 m 个比特位组成的数组构成，所有比特位初始值为 0。插入元素时，使用 k 个不同的哈希函数计算比特位置，将对应的 k 个比特位置设为 1。查询时，检查所有 k 个比特位是否均为 1：若存在任意比特为 0，则元素必定不在集合中；若全部为 1，则元素可能在集合中（可能是假阳性）。
假阳性产生的根本原因在于：随着插入元素数量 n 的增加，越来越多的比特位被置为 1，最终随机查询的元素会因纯偶然因素而使所有 k 个比特位均为 1，导致误判。假阳性率的数学表达式为 (1 - e^(-kn/m))^k，其中 k 为哈希函数数量，m 为比特数组大小，n 为已插入元素数量。以 Floe 数据库的实际参数为例：k=1、n=256K、m=2M 比特时，传统单比特实现的假阳性率高达 11.5%，这意味着每 10 次查询就有超过 1 次产生错误结果。
2 比特单元的设计原理
2 比特单元优化的核心思想是将每个比特位扩展为 2 比特的计数器。这种设计允许布隆过滤器区分三种状态：00 表示该位置未被任何元素映射；01 表示被一个元素映射；10 或 11 表示被多个元素映射。查询时，只有当两个比特位均为 1 时才认为该位置被占用，这与单比特的 “0 或 1” 二元判断相比提供了更精细的区分能力。
这种改进的数学原理在于：传统单比特无法区分 “被映射一次” 和 “被映射多次” 的情况，而 2 比特计数器通过记录映射次数的近似值，更准确地估计每个比特位的实际占用状态。当某个比特位被多个元素映射时，其假阳性贡献会被相应降低，因为需要更多随机比特位同时为 1 才会产生误判。
工程实现的关键技巧
Floe 团队的工程实现采用了一个巧妙的优化：将两个比特位存储在同一个 32 位无符号整数中。这种设计带来了显著的性能优势。首先是单次内存访问：由于两个比特位位于同一 uint32 变量中，读取一个比特位和两个比特位所需的内存操作次数相同，都是一次内存读取加上按位掩码运算。其次是原子操作兼容性：设置两个比特位可以通过单一的原子 OR 操作完成，无需使用锁或其他同步机制，这对于高并发数据库引擎至关重要。最后是缓存友好性：两个比特位共享同一个缓存行，能够更好地利用 CPU 缓存层级。
具体实现中，使用单一哈希值同时计算三个信息：数组索引（16 比特）、第一个比特位置（5 比特）、第二个比特位置（5 比特）。代码实现仅需在掩码生成时增加一次位移操作，查询时增加一个额外的按位与运算。这种微小的代码改动带来了实质性的准确率提升。
性能与准确率的实测数据
根据 Floe 团队的基准测试结果，优化后的性能开销非常有限：put () 操作从 9.12 周期增加到 9.70 周期（约 6% 增长），contains () 操作从 1.97 周期增加到 3.16 周期（增加约 1.2 个周期）。需要注意的是，即使 “变慢” 后的版本仍然比一次函数调用或分支预测失误所需的时间更短，实际执行时间差异在纳秒级别。
然而准确率的提升是显著的：假阳性率从 11.68% 降低至 5.69%，实现了约 51% 的相对降幅。以扫描 1TB 表结构的查询为例，这意味着可以避免解压约 60GB 的冗余数据。简单计算即可发现：每行增加约 1 纳秒的查询时间，却能节省数十 GB 的 I/O 操作，这是一个非常划算的性能交换。
为什么恰好是 2 比特
这涉及到投入产出比的权衡。使用同一份交互式工具进行计算：当比特数从 1 增加到 2 时，滤波器容量从约 10 万元素提升至 25.3 万元素，增长 2.5 倍；从 2 增加到 3 时，容量仅提升 20% 至 30.6 万元素；从 3 增加到 4 时，容量提升不足 5% 至 32 万元素。2 比特恰好处于 “收益显著” 与 “实现复杂度可接受” 的甜蜜点。
此外，更多比特位会破坏单次内存访问的优势。当使用 3 个或更多比特位时，单个 uint32 无法容纳所有比特，必须进行多次内存访问或使用更复杂的数据结构，这会抵消准确率提升带来的收益。
与其他数据结构的对比
虽然 Cuckoo 过滤器和 XOR 过滤器在某些场景下表现更好，但它们需要动态扩容或更复杂的寻址方式。Floe 团队选择固定大小的布隆过滤器有明确的技术考量：固定 256KB 大小意味着无需动态内存分配、编译器可以进行极限优化、可以实现无锁并发访问、并且具有可预测的 L2/L3 缓存行为。这些特性对于延迟敏感型数据库引擎尤为重要。
资料来源：本文技术细节主要参考 Floe 数据库工程博客对 2 比特布隆过滤器优化的实现分析。