6.6.4　2.0版本的算法

Apache MapReduce 2. 0（简称MRv2，也称为YARN，即Yet Another Resource Negotiator）属于下一代MapReduce计算框架，我们将在第12章进行详细介绍。MapReduce 2.0采用了不同于以上两种算法的推测执行机制，它重点关注新启动的备份任务是否有潜力比当前正在运行的任务完成得更早。如果通过一定的算法推测某一时刻启动备份任务，该备份任务肯定会比当前任务完成得晚，那么启动该备份任务只会浪费更多的资源。然而，从另一个角度看，如果推测备份任务比当前任务完成得早，则启动备份任务会加快数据处理，且备份任务完成得越早，启动备份任务的价值越大。

假设某一时刻，任务T的执行进度为progress，则可通过一定的算法推测出该任务的最终完成时刻estimatedEndTime。另一方面，如果此刻为该任务启动一个备份任务，则可推断出它可能的完成的时刻estimatedEndTime’，于是可得出以下几个公式：

estimatedEndTime=estimatedRunTime+taskStartTime

estimatedRunTime=（currentTimestamp-taskStartTime）/progress

estimatedEndTime'=currentTimestamp+averageRunTime

其中，currentTimestamp为当前时刻；taskStartTime为该任务启动时刻；averageRunTime为已经成功运行完成的任务的平均运行时间。这样，MRv2总是选择（estimatedEndTimeestimatedEndTime’）差值最大的任务，并为之启动备份任务。为了防止大量任务同时启动备份任务造成资源浪费，MRv2为每个作业设置了同时启动的备份任务数目上限。

推测执行机制实际上采用了经典的算法优化方法：以空间换时间，它同时启动多个相同任务处理相同的数据，并让这些任务竞争以缩短数据处理时间。显然，这种方法需要占用更多的计算资源。在集群资源紧缺的情况下，应合理使用该机制，争取在多用少量资源的情况下，减少大作业的计算时间。