基于MapReduce的推测执行算法

作     者：黄中平 

作者单位：南京工业大学 

学位级别：硕士

导师姓名：白光伟

授予年度：2017年

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：MapReduce框架 推测执行 调度算法 分布式系统 

摘      要：随着云计算技术的发展和移动多媒体业务需求的飞速增长，分布式计算在处理多媒体数据中扮演着重要的角色。然而，分布式计算框架如MapReduce往往会因为个别节点任务的处理效率低下而影响整体作业的完成质量。\n 在分布式计算框架MapReduce的基础上，本文旨在通过调度算法来处理上述任务滞后问题。分析滞后任务产生的原因和特点，通过改进调度算法来实现计算性能的提高。并设计分布式实时多媒体系统来提高云计算平台的资源利用效率。\n 本文的具体研究工作包括:\n (1)提出基于MapReduce模型的推测执行优化算法。在分布式计算模型中一旦产生问题节点，则会导致多媒体业务如视频转码子任务完成时间的增长，从而影响整体的作业完成时间。本算法针对集群中实时性需求较高并且任务量较小的目标作业，提出基于MapReduce模型的推测执行优化算法，目的是在满足实时性需求的基础上尽量缩短目标作业的完成时间。设计可以在多项式复杂度内完成的启发式算法，在资源允许的范围内该算法可以逼近最优值。仿真结果表明该算法能提高资源的利用效率和作业的完成质量。\n (2)提出生存期感知的推测执行调度算法。在推测执行方法的基础上，结合每个作业的期望完成时间，提出一种优化算法，解决MapReduce框架的调度问题，可以有效降低目标作业的完成时间。本算法不但满足了作业的实时性要求，而且在作业遇到掉队任务时，减少了因使用异常监测的方法使得实时性要求较高的作业失败的情况。算法还通过有效的调度，使得每个节点的资源利用情况得到改善，增加了集群环境的计算能力和处理效率。仿真结果表明生存期感知的推测执行调度算法能够有效提高作业的完成数量。\n (3)在深入研究分布式模型后，设计一个分布式实时多媒体系统——视频转码系统。传统的计算存在很多的问题，如计算能力、存储能力和可扩展性都较差，将视频转码的计算任务迁移到云计算环境下可以有效的增加视频转码的处理能力。本文设计的分布式系统，针对现有技术视频转码效率低下，转码质量不尽完善的问题，利用OpenStack和Hadoop的搭建分布式平台，提高了云环境下基础设施资源和虚拟环境的利用情况。