Data Science and Engineering (DSE)是由中国计算机学会(CCF)主办，数据库专业委员会承办，施普林格·自然(Springer Nature)集团出版的开放获取(OA)期刊。本篇文章精选自DSE最新一期发文，得到中新赛克赞助文章处理费。

文章介绍

在大数据时代，越来越多的服务需要摄取大量、快速、多样的数据，如社交网络数据、智能手机应用使用数据、点击数据等。NoSQL数据库是作为关系数据库的可伸缩性和灵活性更好的替代品而开发的。超空间哈希作为索引结构应用于NoSQL数据库，通过将具有多个属性的对象映射到多维空间来构建索引。除了主键之外，它还可以加速处理一些辅助属性的查询。近年来，GPU丰富的计算资源为实现高性能的超空间哈希提供了机会。

越来越多的研究开始关注用GPU来加速索引结构(B+树、LSM、哈希、跳表等)操作性能，但存在资源利用率低、内存性能差以及通用性不够等问题。目前通用GPU数据结构的研究是有限的，特别具有挑战性的是开发可以在GPU上构建、查询和更新的动态(可变)数据结构。

本文为GPU构造了一个完全并发的动态超空间哈希表，主要完成了以下工作：

(1)提出了一种新的超空间哈希数据结构GHSH(GPU HyperSpace Hashing)，使超空间哈希能更加适合GPU并行架构。在GHSH中，使用数组结构体代替传统的结构体数组布局，其中键、辅助属性和值分别存储。该数据结构更适合GPU的内存层次结构，具有良好的缓存局部性，避免了访问不相关的辅助属性。

(2)本文使用哈希桶级同步，通过原子操作保证一致性，节省了加锁开销。在此基础上，通过模糊读取对读操作进行优化。

(3)本文还提出了一种warp预组合数据共享策略，即在数据共享之前对线程任务进行预组合，以获得高并行加速。

(4)在上述设计的基础上，本文进一步描述了GHSH如何处理批量更新场景中的常见操作，包括批量构建、按键搜索、按辅助属性搜索、修改、插入和删除。

(5)超空间哈希的性能很大程度上取决于超空间的属性配置，不合适的配置会显著影响GHSH的性能。因此，在给定的工作负载和部署设置下，本文设计了代价模型和系统架构，自适应调整空间属性的配置，自主地最大化GHSH的性能。

在Nvidia RTX2080Ti GPU上的实验表明，GHSH的性能比CPU上的同类要快20-100倍。与不能对非主键属性进行查询的其他GPU哈希相比，GHSH的构建和检索性也都与之相当。GHSH支持这些额外操作的性能成本是适中的。在复杂的混合负载中，GHSH有着良好的并发性能。

实验效果

本文评估了基于WCWS、CBB和WPDS (CBB+ PBQ)三种策略基本的查询操作性能。结果如图1所示，使用CBB可以大大提高搜索效率，但CBB作为预处理需要额外的时间。只有使用PBQ才能达到更好的优化效果，平均加速1.25倍。值得注意的是，如果在没有CBB的情况下直接执行PBQ，那么在warp中的分支分歧是无法避免的，因此在warp中的线程是无法并行的。

图1. WPDS的影响

图2表明了本文设计的数据结构和三种技术的有效性。假设所有的修改都需要更换哈希桶，本文发现GHSH数据结构可以实现3.92倍的性能提升。根据本文的数据结构，在用全局内存和原子操作替换锁后，GHSH的桶变化率平均显著提高了27%。这是因为原子操作大大降低了锁的成本。在无锁版本中加入模糊读取策略，这两种技术可以提高34%的修改率。但随着元素数量的增加，由于SM数量的限制，加速效应并不明显。

图2. 修改速率

本文比较了GHSH和CPU上对应的GHSH的速度。由于在集中式的环境中没有开源的并发CPU超空间哈希，本文实现了基于openMP的超空间哈希。实验结果表明，在CPU上，8个线程的构建效果最好，12个线程的辅助属性搜索效果最好。因此，本文使用这些设置作为与GHSH进行比较的基准。为了在CPU和GPU上评估超空间哈希的批量构建和搜索操作，本文对多个数据结构大小进行增量评估。选择了一个初始的存储桶数量，以便最终的内存利用率是60%。表1中报告了给定批次大小b的所有操作率的平均值。GPU上的平均构建速率均值为20.24M /s，是CPU的20倍。GPU的平均搜索速率为28.17M /s，是CPU的100倍。

表1. GPU和CPU上不同批大小的插入和查询速率(M操作次数/秒)

（1）图3(a)显示了构建速率(M个/秒)与表中总元素数(n)的关系。当表的大小非常小时，CUDPP的构建性能特别高，因为大多数原子操作都可以在缓存级别完成。与另外支持增量可变操作的结构相比，静态数据结构通常能够维持更好的批量构建和查询速率。然而，GHSH中这些额外操作的成本是适中的。Slab Hash和GHSH会使GPU资源达到2²⁰≤n≤2²⁴。GHSH的构建速率是Slab Hash的1.32倍，因为GHSH的基本节点存储的数据几乎是Slab Hash的两倍。此外，GHSH中的数据分配可以并行进行，提高了数据的并行性。

（2）查询：对于主键搜索查询，本文生成两组随机查询:1)search-all：所有查询都存在于GHSH中；2)search-null：查询结果不存在。这两种查询分别表示最好和最坏的可能。search-all和search-null的调和平均值分别为838 M/s和732 M/s(见图3(b))。对于批量构建、search-all和search-null，CUDPP相比GHSH的加速分别为1.27x、1.16x和0.86x；Slab Hash相比GHSH上的加速分别是0.84x, 1.01x和1.02x。GHSH的主键查询速度略低于Slab Hash，这是GHSH支持非主键查询的代价。值得一提的是，辅助属性查询必须遍历完整的链表，这相当于键查询的最差情况。

图3(a) 构建速率                           图3(b) 查询速率

图3. 性能与存储元素的总数

（3）增量插入：假设周期性地向哈希表添加一批新元素。对于CUDPP来说，这意味着每次都要从零开始。对于Slab Hash和GHSH，这意味着动态地向相同的数据结构中插入新元素。图4显示了插入不同大小(32k、64k和128k)的新批的两种方法，直到哈希表中存储了200万个元素。对于CUDPP，本文使用固定的60%负载系数。对于Slab Hash和GHSH，本文选择初始设定哈希桶数，以便它的最终内存利用率(插入所有批次后)是60%。正如预期的那样，GHSH对于128k、64k和32k大小的批处理，最终的加速达到了18.3x、27.3x和32.5x，大大超过了CUDPP。随着插入的批的数量增加，性能差距也会增加。相比之下，GHSH对Slab Hash的性能提升效果不如CUDPP明显。对于128k、64k和32k的批处理，相比Slab Hash 而言，GHSH的最终加速分别为2.8x、2.4x和1.8x。

图4. 增量插入性能

图5显示了GHSH在三种不同场景和不同主键区间下的性能。由于更新在计算上比搜索更昂贵，因此给定固定的内存利用率，更新越少性能越好。从实验结果可以看出，键值范围对性能的影响并不大。

图5. GHSH的并发性能

结语

通过对超空间哈希特性和GPU特性的综合分析，本文发现了超空间哈希与GPU之间存在的一些差距，如内存访问需求的差距、内存分歧、查询分歧等。在此基础上，本文提出了一种新的超空间哈希数据结构，其中查询属性是单独存储的。因此，GHSH可以充分利用GPU的内存层次结构，通过GPU上的缓存访问来减少高延迟内存访问的次数。本文还提出了GHSH的三种优化来缓解GPU上的不同分歧，以提高资源利用率：warp预组合数据共享策略、使用原子操作代替锁定的方法和模糊读取策略。实验结果表明，本文的GPU动态超空间哈希表在灵活性和性能上都有优势。

作者简介

任卓，东北大学计算机科学与工程学院硕士研究生，主要研究方向为GPU并行计算。

谷峪，东北大学计算机科学与工程学院教授，主要研究方向主要研究方向为大数据分析、分布式并行计算、时空和图数据管理。

李传文，东北大学计算机科学与工程学院副教授，主要研究方向为时空数据和位置服务、大数据管理、分布式并行计算。

期刊简介

Data Science and Engineering（DSE）是由中国计算机学会（CCF）主办、数据库专业委员会承办、施普林格 自然（Springer Nature）出版的Open Access期刊。为了迎合相关领域的快速发展需求，DSE致力于出版所有和数据科学与工程领域相关的关键科学问题与前沿研究热点，以大数据作为研究重点，征稿范畴主要包括4方面：（1）数据本身，（2）数据信息提取方法，（3）数据计算理论，和（4）用来分析与管理数据的技术和系统。

目前期刊已被ESCI与SCOPUS收录，CiteScore2020为4.9，在Computer Science Applications领域排名#181/693（73^rd Percentile）。稿件处理费由赞助商中新赛克（Sinovatio）承担，欢迎大家免费下载阅读期刊全文，并积极投稿。

原文链接：https://link.springer.com/article/10.1007%2Fs41019-021-00161-5