一. 简介

在 Kubernetes 项目中，默认调度器（default scheduler）的主要职责，就是为一个新创建出来的 Pod，寻找一个最合适的节点（Node）。
而这里“最合适”的含义，包括三层：

从集群所有的节点中，根据调度算法挑选出所有可以运行该 Pod 的节点。
从第一步的结果中，再根据调度算法挑选一个最符合条件的节点作为最终结果。
当一个高优先级的 Pod 调度失败后，该 Pod 并不会被“搁置”，而是会“挤走”某个 Node 上的一些低优先级的 Pod 。

所以在具体的调度流程中，默认调度器会首先调用一组叫作 Predicate 的调度算法，来检查每个 Node。然后，再调用一组叫作 Priority 的调度算法，来给上一步得到的结果里的每个 Node 打分。最终的调度结果，就是得分最高的那个 Node。如果出现资源竞争，那就需要通过 Preemption 的抢占机制来进行调度。

二. Predicates

2.1 定义

Predicates 在调度过程中的作用，可以理解为 Filter，即：它按照调度策略，从当前集群的所有节点中，“过滤”出一系列符合条件的节点。这些节点，都是可以运行待调度 Pod 的宿主机。

2.2 过滤规则

2.2.1 GeneralPredicates

GeneralPredicates 负责的是最基础的调度策略。比如，PodFitsResources 计算的就是宿主机的 CPU 和内存资源等是否够用。
PodFitsResources 检查的只是 Pod 的 requests 字段。Kubernetes 的调度器并没有为 GPU 等硬件资源定义具体的资源类型，而是统一用一种名叫 Extended Resource 的、Key-Value 格式的扩展字段来描述的。
像上面这样一组GeneralPredicates，正是 Kubernetes 考察一个 Pod 能不能运行在一个 Node 上最基本的过滤条件。所以，GeneralPredicates 也会被其他组件（比如 kubelet）直接调用。

2.2.2 Volume 相关的过滤规则

这一组过滤规则负责的是跟容器持久化 Volume 相关的调度策略。其中，NoDiskConflict 检查的条件，是多个 Pod 声明挂载的持久化 Volume 是否有冲突。比如，AWS EBS 类型的 Volume，是不允许被两个 Pod 同时使用的。所以，当一个名叫 A 的 EBS Volume 已经被挂载在了某个节点上时，另一个同样声明使用这个 A Volume 的 Pod，就不能被调度到这个节点上了。

2.2.3 宿主机相关的过滤规则

这一组规则主要考察待调度 Pod 是否满足 Node 本身的某些条件。比如，PodToleratesNodeTaints，负责检查的就是我们前面经常用到的 Node 的“污点”机制。只有当 Pod 的 Toleration 字段与 Node 的 Taint 字段能够匹配的时候，这个 Pod 才能被调度到该节点上。

2.2.4 Pod 相关的过滤规则

这一组规则跟 GeneralPredicates 大多数是重合的。比较特殊的，是 PodAffinityPredicate。这个规则的作用，是检查待调度 Pod 与 Node 上的已有 Pod 之间的亲密（affinity）和反亲密（anti-affinity）关系。

2.3 小结

在具体执行的时候，当开始调度一个 Pod 时，Kubernetes 调度器会同时启动 16 个 Goroutine，来并发地为集群里的所有 Node 计算 Predicates，最后返回可以运行这个 Pod 的宿主机列表。
同时，为每个 Node 执行 Predicates 时，调度器会按照固定的顺序来进行检查。这个顺序，是按照 Predicates 本身的含义来确定的。

三. Priorities

3.1 定义

在 Predicates 阶段完成了节点的“过滤”之后，Priorities 阶段的工作就是为这些节点打分。这里打分的范围是 0-10 分，得分最高的节点就是最后被 Pod 绑定的最佳节点。

3.2 打分规则

3.2.1 LeastRequestedPriority

LeastRequestedPriority 是 Priorities 里最常用到的一个打分规则。
公式如下：

score = (cpu((capacity-sum(requested))10/capacity) + memory((capacity-sum(requested))10/capacity))/2

可以看到，这个算法实际上就是在选择空闲资源（CPU 和 Memory）最多的宿主机。

3.2.2 BalancedResourceAllocation

公式如下：

score = 10 - variance(cpuFraction,memoryFraction,volumeFraction)*10

其中，每种资源的 Fraction 的定义是：Pod 请求的资源 / 节点上的可用资源。而 variance 算法的作用，则是计算每两种资源 Fraction 之间的“距离”。而最后选择的，则是资源 Fraction 差距最小的节点。

可以看出，BalancedResourceAllocation 选择的，其实是调度完成后，所有节点里各种资源分配最均衡的那个节点，从而避免一个节点上 CPU 被大量分配、而 Memory 大量剩余的情况。

3.2.3 ImageLocalityPriority

ImageLocalityPriority 是在 Kubernetes v1.12 里新开启的调度规则，即：如果待调度 Pod 需要使用的镜像很大，并且已经存在于某些 Node 上，那么这些 Node 的得分就会比较高。

为了避免这个算法引发调度堆叠，调度器在计算得分的时候还会根据镜像的分布进行优化，即：如果大镜像分布的节点数目很少，那么这些节点的权重就会被调低，从而“对冲”掉引起调度堆叠的风险。

3.2.4 Others

NodeAffinityPriority 、 TaintTolerationPriority 和 InterPodAffinityPriority 这三种 Priority。
它们与 PodMatchNodeSelector、PodToleratesNodeTaints 和 PodAffinityPredicate 这三个 Predicate 的含义和计算方法是类似的。但是作为 Priority，一个 Node 满足上述规则的字段数目越多，它的得分就会越高。

四. Preemption

4.1 场景

当一个高优先级的 Pod 调度失败后，该 Pod 并不会被“搁置”，而是会“挤走”某个 Node 上的一些低优先级的 Pod 。这样就可以保证这个高优先级 Pod 的调度成功，这就需要用到 Preemption 抢占机制。

4.2 原理

当上述抢占过程发生时，抢占者并不会立刻被调度到被抢占的 Node 上。事实上，调度器只会将抢占者的spec.nominatedNodeName 字段，设置为被抢占的 Node 的名字，所以这就是主要方法。

4.3 案例

4.3.1 PriorityClass 设置

apiVersion: scheduling.k8s.io/v1beta1
kind: PriorityClass
metadata:
  name: high-priority
value: 999999999
globalDefault: false
description: "This is a high-priority config."

上面这个 YAML 文件，定义的是一个名叫 high-priority 的 PriorityClass，其中 value 的值是 999999999。Kubernetes 规定，优先级是一个32 bit的整数，最大值不超过1000000000（10 亿，1 billion），并且值越大代表优先级越高。而超出 10 亿的值，其实是被 Kubernetes 保留下来分配给系统 Pod 使用的。这样做的目的，就是保证系统 Pod 不会被用户抢占掉。

4.3.2 Pod 配置

apiVersion: v1
kind: Pod
metadata:
  name: demo-pod
  labels:
    env: test
spec:
  containers:
  - name: nginx
    image: nginx
    imagePullPolicy: IfNotPresent
  priorityClassName: high-priority

这个 Pod 通过 priorityClassName 字段，声明了要使用名叫 high-priority 的 PriorityClass。当这个 Pod 被提交给 Kubernetes 之后，Kubernetes 的 PriorityAdmissionController 就会自动将这个 Pod 的 spec.priority 字段设置为 999999999。

4.4 队列

Kubernetes 调度器实现抢占算法的一个最重要的设计，就是在调度队列的实现里，使用了两个不同的队列。

4.4.1 activeQ

凡是在 activeQ 里的 Pod，都是下一个调度周期需要调度的对象。所以，当在 Kubernetes 集群里新创建一个 Pod 的时候，调度器会将这个 Pod 入队到 activeQ 里面。调度器不断从队列里出队（Pop）一个 Pod 进行调度，实际上都是从 activeQ 里出队的。

4.4.2 unschedulableQ

这是专门用来存放调度失败的 Pod，类似 Rabbitmq 使用的死信队列。当一个 unschedulableQ 里的 Pod 被更新之后，调度器会自动把这个 Pod 移动到 activeQ 里。

4.4 抢占流程

4.4.1 调度器为“抢占者”寻找“被抢占者”的流程

第一步，调度器会检查这次失败事件的原因，来确认抢占是不是可以帮助抢占者找到一个新节点。这是因为有很多 Predicates 的失败是不能通过抢占来解决的。比如，PodFitsHost 算法（负责的是，检查 Pod 的 nodeSelector 与 Node 的名字是否匹配），这种情况下，除非 Node 的名字发生变化，否则即使删除再多的 Pod，抢占者也不可能调度成功。
第二步，如果确定抢占可以发生，那么调度器就会把自己缓存的所有节点信息复制一份，然后使用这个副本来模拟抢占过程。

当遍历完所有的节点之后，调度器会在上述模拟产生的所有抢占结果里做一个选择，找出最佳结果。而这一步的判断原则，就是尽量减少抢占对整个系统的影响。

4.4.2 调度器就真正开始抢占

第一步，调度器会检“被抢占者”列表，清理这些 Pod 所携带的 nominatedNodeName 字段。
第二步，调度器会把抢占者的 nominatedNodeName，设置为被抢占的 Node 的名字。
第三步，调度器会开启一个Goroutine，同步地删除“被抢占者”。

所以接下来，调度器就会通过正常的调度流程把抢占者调度成功，在这个正常的调度流程里，是一切皆有可能的。

4.5 特殊场景

在为某一对 Pod 和 Node 执行 Predicates 算法的时候，如果待检查的 Node 是一个即将被抢占的节点，即：调度队列里有 nominatedNodeName 字段值是该 Node 名字的 Pod 存在（“潜在的抢占者”）。那么，调度器就会对这个 Node ，将同样的 Predicates 算法运行两遍。

4.5.1 流程

第一遍，调度器会假设上述“潜在的抢占者”已经运行在这个节点上，然后执行 Predicates 算法。
第二遍，调度器会正常执行 Predicates 算法，不考虑任何“潜在的抢占者”。而只有这两遍 Predicates 算法都能通过时，这个 Pod 和 Node 才会被认为是可以绑定（bind）的。

4.5.3 原因

第一遍 Predicates 算法的原因：是由于 InterPodAntiAffinity 规则的存在。
由于 InterPodAntiAffinity 规则关心待考察节点上所有 Pod 之间的互斥关系，所以我们在执行调度算法时必须考虑，如果抢占者已经存在于待考察 Node 上时，待调度 Pod 还能不能调度成功。
我们在这一步只需要考虑那些优先级等于或者大于待调度 Pod 的抢占者。毕竟对于其他较低优先级 Pod 来说，待调度 Pod 总是可以通过抢占运行在待考察 Node 上。
第二遍 Predicates 算法的原因：因为“潜在的抢占者”最后不一定会运行在待考察的 Node 上。原因是，Kubernetes 调度器并不保证抢占者一定会运行在当初选定的被抢占的 Node 上。

五. 总结

process

调度过程如下：

待调度Pod被提交到 apiServer -> 更新到 Etcd -> 调度器 Watch Etcd 感知到有需要调度的Pod（Informer） -> 取出待调度Pod的信息 -> Predicates：挑选出可以运行该Pod的所有Node -> Priorities：给所有Node打分 -> 将Pod绑定到得分最高的Node上 -> 将Pod信息更新回 Etcd -> node的 kubelet 感知到 Etcd 中有自己node需要拉起的Pod -> 取出该Pod信息，做基本的二次检测（端口，资源等） -> 在node 上拉起该pod

抢占过程如下：

Preemption：确定要发生抢占 -> 调度器将所有节点信息复制一份，开始模拟抢占 -> 检查副本里的每一个节点，然后从该节点上逐个删除低优先级Pod，直到满足抢占者能运行 -> 找到一个能运行抢占者Pod的node -> 记录下这个Node名字和被删除Pod的列表 -> 模拟抢占结束 -> 开始真正抢占 -> 删除被抢占者的Pod，将抢占者调度到Node上

欢迎收藏个人博客: Wyatt's Blog ，非常感谢～

Reference

https://time.geekbang.org/column/article/70519?utm_campaign=guanwang&utm_source=baidu-ad&utm_medium=ppzq-pc&utm_content=title&utm_term=baidu-ad-ppzq-title
https://kubernetes.io/docs/concepts/scheduling-eviction/kube-scheduler/
https://dominik-tornow.medium.com/the-kubernetes-scheduler-cd429abac02f
https://alibaba-cloud.medium.com/getting-started-with-kubernetes-scheduling-and-resource-management-4d819c901b8c

Kubernetes：默认调度器三大机制