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

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

元素的查询操作可分为 4 种情况, 且每种情况均可查询到该元素的指纹.

(1) 若查询过程中不存在其他执行插入操作的线程将元素 e 的指纹从候选桶 i 2 迁移到候选桶 i 1 中, 则无锁并
发布谷鸟过滤器会在第 1 阶段查询中返回元素存在.
i 2 迁移到候选桶 , 且后续没有任何线程继
(2) 若查询过程中存在其他执行插入操作的线程将指纹从候选桶 i 1
续迁移该指纹. 则无锁并发布谷鸟过滤器会在第 2 阶段查询中发现该指纹存在于候选桶 i 1 中, 并返回存在.
i 1 中, 之
(3) 若查询过程中存在其他执行插入操作的线程首先将待查询元素的指纹从候选桶 i 2 迁移到候选桶
后在第 2 阶段查询开始前, 将该指纹从候选桶 i 1 迁移到候选桶 i 2 中, 且后续没有任何线程继续迁移该指纹. 则无锁
并发布谷鸟过滤器会在第 2 阶段查询中发现该指纹存在于候选桶 i 2 中, 并返回元素存在.
i 1 中. 之
(4) 若查询过程中存在其他执行插入操作的线程首先将待查询元素的指纹从候选桶 i 2 迁移到候选桶
后在第 2 阶段查询开始前, 将该指纹从候选桶 i 1 迁移到候选桶 i 2 中. 最后在第 2 阶段访问候选桶 i 1 和候选桶 i 2 的
间隙将该指纹从候选桶 i 2 再次迁移到候选桶 i 1 中, 则一次两阶段查询无法发现该指纹. 此时, 无锁并发的布谷鸟过
滤器可根据两阶段查询过程中记录的迁移计数器取值发现指纹在查询期间发生了反复迁移, 并将重试两阶段查询
过程.
查询操作时间复杂度分析如下. 当两阶段查询未发生重试时, 无锁并发布谷鸟过滤器只需检查两次两个候选
桶即可返回元素是否存在. 因此, 当未发生重试时, 无锁并发布谷鸟过滤器查询操作的时间复杂度与标准布谷鸟过
r
滤器相同, 均为 O(1). 若两阶段查询发生重试, 无锁并发布谷鸟过滤器查询操作的时间复杂度为 O(r), 其中 为重
试次数. 本文通过第 3.5 节的理论分析表明查询操作的进展性为无锁, 即任何时刻至少有一个线程不会无限重试
(详见第 3.5 节).

3.2 插入操作
无锁并发布谷鸟过滤器的插入操作如算法 2 所示. 无锁并发布谷鸟过滤器首先计算待插入元素的指纹以及两
个候选桶的索引 (第 1, 2 行). 之后读取两个候选桶 (第 5, 6 行), 并判断候选桶中是否存在空插槽. 若某个候选桶中
存在空插槽, 则使用比较并交换操作 (compare and swap) 将指纹原子地写入到无锁并发布谷鸟过滤器中 (第
8–16 行). 若两个候选桶中均没有空插槽, 则需要移动已插入元素的指纹来产生空插槽以容纳待插入元素的指纹
(第 17 行). 下文将详细描述移动已插入指纹的方法.

算法 2. 无锁并发布谷鸟过滤器的插入操作.
输入: 一个字符串类型的变量 e, 其中 e 表示待插入的元素;
输出: 一个布尔类型的变量 TRUE, 表示插入成功. /*注: 由于过滤器可扩容, 插入必能成功.*/

1. 计算元素指纹 f = h f (e);
2. 计算元素对应的两个候选桶地址 i 1 = h i (e) 和 i 2 = h i (e)⊕h i ( f);
3. /*注释: 循环可在第 11 或 16 行跳出. 性质 8 证明, 不存在某一时刻, 所有线程均陷入死循环*/
4. while (TRUE)
5. 读取桶 i 1 中的所有插槽;
6. 读取桶 i 2 中的所有插槽;
7. /*注释: 查询桶 i 1 中是否有空插槽 */
i 1 中有空插槽)
8. if (桶
9. if (使用比较并交换操作写入失败)
10. continue;
11. return TRUE;
12. /*注释: 查询桶 i 2 中是否有空插槽*/
i 2 中有空插槽)
13. if (桶