作者：卢宇亮，张寿元，刘婉辉，民生银行

导读

云环境或者计算仓库级别（将整个数据中心当做单个计算池）的集群管理系统通常会定义出工作负载的规范，并使用调度器将工作负载放置到集群恰当的位置。好的调度器可以让集群的工作处理更高效，同时提高资源利用率，节省能源开销。
通用调度器，如Kubernetes原生调度器Scheduler实现了根据特定的调度算法和策略将pod调度到指定的计算节点（Node）上。但实际上设计大规模共享集群的调度器并不是一件容易的事情。调度器不仅要了解集群资源的使用和分布情况，还要兼顾任务分配速度和执行效率。过度设计的调度器屏蔽了太多的技术实现，以至于无法按照预期完成调度任务，或导致异常情况的发生，不恰当的调度器的选择同样会降低工作效率，或导致调度任务无法完成。
本文主要从设计原理、代码实现两个层面介绍Kubernetes的调度器以及社区对其的补充加强，同时对业界常用调度器的设计实现进行比较分析。通过本文，读者可了解调度器的来龙去脉，从而为选择甚至设计实现适合实际场景的调度器打下基础。

注明：本文中代码基于v1.11版本Kubernetes进行分析，如有不当之处，欢迎指正！

1.调度器的基本知识

1.1 调度器的定义

通用调度[1]的定义是指基于某种方法将某项任务分配到特定资源以完成相关工作，其中任务可以是虚拟计算元素，如线程、进程或数据流，特定资源一般是指处理器、网络、磁盘等，调度器则是完成这些调度行为的具体实现。使用调度器的目的是实现用户共享系统资源的同时，降低等待时间，提高吞吐率以及资源利用率。
本文中我们讨论的调度器是指大规模集群下调度任务的实现，比较典型的有Mesos[2]/Yarn3、Borg[4]/Omega5、Quincy6、伏羲（阿里云）等。构建大规模集群（如数据中心规模）的成本非常之高，因此精心设计调度器就显得尤为重要。
常见类型的调度器的对比分析如下表1所示（摘自Omega[5]）：

1.2 调度器的考量标准

我们首先思考一下调度器是根据哪些信息来进行调度工作的，以及哪些指标可以用来衡量调度工作质量。
调度器的主要工作是将资源需求与资源提供方做全局最优的匹配。所以一方面调度器的设计需要了解不同类型的资源拓扑，另一方面还需要对工作负载有充分的认识。
了解不同类型的资源拓扑，充分掌握环境拓扑信息能够使调度工作更充分的利用资源（如经常访问数据的任务如果距数据近可以显著减少执行时间），并且可以基于资源拓扑信息定义更加复杂的策略。但全局资源信息的维护消耗会限制集群的整体规模和调度执行时间，这也让调度器难以扩展，从而限制集群规模。
另一方面，由于不同类型的工作负载会有不同的甚至截然相反的特性，调度器还需要对工作负载有充分的认识，例如服务类任务，资源需求少，运行时间长，对调度时间并不敏感；而批处理类任务，资源需求大，运行时间短，任务可能相关，对调度时间要求较高。 同时，调度器也要满足使用方的特殊要求。如任务尽量集中或者分散，保证多个任务同时进行等。
总的来说，好的调度器需要平衡好单次调度（调度时间，质量），同时要考虑到环境变化对调度结果的影响，保持结果最优（必要时重新调度），保证集群规模，同时还要能够支持用户无感知的升级和扩展。调度的结果需要满足但不限于下列条件，并最大可能满足尽可能优先级较高的条件：

• 资源使用率最大化
• 满足用户指定的调度需求
• 满足自定义优先级要求
• 调度效率高，能够根据资源情况快速做出决策
• 能够根据负载的变化调整调度策略
• 充分考虑各种层级的公平性

1.3 锁对调度器设计的影响

对于资源的调度，一定会涉及到锁的应用，不同类型锁的选择将直接决定调度器的使用场景。类似Mesos等两层调度器，一般采用悲观锁的设计实现方式，当资源全部满足任务需要时启动任务，否则将增量继续申请更多的资源直到调度条件满足；而共享状态的调度器，会考虑使用乐观锁的实现方式，Kubernetes默认调度器是基于乐观锁进行设计的。
我们首先通过一个简单的例子，比较下悲观锁和乐观锁处理逻辑的不同，假设有如下的一个场景：

1. 作业A读取对象O
2. 作业B读取对象O
3. 作业A在内存中更新对象O
4. 作业B在内存中更新对象O
5. 作业A写入对象O实现持久化
6. 作业B写入对象O实现持久化

悲观锁的设计是对对象O实现独占锁，直到作业A完成对对象O的更新并写入持久化数据之前，阻断其他读取请求。乐观锁的设计是对对象O实现共享锁，假设所有的工作都能够正常完成，直到有冲突产生，记录冲突的发生并拒绝冲突的请求。
乐观锁一般会结合资源版本实现，同样是上述中的例子，当前对象O的版本为v1，作业A首先完成对对象O的写入持久化操作，并标记对象O的版本为v2，作业B在更新时发现对象版本已经变化，则会取消更改。

2.Kubernetes调度器剖析

Kubernetes中的计算任务大多通过pod来承载运行。pod是用户定义的一个或多个共享存储、网络和命名空间资源的容器的组合，是调度器可调度的最小单元。Kubernetes的调度器是控制平面的一部分，它主要监听APIServer提供的pod任务列表，获取待调度pod，根据预选和优选策略，为这些pod分配运行的节点。概括来说，调度器主要依据资源消耗的描述得到一个调度结果。

2.1 Kubernetes调度器的设计

Kubernetes的调度设计参考了Omega的实现，主要采用两层调度架构，基于全局状态进行调度，通过乐观锁控制资源归属，同时支持多调度器的设计。
两层架构帮助调度器屏蔽了很多底层实现细节，将策略和限制分别实现，同时过滤可用资源，让调度器能够更灵活适应资源变化，满足用户个性化的调度需求。相比单体架构而言，不仅更容易添加自定义规则、支持集群动态伸缩，同时对大规模集群有更好的支持（支持多调度器）。
相比于使用悲观锁和部分环境视图的架构（如Mesos），基于全局状态和乐观锁实现的好处是调度器可以看到集群所有可以支配的资源，然后抢占低优先级任务的资源，以达到策略要求的状态。它的资源分配更符合策略要求，避免了作业囤积资源导致集群死锁的问题。当然这会有抢占任务的开销以及冲突导致的重试，但总体来看资源的使用率更高了。
Kubernetes中默认只有一个调度器，而Omega的设计本身支持资源分配管理器共享资源环境信息给多个调度器。所以从设计上来说，Kubernetes可以支持多个调度器。

2.2 Kubernetes调度器的实现

Kubernetes调度器的工作流程如下图所示。调度器的工作本质是通过监听pod的创建、更新、删除等事件，循环遍历地完成每个pod的调度流程。如调度过程顺利，则基于预选和优选策略，完成pod和主机节点的绑定，最终通知kubelet完成pod启动的过程。如遇到错误的调度过程，通过优先级抢占的方式，获取优先调度的能力，进而重新进入调度循环的过程，等待成功调度。

2.2.1 调度循环的完整逻辑

Kubernetes调度器完成调度的整体流程如下图1所示。下面就每个步骤的实现逻辑进行说明。

图1：Kubernetes调度器的完整流程

（1）基于事件驱动启动循环过程
Kubernetes调度器维护sharedIndexInformer，来完成informer对象的初始化工作。也就是调度器会监听pod创建、更新、删除的操作事件，主动更新事件缓存，并持久化到内存队列，发起调度循环。
该过程的函数入口在
https://github.com/kubernetes/kubernetes/blob/9cbccd38598e5e2750d39e183aef21a749275087/pkg/scheduler/factory/factory.go#L631

（2）将没有调度的pod加到调度器缓存并更新调度器队列
Informer对象负责监听pod的事件，主要的事件类型有：针对已调度pod的addPodToCache、updatePodInCache、deletePodFromCache和针对未被调度pod的addPodToSchedulingQueue、updatePodInSchedulingQueue、deletePodFromSchedulingQueue六种事件。该过程的函数入口在：
https://github.com/kubernetes/kubernetes/blob/9cbccd38598e5e2750d39e183aef21a749275087/pkg/scheduler/eventhandlers.go。
各类事件的含义如下表2所示：

（3）对调度器队列中的每个pod执行调度
这里需要指出的是，在单个pod调度的过程中，对于主机节点的调度算法是顺序执行的。也就是说，pod在调度的过程中会严格的顺序执行Kubernetes内置的策略和优先级，然后选择最合适的节点。
单个pod的调度过程分为预选和优选两个阶段。预选阶段调度器根据一组规则过滤掉不符合要求的主机，选择出合适的节点；优选阶段通过节点优先级打分的方式（依据整体优化策略等），选择出分值最高的节点进行调度。
单个pod的调度过程由以下函数作为入口：https://github.com/kubernetes/kubernetes/blob/9cbccd38598e5e2750d39e183aef21a749275087/pkg/scheduler/scheduler.go#L457

当然，调度的过程可能由于没有满足pod运行条件的节点而调度失败，此时当pod有优先级指定的时候，将触发竞争机制。具有高优先级的pod将尝试抢占低优先级的pod资源。相关部分代码实现如下：

如果资源抢占成功，将在下一次调度循环时标记可调度过程。如果抢占失败，调度程序退出。调度结果不保存意味着pod仍然会出现在未分配列表中。
（4）接下来检查用户提供的插件的条件是否满足
Reserve插件是Kubernets留给用户进行扩展的接口，基于reserver插件用户在这个阶段可以设定自定义条件，从而满足期望的调度过程。插件的入口函数在：https://github.com/kubernetes/kubernetes/blob/9cbccd38598e5e2750d39e183aef21a749275087/pkg/scheduler/plugins/registrar.go
可以在https://github.com/kubernetes/kubernetes/tree/9cbccd38598e5e2750d39e183aef21a749275087/pkg/scheduler/plugins/examples查看插件扩展reserver接口进行自定义调度的示例。
（5）找到满足的节点后，更新Pod对象的标签，保存被调度节点的结果
该过程的函数入口在https://github.com/kubernetes/kubernetes/blob/9cbccd38598e5e2750d39e183aef21a749275087/pkg/scheduler/scheduler.go#L517。

（6）完成pod到节点的绑定
pod到节点的绑定需要首先完成存储卷的挂载，最后通过pod对象的更新，完成最后的绑定。具体代码的逻辑可以参考：https://github.com/kubernetes/kubernetes/blob/9cbccd38598e5e2750d39e183aef21a749275087/pkg/scheduler/scheduler.go#L524。
（7）调度完成后，主协程返回，执行下一个调度
至此调度的完整流程就完成了，下面重点介绍下，在单个pod调度过程中Kubernetes主要是如何对节点进行选择的，主要包括预选和优选两种策略。

2.2.2 单个pod的调度流程

单个pod的调度过程如下图2所示。主要包括由pre-filter、filter、post-filter的预选过程和scoring的优选过程。

图2：单个Pod的调度过程

1、pod进入调度阶段，首先进入预选环节。通过规则过滤找到满足pod调度条件的节点。

k8s内置了许多过滤规则，调度器会按照事先定义好的顺序进行过滤。内置的过滤规则主要包括检查节点是否有足够资源（例如CPU、内存与GPU等）满足pod的运行需求，检查pod容器所需的HostPort是否已被节点上其它容器或服务占用，检查节点标签（label）是否匹配pod的nodeSelector属性要求，根据 taints 和 toleration 的关系判断pod是否可以调度到节点上pod是否满足节点容忍的一些条件，还有检查是否满足csi最大可挂载卷限制等。

2、经过预选策略对节点过滤后，进入优选阶段。调度器根据预置的默认规则进行打分（优先级函数得分*权重的和），然后选择分数最高的节点实现pod到节点的绑定。

Kubernetes内置的优先级函数如下，主要包括平均分布优先级（SelectorSpreadPriority）、最少访问优先级（LeastRequestedPriority）、平衡资源分布优先级（BalancedResourceAllocation）等。

• SelectorSpreadPriority：为了更好的高可用，对同属于一个service、replication controller或者replica的多个Pod副本，尽量调度到多个不同的节点上。
• InterPodAffinityPriority：通过迭代 weightedPodAffinityTerm的元素计算和，如果对该节点满足相应的PodAffinityTerm，则将 “weight” 加到和中，具有最高和的节点是最优选的。
• LeastRequestedPriority：由节点空闲资源与节点总容量的比值，即由（总容量-节点上Pod的容量总和-新Pod的容量）/总容量）来决定节点的优先级。CPU和memory具有相同权重，比值越大的节点得分越高。
• BalancedResourceAllocation：CPU和内存使用率越接近的节点优先级越高，该策略不能单独使用，必须和LeastRequestedPriority同时使用，也就是说尽量选择在部署Pod后各项资源更均衡的机器。
• NodePreferAvoidPodsPriority（权重1w）： 如果节点的 Anotation 没有设置 key-value:scheduler. alpha.kubernetes.io/ preferAvoidPods = "..."，则该 节点对该 policy 的得分就是10分，加上权重10000，那么该节点对该policy的得分至少10W分。如果节点的Anotation设置了scheduler.alpha.kubernetes.io/preferAvoidPods = "..." ，如果该 pod 对应的 Controller 是 ReplicationController 或 ReplicaSet，则该节点对该 policy 的得分就是0分。
• NodeAffinityPriority：实现Kubernetes调度中的亲和性机制。
• TaintTolerationPriority : 使用 Pod 中 tolerationList 与 节点 Taint 进行匹配，配对成功的项越多，则得分越低。

3.Kubernetes调度器的不足和解决思路

3.1典型的几个问题和解决思路

（1）调度器只根据当前资源环境情况进行一次调度，一旦完成调度就没有机制实现调整。
虽然pod只有在自己退出、用户删除以及集群资源不足等情况下才会有变化。但资源拓扑的变化是随时都有可能发生的，如批处理任务会结束，节点会新增或崩溃。这些情况导致调度的结果可能在调度时是最优的，但在拓扑变化后调度质量由于以上情况的发生而下降。
经过社区讨论，认为需要重新找出不满足调度策略的pod，删除并创建替代者来重新调度，据此设计启动了项目descheduler。
（2）调度以单个pod进行的，因而调度互相关联的工作负载会难以实现。
如大数据分析、机器学习等计算多依赖于批处理任务，这类工作负载相关性大，互相之间有依赖关系。为了解决这个问题，社区经过讨论，提出了coscheduling 一次调度一组pod的项目，以此来优化这类调度任务的执行。
（3）目前调度器的实现只关心是否能将pod与节点绑定，资源使用情况的数据未被充分利用
目前，集群的使用量只能通过监控数据间接推导。如果k8s集群剩余资源不足时，并没有直观数据可以用来触发扩容或者告警。
根据上述情况，社区启动了cluster-capacity framework项目 ，提供集群的容量数据，方便集群的维护程序或者管理员基于这些数据做集群扩容等。也有项目抓取监控数据自己计算集群的整体负载情况给调度算法参考，如poseidon。

3.2 Kubernetes调度器的定制扩展

如上节所述，通用调度器在某些场景下并不能满足用户个性化需求，实际环境下运行的集群的调度器，往往需要根据实际的需求做定制与二次开发。
kubernetes的调度器以插件化的形式实现的， 方便用户对调度的定制与二次开发。定制调度器有如下几种方式的选择：
更改Kubernetes内置策略，通过更改默认的策略文件[8]或者重新编译调度器来实现。
扩展调度器在pre-filter、filter、post-filter、reserve、prebind、bind和post-bind各个阶段的接口[9]，更改调度器过滤、打分、抢占、预留的具体实现逻辑。
更改调度器调度算法，从头实现调度器逻辑[10]。

4.企业场景应用的案例

4.1 通用计算场景

Kubernetes default-scheduler满足通用计算的需求，主要服务于以快速开发测试为目标的持续集成和持续部署平台（DevOps平台）、以标准三层架构应用为特点的容器应用运行与运维平台（容器平台）、PaaS平台和云原生应用的核心基础架构平台（aPaaS平台）几种场景。
通常情况下，标准Kubernetes调度器能够满足大多数通过计算场景的诉求，主要解决应用上云过程中不同异构云资源之间的调度问题，应用上云后弹性伸缩、故障自愈等的动态调度响应，标准中间件服务和数据库服务基于日常运维规范的调度问题以及云原生应用在服务治理、配置管理、状态反馈、事件链路跟踪上的综合调度过程。

4.2 批处理场景

大数据分析和机器学习类任务执行时需要大量资源，多个任务同时进行时，资源很快会用尽，部分任务会需要等待资源释放。这类型任务的步骤往往互相关联，单独运行步骤可能会影响最终结果。使用默认的调度器在集群资源紧张时，甚至会出现占用资源的pod都在等待依赖的pod运行完毕，而集群没有空闲资源去运行依赖任务，导致死锁。所以在调度这类任务时，支持群组调度（在调度作业所需的资源都收集完成后才进行调度），减少了pod数量，因而降低调度器的负载，同时避免了很多资源紧张带来的问题。
与默认调度器一次调度一个pod不同，kube-batch定义了PodGroup 定义一组相关的pod资源，并实现了一个全新的调度器。调度器的流程基本与默认调度器相同。Podgroup保证一组pod可以同时被调度。是Kubernetes社区在大数据分析场景中的一种实现。

4.3 特定领域业务场景

特定的业务场景需要调度器能够快速生成调度的策略，并尽可能避免调度超时。Poseidon是大规模集群中基于图应用数据局部性减少任务执行时间同时混合多种调度算法提升调度速度的一种调度器。
Poseidon是基于Firmament算法的调度器，它通过接收heapster数据来构建资源使用信息。调用Firmament实现进行调度。Firmament算法受Quincy[11]启发，构建一个从任务到节点的图，但作者为减少调度时间，将两种计算最短路径的算法合并，将全量环境信息同步改为增量同步。让Firmament处理短时间批量任务时快于Quincy，在资源短缺时没有Kubernetes默认调度器超时的问题。

5.总结

本文主要从设计原理、代码实现等层面介绍Kubernetes的调度器以及社区对其的补充加强，总结了Kubernetes调度器的设计原理以及在何种场景如何增强Kubernetes来满足业务需求，提供技术选型的依据和评价标准。
结合这些思路，后续我们将分享在支持业务运行与调度中的一些实践思路，就Kubernetes支持多调度器、多种调度模式（如coscheduling、kubernetes-batch等）、基于多种资源分布和拓扑层面进行必要的扩展层面进行更多的探索与分享。

参考：

[1] 通用调度器的定义：https://en.wikipedia.org/wiki/Scheduling_(computing)
[2] Mesos: https://amplab.cs.berkeley.edu/wp-content/uploads/2011/06/Mesos-A-Platform-for-Fine-Grained-Resource-Sharing-in-the-Data-Center.pdf
[3] Yarn: https://www.cse.ust.hk/~weiwa/teaching/Fall15-COMP6611B/reading_list/YARN.pdf
[4] Borg: https://ai.google/research/pubs/pub43438
[5] Omega: https://ai.google/research/pubs/pub41684
[6] Quincy: https://www.microsoft.com/en-us/research/publication/quincy-fair-scheduling-for-distributed-computing-clusters/
[7] 阿里云伏羲：http://www.vldb.org/pvldb/vol7/p1393-zhang.pdf
[8] Kubernetes调度器策略文件：https://git.k8s.io/examples/staging/scheduler-policy-config.json
[9] Kubernetes调度器扩展接口：https://github.com/kubernetes/kubernetes/blob/9cbccd38598e5e2750d39e183aef21a749275087/pkg/scheduler/algorithm/scheduler_interface.go#L28
[10] Kubernetes调度器算法：https://github.com/kubernetes/kubernetes/blob/9cbccd38598e5e2750d39e183aef21a749275087/pkg/scheduler/core/generic_scheduler.go#L107
[11] Quincy调度器：https://www.microsoft.com/en-us/research/publication/quincy-fair-scheduling-for-distributed-computing-clusters/

作者信息

卢宇亮：任职民生银行云技术管理中心，负责云平台研发和推广工作。毕业于北京理工大学，先后从事DevOps、云计算、微服务领域的产品研发和技术研究工作。

张寿元：任职民生银行云技术管理中心，高级工程师，负责行内云平台建设、落地工作，之前负责行内中间件系统运维工作，超过十五年的IT经验，熟悉软件开发，运维管理等。

刘婉辉：任职民生银行云技术管理中心，负责行内云平台落地、推广等工作，目前致力于容器及容器编排技术研究以及云平台运维管理等。

转自微信公众号：民生运维