B站的YARN以社区的2.8.四分支结构，采用CapacityScheduler作为调度器， 在此期间，进行了多次核心功能改造，目前支持B站的离线业务、实时业务和部分业务AI训练任务。2020年以来，随着B站业务规模的迅速增长，集群总规模达到8k单集群规模已达4左右k ，日均Application（下文简称App）数量在20w到30w左右。目前最大的单集群整体cpu峰值通常达到80%：
2021年，原来的AZ在1机房无法扩容的背景下，启用了AZ2机房。每个机房都有离线集群、实时集群和在线业务混合集群，分别支持某些业务场景。为了支持跨机房场景，所有这些Client接入Federation，通过RMProxy路由到不同机房的不同集群。具体结构如下图所示：
定义单个App以下是所有的分配时间Container分配时间的总和，和Container分配时间可以理解为从申请开始Container，到App实际拿到该Container时差。例如，如果是某一个例子App如下图所示：
假设一开始(t0)申请 8 个Container，一段时间后(t1)返回 5 个Container，那么一共有5个Container在等待了 t1 - t0 时间过后，我得到了自己的资源。这样样，我们得到了5个Container分配时间。随后(t2)又申请了2 个Container，又过了一段时间(t3)返回了5 个Container。至此，该App再也不需要别的了Container了。所以，按照上面说的，总共有五个Container等待时间为 t1 - t0，有3个Container等待时间为 t3 - t0。这是上次没有分配的三个Container。有2个Container等待时间为 t3 - t2。那么该App的Container等待时间如上图蓝色面积所示，即 5 * (t1 - t0) 3 * (t3 - t0) 2 * (t3 - t2)。
如上图所示，红色代表高优先级App, 灰色是低优先级，我们的优化目标是App分配时间占运行时间的比例越小越好。
如何从业务层面判断调度系统是否成为系统统是否成为系统瓶颈。在YARN在资源设计中，通常每个业务对应一个队列，我们等待队列资源（pending），集群资源利用率（clusterUsedR），队列资源利用率（queueUsedR）这三个变量定义了有效的调度指标（validSchedule）含义：当资源存在等待时，如果集群资源利用率低于一定阈值（如90%），队列资源利用率也低于一定阈值（如95%），则认为此时的调度性能已不能满足队列的资源需求。
if (pending > threshold) { if （root.getUsedCapacity > clusterUtilization）{ return 1 }else{ if (queue.getUsedCapacity > queueThreshold) { return 1 }else { return 0 } }else { return 1 }返回1意味着当前调度满足需求，而返回0意味着当前调度不能满足需求。如下图所示，选择一个操作量较大的队列，发现在夜间高峰时段，有效的调度指标会高频下降0，即高峰时段的调度仍存在一些瓶颈。
以有效的调度指标为判断依据，当每个队列提交过多的任务请求时，可以通过反压服务让步Client提交等待，防止无效请求在集群中无意义积累。
反压服务毕竟压制了用户的请求，而我们的目标是尽力满足用户的资源需求。为了达到这一目标，我们需要对YARN重新梳理调度核心流程：
scheduler.lock sortNodes; for( node : Nodes ) { sortQueues; for (queue : Queues) { sortApps; assignContainer; } } scheduler.unlock至少有两个心流程至少有两个问题。Scheduler 锁从选择节点、队列和App直到分配结束，这个过程的前半部分才可以剥离，调度和写锁只需锁定核心资源的变化；第二，整个调度过程涉及多个对象的排序，行业有很多优化点。因此，对这两点进行了相应的改进。
从上述调度过程可以看出，关注的核心排序逻辑主要存在于队列和App两个层级。
在队列层面，目前我们根据不同的业务需求设置了相应的队列优先级，一些不能按业务划分的操作可以在队列内设置App优先考虑区别对待。对于每个分配过程，调度器不需要感知队列资源的使用并触发每个分配过程中的排序。调度器的主要精力仍然集中在分配上，所以我们在每个队列排序后冷却一段时间。
在App在层面上，目前使用的策略类似SP算法(严格优先调度，Strict Priority)，从高到低按优先级选择，等到高优轮询结束才轮到低优，会有一些低优App无法分配。经调查发现WRR(加权轮询，Weighted Round Robin) 这个问题可以很好地解决，所以我们设计了WRR Ordering Policy作为App层次排序策略。
如上图所示，WRR调度机会的调度机会与这个级别的权重成正比。该策略首先判断是否为优先级5，如果为5，则实施，先优先5App全部执行完毕，然后执行4-0优先级App。这种设计可以在特殊情况下得到保证App能尽快完成。
具体来说，优先级5App现在一定是最重要的App，内部不应对App对比调度顺序，遵循先来后到的原则，对用户更有说服力，所以在优先级5中使用FIFO作为Comparator。一般情况下，App优先级为0(最低优)至4(次高优)WRR作为App分配策略。WRR通过简单的计算，最细粒度可以区分不同的优先级App获取资源速度的目的。内部使用相同的优先级DRF作为Comparator，这是因为比较FairComparator，DRFComparator能够将VCore综合考虑各种资源也纳入了比较范围。对DRFComparator，还引入了App如果一个等待因素被分配，App等待分配时间过长，需要改进App优先分配，避免App长期饿死。
为了观察WRR Ordering Policy我们使用压试工具的效果SLS2400个节点，5000个节点Job，App分为0~34个优先级。压力测试结果如下图所示，任务完成时间按优先级分布，每个时间也有低优先级任务完成，符合预期。
单集群节点的增长YARN对调度性能提出了更高的要求。当RM控制节点数量超过4000后，原默认心跳驱动调度（Heartbeat-Driven Scheduler）集群利用率不能再满了。为了保证RM调度能力和NM我们评估了增长速度的匹配Hadoop开源社区对RM最终决定采用性能提升的解决方案Global Scheduling目前的思路RM改变调度逻辑。
Global Scheduling：全局调度
Proposal ：一个分配的建议，比如某个App要求在队列A分配<1G,2Core>资源
AsyncScheduleThread: 负责提出Proposal线程，可并发
resourceCommitterService: 负责接受或拒绝Proosal 的线程，单线程
Global Schedusling的主要目标可以分为两个，第一是赋予YARN多线程调度的能力，从而提升单集群的调度性能；第二是将App的可选范围从单一Node的转变为批量Nodes（PlacementSet），从而能够支持较优节点调度、满足更复杂的资源请求。基于此，我们将Global Scheduling分为两个版本进行迭代升级，其中v1版本聚焦于YARN多线程改造，v2版本聚焦于批量节点及其选取策略改造。
YARN调度的逻辑能够分为“提出Proposal”、“消费Proposal”两个部分，目前的单线程调度逻辑将两部分在一个线程中完成，而Global Scheduling v1的主要目标是对上述两部分进行解耦，之后将“提出Proposal”的逻辑改为多线程并发，再单独生成一个线程运行“消费Proposal”的逻辑，具体框架如下图所示：
5.3.1 批量ERROR LOG问题
在Global Scheduling 灰度上线离线集群时，发现ERROR Log的数量在启动后陡增，检查日志后发现大量报错信息为：
Trying to schedule for a finished app, please double check.该Log在位于CapacityScheduler.allocateContainerOnSingleNode()内reservedApplication == null的检查中触发。经过分析发现，App在执行完doneApplicationAttempt后应该继续执行doneApplication，而偶发情况下App在doneApplicationAttempt后仍会存在该App提交的Proposal，若此时另一个消费线程消费剩下的Proposal则会持续触发该ERROR Log。修复做法为在tryCommit.accept()中添加一个检查条件，若doneApplicationAttempt中remove的applicationAttemptMap查不到该App Attempt ID，则说明doneApplication已完成，直接拒绝该Proposal。
5.3.2 资源计算口径不一致导致大量Proposals失败
B站YARN对队列的资源分配分为日间版本与夜间版本，其中夜间版本会放大ETL队列的资源量，并大幅度限制Adhoc等队列的资源量。Global Scheduling v1在首次切换为夜间版本时出现了Proposal Failed Num陡增的现象。产生大量Failed是不符合预期的，预期Proposal提出的口径应该与Proposal消费的口径一致，若口径不一致，则会导致超出预期数量的失败Proposal出现。根据Failed Proposal Reason Num的监控，我们发现大量Failed位于accept()的此处：
if (!Resources.fitsIn(resourceCalculator, cluster,
Resources.add(queueUsage.getUsed(partition), netAllocated),
maxResourceLimit))从这里倒推提出Proposal时的调用为checkHeadroom()，此处判断队列使用资源是否会超过限制，需要调用greaterThanOrEqual()方法，这样当ResourceCalculator设置为DRF时，与上述fitsIn()不一致，两者的判断逻辑不一致从而导致了大量Failed产生。同样的问题也出现在ParentQueue.canAssign()中。将提出Proposal的资源计算逻辑与消费Proposal端对齐后，切换夜间版本后分配速率恢复正常。
我们在社区设计的基础上做了如下优化，使得Global Scheduling拥有更好的表现：
1. 精简了日志数量；
2. 多次压测确定了Backlogs长度以及多线程的线程数量；
3. 优化了Reserve Limit的逻辑，以降低Re-reservation Proposal 被接受的数量；
4. 优化了Event Queue的处理方式，以防止RM切换时产生Event堆积；
5. 优化了GC参数；
6. 新增了一批Global Scheduling相关指标的监控，能够及时准确的分析调度运行的情况。
5.4.1 精简日志数量
Global Scheduling改造首当其冲的问题就是日志数量随着多线程数量的成倍增加，大量调度过程中产生的日志严重影响了Global Scheduling在压测环境与生产环境中的性能表现，我们在考虑日志重要程度与调用频率后，将部分日志从INFO级别修改为DEBUG级别，经过对日志的精简后，Global Scheduling在压测中的表现已好于之前的心跳调度版本。
5.4.2 Backlogs长度及线程数量
在进行压测时发现，单独对Backlogs数量改变会导致压测总用时的变化。基于此，我们将Backlogs的长度改为了可动态配置的模式，通过Backlogs长度与多线程数量进行调优。经过多轮压测以及生产环境灰度验证后，最终将Backlogs长度设定为1000，多线程数量设置为4。
5.4.3 Reserve Limit优化
能够被成功消费的Proposal分为Allocate、Reserve、Re-reserve、Release四类，在生产集群观察到Re-reserve的Proposal数量远大于其他三种。
Re-reserve设计的初衷是为了缓解饥饿问题，但原先在RegularContainerAllocator.shouldAllocOrReserveNewContainer()中的公式似乎无法很好的与当前Global Scheduling的逻辑契合，以至于Re-reserve的数量会很轻易的达到MAX_INT。目前社区倾向于通过简化Re-reserve的计算方法及更智能的抢占来优化目前的Re-reserve机制（详见YARN-8149，YARN-9598）。
为了缓解消费线程的压力，我们在Global Scheduling的逻辑中加入了Reserve Limit功能，Reserve Limit能够控制单个App的Reserve上限。通过下图的压测结果能够看到Reserve Limit能够在不影响Allocate Proposal的基础上，一定程度上减少Re-reserve的处理次数。
5.4.4 Event Queue优化
在进行RM主备切换时，发现NodeUpdate汇报呈现逐渐缓慢的趋势，且最多仅能处理2000+左右Nodes的汇报。与此同时大量Event在Event Queue中堆积，最终导致RM在printEventQueueDetails()上浪费了大量时间去处理Event Queue的打印逻辑。因此我们将Event Queue打印逻辑拆分为一个新的线程，在不影响RM的基础上输出Event Queue信息，改动后的RM主备切换节点完全汇报时间大幅降低，能在可控的时间内完成4000+ Nodes的汇报处理工作。
5.4.5 GC优化
与Global Scheduling v1同步进行的还有GC的优化。经过对比，相比G1GC，我们为RM选择了在Java 8中表现的更稳定的ParNew + CMS，在此基础上对年轻代、老年代比重重新划分，并对ParGCCardsPerStrideChunk等参数进行了调优，使其对大内存回收更加高效。调优结果如上图所示，能够看到，GC的优化对YARN单集群整体利用率的提升起到了一定的正面作用。
5.4.6 监控
Global Scheduling的引入带来了新的监控指标，我们选取了以Proposal状态为中心的各类指标以排查Global Scheduling的相关问题。这些指标主要可以概括为：
1. Proposal Succeed / Failed Num
2. Succeed Proposal Reason Num
3. Failed Proposal Reason Num
4. BackLogs Num
5. Reserve Limit Match Num
其中Failed Proposal Reason Num中又可以细分为常规原因Failed与队列原因Failed两类，在队列原因的拒绝中，又能够将由于队列达到Max Limit而Failed的监控细分至LeafQueue级别。
经过压测工具SLS多次压测模拟，压测参数为1W节点，运行100个Jobs，每个job 1W Container。运行完成100个job，心跳调度平均需要3min15s， 而Global Scheduling平均只需要2min， 提升约38%。
从有效调度指标进行分析，选取同样的队列，在上线Global Scheduling V1之后该指标掉0的比例有了很大改善，有效调度时长有了较大提升。
本文主要介绍了大数据调度YARN在B站的落地实践，总体来说主要涉及了两个方面：
1. 引入两个调度性能的评价指标；
2. 对核心调度流程进行重构和优化。
后续我们将继续跨机房，离线实时业务混部，离线作业上云（Yarn On Kubernetes、Kubernetes Native）等在B站的实践。