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

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

选桶 i 2 之间的某一时刻, 存在其他执行插入操作的线程将待查询元素的指纹从候选桶 i 2 迁移到候选桶 i 1 中. 之后
在第 2 阶段查询开始前, 又将该指纹从候选桶 i 1 迁移到候选桶 i 2 中. 最后在第 2 阶段查询候选桶 i 1 和候选桶 i 2 之
间的某一时刻, 将该指纹从候选桶 i 2 再次迁移到候选桶 i 1 中, 则一次两阶段查询无法发现该指纹. 本文将上述情
况称为: 该指纹在两个候选桶之间反复迁移. 上述问题可通过检查两阶段查询过程中记录的迁移计数器的取值发
现并加以解决. 具体来说, 当迁移操作发生后, 参与迁移的两个桶的计数器取值都会大于等于迁移前取值加一. 利
用这一性质, 当第 2 阶段查询没有发现指纹时, 无锁并发布谷鸟过滤器会检查两个阶段记录的迁移计数器值. 若两
个候选桶在第 2 阶段中记录的迁移计数器值均大于等于第 1 阶段中记录的迁移计数器值加 2, 且第 2 个候选桶第 2
阶段迁移计数器值大于等于第 1 个候选桶第 1 阶段迁移计数器值加 3, 则说明指纹发生了反复迁移, 并可能会造
成两阶段查询无法发现该指纹. 此时需要重试两阶段查询, 直到某次两阶段查询没有发生指纹反复迁移为止. 本文
第 3.5 节证明, 任意时刻至少有一个线程不会无限重试. 当两阶段查询结束时, 若两个阶段均未发现匹配指纹, 且
查询过程中没有指纹在两个候选桶之间反复迁移, 说明待查询元素必不存在. 因此, 两阶段查询技术可以避免查询
漏报发生.
无锁并发布谷鸟过滤器的查询操作如算法 1 所示. 无锁并发布谷鸟过滤器首先计算待查询元素的指纹以及两
个候选桶的下标 (第 1, 2 行). 之后执行两阶段查询流程 (第 4–18 行). 具体来说, 其中第 1 阶段查询会分别读取两
个候选桶并查询其中是否存在匹配的指纹 (第 5–8 行). 若第 1 阶段查询未找到匹配的指纹, 则会发起第 2 阶段查询
(第 10–13 行). 若两阶段查询均未找到匹配的指纹则需检查迁移计数器并判断是否需要再次重试两阶段查询流程.
若不需要重试则直接判定元素不是集合成员 (第 15–18 行).

算法 1. 无锁并发布谷鸟过滤器的查询操作.
输入: 一个字符串类型的变量 e, 其中 e 表示待查询的元素;
输出: 一个布尔类型的变量 TRUE 或 FALSE. 其中, 输出 TRUE 表示查询成功, 即待查询元素存在于布谷鸟过滤器
中; 输出 FALSE 表示查询失败, 即待查询元素不存在于布谷鸟过滤器中.

1. 计算元素指纹 f = h f (e);
2. 计算元素对应的两个候选桶地址 i 1 = h i (e) 和 i 2 = h i (e)⊕h i ( f);
3. /*注释: 性质 7 证明, 不存在某一时刻, 所有线程均陷入死循环*/
4. while (TRUE)
5. 读取桶 i 1 中的所有指纹和迁移计数器 ;
t 1
6. 读取桶 i 2 中的所有指纹和迁移计数器 ;
t 2
7. if (桶 i 1 或者桶 i 2 中有和待查询元素 e 的指纹 f 相同的指纹)
8. return TRUE;
9. /*注释: 执行第 2 轮查询*/
t
′
10. 读取桶 i 1 中的所有指纹和迁移计数器 ;
1
t
′
11. 读取桶 i 2 中的所有指纹和迁移计数器 ;
2
i 2 中有和待查询元素 e 的指纹 f 相同的指纹)
12. if (桶 i 1 或者桶
13. return TRUE;
14. /*注释: 判断是否需要重试查询操作*/
15. if ( t ⩾ t 1 +2 & t ⩾ t 2 +2 & t ⩾ t 1 +3)
′
′
′
1 2 2
16. continue;
17. else
18. return FALSE;
两阶段查询技术可以实现无锁并发查询. 具体来说, 对于某个存在于无锁并发布谷鸟过滤器中的元素 e, 对该