Hadoop环境下节点负载均衡调度策略的设计与实现

王溪波 王珊珊 王越峰

（沈阳工业大学 辽宁省沈阳市 110000）

1 引言

云计算是用户通过远程连接来获取计算资源的一种计算方式，许多IT公司都推出相应的云计算平台，将云计算技术看成是一项重要的且有利于公司发展的技术，由此看出对云计算的研究是紧追IT技术的发展路线，有较高的应用价值。但伴随云计算技术的发展会涌现大量的数据，用户和企业都会面临海量数据的存储与处理问题，分布式存储模块可以存储海量数据，系统将大的数据块拆分成若干小的数据块，将这些小的数据块存放在集群的各个节点上。云计算技术的重要典型框架是MapReduce框架，为海量数据的处理提供平台。Hadoop是MapReduce框架的开源实现，既为海量数据的存储提供了可靠的平台-HDFS(Hadoop分布式文件系统)[1]。又能够很好地实现MapReduce框架，MapReduce框架为提高云计算平台上的大批量作业的性能而设计的[2]。

2 Hadoop体系结构

Hadoop是可靠的，可扩展的和开放式的源代码框架，由Apache基金会所开发。Hadoop系统本身具有高扩展性，高效性以及高可靠性等特质。分布式文件系统HDFS（Hadoop Distributed Files System）和分布式计算框架 MapReduce计算架构属于Apache Hadoop的两个核心子模块。

2.1 HDFS分布式文件系统

作为Hadoop集群的核心子项目之一的分布式并行文件系统是基于流数据访问模式开发的，可用于分布式计算的数据存储管理，也可以满足超大规模文件处理的需求。HDFS将分好的数据块存储在各个节点上，对数据块进行备份，以防节点失效。HDFS只需一次写入数据便可以多次使用该数据，这种访问方式具有高效性[5]。在HDFS中，数据可用性可通过数据备份来实现。数据丢失将会立即采取修复措施[6]。

用户需要在系统中运行的应用程序被称为作业，任务作为作业的基本工作单元，各个计算节点可以处理任务，可以把一个作业分成一个或者多个任务[7]。这些任务处理完后被存储在分布式文件系统中。

2.2 MapReduce计算框架

规模性，多样性和高速性的特性促进大数据更加快速的发展[8]。MapReduce是一种编程框架，支持高效的大规模计算，由Google提出。MapReduce架构如图1所示。

系统通常设计为在无共享架构中运行。数据可以分布式存储，并通过并行使用多个磁盘来提高输入/输出速率。MapReduce计

图1：MapReduce架构示意图

算框架依赖于Shuffle机制。Shuffle机制[9]的工作原理是把在Map任务中处理完的作业拉取到Reduce任务执行之前。分块，拷贝和排序代表Shuffle机制的每个不同的阶段。MapReduce的主要目标是分配处理以利用并行处理能力。这通常是通过将输入数据集分割成若干块在不同的机器上运行来完成的。大型集群可以通过MapReduce框架进行高效排序，在几个小时内达到对数兆字节的速度。

3 国内外研究现状

减少作业的完成时间和提高数据本地性是目前许多调度算法的研究重点。在基于节点本地任务完成时间预测的基础上，通过控制不同的资源分配策略来提高数据本地性。现有算法对于作业缺乏整体性规划。

估算一个作业的剩余完成时间方面，杨浩等人[10]设计并实现了一种基于空闲时间的硬实时调度器 LSS，根据作业的剩余完成时间来调整作业的优先级，作业越快处理完优先级越高。Teng等人[11]提出的基于截止时间的硬实时任务调度算法 SPS，该算法通过流工作的周期长短来规定作业的优先级，同时尽量使作业在本地执行，从而大大提高了作业在本地完成的几率。Ullah等人[12]提出了一种新的抢占方法，该方法在进行抢占决策时考虑了被执行作业的剩余执行时间。为了让作业能在时间约束范围内执行完，卢慧[13]提出一种基于资源预估的作业调度算法。不同作业对资源的需求也有所不同，根据资源预估模型以及数据本地性因素来改进延迟调度策略。

表1：Map任务的平均运行时间实现伪代码

图2：数据块分布情况

图3：非本地任务数量实验对比

现实中存在40%的重复性工作[14]，根据重复性工作规律探索出可预测的特征，可以对节点的预计完成时间进行预测从而规划资源分配，提高系统资源利用率。

4 数据本地化调度策略设计

数据本地性是Hadoop集群平台下衡量作业调度器的重要的指标。数据可以在同一机架内传输，也可在不同的机架内传输，这种跨机架的传输方式，产生网络 I/O，降低作业的平均完成时间，增加非本地任务的数量。节点优先处理本地任务可以实现数据本地化，数据的读取和处理便于任务的执行。本地任务越多，数据读取时间越短，非本地任务会加重数据读取时间，它需要从其它节点上读取数据，加重网络负担，使节点间信息传输产生延迟。降低系统运行效率。

数据分配不均会导致任务负载失衡，某些节点需要处理的任务增多，而其余节点会因没有需要处理的任务处于空闲状态。通过计算节点负载情况的任务调度方法来解决MapReduce集群存在大量非本地任务的问题，该方法先计算节点的负载情况，根据节点负载情况进行调度，有利于数据块的合理分配，让节点间的负载处于中间状态，这种根据节点的使用情况进行任务分配的策略在很大程度上满足了数据本地化思想。

如图2表明数据块在集群中的分布状况。MapReduce在选择任务进行调度时，只是简单的根据网络拓扑在同级任务中随机选取。这样的选择方式会造成更多非本地任务的产生,从而降低处理和存储速度。通过计算节点负载进行任务分配的方法可以尽可能的解决这一问题。

5 算法实现

在观察节点负载情况时，并不能直接根据节点剩余任务数量来分配任务，节点性能不同，能处理的任务数量就不同，性能好的节点本身就能处理更多的本地任务。节点在作业执行之初先不需要分配非本地任务，在执行本地任务的过程中根据负载情况完成非本地任务的分配，这一过程是非静态的。所以本文通过节点的本地任务预计完成时间与全部节点执行本地任务的预计完成时间的平均值做比较，小于平均值极为负载较轻的节点，反之较重。

节点的本地任务预计完成时间是通过Map任务的平均运行时间与所有的本地任务的数量的乘积计算得出的。代表已完成的Map任务的平均运行时间，节点中本地任务的数量用表示，给节点分配的任务可能是本地任务和非本地任务，先通过本地任务数量的计算再进行任务合理分配。如公式（2）所示。节点的本地任务预计完成时间：

全部节点执行本地任务的预计完成时间的平均值根据节点的本地任务预计完成时间的总值与节点的个数的比值计算得出。通过平均值与单个节点的预计完成时间我们可以观察到节点的状态。如公式（3）所示。全部节点执行本地任务的预计完成时间的平均值：

6 实验设计

本文研究的作业调度算法是基于Hadoop平台之下，因此需要搭建Hadoop集群。Hadoop集群的核心是HDFS和MapReduce计算框架。通过虚拟机的方式搭建Hadoop集群及其测试环境，假设存在两个机架，给每个机架分配5台虚拟机，每一个虚拟机占据512MB的内存。测试工作为WordCount，通过测试传统的任务调度策略非本地任务的数量以及平均完成时间和本文提出的负载均衡的任务调度策略中非本地任务的数量和平均完成时间进行对比。

首先对两种算法的非本地任务数量进行对比实验，运行job1，job2，job3和job4四个作业，非本地任务数量实验数据如图3所示。默认调度算法的作业中非本地任务数量分别是59，49，99和120。负载均衡的调度策略中非本地任务数量是43，33，85，109。由实验对比图可以看出作业1非本地任务数量降低了27%，作业2的非本地任务数量降低了32%，作业3的非本地任务数量降低了14%，以及作业4的非本地任务数量降低了9%。综上四个任务的非本地任务数量降低值可以预估每个任务的降低值。通过负载均衡调度算法可以看出非本地任务数量降低了20.5%。节点负载均衡调度策略可以减少系统中非本地任务的数量，同时减少数据迁移量，减少任务处理时间，提高系统效率。

其次，对两种算法的平均完成时间进行对比实验，默认调度算法下job1 平均完成时间为700s，job2的平均完成时间为350s，job3的平均完成时间为460s以及job4的平均完成时间为653s。负载均衡调度策略中作业的平均完成时间分别为399，268，430，590。节点负载均衡的任务调度策略相比与系统默认的调度策略有一定的缩短，平均完成时间实验数据如图4所示。作业1的平均完成时间缩短了43%，作业2的平均完成时间缩短了23%，作业3的平均完成时间缩短了6%，作业4的平均完成时间缩短了9%。由多个个体可以估算出整体平均完成时间缩短了20.25%，通过实验证明节点负载调度策略降低了系统的平均完成时间，有效的优化了系统性能。

通过对非本地任务数量以及平均完成时间的对比实验可以看出，负载均衡的任务调度策略比系统默认的调度策略的非本地任务数量减少了，平均完成时间降低了，网络I/O减少了，系统性能提高了。

图4：作业的平均完成时间对比

7 结束语

本文主要提出对数据本地性调度方面进行优化，通过计算节点负载情况的方法来减少非本地任务的产生，从而减少数据迁移量。借助集群环境中MapReduce计算框架来实现根据节点情况分配任务的调度策略，提升系统性能。这种计算节点的调度算法仍存在一些不足，所以接下来，从这几方面完善该任务调度策略。