YARN资源调度策略
YARN 资源调度器是直接从MR基础上修改而来，它提供了三种可用资源调度器，分别是FIFO Scheduler、Yahoo!的Capacity Scheduler 和Fackbook 的 Fair Scheduler，它们的原理和细节基本上与MR的三种调度器一致。都是层级队列方式组织资源的。这种方式符合公司或部门组织架构，有利于资源在不同资源间分配和共享，进而提高集群资源利用率。
一、调度原理
1.1 FIFO Scheduler
FIFO是Hadoop设计之初提供的一个最简单的调度机制： 即先来先服务。所有应用程序被统一提交到一个队里中，Hadoop按照提交顺序依次运行这些作业。只有等先来的应用程序资源满足后，再开始为下一个应用程序进行调度运行和分配资源。
优点：
原理是和实现简单。也不需要任何单独的配置
缺点：
1， 无法提供QoS，只能对所有的任务按照同一优先级处理。
2， 无法适应多租户资源管理。先来的大应用程序把集群资源占满，导致其他用户的程序无法得到及时执行。
3， 应用程序并发运行程度低。
1.2 Capacity Scheduler
Capacity Scheduler容量调度是Yahoo!开发的多用户调度器它以对了为单位划分资源。每个队列可设定一定比例的资源最低保证和使用上限。每个用户也可设置一定的资源使用上限，以防资源滥用。并支持资源共享，将队列剩余资源共享给其他队列使用。配置文件名称为capacity-scheduler.xml。
主要特点：
² 容量保证：管理员为每个队列设置资源最低保证（capacity）和资源使用上限（maximum-capacity，默认100%），而所有提交到该队列的应用程序可以共享这个队列中的资源。
² 弹性调度：如果队列中的资源有剩余或者空闲，可以暂时共享给那些需要资源的队列，而一旦该队列有新的应用程序需要资源运行，则其他队列释放的资源会归还给该队列（非强制回收），从而实现弹性灵活分配调度资源，提高系统资源利用率。
² 多租户管理：支持多用户共享集群资源和多应用程序同时运行。且可对每个用户可使用资源量（user-limit-factor）设置上限。
² 安全隔离：每个队列设置严格的ACL列表（acl_submit_applications），用以限制可以用户或者用户组可以在该队列提交应用程序。实现计算资源隔离。
1.2.1 应用程序提交过程
合法性检查：
1) 应用程序所属用户拥有该叶子队列的应用程序提交权限（ACL）；
2) 该队列及其父队列当前处于RUNNING状态；
3) 队列当前已提交应用程序数目未达到设定上限（yarn.scheduler.capacity.queue-name.maximum-applications，默认1000）；
4) 集群同时处于运行和等待状态的应用程序数量未达到上限（yarn.scheduler.capacity.maximum-applications，默认1000）；
1.2.2 资源分配
应用程序对应的AppMaster进程会为它申请资源。YARN采用了三级资源分配策略。当一个NodeManager节点有空闲资源时，它会上报给RM节点。由RM节点的ResourceScheduler组件分配该空闲资源。分配顺序是：依次选用队列、应用程序、和Container。
步骤 1 选择队列。
所有的队列都是root根队列的子队列。因此在选择队列时，从ROOT开始，基于优先级深度优先遍历算法。具体的优先级可以是资源使用率（已使用的资源量/队列资源容量，对于非叶子队列，它的已使用资源量是各个子队列已使用资源量之和）由小达到排序。
步骤 2 选择应用程序
在上一步中选中一个应用程序后，Capacity Scheduler按照FIFO方式排序，分配该资源给有申请Container资源的第一个应用程序。
步骤 3 选择Container请求
对于同一个应用程序，它请求的Container可能是多样化的，涉及不同的优先级，节点，资源量和数量。当选中一个应用程序后，Capacity Scheduler将尝试优先满足优先级高的Container。
1.2.3 思考：为什么叫容量调度？
Capacity Scheduler资源调度算法如何体现是容量调度？
答：
1) 队列资源采用容量占比的方式进行分配。
2) 队列间的资源分配算法也是采用最小资源使用率。
3) 每个用户的资源限制是资源量占比。
1.3 Fair Scheduler
Fair Scheduler是Facebook开发的多用户调度器。设计目标是为所有的应用分配公平的资源（对公平的定义可以通过参数来设置）。公平不仅可以在队列中的应用体现，也可以在多个队列之间工作。
举个例子，假设有两个用户A和B，他们分别拥有一个队列，且分别设置容量最小为集群的一半，最大为全部集群资源。当A启动一个job而B没有任务时，A会获得全部集群资源；当B启动一个job后，A的job会继续运行，不过一会儿之后两个任务会各自获得一半的集群资源。如果此时B再启动第二个job并且其它job还在运行，则它将会和B的第一个job共享B这个队列的资源，也就是B的两个job会用于四分之一的集群资源，而A的job仍然用于集群一半的资源，结果就是资源最终在两个用户之间平等的共享。
与Capacity Scheduler不同之处：
² 资源公平共享：每个队列中，Fair Scheduler可选择FIFO、Fair或者DRF策略为应用程序分配资源。其中，Fair策略是一种基于最大最小公平算法（内存资源使用率比率）实现的资源多路复用方式，默认情况下，每个队列内部采用该方式分配资源。schedulingPolicy设置队列内部调度策略。如果是非叶子队列，该调度策略为队列间调度策略，如果没有设置，则采用defaultQueueSchedulingPolicy策略。
² 支持资源抢占。队列空闲资源被共享给其他队列后，如果再提交用户程序，需要计算资源，调度器需要为它回收资源。为了尽可能降低不必要的计算浪费，调度器采用了先等待再强制回收的策略。如果等待一段时间后尚有未归还的资源，则会进行资源抢占：从超额使用资源的队列中杀死一部分任务，进而释放资源。
² 负载均衡：Fair Scheduler尽可能把系统中的任务均匀分配到各个节点上。此外用户也可以根据自己的需求设计负载均衡机制。
² 调度策略配置灵活： 每个队列单独设置调度策略（FIFO、Fair或DRF）。
1.3.1 应用程序提交过程
与Capacity Scheduler 的提交过程一致，主要是对权限以及资源数量进行检查。
1.3.2 资源分配过程
也采用了三级资源分配策略，即当一个节点上有空闲资源时，依次选择队列、应用程序和container使用该资源。
步骤1 选择队列
YARN实际运行应用程序的只有叶子队列，其他队列只是一个逻辑概念，用以辅助计算叶子队列的资源量。选择队列实际上就是根据当前所有队列的资源使用情况查找一个最合适的叶子队列。Fair Scheduler也采用了深度优先比遍历算法：从根队列ROOT开始，使用FIFO、Fair或者DRF策略对它的所有子队列进行排序，然后依次处理每个子队列。对于某个子队列，如果它是叶子队列，则直接返回，否则以该队列为根队列，继续按照以上方法查找叶子队列。
步骤 2 选择应用程序
选择一个队列后，按照Fair策略对叶子队列内部的应用程序进行排序，并以此检查排序后的应用程序。
步骤 3 选择Container
对于同一个应用程序，它请求的Container可能是多样化的，涉及不同的优先级，节点，资源量和数量。当选中一个应用程序后，Fair Scheduler将尝试优先满足优先级高的Container。
思考：如何体现公平？
1) Fair调度器中的队列有一个权重属性（这个权重就是对公平的定义），并把这个属性作为公平调度的依据。当调度器分配集群40:60资源给两个队列A和B时便视作公平。如果队列没有设置权重则会被平均分配。这里的权重并不是百分比，我们把40和60分别替换成2和3，效果也是一样的。注意，对于在没有配置文件时按用户自动创建的队列，它们仍有权重并且权重值为1。
2) 各队列之间也可采用Fair 策略进行资源分配。默认调度算法的考量因子是memory，但是也可以也可以设置DRF(Dominant Resource Fairness)，会考虑mem和vcore的资源。
二、问题
2.1 什么时候发生抢占？
Ø 最小资源抢占, 当前queue的资源无法保障时，而又有apps运行，需要向外抢占。
Ø 公平调度抢占, 当前queue的资源为达到max，而又有apps运行，需要向外抢占。
2.2 抢占过程？
步骤1 RM 探测到需要抢占的资源，并标注这些待抢占的Container。
步骤2 RM收到AppMaster的心跳信息，并通过心跳应答将待释放的资源总量和待抢占的Container列表返回给AppMaster。它收到这些Container列表。可以选择如下操作：
1) 杀死这些Container。
2) 选择并杀死其他Container以凑够总量。
3) 不做任何处理，过段时间可能有container自行释放资源或者由RM杀死Container。
步骤3 RM探测到一段时间内，AppMaster未自行杀死约定的Container，则将这些Container标准。等收到这些Container所在NM的心跳信息后，并通过心跳应答将待杀死的Container列表返回给它，NM将这些容器杀死，并通过心跳告知RM。
步骤4 RM收到AppMaster的心跳信息后，并通过心跳应答将已经杀死的Container列表发送给它（也有可能AppMaster早已经通过内部通讯机制获取到这些Container已经被杀死）。
2.3 如何决定是否抢占某个队列资源？
当有多个队列的资源可以被抢占的话，通过算法得到队列每个队列真正可以使用的资源量。并从超过应得资源最多的队列中抢占资源。
2.4 如何使抢占资源代价最小？
资源抢占是通过杀死正在运行的Container来实现资源释放的。由于这些容器已经处于运行状态，直接杀死Container会导致已经完成的计算白白浪费。为了尽可能避免资源浪费，YARN优先选择优先级较低的Container作为资源抢占对象，且不会立刻杀死Container，而是将释放资源的任务留给应用程序自己：RM将待杀死的容器列表发送给对应AppMaster，以期望它采取一定的机制自行释放这些Container占用的资源。如果一段时间后，AppMaster未主动杀死这些容器，则RM再强制杀死这些Container。
2.5 公有云如何实现计算资源隔离？
1) 给每个用户分配计算资源，即新建一个Yarn队列。
2) 给每个队列设置权重，最小资源以及最大资源上限。
3) 每个队列ACL设置可提交应用程序组，主账号的每个成员用户都属于该用户组。
4) 每个工程绑定一个队列，则该工程下的所有计算 任务都运行在该队列上。
5) 不同用户提交计算任务时，则运行在不同的资源队列，从而实现资源隔离，多租户，弹性抢占。
