论文部分内容阅读
随着科学技术的发展,计算机以及互联网通过多种多样的方式在影响着人们的生活和工作。随着这种影响的深入,在日常生活和工作中积累下的数据也呈现出几何数量级的增长。这些数据是一笔宝贵的财富,对数据的分析可以更好的帮助人们了解用户行为和制定商业决策。大量的数据分析任务对计算资源的数量和分配也提出了挑战。云计算可以整合并管理大量的计算资源,成为了任务处理的基础设施。新的计算模型可以利用云计算提供的资源,高效的对海量数据进行处理。例如,Google提出的MapReduce模型在大数据的批处理计算方面优势明显,屏蔽了并行计算的底层细节,让开发者可以更加专注于算法的业务逻辑。在大数据条件下进行作业调度,具有待处理的数据量大,计算资源地理位置分布,计算模型新,对经济指标要求高等特点。本文针对以上特点,围绕作业调度的问题进行了研究。论文的主要工作有:(1)针对MapReduce模型中reduce阶段负载不均衡的问题进行研究。原有MapReduce模型中对数据分区和reduce任务进行了绑定,当数据分区大小不平均或者结点计算能力不同时,会造成负载不均衡的问题。本文建模分析了数据量、算法和计算能力等各个因素对reduce任务完成时间造成的影响,提出了一个负载均衡的MapReduce框架,增加了分区的数量,用采样的方法预测每个分区的大小,结合实际运行时各个结点的计算能力,动态的对分区进行分配,确保各个结点负载均衡,缩短了整个作业的运行时间。(2)针对MapReduce作业调度中缺少对于成本的关注的问题进行研究。使用云平台进行大数据处理的一个关键原因就是对于成本的重视,提供MapReduce作为商业服务已经是一种趋势,目前的MapReduce调度算法还主要关注于作业的运行时间。本文提出了将运行时间和成本作为用户服务质量的两个属性。建立了以运行时间和成本为优化目标的MapReduce作业调度模型,分别使用博弈论和遗传算法对模型进行了求解。本文在Hadoop系统中实现了调度器,当多个用户同时使用Hadoop服务时,调度器会根据用户对时间或者成本的偏好来分配相应的资源数量,使所有用户的满意度达到最大。(3)针对MapReduce中对不同优先级用户分配资源数量的问题进行研究。在同一个集群中,需要保证不同优先级别的用户对于作业截止时间的不同要求。本文提出了一个基于排队网络的多优先级作业调度算法(MPSA)。本文将MapReduce中的map阶段的资源和reduce阶段的资源抽象为两个服务站,总结了MapReduce算法使用两个服务站的三种模式。采用Jackson排队网络对基于MapReduce模型的算法建立了数学模型,应用该网络模型可以求出不同优先级队列对资源的需求。算法在用户到达率和任务规模变化的情况下,可以有效的满足不同优先级用户的截止时间限定。(4)针对在地域分布的数据中心中进行数据密集型工作流调度的问题进行研究。在大数据条件下,进行数据迁移的工作量并不低于进行数据分析的工作量,而且使用带宽也需要支付相应的费用。本文在建立工作流模型的过程中,将数据迁移也映射为工作流的子任务,用有向无环图对工作流进行建模并化简。利用模拟退火算法,将工作流执行时间和花费作为优化目标,计算出一个优化的调度方案。上述研究都是围绕着大数据作业调度的优化而展开的,所获得的研究成果提高了MapReduce模型的性能和用户服务质量,对大数据作业在云计算中的使用做出了有益的贡献。