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

3342 软件学报 2025 年第 36 卷第 7 期

存放在另一个候选桶中, 并返回插入成功.
删除操作: 删除操作首先计算待删除元素的指纹以及两个候选桶的地址, 之后从候选桶中删除一个和待删除
元素的指纹相同的指纹.

2.2 多机器字比较并交换
比较并交换操作 (compare and swap) 是一种底层的原子操作, 该操作常被用于无锁并发算法的设计. 该操作的
功能为: 首先将内存中存储的值与待比较数据进行对比, 若内存中存储的值和待比较数据 d 1 相同, 则触发交换操
作将内存中存储的值更新为 d 2 ; 若内存中存储的值和待比较数据 d 1 不同, 则不触发交换操作并保持内存中存储的
值不变. 该操作可以原子地实现比较并交换功能, 执行时不会被拆分为子指令. 因而任何线程不会观测到该操作的
中间状态, 而只会观测到该操作尚未执行, 或已经执行完成. 相比于使用加锁的方式实现并发, 比较并交换操作更
加底层且高效. 因此, 当使用锁的多线程程序遇到高并发性能瓶颈时, 将锁替换为比较并交换操作有望进一步提升
并发性能.
多机器字比较并交换操作 (K-CAS) [40,41] 是比较并交换操作的扩展. 具体来说, 不同于比较并交换操作只能原
子地修改单个内存地址中的数据, 多机器字比较并交换操作能同时对多个不同内存地址中的数据执行比较并交换
操作. 换句话说, 使用多机器字比较并交换技术读写数据的线程不会观测到多机器字比较并交换操作的中间状态,

只会观测到所有 K 个比较并交换操作均未执行或均已全部执行完毕.

3 无锁并发布谷鸟过滤器设计

本节从查询、插入和删除这 3 个操作出发, 详细介绍了无锁并发布谷鸟过滤器的设计. 此外, 本节还证明了上
述 3 个操作均是可线性化的.

3.1 查询操作
传统布谷鸟过滤器的查询操作在并发场景下会产生查询漏报问题. 具体来说, 对于单线程场景, 布谷鸟过滤
器的查询操作只需要依次检查待查询元素的两个候选桶 i 1 和 i 2 中是否存在匹配的指纹即可. 但是, 对于多线程
并发场景, 直接沿用这一设计会导致并发插入的元素指纹无法被查询到. 例如, 对于某个执行查询操作的线程,
若该线程首先访问待查询元素的第 1 个候选桶 i 1 , 再访问待查询元素的第 2 个候选桶 i 2 . 由于两次访问操作不
是原子的, 若在两次访问操作执行之间存在某个执行插入操作的线程将待查询元素的指纹从候选桶 i 2 迁移到
候选桶 i 1 中, 则会造成即使待查询元素的指纹存在于布谷鸟过滤器中, 执行查询操作的线程依然无法查询到该
指纹, 并返回“待查询元素不存在”的错误信息, 继而造成查询漏报, 这是使用过滤器数据结构的应用 [1−17] 所无法
接受的.
为解决并发引起的查询漏报问题, 本文提出了两阶段查询技术. 该技术的第 1 阶段将检查两个候选桶中是否
存在匹配的指纹, 若不存在, 则进入第 2 阶段, 再次检查两个候选桶中是否存在匹配的指纹. 若两个阶段均未发现
匹配的指纹, 并且在两阶段查询过程中没有指纹在两个候选桶之间反复迁移, 则待查询元素必不存在, 从而避免了
查询漏报.
两阶段查询技术解决查询漏报问题的核心设计在于通过迁移计数器判断指纹是否在两个候选桶之间反复迁
移. 具体来说, 无锁并发布谷鸟过滤器为每个候选桶添加一个记录元素迁移情况的迁移计数器. 当某个指纹被执行
插入操作的线程从候选桶 i 1 迁移到候选桶 i 2 后, 若迁移前两个候选桶的迁移计数器值分别为 t 1 和 t 2 , 则迁移后无
锁并发布谷鸟过滤器会将两个候选桶的迁移计数器的值分别更新为 t 1 +1 和 max(t 1 ,t 2 )+1. 基于这一设计, 两阶段
查询技术可以通过迁移计数器数值变化判断候选桶中是否有指纹迁移发生.
基于上述核心设计, 两阶段查询技术解决查询漏报问题的方案如下. (1) 两阶段查询首先检查待查询元素对应
的两个候选桶中是否存在匹配的指纹, 并记录此时两个候选桶的迁移计数器取值 t 1 和 t 2 . (2) 若未查询到匹配的指
t 和 . (3) 若上述
′
′
纹, 则重新检查两个候选桶中是否存在匹配的指纹, 并再次记录两个候选桶的迁移计数器取值 1 t 2
两个阶段均未查询到匹配的指纹, 并不能直接说明待查询元素不存在. 具体来说, 若在第 1 阶段查询候选桶 i 1 和候