MapReduce是应用于大规模数据处理的并行计算框架。从2004年Google提出该框架开始,MapReduce逐渐被越来越多的互联网公司和研究机构应用于日志分析、数据挖掘等领域。MapReduce提供了作业(Job)的自动切分与并行化,具有负载均衡、容错处理、故障恢复等功能,框架可扩展性强,用户容易使用。然而在MapReduce框架中存在着两类滞后任务(laggard task)----掉队任务(straggling task)和倾斜任务(skew task),它们对MapReduce框架的性能造成了严重影响。在异构的环境下,性能差的计算节点处理任务缓慢形成掉队任务,拖延了整个并行作业的完成。而在同构环境下,当输入数据存在数据倾斜(数据非均匀分布)时,简单地使用Hash算法划分中间数据会导致Reduce任务输入数据差异过大,形成倾斜任务,限制作业的并行化。目前,推测执行(speculative execution)是一种行之有效的处理掉队任务的方法。推测执行是指在作业执行时实时监测任务的执行速率,将可能延迟作业完成的掉队任务进行备份,增加掉队任务提早完成的机会。处理倾斜任务的一般做法是在作业开始前进行采样(Sampling),通过采样了解输入数据和中间数据的分布情况。在作业执行时,中间数据就可以借助采样结果得到尽量均匀地划分,使得Reduce任务处理数据量尽量均等。　　本文深入调研了目前处理掉队任务和倾斜任务的策略,在介绍这些策略的同时讨论了它们存在的诸多问题。针对现有推测执行策略中存在的问题,提出了一种新的处理掉队任务的推测执行策略MCP(Maximize Cost Performance)。MCP策略通过分阶段的方式,利用EWMA预测算法预测每个阶段的执行速度,并藉此计算任务的剩余时间,从而实现准确地选择掉队任务。MCP还利用了代价收益模型以最大化推测执行的性能代价比。此外,MCP还维护了集群计算节点在执行作业时的相关信息,以选择性能良好的计算节点备份掉队任务。针对目前MapReduce任务中采样操作低效的问题,提出了一种新的采样策略SMART(Sampling Maptask At RunTime)。SMART、策略利用了边执行、边采样的思想,通过将Map任务特化为采样任务和统计任务的方法准确统计作业中间数据的分布信息。在此基础上,SMART策略将采样信息以数据接口的方式传递给用户,用户只需要实现划分方法就可以利用这些结果,进而以适当的方法实现划分函数以避免出现倾斜任务。目前,MCP策略和SMART策略分别在Hadoop-0.21的版本中进行了实现,我们在网络实验室的刀片集群中测试了两种策略的有效性。实验证明,在异构环境下MCP推测执行策略性能明显优于Hadoop现有策略(Hadoop-LATE)。MCP相比于Hadoop-LATE减少了17％的作业完成时间,并提高了22％的作业吞吐率。实验还证明MCP不仅适用于同构环境也适用于异构环境,且具有良好的可扩展性。在同构环境下,SMART策略实现了准确采样和均匀的任务划分。由于采用了边执行、边采样的方法,在以Sort作业为工作负载的实验中我们看到,利用基于Key值划分的SMART策略能将作业执行速度提高近2倍。