云计算平台上任务调度算法的研究

摘要

随着应用种类的增多和数据规模的增大，传统资源组织和管理方式无法满足用户对计算和存储的需求，这促使云计算概念出现和快速发展。云计算将成百上千的计算机组成远端大规模集群，将计算能力、数据存储和应用等以服务方式提供给用户，使用户像水电一样使用计算机资源。一经提出，受到学术界和企业界的广泛关注。随着越来越多的应用迁移到云平台，提高云计算平台的性能具有十分重要的意义。
　　随着云计算的不断应用和发展，针对应用需求出现了不同类型的分布式计算框架，相应产生了多种云计算平台。主流云计算平台包括:(1)适合处理离线批量应用的基于MapReduce计算框架的云平台，(2)可快速处理迭代应用和递增应用的基于事件驱动的云平台和(3)支持同时运行多种计算框架应用的弹性计算云平台。
　　本文在深入调研云计算领域关键技术和研究现状的基础上，针对主流云计算平台，以提高云计算平台性能为目标，研究任务调度问题。
　　本文的主要内容和贡献点如下:
　　1.研究了基于MapReduce计算框架的云平台特性，提出了基于预取的调度算法，并进一步实现了一个任务调度器-HPSO。将预测机制、数据预取技术和任务调度三者结合，在任务调度策略的指引下采用数据预取技术，提高具有数据本地性任务的比例，进而优化云平台性能。实验结果显示:HPSO可获得不低于90％的数据本地性，可获得最高1.49倍的加速比。
　　2.分析了基于事件驱动的云平台的特性，提出两步调度算法，并设计了任务调度器-TSS。该算法将新触发器直接分配到监测数据所在节点上，以响应数据更新;随后针对集群负载不均衡的情况，运用主节点宏观调控下的分布式随机抽样均衡算法进行负载均衡。将TSS配置在基于事件驱动的云平台Domino上，通过实验验证了该算法的有效性。
　　3.分析了影响弹性计算云平台的性能因素，该平台采用增量资源机制防止任务饿死，为任务预留资源，导致资源利用率低，基于此提出了一种新的分类调度算法-CategoryS。该算法定义了小作业(small job)和大作业(largejob)两种标签，算法可分为两部分:第一部分，优先执行large job，尽量减少预留资源次数;第二部分，CategoryS将large job预留的资源借给smalljob，当large job所等待的资源到达时，收回借出的预留资源，这样即不影响largejob的运行，且提高集群利用率。将CategoryS配置在YARN上，实验结果表明，该算法可有效提高混合任务集的性能。

目录

声明

摘要

表格索引

插图索引

算法索引

主要符号对照表

第一章 绪论

1．1 云计算的概念

1．1．1 云计算服务分类

1．1．2 云计算研究现状

1．2 研究背景和意义

1．2．1 MapReduce平台的调度算法

1．2．2 基于事件驱动的云平台的调度算法

1．2．3 弹性计算云平台的调度算法

1．3 本文的研究内容

1．3．1 任务调度问题描述

1．3．2 研究内容

1．4 论文结构

第二章 MapReduce平台上基于预取的调度算法

2．1 引言

2．2 相关工作介绍

2．2．1 MapReduce计算框架

2．2．2 Hadoop实现

2．2．3 Hadoop资源管理

2．2．4 数据本地性问题

2．2．5 现有相关解决方案

2．3 基于预取的调度算法设计

2．3．1 任务调度问题描述

2．3．2 算法框架

2．3．3 预测模块

2．3．4 调度优化器模块

2．3．5 预取缓存机制

2．4 实验和分析

2．4．1 性能分析

2．4．2 实验设置

2．4．3 不同基准用例的性能比较

2．4．4 基准用例输入数据大小时的性能比较

2．4．5 HDFS基本数据块大小不同时性能比较

2．4．6 扩展性能分析

2．5 小结

第三章 基于事件驱动云平台的两步调度算法

3．1 引言

3．2 相关工作介绍

3．2．1 基于事件驱动的计算框架

3．2．2 基于事件驱动的云平台

3．2．3 基于事件驱动云平台与MapReduce平台比较

3．2．4 任务调度相关研究

3．3 两步调度算法设计

3．3．1 任务调度问题描述

3．3．2 算法总体框架

3．3．3 触发器分配

3．3．4 负载均衡算法

3．3．5 算法复杂度分析

3．4 TSS设计和实现

3．5 实验和分析

3．5．1 实验设置

3．5．2 PageRank应用性能比较

3．5．3 wordcount应用性能比较

3．5．4 扩展性分析

3．6 小结

第四章 弹性云平台任务调度算法

4．1 引言

4．2 相关工作介绍

4．2．1 弹性计算云平台

4．2．2 相关任务调度算法

4．3 算法设计

4．3．1 问题描述

4．3．2 算法框架

4．3．3 多维资源分配

4．3．4 基于预留资源的调度策略

4．3．5 适用性

4．4 实验和分析性能

4．4．1 性能分析

4．4．2 实验设置

4．4．3 CategoryS性能分析

4．4．4 扩展性分析

4．5 小结

第五章 总结与展望

5．1 主要工作总结

5．2 未来工作展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果