CN107038069B - Hadoop平台下动态标签匹配DLMS调度方法 - Google Patents

Abstract

本发明公开了Hadoop平台下动态标签匹配DLMS调度方法，属于计算机软件领域，针对Hadoop集群节点性能差异大、资源分配随机性、执行时间过长的问题，本发明提出一种将节点性能标签(以下简称节点标签)和作业类别标签(以下简称作业标签)进行动态匹配的调度器。节点初始分类并赋予原始节点标签，节点检测自身性能指标生成动态节点标签，作业根据部分运行信息进行分类生成作业标签，资源调度器将节点资源分配给对应标签的作业。实验结果表明，相对于YARN中自带的调度器在作业执行时间上有较大的缩短。

Description

Hadoop平台下动态标签匹配DLMS调度方法

技术领域

本发明属于计算机软件领域，涉及一种基于Hadoop平台下动态标签匹配DLMS调度方法的设计与实现。

背景技术

早期Hadoop版本由于将资源调度管理和MapReduce框架整合在一个模块中，导致代码的解耦性较差，不能很好的进行扩展，不支持多种框架。Hadoop开源社区设计实现了一种全新架构的新一代Hadoop系统，该系统为Hadoop2.0版本，将资源调度抽取出来构建了一个新的资源调度框架，即新一代的Hadoop系统YARN。众所周知在某一确定的环境下合适的调度算法能够在满足用户作业请求的同时，有效的提升Hadoop作业平台的整体性能和系统的资源利用率。在YARN中默认自带三种调度器：先入先出(fifo)、公平调度器(FairScheduler)和计算能力调度器(Capacity Scheduler)。Hadoop默认采用的是fifo调度器，该算法采用先进先出的调度策略，简单易实现，但是不利于短作业的执行，不支持共享集群和多用户管理；由Facebook提出的公平调度算法考虑不同用户与作业资源配置需求的差异，支持用户公平共享集群的资源，但是作业资源的配置策略不够灵活，容易造成资源的浪费，并且不支持作业抢占；雅虎提出的计算能力调度算法支持多用户共享多队列，计算能力灵活，但是不支持作业抢占易陷入局部最优。

然而在实际的企业生产中，随着企业的数据量加大，每年集群都会加入一些新节点，但是集群节点的性能差异是显著的，这种异构集群在企业生产环境中很普遍。设想如果将一个计算量很大的机器学习的任务分配在CPU计算能力很差的机器节点上，显然会影响作业的整体执行时间。Hadoop自带的三种资源调度器并没有很好地解决这个问题，本发明提出了一种节点性能和作业类别标签动态匹配的资源调度方法(DLMS)，将CPU性能比较好的机器贴上CPU标签，在磁盘IO性能比较好的机器上面贴上IO标签或者是两者都一般的普通标签，作业根据分类可以贴上CPU标签、IO标签任务或者普通标签，然后进入不同的标签队列，调度器尽可能将相应的标签节点的资源分配给相应的标签作业，从而可以减少作业的运行时间，提高系统资源利用率，提高系统整体效率。

发明内容

本发明提出的调度方法将集群节点进行初始分类并赋予相应的标签。NodeManager发送心跳前进行自我检测并对原始标签进行动态调整，并使用机器学习分类算法对作业进行分类赋予相应的标签，并根据用户设定的作业优先级，作业等待时间等属性动态实现作业的排序，并将相应标签的资源分配给相应的标签队列中的作业。

本发明所提出的调度方法主要包括以下模块：

(1)集群节点原始分类及其动态分类标签

集群节点首先需要进行初始分类，根据节点的CPU和磁盘IO性能进行分类。集群中每个节点都需要单独运行一个指定类型的任务并记录下该节点运行该类作业的时间，根据节点运行单个任务的时间与集群中所有节点运行时间平均值的大小关系将节点分成CPU型节点，磁盘IO型节点，普通型节点。

在集群节点运行的过程中，如果一个节点运行部分作业导致负载过大，会对这个节点的标签进行降级处理，直接降级为普通节点。一个节点初始标签是CPU型标签，节点中运行CPU型任务，虽然此节点还有部分资源未使用，但是此时环境中节点CPU性能优势已经失去，为避免这种情况出现，采取动态标签方法，在NodeManager向ResourceManager发送心跳的时候动态检测该节点机器的CPU和IO使用率，如果超过阈值，就将此节点标签贴上普通标签，每次发送心跳时都需要进行检测一次，由此实现节点动态标签。此阈值可以在配置文件中自行配置，如果用户未配置会参照系统默认值。

(2)Map执行信息的获取与回传

Hadoop作业通常分成Map阶段和Reduce阶段，通常大作业map数量在上百个甚至更多，一个作业主要时间是花费在Map阶段的计算上，但是每个Map又是完全相同的执行逻辑，所以会收集作业运行的第一个map进程的运行信息，这些信息在NodeManager向ResourceManager发送心跳时传递到调度器中，调度器根据传回的信息进行作业的分类。

企业生产环境中，每天都会运行一些相同内容逻辑的作业，即用户已知作业应所属的标签，在命令行或者代码中为作业设置作业类型标签，在调度的时候调度器会进行检查，如果用户已经对作业贴上标签，就省去作业分类的环节，直接进行调度。

(3)多优先级队列

为满足不同用户的需求，防止小作业出现“饥饿”现象，采用作业优先级方案。在调度器中新建5个队列即：原始队列、等待优先级队列、CPU优先级队列、IO优先级队列和普通优先级队列。用户提交作业首先是进入原始队列中，先运行作业部分map并收集这部分map运行信息，然后作业进入等待优先级队列中等待Map的运行信息回传并进行分类，最后根据作业的分类类别标签进入到对应标签的队列中。

(3)作业分类

在分类之前需要对数据进行预处理，数据预处理是指在前期对数据进行一些处理。为提高数据挖掘的质量产生了数据预处理技术。数据预处理技术有多种方法：数据清理、数据集成、数据变换和数据规约。这些数据处理技术在数据挖掘之前使用，大大提高数据挖掘模式的质量，降低实际挖掘所需时间。本文数据预处理主要是在数据归一化方面。数据归一化就是把各个变量数据都线性地变换到一个新标尺上，变换后变量最小值为0，最大值为1，这样就保证所有的变量数据都小于等于1。

在作业分类方面选择了简单、使用比较普遍而且分类效果较好的朴素贝叶斯分类器进行分类。如果用户在命令行和任务代码中已经添加作业的类型的话，这个步骤会省掉，直接进入相应的队列中等待分配资源。

(4)数据本地性

Hadoop中遵循一个原则是“移动计算比移动数据更好”，移动到放置数据的计算节点要比把数据移动到一个计算节点更加节省成本，性能更好。关于数据本地性本发明采取了延时降级调度策略。

有益效果如下：

1.本发明针对异构集群环境提出一种动态标签匹配的调度方法，通过对节点和作业进行分类，结合作业本身特性以及提交用户的属性共同组计算作业优先级，在分配资源时将相同类型资源和节点进行匹配，考虑到节点的性能跟现阶段运行的任务量的关系，采用自检测方法动态调整节点标签。最后通过实验来对算法性能进行对比分析。

2.本发明针对数据本地性问题，提出了延时降级的算法，降级分为当前本节点、本机架节点和随机节点三种，通过在一定的延时时间降低本地性等级来提高数据本地性。

3.本发明采用动态标签的方法，首先预先运行不同类型作业，根据单节点运行的时间和集群所有节点的平均时间对比对节点进行分类，然后根据集群节点运行任务的负载情况对节点性能进行自检测并生成相应的新标签。

4.本发明提出对作业进行分类，由于MapReduce作业Map部分都是相同的处理逻辑，所以可以根据作业预先执行的部分信息对作业进行分类。

附图说明

图1作业调度整体框架流程图；

图2调度算法流程图；

图3不同调度算法下三种作业总运行时间对比图；

图4DLMS下500M数据量下Container分布数量图；

图5DLMS下1G数据量下Container分布数量图；

图6DLMS下1.5G数据量下Container分布数量图；

图7作业组在不同调度算法下运行时间对比图；

具体实施方式

为使本发明的目的、技术方案和特点更加清楚明白，以下结合具体实施例子，并参照附图，对本发明进行进一步的细化说明。YARN调度框架如图1所示。

各个步骤解释如下：

(1)用户向YARN提交应用程序，其中包括用户程序、启动ApplicationMaster命令。

(2)ResourceManager为该应用程序分配第一个Container，并与对应的NodeManager通信，要求它启动应用程序的ApplicationMaster。

(3)ApplicationMaster向ResourceManager注册后，为各个任务申请资源，并监控它们的运行状态，直到运行结束

(4)NodeManager发送心跳前进行自我检测生成动态的节点标签，并向ResourceManager汇报资源。

(5)任务分类进入不同的标签队列中，进行优先级排序等待分配资源。

(6)ApplicationMaster通过RPC协议向ResourceManager申请和领取资源。

(7)根据NodeManager汇报的节点标签和资源，调度器将此节点的资源分配给对应标签队列的作业。

(8)ApplicationMaster申请到资源后，便与对应的NodeManager通信，要求它启动任务。

(9)NodeManager为任务设置好运行环境(环境变量、JAR包、二进制程序等)后，将任务启动命令写到脚本中，并通过运行该脚本启动任务。

(10)各个任务通过某个RPC协议向ApplicationMaster汇报自己的状态和进度，可以在任务失败时重新启动任务。

(11)应用程序运行完成后，ApplicationMaster向ResourceManager注销并关闭自己。

首先对集群物理节点进行初始分类，分类的方法过程如下：

(1)设集群机器节点集为N＝{N_i|i∈[1,n]}n为节点总数量，i为从1开始n的正整数，N_i表示集群中第i个物理机器。

(2)在每台节点上都执行一个相同的任务量的CPU、IO和普通型作业并记录作业执行时间；T_cpu(i)表示在第N_i个节点上执行CPU作业的花费时间；T_io(i)表示在第N_i个节点上执行IO作业的花费时间,T_com(i)表示在第N_i个节点上执行普通作业的花费时间。

(3)计算每种作业的集群平均时间，集群平均时间的计算公式如下：

j表示作业的类型，算出每个节点在此种作业下与平均时间的时间差，如果T_cpu(i)＜Avg_cpu，为这个节点贴上CPU型节点的原始标签，如果T_cpu(i)>Avg_cpu，为这个节点贴上普通型原始标签，通过比较后很可能每台节点上的标签会有多个，选择节省时间最多的标签为此节点的最后标签。

设Map的运行信息为M，它包括以下需要收集的信息M＝{MIn,MOut,Rate,Acpu,Mcpu,Zcpu,Mrate}Min表示map输入数据量，MOut表示map输出数据量，Rate表示输入数据量/输出数据量，Acpu表示CPU平均使用率，Mcpu表示cpu中位数，Zcpu表示cpu使用率超过90％的平均数，MRate表示内存使用量，这些数据将成为以后这个作业分类的特征属性。在实验的过程中发现单纯的计算CPU的平均时间不能很好反应作业的特征，通过实验发现CPU型作业的CPU使用率大于90％的次数比较多，其他类型的作业CPU使用率大于90％的次数相对较少，所以把这个信息也加入到map回传的信息中。

在队列优先级方面采取用户自定义双层权重的设计方法，设作业的大小属性所占的权重为worthNum，该属性分成三个等级num∈{long,mid,short}，作业的拥有者属性所占权重为worthUser，该属性分成两个等级user∈(root,others}，作业的紧急程度所占权重为worthEmogence，该属性可分成三个等级prority∈{highPrority,midPrority,lowPrority},作业的等待时间所占的权重为worthWait，等待的计算公式为waitTime＝nowTime-submitTime,赋予相应的权重，最后计算出每个任务的优先级数，然后在相应的队列中进行排序。上述四种任务属性权重相加和为100％，具体公式如下。

worthNum+worthUser+worthEmogence+worthWtait＝100％；

最后权重计算公式：

finalWort＝worthNum*num+worthUser*user+worthEmogence*prority+worthWait*waitTime

在作业分类方面，采用朴素贝叶斯分类器，具体分类步骤如下：

(1)分别计算一个作业在某些条件下是CPU、IO还是普通型作业下的条件概率：

P(job＝cpu|V₁,V₂...V_n)

P(job＝io|V₁,V₂...V_n)

P(job＝com|V₁,V₂...V_n)

其中job∈{cpu,io,com}表示作业类别标签；V_i为作业的属性特征。

(2)根据贝叶斯公式P(B|A)＝P(AB)/P(A)得:

假设V_i之间相对独立，根据独立假设其中

(3)实际计算中P(V₁,V₂,…,V_n)与作业无关可忽略不计，因此最终可得

同理有

作业是CPU型作业、IO型作业还是普通型作业取决于哪个概率值更大。

本地性本文采取了延时降级调度策略。该策略具体思想如下：

为每个作业增加一个延时时间属性，设T_i为第i个作业当前的延时时间，i∈[1,n],n为集群的节点数目，T_local表示本地节点延时时间阈值，T_rack表示机架节点延时时间阈值。当调度器分配资源给作业时，如果作业的执行节点和数据输入节点不在一个节点上，此时T_i自增1，表示该作业有一次延时调度，此时将此资源分配给其它合适的作业，直到当T_i>T_local时，作业的本地性就会降低为机架本地性，此时只要是本机架内的节点都可以将资源分配给该作业；当T_i>T_rack时，作业的本地性降低为随机节点。其中的T_local和T_rack都采用配置文件的方式由用户根据集群情况自行配置。采用延时的调度策略可以保证在一定的延时时间内获得较好的本地性。

DLMS调度方法的基本思想是预先分配部分作业执行，根据作业回传的信息对作业进行分类，然后将节点标签的资源分配给相应的队列中的任务，基本流程：

步骤1当节点通过心跳向资源管理汇报资源的时候，如果原始队列不为空，则遍历原始队列中作业，将已经在命令行或者程序中指定了作业类型标签的作业分配到相应的标签优先级队列中，原始队列移除此作业。

步骤2将原始队列中没有指定作业类型标签的作业调度至等待队列中。

步骤3如果等待优先级队列不为空，则对等待优先级队列中的作业进行分类进入相应的标签优先级队列。

步骤4如果节点性能标签相应的作业类别队列不为空，则将此节点的资源分配给此队列，此轮分配结束。

步骤5设置查看资源访问次数变量，如果超过集群的数量，则将节点的资源按CPU、IO、普通、等待优先级顺序将资源分配给相应的队列，此轮调度结束。本步骤可以防止出现类似以下情况，CPU队列作业过多，导致CPU型节点资源已经耗尽，其他标签的节点还有资源，但是作业无法分配资源的情况。算法的流程图如图2所示。

实验环境

本节将通过实验来验证本文提出的DLMS调度器的实际效果。实验环境为5台PC机搭建而成的Hadoop完全分布式集群，集群的节点机器配置统一为操作系统Ubuntu-12.04.1,JDK1.6，Hadoop2.5.1，内存2G，硬盘50G。其中NameNode的CPU的核数为2，dataNode1的CPU核数为2，dataNode2的CPU核数为4，dataNode3的CPU核数为2，dataNode4的CPU核数为4.

实验结果与说明

首先准备数据量为128M的wordCount(IO型)，kmeans(CPU型)作业各一个，分别在4台节点上面运行6次，记录下作业运行的时间。表1中s表示时间单位秒，avg表示该节点运行相应标签任务的平均时间，allAvg表示所有节点运行相应标签任务的总平均时间，rate的计算公式如下：

负号表示平均时间相对于总平均时间的减少，正号表示平均时间相对于总平均时间的增加。

由表1可以看出DataNode1在运行两个任务的时间都是节省时间的，我们采取节省最多的CPU作业作为机器的原始标签，DataNode2为IO标签，DataNode3、DataNode4为普通机器。

表1原始分类实验表

实验结果及其分析

使用可以明显区分作业类型的几种作业，WordCount在Map阶段需要大量的读取数据和写入中间数据，Map阶段和Reduce阶段基本上没有算数计算，所以将此种作业定性为IO型作业，Kmeans在Map阶段和Reduce阶段都需要大量的计算点和点之间的距离，并没有太多的中间数据的写入，所以将此种作业定性为CPU型作业，TopK在Reduce阶段没有大量的数据写入磁盘，也没有大量的计算，只涉及到简单的比较，所以人为的认为这个是普通型的任务。

通过两组实验来进行验证，第一组实验设置调度器为fifo，在500M、1G和1.5G的数据量下分别运行WordCount，Kmeans，Topk作业各3次，记录每个作业3次的平均时间作为最终时间，切换调度器为Capacity和DLMS调度器做同样的实验操作，实验中记录下DLMS调度器下每种作业的Container在集群的分布，Container是表示集群资源的划分单位，记录了作业分片在集群中运行的分布情况，YARN中每个Map和Reduce进程都是以一个Container来进行表示的。Container在集群中每个节点分布比例表明节点执行作业任务量的比例。图3的横坐标是作业的数据量，纵坐标是WordCount，Kmeans，Topk这3种作业共同运行的总时间。在数据量增大的情况下，DLMS调度器相比于其他的调度器节省大约10％-20％的时间。

因为DLMS会将相应节点标签的资源分配给相应标签的作业。作业的Map和reduce是以一个Container的形式在节点上运行的，图3至图5是在DMLS调度器下不同数据量作业的Container数量。根据上节的原始分类Node1是CPU型的标签节点，Node2和Node3是普通标签节点，Node4是IO标签节点。WordCount是IO型作业，Topk是普通型作业，Kmeans是CPU型作业。从图中可以看出Container的分布规律为WordCount作业在Node4上分配的Container比较多，Tokp在普通节点Node2和Node3上面分布的比较多，Kmeans作业在Node1节点上面分布的比较多。以上不同作业的Container在集群节点上的分布表明DLMS调度器提高了相应节点标签的资源分配给对应标签作业的概率。

第二组实验，准备了5个作业，分别是128M和500M数据量的WordCount作业，128M和500M数据量的Kmeans作业，500M的Topk作业组成一个作业组。5个作业同时提交运行。在不同调度器的集群中模拟连续作业执行情况，记录作业组执行完的总时间。作业组在不同的调度器下运行3次，记录下作业组运行完的总时间。具体结果见图6，从图6中可以看出本文提出的DLMS调度器相比于Hadoop自带调度器执行相同作业组节省的时间是显而易见的，本文提出的DMLS调度器相比Hadoop自带的Fifo调度器节省了大约20％的时间，比Capacity调度器节省了大约10％的运行时间。

Claims (1)

1.Hadoop平台下动态标签匹配DLMS调度方法，其特征在于：

集群节点原始分类及其动态分类标签；

集群节点首先需要进行原始分类，根据节点的CPU和磁盘IO性能进行分类；集群中每个节点都需要单独运行一个指定类型的任务并记录下节点运行指定类型的任务时间，根据节点运行一个指定类型的任务时间与集群中所有节点运行时间平均值的大小关系将节点分成CPU型节点，磁盘IO型节点，普通型节点；

在集群节点运行的过程中，如果一个节点运行部分任务导致负载过大，会对这个节点的标签进行降级处理，直接降级为普通节点；节点初始标签是CPU型标签，节点中运行CPU型任务，采取动态标签方法，在NodeManager向ResourceManager发送心跳的时候动态检测节点机器的CPU和IO使用率，如果超过阈值，就将节点标签贴上普通标签，每次发送心跳时都需要进行检测一次，由此实现节点动态标签；阈值在配置文件中自行配置，如果用户未配置会参照系统默认值；

(1)Map进程运行信息的获取与传递

收集任务运行的第一个Map进程运行信息，第一个Map进程运行信息在NodeManager向ResourceManager发送心跳时传递到调度器中，调度器根据传递的第一个Map进程的运行信息进行任务的分类；

若用户已知任务所属的标签，在命令行或者代码中为任务设置任务类型标签，在调度的时候调度器会进行检查，如果用户已经对任务贴上标签，就省去任务分类环节，直接进行调度；

(2)多优先级队列

在调度器中新建5个队列即：原始队列、等待优先级队列、CPU优先级队列、IO优先级队列和普通优先级队列；用户提交任务首先是进入原始队列中，先运行任务部分Map进程并收集Map进程运行信息，然后任务进入等待优先级队列中等待Map进程运行信息回传并进行分类，最后根据任务的分类类别标签进入到对应标签的队列中；

(3)任务分类

在分类之前需要对数据进行预处理，数据预处理是在数据归一化方面，把各个变量数据都线性地变换到一个新标尺上，变换后变量最小值为0，最大值为1，保证所有的变量数据都小于或者等于1；

在任务分类方面选择朴素贝叶斯分类器进行分类；如果用户在命令行和任务代码中已经添加任务的类型，任务分类会省掉，直接进入相应的队列中等待分配资源；

(4)数据本地性

数据本地性采取延时降级调度策略。

Images