一种基于MapReduce的任务调度算法

摘要

本发明涉及当前大数据领域中的一个非常重要的编程计算框架MapReduce中的任务调度算法，公开了一种基于MapReduce的任务调度算法，在异构集群环境下，基于蚁群算法的多任务调度算法，通过衡量计算节点的处理性能，根据新的任务目标转移函数和新的节点的更新规则，按照本地计算原则将任务分配给各个计算节点。本发明基于经典的蚁群算法进行大规模的优化，提出了一种在异构集群环境下的多任务调度算法并在开源Hadoop平台做了小作业、负载和本地性等场景的测试和性能分析，结果表明在执行效率及任务均衡性方面得到了很大的提升。

说明书

技术领域

本发明涉及当前大数据领域中的一个非常重要的编程计算框架MapReduce中的任务调度算法，特别是涉及一种基于HDFS的动态副本管理方法。 

技术背景

MapReduce作为一种处理大规模数据集的技术，最早由 Google 在 2007 年提出来,受到了学术界和产业界的广泛关注。目前，MapReduce 这种并行编程模型成为了各大 IT 厂商融合在云产品中的关键技术之一，并不断有开源产品投放到这个行业中，例如开源云系统Hadoop、Sector&Sphere 等。近年来,MapReduce 已经成为了云计算领域的主流技术,也成为了科研机构,开源组织以及互联网公司的研究热点,并被列入在 InfoWorld 推出的 2011 年十大新兴企业级技术之中。相信随着云计算观念逐渐普及，MapReduce 会获得更多的关注和更快的发展。MapReduce 的架构思想使得通过普通的 PC 集群就可以完成对千兆级别的海量数据的处理。在实际的应用中，通过 MapReduce 对海量数据进行分析处理并从数据挖掘等方面进行研究，可以获得较高效率，同时还兼顾了成本效益。当前，由于 MapReduce 具有开源和高性能突出优势，已被广泛应用到机器学习，数据挖掘、智能识别等领域。基于 MapReduce 的应用在互联网领域也已经越来越广泛。其中推动MapReduce 商业化的最主要的贡献者是 Yahoo!，Yahoo!构建了超过 4000+个节点的 MapReduce集群，提供了约为 1.5PB 的存储应用。而全球拥有 10 亿用户的著名社交网站 Facebook 为了处理其每日以TB 级增长的数据量，广泛使用了超过100个 MapReduce 集群来作为其哥斯拉级别的大数据的分析工具，主要用来处理 Web 事物流和数据挖掘。此外，EMR 产品是 Amazon架构在其 EC2 和 S3 上的分布式计算平台，以按流量收费的形式向用户提供计算服务。目前，市场上还有包括 Facebook Insights、IBM Platform MapReduce 等在内的多种 MapReduce 应用产品。在国内,众多互联网企业如百度、淘宝和腾讯也都是 MapReduce 应用的忠实粉丝。作为国内最大的搜索引擎百度搭建了超过 10 个集群来处理每日生成的 3PB 数据量，主要是应用于系统日志分析以及网页数据库的挖掘工作。在此值得一提的是电商巨头淘宝，淘宝的MapReduce 集群拥有 2800 多个节点,其总存储容量 50PB，日均作业数高达 15 万，主要用于包括用户消费行为、搜索习惯等多方面的检索分析，也为淘宝在 2012 年双十一的战场上交易额可以高达 191 亿元提供了关键技术支撑,做出了巨大贡献。在海量数据时代，互联网企业将 MapReduce 这种分布式计算模式应用到网络数据库挖掘，日志分析等方面，可以大大提升资源利用率同时为用户提供了更好的用户体验。 

发明内容

本发明要解决的技术问题是：本发明提出一种基于MapReduce的任务调度算法，该算法是在分析蚁群算法和现有的MapReduce任务调度算法的基础上演化而来。可以克服现有调度算法存在的许多问题，有效的解决了本地性计算和小作业处理问题，同时兼顾了节点上的数据倾斜，从而均衡了节点上的任务分配，提高了集群平台的调度性能。 

在大数据处理工程中，任务调度主要存在以下问题： 

1) 本地性计算问题。本地计算指的是在任务计算过程中,应优先选择距离任务所需数据最近的计算节点。那么 Hadoop 中具体的实现方法是首先将存储用户提交数据的节点作为本地执行节点，如果该节点正在执行其他任务且没有空闲资源，则从该节点所在的同一 Rack 上选择其他节点。如果该 Rack 上的所有节点都不能满足当前任务执行的要求，那么 JobTracker就将任务重新分配给其他 Rack 上的节点。从上面的实现过程分析来看，本地性计算问题主要会涉及到任务的再次分配消耗 I/O带宽资源。而在大规模集群中，I/O 带宽是稀缺性资源，因此说，解决好本地性问题有利于减少网络带宽资源耗费，进而提高集群的吞吐率，对于提升集群性能具有重要意义。

2) 数据不均衡问题。在集群中，数据往往有大作业和小作业之分，而对于 Facebook 和 Google这种每天产生 TB 级数据量的企业来说，这种大小混合作业更是其数据的明显特征。然而对于 MapReduce 来说，由于大作业文件可以比较完整的划分为数据块并且让数据块与任务得到很好的映射。因此说,MapReduce 更加擅长处理大作业,而在处理小作业方面，如果这些作业都远远小于系统的设定值，这些作业就不会被分割，可是系统还是要为这些小作业分配一个一个独立的任务。这样做的后果将导致过多的资源被占用，同时会造成节点上任务的执行进度不一致，进而使输出结果传输延迟而造成集群性能下降。 

节点上的任务负载问题。如果将原来的调度算法应用在异构环境中就会造成某些节点上的任务分配过多，进而造成节点上的负载过重从而影响到集群性能。异构环境中的节点在 Cpu数量、内存等方面的处理能力各不相同,因此在异构环境下的调度算法需要考虑衡量节点计算能力的表示方法。 

本发明所采用的技术方案为： 

一种基于MapReduce的任务调度算法，在异构集群环境下，基于蚁群算法的多任务调度算法，通过衡量计算节点的处理性能，根据新的任务目标转移函数和新的节点的更新规则，按照本地计算原则将任务分配给各个计算节点。

所述衡量计算节点的处理性能，在异构环境下的任务调度中，主要衡量节点的初始处理能力，和任务分配到节点上的目标转移概率，其中，节点的初始处理能力根据处理速度﹑内存容量﹑CPU数目和网络传输带宽这四个度量来综合衡量，并分别为这四个度量参数设置阈值，若超过阈值，则统一以阈值计算；在任务调度时，设置一个调度器来专门负责计算任务分配到请求节点的上的初始转移概率。 

因此，本发明算法引入了以下相关定义： 

定义一 设 N={1，2，……，n}，M={1,2,……，m}，作业集 J={J_i|i∈N}，其中 J_i代表一个作业。每个作业划分为对应的一组 Map 任务集 T=J_i={t_k|k∈N}，其中 t_k代表一个任务。

定义二 设 V={v₁,v₂,……，v_n}表示集群中的节点集，而每个计算节点v_i使用处理速度﹑内存容量﹑CPU数目和网络传输带宽这四个度量来综合衡量异构环境下各个计算节点的初始处理能力。而且分别为这四个度量参数设置阈值，若超过阈值，则统一以阈值计算。 

所述节点的初始处理能力取决于节点的初始信息素，由公式1.1计算确定。 

构建计算节点的初始信息素： 

其中，m：cpu数目，p：处理速度，r：内存容量，b：带宽。M₀、P₀、R₀、B₀分别对应的阀值。影响因子α、β、γ为衡量节点处理能力的重要程度。

定义三 在任务调度时，调度器会计算任务分配到请求节点(请求节点即请求分配任务的TaskTracker计算节点)上的初始转移概率，即在t时刻,任务tk分配到请求节点 vi上的转移概率f(t,tk,vi)由公式(1.2)确定。 

 

式中，τ(t,v_i)表示在时刻t，任务t_k在工作节点v_i上的信息素浓度。η(t,vi)为计算节点vi的原始能力即η(t,vi)= τ(0,vi)= τVi (0)。α和β分别是衡量τ和η相对重要性的表示参数。

所述新的任务目标转移函数是将Task作为系统均衡和调度的核心对象，选取作业总体执行时间，节点负载度作为评判标准，并且新增了一个带有FIFO性质的任务池来记录正处理的作业和对应分解的 Map 任务集，选择处理能力强和任务队列较短的请求节点进行任务分配作为目标转移函数建模指标，由 Hadoop 调度器来维护，在获得作业之后调度器会将该作业和分解的任务一起添加到 任务池中，进行调度。 

在 MapReduce 集群计算平台中,真正的核心调度单位是 Task。用户提交的 Job 最终都会被分解为众多的 Task，而各个 Task 之间并行且平等独立的运行。本算法的调度设计是将Task作为系统均衡和调度的核心对象，而且在算法设计中考虑了用户QoS(Quality of Service，中文名为"服务质量"，是指网络提供更高优先服务的一种能力)的评判指标，同时也考虑了节点上的任务负载,既不使节点被拖死也不使节点被饿死。针对集群用户的 QoS 描述通常可以采用整体完成时间、网络带宽等参数指标来量，本发明选取作业总体执行时间，节点负载度等多个指标作为评判标准。 

从蚁群算法的时间复杂度O(NC n²m)可以看出，蚁群算法的搜索时间比较长，而且在大规模环境下蚁群算法的效率并不是很高。因此，本专利算法在设计中对蚁群算法做了相应的改进和优化，同时算法中还新增了一个带有 FIFO (First Input First Output的缩写，先入先出队列)性质的 TaskPool(任务池)，用来记录正处理的作业和对应分解的 Map 任务集，它由 Hadoop 调度器来维护，在获得作业之后调度器会将该作业和分解的任务一起添加到 TaskPool 中，而后根据改进的算法进行调度。 

在本算法中，设任务t_k在计算节点v_i上的预计执行时间耗费为T_exec(t_k,v_i)；任务t_k分配到v_i的网络传输时间为T_trans(t_k,v_i)。Time(t_k,v_i)表示任务在上的完成时间，等于执行时间与网络传输时间之和即公式1.3。 

 

设Task_listlength(v_i)表示计算节点v_i中待执行的任务队列长度，其大小为队列中所有任务完成的时间之和。结合定义三中的初始转移概率可构成最终的目标转移函数见公式(1.4)，即选择处理能力强和任务队列较短的请求节点进行任务分配。

式中，λ₁,λ₂为求解公式中的权重比值。在异构网络环境下，考虑到调度器需要评估计算节点的初始处理能力和负载状况。因此，本算法设定信息素分布在计算节点上而不是在路径上，并且将主要的运算和传输量作为信息素的求解对象。随着任务的执行，计算节点上的信息素也会发生相应的变化并根据任务的执行情况来更新信息素。在t₁时刻将任务t_k分配给请求节点v_i时，节点上的信息素按照公式（1.5）进行更新： 

 

在任务执行了一段时间后,无论执行是否成功,系统的负载都会得到一定程度的减轻。因此为了平衡节点上的信息素负载,信息素浓度按公式(1.6)进行增涨

 

在本发明算法中，重点强调的是节点处理能力而不再是路径距离，因此该算法设计了一个节点处理能力强弱的标记，也相当于是为节点引入的奖惩因子，本算法设置ε=+/-0.2。若在当前计算节点上成功运行完任务则将标记ε设置为正数进行奖励即ε在0 到 1之间；否则设置ε在-1到0之间的负数给予信息素消弱。因此在式(1.6)的基础之上进行修改如公式(1.7)所示。

如果按照这样进行搜索的话，进行到一定程度后同样会出现陷入局部转移的问题。这是由于在调度过程中按照(1.7)中ε的设计，那么某些得到奖励的节点的信息素和那些信息素消弱的节点之间的差异会变得越来越大，而按照转移规则始终会选择信息素浓度较高的节点进行转移，这就导致当前没有被选中的节点在以后被选中的概率也会变得越来越小，从而进入了在某些局部节点之中选择转移。 

因此，本算法基于蚁群系统改进思想进行了优化，设计了基于多样性选择的转移目标函数，见公式(1.8)。 

式中，0≤q₀≤1是初始设定的参数，q是一个随机数，q∈[0,1]。 

为了加快节点搜索和优化节点上的信息素强度，本算法设计了新的节点更新规则，所述新的节点的更新规则是当系统处理完了作业 J_k的所有 Map 任务后则按照全局更新准则做一次全局更新；如果计算节点在n个时刻未得到任何任务的分配，那么该节点上的信息素需要进行局部更新。 

其中 

准则一(全局更新准则)：更新处理过作业J_k任务的所有节点的信息素，同时也对未处理过的节点的信息素予以削弱。对于工作节点v_i和作业J_k更新规则如1.9式：

其中，c_e﹑ρ₂为调节因子常量,本文设置 c_e=1，ρ₂=0.1。Time(J_k)表示作业J_k的完成时间。

在整个调度过程中，如果计算节点在一段时间内(n个时刻)未得到任何任务的分配，那么该节点上的信息素需要进行局部更新，其中， 

准则二(局部更新准则)：在n个时刻内计算节点未得到任何任务的分配，那么该节点上的信息素将按照局部更新准则(2.0)进行更新。

其中1-ρ₃表示消弱系数，本算法设置ρ₃=0.8。 

一种基于MapReduce的任务调度算法，其流程如下： 

1）首先将根据公式1.1初始化各个 TaskTracker 节点信息素；

2）检测到集群中有 TaskTracker 向 JobTracker 发出请求任务分配的消息,调度器将所有请求节点的 ID号加入到禁忌表tabu表中；

3）取出一个作业,并将其与对应分解的 Map任务一起添加到任务池中；

4）系统从任务池中取出任务,并根据公式1.2计算出 tabu 表里面每一个请求节点的初始转移概率；

5）根据任务情况计算出公式(1.4)的转移目标函数,并按照公式 1.8 选择进行转移,并且将被调度的请求节点 ID 号从禁忌表 tabu 表中删除；

6）当任务正常分配给 TaskTracker 后,利用公式1.7进行相应的信息素更新；

7）如果任务执行失败,则重新插入到属于本作业在任务池中的位置,等待下一次重新调度；

8）从任务池中取出下一个任务进行资源节点调度；

9）若当前一个作业处理完毕,根据公式1.9进行全局更新更新处理过该作业 Map 任务的节点信息素；

10）根据公式2.0进行局部更新挥发信息素；

11）从队列中取出下一个作业添加到任务池中等待调度,并重复迭代步骤。

只要将本算法打成jar包，然后修改配置文件mapred-site.xml文件里的参数即可，如附图2所示，即修改配置文件里的value值为本算法所在的路径即可。 

本发明的有益效果为： 

本发明基于经典的蚁群算法进行大规模的优化，提出了一种在异构集群环境下的多任务调度算法并在开源Hadoop平台做了小作业、负载和本地性等场景的测试和性能分析，结果表明在执行效率及任务均衡性方面得到了很大的提升。

附图说明

图1为本发明算法执行流程图； 

图2为本发明配置文件图。

具体实施方式

下面参照附图，结合实施例对本发明详细说明。 

实施例1： 

一种基于MapReduce的任务调度算法，在异构集群环境下，基于蚁群算法的多任务调度算法，通过衡量计算节点的处理性能，根据新的任务目标转移函数和新的节点的更新规则，按照本地计算原则将任务分配给各个计算节点。

实施例2： 

在实施例1的基础上，本实施例所述衡量计算节点的处理性能，主要衡量节点的初始处理能力，和任务分配到节点上的目标转移概率，其中，节点的初始处理能力根据处理速度﹑内存容量﹑CPU数目和网络传输带宽这四个度量来综合衡量，并分别为这四个度量参数设置阈值，若超过阈值，则统一以阈值计算；在任务调度时，设置一个调度器来专门负责计算任务分配到请求节点的上的初始转移概率。

实施例3： 

在实施例2的基础上，所述节点的初始处理能力取决于节点的初始信息素，由公式1.1计算确定。

实施例4： 

在实施例2的基础上，本实施例所述任务分配到请求节点的上的初始转移概率由公式1.2确定。

实施例5： 

在实施例1的基础上，本实施例所述新的任务目标转移函数是将Task作为系统均衡和调度的核心对象，选取作业总体执行时间，节点负载度作为评判标准，并且新增了一个带有FIFO性质的任务池来记录正处理的作业和对应分解的 Map 任务集，选择处理能力强和任务队列较短的请求节点进行任务分配作为目标转移函数建模指标，由 Hadoop 调度器来维护，在获得作业之后调度器会将该作业和分解的任务一起添加到任务池中，进行调度。

实施例6： 

在实施例5的基础上，本实施例所述目标转移函数由公式1.4确定。

实施例7： 

在实施例5或6的基础上，本实施例还包括一种基于多样性选择的目标转移函数，由公式1.8确定。

实施例8： 

在实施例1的基础上，本实施例所述新的节点的更新规则是当系统处理完了作业 Jk的所有 Map 任务后则按照全局更新准则做一次全局更新；如果计算节点在n个时刻未得到任何任务的分配，那么该节点上的信息素需要进行局部更新；其中，全局更新准则按照公式1.9确定，局部更新准则按照公式2.0确定。

[0041] 实施例9： 

在实施例1的基础上，本实施例流程如下：

1）首先将根据公式1.1初始化各个 TaskTracker 节点信息素；

2）检测到集群中有 TaskTracker 向 JobTracker 发出请求任务分配的消息,调度器将所有请求节点的 ID号加入到禁忌表tabu表中；

3）取出一个作业,并将其与对应分解的 Map任务一起添加到任务池中；

4）系统从任务池中取出任务,并根据公式1.2计算出 tabu 表里面每一个请求节点的初始转移概率；

5）根据任务情况计算出公式(1.4)的转移目标函数 ,并按照公式 1.8 选择进行转移,并且将被调度的请求节点 ID 号从禁忌表 tabu 表中删除；

6）当任务正常分配给 TaskTracker 后,利用公式1.7进行相应的信息素更新；

7）如果任务执行失败,则重新插入到属于本作业在任务池中的位置,等待下一次重新调度；

8）从任务池中取出下一个任务进行资源节点调度；

9）若当前一个作业处理完毕,根据公式1.9进行全局更新更新处理过该作业 Map 任务的节点信息素；

10）根据公式2.0进行局部更新挥发信息素；

11）从队列中取出下一个作业添加到任务池中等待调度,并重复迭代步骤。