进击的Kubernetes调度系统（一）：Scheduling Framework
进击的Kubernetes调度系统（二）：支持批任务的Coscheduling/Gang scheduling

作者：王庆璨张凯

前言

Kubernetes已经成为目前事实标准上的容器集群管理平台。它为容器化应用提供了自动化部署、运维、资源调度等全生命周期管理功能。经过3年多的快速发展，Kubernetes在稳定性、扩展性和规模化方面都有了长足进步。尤其是Kubernetes控制平面的核心组件日臻成熟。而作为决定容器能否在集群中运行的调度器Kube-scheduler，更是由于长久以来表现稳定，且已能满足大部分Pod调度场景，逐渐不被开发人员特别关注。

伴随着Kubernetes在公有云以及企业内部IT系统中广泛应用，越来越多的开发人员尝试使用Kubernetes运行和管理Web应用和微服务以外的工作负载。典型场景包括机器学习和深度学习训练任务，高性能计算作业，基因计算工作流，甚至是传统的大数据处理任务。此外，Kubernetes集群所管理的资源类型也愈加丰富，不仅有GPU，TPU和FPGA，RDMA高性能网络，还有针对领域任务的各种定制加速器，比如各种AI芯片，NPU，视频编解码器等。开发人员希望在Kubernetes集群中能像使用CPU和内存那样简单地声明式使用各种异构设备。

总的来说，围绕Kubernetes构建一个容器服务平台，统一管理各种新算力资源，弹性运行多种类型应用，最终把服务按需交付到各种运行环境（包括公共云、数据中心、边缘节点，甚至是终端设备），已然成为云原生技术的发展趋势。

阿里云容器服务团队结合多年Kubernetes产品化与客户支持经验，对Kube-scheduler进行了大量扩展和改进，逐步使其在多种场景下依然能稳定、高效地调度复杂工作负载类型。

《进击的Kubernetes调度系统》系列文章将把我们的经验、技术思考和实现细节全面地展现给Kubernetes用户和开发者，期望帮助大家更好地了解Kubernetes调度系统的强大能力和未来发展方向。

早期方案

首先，让我们来了解一下Kubernetes社区都有过哪些提升调度器扩展能力的方案。

要统一管理和调度异构资源与更多复杂工作负载类型，首先面对挑战的就是Kube-scheduler。在Kubernetes社区里关于提升调度器扩展能力的讨论一直不断。sig-scheduling给出的判断是，越多功能加入，使得调度器代码量庞大，逻辑复杂，导致维护的难度越来越大，很多bug难以发现、处理。而对于使用了自定义调度的用户来说，跟上每一次调度器功能更新，都充满挑战。

在阿里云，我们的用户遇到了同样的挑战。Kubernetes原生调度器循环处理单个Pod容器的固定逻辑，无法及时、简单地支持用户在不同场景的需求。所以针对特定的场景，我们会基于原生Kube-scheduler扩展自己的调度策略。

最初对于Kube-scheduler进行扩展的方式主要有两种，一种是调度器扩展（Scheduler Extender），另外一种是多调度器（Multiple schedulers）。接下来我们对这两种方式分别进行介绍和对比。

Scheduler Extender

社区最初提供的方案是通过Extender的形式来扩展scheduler。Extender是外部服务，支持Filter、Preempt、Prioritize和Bind的扩展，scheduler运行到相应阶段时，通过调用Extender注册的webhook来运行扩展的逻辑，影响调度流程中各阶段的决策结果。

以Filter阶段举例，执行过程会经过2个阶段:

scheduler会先执行内置的Filter策略，如果执行失败的话，会直接标识Pod调度失败。
如何内置的Filter策略执行成功的话，scheduler通过Http调用Extender注册的webhook, 将调度所需要的Pod和Node的信息发送到到Extender，根据返回filter结果，作为最终结果。

我们可以发现Extender存在以下问题:

调用Extender的接口是HTTP请求，受到网络环境的影响，性能远低于本地的函数调用。同时每次调用都需要将Pod和Node的信息进行marshaling和unmarshalling的操作，会进一步降低性能。
用户可以扩展的点比较有限，位置比较固定，无法支持灵活的扩展，例如只能在执行完默认的Filter策略后才能调用。

基于以上介绍，Extender的方式在集群规模较小，调度效率要求不高的情况下，是一个灵活可用的扩展方案，但是在正常生产环境的大型集群中，Extender无法支持高吞吐量，性能较差。

Multiple schedulers

Scheduler在Kubernetes集群中其实类似于一个特殊的Controller，通过监听Pod和Node的信息，给Pod挑选最佳的节点，更新Pod的spec.NodeName的信息来将调度结果同步到节点。所以对于部分有特殊的调度需求的用户，有些开发者通过自研Custom Scheduler来完成以上的流程，然后通过和default scheduler同时部署的方式，来支持自己特殊的调度需求。

Custom Scheduler会存在一下问题：

如果与default scheduler同时部署，因为每个调度器所看到的资源视图都是全局的，所以在调度决策中可能会在同一时刻在同一个节点资源上调度不同的Pod，导致节点资源冲突的问题。
有些用户将调度器所能调度的资源通过Label划分不同的池子，可以避免资源冲突的现象出现。但是这样又会导致整体集群资源利用率的下降。
有些用户选择通过完全自研的方式来替换default scheduler，这种会带来比较高的研发成本，以及Kubernetes版本升级后可能存在的兼容性问题。

Scheduler Extender的性能较差可是维护成本较小，Custom Scheduler的研发和维护的成本特别高但是性能较好，这种情况是开发者面临这种两难处境。这时候Kubernetes Scheduling Framework V2横空出世，给我们带来鱼和熊掌可以兼得的方案。

新一代调度框架 Scheduling Framework之解析

社区也逐渐的发现开发者所面临的困境，为了解决如上问题，使Kube-scheduler扩展性更好、代码更简洁，社区从Kubernetes 1.16版本开始, 构建了一种新的调度框架Kubernetes Scheduling Framework的机制。

Scheduling Framework在原有的调度流程中, 定义了丰富扩展点接口，开发者可以通过实现扩展点所定义的接口来实现插件，将插件注册到扩展点。Scheduling Framework在执行调度流程时，运行到相应的扩展点时，会调用用户注册的插件，影响调度决策的结果。通过这种方式来将用户的调度逻辑集成到Scheduling Framework中。

Framework的调度流程是分为两个阶段scheduling cycle和binding cycle. scheduling cycle是同步执行的，同一个时间只有一个scheduling cycle，是线程安全的。binding cycle是异步执行的，同一个时间中可能会有多个binding cycle在运行，是线程不安全的。

scheduling cycle

scheduling cycle是调度的核心流程，主要的工作是进行调度决策，挑选出唯一的节点。

Queue sort

// QueueSortPlugin is an interface that must be implemented by "QueueSort" plugins.
// These plugins are used to sort pods in the scheduling queue. Only one queue sort
// plugin may be enabled at a time.
type QueueSortPlugin interface {
    Plugin
    // Less are used to sort pods in the scheduling queue.
    Less(*PodInfo, *PodInfo) bool
}

Scheduler中的优先级队列是通过heap实现的，我们可以在QueueSortPlugin中定义heap的比较函数来决定的排序结构。但是需要注意的是heap的比较函数在同一时刻只有一个，所以QueueSort插件只能Enable一个，如果用户Enable了2个则调度器启动时会报错退出。下面是默认的比较函数，可供参考。

// Less is the function used by the activeQ heap algorithm to sort pods.
// It sorts pods based on their priority. When priorities are equal, it uses
// PodQueueInfo.timestamp.
func (pl *PrioritySort) Less(pInfo1, pInfo2 *framework.QueuedPodInfo) bool {
    p1 := pod.GetPodPriority(pInfo1.Pod)
    p2 := pod.GetPodPriority(pInfo2.Pod)
    return (p1 > p2) || (p1 == p2 && pInfo1.Timestamp.Before(pInfo2.Timestamp))
}

PreFilter

PreFilter在scheduling cycle开始时就被调用，只有当所有的PreFilter插件都返回success时，才能进入下一个阶段，否则Pod将会被拒绝掉，标识此次调度流程失败。PreFilter类似于调度流程启动之前的预处理，可以对Pod的信息进行加工。同时PreFilter也可以进行一些预置条件的检查，去检查一些集群维度的条件，判断否满足pod的要求。

Filter

Filter插件是scheduler v1版本中的Predicate的逻辑，用来过滤掉不满足Pod调度要求的节点。为了提升效率，Filter的执行顺序可以被配置，这样用户就可以将可以过滤掉大量节点的Filter策略放到前边执行，从而减少后边Filter策略执行的次数，例如我们可以把NodeSelector的Filter放到第一个，从而过滤掉大量的节点。Node节点执行Filter策略是并发执行的，所以在同一调度周期中多次调用过滤器。

PostFilter

新的PostFilter的接口定义在1.19的版本会发布，主要是用于处理当Pod在Filter阶段失败后的操作，例如抢占，Autoscale触发等行为。

PreScore

PreScore在之前版本称为PostFilter，现在修改为PreScore，主要用于在Score之前进行一些信息生成。此处会获取到通过Filter阶段的节点列表，我们也可以在此处进行一些信息预处理或者生成一些日志或者监控信息。

Scoring

Scoring扩展点是scheduler v1版本中Priority的逻辑，目的是为了基于Filter过滤后的剩余节点，根据Scoring扩展点定义的策略挑选出最优的节点。
Scoring扩展点分为两个阶段：

打分：打分阶段会对Filter后的节点进行打分，scheduler会调用所配置的打分策略
归一化: 对打分之后的结构在0-100之间进行归一化处理

Reserve

Reserve扩展点是scheduler v1版本的assume的操作，此处会对调度结果进行缓存，如果在后边的阶段发生了错误或者失败的情况，会直接进入Unreserve阶段，进行数据回滚。

Permit

Permit扩展点是framework v2版本引入的新功能，当Pod在Reserve阶段完成资源预留之后，Bind操作之前，开发者可以定义自己的策略在Permit节点进行拦截，根据条件对经过此阶段的Pod进行allow、reject和wait的3种操作。allow表示pod允许通过Permit阶段。reject表示pod被Permit阶段拒绝，则Pod调度失败。wait表示将Pod处于等待状态，开发者可以设置超时时间。

binding cycle

binding cycle需要调用apiserver的接口，耗时较长，为了提高调度的效率，需要异步执行，所以此阶段线程不安全。

Bind

Bind扩展点是scheduler v1版本中的Bind操作，会调用apiserver提供的接口，将pod绑定到对应的节点上。

PreBind 和 PostBind

开发者可以在PreBind 和 PostBind分别在Bind操作前后执行，这两个阶段可以进行一些数据信息的获取和更新。

UnReserve

UnReserve扩展点的功能是用于清理到Reserve阶段的的缓存，回滚到初始的状态。当前版本UnReserve与Reserve是分开定义的，未来会将UnReserve与Reserve统一到一起，即要求开发者在实现Reserve同时需要定义UnReserve，保证数据能够有效的清理，避免留下脏数据。

实现自己的调度插件

scheduler-plugins

Kubernetes负责Kube-scheduler的小组sig-scheduling为了更好的管理调度相关的Plugin，新建了项目scheduler-plugins 来方便用户管理不同的插件，用户可以直接基于这个项目来定义自己的插件。接下来我们以其中的Qos的插件来为例，演示是如何开发自己的插件。

QoS的插件主要基于Pod的 QoS(Quality of Service) class 来实现的，目的是为了实现调度过程中如果Pod的优先级相同时，根据Pod的Qos来决定调度顺序，调度顺序是: 1. Guaranteed (requests == limits) 2. Burstable (requests < limits) 3. BestEffort (requests and limits not set)

插件构造

首先插件要定义插件的对象和构造函数

// QoSSort is a plugin that implements QoS class based sorting.
type Sort struct{}

// New initializes a new plugin and returns it.
func New(_ *runtime.Unknown, _ framework.FrameworkHandle) (framework.Plugin, error) {
    return &Sort{}, nil
}

然后，根据我们插件要对应的extention point来实现对应的接口，Qos是作用于QueueSort的部分，所以我们要实现QueueSort接口的函数。如下所示，QueueSortPlugin接口只定义了一个函数Less，所以我们实现这个函数即可。

// QueueSortPlugin is an interface that must be implemented by "QueueSort" plugins.
// These plugins are used to sort pods in the scheduling queue. Only one queue sort
// plugin may be enabled at a time.
type QueueSortPlugin interface {
    Plugin
    // Less are used to sort pods in the scheduling queue.
    Less(*PodInfo, *PodInfo) bool
}

实现的函数如下。默认的default QueueSort在比较的时候，首先比较优先级，然后再比较pod的timestamp。我们重新定义了Less函数，在优先级相同的情况下，通过比较Qos来决定优先级。

// Less is the function used by the activeQ heap algorithm to sort pods.
// It sorts pods based on their priority. When priorities are equal, it uses
// PodInfo.timestamp.
func (*Sort) Less(pInfo1, pInfo2 *framework.PodInfo) bool {
    p1 := pod.GetPodPriority(pInfo1.Pod)
    p2 := pod.GetPodPriority(pInfo2.Pod)
    return (p1 > p2) || (p1 == p2 && compQOS(pInfo1.Pod, pInfo2.Pod))
}

func compQOS(p1, p2 *v1.Pod) bool {
    p1QOS, p2QOS := v1qos.GetPodQOS(p1), v1qos.GetPodQOS(p2)
    if p1QOS == v1.PodQOSGuaranteed {
        return true
    } else if p1QOS == v1.PodQOSBurstable {
        return p2QOS != v1.PodQOSGuaranteed
    } else {
        return p2QOS == v1.PodQOSBestEffort
    }
}

插件注册

我们在启动的main函数中注册自己定义的插件和相应的构造函数

// cmd/main.go
func main() {
    rand.Seed(time.Now().UnixNano())
    command := app.NewSchedulerCommand(
        app.WithPlugin(qos.Name, qos.New),
    )
    if err := command.Execute(); err != nil {
        os.Exit(1)
    }
}

代码编译

$ make

Scheduler启动

kube-scheduler启动时，配置./manifests/qos/scheduler-config.yaml中kubeconfig的路径，启动时传入集群的kubeconfig文件以及插件的配置文件即可。

$ bin/kube-scheduler --kubeconfig=scheduler.conf --config=./manifests/qos/scheduler-config.yaml

至此，相信大家已经通过我们的介绍和示例了解了Kubernetes Scheduling Framework的架构和开发方法。

后续工作

Kubernetes Scheduling Framework作为调度器的新架构方向，在可扩展性和定制化方面进步很大。基于此Kubernetes可以逐步承载更多类型的应用负载了, 一个平台一套IT架构和技术堆栈的愿景向前演进。同时为了更好的支持数据计算类型的任务迁移到Kubernetes平台中，我们也在努力将数据计算类型中常用Coscheduling／Gang Scheduling、Capacity Scheduling、Dominant Resource Fairness和多队列管理等特性，通过Scheduling Framework的插件机制来融入到原生的Kube-scheduler中。
接下来，本系列文章将围绕AI、大数据处理和高规格计算资源集群等场景，介绍我们是如何开发相应调度器插件的。敬请期待。

进击的Kubernetes调度系统（一）：Scheduling Framework

前言