基于GPU的HPGB+-Tree索引*

刘 军 冷芳玲 李宇轩

（1.东北大学信息化建设与网络安全办公室 沈阳 110819）（2.东北大学计算机科学与工程学院 沈阳 110819）

1 引言

具有强大算力的图形处理器GPU近些年的发展十分迅猛，GPU从其自身的架构出发，不断进行迭代更新以达到提升性能的目的。在GPU架构不断演进的过程中，NVIDIA公司所发布的每一代GPU新架构都会添加新特性，例如高传输效率的零拷贝技术等。这些特性使得运行在GPU上的程序更加易用，内部协同处理更加高效。在GPU推出伊始，编写GPU程序需要纹理编码等专业图形处理领域的专业知识，因此编码难度较高。但如今随着Nvidia公司推出CUDA［1］通用并行计算架构，图形卡上的编程难度逐渐降低，相关技术逐渐成熟，GPU被广泛应用于人工智能、深度学习、高性能计算、大数据处理等通用计算领域。近年来，在基于异构体系平台的数据库存储与管理方向的研究越来越受各界关注，已有不少成果应用于实际生产环境当中，例如Pgstorm凭借GPU强大的算力协同PostgreSQL数据库加速任务的执行，可以获得性能上的巨大提升。目前，GPU编程技术在数据库领域的应用还在不断探索阶段，切合GPU特性研究并实现的内存索引所取得的科研成果数量远远不及传统磁盘索引或基于CPU的主存索引，因此研究基于GPU的索引结构对加速数据查询是十分必要的。充分考虑CPU的硬件特点，并结合GPU强大的并行能力共同执行查询任务，以达到高效处理任务，降低查询延迟的目的。本文提出并实现的加速数据库查询的系统核心就是一种基于CPU与GPU协同处理的B+-Tree索引。

2 相关工作

索引是加速数据库查询的重要策略。针对索引的优化是加速数据查询速度最好的方式之一。构建基于GPU的树形索引是目前异构环境下加速数据库操作的主流方法之一。Rao等实现了基于局部性原理和缓存特性设计的树形索引结构CSS-Tree［2］和CSB+-Tree［3］。Fang［4］等将图形显卡的计算能力同索引结构结合在一起，实现了基于GPU的CSS-Tree。T-Tree［5］是一种在节点内包含多个键的平衡二叉树结构，用于将索引信息和数据记录都驻留在主存中。Liu［6］等在GPU平台上利用N个线程并行化构建N个节点的方式来迅速构建起T-Tree索引结构。R-Tree［7］作为广泛被使用的空间索引技术，应用GPU来深入挖掘出其在大规模的空间数据下的查询处理潜力。You［8］等所提出的R-Tree使用基于GPU的并行查询处理技术，实现了较八核CPU并行实现方案的十倍提速。

Daga等［9］介绍了一种利用异构计算平台APU加速B+-Tree搜索的技术。Fix［10］等提出了一种在GPU中以线程块为单位编织查询任务的算法。针对将数据库应用移植到GPU上的问题，Kaczmarski［11］等基于数据库中的B+-Tree索引结构和数据页的管理策略提出了一种用二维数组来表示B+-Tree的索引结构。Kaczmarski［12］等相继又提出了可以高效创建GPU上的B+-Tree索引算法。Huang［13］等介绍了一种在GPU上的批处理构建和插入算法CUBPT。随着并发查询量和数据规模的增加，Yan［14］等提出了一种面向查询吞吐量的新型B+-Tree索引Harmonia，可以激发GPU上低延迟的高速缓存的性能。Ashkiani［15］等提供了一种与B-Tree具有相同操作特性的动态GPU日志结构合并树LSM，在GPU平台上通过减少或消除线程访问节点时的竞争实现了一种可变键值存储［16］的B-Tree。综合现有索引研究成果的优缺点，更好地联合使用CPU和GPU的内存资源与并行计算能力，构建面向查找密集型场景的B+-Tree索引，是本文所实现的基于GPU加速的数据库查询系统的研究重点。

3 面向GPU的HPGB+-Tree索引

由于CPU与GPU硬件构造不同导致存在较大的差异性，基于CPU的B+-Tree索引结构和查询方式并不适用于GPU。例如，孩子节点的寻址采用二分法确定目标键的定位方式等在GPU上均表现不佳。因此对B+-Tree索引结构重构使其适应GPU的硬件特性是当前研究的重点之一。随着索引大小的增长，CPU的性能受到内存带宽的限制［17］，而GPU的内存架构足够高效，所以其内存带宽足够高。但是GPU中可用的内存空间与CPU可用的主机内存相比十分有限。因此在数据量较大的情况下，B+-Tree索引在GPU上的扩展能力会受到限制，所以如何结合CPU与GPU的内存特性构建基于GPU的B+-Tree索引结构是值得研究的问题。

本文所提出的HPGB+-Tree索引结构是基于传统的B+-Tree索引结构进行重构和设计的。B+-Tree索引最早被提出用于磁盘索引［18］，核心结构是平衡多路排序树。B+-Tree只在叶子节点中存储实际数据，内部节点就有足够的空间去容纳更多的键值。B+-Tree不同于二叉树，每个节点对应的盘块所容纳的键值数量远超二叉树，所以B+-Tree的高度就会远低于二叉树，因此B+-Tree的搜索操作只需要很少的磁盘I/O次数就可以定位到含有目标键的叶页。无论是内部节点还是叶子节点都通过二分搜索查找目标键值。在B+-Tree的索引结构中，含有m棵子树的节点最多含有m个候选键。在叶子节点中存储的候选键是有序的，并且叶子节点间通过指针链接。因此，B+-Tree很好地支持了高效的范围查询。B+-Tree另外一个特性是在执行不同的查询任务时，B+-Tree总会遍历相同长度的路径，这就使查询任务的负载较为均衡，查询效率较为稳定。目前B+-Tree索引已被广泛应用在数据库当中，如关系型数据库MySQL等。如图1所示，是一棵传统的B+-Tree示意图。

图1 传统B+-Tree

HPGB+-Tree的索引结构是由传统B+-Tree转换而来，存在于主机端的传统B+-Tree有三种重要的用途：1）用于计算HPGB+-Tree索引相关的元数据信息，如新索引在内存中所需空间大小等。2）作为原始材料构建HPGB+-Tree索引结构并初始化索引数据。3）HPGB+-Tree索引是面向查询密集型的索引结构，因此数据插入采取从主机端的B+-Tree以批量、异步的方式进行，再同步至GPU。

在对HPGB+-Tree索引树的节点Knode进行设计时，选择用结构体数组的方式组织关键字和分支信息，而不是用数组结构体。这是因为并行计算架构CUDA在操作细粒度数组如结构体数组（SoA），即结构体中的元素是数组时是很友好的。但是在操作粗粒度数组如数组结构体（AoS），即数组中的元素是结构体时，在性能测试中表现为访存利用率较低。

结构体在内存中是一片连续的内存空间，应用SoA的方式可以带来内存读写性能的巨大提升。对全局内存带宽的充分利用，是提高内核函数效率和减少带宽浪费的重要手段。在树的搜索过程中，每次会从内存里读取一个节点进行判断。由此可知，采用SoA的方式构建树的节点，可以更好地利用内存资源，同时更方便实现对齐与合并访问内存，将节点所在的内存块加载进缓存中，优化访存速度。

索引树的每个节点都是由结构体数组Knode表示，如图2所示。每个Knode包含三部分：候选键数组、子位置数组以及节点相关元信息。

图2 HPGB+-Tree索引节点结构

在候选键数组Keys中，连续存放着节点内待比较的关键字，用于在查找目标键时确定一条准确的路径。在子位置数组Indices中，存储的是当前节点的所有孩子节点的地址。每一个元素相当于传统B+-Tree内部节点的指针域中存放的其孩子节点的指针。节点相关元信息包括用于标识节点是否为叶子节点的标记符isLeaf，用于标识构建进度的标记Location，以及用于标识当前节点中候选键个数的标记numsOfkey。这种节点设计的好处在于不仅可以高效率的访存，还能够迅速定位搜索路径上孩子节点的位置加速查询任务的执行。

为使GPU的并行计算能力物尽其用，同时考虑到GPU上的内存容量有限，而CPU上并没有这方面的瓶颈。因此本文联合使用主机内存与设备内存，将索引结构分散在两硬件平台之中。具体来讲，HPGB+-Tree索引整体分为两部分，一部分存在于主机内存中，包括索引树Knodes以及实际数据Records。另一部分存在于GPU的设备内存中，这部分是位于主存内索引树Knodes的拷贝镜像，这是由于Records中的元素存储的是实际数据，所占空间较索引树Knodes要大得多，不仅占用显存珍贵的内存资源，而且向显存的数据传输也十分耗时。在第一部分中，Knodes的类型是以AoS方式组织而成的数组结构体，Knodes将遍历传统B+-Tree节点转换而来的结构体Knode作为数组元素。Records是将每条实际数据Record作为数组元素，将数据记录按顺序存储在内存当中，支持以O（1）的时间复杂度Records中获取到记录。值得一提的是，Record依据使用场景的不同，既可以是一个具体的值或一条数据记录的主键，也可以是一条具有多个数值字段的记录。

在第二部分中，存在于GPU上的索引树是主存里Knodes的一个拷贝，也是凭借GPU高性能并行计算的优势来执行查询任务的主要操作对象，具体的拷贝过程是将Knodes从主机内存传输到设备内存中开辟的缓冲区内。HPGB+-Tree索引会长久地驻留在设备内存中，被多个查询任务共享。另外，在加载或构建多个HPGB+-Tree索引时，多个缓冲区会在逻辑上组成索引池，而具体的信息维护工作由CPU负责。如图3所示，是在异构环境下HPGB+-Tree索引结构的示意图。在主存中的HPGB+-Tree索引构建算法伪代码如表1所示。

图3 HPGB+-Tree索引结构

表1 主机到设备数据传输测试实验结果

HPGB+-Tree索引构建算法如下所示。

TRANSFORM_HPGB（root）

1）function TRANSFORM_HPGB（root）

2）Krecords←mallocCpuLeaves（）

3）Knodes←mallocCpuNodes（）

4）queue←enqueue（root）

5）while queue！=null do

6）curNode←dequeue（）

7）initKey（curNode）

8）if node！=leaf then

9） init_indice（curNode）

10） while index

11） next←curNode［index］

12） initIndice（next）

13） queue←enqueue（next）

14） end while

15）end if

16）if curNode==leaf then

17） while index

18） initRecord（curNode）

19） end while

20）end if

21）end while

22）end function

4 实验分析与性能测试

为了验证HPGB+-Tree索引为数据库查询系统带来的查询性能的提升，本节将对基于混合架构的索引算法HPGB+-Tree进行实验测试。为验证索引在混合架构下相比于单一架构的优势，本文选择Aviram［19］提出的基于CPU的高查询性能的无锁B+-Tree索 引，Fix等 提 出 的GPU B+-Tree索 引Braided B+-Tree和前期研究成果即其优化版本Optimized Braided B+-Tree来进行索引性能的对比实验。本节将从实验环境，实验数据，实验方式以及实验结果与分析来组织内容。主要对HPGB+-Tree索引算法进行三个方面的实验测试：1）数据传输实验测试。2）HPGB+-Tree索引的相关参数实验测试。3）基于最佳参数配置的HPGB+-Tree索引等值查询与范围查询的性能表现实验测试。

4.1 实验环境

硬件配置：显卡GPU为NVIDIA 1660Ti，处理器为CPUIntel i7 9700，内存16GB，磁盘512GB SSD；软件配置：操作系统为Ubuntu 18.04，CUDA运行环境为CUDA 9.0，开发IDE为Vscode，CUDA代码编译器为NVCC，C编译器为gcc 4.8，C++编译器为g++4.8，构建工具为Make。

4.2 实验数据和方式

本文进行的实验采用的数据是随机生成的数据记录，记录形式为一张在关系型数据库中具有多个字段的行记录组成的一张二维表。生成的数据记录中的每个字段均为四字节的整型数值，该二维表内数据记录的行数范围为十万量级到千万量级。

本文选择任务的执行时间作为评价指标来衡量本系统内部实现的HPGB+-Tree索引核心算法的性能。

在CUDA架构中，主机端的内存分为可分页内存与锁页内存，如表1和表2所示，是由长度为4字节的整型组成不同规模数据量，使用两种不同类型内存进行主存与设备内存之间的数据传输测试。

表2 设备到主机数据传输测试实验结果

本部分测试不同的HPGB+-Tree索引阶数对执行查询任务速度的影响，确定最大化查询执行效率的最佳索引阶数。分别在不同数据规模下构建32阶、128阶和512阶的HPGB+-Tree索引，然后在系统默认配置五个CUDA流的条件下，批量执行十万个等值查询任务。实验结果如图4所示。在索引阶数为32时，执行时间消耗最小，达到执行查询任务的最佳性能。

图4 不同索引阶数的查询效率

本文所提出的HPGB+-Tree索引继承了B+-Tree索引的优势，叶子节点存储的数据记录是有序的，并且连续存储在一块内存区域中。因此，HPGB+-Tree索引既支持等值查询，又支持范围查询。本文选用传统B+-Tree、基于GPU的Braided B+-Tree和Braided B+-Tree的优化版本Optimized Braided B+-Tree作为实验对比对象，进行等值查询与范围查询的实验测试。

等值查询的实验是在索引阶数为32和等值查询任务规模为一万的实验条件下，对在216~224不同规模的数据下构建的四种索引，进行等值查询的对比实验。实验结果如图5所示。

图5 不同数据规模下的等值查询

由于传统坐标系无法清晰表现出几种索引的性能差距，因此绘制为同x双y坐标系的柱状图。其中传统B+-Tree与Braided B+-Tree索引执行等值查询任务时间消耗较多，所以使用左侧跨度较大的坐标系，而Optimized Braided B+-Tree与HPGB+-Tree索引执行等值查询任务时间消耗较少，因此使用右侧跨度较小的坐标系。其中随着索引数据规模的增大，CPU的执行时间消耗也逐渐变大，并且执行效率远远低于借助高性能硬件平台GPU的其他索引结构。Braided B+-Tree每次执行任务都要将索引文件重新传递到设备内存的临时缓冲区中，因此随数据规模增大，索引文件所占内存也增大，由此造成的数据传输时延会导致执行效率与内核占用率不断降低。在执行等值查询任务时，本文提出的HPGB+-Tree索引算法比Optimized Braided B+-Tree执行效率高近三倍。

范围查询实验是在216~224的数据规模下分别构建阶数为32的四种索引，并进行一万次随机选取区间范围为一百的范围查询测试，实验结果如图6所示。

图6 不同数据规模下的范围查询

为了更好表现出几种索引进行范围查询的实验效果，坐标系构造方式与图3中等值查询实验所绘制的同x双y坐标系构造相同。其中x轴代表各个不同的数据规模，左侧跨度较大的y轴用于标记传统B+-Tree与Braided B+-Tree索引处理范围查询任务的执行时间，右侧跨度较小的y轴用于标记Optimized Braided B+-Tree与HPGB+-Tree索 引 处理范围查询任务的执行时间。

范围查询的执行逻辑与等值查询任务类似，但是范围查询任务需要扫描筛选出符合条件的左右边界内所有的目标值，导致CPU执行任务的消耗时间更加长，查询效率更加低。Braided B+-Tree索引在执行范围查询任务时仍需要重新传输索引结构与数据。在数据量较小时，由于PCIe传输的高带宽对其造成的影响不大。但随数据量级的增大，其影响越来越明显，表现为任务的执行时间逐渐接近CPU。Optimized Braided B+-Tree索引在执行范围查询任务时避免传输索引结构和数据的代价，同时优化了内核程序，使其可以较为高效地获取符合条件的目标键范围。因此执行时间较短，查询效率较高。

本文提出的基于HPGB+-Tree索引范围查询算法在数据传输、任务分配和内核程序等方面都进行了优化，相比于Optimized Braided B+-Tree索引，其执行效率提升近三倍。

5 结语

目前GPU应用于在数据库领域的研究还处于不断探索的阶段，而索引作为加速数据库检索数据的重要技术手段，现有的研究大多数为磁盘索引或主存索引且已非常成熟，因此对利用新硬件平台GPU突破索引性能瓶颈的研究具有重要的意义。

本文提出了一种CPU与GPU协同构建和处理的HPGB+-Tree索引算法，该算法实现索引结构的并行化设计，使其更加切合GPU的硬件特性。同时将实际数据记录存储于容量较大的主存中，索引树的节点拷贝到带宽较高的显存中，解决了CPU内存带宽瓶颈和GPU内存容量受限的问题。在未来的工作中，我们将会研究如何将以HPGB+-Tree索引技术为核心，开发MySQL的扩展模块。