第48卷  第11期            西  安  交  通  大  学  学  报            V ol.48  No.11 2014年11月        JOURNAL OF XI’AN JIAOTONG UNIVERSITY        Nov. 2014
——————————
收稿日期：2014-04-09。  作者简介：袁通（1987-），男，博士生；刘志镜（通信作者），男，教授，博士生导师。  基金项目：国家科技支撑计划资助项目（2012BAH01B05）；陕西省科技统筹创新工程计划资助项目（2012KTZD-02-05-2） DOI ：
多核处理器中基于MapReduce 的哈希划分优化
袁通，刘志镜，刘慧，王梓
（西安电子科技大学计算机学院，710071，西安）
摘要：针对传统的并行哈希划分算法不能高效地利用多核处理器的并行资源，且不能较好处理有倾斜的输入数据的问题，提出了一种在多核处理器中基于MapReduce 的哈希划分算法，并且提出了存储结构优化、多步划分优化、数据倾斜优化3种优化策略。该算法将输入数据分成若干块后提交给各个线程并行处理，并选择合适的策略避免写冲突，使其能够高效地利用多核处理器的并行资源。文中提出的哈希表能够提高cache 效率，从而提升算法的整体性能。引入MapReduce 模型可使多步哈希划分在Map 过程和Redu
ce 过程中分别进行；数据倾斜优化策略能使算法适应有倾斜的输入数据，且具有较好的效果。实验结果表明：在多核处理器中，文中提出的算法能够适应各种分布的输入数据，并且使哈希划分的整体性能得到提升。 关键词：数据划分；哈希处理；多核处理器；MapReduce 模型
中图分类号：TP392  文献标志码： A    文章编号：0253-987X(2014)11-0000-00
Hash Partitioning Optimizations Based on MapReduce for Chip Multiprocessors
YUAN Tong, LIU Zhijing, LIU Hui, WANG Zi
(School of Computer Science and Technology, Xidian University, Xi’an 710071, China)
Abstract ：A hash partitioning method based on MapReduce framework and three efficient optimizations including storage structure optimization, multi-pass partitioning optimization and skew data optimization on chip multiprocessor (CMP) are proposed to address the problems that traditional hash partitioning method cannot take full advantage of CMP’s parallel execution resources and properly process the skew input data. The input data are split into several units which are later processed by all threads simultaneously, and suitable strategy is adopted to avoid writing collision and hence CMP’s parallel execution resources could be fully unitized. The new hash table proposed in this
paper can improve the overall performance of our method by increasing the cache efficiency. The introduction of MapReduce framework makes it possible to multi-pass partition the data in Map phase and Reduce phase respectively. In addition, the skew data optimization can make the proposed method suitable for processing various skew input data. Experiments have testified these advantages displayed by the proposed hash partitioning method. Keywords : data partitioning; hashing; multicore processors; MapReduce framework
划分是数据库中的重要操作，同时也是其他数据库操作（如连接、聚集、排序等）的基本操作。划分是将一个较大的任务分成若干个较小的子任务，而处理若干个子任务所用的时间常常少于处理一个较大任务所用的时间，这是因为较小的任务能够高效地利用cache 和内存。哈希划分是使用范围最
广的划分算法。
当今的硬件发展十分迅速，CPU 拥有更多的核心，每个核心拥有更多的线程。最近，IBM 推出了新一代的POWER 8处理器，支持12核心96线程，共享96 MB 的三级缓存，这说明多核CPU 具有广阔的应用前景。面对新型的硬件架构，传统的并行哈
y2 西安交通大学学报第48卷
希划分算法存在以下不足：①不能高效地利用多核处理器的并行资源，包括不能有效地降低内存存取延迟、减少cache miss和TLB miss等；②存储结构不能高效地支持多核并行读写；③不能较好地处理有倾斜的输入数据。
针对这些问题，本文提出一种多核处理器中基于MapReduce的哈希划分优化方法，用基于共享内存的MapReduce模型实现了哈希划分算法，并比较了4种避免线程冲突的策略。MapReduce模型的使用可以使算法高效地利用多核并行资源。在此基础上，提出了存储结构优化、多步划分优化、数据倾斜优化3种有效的优化方法，以解决现有算法的不足。
1  相关工作
对于在不同应用中的划分操作，人们已经进行了大量的研究，这些研究主要是针对数据库操作。在连接操作[1]和聚集操作[2]中，划分能够明显地提升操作性能。Balkesen等人的研究表明，在整个连接操作中划分操作占用了大部分时间[3]。Manegold等人证明了当划分数量较大时，多步划分比单步划分效果要好，且多步划分中第一次划分数量等于第二次划分数量时效果最好[4]。这是因为多步划分避免了大量的cache丢失和TLB丢失，且内存压力较小。但是，他们提出的Radix-cluster划分并不支持多核并行处理。Cieslewicz等人提出了在多核处理器中并行划分的方法[5]，但局限性是存储结构事先需知道每个划分中的元组数量，且其算法只在处理均匀分布的输入数据时有较好的效果，而多核负载均衡性并不理想。Lisa等人提出用硬件加速器来提升划分性能[6]，但这种方法受限于硬件系统。
MapReduce[7]自2004
在处理海量数据时有巨大的优势。MapReduce最初是针对机提出的，其性能经常受硬盘IO和网络IO 的制约，而基于共享内存的MapReduce[8]则避免了这些瓶颈，适合处理内存数据。所以，数据库管理系统（DBMS）可以利用基于共享内存的MapReduce 来优化划分算法。基于共享内存的MapReduce模型适用于多核处理器，处理器的每一个线程被当作一个计算节点，计算节点之间的通信是以共享内存的方式完成的。2  基于MapReduce的哈希划分
哈希划分可以通过一个MapReduce任务来实现，该MapReduce任务只实现Map任务即可。在Map任务中，根据键值对中key值的哈希值将该键值对写入结果区域。由于多线程并行地将键值对写入结果区域，所以可能会产生线程之间的冲突。为了避免写冲突，常采用以下4种策略。
（1）加锁策略。所有线程共享一个键值对存储结构，每一个划分区域是一个连续的存储空间；线程需要加锁后才能将键值对写入相应的划分区域，写入完成后需要解锁以便其他线程继续写入该区域。该策略的优点是内存消耗较小，且不会随着线程数量的增加而增加；缺点是频繁的加锁、解锁操作影响性能。
（2）无锁策略。每个线程有一个独立的键值对存储结构，由于每个线程只将数据写入自己的存储结构中，所以避免了频繁的加锁解锁操作。该策略的优点是避免了加锁解锁操作；缺点是需要额外的操作将
所有存储结构进行合并，且内存消耗随着线程数量的增加而增加。
（3）两次遍历策略。该策略的思想来源于文献[9]，即每个线程2次遍历分配给它的输入键值对。如图1所示，在一个用4线程将数据哈希划分为4份的任务中，第一次遍历时每个线程计算出属于不同划分的键值对的数量，根据这些数据可以计算出每个线程将不同的键值对写入存储结构的位置
[][]
i
j
R i K j
=
=∑（1）式中：R[i]为划分i在最终存储结构中的起始位置；K[j]为划分j中键值对的数量；i，j=t+pn，其中t为线程编号（本例中t=0，1，2，3），p为划分编号（本例中p=0，1，2，3），n为线程总数（本例中n=4）。
在第二次遍历时，每个线程根据上一步的计算结果将键值对并行写入中间键存储结构中。该策略的优点是：将最终的划分结果连续存储，提高了程序的局部性。该策略的缺点是需要2次遍历输入数据。
（4）并行缓存策略[10]。该策略类似于加锁策略，不同之处是在加锁策略中每写入一个中间键值对都需要加锁解锁，而在并行缓存策略中每个线程有大小一定的独立存储空间，将键值对写入独立存储空
第11期                    袁通，等：多核处理器中基于MapReduce的哈希划分优化                            y3
间时不需要进行加锁解锁操作，但当该存储空间耗
尽时，需要通过加锁解锁操作获得新的存储空间。
hue trunc函数
两次遍历策略
3  哈希划分优化方法
在多核处理器中每个线程被看作一个计算节
点，利用MapReduce思想可以优化哈希划分。本章
主要从存储结构优化、多步划分优化和数据倾斜优
化这3个方面来优化哈希划分。
3.1  存储结构优化
哈希表的结构直接影响整个算法的效果。传统
的哈希表用一个容器或一个数组来存储某一
划分中的键值对，如图2所示。
图2  传统的哈希表结构
如果用一个vector容器来存储某一个划分中的
键值对，当已存元组的数量很大时，元组的存储效
率会明显降低。而如果用一个数组存储某一个划分
中的键值对，元组的存储效率较高且效率不会随着
存储元组数量的增加而降低，但初始化一个容量较
大的数组所需的开销却比较可观。
为此，在加锁策略和无锁策略中，为了提高cache
的效率，我们采用一种优化的哈希表存储结构。不
同于传统的哈希表，优化的哈希表用一个连续的数
组表示，数组的每一位表示一个哈希桶，每一个哈
希桶集中存储某一个划分中的键值对，如图3所示。
每一个哈希桶由2个指针和一段连续的存储空间组
成，连续的存储空间存储属于该划分的元组，free指
MapReduce
过程进行第一次划分，用
表示了利用基于共享内存的模
型优化两步哈希划分的流程，图中
首先将输入数据分割成若干块，每一块数据交
Map产生P1个划
分结果。Map线程之间的写冲突问题可以用第节
中的4种策略之一解决。由于首先将输入数据分割
成大小相同的块，所以第一次划分中各个线程处理
的数据量大致相同，有良好的负载均衡。
接下来，P1个划分结果产生P1个Reduce任务，
每一个Reduce任务交给一个Reduce线程处理，进
行第二次哈希划分，得到最终P1P2个划分结果。这
里需要注意2个问题：①P1个Reduce任务的大小可
y4 西安交通大学学报第48卷
能不一致，这将导致某些Reduce线程处理较多的数据，出现负载不均衡问题，从而导致总体处理时间的增加；②由于最终P1P2个划分结果中的某一个划分只可能来自第一次哈希划分的P1个划分结果中的某一个划分，所以在第二次哈希划分中，Reduce线程之间不会出现写冲突。
3.3
在多步哈希划分中，由于第一次划分产生的
Reduce任务大小可能不一致，所以可能造成Reduce
过程中的负载不均衡，导致总体处理时间增加。针
对这一问题，提出以下优化方法，具体步骤如下。
（1，用于比较第一次哈希划
分的Reduce任务的大小。
（2）线程在处理Reduce任务之前，先
比较Reduce任务的大小和阈值T，Reduce
小于T，则线程处理该任务；如果Reduce
务大于T，则将该任务加入队列D中，并不进行处
理。至此，小于的任务都已被处理，而大于
任务都没有被处理，且都保存在D中。
（3）将队列中的每一个任务平均分为n
为Reduce线程的数量）份任务交给n个
线程并行处理。
（4）将队列D中的每一个任务处理完后，得到
最终的划分结果。
上述优化方法利用多核运算能力解决了多步哈
希划分中Reduce任务负载不均衡的问题。通常将阈
值T设定为
1
2/
C P，其中C表示最初输入数据的大
小，P1表示第一次划分产生的划分结果的数量，也
就是Reduce任务的数量。
4  实验与分析
4.1  实验环境
利C++Linux系统中实了基于
MapReduce的哈希划分及其优化方法。本文的实验
环境基于新型英特尔Sandy Bridge架构的核
处理器（E5-2670 2.6 GHz），每核包含2
体配置如下：核数为8；线程数为16；一级缓存大
小为每核32 KB；二级缓存大小为每核；三
级缓存大小为共享20 MB；内存大小为4×8 GB
DDR3内存（1 600 Hz）；Cache line大小为64 B；快
表大小为每核64个。
本实验采用了2种数据集：一种是均匀分布的
数据集表示）；另一种是有数据倾斜的数据集
（用种数据集均含有16 M24）条元
组，其中每条元组的大小为16 B，含有8 B的编号
和8 B的划分值。这种元组结构常应用在列存储数据
库之中。对于有数据倾斜的数据集，采用Zipf指数
来衡量倾斜程度。详细的数据集属性见表1。
表1  实验数据集
属性参数数据集A 数据集B
键值对大小/B 8/8 8/8
元组数量 16×220 16×220
Zipf指数 1 1.15
第11期                    袁通，等：多核处理器中基于MapReduce 的哈希划分优化                            y5
4.2  单步划分实验与分析
图5给出了4种不同写策略下单步哈希划分的实验结果。实验使用的是数据集A ，且采用了前述的优化方法。在加锁策略中，当Hash Bits 较小时，每一个划分结果有较多的元组，频繁的加锁解锁操
献[5]。实验使用的是数据集A ，在加锁策略和无锁策略下进行单步哈希划分。实验结果表明，由于采用了MapReduce 模型和本文提出的优化方法，所以本文算法比传统哈希划分算法的效果更好。 4.3  多步划分实验与分析
图7和图8分别给出了两次遍历策略下和无锁策略下单步和两步哈希划分的实验结果。该实验使
用的是数据集A ，且在两步划分中第一次划分和第
二次划分的数量分别为/22b ⎡⎤⎢
⎥和/22b ⎢⎥
⎣⎦，其中b 为Hash Bits 。文献[4]表明，由于Cache miss 和TLB miss
的原因，对于较大的划分数来说，多步划分比单步划分效果要好。实验结果表明，利用基于共享内存
用图7  两次遍历策略下单步和两步划分的实验结果
4.4  数据倾斜实验与分析
图9给出了两次遍历策略下使用数据倾斜优化和未使用数据倾斜优化的哈希划分实验结果，该实验使用
的是数据集B 。实验结果表明，在多步划分处理有倾斜的输入数据时，使用本文提出的优化方法

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。