使用HTM扩展争用下的并发索引结构

发布时间:2022-05-09浏览次数:96

项目背景:

      硬件事务性内存(HTM)是一种新兴的硬件功能。HTM简化了并发程序的编程模型,同时保持了高性能和可扩展性。随着HTM处理器的商用,HTM最近被用于构造高效的并发索引结构。然而,随着数据量和用户数量的扩大,数据管理系统必须处理表现出高度竞争的工作负载;同时,传统的基于HTM的并发索引结构无法在高度满足的工作负载下提供可伸缩的性能,严格限制了HTM在数据管理系统上的使用。

项目成果:

      我们首先对基于HTM的并发索引结构进行了深入的分析,并揭示了由于争用下的假冲突和真冲突而导致HTM异常中止的几个原因。在分析的基础上,我们提出了Eunomia,这是一种基于HTM的并发索引结构的设计模式,它包含几个提高HTM性能的原则,包括使用基于版本的并发控制拆分HTM区域以减少HTM工作集,分区数据布局以减少错误冲突,主动检测和避免冲突请求,以及自适应并发控制策略。为了验证它们的有效性,我们应用这些设计原则构建了一个可伸缩的并发B+树和一个使用HTM的跳过列表,其中可伸缩并发B+树的结构设计如图1所示,把索引阶段和操作阶段将单个HTM区域划分为多个部分,每个部件分别用HTM机制保护不同部件的原子性。并采用基于版本的方案,以保证不同HTM区域之间边界的整体一致性。在一台支持HTM20核多核机器上使用键值存储和数据库基准进行评估。实验表明,Eunomia在高竞争条件下会带来显著的加速,而在低竞争条件下会产生较小的开销。具体结果参考论文[2]


 1. 基于Eunomia B+树结构

发表论文:

[1] Wang X, Zhang W, Wang Z, Wei Z, Chen H, Zhao W. Association for Computing Machinery, 2017. Eunomia: Scaling Concurrent Search Trees under Contention Using HTM[C]//Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. , 2017New York, NY, USA: : 385–399.

[2] Zhang W, Wang X, Ji S, Wei Z, Wang Z, Chen H. Eunomia: Scaling Concurrent Index Structures Under Contention Using HTM[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 29(8): 1837–1850.