作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 先进计算与数据处理 • 上一篇    下一篇

基于低冲突帮助机制的快速无等待哈希表算法

李鹏飞,张坤龙,康超凡   

  1. (天津大学计算机科学与技术学院,天津 300072)
  • 收稿日期:2014-10-05 出版日期:2015-11-15 发布日期:2015-11-13
  • 作者简介:李鹏飞(1990-),男,硕士研究生,主研方向:并发数据结构,数据库技术;张坤龙,副教授、博士;康超凡,硕士研究生。
  • 基金资助:
    国家自然科学基金资助项目(61303021);水利部公益性行业科研专项基金资助项目(201401033)。

ast Wait-free Hash Table Algorithm Based on Low-conflict Help Mechanism

LI Pengfei,ZHANG Kunlong,KANG Chaofan   

  1. (School of Computer Science and Technology,Tianjin University,Tianjin 300072,China)
  • Received:2014-10-05 Online:2015-11-15 Published:2015-11-13

摘要: 针对现有无等待哈希表算法未充分利用哈希表的固有并行性,造成线程之间存在高冲突和高冗余的问题,提出一种快速无等待哈希表算法。利用可冻结集合思想简化哈希表操作,采用CAS原子指令保证插入、删除与查找操作均为无等待。根据哈希表结构改进帮助机制 ,使得哈希桶的实现为无等待,只有在扩展哈希表时哈希桶之间才提供帮助。实验结果表明,该算法能降低线程操作间的冲突,提高帮助操作的并行度,当查找率为0、键值范围为0~256且线程数为8时,其吞吐率是现有无等待哈希表算法的2.5倍。

关键词: 并发数据结构, 哈希表, 无等待, 可线性化, 可扩展

Abstract: Existing wait-free hash table algorithms do not take full advantage of the inherent parallelism of hash table,which results in the high redundancy and conflict between threads.In order to solve the problem,this paper proposes a fast wait-free hash table algorithm.It makes use of the freezable set to simplify the operations of hash table.And the Compare and Swap(CAS) primitive is applied to realize the wait-free of insertion,deletion and search operations.It improves the help mechanism based on the structure of hash table to realize the wait-free of hash buckets.In order to avoid the conflics between the operations on different buckets,the help is given only when the hash table extends.Experimental results show that the algorithm can reduce the conflict between thread operation,and improve the parallelism of help operation.When the percentage of lookup is 0,the data range is 0~256 and the thread number reaches 8,throughput of the proposed algorithm is 2.5 times than the existing wait-free hash table algorithm.

Key words: concurrent data structure, hash table, wait-free, linearizability, extensibility

中图分类号: