, 李国忠 1 , 陈瑜 1 , 黄超杰 1 , 杨吴同 1 1.电子科技大学 信息与软件工程学院, 成都 610054;
2.中国科学院重庆绿色智能技术研究院, 重庆 400714
收稿日期: 2016-06-29
基金项目: 国家自然科学基金资助项目（61672136，61650110513）；四川省科技厅项目（2016GZ0322）；中科院西部之光项目（R51A150Z10）；重庆市基础研究与前沿技术研究计划项目（cstc2015jcyjB0244）
作者简介: 田文洪(1972-),男,教授。E-mail:tian_wenhong@uestc.edu.cn
摘要：Hadoop集群广泛应用于企业和研究机构的大数据处理和并行计算中。该文针对Hadoop集群节点管理中缺少动态负载均衡和节能相互结合的调度技术的现状，提出一种动态负反馈调整算法，并设计和实现了一个用于Hadoop平台节点动态管理的系统。通过大量Hadoop经典测试用例测试，结果表明：该算法能够有效提高负载均衡并通过减少节点的空闲时间以有效地节能，与未使用本算法的结果相比，节点平均空闲休眠时间增加25%，节能14%。同时通过与其他算法相比，节点间均衡度有一定程度提升，平均负载方差减少10%。
关键词： 分布式计算 Hadoop 调度算法 动态负载均衡 节能调度
Combined load balancing and energy efficiency in Hadoop
TIAN Wenhong1,2
, LI Guozhong1, CHEN Yu1, HUANG Chaojie1, YANG Wutong11.School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China;
2.Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, Chongqing 400714, China
Abstract:Hadoop clusters are widely used in enterprises and research institutions but there are few tools in Hadoop to dynamically load balance and improve the energy efficiency. A dynamic load balancing method with negative feedback was developed for a dynamic management system for Hadoop systems and tested using classic Hadoop benchmark examples. This method reduces the total idle time of the Hadoop nodes by 25% and reduces energy consumption by 14% on average compared with other algorithms by improving the load balancing through reducing the load variations by 10%.
Key words: distributed computingHadoopscheduling algorithmdynamic load-balancingenergy-efficient scheduling
随着互联网的高速发展,自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 Hadoop运行结构图 |
| 图选项 |
步骤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 动态负反馈算法DANF2.1 Hadoop集群动态管理设计特点本文研究实现Hadoop上的一种新型动态负反馈调度算法DANF，该算法的特点主要包括：
1) 能根据负载自动对节点进行休眠和唤醒操作，能提高总体系统利用率，减少节点开机运行时间，同时减少能耗；
2) 能够避免抖动现象，减少负载方差以提高系统负载均衡度；
3) 设计的方法易于操作和实现。
2.2 负载模型为了计算节点负载，需要建立一个负载信息模型。数据和研究表明，在一个普通的服务器中，处理器的能耗占系统总能耗的40%以上，同时处理器的负载和系统的总能耗呈线性关系，因此将处理器作为一个分量进行建模。在Hadoop运行当中，JVM进程会处理大量的数据，当大量的数据从硬盘读入内存时，内存利用率会显著提高，为了模型的准确，将内存也纳入负载模型。
2.2.1 负载信息设Hadoop集群中一个节点j的负载向量为Lj≤Lcpuj，Lmemj>，其中Lcpuj为测量所得到的CPU的负载，Lmemj为测量所得到的内存的负载，为了衡量不同应用中CPU和内存的不同影响，引入系数p。其中p的取值范围为[0,1]，则节点j的负载
| ${{L}_{j}}=\sqrt{p{{L}^{2}}_{cpuj}+\left( 1-p \right){{L}^{2}}_{memj}}.$ | (1) |
| $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) |
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) |
| $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.2 节点休眠选择节点的选择是算法的核心部分，目前在动态管理系统中，节点的选择算法通常有以下几种选择。
1) 随机算法： 该算法的思想非常简单，是最容易理解和实现的一种算法，达到调度阈值时，随机选择一个节点进行休眠。
2) 轮询算法： 该算法的思想和操作也非常简单，就是将节点依次编号，然后每次按照编号依次休眠。
3) 最小负载算法： 每次对所有节点的负载值排序，然后从中选择一个当前最小负载的节点，将其休眠。
为了减少抖动现象的影响，本文提出一种用于节点选择的基于抖动系数的最小负载算法，该算法在最小负载算法的基础上，增加了抖动系数的计算，具体来说，对于节点j抖动系数kj定义如下：
| ${{k}_{j}}=\left| \frac{{{L}_{j}}({{t}_{i}})-{{L}_{j}}({{t}_{i-1}})}{\Delta t} \right|.$ |
2.3.3 节点唤醒选择当系统达到Wh时，需要将节点唤醒，由于节点休眠中负载较低，直接从队列中将各节点依次取出。
2.4 动态调度模块算法伪代码输入：系统所有节点的CPU和内存负载信息。
输出：系统某个节点的操作。
初始化所有节点，设置Wl,Wh大小。
DO
计算负载
IF Wl＜L(t)＜Wh
CONTINUES;
ELSE IF L(t)＜Wh
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)2计算，每个周期时间为10 s，其中LOAD为各个周期计算的平均值，LOADn为第n个周期的负载，进行5组测试取平均值。
图 2和图 3分别为WordCount和TeraSort方差对比结果。
 |
| 图 2 WordCount方差对比 |
| 图选项 |
 |
| 图 3 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) |
同样5组数据测试，收集完成相同任务对比使用动态调度和未使用动态调度情况下的节点闲置时间。对所有节点的闲置时间Ts进行对比，WordCount例子如图 4，TeraSort例子如图 5所示。
 |
| 图 4 WordCount节点闲置时间对比 |
| 图选项 |
 |
| 图 5 TeraSort节点闲置时间对比 |
| 图选项 |
可以看出，二者使用负反馈动态调整算法后都增加了节点的闲置时间，其中TeraSort相对于WordCount更加明显，测试体现出了DANF算法的优势。
在式(6)中，u是考虑了空闲时间的平均利用率，因此u=LOAD·Tr / Tall。
根据式(6)，由于总时间 Tall相同，Pmin和Pmax均为常数，故系统能耗和平均利用率成正比关系，此处系统空载能耗为 Pmin为50 W，Pmax为300 W，能耗对比分别如图 6和7所示。
 |
| 图 6 WordCount系统能耗对比 |
| 图选项 |
 |
| 图 7 TeraSort系统能耗对比 |
| 图选项 |
可以看出，使用DANF算法后，系统的能耗都得到了降低，与未使用DANF算法的结果相比，DANF算法综合所有测试例子的平均节能为14%。
4 结 论本文介绍了一种基于DANF算法的Hadoop集群动态负载均衡和节能调度方法。针对该调度算法，本文给出了具体实现过程，并对该系统进行了实际测试。同已有的算法相比，该调度算法在提高Hadoop集群利用率和负载均衡的同时，减少了系统总的能耗。针对这一领域，下一步将研究： 新型Hadoop集群调度系统设计，依据不同任务的特征进行综合调度以便减少系统总能耗以及进行不同子集群的负载均衡，使得系统总体完成时间在预定控制范围之内等。
参考文献
| [1] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Leverich J, Kozyrakis C. On the energy (in) efficiency of Hadoop clusters[J]. ACM SIGOPS Operating Systems Review, 2010, 44(1) : 61–65.DOI:10.1145/1740390 |
| [2] | Journal of Central South University(Science and Technology), 41(2):649-654.-->田文洪, 赵勇. 云计算:资源调度管理[M].北京: 国防工业出版社, 2011.TIAN Wenhong, ZHAO Yong. Cloud Computing:Resource Scheduling and Management[M].Beijing: National Defense Press, 2011.(in Chinese) |
| [3] | Journal of Central South University(Science and Technology), 41(2):649-654.-->王鹏. 云计算的关键技术与应用实例[M].北京: 人民邮电出版社, 2010.WANG Peng. Cloud Computing:Key Technologies and Applications[M].Beijing: People's Post and Telecommunication Press, 2010.(in Chinese) |
| [4] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Chen Y, Keys L, Katz R H. Towards energy efficient "mapreduce"[J]. EECS University of California at Berkeley, 2009. |
| [5] | Journal of Central South University(Science and Technology), 41(2):649-654.-->陈涛, 陈启买. 分布式计算机系统负载平衡研究[J]. 计算机技术与发展, 2006, 16(5) : 33–35.CHEN Tao, CHEN Qimai. Research on load balancing in distributed computing system[J]. Computer Technology and Development, 2006, 16(5) : 33–35.(in Chinese) |
| [6] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Chen Y, Ganapathi A S, Fox A, et al. Statistical workloads for energy efficient mapreduce[J]. EECS University of California at Berkeley, 2010. |
| [7] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Nedevschi S, Popa L, Iannaccone G, et al. Reducing network energy consumption via rate-adaptation and sleeping[J]. EECS Department, University of California, Berkeley, 2007. |
| [8] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Polo J, Carrera D, Becerra Y, et al. Performance management of accelerated mapreduce workloads in heterogeneous clusters[C]//Proc 39th IEEE Conf on Parallel Processing. San Diego, UC:IEEE Press, 2010:653-662. http://cn.bing.com/academic/profile?id=2109569477&encoded=0&v=paper_preview&mkt=zh-cn |
| [9] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Xie J, Yin S, Ruan X, et al. Improving mapreduce performance through data placement in heterogeneous hadoop clusters[C]//IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), Atlanta, GA:IEEE Press, 2010:1-9. http://cn.bing.com/academic/profile?id=1996438407&encoded=0&v=paper_preview&mkt=zh-cn |
| [10] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Kim K H, Buyya R, Kim J. Power aware scheduling of bag-of-tasks applications with deadline constraints on DVS-enabled clusters[C]//IEEE International Symposium on CLUSTER Computing & the Grid. Rio:IEEE Computer Society, 2007:541-548. http://cn.bing.com/academic/profile?id=2109558263&encoded=0&v=paper_preview&mkt=zh-cn |
| [11] | Journal of Central South University(Science and Technology), 41(2):649-654.--> Lee Y C, Zomaya A Y. Minimizing energy consumption for precedence-constrained applications using dynamic voltage scaling[C]//Proc 9th IEEE/ACM International Symposium on Cluster, Cloud and the Grid Computing. Washington, D.C., USA:IEEE Press, 2009:92-99. http://cn.bing.com/academic/profile?id=2117706453&encoded=0&v=paper_preview&mkt=zh-cn |
| [12] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Zhang X P. Electric power system analysis operation and control[J]. Electric Engineering, 2006, 2(3) : 1–42. |
| [13] | Journal of Central South University(Science and Technology), 41(2):649-654.-->博韦·西斯特. 深入理解Linux内核[M]. 陈莉君, 张琼声,张宏伟, 译. 北京:中国电力出版社, 2005. Bovet D P. Understanding the Linux Kernel[M]. CHEN Lijun, ZHANG Qiongsheng, ZHANG Hongwei (Translation). Beijing:China Electric Power Press, 2005. (in Chinese) |
| [14] | Journal of Central South University(Science and Technology), 41(2):649-654.-->Beloglazov A, Abawajy J, Buyya R. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[J]. Future Generation Computer Systems, 2012, 28(5) : 755–768.DOI:10.1016/j.future.2011.04.017 |
