基于列存储的多核并行哈希分区优化方法

摘要

本发明公开了一种基于列存储的多核并行哈希分区优化方法，主要解决现有并行哈希分区算法不能高效利用多核处理器资源的问题。其实现方案是：首先，利用映射-化简并行编程模型将数据分区任务动态分配到各个核来执行，根据列存储数据集存储结构的不同，选择相应的避免写冲突策略；然后，用映射线程进行第一次哈希划分，并将所得到的第一次哈希分区结果经过数据倾斜优化后交给化简进程进行第二次哈希分区；最后，返回最终的哈希分区结果。本发明很好的利用了在多核处理器上任务可并行执行的特性，并能够适应各种分布的输入数据，提高了高速缓存效率和多核处理器的整体性能，可用于列存储数据集的多核并行多步哈希分区。

主权项

一种基于列存储的多核并行哈希分区优化方法，其特征在于，包括以下步骤：(1)读取用户输入的列存储数据集，该列存储数据集的数据格式为(Key,Value)形式的键值对，其中Key表示键值对所对应的编号，Value表示键值对所存储的值；(2)将用户输入的列存储数据集分割为若干大小相同的块，并将每一块数据交给一个映射线程进行第一次哈希分区；(3)对于列存储数据集不同的哈希存储结构，选择相应的避免写冲突策略，以确保第一次哈希分区时映射线程的并行执行；(4)通过映射线程并行执行第一次哈希分区，产生m个一次哈希分区结果：(4a)设映射线程的映射哈希函数为：其中HashBits是用户自定义的哈希参数，其取值范围为[2,+∞)，mod为模运算，为向下取整运算；(4b)每个映射线程依据映射哈希函数f₁(Key)，对于列存储数据集(Key，Value)键值对中的Key值进行哈希运算，将运算结果相同的键值对分到同一个分区中，共产生m个一次哈希分区，其大小分别为D₁,D₂,…,D_i,…,D_m，i∈1,2,…,m，m≥2；(5)将产生的m个分区结果通过化简进程进行第二次哈希分区：(5a)设化简线程的化简哈希函数为：其中为向上取整运算；(5b)通过数据倾斜优化方法优化m个一次哈希分区结果，将数据倾斜优化后的分区结果交给m个化简线程进行划分，即由化简线程依据化简哈希函数f₂(Key)，对每个分区结果(Key，Value)键值对中的Key值进行哈希运算，再将运算结果相同的键值对分到同一个分区中，分别产生n个分区结果，n≥2，共产生m×n个二次哈希分区，m×n≥4；(6)将最终的m×n个分区结果输出给用户。