Harmonia: A High Throughput B+tree for GPUs

发布时间:2023-01-05浏览次数:35

项目背景: 

B+树是最重要的数据结构之一,在各个领域得到了广泛的应用。随着并发查询和存储数据规模的增加,设计高效B+树结构变得至关重要。由于计算资源丰富,SIMD体系结构为B+树提供了实现高查询吞吐量的潜在机会。然而,由于资源利用率低和内存性能差,以前的方法无法获得令人满意的性能结果。

项目成果:

我们首先确定了B+树和SIMD体系结构之间的差距。并发B+树查询涉及许多全局内存访问和不同的差异,这与SIMD体系结构特征不匹配。基于这一观察,我们提出了Harmonia,一种新的B+树结构来弥补这些差距。Harmonia 架构设计如图1所示。

Figure 1. Harmonia架构

Harmonia中,B+树结构分为关键区域和子区域。关键区域按宽度优先顺序存储节点及其关键点。子区域被组织为一个前缀和数组,它只在关键区域存储每个节点的第一个子索引。由于前缀和子区域较小,并且子索引可以通过索引计算来检索,因此大部分子索引可以存储在片上缓存中,从而实现良好的缓存局部性。为了提高效率,Harmonia还包括两个优化:部分排序聚合(PSA)和缩小线程组遍历(NTG),分别如图2、图3所示。

对于PSA,我们在发出查询之前在时间窗口中对查询进行排序。由于相邻的排序查询更有可能共享相同的树遍历路径,因此当在SIMD单元中处理多个相邻查询时,合并内存访问的机会会增加。

Figure 2. PSA 搜索方法

对于NTG,我们减少了每个查询的线程数,以避免无用的比较。当每个查询的线程组缩小时,可以将更多查询合并到一个SIMD单元中,这可能会增加执行差异。为了缓解查询组合带来的执行分歧问题,我们设计了一个模型来决定如何缩小查询的线程组,进而缓解内存和执行差异,提高资源利用率。

Figure 3. NTG 搜索方法

      我们对Harmonia CPUGPU平台进行了评估。对28INTEL CPU的评估表明,Harmonia每秒可以实现2.07亿次查询,比基于CPUHB+Tree(最近最先进的B+tree设计方案)快约1.7倍。Volta TITAN V GPU上,它每秒可以实现36亿次查询,比基于GPUHB+Tree3.4倍。具体参考论文[1][2]


参考文献:

[1] Zhaofeng Yan, Yuzhe Lin, Lu Peng, Weihua Zhang. Harmonia: A High Throughput B+ Tree for GPUs. (PPoPP'19, CCF A)

[2] Weihua Zhang,Zhaofeng Yan,Yuzhe Lin,Chuanlei Zhao,Lu Peng. A High Throughput B+tree for SIMD architectures. (TPDS'20, CCF A)

源码链接:https://github.com/fudan-ppi/harmonia