适应异构集群的Mesos多资源调度DRF增强算法

柯尊旺 于炯 廖彬

摘要：云计算集群环境下多资源分配的公平性是考量资源调度子系统最重要的指标之一，DRF作为通用的多资源公平分配算法，在异构异质的集群环境下可能有失公平性。在研究Mesos框架中DRF多资源公平分配算法的基础上，设计并实现了增加机器性能评估影响因子的meDRF分配算法。将计算节点的机器性能得分，作为DRF主导份额计算的因子，使得计算任务有均等的机会获得优质计算资源和劣质计算资源。通过选取Kmeans、Bayes及PageRank 等多种作业进行实验，实验结果表明：meDRF较DRF分配算法更能体现多资源分配的公平性，且资源分配具有更好的稳定性，能有效提高系统资源的利用率。

关键词：资源分配；DRF分配算法；公平性；Mesos

中图分类号：TP311 文献标志码：A

Abstract：The fairness of multiresource allocation is one of the most important indicators in the resource scheduling subsystem， Dominant Resource Fairness （DRF）， as a general resource allocation algorithm for multiresources scenarios， it may be unfair in heterogeneous cluster environment. On the basis of the research on the DRF multiresource fair allocation algorithm under Mesos framework environment， meDRF allocation algorithm was designed and implemented to evaluate the influence factors of the performance of the server. The machine performance scores of computing nodes， as the dominant factor of DRF share calculation， made computing tasks have equal chance to obtain high quality computing resources and poor computing resources. Experiments were conducted by using Kmeans， Bayes and PageRank jobs under Hadoop. The experimental results show that， compared with DRF allocation algorithm， the meDRF algorithm can reflect more fairness of the allocation of resources， and the allocation of resources has better stability， which effectively improves the utilization of system resources.

Key words：resource allocation； Dominant Resource Fairness （DRF） allocation algorithm； fairness； Mesos

0 引言

随着云计算、大数据等新技术及应用的高速发展以及智能终端爆炸式增长，以Hadoop[1]、Spark[2]、Cloudra及Strom等为代表的大数据计算框架得到了快速发展。但是，传统数据中心的资源管理模式无法有效应对种类繁多的上层计算框架的个性化资源管理需求。在这样的背景下，作为下一代数据中心的创新者，软件定义数据中心（Software Defined Data Center，SDDC）[3]将服务器进行虚拟化、软件化数据中心的一切物理资源，并适应上层应用程序不断变化的资源需求，动态地进行资源分配。SDDC通过整合多种计算资源实现资源的统一管理和调度，在计算资源有限的情况下，为确保各计算任务节点的利益最大化，资源调度子系统应该提供一种公平的资源分配策略，使得各计算任务节点具有均等的机会获得计算资源来完成任务。另一方面，不同的计算任务（或作业）对不同资源类型的需求也存在着不同程度的差异，如：计算密集型的MapReduce[4-10]作业更多地需要CPU资源，而I/O密集型的MapReduce作业则需要更多的磁盘及内存资源。因此，SDDC集群中资源调度子系统需要解决多类型资源分配的公平性问题。

当前，资源公平分配方面的研究工作及实践主要集中在单资源类型的场景，以至于在多种资源类型和异质资源混合的应用场景下，仍采用首先将单资源进行抽象，然后再进行资源的分配工作，如Hadoop的slotbased[11]公平调度策略[12-13]。在单资源公平分配场景下，maxmin fairness[14-15]是最通用的单资源公平分配算法，它通过使资源分配向量最小值的最大化，确保任何资源请求不被饿死，是一种优秀的兼顾有效性和公平性的分配策略。而在多资源类型公平分配方面，DRF（Dominant Resource Fairness）[16]是一种针对多资源应用场景的maxmin fairness算法。DRF通过对“主导资源份额（Dominant Share）”进行maxmin fairness，比较合理地解决了多资源类型的分配公平性问题。经过大量的测试工作表明：DRF算法比slotbased算法更能够满足多资源分配的应用场景，资源分配的效率及公平性表现更佳[17]。

在DRF的实践中，资源调度管理框架Mesos[18-19]采用了DRF作为它的多资源公平分配算法，在集群节点的计算资源同构（即集群中的节点配置不存在差异）的情况下，DRF算法表现出优秀的性能，并能很好地权衡资源调度的有效性和公平性。但在实际的应用场景中，同一集群中的不同节点之间的资源质量可能存在着不同程度的差异，而DRF算法并没有考虑因为计算资源质量的差异性而导致的资源分配不公平性问题。为了改进DRF算法对异构集群环境的适应能力，本文通过增加节点性能评估影响因子，提出一种增强的DRF资源分配算法meDRF，使资源调度的各上层应用计算任务之间能够有均等的机会分配到满足需求的计算资源。

1 DRF分配算法

1.1 DRF算法简介

DRF资源分配是一种改进的maxmin fairness算法，能在多资源类型的集群环境中进行资源的公平分配，DRF是一种基于“主导份额（Dominant Share）”的多资源公平分配策略[17]。DRF公平分配算法具有4个性质[20]：

1） 鼓励共享（Sharing Incentive）。即集群中的上层应用之间通过共享自己的资源而不是独占资源来达到更高的资源利用效率。如：在一个具有n个计算任务的集群节点中，每个计算任务最多只能分配1/n的资源。

2） 欺骗屏蔽（Strategyproofness）。DRF能够防止计算任务谎报资源需求量，企图通过欺骗的手段而获取更多资源的行为。

3） 无嫉妒性（Envyfreeness）[21]。任何的计算任务都不能在获得计算资源后，通过已有的资源，去获得（或交换）另一个任务的资源。

4） 帕累托效率性（Pareto Efficiency）。集群中的所有计算任务都不能够在不减少其他任务的资源拥有量的前提下增加自己的资源拥有量。

DRF算法的核心思想是根据每个计算任务的资源需求向量和系统资源总向量，求出各个计算任务的主导份额。该主导份额所对应的主导资源是该计算任务最重要的计算依据。通过平衡各个计算任务的主导份额，来确定每个计算任务的子任务数量，最终得到每个计算任务的资源配额向量。DRF算法描述如下：

1.2 DRF算法的不足

在实际的集群环境中，集群中的计算机可能不是同一时间采购，或者机器品牌及机器型号之间存在着差异。在实际的资源分配过程中，即使分配相同数量的资源，但是由于节点之间的性能差异，分配方案之间存在较大的差异，将会有悖公平性原则[12]。DRF算法并没有考虑这种因计算资源性能的差异而导致的资源分配不公平性的问题，即使分配相同数量的资源，性能高的资源在任务的执行效率上比性能差的资源高。但是在DRF分配算法中，主导份额的计算只与资源数量有关，而与资源的质量无关。计算任务i的主导份额如式（2）所示：

式中：j表示资源类别，k表示资源种类数量，Rj表示资源类别j的资源总量，Wi表示计算任务的权重，Rui， j表示计算任务i已分配的j类别资源总量。

根据式（2）可知计算任务i的主导份额为该计算任务已获得的各类型资源与系统中该类型资源总量的比值中的最大值，如果计算任务存在加权，则主导份额与权重成反比。式（2）中无法体现出集群中节点之间的性能区别。如果有一个计算任务拿到大量的优质资源，而另一个拿到大量的劣质资源，虽然它们主导份额相同，但任务实际的执行效率和运行时间却相差甚远，这将导致资源分配的不公平，这种情况违反了DRF算法的Envyfreeness性质。

2 meDRF分配算法

本文提出的meDRF分配算法，是在DRF算法基础上增加了机器性能评估影响因子，使得计算任务有均等的机会获得优质计算资源和劣质计算资源，而不是长期持有优质或劣质计算资源。本算法的核心思想是：首先给每个集群节点的计算机进行性能评估打分并按照所得分值从小到大排序，再计算出每个计算任务的主导份额并从小到大排序，然后交替使用优质资源、劣质资源为计算任务的子任务进行资源分配，尽可能地使所有计算任务的主导份额趋向于平衡。

假设集群环境中存在n个计算节点，Qk表示机器k的性能评估得分，ηk代表机器k的性能评估得分与平均得分之比，Si表示计算任务i的主导份额，Rkj表示机器k上j类型资源的总量，Ruki， j表示计算任务i在机器k上已经分配的j类型资源数量，Rck， j表示机器k上j类型资源可分配的数量，Wi表示计算任务i的权重。

在Mesos中，使用框架这一术语表示计算任务。图1中灰色区域代表各框架的主导份额，dS1表示框架2和框架1的主导份额差，dS2表示框架3和框架2的主导份额差。为均衡不同框架间的主导份额，框架1在执行第1次分配计算时，在资源足够的情况下分配资源给子任务使其主导份额增加dS1，此时与框架2的主导份额相等。然后框架1进行第2次分配计算时框架2将执行第1次分配计算，框架1和框架2都使它们各自的主导份额增加dS2，此时与框架3的主导份额相等。综上所述，meDRF分配算法的流程描述如下：

1） 对每个集群节点的计算机进行性能评估打分，并按分值从小到大排序，求得ηk值；

2） 计算每个框架的主导份额Si，并按从小到大排序；

3） 计算相邻框架之间的主导份额差dSi；

4） 主导份额最小的框架进行分配计算，如果是第奇数次分配计算则从性能评估分值高的机器分配资源，如果是第偶数次分配计算则从分值低的机器分配资源；

5） 反复执行步骤2）～4），当所有任务分配完毕或者所有资源分配完成时，分配流程结束。

3 实验结果

本实验的集群环境由4个计算节点组成，分别为2台性能较差的曙光服务器和2台性能较好的IBM服务器，共56核CPU和48GB内存，服务器硬件配置如表1所示。集群节点计算机的操作系统Linux版本为CentOS 7.0，Mesos采用最新的0.24.0版本。运行2个Hadoop框架，分别处理不同的任务。本实验选取WordCount，TeraSort、NutchIndex、Kmeans、Bayes及PageRank[22]6种作业进行实验，作业参数设置如表2所示。

对比实验中，框架1的子任务对资源的需求为〈2核CPU，1GB内存〉，框架2的子任务对资源的需求为〈1核CPU，2GB内存〉。本实验在mesos中分别采用DRF算法和修改源程序实现的meDRF算法进行测试。经过运行表2中的MapReduce任务，两个算法分配的资源分布分别如图2、3所示。

通过对比WordCount、TeraSort、NutchIndex、Kmeans、Bayes及PageRank 6种作业分别在DRF、meDRF、异构、同构4种条件下的任务完成时间（如表3所示）。可以发现：不论是DRF还是meDRF算法，同构环境下的任务执行时间都较短；meDRF与DRF算法相比，meDRF大部分情况下的执行时间与DRF算法相比，执行时间较短。这说明更加公平的资源调度策略在一定程度上能够减小作业的执行时间。

实验过程中，本文还对不同作业的执行过程中内存，磁盘及网络资源使用情况进行了监控，如图4所示。

通过图4可以看出不同的MapReduce作业在运行过程中对内存、磁盘与网络资源的利用存在较大的差异，并且相同作业在不同时间点的资源使用情况变化也很大。并且，在异构环境下，这些随时变化的资源需求，已有的DRF算法并不能很好地适应公平性的要求。

算法meDRF比DRF在MapReduce中执行效率较好的原因是：当前Hadoop中采用机架感知的数据存放策略，将数据文件切分为相同大小的数据块（Block）随机存储到集群DataNode节点中。在同构环境中，这种数据的切分与存储方法配合DRF算法的资源分配，能够满足系统可用性与负载分流的要求。但是，在异构环境中，由于集群中各节点的计算能力存在着差异，异构节点处理相同任务（任务数据集大小相同）的完成时间不同。因为只有当一个作业的Map任务成功完成的数量超过一定的阈值时，才能开始分配该作业的Reduce任务给某TaskTracker节点执行，所以对于计算机能力强的节点，DRF算法在异构环境容易造成大量的等待时延。MapReduce任务执行过程中任务之间并不是按照完全并行的方式进行的，Map与Reduce任务之间存在不同程度的执行顺序与数据调用的制约关系。当某任务处于等待其他任务的执行结果（或等待其他任务的执行完毕）才能继续往下执行而处于“被动等待”状态时，DRF算法的资源分配的缺点就显现出来。而meDRF算法则是适应了异构环境的资源分配，较DRF更能提高异构环境下作业的执行效率。

另外，本文对任务运行过程中的资源使用情况进行了监控，对于系统最核心的资源CPU，DRF与meDRF算法的平均CPU负载情况比对如图5所示。从图5可以发现，meDRF算法较DRF算法在120min的监控周期中，meDRF算法的CPU负载更加平稳，波动幅度控制能力更好。

4 结语

本文在研究mesos框架中的DRF多资源公平分配算法的基础上，设计并实现了增加机器性能评估影响因子的meDRF分配算法。实验测试结果表明：meDRF分配算法更能体现多资源分配的公平性，且资源分配具有更好的稳定性，能有效提高计算资源的使用率。通过选取WordCount、TeraSort、NutchIndex、Kmeans、Bayes及PageRank 6种作业进行实验，对比作业运行时间及资源的使用情况，证明了meDRF算法相对于DRF算法的优越性。在实际应用的场景中，不同框架运行的作业类型存在差异，有些框架侧重于分析，而有些侧重于计算。如何使侧重计算的框架获得更多的优质资源，而侧重分析的框架获得较多的劣质资源，进一步提高资源使用率，是下一步的工作目标。

参考文献：

[1]SHVACHKO K， KUANG H， RADIA S， et al. The Hadoop distributed file system[C]// Proceedings of the 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies. Piscataway， NJ： IEEE， 2010： 1-10.

[2]WANG L， WANG Y， XIE Y. Implementation of a parallel algorithm based on a spark cloud computing platform[J]. Algorithms， 2015， 8（3）：407-414.

[3]LEE B S， KANAGAVELU R， AUNG K M M. An efficient flow cache algorithm with improved fairness in softwaredefined data center networks[C]// Proceedings of the 2013 IEEE 2nd International Conference on Cloud Networking. Piscataway， NJ： IEEE， 2013：18-24.

[4]DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters[C]// Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation. Berkeley， CA： USENIX Association， 2004：107-113.

[5]VERNICA R， CAREY M J， LI C. Efficient parallel setsimilarity joins using MapReduce[C]// Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2010： 495-506.

[6]覃雄派，王会举，杜小勇，等.大数据分析： RDBMS与MapReduce的竞争与共生[J].软件学报， 2012，23（1）：32-45.（QIN X P， WANG H J， DU X Y， et al. Big data analysis： competition and symbiosis of RDBMS and MapReduce[J]. Journal of Software， 2012， 23（1）：32-45.）

[7]张雪萍，龚康莉，赵广才. 基于MapReduce的KMedoids并行算法[J]. 计算机应用， 2013，33（4）：1023-1025. （ZHANG X P， GONG K L， ZHAO G C. Parallel KMedoids algorithm based on MapReduce[J]. Journal of Computer Applications， 2013， 33（4）： 1023-1025.）

[8]亓开元，韩燕波，赵卓峰，等.支持高并发数据流处理的MapReduce中间结果缓存[J]. 计算机研究与发展， 2013， 50（1）：111-121.（QI K Y， HAN Y B， ZHAO Z F， et al. MapReduce intermediate result cache for concurrent data stream processing[J]. Journal of Computer Research and Development， 2013， 50（1）：111-121.）

[9]顾荣，王芳芳，袁春风，等. YARM： 基于MapReduce的高效可扩展的语义推理引擎[J]. 计算机学报， 2015，38（1）：74-85. （GU R， WANG F F， YUAN C F， et al. YARM： efficient and scalable semantic reasoning engine based on MapReduce[J]. Chinese Journal of Computers， 2015，38（1）：74-85.）

[10]王习特，申德荣，于戈，等. MapReduce集群中最大收益问题的研究[J]. 计算机学报， 2015， 38（1）：109-121.（WANG X T， SHEN D R， YU G，et al. Research on maximum benefit problem in a MapReduce cluster[J]. Chinese Journal of Computers， 2015， 38（1）：109-121.）

[11]TANG S， LEE B S， HE B. DynamicMR： a dynamic slot allocation optimization framework for MapReduce clusters[J]. IEEE Transactions on Cloud Computing， 2014， 2（3）：333-347.

[12]夏祎. Hadoop平台下的作业调度算法研究与改进[D]. 广州： 华南理工大学， 2010： 30-40. （XIA Y. Research and improvement of Hadoop job scheduling algorithm[D]. Guangzhou： South China University of Technology， 2010： 30-40.）

[13]赵春燕.云环境下作业调度算法研究与实现[D]. 北京： 北京交通大学， 2009： 36-37. （ZHAO C Y. Research and implementation of a cloud environment job scheduling algorithm[D]. Beijing： Beijing Jiaotong University， 2009： 36-37.）

[14]最大最小公平算法[EB/OL]. [2015-10-22].https：//en.wikipedia.org /wiki/Maxmin_fairness.（Maxmin fairness[EB/OL]. [2015-10-22]. https：//en.wikipedia.org/wiki/Maxmin_fairness.）

[15]ASADPOUR A， SABERI A. An approximation algorithm for maxmin fair allocation of indivisible goods[J]. SIAM Journal on Computing， 2010， 39（7）：2970-2989.

[16]GHODSI A， ZAHARIA M， HINDMAN B， et al. Dominant resource fairness： fair allocation of multiple resource types[C]// Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation. Berkeley， CA： USENIX Association， 2011： 323-336.

[17]卢笛，马建峰，王一川，等.云计算下保障公平性的多资源分配算法[J]. 西安电子科技大学学报（自然科学版）， 2014，41（3）：162-168. （LU D， MA J F， WANG Y C， et al. Enhanced fairnessbased multiresource allocation algorithm for cloud computing[J]. Journal of Xidian University （Natural Science）， 2014，41（3）：162-168.）

[18]Apache Mesos Documentation[EB/OL]. [2015-10-03]. http：//mesos.apache.org/documentation/latest/index.html.

[19]HINDMAN B， KONWINSKI A， ZAHARIA M， et al. Mesos： a platform for finegrained resource sharing in the data center[C]// Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation. Berkeley， CA： USENIX， 2011：429-483.

[20]霍菁，石京燕，孙功星，等.一种改进的DRF算法对BESIII集群资源管理的优化[J]. 核电子学与探测技术，2014，34（10）：1153-1158. （HUO J， SHI J Y， SUN G X， et al. The optimization of BESIII cluster resource management by using the improved DRF algorithm[J]. Nuclear Electronics & Detection Technology， 2014，34（10）：1153-1158.）

[21]BOUVERET S， LANG J. Efficiency and envyfreeness in fair division of indivisible goods： logical representation and complexity[J]. Journal of Artificial Intelligence Research， 2008，32（1）： 525-564.

[22]BOLDI P， SANTINI M， VIGNA S. PageRank： functional dependencies[J]. ACM Transactions on Information Systems， 2009， 27（4）：1139-1141.