| 摘要: |
| 布谷鸟过滤器是一种高效的概率型数据结构, 该数据结构可以快速判断某个元素是否存在于给定集合中, 被广泛应用于计算机网络、物联网应用以及数据库系统中. 在实践中, 上述系统通常需要处理海量数据以及大量并发请求. 实现支持高并发的布谷鸟过滤器可以显著提升系统吞吐以及数据处理能力, 对提升系统性能至关重要. 为此, 设计一个支持无锁并发的布谷鸟过滤器. 该过滤器通过所提出的两阶段查询、路径探查与元素迁移分离, 以及基于多机器字比较并交换的原子迁移技术实现高性能的查询、插入和删除操作. 理论分析和实验验证结果均表明, 无锁并发布谷鸟过滤器显著提升现有最先进算法的并发性能. 无锁并发布谷鸟过滤器的查询吞吐量, 平均为使用细粒度锁的布谷鸟过滤器的查询吞吐量的1.94倍. |
| 关键词: 布谷鸟过滤器 并发 近似成员资格查询 概率数据结构 计算机网络 |
| DOI：10.13328/j.cnki.jos.007214 |
| 分类号:TP393 |
| 基金项目:国家自然科学基金(62272223); 江苏省高层次双创计划; 软件新技术与产业化协同创新中心(南京大学)支持项目 |
|
| 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 |
