走进 YARN 资源管理和调度｜ 青训营笔记

这是我参与「第四届青训营 」笔记创作活动的的第 16 天

在前面的课程中我们学习了各种各样针对不同使用场景的计算引擎，例如：Flink、Spark 等，使用这些计算引擎的任务最终都需要运行在集群的节点上，如果调度这些任务就是本模块内容所要解决的问题。

下面我们开启《资源和调度》模块，资源和调度主要解决大规模集群中资源管理和任务调度相关问题。在本模块中主要会讲解两个典型系统：主要针对离线业务场景的 Hadoop YARN 系统，主要针对在线服务场景的 Kubernetes。

• 在《走进 YARN 资源管理与调度》课程中，会讲解 YARN 系统的设计思想和整体架构，两个核心模块 Resource Manger 和 Node Manager 的整体架构和主要职责，YARN 系统中 Fair Share 和 DRF 两种典型的调度策略， YARN 系统内部的事件处理机制， YARN 系统在高可用性方面的实现逻辑和 Failover 处理流程。最后会介绍字节跳动公司内根据业务场景对 YARN 系统的优化，主要包括：Gang 性调度器设计与应用、单集群规模突破 50K 优化、反调度器设计与应用。

• 在 《深入理解 K8S 资源管理与调度》课程中，会讲解 K8S 发展的背景和基本概念，K8S 中的资源管理机制，K8S 中的资源调度方式，以及字节跳动公司内部针对在线业务场景所做的优化。

YARN 概述

初识调度系统

场景描述

首先考虑如下虚拟场景，如何进行高效调度在保障就餐公平性的前提下让尽可能多的学生都能够在该餐厅就餐、尽可能多的座位被有效使用？

• 学校为改善学生生活新建了一所美食餐厅，餐厅座位有限且只能堂食；

• 各个学院需要缴纳一定管理费用后其学生才能在该餐厅用餐，缴纳费用与分配的座位数成正比；

• 因餐厅物美价廉、环境干净，来该餐厅就餐的人络绎不绝；

简易分配模型

一种简易的分配模型参考如下：

• 各学院学院缴纳费用后获得固定座位数；

• 学生按照学院组织，学院内的用餐小组按照预定时间排队，每个小组有一个负责人；

• 餐厅经理（两个备用经理）对所有学院按照分配座位满足率由低到高排序，优先选择靠前学院进行餐位派发；

• 餐厅经理选择一个学院后，基于餐厅座位情况，以 FIFO 方式选择用餐小组并分配桌号；

• 用餐小组在餐厅经理助手引导下到特定位置进行就餐，用餐小组负责人安排组内有序成员就坐；

• 用餐结束后，用餐小组负责人向餐厅助手说明；

优化的分片模型

• 保障公平性

  • 学院间按照分配座位满足率排序；
  • 学院内先来先服务、后来后服务；

• 保障高效性

  • 餐厅经理有很多助手以辅助其派发，助理可以统计就餐信息、学院排序、引导等；
  • 餐厅经理做决策，助手异步同步信息；

• 保障高可用

  • 两个备用经理，随时可以工作；

• 如何满足 “尽可能多”？

  • 座位超售：所有学院分配座位大于总座位数
  • 学院超用：有座位时学院可以超分配座位
  • 座位超发：“允许一个座位坐两个人”
  • 鼓励快餐：鼓励大家快速就餐离开

• 就餐学生有个性化需求

  • 同用餐小组必须坐一个桌子
  • 同用餐小组必须坐不同桌子
  • 用餐小组必须要坐靠窗位置
  • 有重要活动同学需靠前就餐

调度系统演进

调度系统发展的背景

如今，我们已经由信息科技时代（IT）进化到数据科技时代（DT），数据中蕴藏的海量信息激发我们开发各种计算模型和计算框架进行挖掘，而这些计算模型和计算框架最终都需要落地计算。同时数据计算方式也发生了很大变革，从单机到分布式集群再到大规模数据中心，计算越来越快。对于大型互联网公司而言，为了完成各种对外服务以及对内挖掘等任务，需要的硬件资源数以万计，具有较高的成本。

调度系统解决的问题

当用有限资源解决有限资源无法满足的需求时就需要调度。如何充分挖掘硬件资源潜力、灵活进行资源管理与调度以及提高集群整体利用率成为降本增效的关键问题。资源资源管理与调度主要解决资源请求和可用资源的映射 (Mapping) 问题，也就是将负载的资源请求与当前计算集群中的可用物理资源通过一定的调度策略进行匹配 (Matching)。

调度系统预达的目标

集群资源管理与调度系统的核心目标是： 设计出更好的资源管理与调度策略，使得整个集群在保障任务 SLA 的前提下能够实现更高的资源利用率、更快的计算任务完成速度。

• 严格的多租户间公平、容量保障

• 调度过程的高吞吐与低延迟

• 高可靠性与高可用性保障

• 高可扩展的调度策略

• 高集群整体物理利用率

• 满足上层任务的个性化调度需求

• 任务持续、高效、稳定运行

• We want to have all of them… However…

调度系统设计的基本问题

• 资源异质性与工作负载异质性

异质性通常指组成元素构成的多元性和相互之间较大的差异性。资源异质性是从系统所拥有的资源角度来看的，对于大型数据中心来说，其采购往往是分批次的，不同批次的机器硬件配置和计算存储资源都存在较大差异，很难保证采用完全相同的配置，目前主要通过将资源分配单位细粒度划分以及虚拟化技术来解决；工作负载异质性是从系统提交的任务角度来看的，负载类型多样化（流处理、批处理、内存计算、在线服务等），任务偏好多样化和动态化（任务的约束条件、运行过程中资源使用动态变化），资源需求多样化（CPU，内存，GPU，IO 等），例如对外服务要保证高可用和快速响应，对于批处理任务要保证快速调度等。

• 数据局部性

大数据场景下因为数据传输开销要远大于计算逻辑传输开销，因此往往将计算任务推送到数据存储所在地进行，这种设计哲学一般被称为数据局部性问题。在资源管理与调度语境下一般存在 3 种类型数据局部性：节点局部性，机架局部性和全局局部性。节点局部性完成计算不需要进行数据传输，机架局部性需要在机架之间进行数据传输存在一定开销，其它情况则属于全局局部性需要跨机架进行网络传输进而产生较大的网络传输开销，因此最优的方式是尽可能保证节点局部性。

• 抢占式与非 抢占式调度

在多用户多任务场景下，面对已分配资源，资源管理与调度系统有两种不同类型的调度方式：抢占式调度与非抢占式调度。抢占式调度指的是当系统资源不足或存在资源竞争时高优先级的任务可以抢占低优先级任务的资源；非抢占式调度，每次只允许从空闲资源中分配，空闲资源若不足则须等待其它任务释放资源后才能继续推进，mesos 采用非抢占式调度。两种方式各有特点，一般如果强调高优先级任务执行效率的调度策略会采用抢占式调度，强调资源公平分配的调度会采用非抢占式调度。

• 资源分配粒度

大数据场景下的计算任务往往呈现层级结构，例如：作业级（Job）- 任务级（Task）- 实例级（Instance），从计算任务视角来看，此时资源调度系统就面临资源分配粒度问题，资源分配粒度主要存在三种方式：（1）群体分配策略（Gang Scheduler），即要么全满足要么全不满足，Flink 和 MPI 任务依赖这种方式；（2）增量满足式分配策略，只要分配部分资源就可以启动运行，MR 采用这种方式；（3）资源储备策略，资源达到一定量才能启动作业，在未获得足够资源时作业可以先持有目前已经分配的资源并等待其他作业释放资源，调度系统不断获取新资源并进行储备和积累，直到分配到的资源量达到最低标准后开始运行，在作业启动前已经分配的资源处于闲置状态。

• 饿死与死锁问题

饿死是由于调度策略不当而导致计算任务长时间无法获得开始执行所需要的最少资源量，例如支持优先级调度时，如果不断出现高优先级任务，那么低优先级任务可能饿死；死锁是由于资源分配不当而导致整个调度系统无法正常执行，例如在资源储备策略下，如果 AB 两个作业启动作业需要的最小资源为 2/3，那么如果两个任务被分配了 1/2 的资源时，就导致死锁。调度系统出现死锁必然表现为某些作业处于饿死状态，但计算任务饿死的情景并不一定意味着调度系统处于死锁状态。

• 资源隔离方法

为了减少任务之间的干扰需要进行一定的隔离措施，LXC 是一种轻量级的内核虚拟化技术，LXC 在资源管理方面依赖于 Linux 内核的 cgroups 子系统，cgroups 子系统是 Linux 内核提供的一个基于进程组的资源管理框架，可以为特定的进程组限定可以使用的资源。其他技术有 Intel RDT。

调度系统范型

1. (a) 集中式调度系统
   • 产生背景：该调度系统是大规模数据分析和云计算出现的雏形，主要进行大规模的集群管理以提高数据处理能力。
   • 基本原理：中心式调度系统融合了资源管理和任务调度，有一个中心式的 JobTracker 负责进行集群资源的合理分配、任务的统一调度、集群计算节点信息的统计维护、任务执行过程中的状态管理等。
   • 优点：
     • JobTracker 能够感知集群中所有资源和任务的执行状态，能够进行全局最优的资源分配和调度，避免任务间的干扰，适当进行任务抢占，保证任务计算效率和服务质量；
     • 架构模型简单，只有一个全局的管理者负责进行所有管理。
   • 缺点：
     • JobTracker 作为集群的中心，存在单点瓶颈问题，不能支持大规模集群；
     • 内部实现异常复杂，一个调度器中需要实现所有的功能模块，可扩展性差；
     • 负载变更会导致系统需要进行不断的迭代，这将增加系统的复杂性，不利于后期的维护和扩展；
     • 只支持单类型的任务，MR 类型的批处理任务；
   • 典型的调度系统：Hadoop1.* 版本；K8S 中的 kube-scheduler，Quasar。
2. (b) 两层调度系统
   • 产生背景：为了解决集中式调度系统的扩展性问题，系统实现复杂，可扩展性差，不能支持不同类型任务等缺点。
   • 实现原理：将资源管理和任务调度解耦。集群资源管理器负责维护集群中的资源信息并将资源分配给具体的任务，任务管理器负责申请资源并将申请到的资源根据用户逻辑进行细分和具体的任务调度。
   • 优点：
     • 资源管理器只负责资源分配，任务调度由应用完成，提高了系统的扩展性；
     • 任务调度逻辑由具体的任务完成，能够提供对不同类型任务的支持；
     • 内部实现模块化，利于维护和扩展；
   • 缺点：
     • 任务无法感知全局的资源情况，只能基于 request/offer 来进行资源获取，无法有效避免异构负载之间的性能干扰问题；
     • 任务调度和资源管理解耦不利于实现多任务间的优先级抢占；
     • 所有任务的资源请求都需要资源管理器进行处理，此外其还需要与节点管理器之间维持通信，导致资源管理器存在单点问题；
   • 典型系统：Mesos，YARN，Fuxi
   • Mesos 最先将资源管理和任务调度解耦的 offer-based（基于资源供应）方案，其有一个中心的资源管理器，通过分配策略（DRF）将资源分配给不同的计算框架，每个计算框架依据自身的逻辑、资源偏好等采取增量或者 All-or-Nothing 的方式决定接受还是拒绝分配的资源，计算框架根据分配到的资源进行下一步的资源分配和任务执行。
3. (c) 共享状态调度系统
   • 产生背景：前面的调度器存在一个问题就是计算框架在进行资源申请的时候无法获知到集群的全局资源信息，这就导致无法进行全局最优的调度，共享状态调度器就提供了这个问题的一种解决方式。
   • 基本原理：是一个半分布式的架构，通过共享集群状态为应用提供全局的资源视图，并采用乐观并发机制进行资源申请和释放，来提高系统的并发度。
   • 优点：
     • 支持全局最优调度；
     • 能够一定程度的提高并发度；
   • 缺点：
     • 高并发资源请求下会造成频繁的资源竞争；
     • 不利于资源分配的公平性；
     • 资源全局副本维护模块存在单点瓶颈；
   • 典型系统：Omega
4. (d) 分布式调度系统
   • 产生背景：提高系统吞吐率和并发度
   • 基本原理：分布式调度器之间没有通讯协作，每个分布式调度器根据自己最少的先验知识进行最快的决策，每个调度器单独响应任务，总体的执行计划与资源分配服从统计意义。
   • 优点：提高吞吐量和并发度
   • 缺点：
     • 调度质量得不到保障；
     • 资源非公平分配；
     • 不能支持多租户管理；
     • 不能避免不同任务之间的性能干扰；
   • 典型系统：Sparrow 是一个完全的去中心化的分布式调度系统，通常用于满足低延迟高吞吐的短任务场景。系统包含多个调度器，这些调度器分布在集群的节点上，作业可以提交给任何一个分布式调度器。其核心是采用随机调度模型，利用二次幂采样原理针对每个任务随机采样出两个服务节点，选择任务等待队列最短的一个作为调度结果，也可以采用异步预定的方式进行资源调度。实验证明近似最优解能够有效的满足大规模毫秒调度性能的需求。
5. (e) 混合式调度系统
   • 产生背景：针对一些特定的混合任务调度场景，某些任务需要比较快的调度响应，而其他任务不需要很快的调度响应，但是需要保证调度质量。
   • 基本原理：设计两条资源请求和任务调度路径，保留两层调度的优点，同时兼顾分布式调度器的优势。对于没有资源偏好且响应要求高的任务采用分布式调度器，对于资源调度质量要求较高的采用集中式资源管理器进行资源分配。
   • 优点：
     • 能够针对不同类型的任务进行不同方式的调度；
     • 为应用层提供灵活的接口和性能保障；
   • 缺点：复杂化了计算框架层的业务逻辑；调度系统内部也需要针对两种不同的调度器进行协同处理；
   • 典型调度系统：Mercury: 微软的混合调度机制，中心式调度器对调度质量要求较高的作业进行公平的资源分配，分布式调度器对时间敏感和吞吐率要求高的作业进行调度。

YARN 设计思想

演化背景

Hadoop 1.0 时代：由分布式存储系统 HDFS 和分布式计算框架 MapReduce (MR v1) 组成，MR v1 存在很多局限：

• 可扩展性差：JobTracker 兼备资源管理和任务控制，是系统最大的瓶颈；

• 可靠性差：采用 master/slave 结构，master 存在单点故障问题；

• 资源利用率低：基于槽位的资源分配模型，各槽位间资源使用差异大；

• 无法支持多种计算框架：只支持 MR 任务，无法支持其他计算框架；

Hadoop 2.0 时代：解决了 Hadoop 1.0 时代中 HDFS 和 MR 中存在的问题：

• YARN (MR v2) 在 MR v1 的基础上发展而来，将资源管理和任务控制解耦，分别由 Resource Manager 和 ApplicationMaster 负责，是一个两层调度系统；

• Hadoop YARN (Yet Another Resource Negotiator) 支持多种计算框架的统一资源管理平台；

离线调度生态介绍

• 用户逻辑层：数据分析任务、模型训练任务等

• 作业托管层：管理各种类型上层任务

• 分布式计算引擎层：各种针对不同使用场景的计算引擎，例如：MR、Spark、Flink 等

• 集群资源管理层：YARN

• 裸金属层：众多物理节点组成

YARN 面临的挑战

1. 公平性：各租户能够公平的拿到资源运行任务
2. 高性能：高调度吞吐、低调度延迟，保障资源快速流转
3. 高可用：集群要具备很强的容错能力
4. 大规模：单集群规模提升，原生 YARN 单集群仅支持 5K（原生 YARN 5K）
5. 高集群资源利用率
6. 高任务运行质量保障

YARN 整体架构

系统架构

上图为 YARN 架构，主要包含两大角色：

• Resource Manager

  • 整个集群的大脑，负责为应用调度资源，管理应用生命周期；
  • 对用户提供接口，包括命令行接口，API， WebUI 接口；
  • 可以同时存在多个 RM，同一时间只有一个在工作，RM 之间通过 ZK 选主；

• Node Manager

  • 为整个集群提供资源，接受 Container 运行；
  • 管理 Contianer 的运行时生命周期，包括 Localization, 资源隔离，日志聚合等；

YARN 上运行的作业在运行时会访问外部的数据服务，常见的如 HDFS， Kafka 等；在运行结束后由 YARN 负责将日志上传到 HDFS；

任务运行生命周期核心流程

1. Client 获取 ApplicationID，调用 ApplicationClientProtocol #getNewApplication。
2. RM 返回 GetNewApplicationResponse，其中主要包括：ApplicationID、最大可申请资源以及相关配置。
3. Client 将任务运行所需的资源上传至 HDFS 的指定目录下，并初始化 AM 配置，主要构造 ApplicationSubmissionContext （应用 ID、应用名称、所属队列、应用优先级、应用类型、应用尝试次数、运行 AM 所需要的资源等）和 ContainerLaunchContext（容器运行所需的本地资源、容器持有的安全令牌、应用自有的数据、使用的环境变量、启动容器的命令行等）。
4. Client 将 AM 提交至 RM，调用 ApplicationClientProtocol #submitApplication。
5. RM 根据一定的分配策略为 AM 分配 container，并与 NM 通信。
6. NM 启动 AM。
7. AM 从 HDFS 下载本任务运行所需要的资源并进行初始化工作。
8. AM 向 RM 注册和申请资源。ApplicationMasterProtocol # registerApplicationMaster，注册信息包括：AM 所在节点的主机名、AM 的对外 RPC 服务端口和跟踪应用状态的 Web 接口；ApplicationMasterProtocol # allocate，相关信息封装在 AllocateRequest 中包括：响应 ID、申请的资源列表、AM 主动释放的容器列表、资源黑名单、应用运行进度。
9. RM 接受 AM 请求后，按照调度算法分配全部或部分申请的资源给 AM，返回一个 AllocateResponse 对象，其中包括：响应 ID、分配的 container 列表、已完成的 container 状态列表、状态被更新过的节点列表、资源抢占信息（强制收回部分和可自主调配部分）等。
10. AM 获取到资源后与对应的 NM 通信以启动 container， ContainerManagementProtocol # startContainers
11. NM 启动 container。
12. Container 从 HDFS 下载任务运行必要的资源。
13. Container 在运行过程中与 AM 通信及时汇报运行情况。
14. 任务运行完成后 AM 向 RM 注销，ApplicationMasterProtocol # finishApplicationMaster ()。

YARN 核心模块

• Resource Manager
  • 整体架构
  • 主要职责
  • 状态机管理
  • 调度器分析
• Node Manager
  • 整体架构
  • 主要职责
  • 状态机管理
  • 节点健康检测机制

Resource Manager

整体架构

主要职责

总的来说，RM 负责集群所有资源的统一管理和分配，接收各节点汇报信息并按照一定策略分配给各个任务；

• 与客户端交互，处理来自客户端的请求

• 启动和管理 AM，运行失败时自动重试

• 管理所有 NM，接收 NM 的汇报信息并下达管理指令

• 资源管理与调度

  • 将资源按照一定方式组织起来，例如：资源池
  • 将任务按照一定方式组织起来，例如：队列
  • 接收来自各个 AM 的资源请求
  • 按照一定分配策略将资源分配给 AM

状态机管理

RMApp 状态机

• NEW_SAVING: 收到提交的应用程序后，创建 RMAppImpl 对象并将基本信息持久化；

• ACCEPTED：调度器接受该应用程序后所处的状态，任务等待被分配资源；

• RUNNING：任务成功获取到资源并在节点运行

RMAppAttempt 状态机

• SCHEDULED: 通过 Scheduler 合法性检查后所处的状态，开始为该 App 分配资源；

• ALLOCATED_SAVING：收到分配的 Container 后，在持久化完成前所处的状态；

• ALLOCATED：信息持久化完成后所处的状态；

• LAUNCHED：RM 的 ApplicationMasterLauncher 与 NM 通信以启动 AM 时所处的状态；

RMContainer 状态机

• RESERVED: 开启资源预留时，当前节点不能满足资源请求时所处的状态；

• ALLOCATED：调度器分配一个 Container 给 AM；

• ACQUIRED：AM 获取到分配的 Container 后所处的状态；

• EXPIRED: AM 获取到 Container 后，若在一定时间内未启动 Container，RM 会强制回收该 Container;

RMNode 状态机

• DECOMMSIONED: 节点下线后的状态；

• UNHEALTHY：节点处于不健康状态，健康检测脚本异常或磁盘故障；

• LOST：超过一定时间（默认 10 分钟）未与 RM 发生心跳后所处的状态；

调度分析

任务 / 资源组织

• 任务按队列组织
• 节点按 Label 组织

调度流程

YARN 调度流程由心跳触发：

• AM 定期与 RM 保持心跳，并将资源请求记录在 RM 中；

• 触发时机：由节点心跳触发针对此节点的调度；

• 找 Label: 根据节点 Label 找到对应 Lable 下的所有队列；

• 找队列：将队列进行 DRF 排序，找到当前最 “饥饿” 的队列；

• 找应用：将此队列内所有应用按照优先级进行排序 (优先级由用户提交时指定), 找到优先级最高的应用，优先级相同时按 DRF 算法排序；

• 找资源请求：将此应用内的所有资源请求按照优先级排序 (优先级由计算引擎指定), 找到优先级最高的资源请求进行资源分配；

典型调度器对比

	Fair Scheduler	CapacityScheduler
目标	提供一种多租户资源分配方法，提高集群资源利用率减小集群	管理成本
设计思想	基于最大最小公平算法分配资源	资源按比例分配给各队列，并添加各种限制
是否支持动态加载配置	是	是
是否支持负载均衡	是	否
Container 请求资源粒度	最小资源量的整数倍	专门的内存规整化参数控制，粒度更小
本地性任务调度优化	基于跳过次数的延迟调度	基于跳过次数的延迟调度
队列间资源分配方式	Fair、FIFO、DRF	资源使用率低者优先
队列内部资源分配方式	Fair、FIFO、DRF	FIFO 、DRF

Node Manager

整体架构

主要职责

总的来说，NM 是节点代理，从 AM 接受命令（启停 Container）并执行，通过心跳方式向 RM 汇报节点状态并领取命令（清理 Container）。

• 与 RM 交互

  • 心跳汇报节点健康状况和 Container 运行状态；
  • 领取 RM 下达的命令；

• 与 AM 交互

  • 启动容器
  • 停止容器
  • 获取容器状态

状态机管理

Application

• INITING: Application 初始化状态，创建工作目录和日志目录；

• FINISHING_CONTAINERS_WAIT：调等待回收 Container 所占用的资源所处的状态；

• APPLICATION_RESOURCE_CLEANINGUP：Application 所有 Container 占用的资源被回收后所处的状态；

Container

• LOCALIZING: 正在从 HDFS 下载依赖的资源；

• EXITED_WITH_SUCCESS：Container 运行脚本正常退出执行；

• CONTAINER_CLEANUP_AFTER_KILL：Container 被 kill 后所处的状态；

LocalizedResource

• DOWNLOADING: 资源处于下载状态；

• LOCALIZED：资源下载完成；

• FAILED：资源下载失败；

节点健康检查机制

节点健康检测机制是 NM 自带的健康状况诊断机制。通过该机制 NM 可时刻掌握自己健康状况并及时汇报给 RM，RM 根据 NM 健康情况决定是否为其分配新任务。

• 自定义 Shell

  • NodeHealthScriptRunner 服务周期性执行节点健康状况检测脚本；
  • 若输出以 “ERROR” 开头，节点处于 unhealthy 状态并随心跳上报给 RM，RM 拉黑节点并停止分配新任务；
  • 脚本一直执行，一旦节点变为 healthy 状态，RM 会继续为该节点分配新任务；

• 检测磁盘损坏数目

  • LocalDirsHandlerService 服务周期性检测 NM 本地磁盘好坏，一旦发现正常磁盘比例低于一定阈值则节点处于 unhealthy 状态；
  • NM 判断磁盘好坏的标准：如果一个目录具有读、写和执行权限，则目录正常；

重要机制

YARN 如何保证公平性？

考虑如下工业界场景：某互联网公司有 5000 台服务器，但是有很多业务部门，每个业务部门下又有很多员工，每个员工又有不同数量和规模的任务需要运行。如何进行调度，在保证各业务部门、各员工能够公平拿到资源的同时提高集群整体资源利用率？

公平性保障

Fair Share 调度策略背景

为什么需要 Fair Share 调度策略？

• 保障公平的前提下实现队列间资源共享，提高资源利用率
• 缓解繁忙队列压力

什么是 Fair Share 调度策略？

• 队列配置 minShare 和 maxShare，当队列空闲时按照一定策略将资源分配给其他活跃队列；

Fair Share 类型

• Steady Fair Share
• Instantaneous Fair Share

两种 Fair Share 定义

• Steady Fair Share: TotalResource * S.weight
• Instantaneous Fair Share:
  • 定义
    • 所有队列 Fair Share 之和 <= TotalResource;
    • S.minShare <= Fair Share <= S.maxShare；
  • 目标
    • 找到一个 R 使其满足：
    • R * （All S.wieght）<= TotalResource;
    • S.minShare <= R * S.weight <= S.maxShare;
  • 结果
    • 若 S.minShare > R * S.weight， Fair Share = S.minShare
    • 若 S.maxShare < R * S.weight，Fair Share = S.maxShare
    • 其他 Fair Share = R * S.weight

Fair Share 计算逻辑

• 计算 Total Resource

• 初始化 R 上限 RMax

  • 获取所有 non-fixed Schedulable 的 maxShare
  • 初始化 R 为 1，每次翻倍
  • 直到所有 Schedulable 分完所有资源

• 通过二分法寻找 R [0,RMax]

  • mid = (left + right) / 2.0
  • 若 plannedResourceUsed == totalResource，right = mid；
  • 若 plannedResourceUsed < totalResource，left = mid；
  • 若 plannedResourceUsed > totalResource，right = mid；

• 计算 Fair Share

  • 若 S.minShare > right * S.weight, Fair Share = S.minShare;
  • 若 S.maxShare < right * S.weight, Fair Share = S.maxShare;
  • 其他情况 Fair Share = right * S.weight

DRF (Dominant Resource Fair) 调度策略

为什么需要 DRF 调度策略？

• 在保证公平性的前提下进行资源降维，以达到更好的分配效果；

什么是 DRF 调度策略？

• DRF 是最大最小公平算法在多维资源上的具体实现；

• 旨在使不同用户的 “主分享量” 最大化的保持公平；

最大最小公平算法：最大化最小资源需求的满足度

• 资源按照需求递增的顺序进行分配；

• 用户获取的资源不超过自身需求；

• 对未满足的用户，等价分享剩余资源；

例如下面场景：A B C D 四个用户的资源需求分别是 2、2.6、4、5 份，现在总共有 10 份资源，首先将所有资源均分，每个用户得到 2.5 份资源。对于 A 用户多分配 0.5 份，继续将这 0.5 份资源平均分配给 B C D，B 用户得到 2.666 份资源。会继续将 B 多分配的 0.066 份资源平均分配给 C 和 D。

DRF 调度策略描述

• 场景：系统有 <9CPU, 18G>，A 每个任务需要 <1CPU，4G>，B 每个任务需要 <3CPU，1G>，对于 A 因为：1/9 < 4/18，所以 A 任务的主资源是内存，B 任务的主资源是 CPU；

• 数学模型：一定约束条件下的最优化问题，下面 x 代表 A 任务的个数，y 代表 B 任务的个数

  • 最大化资源分配 max (x,y)
  • 约束条件：
    • （x+3y）<=9 (CPU 约束);
    • (4x+y)<= 18（内存约束）;
    • 4x/18 == 3y/9（主资源公平约束）;

• 最终计算得到： x=3,y=2

DRF 调度策略计算逻辑

R 表示总资源量，有 m 个维度

C 已经使用的资源量

si 用户 i 的 “主分享量”

Ui 分配给用户 i 的资源量

• 选择最小 “主分享量” 用户 i

• Di 用户 i 下一个任务资源需求量

• 若资源充足

  • 更新已使用资源量
  • 更新用户 i 的已分配资源量
  • 更新用户 i 的 “主分享量”

高性能保障

状态机管理

• 状态机由一组状态（初始状态、中间状态和最终状态）组成，状态机从初始状态开始运行，接收一组特定事件，经过一系列中间状态后，到达最终状态并退出；

• 每种状态转换由一个四元组表示：转换前状态、转换后状态、事件和回调函数；

• YARN 定义了三种状态转换方式如下所示：

事件处理模型

YARN 采用了基于事件驱动的并发模型，具有很强的并发性可提高系统性能。

• RM 中所有处理请求都会作为事件进入系统；

• AsyncDispatcher 负责传递事件给相应事件调度器 --EventHandler；

• 事件调度器可能将该事件转发给另外一个事件调度器或带有有限状态机的事件处理器；

• 处理结果也以事件形式输出，新事件会再次被中央异步调度器转发给下一个事件调度器，直至处理完成。

高可用保障

RM 高可用

热备方案：集群中存在一个对外服务的 Active Master 和若干 Standby Master，一旦 Active Master 故障，立即采取一定策略选取某个 Standby Master 转换为 Active Master 正常对外提供服务；

基于共享存储的 HA 解决方案：Active Master 不断将信息写入共享存储系统（ZK）, 故障切换时 Standby Master 从共享存储恢复数据，待信息完全同步后切换至 Active Master;

两种切换模式：

• 手动模式：使用 “yarn rmadmin” 命令将现在的 Active Master 切换为 Standby 并选择一个 Standby 切换为 Active Master；

• 自动模式：使用 ZK 的 ActiveStandbyElector 进行选主操作，ZK 中有一个 /yarn-leader-election/yarn1 的锁节点，所有 RM 在启动时去竞争写一个 Lock 子节点：/yarn-leader-election/yarn1/ActiveBreadCrumb，该节点是临时节点。ZK 保证最终只有一个 RM 能够创建成功，创建成功的为 Active Master;

Client 、 AM、NM 自动重试：切主时各组件基于配置文件中的所有 RM 采用 round-robin 轮询方式不断尝试连接 RM 直到命中 Active Master；

NM 高可用

• 相关信息存储至 leveldb 数据库；

• NM 重启时加载 yarn-nm-recovery 下的 leveldb 数据库；

公司实践

Gang 调度器

为什么要开发 Gang 调度器？

原生 YARN 的架构设计目标专注在离线 Batch 类计算作业上面，对于高吞吐追求极致，但是对于 latency 和全局约束上没有很好支持。流式 / 模型训练任务的出现，需求与 Batch 类相差较大， 当前 YARN 的架构已经无法很好的满足这部分任务。流式作业和训练作业的调度需求与批处理有很大的不同：批处理强调高吞吐，而流式 / 训练类型作业更强调低延迟和全局视角；目前 Flink 作业和模型训练类的作业在 YARN 上面运行， 在调度层面都遇到三个问题:

1. 调度缺乏全局视角

   1. 由于 YARN 的调度以 NM 心跳触发，各个心跳彼此独立，因此没有全局的视角；
   2. 目前为了达到尽量全局的视角，目前有两种应对方法:
      • YARN 管理员增加了一些单个节点的过滤条件，在尝试若干个节点后再放宽过滤条件；
      • 应用 AM 向 YARN 申请尽可能多的资源，经过自己的筛选后再释放掉不符合预期的资源；

2. 单个 Application 调度过慢

   1. 由于 YARN 架构设计是全异步的，由 NM 的心跳触发调度，即使整个集群有闲置资源也需要等待心跳才能进行分配；
   2. 由于 AM 的申请也是异步的， 导致 AM 至少需要两次心跳才能得到想要申请的资源 (第 1 次只是提出申请，第 2 次能拿到两次心跳之间已经调度分配的 container)；

3. Application 之间存在资源互锁情况

   1. YARN 支持多个应用按 share 同时分配资源，导致部分请求存在互锁的情况，即:
      • 假设整个集群目前有 15 个核，A 作业和 B 作业都需要 10 个核才能运行，但是 A 申请到了 7 个，B 申请了 8 个，最终 A 和 B 都无法启动，并且这些资源也无法被其它人使用；
      • 这种情况在资源稀缺 (如 GPU) 时会表现得特别明显；

Gang 调度器有什么典型特点？

• 全局视角：增加 YARN 调度时的全局视角

  • 首先支持 Flink/GPU 训练的全局约束需求 (负载均衡 / GPU 亲和性)
  • 为未来更丰富的全局约束留出扩展空间

• 低延迟:

  • 对于低 latency 需求的申请，在集群可以满足资源的条件时，1 次申请直接返回资源 (ms 级别)。

• Gang 性交付:

  • 调度提供 all-or-nothing 的语义， 对于无法满足的申请直接返回失败， 对于可以满足的申请直接交付所有的申请资源，规避应用之间资源互锁的情况。

Gang 调度流程

• 选择 App

  • 基于公平性策略对所有队列排序并选择一个队列；
  • 基于公平性策略对队列内的任务排序并选择一个任务；

• 分配资源

  • 强约束阶段：过滤掉不符合条件的节点
  • 弱约束阶段：选择合适的节点分配资源（不排序，时间复杂度 O (n)）
    • Quota 平均：分配后节点已使用资源尽可能平均。总请求资源为 V1，总节点数为 N，已用资源为 U，节点目标资源为：$S=(V1+U)/N$，遍历所有节点，每个节点分配 S - Un 即可；
    • 跳过高 load 节点：优先往低 load 节点调度。满足 load 阈值节点 N1，不满足 N2，优先把 N1 剩余资源分配完，分配后未满足资源量为 V2，每个节点分配 V2/N2;
    • 兜底分配

Gang Scheduler 调度与原生调度 Fair Scheduler 的关系

• 两个调度器会并存在 RM 中，当用户可以配置使用，默认使用原生调度器 (Fair Scheduler)

• Gang Scheduler 不是一个完整的 Scheduler，它只负责决定哪个 container 被分配到哪台机器上，不负责完整的 container 生命周期管理，这些管理工作依然由 Fair Scheduler 负责

• 两种调度模式在调度资源时会争抢 Node 级别的锁，各自调度。

反调度器

为什么需要开发反调度器？

• 调度器的调度决策受 “时空” 限制

  • 在目前系统中，当有资源请求到来时，调度器只根据资源请求内容和当前时刻集群状态信息做出正确的调度决策，一旦资源请求与空闲资源匹配完成则本次调度过程结束，调度器不会维护当前资源请求下任务和集群的后续状态信息。因此，调度器的调度决策受 “时空” 限制。

  • “时” 表示触发调度时的时刻

  • “空” 表示触发调度时集群的状态。

• 任务运行和集群状态高动态性

  • 在大规模集群中，任务运行过程和集群状态具有高动态性。对于任务来说，其资源使用量会伴随着请求流量的变化而不断波动。
  • 对于集群来说，随着任务调度过程的持续进行、集群节点的添加和故障、集群节点标签的改变等，集群状态每时每刻都在发生变化。

• 需要持续保证最初调度决策的正确性

  • 任务配置的调度约束在运行过程中需要持续被满足

反调度流程

• 根据 AM 请求中的强约束，构造强约束集；

• 遍历强约束集选择不再符合强约束条件的节点；

• 遍历异常节点下的 Container，针对每个节点选择需要进行反调度的 Container，并添加至反调度 Container 列表中；

• 将反调度 Container 列表随心跳返回给对应 AM；

反调度器与 Gang 调度器关系

反调度器与 Gang 调度器关系：是 Gang 调度器的 “伴侣”

• 两者不同点

  • 发挥作用的时机不同。调度器在资源请求到来时根据当前时刻集群信息进行资源分配。反调度器在任务运行过程中，检测出不再正确的调度决策并进行修正。
  • 处理机制相反。调度器负责根据调度策略分配 container 到计算节点。反调度器负责根据反调度策略清理计算节点上的 container。

• 两者联系

  • 反调度器是调度器的修正和补充，在反调度器的恢复过程中需要通过调度器进行新 container 的申请，两者共同促进资源的合理分配。

单集群 50K 突破

为什么需要提升单集群规模？

• 更好的资源池化和资源共享

  • 资源池更大，有利于资源的分时复用和共享；
  • 资源高效共享可以提高集群整体资源利用率；

• 降低运维成本

  • YARN 原生系统单集群仅支持 5K 节点；
  • 每多一个集群，运维负担就会加重；

提升单集群规模有哪些瓶颈点？

• RPC 层：接收请求、处理请求、返回结果
  • RPC 处理时间 5ms，handler 默认 80 线程，消费吞吐约 16K/s，RPC server queue 容易打满
• Dispatcher 层：将事件传递给对应的事件调度器
  • 生产速率过大，AsyncDispatcher queue 容易 pending
  • 消费速率过低，Scheduler 的 NODE_UPDATE 事件处理过慢
• Scheduler 层：真正调度
  • FSLeafQueue 分配单 Container 延迟太高，存在空转

心跳反压机制

心跳反压机制：将 NM 节点的心跳机制改为根据 RM 的压力动态调整 ，当事件池中的事件超过阈值时调大心跳周期，当事件池中的事件小于阈值时调小心跳周期

多线程调度

• 多线程调度：收到调度事件后，对节点按 hashcode 放到对应的 scheduler queue 即返回

其他优化

• 事件精简：对 YARN 内部事件梳理调整，精准修改了一些事件处理逻辑

• 空转优化：调度时过滤不需要资源的 App，减少空转

• 内存单位优化：修改内存单位 (int->long) 突破单个集群 21 亿 MB 限制

• 切主优化：通过对切主过程进行深度优化，将切主时间控制在秒级