主资源公平调度算法在YARN中应用研究

陈昕　刘朝晖

摘要：Apache Hadoop YARN是一种新的通用的Hadoop资源管理器，是在Mapreduce1的基础上发展起来的，该引入为集群在利用率、资源统一管理和数据共享等方面带来了巨大好处。为此，文章在分析了Hadoop YARN计算框架的基本结构和工作流程，重点研究了Hadoop YARN中的多资源分配机制，尤其是主资源公平调度算法（Dominant Resource Fairness，DRF）在YARN中的应用。

关键词：Hadoop；YARN；资源调度器；资源分配算法；DRF

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）05-0173-03

1 YARN的基本结构及工作流程

1.1 YARN 基本架构

YARN是Hadoop 2.0中的资源管理系统，它是在MapReduce的基础上发展起来的，与MapReduce不同的是，MapReduce有一个全局的管理器JobTracker，而YARN将JobTracker的功能拆分开来，成为了两个独立的管理器ResourceManager和 ApplicationMaster。ResourceManager负责全局的资源管理， ResourceManager负责单个应用程序的管理。

1.2 YARN基本组成结构

和MRv1一样，YARN也是Master/Slave结构，不过在YARN中有一个ResourceManager作为Master负责对各个Slave（NodeManager）上的资源进行统一的管理和调度。用户提交的应用程序需要提供一个ApplicationMaster跟踪和管理这个程序，它将向ResourceManager申请资源，之后会启动NodeManager任务。本小节我们将介绍YARN的基本组成结构。

1.2.1 ResourceManager（RM）

ResourceManager作为Hadoop全局的资源管理器，主要是负责YARN的资源管理和分配。它由两个组件构成：调度器（Scheduler）和应用程序管理器（Applications Manager，ASM）。

1）调度器

调度器和MRv1的一样，可以根据多种限制条件（如容量、队列等），将资源分配给系统中各个正在运行的应用程序。该调度器不从事任何与具体应用程序相关的工作（如监控或者跟踪应用的执行状态、重新启动因应用执行失败或者硬件故障而产生的失败任务），这些都由应用程序相关的ApplicationMaster完成。当应用程序需求资源时，调度器会将资源分配单位被抽象成一个“资源容器”（Resource Container，简称Container）分配出去。此外，调度器是可插拔的，同时用户只要实现了Hadoop提供的接口就可以实现自己的调度器。YARN也实现了多种直接可调用的调度器，比如公平调度器（Fair Scheduler）[1]和计算能力调度器（Capacity Scheduler）[2]等。

2）应用程序管理器（Applications Manager，ASM）

Applications Manager是一个管理整个系统中所有应用程序的管理器，主要功能包括提交应用程序、与调度器协商资源以启动ApplicationMaster、监控ApplicationMaster等。

1.2.2 ApplicationMaster（AM）

用户提交的每个应用程序均包含1个ApplicationMaster，主要负责：1）与ResourceManager调度器协商以获取资源（用Container表示），2）将任务分配给内部的任务，3）启动/停止任务、监控所有任务运行状态，若任务失败则重启任务。

1.2.3 NodeManager（NM）

NodeManager是每个节点上的资源和任务管理器，主要负责：1）定时地通过心跳的方式向ResourceManager汇报本节点上的资源使用情况和各个Container的运行状态；2）它接收并处理来自ApplicationMaster的Container启动/停止等各种请求。

1.2.4 Container

YARN中对资源抽象是用Container表示的，包括内存、CPU、磁盘、网络等多维度的资源都进行了封装，当ApplicationMaster向ResourceManager申请资源时，ResourceManager为ApplicationMaster返回的资源便是用 Container表示的。每个任务都会被分配一个Container，且该任务只能使用该Container中的资源，与MRv1中的slot不同的是，Container是一个动态资源划分单位，可以根据应用程序的需求动态生成的。目前YARN采用了DRF算法支持多维度的调度，不过目前仅支持CPU和内存两种资源，同时使用轻量级资源隔离机制进行资源隔离。

1.3 YARN工作流程

当用户向YARN中提交一个应用程序后，YARN将分两个阶段运行该应用程序：

阶段1：启动ApplicationMaster；

阶段2： ApplicationMaster创建应用程序，为应用程序申请资源，在程序运行完成前都监控它的整个运行过程。

步骤1 首先需要用户向YARN中提交应用程序，这个其中包括了ApplicationMaster程序、ApplicationMaster的启动命令、用户程序等。

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

步骤3 ApplicationMaster启动后，先要向ResourceManager注册，注册成功后用户可以直接通过ResourceManager查看应用程序的运行状态，然后ResourceManager将为各个任务申请资源，并监控它的运行状态，直到运行结束，即重复步骤4～7。

步骤4 在RPC协议的基础上，ApplicationMaster采用轮询的方式向ResourceManager申请和领取资源。

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

步骤6 NodeManager为任务设置好运行环境（包括环境变量、JAR包、二进制程序等）后，将任务启动命令写到一个脚本中，并通过运行该脚本启动任务。

步骤7 各个任务通过RPC协议向ApplicationMaster汇报自己的状态和进度，这样ApplicationMaster就可以随时掌握各个任务的运行状态，当任务失败时可以重新启动任务。在应用程序运行过程中，用户也可随时通过RPC向ApplicationMaster查询应用程序的当前运行状态。

步骤8 应用程序运行完成后，ApplicationMaster向ResourceManager注销并关闭自己[3]。

2 YARN的资源分配算法

资源调度机制是YARN资源调度器的核心。YARN资源调度器采用了多种调度机制，主要包括：双层资源调度机制、层级队列管理机制、资源保证和资源抢占机制。其中双层资源调度机制是其核心，是YARN进行资源分配的总体架构；层级队列管理机制是YARN对上层资源分配队列的管理方式；资源保证和资源抢占机制是YARN保证任务资源需求的机制[4]。在为了支持多维度的资源调度，YARN的资源调度器采用了主资源公平调度算法（Dominant Resource Fairness ，DRF）。该算法扩展了最大最小公平算法（max-min fairness），使其能够支持多维资源的调度。

2.1 最大最小公平策略（max-min fairness）介绍

在共享的计算机系统中，资源分配是一个重要的组成部分。最通用的分配策略是最大最小公平策略（max-min fairness），这种策略会最大化系统中一个用户收到的最小分配，在不考虑权重的情况下，这种策略每一轮会给予每个用户一份均等的资源。一般意义的max-min fairness是包含权重的，每一轮用户可以获得与它的权重对应的资源比例。加权max-min fairness的更具有一般性并且能提供性能隔离的能力。加权max-min fairness模型也可以支撑许多其他资源分配策略，包括优先级、deadline based allocation等。鉴于这些特征，max-min fairness已经被很多算法实现，如round-robin、proportional resource sharing、weighted fair queueing[5]。在不同的场景中，这些算法都被大量的实现，比如链路带宽、CPU、内存、存储等。虽然该策略已经被多方面应用，但目前为止主要还是集中在单资源类型的场景下。

实际上，由于一般意义上的max-min fairness是加权的，所以假设有A，B，C，D四个用户，权值分别为x，y， z，f。需求分别为a，b，c，d。总资源为e。我们可以多轮的分配资源。每一轮给用户分别分配e*j/（x+y+z+f）单位的资源（j代表用户相应权值）。若用户这一轮已经超出需求，则下一轮不分配，并且多出的资源留给下一轮作为总资源的一部分。这样直到所有资源分配完毕。

2.2 DRF算法

DRF是一种通用的多资源的max-min fairness分配策略。在DRF算法中，所需份额最大的资源叫做主资源，然后将max-min fairness应用在主资源上，这样多维度的资源调度就变为了单一资源的调度的问题，因为随着调度的进行，每个资源的份额都在变化，选择的主资源也在变化。举个例子，有两个用户A、B，A是计算密集型的，B是I/O密集型的，DRF在分配资源的时候会尽量的使得用户A的CPU资源份额和用户B的I/O资源份额比较均衡。

2.3 DRF计算方式

假设有两个用户，用户A、B，系统的CPU和内存分别为9、18GB.用户A每次都请求（1CPU，4GB）资源；用户B每次都请求（3CPU，4GB）资源。在这种情况下，如何均衡的分配资源？

在这个例子中，由于用户A的CPU占总CPU 1/9，RAM占总RAM的 2/9，而用户B的CPU占1/3，RAM占2/9，所以A的主资源为内存，B的主资源为CPU。基于这点，DRF会最大化A的内存的最小化分配，并会最大化B的CPU的最小分配。这就是DRF的分配策略。

3 结束语

在Hadoop中，YARN是其核心部分，而在YARN架构中，资源调度又是重中之重。现今YARN架构中实现的多资源调度是基于DRF算法的，充分的研究DRF的原理和在YARN实现，有助于我们部署平台和性能优化，还有助于我们发现其不足，为今后的多资源调度研究打下坚实基础。

参考文献：

[1] Hadoop Capacity Scheduler[EB/OL].（2015-01-07）. http：//Hadoop.apache.org/commom/docs/r2.2.0/capacity_scheduler.html.

[2] Hadoop Fair Scheduler[EB/OL].（2015-01-07）. http：//Hadoop.apache.org/commom/docs/r2.2.0/fair_schduler.html.

[3] 董春涛， 李文婷， 沈晴霓， 等. Hadoop YARN大数据计算框架及其资源调度机制研究[J]. 信息通信技术， 2015（1）： 77-84.

[4] 董西成. Hadoop技术内幕 深入解析YARN架构设计与实现原理[M]. 北京： 机械工业出版社，2014.

[5] Ali Ghodsi， Matei Zaharia， Benjamin Hindman.Dominant Resource Fairness：Fair Allocation of Multiple Resource Types[R]. Technical Report No.UCB/EECS-2011-18， 2011.