Kubernetes — 调度系统

阳光穿透心脏的1/2处 2023-10-05 14:08 54阅读 0赞

## 目录 ##

#### 文章目录 ####

*  目录
 *  调度系统
 *  Kubernetes 调度器的设计
 *  Kubernetes 调度器的工作流
 *  Kubernetes 调度系统的未来
 *  Scheduler Extender（调度器扩展）
 *  Multiple Schedulers（多调度器）
 *  Kubernetes Scheduling Framework（调度框架）
 *   *  Scheduling Cycle
     *  Binding Cycle
 *  基于 scheduler-plugins 实现定制化的调度插件
 *  Coscheduling/Gang scheduling
 *   *  为什么需要 Gang Scheduling？
     *  Coscheduling Plugin
 *  Binpack Scheduling
 *   *  为什么需要 Binpack Scheduling？
     *  Binpack Scheduling Plugin

## 调度系统 ##

**通用调度的定义是指**：基于某种方法将某项任务分配到特定资源以完成相关工作，其中任务可以是虚拟计算元素，如线程、进程或数据流，特定资源一般是指处理器、网络、磁盘等，调度器则是完成这些调度行为的具体实现。使用调度器的目的是实现用户共享系统资源的同时，降低等待时间，提高吞吐率以及资源利用率。

构建大规模集群（如数据中心规模）的成本非常之高，因此精心设计调度器就显得尤为重要。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center]

调度器的主要工作是将资源需求与资源提供方做全局最优的匹配。所以一方面调度器的设计需要了解不同类型的资源拓扑，另一方面还需要对工作负载有充分的认识。了解不同类型的资源拓扑，充分掌握环境拓扑信息能够使调度工作更充分的利用资源（如经常访问数据的任务如果距数据近可以显著减少执行时间），并且可以基于资源拓扑信息定义更加复杂的策略。但全局资源信息的维护消耗会限制集群的整体规模和调度执行时间，这也让调度器难以扩展，从而限制集群规模。

另一方面，由于不同类型的工作负载会有不同的甚至截然相反的特性，调度器还需要对工作负载有充分的认识，例如：服务类任务，资源需求少，运行时间长，对调度时间并不敏感；而批处理类任务，资源需求大，运行时间短，任务可能相关，对调度时间要求较高。 同时，调度器也要满足使用方的特殊要求。如任务尽量集中或者分散，保证多个任务同时进行等。

总的来说，好的调度器需要平衡好单次调度（调度时间，质量），同时要考虑到环境变化对调度结果的影响，保持结果最优（必要时重新调度），保证集群规模，同时还要能够支持用户无感知的升级和扩展。调度的结果需要满足但不限于下列条件，并最大可能满足尽可能优先级较高的条件：

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

对于资源的调度，一定会涉及到锁的应用，不同类型锁的选择将直接决定调度器的使用场景。类似 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 在更新时发现对象版本已经变化，则会取消更改。

注：乐观锁和悲观锁是两种思想，用于解决并发场景下的数据竞争问题。

*  **乐观锁**：在操作数据时非常乐观，认为别人不会同时修改数据。因此乐观锁不会上锁，只是在执行更新的时候判断一下在此期间别人是否修改了数据：如果别人修改了数据则放弃操作，否则执行操作。
 *  **悲观锁**：在操作数据时比较悲观，认为别人会同时修改数据。因此操作数据时直接把数据锁住，直到操作完成后才会释放锁；上锁期间其他人不能修改数据。

## Kubernetes 调度器的设计 ##

Kubernetes 的调度设计采用了两层调度架构，基于全局状态进行调度，通过乐观锁控制资源归属，同时支持多调度器。

两层架构帮助调度器屏蔽了很多底层实现细节，将策略和限制分别实现，同时过滤可用资源，让调度器能够更灵活适应资源变化，满足用户个性化的调度需求。相比单体架构而言，不仅更容易添加自定义规则、支持集群动态伸缩，同时对大规模集群有更好的支持（支持多调度器）。

相比于使用悲观锁和部分环境视图的架构，基于全局状态和乐观锁实现的好处是：调度器可以看到集群所有可以支配的资源，然后抢占低优先级任务的资源，以达到策略要求的状态。它的资源分配更符合策略要求，避免了作业囤积资源导致集群死锁的问题。当然这会有抢占任务的开销以及冲突导致的重试，但总体来看资源的使用率更高了。

## Kubernetes 调度器的工作流 ##

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 1]

## Kubernetes 调度系统的未来 ##

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

开发人员希望在 Kubernetes 集群中能像使用 CPU 内存那样简单地声明和使用各种异构设备。

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

## Scheduler Extender（调度器扩展） ##

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 2]

可以发现 Extender 存在以下问题：

1.  调用 Extender 的通信协议是 HTTP，受到网络环境的影响，性能远低于本地的函数调用。同时每次调用都需要将 Pod 和 Node 的信息进行 marshaling 和 unmarshalling 的操作，会进一步降低性能；
2.  扩展点受限，位置比较固定，无法支持灵活的扩展，只能在执行完 Default Filter 策略之后调用。

可见，Scheduler Extender 适用于集群规模较小，调度效率要求不高的场景。但是在大型集群中，Extender 无法支持高吞吐量，性能较差。

## Multiple Schedulers（多调度器） ##

Scheduler 通过监听 Pod 和 Node 的信息，给 Pod 挑选最佳的 Node，更新 Pod 的 spec.NodeName 的信息来将调度结果同步到 Node。所以对于部分有特殊的调度需求的用户，可以通过自研 Custom Scheduler 来完成以上的流程，然后通过和 Default Scheduler 同时部署的方式，来支持自己特殊的调度需求。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 3]

Custom Scheduler 会存在以下问题：

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

## Kubernetes Scheduling Framework（调度框架） ##

从 Kubernetes 1.16 版本开始，社区构建了新一代调度框架 Kubernetes Scheduling Framework V2。

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

Framework 的调度流程是分为两个阶段：

*  Scheduling Cycle：同步执行，同一个时间只有一个 scheduling cycle，是线程安全的；
 *  Binding Cycle：异步执行，同一个时间中可能会有多个 binding cycle在运行，是线程不安全的。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 4]

### Scheduling Cycle ###

Scheduling Cycle 是调度的核心流程，主要的工作是进行调度决策，挑选出唯一的 Node。

1.  **Queue Sort**：Scheduler 中的优先级队列是通过 heap（堆）来实现的，我们可以在 QueueSortPlugin 中定义 heap 的比较函数来决定的优先级排序。需要注意的是，heap 的比较函数同一时刻只能存在一个，即：QueueSort 插件只能 Enable 一个，如果 Enable 了 2 个则 kube-scheduler 在启动时会报错退出。

// 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
    }
    
    // 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))
    }

1.  **PreFilter**：PreFilter 是调度流程启动之前的预处理，可以对 Pod 的信息进行加工。同时 PreFilter 也可以进行一些预置条件的检查，去检查一些集群维度的条件，判断否满足 Pod 的要求。在 Scheduling Cycle 开始时就被调用，只有当所有的 PreFilter 插件都返回 success 时，才能进入下一个阶段。否则，Pod 直接被拒绝掉，此次调度流程失败。
2.  **Filter**：Filter 插件是 Scheduler v1 版本中的 Predicate 的逻辑，用来过滤不满足 Pod 调度要求的 Node。为了提升效率，Filter 的执行顺序可以被配置，这样用户就可以将可以过滤掉大量节点的 Filter 策略放到前边执行，从而减少后续 Filter 策略执行的次数。例如：我们可以把 NodeSelector 的 Filter 放到第一个，从而过滤掉大量的节点。
3.  **PostFilter**：新的 PostFilter 的接口定义在 1.19 的版本发布，用于处理当 Pod 在 Filter 阶段失败后的操作，例如：抢占，Autoscale 触发等行为。
4.  **PreScore**：PreScore 在之前版本称为 PostFilter，现在命名为 PreScore。用于在 Score 之前进行一些信息生成。此处会获取到通过 Filter 阶段的 Node List，我们也可以在此处进行一些信息预处理或者生成一些日志或者监控信息。
5.  **Scoring**：Scoring 扩展点是 Scheduler v1 版本中 Priority 的逻辑。基于 Filter 过滤后剩余的 Node List，根据 Scoring 扩展点定义的策略挑选出最优的节点。Scoring 细分为两个阶段：1）打分：对 Filter 后的 Node List 进行打分，Scheduler 会调用所配置的打分策略；2）归一化：对打分之后的结构在 0-100 之间进行归一化处理。
6.  **Reserve**：Reserve 扩展点是 Scheduler v1 版本的 assume 的操作，此处会对调度结果进行缓存，如果在后边的阶段发生了错误或者失败的情况，会直接进入 Unreserve 阶段，进行数据回滚。
7.  **Permit**：Permit 扩展点是 Framework v2 版本引入的新功能，当 Pod 在 Reserve 阶段完成资源预留之后，Bind 操作之前，开发者可以定义自己的策略在 Permit 节点进行拦截，根据条件对经过此阶段的 Pod 进行 Allow（允许）、Reject（拒绝）和 Wait（等待，可设置超时时间）的 3 种操作。

### Binding Cycle ###

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

1.  **Bind**：Bind 扩展点是 Scheduler v1 版本中的 Bind 操作，会调用 kube-apiserver 提供的接口，将 Pod 绑定到对应的 Node 上。
2.  **PreBind 和 PostBind**：开发者可以在 PreBind 和 PostBind 分别在 Bind 操作前后执行，这两个阶段可以进行一些数据信息的获取和更新。
3.  **UnReserve**：UnReserve 扩展点的功能是用于清理到 Reserve 阶段的的缓存，回滚到初始的状态。当前版本 UnReserve 与 Reserve 是分开定义的，未来会将 UnReserve 与 Reserve 统一到一起，即要求开发者在实现 Reserve 同时需要定义 UnReserve，保证数据能够有效的清理，避免留下脏数据。

## 基于 scheduler-plugins 实现定制化的调度插件 ##

负责 Kube-scheduler 的小组 sig-scheduling 为了更好的管理调度相关的 Plugin，新建了项目 scheduler-plugins 来方便用户管理不同的插件，用户可以直接基于这个项目来定义自己的插件。

QoS 的插件主要基于 Pod 的 QoS Class 来实现的，目的是为了实现调度过程中如果 Pod 的优先级相同时，根据 Pod 的 QoS 来决定调度顺序，调度顺序：

1.  Guaranteed (requests == limits)
2.  Burstable (requests < limits)
3.  BestEffort (requests and limits not set)

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

// QoS Sort 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 Sort 是作用于 QueueSort 的部分，所以我们要实现 QueueSort 接口的函数。如下所示，QueueSortPlugin 接口只定义了一个函数 Less，所以我们实现这个函数即可。

Default QueueSort 在比较的时候，首先比较优先级，然后再比较 Pod 的 timestamp。我们重新定义了 Less 函数，在优先级相同的情况下，通过比较 QoS 来决定优先级。

// 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
    }
    
    // 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
        }
    }

最后，需要在 kube-scheduler 的 main 函数中注册自定义的插件和相应的构造函数：

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)
        }
    }

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

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

## Coscheduling/Gang scheduling ##

Coscheduling 的定义是：在并发系统中将多个相关联的进程调度到不同处理器上同时运行的策略。

在 Coscheduling 的场景中，最主要的原则是保证所有相关联的进程能够同时启动，防止部分进程的异常，导致整个关联进程组的阻塞。这种导致阻塞的部分异常进程，称之为 “碎片（Fragement）”。

在 Coscheduling 的具体实现过程中，根据是否允许 “碎片” 存在，可以细分为：

*  Explicit Coscheduling
 *  Local Coscheduling
 *  Implicit Coscheduling

其中 Explicit Coscheduling 就是大家常听到的 Gang Scheduling，要求完全不允许有 “碎片” 存在， 也就是 “All or Nothing”。

将上述的概念对应到 Kubernetes 中，就是 Kubernetes 的 “批量调度任务” 功能了。一个批任务（关联进程组）包括了 N 个 Pod（进程），Kubernetes Scheduler 负责将这 N 个 Pod 调度到 M 个 Node（处理器）上同时运行。如果这个批任务需要部分的 Pods 同时启动才能被认为是 “可运行” 的，那么我们称需启动 Pods 的最小数量为 min-available。特别地，当 min-available=N 时，批任务要求满足 Gang Scheduling。

### 为什么需要 Gang Scheduling？ ###

Kubernetes Default Scheduler 是以 Pod 为调度单元进行依次调度的，并不考虑 Pod 之间的关联关系。但是很多数据计算类的离线作业具有组合调度的特点，即：要求所有的子任务都能够成功创建后，整个作业才能正常运行。这正是 Gang Scheduling 的场景。

例如：JobA 需要 4 个 Pod 同时启动，才算正常运行。kube-scheduler 依次调度 3 个 Pod 并创建成功，到第 4 个 Pod 时，集群资源不足，则 JobA 的 3 个 Pod 处于空等的状态。但是它们已经占用了部分资源，如果第 4 个 Pod 不能及时启动的话，整个 JobA 无法成功运行，更糟糕的是导致集群资源浪费。

更坏的情况是：集群其他的资源刚好被 JobB 的 3 个 Pod 所占用，同时在等待 JobB 的第 4 个 Pod 创建，此时整个集群就出现了死锁。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 5]

对此，社区目前有 Kube-batch 以及基于 Kube-batch 衍生的 Volcano 项目来解决这一问题。实现的方式是通过开发新的调度器将 Scheduler 中的调度单元从 Pod 修改为 PodGroup，以组的形式进行调度。使用方式是如果需要 Coscheduling 功能的 Pod 走 New Scheduler，而其他的 Pod 走 Default Scheduler 进行调度。

这些方案虽然能够解决 Coscheduling 的问题，但是同样引入了新的问题。对于同一集群资源的调度是需要具备中心化特性的。如果同时存在两个调度器的话，就有可能会出现决策冲突，例如：出现分别将同一块资源分配给两个不同的 Pod 的情况。解决的方式往往是通过 Label 将 Node 划分成两个不同的 Pool，或者部署多个集群。然而，这种方式势必会导致整体集群资源的浪费以及运维成本的增加。

再者，Volcano 运行需要启动定制的 MutatingAdmissionWebhook 和 ValidatingAdmissionWebhook。这些 Webhooks 本身存在单点风险，一旦出现故障，将影响集群内所有 Pod 的创建。另外，多运行一套调度器，本身也会带来维护上的复杂性，以及与上游 kube-scheduler 接口兼容上的不确定性。

### Coscheduling Plugin ###

一个全新的方案是基于 scheduler-plugins 来实现的 Coscheduling Plugin。

1.  **定义 PodGroup**：通过 Label 来定义 PodGroup 的概念，拥有同样 Label 的 Pod 同属于一个 PodGroup。min-available 是用来标识该 PodGroup 的作业能够正式运行时所需要的最小副本数。

labels:
         pod-group.scheduling.sigs.k8s.io/name: tf-smoke-gpu
         pod-group.scheduling.sigs.k8s.io/min-available: "2"

*  pod-group.scheduling.sigs.k8s.io/name：用于表示 PodGroup 的 Name；
 *  pod-group.scheduling.sigs.k8s.io/min-available：用于表示当前集群资源至少满足 min-available 个 pod 启动时，才能整体调度该任务。

注: 要求属于同一个 PodGroup 的 Pod 必须保持相同的优先级

1.  **Permit**：Permit 插件提供了延迟绑定的功能，即 Pod 进入到 Permit 阶段时，用户可以自定义条件来 Allow（允许）、Reject（拒绝）和 Wait（等待，可设置超时时间）。Permit 的延迟绑定的功能刚好可以让属于同一个 PodGruop 的 Pod 调度到这个节点时，进行等待，等待积累的 Pod 数目满足足够的数目时，再统一运行同一个 PodGruop 的所有 Pod 进行绑定并创建。

例如：当 JobA 调度时，需要 4 个 Pod 同时启动，才能正常运行。但此时集群仅能满足 3 个 Pod 创建，此时与 Default Scheduler 不同的是，并不是直接将 3 个 Pod 调度并创建。而是通过 Framework 的 Permit 机制进行等待。当集群中有空闲资源被释放后，JobA 的中 Pod 所需要的资源均可以满足。则 JobA 的 4 个 Pod 被一起调度创建出来，正常运行任务。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 6]

1.  **QueueSort**：由于 Default Scheduler 的队列并不能感知 PodGroup 的信息，所以 PodGroup 的 Pods 在出队时会处于无序性。当一个新的 Pod 创建后，入队后，无法跟与其相同的 PodGroup 的 Pod 排列在一起，只能继续以混乱的形式交错排列。这种无序性就会导致如果 PodGroupA 在 Permit 阶段处于等待状态，此时 PodGroupB 的 Pod 调度完成后也处于等待状态，相互占有资源使得 PodGroupA 和 PodGroupB 均无法正常调度。这种情况即是把死锁现象出现的位置从 Node 节点移动到 Permit 阶段，无法解决前文提到的问题。针对这个问题，可以通过实现 QueueSort 插件，保证在队列中属于同一个 PodGroup 的 Pod 能够排列在一起。我们通过定义 QueueSort 所用的 Less 方法，作用于 Pod 在入队后排队的顺序：

func  Less(podA *PodInfo, podB *PodInfo) bool

*  首先，继承了默认的基于优先级的比较方式，高优先级的 Pod 会排在低优先级的 Pod 之前。
 *  然后，如果两个 Pod 的优先级相同，我们定义了新的排队逻辑来支持 PodGroup 的排序。
    
     *  如果两个 Pod 都是 regularPod（普通 Pod），则谁先创建，谁在队列里边排在前边；
     *  如果两个 Pod 一个是 regularPod，另一个是 pgPod（属于某个 PodGroup 的 Pod），我们比较的是 regularPod 的创建时间和 pgPod 所属 PodGroup 的创建时间，则谁先创建谁在队列里边排在前边；
     *  如果两个 Pod 都是 pgPod，我们比较两个 PodGroup 的创建时间，则谁先创建谁在队列里边排在前边。同时有可能两个 PodGroup 的创建时间相同，我们引入了自增 ID，使得 PodGroup 的 ID 谁小谁排在前边，目的是为了区分不同的 PodGroup。

通过如上的排队策略，实现了属于同一个 PodGroup 的 Pod 能够同一个 PodGroup 的 Pod 能够排列在一起。当一个新的 Pod 创建后，入队后，会跟与其相同的 PodGroup 的 Pod 排列在一起。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 7]

1.  **Prefilter**：为了减少无效的调度操作，提升调度的性能，在 Prefilter 阶段增加了一个过滤条件，当一个 Pod 调度时，会计算该 Pod 所属 PodGroup 的 Pod 的 Sum（包括 Running 状态的），如果 Sum 小于 min-available 时，则肯定无法满足 min-available 的要求，则直接在 Prefilter 阶段拒绝掉，不再进入调度的主流程。
2.  **UnReserve**：如果某个 Pod 在 Permit 阶段等待超时了，则会进入到 UnReserve 阶段，会直接拒绝掉所有跟 Pod 属于同一个 PodGroup 的 Pod，避免剩余的 Pod 进行长时间的无效等待。

**部署 Coscheduling Plugin**：

$  wget http://kubeflow.oss-cn-beijing.aliyuncs.com/ack-coscheduling.tar.gz
    $  tar zxvf ack-coscheduling.tar.gz
    $  helm install ack-coscheduling -n kube-system ./ack-coscheduling
    NAME: ack-coscheduling
    LAST DEPLOYED: Mon Apr 13 16:03:57 2020
    NAMESPACE: kube-system
    STATUS: deployed
    REVISION: 1
    TEST SUITE: None

**验证 Coscheduling Plugin**：

$ helm get manifest ack-coscheduling -n kube-system | kubectl get -n kube-system -f -
    NAME                           COMPLETIONS   DURATION   AGE
    scheduler-update-clusterrole   1/1           8s         35s
    scheduler-update               3/1 of 3      8s         35s

**卸载 Coscheduling Plugin**：

$ helm uninstall ack-coscheduling -n kube-system

## Binpack Scheduling ##

### 为什么需要 Binpack Scheduling？ ###

Kubernetes 默认开启的资源调度策略是 LeastRequestedPriority，消耗的资源最少的节点会优先被调度，使得整体集群的资源使用在所有节点之间分配地相对均匀。但是这种调度策略往往也会在单个节点上产生较多资源碎片。

如下这种情况情况，每个 Node 都有 1 个 GPU 卡空闲，可是又无法被利用，导致资源 GPU 这种昂贵的资源被浪费。如果使用的资源调度策略是 Binpack（装箱），优先将节点资源填满之后，再调度下一个节点，则上图所出现的资源碎片问题得到解决。申请 2GPU 的作业被正常调度到节点上，提升了集群的资源使用率。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 8]

### Binpack Scheduling Plugin ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 9]

Binpack 实现已经抽象成 Kubernetes Scheduler Framework 的 Score 插件 RequestedToCapacityRatio，用于优选阶段给 Node 打分。将 Node 根据自己定义的配置进行打分。具体的实现可以分为两个部分：构建打分函数、打分。

1.  构建打分函数就是用户可以自定义不同的利用率所对应的分值大小，以便影响调度的决策过程。

如果用户设定的对应方式如下所示，即：如果资源利用率为 0 的时候，得分为 0 分，当资源利用率为 100 时，得分为 10 分，所以得到的资源利用率越高，得分越高，则这个行为是 Binpack 的资源分配方式。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 10]  
用户也可以设置成利用率为 0 时，得分为 10 分，利用率为 100 时，得分为 0 分。这样意味着资源利用率越低，则得分越高，这种行为是 spreading（展开）的资源分配方式。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 11]

用户除了 2 个点之外也可以新增更多的点，对应关系可以不是线性的关系，例如：可以标识资源利用率为 50 时，得分为 8，则会将打分分割为两个区间: 0-50 和 50-100。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 12]

1.  打分：用户可以自己定义在 Binpack 计算中所要参考的资源以及权重值，例如：可以只是设定 GPU 和 CPU 的值和权重。

resourcetoweightmap: 
        "cpu": 1
        "nvidia.com/gpu": 1

然后在打分过程中，通过计算 `(pod.Request + node.Allocated)/node.Total` 的结果得到对应资源的利用率，并且将利用率带入上文中所述的打分函数中，得到相应的分数。最后将所有的资源根据 weight 值，加权得到最终的分数。

Score = line(resource1_utilization) * weight1 + line(resource2_utilization) * weight2 ....) / (weight1 + weight2 ....)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201122144024426.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201122144938382.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2020112213191334.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201122132244286.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201122131440150.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201122135914956.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201122140710690.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20201122141108878.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20201122141629997.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20201122141727542.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20201122142023754.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20201122142058228.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr_size_16_color_FFFFFF_t_70_pic_center 12]: https://img-blog.csdnimg.cn/20201122142125476.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ptaWxr,size_16,color_FFFFFF,t_70#pic_center