一种基于MapReduce的最优本地化任务调度方法

摘要

本发明提出一种可以同时工作在同构和异构集群环境下MapReduce任务调度算法，属于计算机技术领域。该调度算法能综合考虑集群中各计算节点的处理性能，把计算节点和计算任务抽象为一个二分图，通过适当扩展该二分图并结合KM带权最优匹配算法形成最终的全局任务调度方案。实验数据表明，该调度算法能将Map阶段数据本地化程度提升到接近100％，MapReduce作业整体执行时间最优能减少67.1％。

主权项

一种基于MapReduce的最优本地化任务调度方法，包括以下步骤：步骤一.模型抽象：将集群中的物理计算节点抽象为一类点的集合，将集群中准备处理的数据块抽象为另一类点的集合并构建二分图；将抽象后的每个数据块对应的点和每个物理计算节点对应的点连接，若某个物理计算节点上存储有某数据块，则该数据块与该计算节点间的连接线为一条实线，即这种实线连接的数据块所对应的任务为本地化任务，反之，非本地化的数据块与计算节点之间则用虚线连接；对所述连接线赋权值：定义三个权值α、β、γ，满足α<β<γ，本地化任务对应的是用实线连接的数据块和物理节点形成处理关系的一类任务，在图中这类任务对应的连线的权值为α；非本地化任务对应的是用虚线连接的数据块和物理节点形成处理关系的一类任务，在所述二分图中这类任务对应的连线的权值为β或γ，其中所连接的数据块的物理位置与计算节点的物理位置若属于计算集群中的相同机架，则虚线权值为β，若所连接的数据块的物理位置与计算节点的物理位置分别属于计算集群中的不同机架，则虚线权值为γ；由此得抽象后的二分图模型；步骤二.计算节点初始化：将集群中各个物理计算节点的计算性能初始化为相同值，即假定每个物理计算节点在单位时间内均能处理相同数量的数据块；步骤三.第一次模型扩展：对步骤一所得的二分图模型进行扩展，通过虚拟增加数据块或者镜像计算节点，使扩展后的模型中计算节点数与数据块数相等，从而使扩展后的模型能使用KM带权最优匹配算法；步骤四.生成第一次调度方案：利用KM带权最优匹配算法对步骤三所得的经第一次扩展的模型进行匹配，得到一个全局权值最小的任务调度结果；若步骤三的模型扩展过程中通过虚拟增加了数据块，则将虚拟的数据块从调度结果的队列中剔除，若通过虚拟增加了镜像计算节点，则将调度结果中分配给每个镜像节点的任务分配至其相应的原始物理计算节点上，最终得第一次任务调度方案；步骤五.物理计算节点实际性能评估：执行第一次任务调度方案，待所有计算节点启动第一个任务后，通过各计算节点Map阶段处理的数据量和花费的时间计算各计算节点的实际计算性能。步骤六.物理计算节点性能判定：若步骤五所得的每个物理计算节点的实际计算性能均相同，则继续执行第一次任务调度方案直至任务调度完成；若不完全相同，则执行步骤七，且各个计算节点继续执行当前正在处理的任务；步骤七.第二次模型扩展：对步骤一所得的二分图模型进行扩展，使得扩展后的模型中计算节点数与整个集群中经第一次任务调度方案处理后剩余待处理的数据块数相等，从而使扩展后的模型能使用KM带权最优匹配算法；步骤八.生成第二次调度方案：利用KM带权最优匹配算法对步骤七所得的经第二次扩展的模型进行匹配，得到一个全局权值最小的任务调度结果；若步骤七通过虚拟增加了镜像计算节点，则将调度结果中分配给每个镜像节点的任务映射到其相应的原始物理计算节点上，最终得第二次任务调度方案；步骤九.调度完成：执行第二次调度任务方案对剩余的待处理数据块进行任务分配，完成任务调度。