Kubernetes Scheduler 概述

调度器的主要职责是负责整个集群资源的调度功能，根据特定的调度算法和策略，将业务调度到最优的工作节点上去，达到更加合理、更加充分利用集群资源的目的。而 Kubernetes 中的默认调度器（default-scheduler）是 kube-scheduler，其主要职责就是为一个新创建出来的 Pod，寻找一个最
合适的节点（Node）。其主要思想可简单表述成下面两个阶段：

1. 根据过滤算法从集群的所有节点中挑选出所有可以运行该 Pod 的节点；
2. 从第一步的结果中，再根据优选算法挑选一个最符合条件的节点作为最终结果。
   所以在具体的调度流程中，默认调度器会首先调用一组叫作 Predicate 的调度算法，来检查每个 Node。然后，再调用一组叫作 Priority 的调度算法，来给上一步得到的结果里的每个 Node 打分。最终的调度结果，就是得分最高的那个 Node。调度器简单逻辑如下所示：

kube-scheduler 调度器的工作原理

从上面的简介中可知调度器主要包括预选和优选两个大阶段，但为了更好的提高调度器的性能 Kubernetes 对默认调度器的设计非常复杂。个人看了张磊老师的文章，觉得大佬写的通俗易懂，在这里我主要做个记录吧，后面可借鉴这个文章去分析源码是如何实现的。在 Kubernetes 中，默认调度器的工作原理，可以用如下所示的一幅示意图来表示。

可以看到，Kubernetes 的调度器的核心，实际上就是两个相互独立的控制循环。
其中，第一个控制循环，我们可以称之为 Informer Path。 它的主要目的，是启动一系列 Informer，用来监听（Watch）Etcd 中 Pod、Node、Service 等与调度相关的 API 对象的变化。比如，当一个待调度 Pod（即：它的 nodeName 字段是空的）被创建出来之后，调度器就会通过 Pod Informer 的 Handler，将这个待调度 Pod 添加进调度队列。在默认情况下，Kubernetes 的调度队列是一个 PriorityQueue（优先级队列），并且当某些集群信息发生变化的时候，调度器还会对调度队列里的内容进行一些特殊操作。这里的设计，主要是出于调度优先级和抢占的考虑，我会在后面的文章中再详细介绍这部分内容。
此外，Kubernetes 的默认调度器还要负责对调度器缓存（即：scheduler cache）进行更新。事实上，Kubernetes 调度部分进行性能优化的一个最根本原则，就是尽最大可能将集群信息Cache 化，以便从根本上提高 Predicate 和 Priority 调度算法的执行效率。

而第二个控制循环，是调度器负责 Pod 调度的主循环，我们可以称之为 Scheduling Path。 Scheduling Path 的主要逻辑，就是不断地从调度队列里出队一个 Pod。然后，调用Predicates 算法进行“过滤”。这一步“过滤”得到的一组 Node，就是所有可以运行这个Pod 的宿主机列表。当然，Predicates 算法需要的 Node 信息，都是从 Scheduler Cache 里直接拿到的，这是调度器保证算法执行效率的主要手段之一。

接下来，调度器就会再调用 Priorities 算法为上述列表里的 Node 打分，分数从 0 到 10。得分最高的 Node，就会作为这次调度的结果。

调度算法执行完成后，调度器就需要将 Pod 对象的 nodeName 字段的值，修改为上述 Node的名字。这个步骤在 Kubernetes 里面被称作 Bind。 但是，为了不在关键调度路径里远程访问 APIServer，Kubernetes 的默认调度器在 Bind 阶段，只会更新 Scheduler Cache 里的 Pod 和 Node 的信息。这种基于“乐观”假设的 API 对象更新方式，在 Kubernetes 里被称作 Assume。 Assume 之后，调度器才会创建一个 Goroutine 来异步地向 APIServer 发起更新 Pod 的请求，来真正完成 Bind 操作。如果这次异步的 Bind 过程失败了，其实也没有太大关系，等Scheduler Cache 同步之后一切就会恢复正常。

注意： 调度器调度之前是只监听 spec.nodeName 为空的 pod，并将其添加到调度器的优先级队列中，调度器执行之后是将选中的 node 名字赋值给 pod 的 spec.nodeName 中，即表示调度成功。

当然，正是由于上述 Kubernetes 调度器的“乐观”绑定的设计，当一个新的 Pod 完成调度需要在某个节点上运行起来之前，该节点上的 kubelet 还会通过一个叫作 Admit 的操作来再次验证该 Pod 是否确实能够运行在该节点上。这一步 Admit 操作，实际上就是把一组叫作GeneralPredicates 的、最基本的调度算法，比如：“资源是否可用”、“端口是否冲突”等再执行一遍，作为 kubelet 端的二次确认。

除了上述的“Cache 化”和“乐观绑定”，Kubernetes 默认调度器还有一个重要的设计，那就是“无锁化”。 在 Scheduling Path 上，调度器会启动多个 Goroutine（最多16个）以节点为粒度并发执行 Predicates 算法，从而提高这一阶段的执行效率。而与之类似的，Priorities 算法也会以 MapReduce 的方式并行计算然后再进行汇总。而在这些所有需要并发的路径上，调度器会避免设置任何全局的竞争资源，从而免去了使用锁进行同步带来的巨大的性能损耗。

所以，在这种思想的指导下，如果你再去查看一下前面的调度器原理图，你就会发现，Kubernetes 调度器只有对调度队列和 Scheduler Cache 进行操作时，才需要加锁。而这两部分操作，都不在 Scheduling Path 的算法执行路径上。

当然，Kubernetes 调度器的上述设计思想，也是在集群规模不断增长的演进过程中逐步实现的。尤其是 “Cache 化”，这个变化其实是最近几年 Kubernetes 调度器性能得以提升的一个关键演化。

不过，随着 Kubernetes 项目发展到今天，它的默认调度器也已经来到了一个关键的十字路口。事实上，Kubernetes 现今发展的主旋律，是整个开源项目的“民主化”。也就是说，Kubernetes 下一步发展的方向，是组件的轻量化、接口化和插件化。所以，我们才有了 CRI、CNI、CSI、CRD、Aggregated APIServer、Initializer、Device Plugin 等各个层级的可扩展能力。可是，默认调度器，却成了 Kubernetes 项目里最后一个没有对外暴露出良好定义过的、可扩展接口的组件。当然随着时间的发展以及用户和市场的需求，Kubernete scheduler 可扩展接口也得到了支持，后面我将详细介绍 Scheduler Framework。

总结

本文主要介绍了 Kubernetes 默认调度器 kube-scheduler 的实现原理，即两个控制循环：Informer path 和 Scheduling path，这两个控制循环实现了对资源依赖的解藕，实现了高性能的调度器。其中 Informer path 与 apiserver 建立通信不断 watch 资源变化情况，并将其本地cache 化；Scheduling path 则不断的从 cache 中读取数据，通过一系列的调度算法后对pod 和资源进行调度和分配，最终将 pod 绑定到合适的节点上。从上面的原理可知，Kubernetes 调度器实现高性能优化的方法主要有以下几个方面：

• 优先级队列的实现： 对于高优先级的 pod 或者特殊的 pod，可以通过指定器优先级来提高被优先调度的可能性。
• 资源本地 cache 化： Informer path 中 pod 添加到优先级队列中和 nodeinfo 添加到本地cache 中。
• Assume 乐观绑定： bind 阶段不在关键路径调用 apiserver，只更新 scheduler cache 信息。正真的 bind操作通过 goroutine 异步执行。
• 并行执行过滤算法和打分算法： 同一个 pod 在执行不相关的调度算法时会启用 16个 goroutine 来并行计算。
• 循环无锁化： 调度器的主循环中尽量不产生资源竞争，即不添加锁处理；只有在更新优先级队列和 cache 时才会添加锁，避免数据竞争，但这两步都不主循环中。
• 提前结束过滤： 其实为提高调度器的执行性能，在 k8s 1.12 之后会增加一个 percentageOfNodesToScore 字段，即指定需要打分的节点数（百分比），当过滤出来的节点数（满足条件可打分的节点）达到这个指定的值时会停止过滤集群中剩余的pod；只会对过滤出来的指定数量的pod进行打分判断。这种方法在集群规模很小是效果不是很显著，但是在集群规模很大时，调度器的性能提高会非常显著。

目前 Kubernetes 默认调度器能支持绝大部分场景，对于一些比较特殊复杂的场景中用户可以通过后面介绍的 Scheduler Framework 以及插件机制进行扩展。