论文部分内容阅读
摘 要 Hadoop作为一个开源云计算框架，因为其优秀的分布式存储能力及其上运行的Map Reduce计算框架，越来越多的公司用Hadoop处理庞大的数据。负载均衡对分布式计算的性能有重要影响，Hadoop基于最简单的hash算法对任务进行分派，并没有对异构环境及多任务运行环境的因素做过多考虑。为了解决上述存在的不足，我们提出一种负载均衡框架，对计算节点的性能情况进行监控，预测节点的计算能力，依据预测结果来对Map Reduce的计算任务进行分配，从而最大化分布式集群的计算能力。
关键词 Hadoop；Map Reduce；负载均衡；性能预测
中图分类号：TP311 文献标识码：A 文章编号：1671-7597（2015）02-0063-02
随着互联网络、智能设备的迅速发展，每个人每天在网络上都会产生大量的数据，对于企业来说，对于大数据的存储与处理越发显得重要。在Hadoop上面的Map Reduce是一个强大的分布式计算框架。它的执行包括两个基本的函数：Map和Reduce。对于一个计算任务，框架会把任务分成一些Map与Reduce作业，S每个作业在不同的计算节点上并行执行，良好的调度算法能够显著的提高系统的并行性、资源利用率，使系统达到负载均衡。
对于Map Reduce操作的负载均衡是困难的，默认的Hadoop调度算法根据数据本地性原则选择合适的节点执行Map作业，对于Reduce操作则采用hash算法来把不同key的数据分给不同的Reduce作业。默认的调度算法有两个明显的问题，首先，该算法没有对异构环境进行考虑，对于大规模的分布式集群来说，很难保证机器的同构性，因此，若对性能不同的机器上执行相同的Reduce作业，必然會导致执行效率变低；其次，Hadoop是一个可以执行多任务的系统，当前环境下可能已经有一些任务正在运行，那么每个节点的剩余计算能力也不相同，同样不能将Reduce作业平均分配到每个节点。因此，本文提出了一个基于性能预测的Reduce作业调度算法。
1 相关技术
1）Map Reduce。
Map/Reduce是Google提出的一种并行分布式计算架构，用于大规模数据集的并行计算，现在已在搜索和处理海量数据领域得到了广泛的应用。Google的云计算技术源于信息检索领域的海量数据的分析任务，指定一个Map函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce函数，用来保证所有映射的键值对中的每一个共享相同的键组。Map操作是一个分解的过程，它将输入数据拆分为大量的数据块，将每一个数据块分配给一个计算节点进行处理，从而具有分布式的特点；Reduce操作与Map操作刚好相反，会将分开的数据整合到一起，最后将汇总的结果进行输出。
2）指数平滑法。
指数平滑法（Exponential Smoothing，ES）是布朗（Robert G.Brown）所提出，布朗认为时间序列的态势具有稳定性或规则性，所以时间序列可被合理地顺势推延，最近的过去态势，在某种程度上会持续的未来，所以将较大的权数放在最近的资料。指数平滑法是用以往的历史数据的指数加权组合，来直接预报时间序列的将来值。
2 可用计算节点性能估算
1）性能定义。
为了对分布式节点的运算能力进行估算，首先需要对分布式计算节点的计算能力进行建模。计算节点的性能指标通常由cpu速度、内存容量、磁盘读写速度、网络带宽等多种因素相关，为了简化性能评估模型，本文只对cpu计算速度指标进行研究。对于cpu的计算速度来说，最基本的评价要素为cpu的主频、多核能力与并行能力。
根据上述公式一系列共识，我们可用通过原始的cpu性能指标、实时cpu运行指标以及估计算法预测每个可用计算节点的可用计算能力。下面，我们将根据计算得到的结果，对Reduce工作进行合理的调度。
3 基于预测结果的调度算法
Map Reduce主要分为Map函数与Reduce函数两个阶段，对于Map函数来说，数据移动的代价远远数据计算的代价，因此默认的数据本地化计算已经拥有较好的性能。对于Reduce函数来说，由于运行环境的异构性以及多任务的计算环境，如果把更多的Reduce任务分配到计算能力更强的机器，则会显著提高框架性能。因此我们提出了以下对于Reduce任务进行分配的算法：
首先根据每台可用计算节点的性能指标计算整个集群的性能；然后根据Reduce任务个数对集群性能进行均分，得到每个Reduce任务的均分性能；接着建立最大堆的数据结构，保存每个可用计算节点的性能指标，对于每一个Reduce任务，依次取最大堆顶的计算节点进行任务分配，分配后减去Reduce均分性能，若性能大于0，则入堆，否则把计算节点从堆中删除，直到Reduce任务分配完毕位置。
4 结论
本文主要分析了当前Hadoop中Map Reduce负载均衡策略对于异构环境以及多任务环境的不足，并且尝试提出了一种基于平滑指数预测的Reduce任务调度框架，依据每个可用计算节点的计算能力来对任务进行调度，并给出了理论方法与算法
描述。
本文提出的框架可以对Map Reduce负载均衡进行优化，但也存在需要补充的一些地方，首先对于性能的定义与估算只考虑了cpu计算能力，没有对存储、网络等指标进行考虑，其次每个Reduce任务根据hash算法获得计算数据，计算数据是否均匀与数据逻辑有关，本文并没有解决这个问题。作者将会在将来的工作中着力解决上述两个问题。
注：本文受多摄像头的吸虫机绿色控害技术研究（国家星火项目2011GA750019）资助
参考文献
[1]K. Shvachko， H. Kuang， S. Radia， R. Chansler， “The Hadoop Distributed File System，” 26th IEEE Symposium on Mass Storage Systems and technologies， Yahoo！， Sunnyvale， pp. 1-10， May 2010.
[2]J. Dittrich， J.-A. Quian?e-Ruiz， A. Jindal， Y. Kargin， V. Setty and J.Schad， “Hadoop++： Making a yellow elephant run like a cheetah（without it even noticing），” Proceedings of VLDB Endowment，3（2），pp.515-529，September 2010.
[3]柳香，李瑞台，李俊红，段胜业.Hadoop性能优化研究[J].河北师范大学学报（自然科学版），2011（06）：567-570.
[4]刘娟，豆育升，何晨，唐红.基于调度器的Hadoop性能优化方法研究[J].计算机工程与设计，2013（01）：190-194.
关键词 Hadoop；Map Reduce；负载均衡；性能预测
中图分类号：TP311 文献标识码：A 文章编号：1671-7597（2015）02-0063-02
随着互联网络、智能设备的迅速发展，每个人每天在网络上都会产生大量的数据，对于企业来说，对于大数据的存储与处理越发显得重要。在Hadoop上面的Map Reduce是一个强大的分布式计算框架。它的执行包括两个基本的函数：Map和Reduce。对于一个计算任务，框架会把任务分成一些Map与Reduce作业，S每个作业在不同的计算节点上并行执行，良好的调度算法能够显著的提高系统的并行性、资源利用率，使系统达到负载均衡。
对于Map Reduce操作的负载均衡是困难的，默认的Hadoop调度算法根据数据本地性原则选择合适的节点执行Map作业，对于Reduce操作则采用hash算法来把不同key的数据分给不同的Reduce作业。默认的调度算法有两个明显的问题，首先，该算法没有对异构环境进行考虑，对于大规模的分布式集群来说，很难保证机器的同构性，因此，若对性能不同的机器上执行相同的Reduce作业，必然會导致执行效率变低；其次，Hadoop是一个可以执行多任务的系统，当前环境下可能已经有一些任务正在运行，那么每个节点的剩余计算能力也不相同，同样不能将Reduce作业平均分配到每个节点。因此，本文提出了一个基于性能预测的Reduce作业调度算法。
1 相关技术
1）Map Reduce。
Map/Reduce是Google提出的一种并行分布式计算架构，用于大规模数据集的并行计算，现在已在搜索和处理海量数据领域得到了广泛的应用。Google的云计算技术源于信息检索领域的海量数据的分析任务，指定一个Map函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce函数，用来保证所有映射的键值对中的每一个共享相同的键组。Map操作是一个分解的过程，它将输入数据拆分为大量的数据块，将每一个数据块分配给一个计算节点进行处理，从而具有分布式的特点；Reduce操作与Map操作刚好相反，会将分开的数据整合到一起，最后将汇总的结果进行输出。
2）指数平滑法。
指数平滑法（Exponential Smoothing，ES）是布朗（Robert G.Brown）所提出，布朗认为时间序列的态势具有稳定性或规则性，所以时间序列可被合理地顺势推延，最近的过去态势，在某种程度上会持续的未来，所以将较大的权数放在最近的资料。指数平滑法是用以往的历史数据的指数加权组合，来直接预报时间序列的将来值。
2 可用计算节点性能估算
1）性能定义。
为了对分布式节点的运算能力进行估算，首先需要对分布式计算节点的计算能力进行建模。计算节点的性能指标通常由cpu速度、内存容量、磁盘读写速度、网络带宽等多种因素相关，为了简化性能评估模型，本文只对cpu计算速度指标进行研究。对于cpu的计算速度来说，最基本的评价要素为cpu的主频、多核能力与并行能力。
根据上述公式一系列共识，我们可用通过原始的cpu性能指标、实时cpu运行指标以及估计算法预测每个可用计算节点的可用计算能力。下面，我们将根据计算得到的结果，对Reduce工作进行合理的调度。
3 基于预测结果的调度算法
Map Reduce主要分为Map函数与Reduce函数两个阶段，对于Map函数来说，数据移动的代价远远数据计算的代价，因此默认的数据本地化计算已经拥有较好的性能。对于Reduce函数来说，由于运行环境的异构性以及多任务的计算环境，如果把更多的Reduce任务分配到计算能力更强的机器，则会显著提高框架性能。因此我们提出了以下对于Reduce任务进行分配的算法：
首先根据每台可用计算节点的性能指标计算整个集群的性能；然后根据Reduce任务个数对集群性能进行均分，得到每个Reduce任务的均分性能；接着建立最大堆的数据结构，保存每个可用计算节点的性能指标，对于每一个Reduce任务，依次取最大堆顶的计算节点进行任务分配，分配后减去Reduce均分性能，若性能大于0，则入堆，否则把计算节点从堆中删除，直到Reduce任务分配完毕位置。
4 结论
本文主要分析了当前Hadoop中Map Reduce负载均衡策略对于异构环境以及多任务环境的不足，并且尝试提出了一种基于平滑指数预测的Reduce任务调度框架，依据每个可用计算节点的计算能力来对任务进行调度，并给出了理论方法与算法
描述。
本文提出的框架可以对Map Reduce负载均衡进行优化，但也存在需要补充的一些地方，首先对于性能的定义与估算只考虑了cpu计算能力，没有对存储、网络等指标进行考虑，其次每个Reduce任务根据hash算法获得计算数据，计算数据是否均匀与数据逻辑有关，本文并没有解决这个问题。作者将会在将来的工作中着力解决上述两个问题。
注：本文受多摄像头的吸虫机绿色控害技术研究（国家星火项目2011GA750019）资助
参考文献
[1]K. Shvachko， H. Kuang， S. Radia， R. Chansler， “The Hadoop Distributed File System，” 26th IEEE Symposium on Mass Storage Systems and technologies， Yahoo！， Sunnyvale， pp. 1-10， May 2010.
[2]J. Dittrich， J.-A. Quian?e-Ruiz， A. Jindal， Y. Kargin， V. Setty and J.Schad， “Hadoop++： Making a yellow elephant run like a cheetah（without it even noticing），” Proceedings of VLDB Endowment，3（2），pp.515-529，September 2010.
[3]柳香，李瑞台，李俊红，段胜业.Hadoop性能优化研究[J].河北师范大学学报（自然科学版），2011（06）：567-570.
[4]刘娟，豆育升，何晨，唐红.基于调度器的Hadoop性能优化方法研究[J].计算机工程与设计，2013（01）：190-194.