CN112000846B - 基于gpu分组lsm树索引的方法 - Google Patents

Abstract

本发明提供一种基于GPU分组LSM树索引的方法，涉及GPU数据库技术领域。本发明首先将数据进行预处理，当value为变长时，在GPU上进行查询时不能很好的利用缓存而且数据传输代价也会增大。本发明针对以上情况，将数据中的Key和Value进行分离，GPU中仅仅存放Value的地址，真正的Value存放在内存中。针对LSM插入速度慢的问题，本发明将原来的LSM树每一层分为多个组，每个组都是一个有序数组，合并到下一层的时候通过GPU上大量的线程并行的归并。由于将LSM树进行分组，意味着查询需要花费更高的代价。为了提高查询速度，本发明在GPU上设计了一种适应于GPU结构的布隆过滤器，通过布隆过滤器减少了大量不必要的查询开销。

Description

基于GPU分组LSM树索引的方法

技术领域

本发明涉及GPU数据库技术领域，尤其涉及一种基于GPU分组LSM树索引的方法。

背景技术

随着大数据时代的到来，数据总量和数据访问量都在爆炸式的增长。传统的关系型数据库已经不能够满足这种高并发的访问场景。而Nosql数据库不依赖于关系数据库的传统结构且更加灵活和方便，因此非常适用于云存储,电子商务和web访问等。键值(Key-Value,KV)是Nosql数据库的基本类型,通过GET,PUT,DELETE等简单的接口就能对大量非结构化的数据进行读写。

目前主流的Nosql数据库的索引结构都是日志结构合并树(log-sturctre mergetree,LSM Tree)。LSM树是重要的数据结构之一。它被广泛用于levelDB，rocksDB，Cassandra等NoSql数据库中。LSM树是一种多层的结构，它的基本思想是先将数据的修改或者插入保存在内存中，当内存达到容量限制再将这些操作顺序写入磁盘，磁盘中的树在后台会进行定期的合并操作，最后以归并的方式合并成一棵大树。相比于其它索引结构例如B树，它在数据的插入，删除修改方面有极高的速度。由于LSM树的这种分层结构，查询也会在内存和磁盘上进行多次二分查找，这样就明显的降低了它的查询速度。因此LSM树适用于写入远大于读取的场景。相比于内存上的数据结构，LSM树这种磁盘上的数据结构性能的瓶颈在于磁盘IO上。

先前的工作都是针对磁盘IO问题也就是LSM树的读写放大问题进行优化的，例如WiscKey进行KV分离，降低写Value的代价。PebblesDB通过弱化全局有序来降低写放大。

相比于磁盘上的数据结构，内存中的数据结构性能在于算法的时间复杂度和并发线程的数量。而GPU的大量线程和高速的带宽就非常适合于处理LSM这种数据结构。由于GPU的多核处理器使用SIMD执行方法大大提高了数据处理速度并减少数据响应时间，许多索引结构已经在GPU上实现了高性能，例如Harmonia，SlabHash等。目前在GPU上实现的索引结构主要分为两大类，基于hash的索引和基于树的索引。基于hash索引的结构能够进行快速的插入删除更新和点查找，但不能像基于树的索引结构支持范围查找。而且对于更新操作许多GPU索引结构不是动态的更新，而是在GPU上重新构建索引结构。GPULSM树是首个在GPU上实现的LSM树索引结构但是它的插入查询等操作也没有很好的和GPU硬件结构匹配。

发明内容

针对现有技术的不足，本发明提供一种基于GPU分组LSM树索引的方法，将LSM树每一层分为多个组，数据在组内有序，在组间无序。当某一层数据满了的时候通过GPU上的大量线程并行的归并到下一层中。而针对LSM树查询速度慢的问题，本发明通过布隆过滤器排除掉了大量不必要的查询，提高了查询效率。

为解决上述技术问题，本发明所采取的技术方案是：

一种基于GPU分组LSM树索引的方法，包括以下步骤：

步骤1：对Key-Value数据进行预处理，将数据在内存中进行键值Key和数据Value的分离；

将Value存放在内存中，同时在内存中用哈希表存储Value和对应的地址，查询时以O(1)的时间复杂度定位Value；分离之后将Key和Value的地址拷贝到GPU的全局内存中；

步骤2：将数据插入到GPU分组LSM树中；在GPU分组LSM树中，所有数据均是按批进行插入，假设每一批数据大小为b，数据组group的数量为g，因此GPUGLSM中每一层都会有g个group且第i层有b*g⁽ⁱ⁺¹⁾个组，整个GPU分组LSM包含的数据都是b的整数倍；使用GPU的基数排序对数据进行排序，并查看GPU分组LSM树中第一层是否有空的组，有则将数据拷贝到该组中，没有则触发合并操作，使第一层为空然后将数据拷贝到第一层；

步骤3：进行数据查询时，进行部分排序提高合并内存访问效率，确定需要排序比特位数量；

假设Key的长度位为B个比特，GPU分组LSM树的大小为T，GPU缓存存放的Key的长度为K，Key的范围长度为2^B，LSM树中的每一个Key覆盖的范围是2^B/T*K，则该范围的平均比特位个数为log₂(2^B/T*K)；若查询中的内存请求属于高速缓存行的覆盖范围，则无论请求的Key是否排序，都是合并的内存访问；因此，当查询的Key位于同一高速缓存行中时，不对查询进行排序，使用以下公式计算排序的比特位数量N：

N＝B-log₂(2^B/T*K)

步骤4：对查询的数据使用布隆过滤器筛选掉无关的查询；

所述布隆过滤器SBF由M个哈希函数组成，M为正整数，每个哈希函数是独立不相关的；

步骤5：将访问的数据加载到共享内存中；查询会访问每一个group中的固定位置的数据，这些查询数据会全部访问这棵树的根节点，数据访问这棵树的前L层数据，其中L为正整数；

步骤6：在GPU上对共享内存中的数据进行查询，得到对应的全局内存中的位置，然后再到全局内存中进行查询；由于GPU上存放的是Value的地址，因此查询完成后会将查询结果拷贝到内存中去，再由CPU端进行处理，通过查找Hash表取出对应Value的值，这样就完成了在GPU分组LSM树上的查询过程。

采用上述技术方案所产生的有益效果在于：

本发明提出了一种基于GPU分组LSM树索引的方法，本发明适用于写多读少的场景例，如图处理和web应用等，在GPULSM树的基础上设计了一种新的GPU数据结构，GPU分组LSM树，该结构能够通过并行的合并策略提高了插入的速度，同时通过布隆过滤器，部分排序等策略提高了查询速度。

附图说明

图1为本发明实施例GPU分组LSM树整体流程图；

图2为本发明实施例将key与value进行分离示意图；

图3为本发明实施例对value的地址进行hash映射示意图；

图4为本发明实施例GPU分组LSM树的插入过程示意图；

图5为本发明实施例插入数据流程图；

图6为本发明实施例并行合并示意图；

图7为本发明实施例随机内存访问示意图；

图8为本发明实施例合并内存访问示意图；

图9为本发明实施例warp内随机访问示意图；

图10为本发明实施例warp内部分排序示意图；

图11为本发明实施例GPUOne-hash布隆过滤器示意图；

图12为本发明实施例使用共享内存加速查询示意图。

具体实施方式

下面结合附图对本发明具体实施方式加以详细的说明。

本发明分为两大部分：GPU分组LSM树的插入更新和删除，以及GPU分组LSM树上的查询，

对于插入更新或者删除操作来说，首先需要将数据在内存中进行Key和Value的分离，将Value存放到内存中，同时将Value的地址记录到内存中的Hash表中；然后将数据从内存拷贝到GPU全局内存的缓冲区中，这里会拷贝Key和对应的Value地址。接着GPU会对缓冲区中的数据进行一次排序，排完序之后会拷贝到GPU分组LSM树的第一层中，如果第一层放不下则会触发合并操作，将数据刷到下面的层中。

对于查询操作来说，为了减少GPU的warp分散提高合并内存访问效率，首先会对数据进行部分排序，然后通过布隆过滤器过滤掉大量的无效查询，最后真正需要查询的数据已经比原来少了许多。在GPU分组LSM树上首先对在每一层上进行查询，每一层上会对每一个组进行查询，由于查询使用的是二分查找算法，因此大量的查询请求会频繁访问同一个组中某些数据，因此在真正在查询的时候会将这些数据加载到GPU共享内存中。

本发明采用的技术方案是：

一种基于GPU分组LSM树索引的方法，如图1所示，包括以下步骤：

步骤1：对Key-Value数据进行预处理，将数据在内存中进行键值Key和数据Value的分离；如图2所示，插入的数据Value长短不一样，有些Value的长度可能特别长都超过了GPU缓存的大小，会造成GPU访问该Value时进行过次加载，降低访存效率。本发明因此将Value的地址和Key一同放入GPU全局内存中提高合并内存访问效率。查询的时候通过图2中的addr也就是地址，去内存中寻找真正的Value值。为了能够再内存中迅速定位到Value的位置，如图3所示，本发明在内存中使用哈希表存储Value和对应的地址，查询时只需O(1)的时间复杂度就能够迅速得等到对应的Value。

步骤2：将数据插入到GPU分组LSM树中；在GPU分组LSM树中，所有数据均是按批进行插入，假设每一批数据大小为b，数据组group的数量为g，因此GPUGLSM中每一层都会有g个group且第i层有b*g⁽ⁱ⁺¹⁾个组，整个GPU分组LSM包含的数据都是b的整数倍；使用GPU的基数排序对数据进行排序，并查看GPU分组LSM树中第一层是否有空的组，有则将数据拷贝到该组中，没有则触发合并操作，使第一层为空然后将数据拷贝到第一层；

本实施例中如图4所示，图中GPU分组LSM树的每层分为两个group。第0层的group大小等于一批数据的大小，当新的一批数据插入时先将第0层的数据合并到第一层中，然后将buffer中排序后的数据复制到第0层中。详细的插入过程见图5,与GPULSM的缓冲区结构设计不同，GPU分组LSM先找到需要合并的最大层数，然后以自底向上的方式执行合并，这大大减少了缓冲区对GPU全局内存的占用。合并的过程不需要额外的缓冲区。与GPULSM的合并方式不同的是本发明采用的是并行规约的合并方式，类似于合并排序的最后一步过程，将几个有序的数组合并为一个新的有序数组从而减少了插入的时间。合并过程如图6所示，当每一层的group数量为4时，在GPU上只需要两次并行合并，而在CPU上需要3次，如果group的数量越多那么在GPU上合并的时间将会越少，从而提高查询速度。

步骤3：进行数据查询时，进行部分排序提高合并内存访问效率，确定需要排序比特位数量；

假设Key的长度位为B个比特，GPU分组LSM树的大小为T，GPU缓存存放的Key的长度为K，Key的范围长度为2^B，LSM树中的每一个Key覆盖的范围是2^B/T*K，则该范围的平均比特位个数为log₂(2^B/T*K)；若查询中的内存请求属于高速缓存行的覆盖范围，则无论请求的Key是否排序，都是合并的内存访问；因此，当查询的Key位于同一高速缓存行中时，不对查询进行排序，使用以下公式计算排序的比特位数量N：

N＝B-log₂(2^B/T*K)

在GPU上进行查询也就是访问GPU的全局内存，而GPU上合并内存的访问效率直接影响到了查询的速度。如图7所示，在排序前每个warp中的线程需要查询两个key，每一个线程都需要访问图中的三个节点。第一个warp中的查询只有在访问二分搜索树的根节点会合并内存访问，而访问其余节点则出现了warp分散和内存分散，所以整个访问需要5次全局内存访问。同样的第二个warp中的查询也需要5次全局内存访问。当对到来的查询排序后，如图8所示，看到第一个warp中的查询会共同访问二分搜索树的根节点和下一层节点，同样的第二个warp中的查询也会访问二分搜索树的根节点和下一层节点。对应于GPU GLSM来说就是warp中的线程会在前两次查询group的时候会共同访问同一个位置的数据。相比于没有排序的查询，排序完成后每一个warp需要4次全局内存访问，这样就减少了全局内存访问次数。而且在访问二分搜索树的前两层时执行的是相同的指令，这样就减少了warp分散。

尽管排序能够提高GPU GLSM的查询性能，但是我们没有必要使这些到来的查询保证严格有序。如图9所示，warp 1中的查询1和10分别需要进行两次全局内存访问，warp2中的查询2，32需要同样需要进行两次全局内存访问。这些warp中的线程每次访问全局内存都会将L1 cache line大小的数据从全局内存加载到L1 cache line,如果这些查询能够访问的位置在全局内存中的位置比较靠近那么就可以减少对于全局内存的访问。虽然我们对这些数据进行排序之后，warp1中的查询1,2就能访问同一个GPU高缓行。而且对同一个group进行查找时warp中的线程会尽可能的走同一条路径，这样就能够极大的减少warp分歧。但是对这些数据进行一次排序的代价也比较高，而且没有必要要求查询的数据完全有序。同一个warp中的数据能够尽可能的访问同一个高缓行的数据就能够实现很好的效果。如图10所示，对查询的数据进行部分排序，只需要排序前K比特的数据使warp间有序，而warp内部可以无序，同样能够实现合并内存访问。

步骤4：对查询的数据使用布隆过滤器筛选掉无关的查询，如图11所示；

所述布隆过滤器(SBF)由M个哈希函数组成，每个哈希函数是独立不相关的；

本实施例中本发明将每个分区划分为多个block，每一个block的长度为GPU高缓行的长度也就是1024。为了保证互质的条件每一个block的模运算的值为小于1024的质数，例如1021,1019,1013,1009,等，因此每一个block都会浪费掉一小部分空间。由于插入的数据每一批都需要排序，而我们的数据都是32位的，排序完成后每一批数据的前几比特都是有序的。对于GPU上的线程来说如果每一个warp都访问相同位置的数据，那么只需要一次GPU高缓行的加载就能够完成。因此我们将数据的前几比特用于定位到具体的分区和block，再通过模运算来定位到block中的位置。

假设集合中有n个元素，共进行k次模运算，第i个模运算的值为m_i，则可以通过以下公式估算出One-hash布隆过滤器的误报率：

改变模运算的次数就能够调整GPUone-hash布隆过滤器的误报率，排除掉大量无效的查询；

步骤5：将访问的数据加载到共享内存中；由于查询会访问每一个group中的固定位置的数据，这些查询数据会全部访问这棵树的根节点，数据访问这棵树的前L层数据，其中L为正整数；在GPU中共享内存是片上缓存，它的延迟比全局内存低许多，在进行计算时需要将全局内存中的数据拷贝到共享内存中，而拷贝也会消耗一些时间。如果共享内存中存放的是warp中不经常访问的数据那么拷贝就会影响它的计算性能，因此共享内存适合存放一些需要重复利用的或者经常访问的数据。图12显示了warp中的线程查询过程。当warp中的两个key：1和2发起查询时，首先访问整个组中间的元素第一层元素，然后访问第二层和第三层的元素。图中要查询的小方块位于不同全局内存中。假设当前组的大小为Q，则整个查询所需的数据负载为logQ倍。为了减少GPU对全局内存的加载次数，本发明将整个group中经常访问的数据加载到共享内存中。

步骤6：在GPU上对共享内存中的数据进行查询，得到对应的全局内存中的位置，然后再到全局内存中进行查询；由于GPU上存放的是Value的地址，因此查询完成后会将查询结果拷贝到内存中去，再由CPU端进行处理，通过查找Hash表取出对应Value的值，这样就完成了在GPU分组LSM树上的查询过程。

以上描述仅为本公开的较佳实施例以及对所运用技术原理的说明。本领域技术人员应当理解，本公开的实施例中所涉及的发明范围，并不限于上述技术特征的特定组合而成的技术方案，同时也应涵盖在不脱离上述发明构思的情况下，由上述技术特征或其等同特征进行任意组合而形成的其它技术方案。例如上述特征与本公开的实施例中公开的(但不限于)具有类似功能的技术特征进行互相替换而形成的技术方案。

Claims (2)

1.一种基于GPU分组LSM树索引的方法，其特征在于：包括以下步骤：

步骤1：对Key-Value数据进行预处理，将数据在内存中进行键值Key和数据Value的分离；将Value存放在内存中，同时在内存中用哈希表存储Value和对应的地址，查询时以O(1)的时间复杂度定位Value；分离之后将Key和Value的地址拷贝到GPU的全局内存中；

步骤2：将数据插入到GPU分组LSM树中；

所述GPU分组LSM树中，所有数据均是按批进行插入，假设每一批数据大小为b，数据组group的数量为g，因此GPU分组LSM中每一层都会有g个group且第i层有b*g⁽ⁱ⁺¹⁾个组，整个GPU分组LSM包含的数据都是b的整数倍；使用GPU的基数排序对数据进行排序，并查看GPU分组LSM树中第一层是否有空的组，有则将数据拷贝到该组中，没有则触发合并操作，使第一层为空然后将数据拷贝到第一层；

步骤3：进行数据查询时，进行部分排序提高合并内存访问效率，确定需要排序比特位数量；

假设Key的长度位为B个比特，GPU分组LSM树的大小为T，GPU缓存存放的Key的长度为K，Key的范围长度为2^B，LSM树中的每一个Key覆盖的范围是2^B/T*K，则该范围的平均比特位个数为log₂(2^B/T*K)；若查询中的内存请求属于高速缓存行的覆盖范围，则无论请求的Key是否排序，都是合并的内存访问；因此，当查询的Key位于同一高速缓存行中时，不对查询进行排序，使用以下公式计算排序的比特位数量N：

N＝B-log₂(2^B/T*K)

步骤4：对查询的数据使用布隆过滤器筛选掉无关查询；

步骤5：将访问的数据加载到共享内存中；查询会访问每一个group中的固定位置的数据，这些查询数据会全部访问这棵树的根节点，数据访问这棵树的前L层数据，其中L为正整数；

步骤6：在GPU上对共享内存中的数据进行查询，得到对应的全局内存中的位置，然后再到全局内存中进行查询；由于GPU上存放的是Value的地址，因此查询完成后会将查询结果拷贝到内存中去，再由CPU端进行处理，通过查找Hash表取出对应Value的值，这样就完成了在GPU分组LSM树上的查询过程。

2.根据权利要求1所述的一种基于GPU分组LSM树索引的方法，其特征在于，步骤4所述布隆过滤器SBF由M个哈希函数组成，M为正整数，每个哈希函数是独立不相关的。

Images