一种基于Value均值的MapReduce任务分配策略

2019-04-30薛愈洁

太原学院学报(自然科学版) 2019年1期

薛愈洁

(太原学院,山西太原 030001)

0 引言

大数据是巨量数据集合,与传统数据不同,其不仅数据量庞大,数据维度高,而且数据结构复杂,处理难度大,因此对大数据的精确高效处理一直都是研究的热点。目前,分布式计算是解决大数据难题的重要方法,由google公司提出的MapReduce编程思想是并行与分布式计算的重要思想[1-2],是一种简化的并行计算模型,其核心是“分而治之”——将数据处理流程进行Map过程和Reduce过程的高度抽象划分,虽然两者的计算相互独立,但是又通过Map输出与Reduce输入相互联系。

大多数并行与分布式计算平台对于MapReduce编程思想都有相应的实现[3]——常见的有Hadoop平台与Spark平台,该类平台将内部并行运行机制进行封装,使算法设计逻辑与具体实现流程相对独立,将程序并行运行在分布式系统上[4],提高了程序设计的高效性。作为较成熟的编程思想,目前对MapReduce编程思想主要研究集中在借助现有的分布式计算机平台,对已有算法的可并行化研究,优化数据处理过程,提高数据处理性能,实现处理效果的提升[5-6],而对于MapReduce自身的任务分配机制研究不够充分。利用MapReduce思想,在数据处理过程中,容易出现相同的Map值的Value集合数据量差别巨大的情况,导致不同的Reduce任务工作量不同,造成集群负载不均衡问题,相对降低了数据处理效率。目前大多数并行与分布式计算平台通过静态HDFS文件系统的数据块容量解决任务分配不均衡问题,但效果有待提高。为了能更好地提升MapReduce框架的计算性能,本文通过分析MapReduce思想中Map任务与Reduce任务处理机制,针对MapReduce思想中Reduce任务所在节点的负载不均衡现象,提出一种基于Value均值的MapReduce任务分配策略,通过制定Value均值收敛规则,使Value集合能够相对均匀地分布于不同Reduce任务中,使Reduce任务计算节点负载趋于均衡,不仅提高了数据处理效率,而且具有广泛性。

1 MapReduce思想

1.1 基本原理

MapReduce编程思想[7-8]的核心是将单个复杂的任务划分为多个简单的任务分别进行处理,分为Map任务与Reduce任务。Map任务主要用于数据格式化处理,将数据格式化为键值对的形式,Reduce任务负责接收键值对,将相同Key值的Value值进行归并,得到

1.2 处理过程

图1 MapReduce处理过程Fig.1 The processing of MapReduce

由图1可知,不同Map任务会产生不同的Key,Reduce任务会将相同Key值的Value值进行合并。每个Reduce任务会处理相同Key值的Value值集合,不同Key值的Value集合被分配到不同的Reduce任务中,导致Reduce任务量不同。

定义1:在MapReduce任务中,若不同key值所划分的Reduce任务量相差不大,则Reduce任务所在节点的负载相差不大,称Reduce任务分配相对均衡状态(RBS状态);反之,则称Reduce任务分配相对不均衡状态(RIS状态)。

2 Key值标签

2.1 传统任务分配(Traditional Task Allocation,TTA)

传统的MapReduce中Map任务不改变Key值,将原始数据格式化成键值对形式,经过MapReduce的Shuffle阶段,在Reduce计算节点上生成集合所包含的数据量不同,特别是复杂数据集,产生的List往往相差很大。有集合S1、S2举例如下:

={object1,object2,object3,…，objectn}(n为10＾6数量级)

={object1,object2,bject3,…objectm}(m为10＾9数量级)

数据处理时,两组List分别分配于不同的Reduce任务中,即位于不同的计算节点,忽略节点计算能力的差异,理想情况下,两集合数据进行相同处理时,时间开销T存在以下关系:

T(S2)=T(S1)×10＾3。

由此可得,处理集合S2的时间开销T(S2)大于处理集合S1的时间开销T(S1),为T(S1)的10＾3倍。

2.2 基于Key值任务分配(Key-Traditional Task Allocation,KTTA)

传统任务分配算法(TTA)无法均衡不同Reduce任务的数据集合,导致每个Key值的Reduce任务待处理的数据量存在差异。针对上述问题,提出基于Key值的任务分配策略(KTTA),Map任务执行完毕后,Value任务先计算每个集合元素数量N,并计算该集合元素个数的平均值Mean。每个值与均值的差异小于某个阈值ε,则进行K-means运算。

其主要过程如下:

步骤1:输入数据集InputDataSet(IS),通过Map任务,将IS数据集输出为键值对形式。

步骤2:获取每个key值所对应的集合的元素数量N,取所有N的平均值Mean。

步骤3:通过Map任务,将所有大于ε的List