随着互联网的高速发展,自2005年以来,信息量的增长呈指数级上升,据互联网数据中心(Internet Data Center，IDC)的调查显示，2011年全球被创建和复制的数据总量为1.8 ZB，并且预测2020年这个数字将达到35 ZB^[1]。传统的数据处理和分析方法受到单机CPU和内存的限制，在处理海量数据时出现计算瓶颈，迫使工业界以及学术界研究新的方法来处理和存储数据,在这种情况下，Hadoop应运而生并广泛用于工业界以及学术界,Hadoop的高效和易用得到了广泛的认可，但是同其他集群系统一样，Hadoop集群也存在着能耗过高问题。根据美国自然资源保护委员会的数据，2013年美国数据中心统计的电力能耗达到910亿 kWh^[2]。这样大规模的用电造成的大量碳排放对环境造成了巨大的影响； 与此同时，约有1/3的服务器利用率非常低，仅以18%的容量运行，浪费了大量的电力。2013年中国数据中心统计总用电量约700亿 kWh，其中半数以上都存在严重的能耗问题，以业界的标准电源使用效率(power usage effectiveness,PUE)来计算，中国的PUE普遍高于2.0，属于极低的能耗利用率，作为耗能大户，如何降低数据中心能耗，提高能源利用率，成为了数据中心迫切需要解决的问题。

长期以来，计算服务器的能耗问题^[2]都是一个广泛研究的问题，特别是对于大规模计算，能耗的减少可以有效地提高效率和减小对环境的影响。王鹏^[3]研究表明，计算机的能耗主要取决于负载，换句话说，依据负载情况动态的暂停节点可以有效地减少集群能耗。一项由Google工程师花费6个月的研究表明，大部分的计算节点在75%的时间CPU利用率都低于50%，如果大量节点处于低负载情况，可以采用暂停部分节点的方法，达到负载均衡和节能的目的^[4-5]。作为需要大规模节点的系统，Hadoop在设计之初并未考虑动态调度。传统的Hadoop中，集群节点从任务一开始节点数目便已经完全确定，对于能耗和资源利用率都不高。

本文提出一个Hadoop动态管理的算法并用软件实现，可以根据任务量的大小，实现每隔一段时间自动对Hadoop所有节点进行负载信息采集，通过自定义的负载模型判断负载信息值是否低于预定范围，控制对节点的暂停和启动，以达到集群节能优化的目的。

1 Hadoop概述和研究背景 1.1 Hadoop框架

Hadoop是一个能够对大数据进行分布式处理的软件框架。Hadoop的构成最主要是MapReduce和HDFS。MapReduce是通过Map和Reduce阶段对并行处理任务的分解与结果的汇总。HDFS是Hadoop分布式文件系统，Hadoop具有很好的通用性，极大地方便了编程人员在不会分布式并行编程的情况下，将程序运行在分布式系统上^[3]。

1.2 Hadoop运行流程

Hadoop将计算任务抽象成map和reduce 2个计算过程，计算流程如图 1所示。

步骤1 首先对输入数据源进行切片，Master调度节点读取输入文件执行map任务。

步骤2 节点执行map任务，将任务输出保存在本地。

步骤3 合并中间结果并进行Shuffle和Sort。

步骤4 master调度worker执行reduce任务，reduce worker读取map任务的输出文件并将任务输出保存到HDFS。

很多研究人员已经开始了Hadoop节能方面的研究，Leverich等^[1]认为Hadoop在节能方面存在非常大的改进空间，建议对节点数据采用新的算法； Chen等^[6]基于节点、 工作时间、 功率建立了一个模型，并认为基于这个模型能取得较好效果^[3]； 他们也认为优化能耗效率和优化性能有同样的价值^[4]。 瑞士科学家修改了Hadoop的块分配算法，减少了Hadoop的能源消耗^[7]，其研究致力于静态数据块分配，不能实现动态处理； Polo等^[8]对于异构的Hadoop集群的调度算法进行了研究和优化； Xie等^[9]实现了Hadoop集群调度的相关工作，其研究主要致力于通过和硬件系统的紧密结合实现一种对不同任务进行定制的调度算法。此外，动态电压调节也被研究人员广泛使用于减少能耗^[10-11]，不过不足的是它需要特殊的硬件环境。本文提出的设计可以动态休眠空闲节点降低系统平均利用率，不需要特殊硬件设施，从而减少能耗。

2 动态负反馈算法DANF 2.1 Hadoop集群动态管理设计特点

本文研究实现Hadoop上的一种新型动态负反馈调度算法DANF，该算法的特点主要包括：

1) 能根据负载自动对节点进行休眠和唤醒操作，能提高总体系统利用率，减少节点开机运行时间，同时减少能耗；

2) 能够避免抖动现象，减少负载方差以提高系统负载均衡度；

3) 设计的方法易于操作和实现。

2.2 负载模型

为了计算节点负载，需要建立一个负载信息模型。数据和研究表明，在一个普通的服务器中，处理器的能耗占系统总能耗的40%以上，同时处理器的负载和系统的总能耗呈线性关系，因此将处理器作为一个分量进行建模。在Hadoop运行当中，JVM进程会处理大量的数据，当大量的数据从硬盘读入内存时，内存利用率会显著提高，为了模型的准确，将内存也纳入负载模型。

2.2.1 负载信息

设Hadoop集群中一个节点j的负载向量为L_j≤L_cpuj，L_memj>，其中L_cpuj为测量所得到的CPU的负载，L_memj为测量所得到的内存的负载，为了衡量不同应用中CPU和内存的不同影响，引入系数p。其中p的取值范围为[0,1]，则节点j的负载

${{L}_{j}}=\sqrt{p{{L}^{2}}_{cpuj}+\left( 1-p \right){{L}^{2}}_{memj}}.$

(1)

进一步，设集群拥有n个节点，则所有n个节点在时刻t_i的平均负载即为集群在时刻t_i的负载，故集群负载

$L\left( {{t}_{i}} \right)=\sum\limits_{i=1}^{n}{\frac{\sqrt{p{{L}_{cpu}}{{({{t}_{i}})}^{2}}+\left( 1-p \right){{L}_{mem}}{{({{t}_{i}})}^{2}}}}{n}}.$

(2)

其中p的取值根据具体应用决定，若应用为消耗大量CPU的科学计算，则可以取较大的值，如0.8以上； 若应用为消耗大量内存的大数据运算，则可以将值设置较小。

2.2.2 时间度量的选择

该值是一个动态值，由于存在抖动现象，获得更加准确的数据需要设置一个观察周期。若观察周期太大，信息更新太慢，则节点信息不准确； 若观察周期太小，则过于频繁查询反而影响节点数据。经过测试表明，观察周期与系统任务有关系，密集型计算应用中应当减少调度，否则对系统性能影响较大； 大规模数据中可以减少调度时间，以减少能耗。

2.2.3 负反馈机制

在Hadoop集群中，由于距离或者网络的延迟，或者是某个任务启动或者停止，会让采集到的CPU或内存信息产生一定的抖动误差，为了减少这种波动引起的误差，提高负载信息准确性，引入控制系统中常见的负反馈调整机制，在控制系统中，负反馈主要是在输入时刻加入调整量，抵消变化过大的情况。

在控制系统理论中，通常使用一种负反馈调整方法来减少波动误差，这里采用已经在自动化理论中广泛使用的自动调节公式。若系统在上一个周期值为X(t-1)，当前周期的观测值为X′(t)，则当前周期的值

$X(t)=X\left( t-1 \right)+\sqrt[3]{\frac{X\prime {{(t)}^{2}}}{A}-X\left( t-1 \right)}.$

(3)

在实际情况中，A通常选择接近X(t-1)的值，将自动调节公式应用到负载信息计算中，设系统在上一个周期负载值为L(t_i-1)，A为L(t_i-1)，本周期的观测值为L′(t_i)，则系统的负载为

$L({{t}_{i}})=\left\{ \begin{matrix} L({{t}_{i-1}})+\sqrt[3]{L\prime ({{t}_{i}})-L({{t}_{i-1}})}, & i\ge 1; \\ L\prime ({{t}_{i}}), & i=0. \\ \end{matrix} \right.$

(4)

2.3 DANF调度算法设计与实现 2.3.1 调度条件

利用式(1)—(4)中得出的负载值，通过预设或让用户自己定义W_l和W_h,W_l为负载下阀值，W_h为负载上阈值。当W_l＜ (t_i)＜W_h 时为理想负载，不用处理； 当节点负载 (t_i)＜W_l时为轻负载，按照休眠选择算法休眠结点，每次休眠一个节点或多个节点至系统平均负载为理想负载； 当L(t_i)>W_h时刻为高负载，按照节点唤醒选择算法唤醒节点，每次唤醒一个节点或多个节点至系统平均负载为理想负载^[12]。

2.3.2 节点休眠选择

节点的选择是算法的核心部分，目前在动态管理系统中，节点的选择算法通常有以下几种选择。

1) 随机算法： 该算法的思想非常简单，是最容易理解和实现的一种算法，达到调度阈值时，随机选择一个节点进行休眠。

2) 轮询算法： 该算法的思想和操作也非常简单，就是将节点依次编号，然后每次按照编号依次休眠。

3) 最小负载算法： 每次对所有节点的负载值排序，然后从中选择一个当前最小负载的节点，将其休眠。

为了减少抖动现象的影响，本文提出一种用于节点选择的基于抖动系数的最小负载算法，该算法在最小负载算法的基础上，增加了抖动系数的计算，具体来说，对于节点j抖动系数k_j定义如下：

${{k}_{j}}=\left| \frac{{{L}_{j}}({{t}_{i}})-{{L}_{j}}({{t}_{i-1}})}{\Delta t} \right|.$

其中： Δt为一个观察周期的时间长度，k_j大于0。显然，k_j值越大，表示节点相对稳定状况越差，考虑抖动系数后，若节点负载较小，但变化较大，也会由于抖动系数较大而不会被选择，因此提高了稳定性。算法在选择节点时，计算每一个节点的负载和抖动系数的乘积k_jL_j(t_i)，然后将乘积排序，每次取出最小值，有效地防止了频繁地调度某一个节点对系统的影响，良好的节点选择可以有效提高系统的稳定性。

2.3.3 节点唤醒选择

当系统达到W_h时，需要将节点唤醒，由于节点休眠中负载较低，直接从队列中将各节点依次取出。

2.4 动态调度模块算法伪代码

输入：系统所有节点的CPU和内存负载信息。

输出：系统某个节点的操作。

初始化所有节点，设置W_l,W_h大小。

DO

计算负载

IF W_l＜L(t)＜W_h

CONTINUES;

ELSE IF L(t)＜W_h

FOR每一个节点

计算所有节点基于抖动的最小负载并按升序排列

取出第一个节点，并放入休眠队列

END FOR

ELSE

取出休眠队列队第一个节点并唤醒

END DO

2.5 系统具体实现

整个系统包括资源获取、 远程控制和节点控制3个模块。

2.5.1 资源获取模块

资源获取主要通过读取linux进程文件系统procfs实现，procfs是一个伪文件系统^[13]，它允许对一些非传统意义上的文件通过标准文件I/O接口进行访问。用户执行ls(1)命令显示/proc/目录结构时，系统读取内核内存并返回相应内容，因此可以利用它来计算CPU利用率和内存信息。

2.5.2 远程控制模块

远程控制模块使用远程SSH调用实现，使用第三方Java类库Ganymed SSH-2 for Java(用纯Java实现SSH-2协议的一个包)直接在Java程序中连接SSH服务器。

2.5.3 系统节点增/删模块

使用Java文件流在配置文件中增加和删除节点信息，通过远程SSH调用进行节点信息刷新。

3 性能分析对比 3.1 测试环境

采用16个节点组建Hadoop集群，每个节点配置相同，均为双核处理器，512 MB内存，采用CentOS 6.3系统，Hadoop版本为Hadoop 0.21。

3.2 设计性能测试

测试选用Hadoop计算例子WordCount和排序TeraSort，WordCount数据来源于维基百科，TeraSort数据来源于TeraGen，输入数据大小分别为0.5，1，2，4，8 GB，按照设定周期监控集群资源，在节点的选取过程中分别使用随机算法、 轮转算法、 最小负载算法和负反馈动态调整(DANF)算法。

3.2.1 负载均衡性能测试

为了衡量算法中节点负载均衡程度，可以通过调度后负载均衡程度来衡量。采用方差 (LOADn-LOAD)²计算，每个周期时间为10 s，其中LOAD为各个周期计算的平均值，LOADn为第n个周期的负载，进行5组测试取平均值。

图 2和图 3分别为WordCount和TeraSort方差对比结果。

可以看出，TeraSort相比WordCount方差更大，DANF算法在实际运行过程中，由于每次选取的节点抖动比较小，从而使得集群节点负载值方差较小，系统负载更加均衡。

3.2.2 节能测试

评估标准： 为了度量能耗，采用线性能耗模型^[14]

$\begin{align} & E=P(u){{T}_{all}}= \\ & [{{P}_{min}}+({{P}_{max}}-{{P}_{min}})\text{ }u]{{T}_{all}}. \\ \end{align}$

(6)

其中： P_min是系统空闲时的能耗，P_max是服务器满载时的能耗，u是服务器T_all时间内的平均利用率，T_all是服务器开始到测试结束开机总时间。设 T_r为节点工作时间，T_s为节点空闲时间，则 T_all=T_r+T_s。

同样5组数据测试，收集完成相同任务对比使用动态调度和未使用动态调度情况下的节点闲置时间。对所有节点的闲置时间T_s进行对比，WordCount例子如图 4，TeraSort例子如图 5所示。

可以看出，二者使用负反馈动态调整算法后都增加了节点的闲置时间，其中TeraSort相对于WordCount更加明显，测试体现出了DANF算法的优势。

在式(6)中，u是考虑了空闲时间的平均利用率，因此u=LOAD·T_r / T_all。

根据式(6)，由于总时间 T_all相同，P_min和P_max均为常数，故系统能耗和平均利用率成正比关系，此处系统空载能耗为 P_min为50 W，P_max为300 W，能耗对比分别如图 6和7所示。

可以看出，使用DANF算法后，系统的能耗都得到了降低，与未使用DANF算法的结果相比，DANF算法综合所有测试例子的平均节能为14%。

4 结 论

本文介绍了一种基于DANF算法的Hadoop集群动态负载均衡和节能调度方法。针对该调度算法，本文给出了具体实现过程，并对该系统进行了实际测试。同已有的算法相比，该调度算法在提高Hadoop集群利用率和负载均衡的同时，减少了系统总的能耗。针对这一领域，下一步将研究： 新型Hadoop集群调度系统设计，依据不同任务的特征进行综合调度以便减少系统总能耗以及进行不同子集群的负载均衡，使得系统总体完成时间在预定控制范围之内等。