Hadoop多作业环境下自学反馈的任务调度方法

摘要

本发明涉及高性能集群领域的任务调度方法，Hadoop的每个工作节点通过作业提交阶段的解析后，获取到符合任务的实际阶段权值，通过几何平均值方法的处理后，为该作业的其余任务建立阶段权值的参考标准；在任务反馈阶段，该作业的其余任务采用所述参考标准，结合子阶段的进度对任务剩余执行时间进行估计；在作业反馈阶段，将所有任务的阶段权值用分段的方式求取几何平均值，并建立作业名-阶段权值映射记录，作为该节点上后续作业执行的参考。本发明能够在多作业并行执行的环境下分别对各个作业的任务进行自主学和信息反馈，获得更精确的阶段权值估计，提高任务剩余执行时间预估的准确性，进而提高落后任务选择的命中率，促进集群资源的优化利用。

主权项

一种Hadoop多作业环境下自学习反馈的任务调度方法，其特征在于包括以下阶段步骤：步骤1、在作业进行解析阶段，为每个节点上的每个作业设置任务阶段权值的初始值，如果有相同类型的作业在该节点上执行过则以已完成作业反馈的阶段权值信息设置初始值；否则，以该节点上完成的各种作业中出现频率最高的阶段权值信息为其设置初始值；步骤2、在自学习阶段，利用该节点上该作业已经完成的前若干个Map任务和Reduce任务的实际执行时间，分别计算出其相应子阶段执行时间的比例，转化成阶段权值；利用求几何平均值的方法分别修正该作业前若干个Map任务和Reduce任务的阶段权值；步骤3、在任务反馈阶段，将修正过的阶段权值作为该作业标准的阶段权值设置，该节点上该作业剩余的任务启动时均采用该标准设置；结合任务子阶段的进度，估算每个任务执行的出剩余的执行时间，作为落后任务筛选的判别条件；步骤4、在作业所有的任务完成后进入作业反馈阶段，该阶段分别对该节点上该作业的所有Map任务和Reduce任务分别进行分阶段的求取几何平均值，并在节点上更新作业名‑阶段权值映射记录，作为后续该节点上作业执行的参考；所述步骤2中的阶段权值计算公式如下所示：$\begin{array}{cc}\left\{\begin{array}{c}M1=MDT1/(MSE-MMS)\\ M2=1.0-M1\end{array}\right.& \left\{\begin{array}{c}MDT1=MME-MMS\\ MDT2=MSE-MSS\end{array}\right.\end{array}$$\begin{array}{cc}\left\{\begin{array}{c}R1=RDT1/(RRE-RSHS)\\ R2=RDT2/(RRE-RSHS)\\ R3=1.0-R1-R2\end{array}\right.& \left\{\begin{array}{c}RDT1=RSHE-RSHS\\ RDT2=RSE-RSS\\ RDT3=RRE-RRS\end{array}\right.\end{array}$其中，M1,M2,R1,R2,R3分别代表Map任务的Map，Sort阶段和Reduce任务的Shuffle，Sort，Reduce阶段的执行时间比例，即阶段权值；MDT1,MDT2,RDT1,RDT2,RDT3分别代表各个阶段的执行时间；Map任务的Map阶段的开始时间和结束时间表示成MMS和MME，MSS和MSE表示Map任务的Sort阶段的开始时间和结束时间；RSHS,RSS和RRS表示Reduce任务的Shuffle，Sort和Reduce阶段的开始时间，RSHE,RSE和RRE是阶段的结束时间；所述几何平均值计算公式如下所示：$geomean=\sqrt[k]{x_1*x_2*...*x_k}$其中x分别代表M1,M2,R1,R2,R3，k为用于自学习阶段的任务数；所述步骤3中剩余的执行时间的估算采取Hadoop默认的计算方式，参与估算的相关公式如下所示：$\mathrm{Pr}ogress=\underset{i=1}{\overset{n}{\Sigma }}{\mathrm{PhaseWeight}}_i*{\mathrm{SubProgress}}_i$ProgressRate＝Progress/T其中，PhaseWeight_i表示阶段i的权值，SubProgress_i表示阶段i的子进度，n代表任务的阶段数，对于Map任务，n取2，对于Reduce任务，n取3；ProgressRate表示任务的处理速率，则从以上公式就能够得出对剩余执行时间TimeToEnd的估算：TimeToEnd＝(1.0‑Progress)/ProgressRate。