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

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

3. /*注释: 开始删除操作, 性质 9 证明, 不存在某一时刻, 所有线程均陷入死循环*/
4. while (TRUE)
i 1 中的所有指纹和迁移计数器 ;
5. 读取桶 t 1
6. 读取桶 i 2 中的所有指纹和迁移计数器 ;
t 2
7. if (桶 i 1 中有指纹 f)
8. if (使用比较并交换操作写入删除指纹后的桶失败)
9. continue;
10. return TRUE;
i 2 中有指纹 f)
11. if (桶
12. if (使用比较并交换操作写入删除指纹后的桶失败)
13. continue;
14. return TRUE;
15. /*注释: 执行第 2 轮查询 */
t
′
16. 读取桶 i 1 中的所有指纹和迁移计数器 ;
1
t
′
17. 读取桶 i 2 中的所有指纹和迁移计数器 ;
2
18. if (桶 i 1 中有指纹 f)
19. if (使用比较并交换操作写入删除指纹后的桶失败)
20. continue;
21. return TRUE;
i 2 中有指纹 f)
22. if (桶
23. if (使用比较并交换操作写入删除指纹后的桶失败)
24. continue;
25. return TRUE;
26. /*注释: 判断是否需要重试*/
27. if ( t ⩾ t 1 +2 & t ⩾ t 2 +2 & t ⩾ t 1 +3)
′
′
′
1 2 2
28. continue;
29. else
30. return FALSE;
删除操作时间复杂度分析如下. 当删除操作未发生重试时, 无锁并发布谷鸟过滤器只需读写两次两个候选桶
即可. 因此, 当未发生重试时, 无锁并发布谷鸟过滤器删除操作的时间复杂度与标准布谷鸟过滤器相同, 均为 O(1).
O(r), 其
若删除操作发生重试, 和查询操作的分析方法相同, 无锁并发布谷鸟过滤器删除操作的时间复杂度也为
中 r 为重试次数. 通过第 3.5 节的理论分析表明删除操作的进展性也为无锁, 即任何时刻至少有一个线程不会无限
重试 (详见第 3.5 节).

3.4 正确性分析
性质 1. 查询操作是可线性化的.
若查询操作在两阶段查询过程中发现与待查询元素匹配的指纹, 则读对应的哈希桶指令可作为查询操作的可
线性化点. 除此之外, 当且仅当待查询元素的指纹在访问哈希桶的间隙中被多次迁移时, 两阶段查询过程无法发现
该指纹. 但是由于每次指纹迁移成功后, 参与迁移的两个哈希桶的迁移计数器值至少增加 1. 因此当两阶段查询没
有发现元素对应的指纹时, 通过检查迁移计数器即可识别此类情况. 之后, 触发重试直到找到待查询元素的指纹为
止. 需要注意, 通过迁移计数器判断是否需要重试, 可能会将不需要重试的情况误报为需要重试. 例如在第 1 和第 2