Hadoop任务分配策略的改进摘要:HadoopT泛应用于大数据的并行处理，其现有的任务分配策略多面向同构环境，或者没有充分利用集群的全局信息，或者在异构环境下无法兼顾执行效率与算法复杂度。针对这些问题，提出异构环境下的任务分配算法入Flow算法，将原先一次完成的任务分配过程划分成多轮，每轮基于当前集群状态，以及上轮任务的执行情况，动态进行任务分配，直至全部任务分配结束，以期达到最优执行效率。通过与其他算法对比实验表明，XFlow算法能够更好地适应集群的动态变化，有效减少作业执行时间。关键词：Hadoop；MapReduce；任务分配；异构环境；最小费用最大流:TP301.6；TP393.027.2文献标志码：A0引言近年来，随着全球数据的爆炸式增长，海量数据的处理成为了一个新的研究热点。云计算[1]应运而生，类如MapReduce[2]>Dryad[3]等编程模型的出现，使得大规模集群计算变得更加简单。Hadoop[4]是GoogleMapReduce的开源实现，已经被广泛地应用于各种大数据的并行处理问题,在搜索引擎、文本处理、机器翻译等领域都得到了大量应用与研究。Hadoop具有良好的扩展性，能够处理分布在数以万计的低成本计算节点中的海量数据。例如：Facebook的Iladoop数据仓库中存储了超过2PB的数据，每天有超过7500个应用在Hadoop集群上运行，处理超过60TB的数据［5］。---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---Iladoop屮的文件在存储时被切分成若干个相同大小的数据块，每个数据块备份后分散存储在集群的数据节点上。在进行数据处理时，Hadoop首先将一个作业切分成若干个Map任务并分配到各个节点上并行执行，每个Map任务处理一个数据块，Reduce任务从各个节点上获取执行结果并产生最终的输出。在执行Map任务时，如果数据恰好在Map任务执行的节点上，则称该Map任务是木地任务，否则称为远程任务。执行一个木地的Map任务比执行一个远程的Map任务代价更小，在Hadoop这种网络带宽比较稀缺的环境中体现得更为明显。如何调度任务使得作业在执行过程中拥有更多的本地化任务从而减小作业执行代价已经成为了一个研究热点。当前主要的调度算法可以分为静态调度和动态调度两类。静态调度的调度策略事先确定，不考虑集群运行时的动态变化；而动态调度是调度器动态地获取集群的状态信息，并根据这些信息动态调整调度策略。Hadoop默认的任务分配算法［6］使用贪心算法，当一个节点出现空闲的资源时，尽可能地分配木地任务，如果没有本地任务，则分配远程任务。这种任务分配策略的优点是简单、易于实现，同时也减轻了Jobtracket的负担，但也存在着不利于任务执行的木地化的显著缺点。Facebook提出了公平调度器［7］,使用最大最小公平共享算法在作业间实现公平调度，该算法为新作业分配资源时必须强制结束已有作业的部分任务以释放资源，从而导致资源浪费；而且公平调度没有区分対待长作业和短作业，无法保证系统整体性能。Zaharia等［8］提出了延迟调度算法，即当一个作业中没有本地化的任务时，调度器---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---先调度其他作业，而让该作业等待一小段时间。该调度策略在集群屮存在大量短任务时能够非常冇效地提高任务的本地性，但当集群中的任务多为长任务时表现不佳。Yahoo!提出了计算能力调度器［9］,将作业以队列为单位进行划分，适合于多用户共享集群的情况。当节点出现空闲时，调度器会根据计算能力调度算法依次选择队列、作业和任务，但没有考虑异构环境下的系统行为。Zaharia等［10］提出了一种异构环境卜的调度策略，通过LATE(LongestApproximateTimetoEnd)算法，预测任务执行的进度，并在其他节点重新执行那些进度缓慢的任务。该策略考虑了节点Z间的异构性，并具有良好的鲁棒性，但对任务本地化考虑不够。以上调度器都属于动态调度，其共同的缺点是在节点资源出现空闲时才对进行任务的分配，没有利用JobTracker空闲时将分配策略预先制定好。为了更冇效地进行任务分配，Fischer等［11］对Hadoop任务分配问题进行了建模，提出了Hadoop任务分配(HadoopTaskAssignment,HTA)问题，即给定一个作业的数...