软件学报

作者：王瀚橙，陈志鹏，戴海鹏，顾荣，KIMChaewon，陈贵海

单位：王瀚橙，南京大学 计算机学院, 江苏 南京 21002311,陈志鹏，南京大学 计算机学院, 江苏 南京 21002302,戴海鹏，南京大学 计算机学院, 江苏 南京 21002303,顾荣，南京大学 计算机学院, 江苏 南京 21002304,KIMChaewon，南京大学 计算机学院, 江苏 南京 21002305,陈贵海，南京大学 计算机学院, 江苏 南京 21002306

关键词：布谷鸟过滤器;并发;近似成员资格查询;概率数据结构;计算机网络

基金：国家自然科学基金(62272223); 江苏省高层次双创计划; 软件新技术与产业化协同创新中心(南京大学)支持项目

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

来源：2025年第7期

《软件学报》期刊编辑部

查看软件学报杂志2025年第7期