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

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

14. if (使用比较并交换操作写入失败)
15. continue;
16. return TRUE;
17. 根据桶 i 1 和 i 2 开始执行路径探查和元素迁移操作;
18. /*注释: 如果无法找到可行路径, 则对过滤器进行扩容, 直到插入成功*/
对于单线程场景, 标准布谷鸟过滤器指纹移动所涉及的路径探查和指纹迁移过程是紧密耦合的. 具体来说, 若
某个指纹 f 从一个候选桶 (例如, 桶 i 1 ) 中被踢出后, 在其另一个候选桶 i 2 中没有发现空插槽, 此时插入操作会随机
′
′
踢出候选桶 i 2 中的某个插槽中的指纹 (例如, 桶 f ) 以产生一个空插槽来存储被踢出的指纹. 被踢出的指纹 f 将重
复上述流程, 直到在另一个候选桶中找到能够直接存储该指纹的空插槽为止. 图 2(a) 给出了上述过程的一个示例.
< f 3 , f 4 > 中. 之后执行元
标准布谷鸟过滤器以桶 < f 1 , f 2 > 为起点, 首先执行路径探查操作发现指纹 f 1 可迁移到桶
素迁移操作, 将指纹 f 3 踢出用于存放指纹 . 指纹 f 3 被踢出后, 标准布谷鸟过滤器再次执行路径探查操作发现被
f 1
踢出的指纹 f 3 可迁移到桶 < f 5 , f 6 > 中并再次执行元素迁移操作. 简言之, 标准布谷鸟过滤器的插入操作需要交替
执行路径探查和指纹迁移过程, 造成路径探查和指纹迁移过程紧密耦合.

f 7 f 8
f 1 f 2
f 1 f 2
f 3 f 4 f 7 f 8
f 3 f 4
f 5 f 6
f 5 f 6 f 9 f 10
f 9 f 10
(a) 单线程标准布谷鸟过滤器 (b) 无锁并发布谷过滤器使
使用深度优先方法以桶<f 1 , f 2 > 用广度优先方法以桶<f 1 , f 2 >
为起点探查布谷鸟逐出路径 为起点探查布谷鸟逐出路径
图 2 单线程标准布谷鸟过滤器和无锁并发布谷鸟过滤器路径探查过程对比

但是, 对于多线程并发场景, 直接使用上述方案存在两点问题: (1) 路径探查和指纹迁移紧密耦合会导致插入
过程中存在某些指纹被暂时踢出数据结构, 当一个插入线程将指纹从哈希表中踢出且尚未将其写入到另一个候选
桶中时, 此刻指纹存储在线程本地内存空间中, 无法被其他线程获取. 若此时有其他执行查询操作的线程正在寻找
此指纹, 显然无法查询到该元素, 继而产生假阴性. (2) 路径探查和指纹迁移紧密耦合使得标准布谷鸟过滤器的路
径探查操作不得不基于深度优先方法进行搜索. 然而深度优先方法相比于广度优先方法探查到的逐出路径更长,
造成多线程插入时不同写入线程冲突加剧, 继而难以获得性能提升.
为解决上述问题, 本文提出了路径探查与元素迁移分离技术. 该技术首先使用广度优先方法进行路径探查, 当
探查到可行逐出路径后再执行元素迁移. 如图 2(b) 所示, 无锁并发布谷鸟过滤器以桶 < f 1 , f 2 > 为起点, 通过广度

优先搜索首先计算出指纹 f 1 和指纹 f 2 的候选桶分别为桶 < f 3 , f 4 > 和桶 < f 7 , f 8 >. 由于上述两桶中均没有空插槽,
f 3 f 4 f 7 f 8 的候选桶. 并可探查到一条长度为
无锁并发布谷鸟过滤器继续使用广度优先搜索计算指纹 , , , 3 的指纹
f 2 ⇒ f 7 ⇒< empty >. 由于使用广度优先搜索可获得最短的逐出路径, 因此这一设计缓解了标准布谷鸟过
逐出路径
滤器深度优先搜索造成迁移路径过长的问题 (简言之, 这一设计可缓解问题 (2)).
基于这一设计, 无锁并发布谷鸟过滤器实现了在不迁移元素的前提下探查路径. 当找到一条可行的指纹迁
移路径后, 无锁并发布谷鸟过滤器开始执行元素迁移操作: 无锁并发布谷鸟过滤器将从可行迁移路径的最后一
个桶开始, 反向遍历路径, 逐步将空插槽移动到待插入元素的候选桶中. 此设计解决了其他执行查询操作的线
程因无法访问到迁移过程中被暂时踢出数据结构的指纹从而产生假阴性的问题 (简言之, 这一设计可解决问
题 (1)).
路径探查与元素迁移分离技术的伪代码如算法 3 所示. 具体来说, 路径探查操作首先向队列中插入广度优