黄伟建 贾孟玉 黄亮

摘  要： 针对传统MapReduce环境下Hash分区处理偏差数据时存在效率低下负载不均衡问题，采用两阶段分区，即基于并行相似随机抽样贪心算法分区。该抽样是基于Hadoop随机抽样在给定样本比率或特定置信度下的误差范围内快速且低错误率的预测key分布结果。优点在于利用MapReduce框架的并行性减少抽样开销成本，并采用一种评估模型来确定合适的抽样率，达到减少抽样开销成本和提高抽样准确性的目的。结合贪心算法分区代替Hadoop平台默认的Hash分区算法来划分中间数据，实现MapReduce负载均衡。Matlab实验仿真结果表明，并行随机抽样贪心算法分区无论从负载均衡还是执行时间上都优于原生Hadoop中Hash分区算法。

关键词： MapReduce; 负载均衡; 贪心算法分区; 并行随机抽样; 分区建模; 对比验证

Abstract： In allusion to inefficiency and load imbalance in the traditional MapReduce environment when the Hash partitioning is used to process the bias data， the two?stage partitioning algorithm?greedy partitioning based on the parallel similarity random sampling is adopted. This sampling is based on Hadoop random sampling to predict key distribution results with fast and low error rate throughout the error range of the given sample ratio or the specific confidence coefficient. The advantage of this sampling way is that the overhead costs of sampling are reduced by means of the parallelism of MapReduce framework， and the appropriate sampling rate is determined with an evaluation model to reduce the overhead cost of sampling and improve the sampling′s accuracy. The intermediate data is divided by using the greedy algorithm partitioning to replace the default Hash partitioning algorithm of Hadoop platform， so as to realize the MapReduce load balancing. The Matlab simulation results show that the greedy partitioning algorithm based on the parallel sampling is superior to the Hash partitioning algorithm in the native Hadoop in terms of load balancing and execution time.

Keywords： MapReduce; load balancing; greedy algorithm partitioning; parallel random sampling; partitioning modeling; comparison validation

0  引  言

目前，两阶分区（抽样和分区）是一种解决MapReduce处理偏差数据时存在Redcue负载不均衡问题的简单且高效的算法。文献[1]研究抽样过程影响开销与成本的各种因素，如准确率、节点个数、样本规模，并给出理论证明，为两阶段分区提供了理论支撑。有学者提出用贪心算法代替Hash算法，但其抽样采用普通系统抽样，当抽样率到达一定阈值时抽样开销成本会影响MapReduce整体性能[2]。文献[3?4]缺乏有效估计数据分布的预处理。然而很少学者在抽样过程中考虑抽样结果准确性和抽样带来的开销成本问题，所以有必要对此问题进行研究。

于是在上述学者研究的基础上对抽样分区进行优化，采用一种argMin函数方法来解决抽样开销和结果准确性之间的平衡问题。……