Hadoop平台下基于预释放资源列表的任务调度算法

摘要

本发明提出一种Hadoop平台下基于预释放资源列表的任务调度算法，充分利用了Hadoop记录的历史信息和集群当前状况监控信息来更好地帮助资源调度。本算法无需手动设置延迟等待时间。并通过对预释放资源列表中的资源进行预调度，解决了公平性和本地性之间的矛盾。另外，本发明提出的任务调度算法可以像延迟调度算法一样，同时应用于公平调度器和计算能力调度器。本发明的调度算法使用了预释放资源列表，通过资源列表与任务列表的匹配调度，无论在Hadoop完成时间、任务本地性，还是平均作业响应时间方面，都取得了更好的效果。

说明书

技术领域

本发明涉及分布式计算技术领域，特别是涉及一种Hadoop平台下基于预释放资源列表的任务调度算法。

背景技术

互联网技术催生了大数据时代的来临。当前，大数据已经成为了炙手可热的研究焦点。由于海量的数据使得单个的计算机已经无法满足存储及计算的要求，各种大数据的计算模式及其对应的分布式计算系统开始不断涌现。MapReduce无疑是其中最为经典的大数据计算模式，Apache Hadoop作为MapReduce的开源实现，得到了广泛的使用。任务调度与资源分配一直以来都是大规模分布式集群研究的关键技术，这对提高大数据集群的计算效率尤其重要。

目前Hadoop中常用的任务调度器有FIFO调度器、公平(Fair)调度器[1]和计算能力(Capacity)调度器[2]。其中FIFO调度器主要适用于批处理作业的处理，并不适合于多用户、复杂作业类型的环境。为了克服FIFO调度器的不足，多用户多队列调度器诞生了。这种调度器允许管理员按照应用需求对用户或者应用程序分组，并为不同的分组分配不同的资源量，同时通过添加各种约束防止单个用户或者应用程序独占资源，进而能够满足各种QoS需求。

Hadoop的JobTracker与TaskTracker之间通过“pull”方式进行通信。即JobTracker从不会主动向TaskTracker发送任何信息，而是由TaskTracker主动通过心跳“领取”属于自己的信息。所以JobTracker只能通过心跳应答的形式为各个TaskTracker分配任务。并且每个TaskTracker是在不同的时间向JobTracker发送心跳请求。所以即使当前有一批存在空闲资源的TaskTracker，任务调度器也是逐个接收到它们的心跳请求的。现有的任务调度算法都只根据当前请求任务的从节点状况，来选择任务进行分配。而没有将更多的资源与集群中各个作业的真实需求联系起来，从而做出更优的调度方案。公平调度器和计算能力调度器在选择队列和选择作业的时候都遵循公平的原则或者是计算能力的原则，但在选择任务的时候，为了满足任务的本地性，采用了延迟调度算法[3]。在当前作业没有满足本地性要求的任务时，需要将资源让给下一个作业。所以公平调度器存在公平性和本地性之间的矛盾，计算能力调度器存在计算能力和本地性之间的矛盾。同时，延迟调度算法需要手动设置node-local等待时间和rack-local等待时间两个参数。而这两个参数跟集群情况和作业情况密切相关，一般很难找到适合当前集群中作业情况的参数设置，而且也不可能在作业情况改变的情况下，又重新去调度这两个参数。

发明内容

本发明的目的就是要克服现有技术的不足，提供一种Hadoop平台下基于预释放资源列表的任务调度算法，为每个作业分配更适合的资源。

为解决以上技术问题，本发明所采用的技术方案是：一种Hadoop平台下基于预释放资源列表的任务调度算法，所述方法包括以下步骤：

S101：空闲TaskTracker提交任务请求；

S102：初始化所有作业的预分配资源数；

S103：筛选出还需要资源的所有队列needSlotPools；

S104：判断needSlotPools是否为空；如果为空，则不为该TaskTracker分配任务，调度结束；如果不为空，继续执行下一步；

S105：通过公平原则从needSlotPools中选择一个队列chosedPool；

S106：从被选中的队列chosedPool中筛选出还需要资源的所有作业needSlotJobs；

S107：通过公平原则或者FIFO原则，从needSlotJobs中选择一个作业chosedJob；

S108：创建被选中作业chosedJob的预释放资源列表；

S109：判断生成的预释放资源是否为空；如果为空，则从chosedJob中按照任务调度原则选择一个任务，调度结束；否则，继续执行下一步；

S110：将预释放资源列表中的第一个资源预分配给chosedJob；跳转到S103继续执行。

进一步的，所述步骤S103具体筛选过程包括：

比较队列的资源需求量与队列的预分配资源数，如果队列的资源需求量大于队列的预分配资源数，则队列需要资源；否则，队列不需要资源。

其中，一个队列的资源需求量等于该队列下所有作业的资源需求量的和；一个作业的资源需求量等于该作业尚未运行的任务数；一个队列的预分配资源数等于该队列下所有作业的预分配资源数的和。

进一步的，所述步骤S106具体筛选过程包括：

比较作业的资源需求量与作业的预分配资源数，如果作业的资源需求量大于作业的预分配资源数，则作业需要资源；否则，作业不需要资源。

进一步的，所述步骤S108预释放资源列表创建过程包括：

从当前所有正在运行的任务中挑选出来满足一定条件的任务加入预释放资源列表，再将满足条件的任务按照作业在任务所在资源的任务完成时间由小到大排序，即生成本发明的预释放资源列表；其中，该条件包括任务所在资源不能包含在预分配资源列表中，以及作业在任务所在资源的任务完成时间小于作业在当前空闲资源的任务完成时间。

本发明提出一种基于预释放资源列表的任务调度算法，充分利用了Hadoop记录的历史信息和集群当前状况监控信息来更好地帮助资源调度。本算法无需手动设置延迟等待时间。并通过对预释放资源列表中的资源进行预调度，解决了公平性和本地性之间的矛盾。另外，本发明提出的任务调度算法可以像延迟调度算法一样，同时应用于公平调度器和计算能力调度器。本发明的调度算法使用了预释放资源列表，通过资源列表与任务列表的匹配调度，本发明的算法无论在Hadoop完成时间、任务本地性，还是平均作业响应时间方面，都取得了更好的效果。

附图说明

图1为本发明算法基于预释放资源列表的资源三级调度模型示意图；

图2为本发明算法的总体流程示意图；

图3为本发明算法基于预释放资源列表的调度结果示意图；

图4为本发明算法的Hadoop完成时间比较示意图；

图5为本发明算法作业的任务本地性比较示意图；

图6为本发明算法的平均作业响应时间比较示意图。

具体实施方式

下面结合附图及实施例对本发明的实施方式作进一步描述。

如图1所示，本发明遵循如图所示的资源三级调度模型，包括：

步骤1：选择队列。按照公平原则选择最优先的队列。

步骤2：选择作业。从选中队列中的作业，按照公平原则或FIFO原则选择最优先的作业。

步骤3：选择任务。通过基于预释放资源列表的任务调度算法选择一个任务。

图中，①Fair原则选择队列；②Fair或FIFO原则选择作业；③基于作业的预释放资源列表选择任务。

图1则为本发明实施例的流程示意图，该方法包括：

S101、空闲TaskTracker提交任务请求；

S102、初始化所有作业的预分配资源数；

作业的预分配资源数用Job.preAssignNum表示。初始化所有作业：Job.preAssignNum＝0；

S103、筛选出还需要资源的所有队列needSlotPools；

具体筛选过程是通过比较队列的资源需求量与队列的预分配资源数。如果队列的资源需求量大于队列的预分配资源数，说明队列需要资源；否则就说明队列不需要资源。其中一个队列的资源需求量等于该队列下所有作业的资源需求量的和。一个作业的资源需求量等于该作业尚未运行的任务数。一个队列的预分配资源数等于该队列下所有作业的预分配资源数的和。

S104、判断needSlotPools是否为空。如果为空，则不为该TaskTracker分配任务，调度结束；如果不为空，继续执行下一步。

needSlotPools为空，说明所有的队列都不需要资源，因此不为TaskTracer分配任务，调度结束。

S105、通过公平原则从needSlotPools中选择一个队列chosedPool；

公平原则具体是指：当存在资源使用量小于最小资源量的队列时，优先选择资源使用率最低的队列，即(runningTasks+poolPreAssignNum)/minShare最小的队列。其中runningTasks是队列当前正在运行的Task数目，poolPreAssignNum是已经预分配给该队列的资源量，minShare为队列的最小资源量，它等于用户配置的队列最小资源量与该队列当前的真实资源需求量再减去poolPreAssignNum的最小值。否则选择任务权重比最小的队列，其中队列的任务权重比为：tasksToWeightRatio＝(runningTasks+poolPreAssignNum)/poolWeight。其中poolWeight是管理员配置的队列权重。

S106、从被选中的队列chosedPool中筛选出还需要资源的所有作业needSlotJobs；

具体的筛选过程是通过比较作业的资源需求量与作业的预分配资源数。如果作业的资源需求量大于作业的预分配资源数，说明作业需要资源；否则就说明作业不需要资源。

S107、通过公平原则或者FIFO原则，从needSlotJobs中选择一个作业chosedJob；

公平调度器允许管理员将队列设置为公平队列或FIFO队列。公平队列按照公平原则选择作业，FIFO队列则按照FIFO原则选择作业。

其中，作业的公平原则是指：优先将资源分配给资源池中任务权重比最小的作业，其中作业的任务权重比为：tasksToWeightRatio＝(runningTasks+jobPreAssignNum)/jobWeight。其中jobPreAssignNum是已经预分配给该作业的资源量，jobWeight是管理员配置的作业权重；当作业的任务权重比也一样时，则优先选择提交时间较早的作业。

FIFO原则是指：优先选择优先级最高的作业；优先级相同的情况下，选择作业提交时间最早的作业。

S108、创建被选中作业chosedJob的预释放资源列表；

预释放资源列表是从当前所有正在运行的任务中挑选出来的。将满足如下条件的任务加入预释放资源列表，再将满足条件的任务按照作业在任务所在资源的任务完成时间由小到大排序，即生成本发明的预释放资源列表。

条件1：任务所在资源不能包含在预分配资源列表中。

其中预分配资源列表是指一批已经预分配给Job的资源。在下节的基于预释放资源列表的任务调度算法中会进行预分配。

条件2：作业在任务所在资源的任务完成时间小于作业在当前空闲资源的任务完成时间。

其中作业在任务所在资源的任务完成时间是由三部分构成的，该任务的剩余完成时间、当前作业中的任务在该任务所在主机的完成所需时间和数据传输时间。作业中的任务在当前空闲资源的完成时间由两部分构成，当前作业中的任务在该任务所在主机的完成所需时间和数据传输时间。

任务的剩余完成时间和任务在指定主机的完成所需时间在Hadoop的任务推测执行机制中均提供相应实现。数据传输时间是由任务的本地性决定的。对node-local任务的数据传输时间为0，rack-local和non-local任务的数据传输时间取决于任务数据大小和机架内的网络带宽及机架间的网络带宽。

在本发明的任务调度器中，不同作业会生成不同的预释放资源列表。因为现在Hadoop集群的机器一般都是异构的，导致这些机器的CPU运算能力和I/O读写能力都是不同的。这样，Hadoop中不同类型的作业，如CPU密集型或I/O密集型作业面对同一个资源时，任务的处理时间是不一样的。所以需要针对不同作业生成不同的预释放资源列表。

构建预释放资源列表的伪代码如下所示：

输入参数依次为：按照公平原则被选中的作业，当前申请任务的空闲TaskTracker和预分配资源列表

S109、判断生成的预释放资源是否为空。如果为空，则从chosedJob中按照任务调度原则选择一个任务，调度结束；否则继续执行下一步；

任务调度原则是指优先选择满足node-local的任务，次优选择rack-local的任务，最后选择non-local的x任务。

S110、将预释放资源列表中的第一个资源预分配给chosedJob。跳转到S103继续执行。

将chosedJob的预分配资源数加1，即chosedJob.preAssignNum+＝1；同时将预分配给chosedJob的资源加入到预分配资源列表中。

从上面的流程中可以看到，本发明的调度结果存在两种可能，一种可能是不为TaskTracker分配任务。这种情况一般是所有的队列都已经预分配了足够的预释放资源，也就是说存在足够多的能使任务更快完成的预释放资源，所以就不为这个较慢的TaskTracker分配任务了。另外一种可能是从chosedJob中按照任务调度原则选择一个任务。此时预释放资源列表为空，说明该chosedJob已经找不到比当前TaskTracker更好的资源，所以直接从chosedJob中选择一个任务进行调度。

下面通过一个实例进一步描述该备份任务选择算法，并将直接调度算法、延迟调度算法和本发明的调度算法进行对比。如图3所示，假设当前集群只有一个队列，队列中有3个作业。Job1、Job2和Job3分别在Slot1、Slot2和Slot3上有数据本地性。作业优先级job1>job2>job3。Slot3、Slot1和Slot2将依次空闲。当前Slot3是请求任务的空闲资源。

(1)首先Slot3空闲资源开始请求任务，按照公平原则首先让Job1选择资源。按照本算法Job1会选择预释放资源列表的第一个资源。于是将Slot1预调度给Job1；继续按照公平原则让Job2选择资源，同样选择预释放资源列表中的第一个资源。于是将Slot2预调度给Job2。最后按照公平的原则让Job3选择资源，Job3的预释放资源列表为空，因为Job3的任务在Slot1和Slot2上的完成时间要小于在Slot3的完成时间，此时就将Slot3分配给Job3，同时因为Job3有node-local任务在Slot3上，所以Job3会选择一个本地性的任务在Slot3上执行。

(2)接着Slot2空闲出来，并请求任务。按照公平的原则首先让Job1选择资源，将Slot1预分配给Job1；接着Job2选择资源，直接从Job2上选择一个本地任务在Slot2上执行。

(3)最后Slot1空闲出来，并请求任务。Job1选择一个本地任务在Slot1上执行。

通过我们本发明的任务调度算法，所有的作业都获得满足本地性的资源。

接下来再看看延迟调度算法的结果：

(1)Slot3空闲并请求资源：因为Slot3不满足Job1的本地性，Job1把Slot3让给下一个Job；Slot3同样不满足Job2的本地性，Job2继续把资源让给下一个作业；Slot3满足Job3的本地性，所以就将Slot3分配给Job3。

(2)Slot2空闲并请求资源：Slot2同样不满足Job1的本地性，但此时Job1是否会把资源让给下一个作业，取决于延迟调度算法延迟等待时间值的设置。如果当前等待时间小于W1，则让给Job2；如果当前等待时间大于W1且小于W1+W2，则看Slot2是否满足rack-local，满足的话，Slot2调度给Job1，否则让给Job2。如果大于W1+W2，则直接将Slot2调度给Job1。其中W1和W2是延迟调度算法需要设置的两个时间参数。

(3)Slot1空闲并请求资源。Slot1调度给剩下的那个作业。

另外，FIFO调度器采用了直接调度算法，即直接把当前空闲的资源调度给当前优先级高的作业。所以调度结果就是Slot3分配给Job1，Slot2分配给Job2，Slot1分配给Job1。

通过下面的表格对比一下不同的调度算法的结果：

表1举例场景下不同算法的调度结果对比

从上表可以看出，本发明的算法任务本地性的效果是最好的，而延迟调度算法的结果则取决于延迟等待时间的设置。而直接调度算法则是任务本地性最差的。

但本算法的原则并不是为了使更多任务满足本地性，而是每次调度都让被选中的作业选择对该作业对说最快的资源。不同于延迟调度算法，在当前作业满足不了本地性的情况下，需要将调度机会让给下一个作业。也就是说，公平性需要让步于本地性。这就存在了公平性和本地性之间的矛盾。本发明提出的预释放资源列表，保证了作业能够从更多的资源中发现更快的资源。然后通过预调度，保证了每次选中的作业都可以选择对该作业来说最好的资源。最好的资源不是指满足本地性的资源，而是指能使作业中的任务更快完成的资源。因为非本地性任务需要数据传输时间，所以，一般来说，满足本地性的任务完成得更快。所以，这也保证了本算法能保持很高的任务本地性。

为了验证本发明的可行性和有效性，将本发明的基于预释放资源列表的公平调度算法(Fair-PRRL，Pre-Release Resources List)和Hadoop的采用延迟调度的公平调度算法(Fair-DL，Delay Sheduling)以及FIFO调度算法进行对比。考察不同算法运行各种类型的作业的结果，然后对算法在整个Hadoop的完成时间、作业本地性任务的情况以及平均作业响应时间等方面进行评估。

考虑到将一个调度算法直接在实际工作集群系统进行长时间测试计算、评估耗时太长，而且要找到集群规模、计算资源与计算场景完全满足每一次实验要求的实际系统也是非常困难的。因此，本发明根据Hadoop底层原理，基于Java语言实现了一个Hadoop模拟器，用于验证和分析本调度算法的有效性。以下是一些相关实现细节：

(1)模拟的Hadoop硬件配置情况：3个机架，每个机架上分别有10个慢节点、10个普通节点和10个快节点。其中，慢节点的任务处理速率是普通节点的0.8倍，快节点的任务处理速率是普通节点的1.2倍。每个节点上都设置4个Slot。机架内的网络带宽是20M/S，机架间的带宽则是5M/S。

(2)HDFS的配置情况：每个数据块的大小设置为128M。然后每个数据块的备份数设置为3。其备份策略考虑了负载均衡，具体为：首先选择当前负载最小的节点保存第一份数据；第二份数据保存的节点要求与第一份数据所在节点同机架但不同节点，在满足要求的情况下选择负载最小的节点；第三份数据保存的节点与第一份数据不同机架，同时也选择负载最小的节点。每个数据块有3份备份，这表明每个任务在3个节点上会有节点本地性。

(3)延迟调度算法的两个时间参数：W1设置为5秒，W2设置为20秒。这两个时间参数的设置也是考虑了集群的网络带宽。因为在一个机架内，一个任务的数据传输时间约为6.4秒，通过BlockSize除以机架内网络带宽计算所得；而跨机架传输时，一个任务的数据传输时间约为25.6秒，通过BlockSize除以机架间网络带宽计算所得。保证了等待到本地性任务的收益要大于非本地性任务的数据传输时间。

(4)作业类型情况：根据作业大小，划分了三种类型的作业。

表2不同作业类型的任务处理时间

一个作业数据量的大小决定了这个作业包含的任务数，比如大作业的数据量为800*128M，就表明大作业会被分成800个任务。

我们总共运行了四组实验，具体如下：

(1)创建3个队列，每个队列提交100个小作业，同时运行。

(2)创建3个队列，每个队列提交50个普通作业，同时运行。

(3)创建3个队列，每个队列提交20个大作业，同时运行。

(4)创建3个队列，每个队列提交100个小作业、50个普通作业和20个大作业，同时运行。

图4显示了各个调度算法分别运行完成Hadoop中所有作业所需要的时间。实验结果表明，Fair-PRRL算法在Hadoop完成时间方面明显好于Fair-DL算法。在运行小作业时，Fair-PRRL算法的Hadoop完成时间少于FIFO算法，而其它情况下，则略大于FIFO算法。这也说明，其实在执行批处理作业的时候，FIFO算法反而是效果最好的。因为FIFO算法只是按照作业提交时间逐个地执行作业，这样，作业执行的时候就不会有别的作业抢占资源。而Fair-DL算法，会同时运行很多作业，这样就可能导致某个作业的本地性资源，正好有其它作业的任务在这个资源上面执行。这就导致了这个作业只能选择非本地性的资源了，这也导致了更多的运行时间。Fair-PRRL算法也是同时运行多个作业，所以也存在着这样的问题。

Fari-DL算法和Fair-PRRL算法都考虑到了这个问题，所以Fari-DL算法通过延迟调度来解决作业的本地性资源已经被别的作业占领的问题，Fair-PRRL算法则通过基于预释放资源列表的任务调度算法来解决这个问题。

图5显示了各个调度算法的任务本地性情况。图中的nonLocalNum表示非本地性任务数，rackLocalNum表示rack-local的任务数，nodeLocalNum表示node-local的任务数。从结果来看，Fari-DL的本地性情况是最差的，Fari-DL算法和FIFO算法效果差不多。并且在小作业的情况下，Fari-DL算法的任务本地性效果更好。

Fari-DL算法都是在执行小作业的情况下，Hadoop完成时间和任务本地性情况优于FIFO算法，原因是当小作业较多时，本发明算法可以构建出足够大的预释放资源列表，从而有更多的选择可以获取到对当前作业更好的资源。

FIFO算法虽然在Hadoop完成时间和任务本地性方面表现很好，但它并不是一个适用多用户、多队列的一个调度算法。因为它逐个地按照作业提交时间执行作业，会导致后面的作业长时间处于等待状态。所以如果是在多用户、多队列的情况下，那么后提交作业的用户将会长时间的得不到反馈，处于后面的队列也是同样的道理。

图6展示了各个算法的平均作业响应时间。平均作业响应时间是指作业从提交到开始执行所需要的时间。FIFO算法的平均作业响应时间远远大于另外两个算法。而Fari-PRRL算法和Fari-DL算法则相差不大。

综合以上三个性能指标，本发明的Fari-PRRL调度算法无疑是最好的。虽然FIFO算法在Hadoop完成时间和任务本地性方面效果都不错，但Fari-PRRL算法与之相差不大，甚至在小作业较多的情况下，Fari-PRRL算法还略好于FIFO算法。而且FIFO算法不适合于多用户、多队列的情形，也大大限制了它的使用场景。至于Fari-DL算法，Fari-PRRL算法在Hadoop完成时间和任务本地性方面都要明显更好，作业的平均响应时间因为都是采用的公平调度原则，所以相差不大。

以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。

参考文献：

[1]Hadoop:Capacity Scheduler.http://hadoop.apache.org/docs/current/hadoop-yarn/hadoop-yarn-site/CapacityScheduler.html

[2]Hadoop:Fair Scheduler.http://hadoop.apache.org/docs/current/hadoop-yarn/hadoop-yar n-site/FairScheduler.html

[3]Zaharia M,Borthakur D,Sen Sarma J,et al.Delay scheduling:a simple technique for achieving locality and fairness in cluster scheduling.In:European Conference on Comp uter Systems.New York,2010,265-278.