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

王瀚橙 等: 无锁并发布谷鸟过滤器 3341

无锁并发方案. 但是, 该方案无法应用于哈希桶内存在多个插槽的布谷鸟过滤器中. 无锁罗宾汉哈希表 [39] 使用 K-CAS
操作 [40,41] 实现原子地写入多个元素, 并结合时间戳无锁地读取元素. 无锁跳房子哈希 [42] 使用 K-CAS 操作进行元素
迁移操作中的状态设置和时间戳更新. 无等待可扩展哈希 [43] 通过将桶和目录的数据与引用拆分, 结合写时复制机
制与线程间帮助机制, 实现无等待的读写操作. 需要注意, 哈希表数据结构与布谷鸟过滤器虽然结构相近, 但两种
数据结构语义上具有本质区别. 例如, 哈希表数据结构会保存元素的完整值, 但布谷鸟过滤器只保存元素的部分
值 (指纹). 这一区别造成该领域的相关工作难以应用于本文研究的过滤器数据结构中.
综上, 现有的并发过滤器数据结构主要使用锁提升多线程性能, 当并发线程数量较多时, 锁竞争会影响数据结
构的性能, 继而导致并发性能瓶颈. 据我们所知, 本文提出的无锁并发布谷鸟过滤器是首个可以支持无锁并发的布
谷鸟过滤器数据结构.

2 背景知识

本文所提出的方法主要基于布谷鸟过滤器和多机器字比较并交换 (K-CAS) 技术, 接下来将对上述两点背景
知识进行介绍.

2.1 布谷鸟过滤器
布谷鸟过滤器 [30] 的数据结构由哈希表、哈希桶、插槽三级存储结构组成. 具体来说, 布谷鸟过滤器的哈希表
由若干哈希桶组成, 每个哈希桶中包含若干插槽. 图 1 展示了一个具有 6 个哈希桶的布谷鸟过滤器, 其中每个哈希
桶中具有 3 个插槽.

0 布谷鸟过滤器 0 f 0
1 的查询操作通 1 f 1 布谷鸟过滤器
过检查元素的
2 2 的插入操作通
两个对应桶中 过移动先前插
3 是否存在匹配 3 f 2 入的指纹产生
的指纹判断元
4 4 空插槽来容纳
素是否存在
5 5 新的指纹 f 0
(a) 布谷鸟过滤器的查询操作 (b) 布谷鸟过滤器的插入操作
图 1 布谷鸟过滤器执行查询操作和插入操作的示例

查询操作: 布谷鸟过滤器通过保存元素的指纹来近似地存储元素, 并且每个元素均有两个哈希桶与该元素对

应. 具体来说, 对于待查询元素 e, 布谷鸟过滤器首先使用哈希函数 h f 计算元素的指纹 f = h f (e). 之后, 布谷鸟过滤
器使用哈希函数 h i 计算元素对应的两个候选桶地址 i 1 = h i (e) 和 i 2 = h i (e)⊕h i ( f). 最后, 布谷鸟过滤器逐个比较两
f 相同的指纹. 只要某个候选桶中存在一个相同的指纹
个候选桶中的插槽, 判断是否存在和待查询元素 e 的指纹
e
则返回待查询元素 e 存在. 反之, 则返回待查询元素 不存在. 图 1(a) 给出了查询元素是否存在的一个示例. 待查
询元素的两个候选桶为桶 1 和桶 4, 只要桶 1 和桶 4 所包含的 6 个插槽中的任意一个插槽内具有匹配的指纹, 则
返回待查询元素 e 存在.
插入操作: 对于待插入元素 e, 布谷鸟过滤器首先计算元素的指纹 f 以及该元素的两个候选桶的地址 i 1 和 .
i 2
e 的指纹插入任意一个空插槽中并返回插入成功. 若两个候选桶中均
若两个候选桶中存在空插槽, 则直接将元素
′
f
e
没有空插槽, 则从两个候选桶中随机踢出一个指纹 f , 进而产生一个空插槽来存放待插入元素 的指纹 . 之后,
f 的另一个候选桶中有空插槽, 则将被踢出的指纹保存到另一个候选桶中. 否则, 从另一个候选
′
若被踢出的指纹
f , 产生一个空插槽存放指纹 . 重复上述过程直到寻找到一个空插槽存放被踢出的指
′
′′
f
桶中再随机踢出一个指纹
纹. 图 1(b) 给出了向布谷鸟过滤器中插入指纹为 f 0 的元素的示例. 由于该元素的两个候选桶均已满, 因此需要从
候选桶中随机踢出一个指纹 (例如 f 1 ), 并将 f 0 保存到 f 1 所在的插槽中. 由于指纹 f 1 的另一个候选桶中也不存在空
插槽, 则继续随机踢出指纹 f 2 来存放指纹 . 最后, 由于指纹 f 2 的另一个候选桶中有空插槽, 因此指纹 f 2 可以直接
f 1