基于增量式分区策略的MapReduce数据均衡方法

被引：44

作者：

王卓

陈群

李战怀

潘巍

尤立

机构：

[1] 西北工业大学计算机学院

来源：

计算机学报 | 2016年 / 39卷 / 01期

关键词：

增量分配; 细粒度分区; 数据倾斜; 均衡分区; MapReduce; 大数据;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

摘要：

MapReduce以其简洁的编程模型,被广泛应用于大规模和高维度数据集的处理,如日志分析、文档聚类和其他数据分析.开源系统Hadoop很好地实现了MapReduce模型,但由于自身采用一次分区机制,即通过Hash/Range分区函数对数据进行一次划分,导致在处理密集数据时,Reduce端常会出现数据倾斜的问题.虽然系统为用户提供了自定义分区函数方法,但不幸的是在不清楚输入数据分布的情况下,数据倾斜问题很难被避免.为解决数据划分的不均衡,该文提出一种将分区向Reducer指派时按照多轮分配的分区策略.该方法首先在Map端产生多于Reducer个数的细粒度分区,同时在Mapper运行过程中实时统计各细粒度分区的数据量;然后由JobTracker根据全局的分区分布信息筛选出部分未分配的细粒度分区,并用代价评估模型将选中的细粒度分区分配到各Reducer上;依照此方法,经过多轮的筛选、分配,最终在执行Reduce()函数前,将所有细粒度分区分配到Reduce端,以此解决分区后各Reducer接收数据总量均衡的问题.最后在Zipf分布数据集和真实数据集上与现有的分区切分方法Closer进行了对比,增量式分区策略更好地解决了数据划分后的均衡问题.

引用

页码：19 / 35

页数：17

共 5 条

[1]

一种基于动态划分的MapReduce负载均衡方法 [J].

周家帅 ;

王琦 ;

高军 .

计算机研究与发展 , 2013, (S1) :369-377

[2]

基于消息传递机制的MapReduce图算法研究 [J].

潘巍 ;

李战怀 ;

伍赛 ;

陈群 .

计算机学报, 2011, 34 (10) :1768-1784

[3]

架构大数据:挑战、现状与展望 [J].

王珊 ;

王会举 ;

覃雄派 ;

周烜 .

计算机学报, 2011, 34 (10) :1741-1752

[4]

MapReduce中基于抽样技术的倾斜问题研究 [D].

耿玉娇 .

大连海事大学,

2013

[5]

Complexity of the min–max and min–max regret assignment problems[J] Hassene Aissi;Cristina Bazgan;Daniel Vanderpooten Operations Research Letters 2005,

← 1 →