并行随机抽样贪心算法分区的MapReduce负载均衡研究

摘要

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