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