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

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

filter) [18] 由于更加优秀的性能, 近些年被越来越多的采用 [4,7,14,16,19−23] . 例如, 在数据挖掘中, 它被用于过滤掉不必要
的候选数据, 以提高数据挖掘效率; 在网络过滤中, 它被用于过滤掉不必要的流量, 以提高网络访问请求的性能; 在
数据库查询中, 它被用于过滤掉不必要的记录, 以减少昂贵的磁盘查询操作. 布谷鸟过滤器是一种基于哈希表的数
据结构, 它保证了插入和查询操作的时间复杂度都为 O(1). 布谷鸟过滤器的基本原理是将元素映射到哈希表的两
个位置, 并将这些元素的指纹存储在其中一个哈希桶中. 当需要查询一个元素是否在集合中时, 布谷鸟过滤器会检
查哈希表中对应的桶中是否存在该元素的指纹. 如果存在, 那么该元素在集合中; 否则, 该元素就不在集合中. 需要
注意的是, 由于哈希表中存储的是元素的指纹而非元素本身, 布谷鸟过滤器会有一定的误判率, 也就是会将未存储
在过滤器内的元素误判为在过滤器内. 但是, 传统的布谷鸟在设计时假设每个元素出现的次数或者误判的代价是
均匀的. 因此, 当查询元素的频率非均匀甚至非常倾斜时, 过滤器的误判率会增大. 例如, 如果一个元素 A 重复了
1 000 次, 而另一个元素 B 只出现了 1 次, 那么误判元素 A 带来的误判代价就会更大. 为了更好地解释这个问题,
本文给出两个实际系统中的例子.
案例 1. 如图 1(a) 所示, 在数据中心网络多播中, 一些最新的研究工作 [9] 提出将转发路径或端口存进过滤器.
然后, 在数据包转发过程中, 交换机会检查某个端口是否在过滤器中, 以决定是否将数据包转发至该端口. 然而, 由
于过滤器的误判, 这些数据包可能会被错误地转发至一些额外的端口, 从而导致网络带宽的浪费和占用. 尽管存在
P 4 端口连接了更多的网络端口 (
误判, 但错误地转发至不同端口所造成的网络带宽占用是不同的. 例如, 由于 P 6
和 P 7 ), 因此错误地将流量转发至 P 4 端口会比错误地转发至 P 8 端口带来更多的网络带宽占用.

转发路径 无关路径
P 1
过滤器 数据 黑名单过滤器
P 2
P 6 H 2
P 1 P 4 放行安全访问
P 3 H 1 S 1 S 4 访问请求
P 2 P 7
P 3
H 3
过滤器 数据
S 3 P 8
S 2 H 4 拦截危险访问
编码 P 2 , P 3 , P 5 P 5 P 9
H 6
过滤器 数据 过滤器 数据
P 9
H 5
P 5 P 8 P 9
(a) 网络多播中利用过滤器实现数据包转发 (b) 网络入侵检测系统快速判定恶意网络流量
图 1 不同元素遭遇过滤器误判带来的代价不相同

案例 2. 如图 1(b) 所示, 网络入侵检测系统 [24] 在检测网络访问请求时, 为了提高检测速度, 会将黑名单内的 IP
地址编码进过滤器, 从而能快速判断恶意网络流量. 然而, 一个明显的问题是, 一些正常的网络流量被误判后, 也必
须经过额外的检查过程, 这必然降低正常访问的速度. 特别是, 一些重要的访问请求或常用应用的流量一旦被误
判, 整体的延迟就会大大增加.
考虑到布谷鸟过滤器的优秀性能和丰富的操作, 已有许多基于布谷鸟过滤器的研究, 例如提升布谷鸟过滤器
的性能 [19,25] ; 增加更多的功能, 如支持扩容 [20,26] 和支持数据库中复杂的操作符 [14] . 然而, 这些研究都忽略了查询元
素集合在一些网络应用中是可以获取的. 这里的查询集合是指在查询过程中的负元素 (即不在过滤器内的元素)
的信息是可以获取的, 且这些元素在被过滤器误判时的代价并不相同. 据我们所知, 目前还没有布谷鸟过滤器的设
计考虑到元素误判代价的不同. 最相关的研究是 Xie 等人 [27] 提出的一种基于布隆过滤器的变种 HABF, 但由于布
谷鸟过滤器和布隆过滤器的结构和操作均不相同, 因此无法直接将 HABF 的方法应用过来.
对于构建代价敏感的布谷鸟过滤器问题, 主要挑战有以下两点: (1) 布谷鸟过滤元素主要通过随机哈希实现,
所以很难直接控制哈希函数值来避免某个元素误判; (2) 过滤器设计中加入的复杂操作会大幅降低过滤器查询速
度, 限制布谷鸟过滤器的应用场景.
针对上述问题, 本文提出了一种基于指纹可变哈希布谷鸟过滤器 (variable hashing-fingerprint cuckoo filter,