Hadoop云平台调度算法研究

摘要

Hadoop集群虽然已经存在多年，但是依然是当前集群加速计算中的主要工具，并在各大互联网公司得到广泛应用。由于调度算法在集群中起到了关键作用，而Hadoop中的调度算法还是有有待改进的地方，故对Hadoop的研究依然很有意义。同时，云计算技术使得用户能够快速获得任意大小的集群，来执行一个给定的工作负载，然后用户为使用资源的时长付费，所以如何优化Hadoop云平台的租用费用也很有研究意义。此外，随着云平台规模的不断扩大，并且普通节点大量用于云平台的资源中，因而节点的容错研究也变得越来越关键，如何提高 Hadoop云平台的容错性是一个值得研究的课题。
　　为了利用有限的资源最大地减少作业的完成时间，本文在研究Hadoop推测执行机制的基础上，为此提出了一个基于平衡的推测执行算法（Balance-SE）。算法在进行推测执行时，先对每个作业进行筛选，让只有满足条件的作业进行推测执行机制，从而使得推测执行机制的进行能够真正使得作业的总完成时间得到减少，避免了许多不必要的备份任务的执行。同时，由于云平台具有按使用付费的特性，为了最小化用户租用云平台资源的开销，我们为每个不同的MapReduce应用选择一个最佳的 Hadoop配置平台，这里的配置信息包括虚拟机(Virtual Machine，VM)的类型、个数，以及作业的调度。即给定一系列MapReduce作业和一个作业截止完成时间，为这些作业决策一个同构或者异构的最优Hadoop集群配置，使得用户的租用费用最小。由于Hadoop云平台容错的重要性，以及不同类型的VM具有不同的计算能力，从而使得不同类型的VM发生故障将引起不同的开销，显然，发生故障的VM计算能力越大，导致的开销也越大。因此，本文在此基础上设计了一个基于自适应和检查点的容错算法。首先每个VM根据其完成作业的情况，自适应地更新自身的可靠性，如果 VM正确地完成一个作业，则相应的可靠性增加，若运行一个作业失败，则VM可靠性降低。接着，对于可靠性低于一定阈值的VM进行检查点设置，而针对不同类型的VM，本文分别进行考虑，为不同类型的虚拟机节点设置不同的检查点，从而平衡地提高系统的总体容错性。
　　为了检测本文设计的算法的有效性，本文对以上两个算法分别进行了实验，最终的实验表明，相较于Hadoop原有的推测执行算法和LATE算法，本文提出的Balance-SE算法很好地减少了作业的完成时间。另一方面，本文在决策最优平台算法的基础上设计的基于自适应和检查点的容错算法使得在有故障的情况下，节点容错性得到提高，表现为作业的完成时间减少了。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1 研究背景与意义

1.2 国内外研究现状

1.3 论文主要工作以及论文组织结构

第二章 相关理论与技术

2.1 MapReduce模型

2.2 Hadoop相关技术

2.3 云计算

2.4 本章小结

第三章 基于平衡的推测执行算法

3.1 LATE调度算法

3.2 LATE算法的关键步骤

3.3 基于LATE算法的相关研究

3.4 基于平衡的推测执行算法

3.5 本章小结

第四章 Hadoop云平台的最优决策方案和容错

4.1 Hadoop云平台的最优决策方案

4.2 自适应的Hadoop容错算法

4.3 本章小结

第五章 实验结果与分析

5.1 实验平台的选择及其配置

5.2 实验结果分析

5.3 本章小结

第六章 总结与展望

参考文献

致谢

作者简介