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

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

P 和集合 N 的划分由需要拦截的高风险网站决定. 其次, 我们关注如何获取误判代价 C(x). 这里的误判代价 C(x)
也是根据特定应用场景要求来设定的. 例如在网络多播场景中, 不同级别的端口所连接的机器数量不同, 导致过滤
器误判时转发给不同端口带来的额外开销是有差异的. 我们可以根据每个端口不同的误判开销来为其分配一个特
定误判代价. 而在网络黑名单中, 我们可以根据恶意网站访问的流量设置其误判代价.
代价敏感的近似集合成员查询问题与传统的近似集合成员查询问题的定义有两点不同. 一是本文假设集合 N
的信息是可以获得的, 即不在 P 集合内的元素信息是可知的. 传统问题定义中并没有假设集合 N 内元素信息是可
获取的, 但本文的假设是基于实际应用的. 例如, 在网络多播机制中需要转发的端口集合和不需要转发的端口集合
信息都是明确可知的, 对应到本文中集合 N 和集合 P 的信息都是可以获取的. 此外, 集合 N 的信息在许多网络应
用中也是可以获取的 [27,29] . 二是本文假设集合 N 的元素被误判的代价是不相同的, 并应该被区别对待. 这个假设同
样可以在现实应用中找到对应的例子. 以网络多播问题为例, 数据中心网络拓扑中不同级别的端口连接的机器数
量是不一样的, 因此错误转发给不同端口带来的冗余流量和带宽占用是显著不同的. 同样, 在检测恶意网站时, 一
些知名的恶意网站占用的网络流量远远超过其他普通恶意网站, 正确区分这些恶意网站带来的代价是必需的.
当然, 为了解决上述问题, 一个简单的解决方案是直接存储或压缩存储集合 P, 但显然占用的空间较大, 这在
一些对空间要求较高的应用中是难以应用的, 例如在网络交换机上或多播数据包头部. 考虑到苛刻的空间要求, 因
此可行的方案是利用空间效率较高的过滤器来近似地解决上述问题. 然而, 传统过滤器在设计时忽略了上述两个
问题的假设, 导致误判率较高. 为了解决上述的代价敏感近似集合成员查询问题, 本文设计了一种指纹可变哈希布
谷鸟过滤器.

2.2 基本思路
为了解决代价敏感近似集合成员查询问题, 本文设计了指纹可变哈希布谷鸟过滤器, 目标是降低总体的误判
代价, 特别是避免高代价元素被误判. 为了实现这个目标, 本文观察到元素被误判的原因是不同元素映射到了同一
个桶内, 并且在一个桶内拥有相同的哈希指纹. 因此, 为了避免特定元素被误判, 可行的方法就是改变映射的哈希
桶的位置或者改变冲突元素的指纹信息. 但是, 考虑到本文需要保持映射到桶的随机性, 从而保持哈希表能尽量均
匀地装载更多的元素, 也就是说, 无法直接改变映射的哈希桶的哈希函数, 因此本文转而考虑修改冲突的元素的指
纹信息.
然而, 直接修改指纹会导致被修改的元素无法被正确查询到. 因此, 本文的方法是不直接修改指纹, 而是修改
y
y
产生指纹的哈希函数. 例如, 当元素 x 与误判代价较高的元素 发生冲突时, 即 x 和 在同一个桶内, 并且它们的指
纹完全相同, 即 f(x) = f(y), 其中 f 是产生指纹的哈希函数. 本文将哈希函数 f 修改为另一个哈希函数 , 这样元
f 1
y
素 x 和元素 冲突的概率就会大大降低.
那么, 是否需要为每个冲突的元素都去修改指纹哈希函数. 考虑到过滤器是一个空间非常高效的结构, 如果为
每个元素都去修改指纹哈希函数, 记录的成本就会很高, 而且重复计算不同的哈希函数也会极大地降低过滤器的
查询吞吐率. 因此, 本文并不会单独修改每个元素, 而是只为误判代价高的元素修改指纹函数. 考虑到误判代价高
的元素占比并不多, 即每个哈希桶内的误判代价较高的元素数量有限, 一个更好的做法是按照桶为单位调整哈希
函数. 因此, 本文为每个哈希桶单独分配一个空间, 用于记录该哈希桶内修改后的哈希函数.

2.3 结构设计
为了实现上述目标, 本文设计了如后文图 4 所示的指纹可变哈希布谷鸟过滤器. 指纹可变哈希布谷鸟过滤器
的结构与布谷鸟过滤器相似, 都是由多个哈希桶组成. 但不同的是, 在每个哈希桶内部, 除了用于记录元素指纹信
息的指纹单元, 还有一个额外的指纹哈希索引单元, 用于记录该桶内产生指纹的哈希函数的编号. 此外, 不同于标
准布谷鸟过滤器的是, 本文中用于确定桶位置和生成指纹的哈希函数是相互独立的.

2.4 指纹可变哈希布谷鸟过滤器的查询过程
指纹可变哈希布谷鸟过滤器的查询过程与标准布谷鸟过滤器的查询过程类似, 都是检查映射到的两个哈希桶
内是否包含与查询元素相同的指纹, 唯一不同之处在于每个桶内产生指纹的哈希函数是不同的, 因此需要根据每