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

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

13. if (K-CAS 成功更新源哈希桶和目标哈希桶中的指纹和迁移计数器)
14. return TRUE;
15. else
16. return FALSE;
17. else
18. return FALSE;

K-CAS 操作可原子地将一个指纹从哈希桶 i 1 迁移到哈希桶 i 2 中. 具体来说, 若线程 T 1 正在执行指纹迁移操
作, 则该线程需要完成如下 3 个步骤: (1) 线程 T 1 首先原子地将哈希桶 i 1 的值标记为特殊值 V T1 . 若标记成功, 则其
他需要读写哈希桶 i 1 的线程将停止读写哈希桶 i 1 并协助线程 T 1 完成线程 T 1 的后续步骤 (步骤 (2) 和步骤 (3)). 如
果标记失败, 则线程 T 1 不会对哈希桶 i 1 进行任何修改, 从而保证原子性. (2) 当哈希桶 i 1 被线程 T 1 标记成功后, 线
程 T 1 将会再次原子地将哈希桶 i 2 的值标记为特殊值 V T1 . 如果再次标记成功, 此时, 其他任何读写哈希桶 i 1 和 i 2
的线程均只能协助 T 1 线程完成 T 1 线程的第 3 步. 如果标记失败, 线程 T 1 会还原哈希桶 i 1 的值. 还原后线程 T 1 没
有对哈希桶 i 1 和哈希桶 i 2 进行任何修改, 从而保证原子性. (3) 当哈希桶 i 1 和哈希桶 i 2 均被标记为特殊值 V T 后,
1
此时, 其他所有需要读写哈希桶 i 1 或 i 2 的线程均只能协助线程 T 1 修改这两个哈希桶. 即, 这些线程只能执行线程
T 1 将要执行的修改操作, 并且只有在 T 1 所需修改全部完成后, 才能切换回先前程序运行的上下文继续读写这两个
哈希桶. 基于上述机制, 其他需要读写这两个哈希桶的线程在其程序运行上下文中只能读取到 T 1 线程开始修改两
个哈希桶前或修改两个哈希桶后的哈希桶值. 因此, 从其他线程视角看, 这两个哈希桶的修改是原子的. 综上所述,
基于多机器字比较并交换的原子迁移技术可以保证指纹迁移操作只存在两种结果: 其一为指纹迁移完全成功 (步
骤 (3)), 其二为不对哈希桶执行任何修改 (步骤 (1)、步骤 (2)). 即, 其他线程在他们的程序运行上下文中只能读取
到 T 1 开始修改前或修改后的值, 因此可保证操作的原子性.
上述说明的一个简单示例如下, 假设线程 T 1 需要将指纹从哈希桶 i 1 迁移到哈希桶 i 2 , 线程 T 2 需要读取两个
哈希桶的值. 使用 K-CAS 操作后, 实际执行过程为: (1) 假设线程 T 1 抢先将哈希桶 i 1 的值标记为特殊值. (2) 当线
程 T 2 读取到被标记的哈希桶 i 1 时, 线程 T 2 将暂停对哈希桶 i 1 的读取, 并转而代替线程 T 1 完成对哈希桶 i 2 的标记
以及对哈希桶 i 1 和 i 2 的写入操作. (3) 当线程 T 2 协助线程 T 1 完成写入后, 线程 T 2 才能继续读取哈希桶 i 1 和 i 2 的
值. 即, 线程 T 2 最终读取到的是写入完成后的值, 而非修改期间可能出现的值, 因此保证了原子性.
插入操作时间复杂度分析如下. 相较于标准布谷鸟过滤器, 无锁并发布谷鸟过滤器的插入操作主要引入了 K-CAS
多字节比较并交换操作. 当插入操作不产生重试时, 由于 K-CAS 操作本身并不增加插入操作的时间复杂度, 无锁
O(1). 若插入操作发生重试, 无
并发布谷鸟过滤器的插入时间复杂度和标准布谷鸟过滤器的插入时间复杂度同为
O(r), 其中 为重试次数. 本文通过第 3.5 节的理论分析表明插入
r
锁并发布谷鸟过滤器插入操作的时间复杂度为
操作的进展性为无锁, 即任何时刻至少有一个线程不会无限重试 (详见第 3.5 节).

3.3 删除操作
无锁并发布谷鸟过滤器的删除操作如算法 5 所示. 无锁并发布谷鸟过滤器的删除操作在查询操作的基础上增
加了找到待删除指纹后使用 CAS 操作删除指纹的过程 (第 8, 12, 19, 23 行).

算法 5. 无锁并发布谷鸟过滤器的删除操作.
输入: 一个字符串类型的变量 e, 其中 e 表示待删除的元素;
输出: 一个布尔类型的变量 TRUE 或 FALSE. 其中, 输出 TRUE 表示删除成功, 即成功从布谷鸟过滤器中删除给定
元素 e; 输出 FALSE 表示删除失败, 即未成功从布谷鸟过滤器中删除给定元素 e.

1. 计算元素指纹 f = h f (e);
2. 计算元素对应的两个候选桶地址 i 1 = h i (e) 和 i 2 = h i (e)⊕h i ( f);