Page 448 - 《软件学报》2025年第7期

李猛 等: 代价敏感的指纹可变哈希布谷鸟过滤器 3369

  2 d   2 d
 ∑   ∑ 
       



E(Y) = 1− p i +...+ 1− p i  

     
i∈[0,0] i∈[0,n−1]
   
 ∑   ∑ 
      2 d −1




⩽ 1− p i +...+ 1− p i (1− p 0 )





    
i∈[0,0] i∈[0,n−1]
⩽ np(1− p 0 ) 2 d −1 (14)
( ( c ) n ) ( nc ) nc
n
下面继续讨论 1− p 0 的取值范围. 根据 1− p 0 = 1−(1− p) = 1− 1− ≈ 1−1+ = < 1, 因此, 使用 d
2 e 2 e 2 e
E(Y) np(1− p 0 ) 2 d −1 ( nc ) 2 d −1
比特的哈希索引空间时, 冲突元素的数量比例至少下降至 = = .
np np 2 e
误判率分析总结: 针对误判率, 相比标准布谷鸟过滤器, VHCF 的误判率可以显著降低, 并且误判率的下降比
( ) 2 d −1
nc
例可以被理论证明, 至少为 .
2 e
4 实验分析
本节将展开综合的实验来全面评估指纹可变哈希布谷鸟过滤器的性能. 首先介绍实验配置, 包括实验平台、
对比算法、评估指标和数据集. 实验主要包括两部分: 一是研究参数变化对于指纹可变哈希布谷鸟过滤器性能的
影响; 二是在多个数据集上评估 VHCF 和前人提出的方法并进行对比, 例如误判率、查询和构造时延.

4.1 实验配置
40 线程的 Intel Xeon Gold 5218R CPU 64 GB 内存的服务器评估
● 实验平台. 使用一台配备了两颗 20 核 以及
不同算法的性能. 使用 C++实现了指纹可变哈希布谷鸟过滤器 VHCF. 所有实验均使用 GCC 编译器编译并运行
在 CentOS 操作系统上. 实验部分汇报的结果都是重复 10 次后取平均值.
● 对比算法. 本文使用两个经典的过滤器和两个最新的数据分布自适应的过滤器进行测试. 4 个对比算法依
次是 (1) 标准 Bloom 过滤器 BF [34] , 作为一个基准来衡量其他过滤器的性能; (2) 标准布谷鸟过滤器 CF [18] , 作为基
于布谷鸟过滤器的变种的基准来衡量其他过滤器的性能; (3) 哈希自适应 Bloom 过滤器 HABF [27] , HABF 作为
Bloom 的一个变种, 是一个代价敏感的过滤器, 同时也是本文一个主要的对比算法. (4) 自适应布谷鸟过滤器
[28]
ACF , ACF 是面向在线场景设计的自适应过滤器, 由布谷鸟过滤器和布谷鸟哈希表两部分组成. 当一个元素发
生误判时, ACF 会修改引起该元素误判的指纹信息从而降低误判率. 最后, 本文提出的 VHCF 以及所有其他过滤
器的测试代码已发布在 https://github.com/Ln7-best/VHCF.
● 性能评估指标. 本文主要在 3 个指标上评估了指纹可变哈希谷鸟过滤器的性能: (1) 代价加权误判率 (weighted
∑
F(x)·C(x)
x∈N
false positive rate, Weighted FPR), 其定义为 ∑ , 其中 F(x) = 1 表示过滤器 F 判定元素 x 在集合 P 中
C(x)
x∈N
C(x) = 1 时, 此时代价加权误判率等同于普通 FPR); (2) 查询吞吐量, 查询吞吐量指的是单位时间内过滤器执行
(当
查询操作的次数, 单位为百万次每秒 (Mops/s); (3) 构造时延, 本文将其定义为在构造过滤器时, 平均每个元素需要
消耗的时间, 单位为纳秒 (ns).
● 测试数据集. 本文在 3 个场景的数据集上评估了算法的性能. 第 1 个场景是在数据中心 Fat Tree 拓扑架构 [9]
下利用过滤器进行转发. 本文分别生成了 Fat Tree 结构下不同的 k 值对应的误判率. 在 Fat Tree 网络架构中, k 参
数是重要的参数, 它表示了网络的规模和复杂性. 具体来说, k 参数定义了 Fat Tree 的端口数量, 也就是每个交换机
可以连接的其他交换机或主机的数量. 因此, k 参数直接影响了网络的带宽、容量和延迟等性能指标. 例如, 如果
k = 6, 那么每个交换机可以连接 6 个其他交换机或主机, 网络的总带宽和容量就会较 k = 4 时相应增大. 为了测试
方便, 本文随机选择 1 个主机作为发送方, 40% 的主机作为接收方, 并将发送方和接收方之间的最短路径合并成多
播的转发路径. 第 2 个场景是恶意流量识别, 本文采用了 CAIDA 数据集 [35] 进行测试. 这个数据集是从骨干网络流
量中收集的真实数据, 包含 700 万个不同的元素. 第 3 个场景是骨干网络路由流量识别, 本文使用了 MAWI [36] 数据