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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(7):3339−3357 [doi: 10.13328/j.cnki.jos.007214] [CSTR: 32375.14.jos.007214] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
无锁并发布谷鸟过滤器

王瀚橙, 陈志鹏, 戴海鹏, 顾 荣, KIM Chaewon, 陈贵海

(南京大学 计算机学院, 江苏 南京 210023)
通信作者: 戴海鹏, E-mail: haipengdai@nju.edu.cn; 陈贵海, E-mail: gchen@nju.edu.cn

摘 要: 布谷鸟过滤器是一种高效的概率型数据结构, 该数据结构可以快速判断某个元素是否存在于给定集合中,
被广泛应用于计算机网络、物联网应用以及数据库系统中. 在实践中, 上述系统通常需要处理海量数据以及大量
并发请求. 实现支持高并发的布谷鸟过滤器可以显著提升系统吞吐以及数据处理能力, 对提升系统性能至关重要.
为此, 设计一个支持无锁并发的布谷鸟过滤器. 该过滤器通过所提出的两阶段查询、路径探查与元素迁移分离, 以
及基于多机器字比较并交换的原子迁移技术实现高性能的查询、插入和删除操作. 理论分析和实验验证结果均表
明, 无锁并发布谷鸟过滤器显著提升现有最先进算法的并发性能. 无锁并发布谷鸟过滤器的查询吞吐量, 平均为使
用细粒度锁的布谷鸟过滤器的查询吞吐量的 1.94 倍.
关键词: 布谷鸟过滤器; 并发; 近似成员资格查询; 概率数据结构; 计算机网络
中图法分类号: TP393

中文引用格式: 王瀚橙, 陈志鹏, 戴海鹏, 顾荣, Kim C, 陈贵海. 无锁并发布谷鸟过滤器. 软件学报, 2025, 36(7): 3339–3357. http://
www.jos.org.cn/1000-9825/7214.htm
英文引用格式: Wang HC, Chen ZP, Dai HP, Gu R, Kim C, Chen GH. Lock-free Concurrent Cuckoo Filter. Ruan Jian Xue Bao/Journal
of Software, 2025, 36(7): 3339–3357 (in Chinese). http://www.jos.org.cn/1000-9825/7214.htm

Lock-free Concurrent Cuckoo Filter
WANG Han-Cheng, CHEN Zhi-Peng, DAI Hai-Peng, GU Rong, KIM Chaewon, CHEN Gui-Hai
(School of Computer Science, Nanjing University, Nanjing 210023, China)
Abstract: The cuckoo filter is an efficient probabilistic data structure that can quickly determine whether an element exists in a given set.
The cuckoo filter is widely used in computer networks, IoT applications, and database systems. These systems usually involve the handling
of massive amounts of data and numerous concurrent requests in practice. A cuckoo filter that supports high concurrency can significantly
improve system throughput and data processing capabilities, which is crucial to system performance enhancement. Therefore, a cuckoo
filter that supports lock-free concurrency is designed. The filter achieves high-performance lookup, insertion, and deletion through the two-
stage query, separation of path exploration and element migration, and atomic migration based on multi-word compare-and-swap.
Theoretical analysis and experimental results indicate that the lock-free concurrent cuckoo filter significantly improves the concurrent
performance of the most cutting-edge algorithms in current times. The lookup throughput of a lock-free concurrent cuckoo filter is on
average 1.94 times that of a cuckoo filter using fine-grained locks.
Key words: cuckoo filter; concurrency; approximate membership query; probabilistic data structure; computer network
布谷鸟过滤器是一种高性能的近似成员资格查询数据结构. 该数据结构可以快速判断某个元素是否存在于给
定集合中, 因而被广泛应用于流数据挖掘 [1,2] 、查询加速 [3,4] 、隐私保护 [5,6] 、智慧城市 [7] 、网络监测 [8] 、源代码漏
洞检测 [9] 、区块链 [10] 、无线传感器网络安全 [11] 、数据库系统 [12−16] 、缓存性能优化 [17] 等应用中. 在实践中, 上述应
用通常需要高效地处理海量数据以及大量并发请求. 设计并实现支持高并发的布谷鸟过滤器可以显著提升系统吞

* 基金项目: 国家自然科学基金 (62272223); 江苏省高层次双创计划; 软件新技术与产业化协同创新中心 (南京大学) 支持项目
收稿时间: 2023-10-13; 修改时间: 2024-02-12; 采用时间: 2024-04-11; jos 在线出版时间: 2024-06-20
CNKI 网络首发时间: 2024-06-21