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

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

该哈希桶中是否存在空插槽. 若哈希桶中存在空插槽, 则成功搜索到可行路径并结束路径探查 (第 10–12 行).
否则, 将该哈希桶中每个指纹对应的另一候选桶的相关信息插入到队列中 (第 13, 14 行), 并继续寻找可行迁移
路径. 找到可行迁移路径后, 首先使用图 3 中存储的信息解码可行迁移路径 (第 16, 17 行). 之后反向遍历可行
迁移路径, 对于可行迁移路径中的每个元素, 首先寻找该元素的源哈希桶对应的目标哈希桶 (第 20–27 行). 若
目标桶中无空槽则需要重试搜索路径. 这是因为在执行元素迁移操作过程中, 已探查到的可行迁移路径可能被
其他并发执行插入操作的线程破坏. 此时, 元素迁移操作无法继续执行, 需要重新执行路径探查操作以获得新
的可行迁移路径. 若目标桶中有空槽, 则可直接进行一次指纹原子迁移 (第 28 行). 下文将详细介绍指纹原子迁
移过程.

0 1 3 5 31
迁移路径起始 迁移路径第 1 个 迁移路径第 2 个 …
哈希桶标识 指纹槽下标 指纹槽下标
图 3 使用一个 32 位定长整数编码迁移路径

在执行元素迁移操作过程中 (算法 3 第 28 行), 每个指纹从源哈希桶迁移到目标哈希桶的过程需要保证是原
子的 [44] . 如果简单地将迁移步骤拆分为两个 CAS 操作 (先在目标哈希桶中插入指纹, 再将源哈希桶中指纹删除),
则在某一时刻会出现源哈希桶和目标哈希桶中指纹都存在的中间状态. 若有并发的删除操作在此中间状态执行,
此时本应被删除的指纹将仍然存在于过滤器中, 导致后续查询操作仍然认为该元素是集合成员, 与预期的删除操
作语义不符.
为解决这一问题, 本文提出了基于多机器字比较并交换 (K-CAS) 的原子迁移技术, 该技术使用 K-CAS 操作
原子地更新两个哈希桶, 使得无锁并发布谷鸟过滤器能在目标哈希桶与源哈希桶间原子地迁移指纹. 具体来说, 单
次指纹迁移操作如算法 4 所示. 该操作首先读取源哈希桶索引并判断待迁移指纹是否仍然存在, 以防止待迁移指
纹在迁移前被其他执行删除操作的线程删除 (第 2–4 行). 若待迁移指纹存在, 则继续读取目标哈希桶, 并判断目标
哈希桶中是否有空指纹槽 (第 6–11 行). 若有空指纹槽, 则计算更新后的源哈希桶和目标哈希桶值, 并使用 K-CAS
操作原子地更新两个哈希桶 (第 12 行).

算法 4. 无锁并发布谷鸟过滤器的单次指纹迁移操作.
输入: 两个整数类型变量: 源哈希桶索引以及待迁移指纹所在指纹槽下标;
输出: 一个布尔类型的变量 TRUE 或 FALSE. 其中, 输出 TRUE 表示操作成功, 即成功完成单次指纹迁移; 输出
FALSE 表示操作失败, 即未成功完成单次指纹迁移.
1. while (TRUE)
2. 读取源哈希桶中的所有指纹;
3. if (待迁移指纹已不存在)
4. return FALSE;
5. /*注释: 读取目标哈希桶*/
6. 计算目标哈希桶的索引;
7. 读取目标哈希桶中的所有指纹;
8. /*注释: 若目标桶可以容纳待迁移指纹则开始迁移指纹*/
9. if (源哈希桶和目标哈希桶索引不相等并且目标哈希桶中有空插槽)
10. if (源哈希桶中的数据发生了改变)
11. continue;
12. 使用 K-CAS 更新源哈希桶和目标哈希桶中的指纹和迁移计数器.