作者 | 汪萌海（木苏） 阿里巴巴技术专家
关注“阿里巴巴云原生”公众号，回复关键词“入门”，即可下载从零入门 K8s 系列文章 PPT。
导读：Kubernetes 作为当下最流行的容器自动化运维平台，以声明式实现了灵活的容器编排，本文以 v1.16 版本为基础详细介绍了 K8s 的基本调度框架、流程，以及主要的过滤器、Score 算法实现等，并介绍了两种方式用于实现自定义调度能力。
调度流程
调度流程概览
Kubernetes 作为当下最主流的容器自动化运维平台，作为 K8s 的容器编排的核心组件 kube-scheduler 将是我今天介绍的主角，如下介绍的版本都是以 release-1.16 为基础，下图是 kube-scheduler 的主要几大组件：
Policy
Scheduler 的调度策略启动配置目前支持三种方式，配置文件 / 命令行参数 / ConfigMap。调度策略可以配置指定调度主流程中要用哪些过滤器 (Predicates)、打分器 (Priorities) 、外部扩展的调度器 (Extenders)，以及最新支持的 SchedulerFramwork 的自定义扩展点 (Plugins)。
Informer
Scheduler 在启动的时候通过 K8s 的 informer 机制以 List+Watch 从 kube-apiserver 获取调度需要的数据例如：Pods、Nodes、Persistant Volume(PV), Persistant Volume Claim(PVC) 等等，并将这些数据做一定的预处理作为调度器的的 Cache。
调度流水线
通过 Informer 将需要调度的 Pod 插入 Queue 中，Pipeline 会循环从 Queue Pop 等待调度的 Pod 放入 Pipeline 执行。
调度流水线 (Schedule Pipeline) 主要有三个阶段：Scheduler Thread，Wait Thread，Bind Thread。
- Scheduler Thread 阶段: 从如上的架构图可以看到 Schduler Thread 会经历 Pre Filter -> Filter -> Post Filter-> Score -> Reserve，可以简单理解为 Filter -> Score -> Reserve。
Filter 阶段用于选择符合 Pod Spec 描述的 Nodes；Score 阶段用于从 Filter 过后的 Nodes 进行打分和排序；Reserve 阶段将 Pod 跟排序后的最优 Node 的 NodeCache 中，表示这个 Pod 已经分配到这个 Node 上, 让下一个等待调度的 Pod 对这个 Node 进行 Filter 和 Score 的时候能看到刚才分配的 Pod。
- Wait Thread 阶段: 这个阶段可以用来等待 Pod 关联的资源的 Ready 等待，例如等待 PVC 的 PV 创建成功，或者 Gang 调度中等待关联的 Pod 调度成功等等；
- Bind Thread 阶段: 用于将 Pod 和 Node 的关联持久化 Kube APIServer。
整个调度流水线只有在 Scheduler Thread 阶段是串行的一个 Pod 一个 Pod 的进行调度，在 Wait 和 Bind 阶段 Pod 都是异步并行执行。
调度详细流程
解说完 kube-scheduler 的几大部件的作用和关联关系之后，接下来深入理解下 Scheduler Pipeline 的具体工作原理，如下是 kube-scheduler 的详细流程图，先解说调度队列：
SchedulingQueue 有三个子队列 activeQ、backoffQ、unschedulableQ。
Scheduler 启动的时候所有等待被调度的 Pod 都会进入 activieQ，activeQ 会按照 Pod 的 priority 进行排序，Scheduler Pipepline 会从 activeQ 获取一个 Pod 进行 Pipeline 执行调度流程，当调度失败之后会直接根据情况选择进入 unschedulableQ 或者 backoffQ，如果在当前 Pod 调度期间 Node Cache、Pod Cache 等 Scheduler Cache 有变化就进入 backoffQ，否则进入 unschedulableQ。
unschedulableQ 会定期较长时间（例如 60 秒）刷入 activeQ 或者 backoffQ，或者在 Scheduler Cache 发生变化的时候触发关联的 Pod 刷入 activeQ 或者 backoffQ；backoffQ 会以 backoff 机制相比 unschedulableQ 比较快地让待调度的 Pod 进入 activeQ 进行重新调度。
接着详细介绍 Scheduler Thread 阶段，在 Scheduler Pipeline 拿到一个等待调度的 Pod，会从 NodeCache 里面拿到相关的 Node 执行 Filter 逻辑匹配，这从 NodeCache 遍历 Node 的过程有一个空间算法上的优化，简单可以概括为在避免过滤所有节点的同时考虑了调度的容灾取样调度。
具体的优化算法逻辑（有兴趣的同学可以看 node_tree.go 的 Next 方法）：在 NodeCache 中，Node 是按照 zone 进行分堆。在 filter 阶段的时候，为会 NodeCache 维护一个 zondeIndex，每 Pop 一个 Node 进行过滤，zoneIndex 往后挪一个位置，然后从该 zone 的 node 列表中取一个 node 出来。
可以看到上图纵轴有一个 nodeIndex，每次也会自增。如果当前 zone 的节点无数据，那就会从下一个 zone 中拿数据。大概的流程就是 zoneIndex 从左向右，nodeIndex 从上到下，保证拿到的 Node 节点是按照 zone 打散，从而实现避免过滤所有节点的同时考虑了节点的 az 均衡部署。（最新 release-v.1.17 的版本已经取消这种算法，为什么取消应该是没有考虑 Pod 的 prefer 和 node 的 prefer，没有实现 Pod 的 Spec 要求）
取样调度里面的取样规模这里简单介绍一下，默认的取样比率公式 = Max (5, 50 – 集群的 node 数 / 125),取样规模 = Max (100, 集群 Node 数*取样比率)。
这里举个例子：节点规模为 3000 个节点，那么取样比例 = Max (5, 50 – 3000/125) = 26%，那么取样规模 = Max (100, 3000* 0.26) = 780，在调度流水线里面，Filter 只要匹配到 780 个候选节点，就可以停止 Filter 流程，走到 Score 阶段。
Score 阶段依据 Policy 配置的算分插件，进行排序，分数最高的节点作为 SelectHost。接着将这个 Pod 分配到这个 Node 上，这个过程叫做 Reserver 阶段可以称为账本预占。预占的过程修改 Pod 在 PodCache 的状态为 Assumed 的状态(处于内存态)。
调度过程涉及到 Pod 状态机的生命周期，这里简单介绍下 Pod 的几个主要状态: Initial（虚拟状态）->Assumed（Reserver)->Added->Deleted(虚拟状态）; 当通过 Informer watch 到 Pod 数据已经确定分配到这个节点的时候，才会把 Pod 的状态变成 Added。选中完节点在 Bind 的时候，有可能会 Bind 失败，在 Bind 失败的时候会做回退，就是把预占用的账本做 Assumed 的数据退回 Initial，也就是把 Assumed 状态擦除，从 Node 里面把 Pod 账本清除。
如果 Bind 失败，会把 Pod 重新丢回到 unschedulableQ 队列里面。在调度队列中，什么情况下 Pod 会到 backoffQ 中呢？这是一个很细节的点。如果在这么一个调度周期里面，Cache 发生了变化，会把 Pod 放到 backoffQ 里面。在 backoffQ 里面等待的时间会比在 unschedulableQ 里面时间更短，backoffQ 里有一个降级策略，是 2 的指数次幂降级。假设重试第一次为 1s，那第二次就是 2s，第三次就是 4s，第四次就是 8s，最大到 10s。
调度算法实现
Predicates (过滤器)
Filter 根据功能用途可以把它们分为四类：
- 存储匹配相关
- Pode 和 Node 匹配相关
- Pod 和 Pod 匹配相关
- Pod 打散相关
存储相关
存储相关的几个过滤器的功能：
- NoVolumeZoneConflict，pvc 关联的 pv 的 label 上设置 zoneaz 限制待匹配的节点要跟 pv；
- MaxCSIVolumeCountPred，是用来校验 pvc 上指定的 Provision 在 CSI plugin 上的单机最大 pv 数限制；
- CheckVolumeBindingPred，在 pvc 和 pv 的 binding 过程中对其进行逻辑校验，里头的逻辑写的比较复杂，主要都是如何复用 pv；
- NoDiskConfict，SCSI 存储不会被重复的 volume。
Pod 和 Node 匹配相关
- CheckNodeCondition：校验节点是否准备好被调度，校验node.condition的condition type ：Ready为true和NetworkUnavailable为false以及Node.Spec.Unschedulable为false；
- CheckNodeUnschedulable：在 node 节点上有一个 NodeUnschedulable 的标记，我们可以通过 kube-controller 对这个节点直接标记为不可调度，那这个节点就不会被调度了。在 1.16 的版本里，这个 Unschedulable 已经变成了一个 Taints。也就是说需要校验一下 Pod 上打上的 Tolerates 是不是可以容忍这个 Taints；
- PodToleratesNodeTaints：校验 Node 的 Taints 是否被 Pod Tolerates 包含；
- PodFitsHostPorts：校验 Pod 上的 Container 声明的 Ports 是否正在被 Node 上已经分配的 Pod 使用；
- MatchNodeSelector: 校验 Pod.Spec.Affinity.NodeAffinity 和 Pod.Spec.NodeSelector 是否与 Node 的 Labels 匹配。
Pod 和 Pod 匹配相关
MatchinterPodAffinity：主要是 PodAffinity 和 PodAntiAffinity 的校验逻辑，这里面最大的复杂度是在于 Affinity 里面的 PodAffinityTerm 描述支持的 TopologyKey（可以表示在 node/zone/az 等拓扑结构上），这个其实是一个性能杀手。
Pod 打散相关
- EvenPodsSpread
- CheckServiceAffinity
EvenPodsSpread
这是一个新的功能特性，首先来看一下 EvenPodsSpread 中 Spec 描述：
— 描述符合条件的一组 Pod 在指定 TopologyKey 上的打散要求。
下面我们来看一下怎么描述一组 Pod，如下图所示：
spec:
topologySpreadConstraints:
- maxSkew: 1
whenUnsatisfiable: DoNotSchedule
topologyKey: k8s.io/hostname
selector:
matchLabels:
app: foo
matchExpressions:
- key: app
operator: In
values: ['foo', 'foo2']topologySpreadConstraints: 用于描述 Pod 要在什么拓扑结构上进行均衡打散，多个 topologySpreadConstraint 之间是 and 关系；
selector：用于描述需要满足的拓扑打散的一组 Pod 的列表
topologyKey: 作用在什么拓扑结构上；
maxSkew: 最大允许的不均衡数量；
whenUnsatisfiable: 当不满足 topologySpreadConstraint 的时候的策略，DoNotSchedule：表示作用于 filter 阶段，ScheduleAnyway：作用于 score 阶段。
下面举例描述下：
selector 选择的是所有 lable 符合 app=foo 的 pod，必须在 zone 级别是打散的，允许最大不均衡数为 1。
集群中有三个 zone，上图中 label 的值 app=foo 的 Pod 在 zone1 和 zone2 中都分配了一个 pod。
计算不均衡数量公式为：ActualSkew = count[topo] – min(count[topo])
首先，依据 selector 获取到符合条件的 Pod 列表
其次，会按照 topologyKey 去分组得到 count[topo]
如上图所示：
假设 maxSkew 为 1，如果分配到 zone1/zone2，skew 的值为2，大于前面设置的 maxSkew。这是不匹配的，所以只能分配到 zone3。如果分配到 zone3 的话，min(count[topo]) 为1，count[topo]为 1，那 skew 就等于 0，因此只能分配到 zone2。
假设 maxSkew 为 2，分配到 z1(z2)，skew 的值为 2/1/0(1/2/0)，最大值为 2，满足
