接上篇：

【Free Style】Hadoop-Yarn之Resource Manager源码分析(三)

https://portal.huaweicloud.com/blogs/45e07b16c07311e7b8317ca23e93a891

4      算法介绍

Yarn的调度器的作用主要是回答了如何选择一堆队列，在队列上如何选择一个应用的问题。

Yarn Scheduler支持的调度机制包括：

a)         双层资源调度机制-----核心，Yarn资源分配总体架构

b)        层级队列管理机制----对上层资源分配的管理方式；

c)         资源保证和资源抢占机制----保证资源需求的机制

目前Yarn支持的调度算法主要有三种，Fifo Scheduler，Capacity Scheduler，Fair Scheduler。

a)         FIFO Scheduler：最简单的调度器，按照先进先出的方式处理应用。只有一个队列可提交应用，所有用户提交到这个队列。

b)        Capacity Scheduler（Yahoo）：可以看作是FifoScheduler的多队列版本。每个队列可以限制资源使用量。但是，队列间的资源分配以使用量作排列依据，使得容量小的队列有竞争优势。在同一个队列中使用FIFO

c)         Fair Scheduler（Facebook）：多队列，多用户共享资源。特有的客户端创建队列的特性，使得权限控制不太完美。根据队列设定的最小共享量或者权重等参数，按比例共享资源。延迟调度机制跟CapacityScheduler的目的类似，但是实现方式稍有不同。

算法对比如下：

4.1      资源分配模型

Yarn的资源分配模型如下，当NM通过心跳信息告知RM本身所拥有的资源之后，RM中调度器需要选择一个应用为其分配资源。其基本步骤如下：

1）选择队列：Capacity Scheduler优先选择资源利用率低的队列；而FairScheduler则依赖于所选择的具体策略，可以是Fair，FIFO，或者DRF。

2）从队列中选择应用：Capacity Scheduler使用FIFO，而Fair Scheduler同样使用Fair、FiFO，DRF等方式；

3）最后从应用中选择合适的容器进行分配，主要依赖于容器的优先级以及本地性特征。

      Capacity Scheduler

Capacity Scheduler允许多租户能够安全共享一个大的集群，在满足分配容量的限制下，为应用及时分配资源。CapacityScheduler确保共享一个大的集群的每一个组织所需的资源。资源共享的同时，每个组织可以访问那些不被使用的超额资源。

CapacityScheduler提供一个严格的限制集合，确保单个应用/用户/队列不能消耗不成比例的资源，同时，CapacityScheduler支持来自单个用户或者队列的已初始化/挂起的应用的限制，从而确保集群的公平和稳定。

目前Capacity支持以下特性：

a)         Hierarchical Queues：层次化队列确保资源共享。

b)        Capacity Guarantees：所有提交到一个queue上的应用可以访问所有分配给该queue的资源。管理员可以配置软限制或者可选的硬性要求在这些queue上的资源。

c)         Security ：每个queue都有严格的ACL用于控制哪些用户可以提交应用到某个queue上。同时也确保用户不能看到或者修改其他用户的引用。支持per-queue管理员角色和系统管理员角色。

d)        Elasticity ：空闲资源可以超分配给任意的queue，但是如果有一些在容量以下的queue需要资源时，这些资源将会被分配给那些在不足容量的队列的应用，这样可以防止集群中有人而已占用资源。

e)         Multi-tenancy：全面的限制以防止单个应用、用户、队列垄断整个queue或者集群的资源。

f)         Operability：1）Runtime Configuration：queue可以被动态修改（包括定义和属性，如容量，ACL等），也可以被动态创建，但是不能动态删除。2）Drain applications：管理员可以停止一个queue，新的应用不能被提交到该queue，但是已经存在的app可以运行到结束为止。管理员也可以重新start一个停止了的queue。

g)        Resource-based Scheduling：支持资源密集型app，app可以指定比默认情况更高的资源需求。目前支持内存资源。

h)        Queue Mapping based on User or Group：基于user或者group将一个job映射到一个指定的queue。

Queue（队列）是CapacityScheduler提供的主要抽象，由管理员创建表示共享集群的价值。CapacityScheduler提供多级别的queue，确保同一个组织的queue优先共享空闲资源，提供同一个组织中应用对于共享资源的亲和性。CapacityScheduler有一个预定义的queue，叫做root。系统中所有其他的queue都是root的子queue。子queue不会直接继承父亲的属性，除非有另外的说明。下图是queue的配置文件：

Capacity Scheduler的Queue可配置属性属性（etc/hadoop/capacity-scheduler.xml）：

a)         资源分配

                        i.              Capacity：百分比，同一层的所有queue的综合等于100.但是queue中应用可以消耗比queue capacity更多的资源（当存在空闲资源时），提供弹性能力。

                      ii.              Maximum Capacity：限制queue中app的弹性值。

                    iii.              Minimum-user-limit：每个队列在任意时刻分配给一个用户的资源分配比例最低值。通常还有一个默认最大值，是总资源/用户数。

                     iv.              User-limit-factor：queue容量的倍数，用于单个用户获取更多的资源，通常设置为1。

                       v.              Maximum-allocation-mb：queue中分配给每个container的最大内存。覆盖集群中maximum-allocation-mb参数，但是要小于等于该值。

                     vi.              Maximum-allocation-vcores：queue中分配给每个container的最大virtual core。覆盖集群中maximum-allocation-vcores参数，但是要小于等于该值。

b)        运行、挂起进程限制

                        i.              Maximum-applications/per-queue Maximum-applications: 系统中并发的app最大个数，单个queue上的app个数按照容量的比例进行划分。也可以对每个queue进行单独设置，但是要小于或者等于比例划分的值。

                      ii.              Maximum-am-resource-percent / per-queue Maximum-am-resource-percent: 运行AM的资源最大比例。

c)         Queue管理和权限

                        i.              State：queue的状态，可以是running或者stopped

                      ii.              Acl_submit_applications: 控制app提交权限；acl规则如果没有被特殊指定会从父queue继承。

                    iii.              Acl_administer_queue：控制app管理权限。

d)        Queue映射

                        i.              Queue-mappings：指定user或者group与特定的queue进行映射。

                      ii.              Queue-mapping-override.enable：特定user的queue是否可以被覆盖。

Capacity Scheduler具有的其他属性：

a)         资源计算器

                        i.              resource-calculator：用于在Scheduler中比较资源。如DefaultResourceCalculate和DominantResourceCalculate，前者只使用内存，后者使用多种条件。

b)        数据位置

                        i.              node-locality-delay：在本rack中执行调度允许失败的次数。

4.3      Fair Scheduler

Fair Scheduler为每个app平均分配资源，资源的等价共享。Hadoop NextGen能够基于多种资源类型进行调度，目前，Fair Scheduler的缺省决策基于内存，但是也可以配置基于内存和CPU，使用DRF。Fair Scheduler不像缺省的hadoop调度器，他可以确保短任务在理想时间内执行完成，并且长任务不会饿死。

Fair Scheduler将app组织为queue，然后在queue之间进行公平共享。缺省的，所有用户共享一个名为default的queue，但是如果app在容器资源请求中指定了队列，那么该请求将会被提交到对应的queue。另外也可以通过包含在配置请求中的用户名字分配queue。在每个queue中，调度策略被用于在所有running app之间共享资源。缺省调度策略是基于内存的公平共享，但是也可以配置FIFO以及DRF多资源调度策略。Queue可以被划分成多个子queue，同时每个queue配置不同的权值。

Fair Scheduler的queue具有以下属性：

a)         Fair Scheduler支持层次化queue，所有的queue都从“root”queue划分出来。

b)        所有的可用资源在root queue的所有子queue之间按照fair Scheduling方式进行分发；同时这些queue也按照相同的方式分发给他们的子queue。App只能在叶子queue上进行调度。

c)         Queue的名字：parent.queuename

d)        Fair scheduler允许按照用户的需要对不同的queue设置不同的客户策略，以便按照用户的需要共享资源。可选的调度策略包括：FIFOPolicy， FairSharePolicy，DRFPolicy。

Fair Scheduler除了提供公平共享，同时也能够提供最小共享保证，这对于保证某些user，group或者产品app总是能够得到足够的资源是非常有用的。当一个queue包含app时，它至少能够分配到最小的share，但是如果当这个queue不需要他所有的share时，超额部分可以分配给其他app。这可以在保证queue capacity的同时，在queue中没有app时有效提供资源利用率。

4.3.1        Fair Scheduler调度流程

Fair Scheduler的调度流程：

1. 对Queue进行排序，使用SchedulingAlgorithms.FairShareComparator排序。排序规则如下

1)    比较 资源使用量 < min(资源需求量,最小份额），即是否饥饿；

2)    比较 资源分配比=资源使用量/min(资源需求量, 最小份额, 1)

3)    比较 使用量与权重的比例 =资源使用量/权值，小的排前面, 即权重大的优先, 使用量小的优先

4)    比较 提交时间，早的优先, app id小的排前面。

1. 排序之后，第一个队列成为最优先分配资源的队列。因此只需要把资源分配给该队列；

2. 然后基于特定策略（FIFO，Fair，DRF等）将资源分配给应用；

3. 如果第一个队列不需要资源，则继续分配给下一个队列。如果已经分配则继续执行第一步，直到资源分配完成。

4.3.2        Fair Scheduler支持的配置文件

Fair Scheduling支持的配置，主要有两类，一类是Scheduler范围的，在yarn-site.xml，另一类主要是在allocation file中，用于表示存在哪些queue以及他们相应的weights和capacities。

a)         在yarn-site.xml

                        i.              Allocation.file : allocation file的路径。

                      ii.              User-as-default-queue：是否使用分配相关的用户名作为默认的queue name。

                    iii.              Preemption：是否使用抢占；

                     iv.              Preemption.cluster-utilization-threshhold：抢占触发的利用率阈值。

                       v.              Sizebasedweight：是否基于app的size去分配shares，而不是等价共享。Size = loge(1 + requested memory) / loge(2)  此处并未说明request memory的单位。

                     vi.              Assignmultiple：是否允许在一个心跳中有多个container分配。

                   vii.              Max.assign：如果assignmultiple是true，则该字段表示最多多少个。

                 viii.              Locality.threshold.node：对于指定node请求container的APP，该参数指定了在其他节点上放置app之前在指定node上获得最后一个container的尝试调度次数。

                     ix.              Locality.threshold.rack：与node的概念相似，只是修改为rack；

                       x.              Allow-undeclared-pools：用于表示是否允许创建未指定的pool，在app提交的时候，如果submitter指定的app queue或者由user-as-default-queue使用的queue不存在是，该特性会创建对应的queue。如果该参数未指定，那么就会放到default queue。

                     xi.              Update-interval-ms：锁定调度器，重新计算公平共享，重新计算需求，检查是否应该得到抢占的时间间隔。

b)        在allocation file中

                        i.              Queue elements

1.         minResources：queue能够得到的最小资源。如果queue的最小共享没有得到满足，那么在同一个parent下，他会优先得到共享资源。如果多个queue资源没有得到满足，那么获得资源比例最小的queue具有最高优先级。

2.         maxResources：queue最大能够得到的资源。

3.         maxRunningApps：queue并发运行的app数量；

4.         maxAMShare：在一个queue中AM所能占用的资源比例。

5.         weight：queue的权值。权值为2的queue能得到的资源机会是权值为1的queue的两倍（这个权值和指定的资源量之间是什么关系，是否例如权值是2，mem是1G，vcore是2的queue 和 权值是1，mem是2G，vcore是4的queue之间怎么分配资源）

6.         schedulingPolicy：调度策略，fifo，fair，drf。其中fifo是指先提交的app优先获得container，后达到的在有剩余资源的时候才能运行。

7.         aclSubmitApps：可以提交app到该queue的user或者group列表；

8.         aclAdministerApps：可以管理该queue的user或者group列表

9.         minSharePreemptionTimeout：queue在最小share无法满足的情况下，抢占其他queue资源之前的等待时间；

10.     fairSharePreemptionTimeout：queue在低于公平共享阈值的情况下，抢占其他queue资源之前的等待时间；

11.     fairSharePreemptionThreshold：queue的公平共享抢占阈值，如果没有设置就从父亲继承。

                      ii.              User elements：user管理行为设置。

1.         MaxRunningApps：设置单个app并发运行app数量

                    iii.              userMaxAppsDefault：任一用户的缺省运行app数目。

                     iv.              defaultFairSharePreemptionTimeout：root queue的缺省公平共享抢占超时时间

                       v.              defaultMinSharePreemptionTimeout：root queue的缺省最小共享抢占超时时间

                     vi.              defaultFairSharePreemptionThreshold ：root queue的公平共享抢占阈值；

                   vii.              queueMaxAppsDefault ：queue的缺省运行app数；

                 viii.              queueMaxAMShareDefault ：queue的缺省AM资源限制；

                     ix.              defaultQueueSchedulingPolicy ：queue缺省的调度策略；

                       x.              queuePlacementPolicy ：要求调度器将app放置到queue中的规则列表

前文：

Free Style】Hadoop-Yarn之Resource Manager源码分析(一)

【Free Style】Hadoop-Yarn之Resource Manager源码分析(二)

【Free Style】Hadoop-Yarn之Resource Manager源码分析(三)