Hadoop平台中一种Reduce负载均衡贪心算法

摘要：

MapReduce是目前广泛应用的并行计算框架,是Hadoop平台的重要组成部分.主要包括Map和Reduce函数,Map函数输出key-value键值对作为Reduce的输入.由于输入的动态性,不同主机上的Reduce处理的输入量存在不均衡性.如何解决Reduce的负载均衡是优化MapReduce的一个重要研究方向.对整体数据进行抽样,通过适量的样本分析数据,达到较小的代价获得可靠的key分布,提出贪心算法代替Hadoop平台默认的Hash算法来划分数据,实现Reduce负载均衡.提出的贪心算法主要思想是根据抽样数据,求取所有key频次的和对于Reduce节点数量的平均值,然后依次为每一个Reduce分配一个接近平均值的负载,从而达到整体的负载均衡.模拟实验表明,所提算法与默认的hash分区算法相比,运行时间节约10.6％,达到更好的负载均衡.

关键词：MapReduce、贪心算法、Reduce负载均衡、抽样

所属期刊栏目：33

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61103202;国家教育部博士点基金资助项目20110162120046;中南大学教师研究基金资助项目2014JSJJ019

在线出版日期：2016-11-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：2656-2659