一种MapReduce中备份任务推测执行策略的优化方案

摘要

一种MapReduce中备份任务推测执行策略的优化方案，采用指数平滑算法，结合集群中节点实时性能，对任务运行各阶段的时间分别计算，达到对任务运行的剩余时间进行准确预测的目的。解决了默认情况下，推测执行准确率低，由于错误地启动备份任务的问题。本方案极大程度的提高推测执行的正确率，节省了任务运行的时间，有效地节约了集群中有限的资源。

主权项

一种MapReduce中备份任务推测执行策略的优化方案，其特征在于，包括4个步骤：预测当前各任务完成时间、预测新任务完成时间、选择需备份的任务和选择在哪个节点上备份执行；具体步骤如下：(1)预测当前各任务完成时间具体来说需根据以下公式：$\begin{array}{c}{T}_{rem}=T_{cp}+T_{fp}\\ =T_{cp}+\underset{p\inf p}{\Sigma }{T}_{{\mathrm{avg}}_p}*{\mathrm{factor}}_d\end{array}$${\mathrm{factor}}_d=\frac{{\mathrm{data}}_{input}}{{\mathrm{data}}_{avg}}$其中，T_rem代表当前任务总的剩余时间，它由当前阶段剩余时间和剩余阶段总的剩余时间组成；进一步的化简公式中，p代表剩余阶段中的某一个，fp代表剩余所有的阶段，代表某阶段p的平均完成时间；factor_d是个参数，可以表示为当前数据处理量和平均每个任务数据处理量的比值，data_input代表当前处理数据量，data_avg代表平均每个节点的处理数据量；其次，我们根据平滑处理后的公式来计算当前阶段的剩余时间；(2)预测新任务完成时间：新任务的完成时间依据以下公式T_bf＝TimeStamp+T_avg其中，T_bf代表备份任务完成的时刻，TimeStamp代表当前时刻，T_avg代表已经完成的任务在该阶段所用的时间；(3)选则需备份的任务遍历所有任务，选择如果开启备份执行，最后可能是有效任务的任务，也就是说，剩余执行时间和假如开启备份任务完成时间差最大的任务；(4)选择在哪个节点上备份执行根据节点的位置进行分类：分为Data‑Local、Rack‑Local以及Other‑Local,优先选择Data‑Local,其次再根据剩余资源选择当前最优节点,会更有可能成为有效的推测执行。