无锁并发布谷鸟过滤器
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP393

基金项目:

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


Lock-free Concurrent Cuckoo Filter
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    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.

    参考文献
    相似文献
    引证文献
引用本文

王瀚橙,陈志鹏,戴海鹏,顾荣,KIM Chaewon,陈贵海.无锁并发布谷鸟过滤器.软件学报,,():1-20

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2023-10-13
  • 最后修改日期:2024-02-12
  • 录用日期:
  • 在线发布日期: 2024-06-20
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号