在网络入侵检测、基因组数据去重和高速数据包过滤等场景中，Bloom Filter 以其紧凑的空间开销和高效的查询性能被广泛采用。然而，标准 Bloom Filter 仅支持插入操作，无法满足需要删除元素的场景。两位计数器 Bloom Filter（Two-Bit Counter Counting Bloom Filter，简称 2-bit CBF）通过将每位扩展为 2 位计数器，在保持 Bloom Filter 优势的同时支持有限次数的删除操作，同时能够粗略估计元素的出现频次。在 FPGA 上实现这一结构时，工程师需要在内存带宽、逻辑资源和预测精度之间做出精细的权衡，本文将从数学推导出发，给出可落地于实际硬件设计的参数建议。
误判率公式的数学推导
理解两位计数器 Bloom Filter 的误判率是进行工程设计的前提。设滤波器包含 m 个计数器，每个计数器为 2 位（可表示 0 至 3 的整数值），共使用 k 个哈希函数，插入 n 个元素。在非饱和状态下（即没有任何计数器的值达到上限 3），每个计数器被设置为 1 的概率与标准 Bloom Filter 完全一致：某一位未被置位的概率为 e^(-kn/m)，因此至少被置位一次的概率为 1-e^(-kn/m)。查询时，只要所有 k 个对应计数器均非零，即认为元素可能存在。由于查询只判断 “计数器大于 0” 与 “计数器等于 0”，并不读取具体计数值，因此误判率的近似公式与标准 Bloom Filter 相同：
p ≈ (1 - e^(-kn/m))^k
这里的 m 是计数器数量而非比特数，每个计数器占用 2 位存储。值得注意的是，当部分计数器因高频元素而饱和至 3 时，实际误判率会高于上述公式的预测值，因为饱和会导致计数器无法继续反映真实的冲突程度。饱和效应在负载因子（n/m）超过 0.5 后会逐渐显著，此时需要通过仿真或更精确的分析模型进行评估。
在 FPGA 实现中，工程师通常根据目标误判率 p 和预期插入元素数量 n 反推所需的计数器数量 m 和哈希函数个数 k。对于 2-bit CBF，典型的工程做法是先确定 m，再通过数值方法求解使 p 最小化的 k 值。经验上，当 m/n 约为 10 至 15 时，选用 k=7 至 9 个哈希函数可以在典型负载下获得 10^-3 至 10^-4 量级的误判率。
FPGA 内存架构与位操作实现
在 FPGA 上实现两位计数器 Bloom Filter，核心挑战在于如何在有限的内存带宽下高效完成 k 个计数器的读 - 修改 - 写操作。现代 FPGA 通常配备 Block RAM（BRAM）或 UltraRAM，部分高性能系统还会连接 HBM/HMC 外部内存。以下是针对不同存储层次的实现策略。
对于片上 BRAM，最有效的做法是将多个 2 位计数器打包成固定宽度的逻辑字。假设使用 32 位逻辑字，则每个字可容纳 16 个计数器；使用 64 位字则可容纳 32 个计数器。具体操作流程如下：首先根据哈希函数输出的低地址位计算计数器索引 i，然后计算字索引⌊i/C⌋（C 为每字计数器数）和位偏移 2×(i mod C)。读取整个字后，提取对应字段进行饱和递增或饱和递减操作，再写回。整个读 - 修改 - 写过程可以在 4 级流水线内完成：第一级计算哈希和地址，第二级读取内存，第三级提取和更新计数器，第四级写回。如果使用双端口 BRAM，可以实现每周期同时进行读和写操作，从而维持高吞吐。
对于需要更高容量的场景，可以采用分区分组（partitioned/banked）架构。将整个滤波器划分为 k 个独立的 bank，每个哈希函数对应一个 bank，这样可以在单次查询中并行访问所有 k 个计数器而无需访问同一内存 bank。该架构的另一个优势是避免了多哈希函数访问同一物理 BRAM 产生的端口冲突。在 Xilinx UltraScale + 系列上，可以将滤波器分布到多个 36K BRAM 块中，每个 bank 使用独立的端口，从而实现 k 路并行访问。
内存开销与精度的工程权衡
两位计数器 Bloom Filter 相较于标准单比特 Bloom Filter，内存开销增加了一倍（每计数器从 1 位变为 2 位），但换来了两个关键能力：一是支持有限次数的删除操作，二是能够区分 “元素不存在”、“单次出现” 和 “多次出现” 三种状态。在工程实践中，这一精度提升的代价需要根据具体应用场景进行量化评估。
假设目标场景为网络流去重，流表规模为 100 万条流记录，预期每条流平均被测量 100 次。如果使用单比特 Bloom Filter，内存需求约为 100 万位（约 125KB），但无法区分重复记录与新记录。如果使用 2-bit CBF，同等误判率下需要约 200 万位（约 250KB），但可以准确识别出哪些流已经出现过。当需要支持删除操作时（如流超时后的清理），2-bit CBF 的优势更加明显：单比特 Filter 在删除操作后无法恢复被误判的空间，而 2-bit CBF 可以通过递减计数器释放占位。
饱和处理是另一个重要的工程考量。当某个计数器达到上限 3 后，继续插入相同哈希值的元素将导致计数器保持 3 而非继续增长，这会使该计数器失去区分能力。在 FPGA 中实现时，可以通过检测饱和来优化写回操作：当读取到的计数器值已是 3（插入场景）或已是 0（删除场景）时，可以跳过写回以节省带宽。但需要注意，这种优化在高频冲突场景下可能导致时序紧张，因为需要先读取才能判断是否饱和。
可落地的参数配置清单
以下给出面向典型 FPGA 平台的参数建议，基于 BRAM 实现、目标吞吐量 100 万次查询每秒的场景：
关于内存配置，推荐采用 64 位逻辑字封装 32 个计数器，这样每个 BRAM36E2 块（72 位物理宽度）可以容纳 36×32=1152 个计数器。对于 100 万级规模的滤波器，需要约 868 个 BRAM36E2 块，占用约 31 个 SLICE 资源。在哈希函数数量方面，当 m/n=12 时，k=8 可在误判率和计算开销之间取得较好平衡；高吞吐量场景可考虑 k=7 以降低逻辑资源消耗。在流水线设计上，建议采用 4 级流水线结构，每个哈希函数使用独立的计算单元，通过 Xilinx 的 DSP48 或 LUT 实现轻量级哈希（如 CRC32 或基于 XXHash 的简化版本）。对于需要更高容量的场景，可将滤波器扩展到 HBM，每个 HBM 通道对应一个独立的分区，利用其高带宽特性实现数千次并行查询。
此外，监控机制的设计同样关键。建议在 FPGA 中加入饱和计数器，定期上报达到上限 3 的计数器比例。当该比例超过 5% 时，应触发告警并考虑扩容或清理旧数据，因为这意味着误判率正在上升。