数据偏斜条件下面向性能与能耗的任务调度算法研究

摘要

随着互联网技术的不断蓬勃发展，信息化已经逐渐渗透到各行各业，与人类的生活密不可分。互联网用户数量的成倍增长，直接导致了海量数据爆发式的增长，使得分布式计算与云计算有了发展的平台。如何使用更为高效的计算框架来从海量数据中提取出对企业有用的信息，进而推动企业的发展，是企业长期研究的课题。作为云计算平台中炙手可热的成员，MapReduce计算框架受到了各大企业和研究机构的关注。MapReduce是由Google公司于2006年提出的分布式计算框架，经过近十年的演化，它已变得越来越完美。其简便的编程模型，使得用户只需要编写简单的map函数和reduce函数就可以实现各自的需求，而不用考虑底层的容错、冗余、节点通信等复杂问题。
　　但是，随着海量数据出现数据分布不均衡，MapReduce框架中自带的Hash分配策略已不能满足用户的需求了。因为Hash算法按键值对分配任务给Reduce的策略在数据偏斜时会导致Reducer负载分布不均，使得系统中出现很多“拖后腿”的任务。本文就该问题提出了一个高效的CSRA算法，该算法通过对任务队列更合理的调度，并对系统判定出的大任务进行分割，从而达到减少任务的执行时间以及在Reduce阶段的变异系数的目的。该算法将任务的实时状态考虑到计算模型中，有效的提高系统的资源利用率。在Hadoop平台上实现CSRA算法的实验结果表明，该算法能很大程度的减少常见应用的执行时间。
　　基于CSRA算法，本文还研究了并行分布式系统的能耗问题。异构分布式系统凭借着低成本、良好的可扩展性和容错性，使得很多企业纷纷将平台建立在分布式系统之上。随着互联网企业的不断壮大发展，数据中心像雨后春笋般不断增长，如何高效的管理数据中心的资源，合理的进行任务调度，已经成为绿色计算亟待解决的问题。本文基于DVFS技术提出了任务节能调度算法DEWTS，该算法首先通过CSRA算法提出的启发式任务时间估算方法估算出任务的执行时间，确定任务的优先级别，并对任务进行合理的调度，在调度完成后，根据处理器上的任务数和处理器的资源利用率对处理器进行合并，之后重新利用CSRA算法对任务进行调度。在调度完成后，利用DVFS技术合理的调节任务在执行过程中的电压/频率。实验结果表明DEWTS算法能保证任务的整体完成时间，降低系统的总能耗。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景及意义

1．2 研究现状

1．2．1 负载均衡研究现状

1．2．2 节能技术研究现状

1．3 本文主要工作

1．4 本文组织结构

第2章 Hadoop平台和节能技术概述

2．1 Hadoop平台概述

2．1．1 HDFS的工作原理及特点

2．1．2 MapReduce计算框架的工作原理及特点

2．2 负载均衡机制

2．3 分布式系统能耗优化技术

2．3．1 传统调度方案

2．3．2 基于DVFS的技术调度方案

2．4 本章小结

第3章 MapReduce的负载均衡策略

3．1 资源分配策略模型

3．1．1 资源利用率

3．1．2 启发式剩余时间估计

3．1．3 快慢节点判断

3．1．4 大任务预判

3．1．5 大任务的分割

3．2 负载均衡策略

3．2．1 任务优先级判定算法

3．2．2 大任务分割算法

3．3 实验结果与分析

3．3．1 不同数据偏斜度下的评估

3．3．2 Grep实例不同输出百分比下的评估

3．3．3 不同数据量下的Grep实例评估

3．4 本章小结

第4章 基于DVFS技术的节能调度策略

4．1 能耗模型

4．2 DVFS技术的优化调度算法

4．2．1 处理器合并过程

4．2．2 基于DVFS技术的任务拉伸任务

4．3 实验结果与分析

4．3．1 不同处理器数量下的评估

4．3．2 不同CCR值下的评估

4．3．3 数据不同并行度下的评估

4．4 本章小结

总结与展望

参考文献

致谢

附录A 攻读学位期间发表论文目录

附录B 攻读硕士学位期间所参与的科研项目