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

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

吐以及数据处理能力, 对提升系统性能意义重大 [3,18−21] .
但是, 设计支持高并发的布谷鸟过滤器十分困难. 其难点主要包括以下两个方面: (1) 正确性. 设计正确的并发
数据结构充满挑战. 具体来说, 当多个线程并发地修改同一块数据时, 若不采取合适的同步方案保障操作的原子
性, 一个线程可能会读取到另一线程修改操作的中间状态, 使得多线程程序的运行结果完全不可预测. 此外, 编译
器指令重排、处理器乱序执行以及数据缓存产生的线程间可见性问题使得多线程程序难以分析. 因此, 为保证正
确性, 多线程程序需要仔细设计并分析同步机制以确保数据一致和线程协调. (2) 扩展性. 设计具有高扩展性 (即吞
吐随并发线程数量增加而线性或亚线性增加) 的并发数据结构充满挑战. 具体来说, 如果使用全局锁来保证数据结
构在多线程并发场景下的正确性, 同一时刻只有一个线程能获得全局锁. 这造成所有线程只能依次执行. 因此, 使
用全局锁的数据结构的吞吐无法随线程数量增长而提升 [22,23] . 如果使用细粒度锁来保证数据结构在多线程并发场
景下的正确性, 多个线程可以同时执行. 但是由于不同线程之间存在锁竞争以及上下文切换开销, 当并发执行的线
程数量较多时, 使用细粒度锁的数据结构的吞吐难以进一步提升 [24−26] .
为解决上述问题, 本文提出了支持无锁并发的布谷鸟过滤器. 此过滤器通过本文提出的两阶段查询协议、路
径探查与元素迁移分离、基于多机器字比较并交换的原子迁移实现线程安全的查询、插入和删除操作. 理论分析
和实验结果表明, 无锁并发的布谷鸟过滤器显著提升了现有最新算法的并发性能.
本文第 1 节介绍并发过滤器的研究现状. 第 2 节介绍本文所需的基础知识, 包括布谷鸟过滤器以及无锁并发
技术. 第 3 节介绍本文提出的无锁并发布谷鸟过滤器. 第 4 节通过实验验证所提方法的有效性. 最后总结全文.

1 相关工作

1.1 过滤器数据结构概述
过滤器数据结构可以近似地判断一个元素是否存在于给定集合中. 过滤器数据结构主要可分为两类: 基于位
图的过滤器和基于指纹的过滤器.
基于位图的过滤器主要包括布隆过滤器及其变体 [27,28] . 布隆过滤器由一个长度为 m 比特的位图数组以及 个
k
k 个哈希函数的计算结果, 将位图中 个比特位设置为 1. 布隆过滤器
k
哈希函数组成. 布隆过滤器的插入操作根据
k
k
的查询操作根据 k 个哈希函数的计算结果, 查询位图中的 个比特位. 若 个比特位均为 1, 则返回该元素存在于
已插入元素的集合中. 此外, 布隆过滤器不支持删除操作.
基于指纹的过滤器主要包括布谷鸟过滤器及其变体 [29,30] . 不同于布隆过滤器通过将元素映射到位图数组中的
f 位指纹 f 位片段) 来保存元素. 这一设
k 个比特位来保存元素, 布谷鸟过滤器通过保存元素的 (即元素哈希值的
计使得基于指纹的过滤器可以支持删除操作. 例如, 布谷鸟过滤器由一个具有若干哈希桶的指纹哈希表组成. 布谷
鸟过滤器的插入操作会将元素的指纹保存到指纹哈希表中. 查询操作通过查询指纹哈希表中是否存在待查询元素
的指纹近似地判断待查询元素是否存在. 布谷鸟过滤器的删除操作会将待删除元素的指纹从指纹哈希表中移除.
注意, 本文将在第 2.1 节中详细介绍布谷鸟过滤器的插入、查询和删除操作.

1.2 并发过滤器及其他相关并发数据结构
现有的过滤器主要使用锁支持并发. 多线程布隆过滤器 [31] 将细粒度锁应用于布隆过滤器中, 以提升其多核可
扩展性. 向量商过滤器 [32] 将布谷鸟哈希替换为 power-of-two-choices 哈希, 并将哈希桶替换为商过滤器 [33] . 之后,
向量商过滤器使用桶级别的细粒度锁实现了较高的并发扩展性. 计数商过滤器 [34] 在商过滤器基础上通过增加让
多个指纹槽共享一个互斥锁的设计提升了多线程性能. 据我们所知, 目前支持并发的过滤器均使用锁实现并发. 由
于不同线程之间存在锁竞争, 这不可避免地造成当并发线程数较多时产生性能瓶颈. 本文提出的无锁并发布谷鸟
过滤器可以避免锁竞争产生的开销, 从而缓解当并发线程数较多时性能难以继续提升的问题.
并发技术也广泛应用于其他非过滤器数据结构中, 如哈希表 [22] 、B-树 [35,36] 、自适应前缀树 [37] 等. 其中, 与过滤
器数据结构最相关的是哈希表数据结构. 例如, 细粒度锁布谷鸟哈希表 [22] 为若干个连续的哈希桶设置一个锁, 通
过细粒度锁实现并发. 无锁并发布谷鸟哈希表 [38] 针对哈希桶内仅存在一个插槽的特殊情况提出基于 CAS 指令的