前言

《云原生王者之路集训营》是华为云云原生团队精心打磨的云原生学习技术公开课，分为黄金、钻石、王者三个阶段，帮助广大技术爱好者快速掌握云原生相关技能。本课程为黄金课程的第三课，由容器基础设施团队，容器批量计算架构师William Wang主讲，为大家深入讲解Kubernetes调度流程原理以及典型调度算法。

目标学员：计算机、软件工程等专业的大学生，涉及Kubernetes、Istio等技术的应用开发者，其他的云原生技术兴趣爱好。学完本课程后，您将能够：了解Kubernetes调度器的工作原理及典型的调度算法；理解常见的Kubernetes的高级调度特性；理解华为云 Volcano 的典型批量调度算法。

一 kubernetes scheduling

1.1 kubernetes调度模式

调度器是主节点上的组件，该组件监视那些新创建的未指定运行节点的 Pod，并选择节点让 Pod 在特定Node上面运行。

1.2 kubernetes default schedule 特点

kube-scheduler 是 Kubernetes 集群的默认调度器，并且是集群控制面的一部分，kube-scheduler 在设计上是允许用户自己编写调度组件并替换原有的 kube-scheduler。

对每一个新创建的 Pod 或者是未被调度的 Pod，kube-scheduler 会选择一个最优的 Node 去运行这个 Pod。然而，Pod 内的每一个容器对资源都有不同的需求，而且 Pod 本身也有不同的资源需求。因此，Pod 在被调度到 Node 上之前，根据这些特定的资源调度需求，需要对集群中的 Node 进行一次过滤。

在一个集群中，满足一个 Pod 调度请求的所有 Node 称之为 可调度节点。如果没有任何一个 Node 能满足 Pod 的资源请求，那么这个 Pod 将一直停留在未调度状态直到调度器能够找到合适的 Node。

调度器先在集群中找到一个 Pod 的所有可调度节点，然后根据一系列函数对这些可调度节点打分，然后选出其中得分最高的 Node 来运行 Pod。之后，调度器将这个调度决定通知给 kube-apiserver，这个过程叫做绑定。

在做调度决定时需要考虑的因素包括：单独和整体的资源请求、硬件/软件/策略限制、亲和以及反亲和要求、数据局域性、负载间的干扰等等。

1.3 调度框架和调度流程

1.  Informer list/watch资源变化，更新queue和cache;NextPod()从待调度队列获取队首的Pod;
2.  从cache中获取Node列表;
3.  针对Pod和NodeList执行Predicate算法,过滤掉不合适的节点;
4.  针对Pod和NodeList执行Priority算法,给节点打分;
5.  根据打分，计算出得分最高的节点;
6.  当高优先级的Pod没有找到合适的节点时,调度器尝试为其抢占优先级低的Pod;
7.  当调度器为Pod选择了一个合适的节点时,通过Bind将Pod和节点进行绑定;

通过cache机制可以对在进行执行Predicate的时候提升效率。

在节点绑定bind操作不是这直接操作apiserver的bind，而是在缓存至执行bind操作node的pod信息。之后启动golang的协程异步向apiserver发请求，这种机制可以大大加快调度器处理pod的速度和效率。

1.3 调度策略与算法

• Predicates，筛选不合格的节点。

预选阶段：排除完全不符合运行这个 POD 的节点、例如资源最低要求、资源最高限额、端口是否被占用。

• Priorities

优选阶段：基于一系列的算法函数计算出每个节点的优先级，按照优先级排序，取得分最高的 node。

选中阶段：如果优选阶段产生多个结果，那么随机挑选一个节点。

优选：调度器会为 Pod 从所有可调度节点中选取一个最合适的 Node。根据当前启用的打分规则，调度器会给每一个可调度节点进行打分。最后，kube-scheduler 会将 Pod 调度到得分最高的 Node 上。如果存在多个得分最高的 Node，kube-scheduler 会从中随机选取一个。

优先级选项包括：

• LeastRequestedPriority ：通过计算 CPU 和 Memory 的使用率来决定权重，使用率越低权重越高。换句话说，这个优先级指标倾向于资源使用比例更低的节点 ；
• BalancedResourceAllocation ：节点上 CPU 和 Memory 使用率越接近，权重越高。这个应该和上面的一起使用，不应该单独使用；
• ImageLocalityPriority ：倾向于已经有要使用镜像的节点，镜像总大小值越大，权重越高

通过算法对所有的优先级项目和权重进行计算，得出最终的结果。

二 Kubernetes的高级调度特性

2.1 kubernetes中的Label，selector机制

kubernetes中的Label，selector机制通常用于对Pod进行过滤，分离和筛选。

任意的metadata，所有API对象都有Label，通常用来标记“身份”，可以查询时用selectors过滤

类似SQL 'select .. where... '

Label是kubernetes系统中的一个重要概念。它的作用就是在资源上添加标识，用来对它们进行区分和选择。Label的特点:

一个Label会以key/value键值对的形式附加到各种对象上，如Node、Pod、Service等等。

一个资源对象可以定义任意数量的Label，同一个Label也可以被添加到任意数量的资源对象上去。

Label通常在资源对象定义时确定，当然也可以在对象创建后勃态添加或者删除。

可以通过Label实现资源的多维度分组，以便灵活、方便地进行资源分配、调度、配置、部署等管理工作。

• Label用于给某个资源对象定义标识
• Label Selector用于查询和筛选拥有某些标签的资源对象

App:标识app的名称

Phase：表示运行环境

Role：表示角色

可以通过App，Role进行组合进行pod的调度。

2.2 Node Affinity

希望pod可以调度到一些特定的节点上，有些node支持gpu或性能比较好。通过selector机制，可以将pod运行在某些选定的节点上。

2.3 Pod Affinity

POD 和 POD 出于高效的通信这种需求，所以需要将 POD 和 POD 组织在同一台机器，同一个机房，例如：LNMT 如果能运行在同一个主机上更好。想把一组 POD 运行在一起，使用节点亲和性就可以实现，为了达成这个目的，我们需要：把节点标签精心编排，希望在一起运行的 POD，就使用同一组标签选择器来选择节点，这种方式需要管理节点标签和 POD 亲和性才能做到。

想把一组 POD 运行在一起，使用 POD 亲和性，我们可以设置 POD 对某个 POD 的亲和性，那么比如：LNMT，那么 MySQL 和 Tomcat 可以设置为更加亲和 Ngninx 所在的主机或机柜，所以必须有个前提就是 POD 和 POD 怎么才是最近的，这个标准是什么，也就是什么是同一位置，怎么才能知道 node 和 node 是在一个机柜。所以可以为同一个机柜的 node 节点打上相同的标签。

MySQL 和 Tomcat 一定不能和 Nginx 运行在一起，这就是反亲和性。

•  POD 对其他 POD 的亲和性，

详见：kubectl explain pods.spec.affinity.podAffinity

podAffinity                <Object>                              # POD 对其他 POD 的亲和性
  preferredDuringSchedulingIgnoredDuringExecution  <[]Object>    # 软性亲和性，尽量满足亲和性
    podAffinityTerm        <Object>                              # 亲和的 POD 对象
      labelSelector        <Object>                              # 标签选择器对象列表
        matchExpressions   <[]Object>                            # 标签选择器对象，选 POD 标签
          key              <string>                              # 标签
          operator         <string>                              # 操作：比较
          values           <[]string>                            # 值
        matchLabels        <map[string]string>                   # 集合标签选择器
      namespaces           <[]string>                            # 名称空间的列表
      topologyKey          <string>                              # 亲和判断条件
    weight                 <integer>                             # 权重 1 - 100
  requiredDuringSchedulingIgnoredDuringExecution   <[]Object>    # 硬性亲和性，不满足则 Pending
    labelSelector          <Object>                              # 标签选择器对象列表
      matchExpressions   <[]Object>                              # 标签选择器对象，选 POD 标签
        key              <string>                                # 标签
        operator         <string>                                # 操作：比较
        values           <[]string>                              # 值
      matchLabels        <map[string]string>                     # 集合标签选择器
    namespaces             <[]string>                            # 名称空间的列表
    topologyKey            <string>                              # 亲和判断条件

如上图，serivce：A需要调度到与service：B相同zone的toplogyKey中，可以看到node2和node3均为zone：central，由于Node2资源不足，所以service：A被调度到Node3上。

将topologyKey改成hostname，也就是希望service：A运行在与service：B同一个node上面，但是node2由于资源不足，所以service：A也就无法完成调度。

2.4 Taints-tolerations

Taint需要与Toleration配合使用，让pod避开那些不合适的node。在node上设置一个或多个Taint后，除非pod明确声明能够容忍这些“污点”，否则无法在这些node上运行。Toleration是pod的属性，让pod能够（注意，只是能够，而非必须）运行在标注了Taint的node上。Node反亲和配置。

• tains

taints          <[]Object>     # 污点对象列表
  effect        <string>       # 当 POD 不能容忍这个污点的时候，要采取的行为，也就是排斥不容忍污点的 POD
    NoSchedule                 # 影响调度过程，但是已经调度完成 POD 无影响
    PreferNoSchedule           # 影响调度过程，尝试驱逐调度已经完成的但不容忍新污点的 POD
    NoExecute                  # 新增的污点，影响新的调度过程，且强力驱逐调度已经完成的但不容忍新污点的 POD
  key           <string>       # 键
  timeAdded     <string>       #
  value         <string>       # 值

• tolerations

tolerations            <[]Object>    # 容忍度对象
  effect               <string>      # 能否容忍 node 上的污点驱逐策略，为空表示容忍任何驱逐策略
    NoSchedule                       # 能容忍 node 污点的 NoSchedule
    PreferNoSchedule                 # 能容忍 node 污点的 PreferNoSchedule
    NoExecute                        # 能容忍 node 污点的 NoExecute
  key                  <string>      # 污点的键
  operator             <string>      # Exists 污点存在不管什么值，Equal 污点的值必须等值
  tolerationSeconds    <integer>     # 容忍时间，即如果被驱逐，可以等多久再走，默认 0 秒，NoExecute 使用
  value                <string>      # 污点的值

可以看到这个pod可以调度到node1/node2/node3上，假如现在调度到node1上。

现在再来一个pod，如果需求GPUs，但是node1上已经有pod了。

该场景就非常适合taint-toleratation，此时可以在node1上面可以打上GPU的PreferBlockScheduling。

可以在为Node上面配置一个软性taint，尽量排斥没有对应toleration的Pod，此时在打分阶段可以选择满足条件的pod。

也可以在pod上面打上一个硬性的toleration，能够容忍key为GPU，effect为NoSchedule，此时就可以pod调度到Node1上。

三 华为云 Volcano 的典型批量调度算法

3.1 云计算批量计算面临的挑战

3.1.1 作业管理缺失

1. Pod级别调度，无法感知.上层应用
2. 缺少作业概念、缺少完善的生命周期的管理
3. 缺少任务依赖、作业依赖支持

3.1.2 调度策略局限

1. 不支持Gang-Scheduling、 Fairshaing scheduling
2. 不支持多场景的Resource reservation, backfill
3. 不支持CPU/O topology based scheduling

3.1.3 领域计算框架支持不足

1. 1:1的operator部署运维复杂
2. 不同框架对作业管理、并行计算等要求不同
3. 计算密集，资源波动大，需要高级调度能力

3.1.4 资源规划复用、异构计算支持不足

1.  缺少队列概念
2.  不支持集群资源的动态规划以及资源复用
3.  对异构资源支持不足
   

3.2 Volcano帮助批量计算面对云原生的各种挑战

1. 业界首个云原生批量计算平台.
2. 2019年6月.上海KubeCon正式开源
3. 2020年4月成为CNCF官方项目
4. 2021年3月发布1.2版本
5. 每3个月一个特性版本，最新版本v1.2.0 
6. 社区活跃度:

• • a.1.7k star, 300+ fork, 150+贡献者
  • b.5 Maintainer, 8 Reviewer
  • c.30家企业、科研机构

3.3 Volcano 总体架构和优势

3.3.1 总体架构

3.3.2 优势

1. 高性能:提供队列调度、优先级调度、抢占、装箱、资源预留、拓扑调度等丰富的调度策略，在多种场景下提升应用性能
2. 智能混合调度:支持在线、离线混合部署调度，提高整体资源利用效率
3. 应用感知:感知应用类型和特点，针对大数据、Al、HPC负载提供完善的生命周期
4. 集群联邦调度:支持多集群调度和作业分发，满足效率优先、成本优先等不同的场景诉求
5. 大规模:支持大规模集群调度，单集群规模支持1w节点，100w容器
6. 高扩展:插件化算法集成框架，提供两级插件扩展，方便二次开发，满足不同场景诉求
7. 易运维: Volcano作业提供统一 接口，避免过多Operator带来的繁杂管理
8. 社区成熟: CNCF首个批量计算平台，已支持众多的主流AI、大数据、高性能计算框架，众多用户已应用于生产环境

Volcano是一个基于Kubernetes的批处理平台，提供了机器学习、深度学习、生物信息学、基因组学及其他大数据应用所需要而Kubernetes当前缺失的一系列特性。

Volcano源自于华为云高性能批量计算解决方案，在支撑华为云一站式AI开发平台ModelArts、云容器实例CCI等服务稳定运行中发挥重要作用。Volcano提供了高性能任务调度引擎、高性能异构芯片管理、高性能任务运行管理等通用计算能力，通过接入AI、大数据、基因、渲染等诸多行业计算框架服务终端用户。(目前Volcano项目已经在Github开源)

3.4 典型的调度算法

1. Gang-scheduling：运行批处理作业（如Tensorflow/MPI）时，必须协调作业的所有任务才能一起启动；否则，将不会启动任何任务。如果有足够的资源并行运行作业的所有任务，则该作业将正确执行； 但是，在大多数情况下，尤其是在prem环境中，情况并非如此。在最坏的情况下，由于死锁，所有作业都挂起。其中每个作业只成功启动了部分任务，并等待其余任务启动。
2. SLA:当集群资源不足时候，如果还持续的在集群中提交大作业或者小作业，会导致集群的压力巨大，SLA调度算法运行用户为优先级高的作业配置一个最长等待时间，等待时间到了后，系统就会为大作业进行集群资源的预留，直到这个大作业能成功运行，从而解决大作业被饿死的情况。
3. TDM：基于时分复用的调度算法，用户可以配置哪些时间段，或者哪些资源在这个时间段可以去share出来，供批处理任务来使用，可以有效提升资源利用率。
4. Preempt & Reclaim：通过公平分享来支持借贷模型，一些作业/队列在空闲时会过度使用资源。但是，如果有任何进一步的资源请求，资源“所有者”将“收回”。 资源可以在队列或作业之间共享：回收用于队列之间的资源平衡，抢占用于作业之间的资源平衡。
5. DRF：目前的公平调度是基于DRF，并通过 plugin 插件来实现。在 OpenSession 中会先计算每个作业的 dominant resource和每个作业share的初始值；然后注册 JobOrderFn回调函数，JobOrderFn 中接收两个作业对象，并根据对像的 dominant resource 的 share值对作业进行排序；同时注册EventHandler, 当Pod被分配或抢占资源时，drf根据相应的作业及资源信息动态更新share值。
6. FairShare：

不同namespace的资源可以提交到不同的queue，同一个namespace的资源也可以提交到同一个queue。

• queue中不同job直接的公平调度。
• namespace级别的公平调度。
• queue和queue之间的公平调度。
• Task- Topology：

3个作业的执行时间总和;每个作业带2ps + 4workers

默认调度器执行时间波动较大。

执行时间的提高量依据数据在作业中的比例而定。

减少Pod Affinity/Anti- Affinity,提高调度器的整体性能。

7. MinResource：

• Spark driver和executor pod竞争节点资源，overcommit情况下引发死锁。
  
• 通过为Driver pod和Executor Pod静态划分Dedicated节点解决，存在碎片率问题。
  
• 通过为PodGroup预留minResource,防止OverCommit,合理规划并行度，解决资源竞争导致的死锁问题。
• 无需静态规划专有节点，减少资源碎片，相对于静态规划专有节点方案，性能提升30%+。

总结

本节课重点介绍kubernetes的调度算法及高级调度特性，以及华为云volcano的典型调度算法。

未来，华为云也将基于云原生技术持续创新，助力繁荣云原生生态，让各行各业走向快速智能发展之路。将极大促进Volcano上下游社区生态构建及合作，吸引广大云原生企业用户深度参与，Volcano将在企业数字化、云原生转型过程中发挥越来越重要的作用，华为云也将在云原生领域持续耕耘、持续引领创新、繁荣生态，助力各行业走向快速智能发展之路。

本文整理自华为云社区【内容共创】活动第13期。

https://bbs.huaweicloud.com/blogs/330939

任务20.华为云云原生钻石课程03：Kubernetes高级调度器原理详解