一、Kubernetes的调度流程原理与算法详解
众所周知，Kubernetes 是为了管理大规模的集群，当集群的计算节点非常多时，如何为pod寻找合适的node，这也是Kubernetes调度器的工作职责所在。Kubernetes调度器的输入是再调度的pod,经过一系列算法执行之后，为pod选择了合适的node，其输出对于pod资源对象变化而言，yaml文件里spark node name里添加了一个node的值。
Kubernetes default scheduler 的特点：
- 基于队列的调度器
- 一次只调度一个Pod
- 调度时刻全局最优
Kubernetes scheduler架构和调度流程
图中虚线部分为Kubernetes的主要组件 ，包含Informer、调度队列、调度器的cache以及调度主循环。
- Informer通过 list/watch机制获取资源信息变化，更新queue和 cache；
- NextPod() 从待调度队列获取队首的Pod；
- 从cache中获取Node列表；
- 针对Pod和NodeList执行Predicate算法，过滤掉不合适的节点；
- 针对Pod和NodeList执行Priority算法，给节点打分；
- 根据打分，计算出得分最高的节点；
- 当高优先级的Pod没有找到合适的节点时，调度器尝试为其抢占优先级低的Pod；
- 当调度器为Pod选择了一个合适的节点时，通过Bind将Pod和节点进行绑定；
Kubernetes的调度策略与算法
主要有两类算法：Predicate和Priority。Predicate是对于所有的node进行筛选，滤除不合格的节点，Priority是对于Predicate筛选过的node进行打分，挑选最优的节点。通过Predicate策略筛选符合条件的Node，主要是node上不同的pod会存在资源冲突，Predicate主要的目的是为了避免资源冲突、节点超载、端口的冲突等。
典型Predicate算法
典型Priority算法
二、Kubernetes高级调度算法详解
Kubernetes中的Label、Selector机制
很多高级的调度特性都是依赖Selector机制去实现的，Kubernetes通过Label、Selector机制对于集群中的资源对象进行过滤、分类、筛选，类似在SQL使用select语句的效果。
案例：下图有4个pod，每个pod都进行了标记，比如APP=MyApp，代表pod属于哪个App；Phase代表pod属于哪个阶段，是prod还是test；Role代表pod是前端的pod还是后端的pod。
通过”APP=My APP”简单的selector，即可筛选出MyApp应用下的所有pod：
还可以通过”APP=My APP，Role=FE”筛选出MyApp应用里所有前端的pod：
Node Affinity
Node Affinity特性是让Pod在一组指定的Node上运行，下图案例是通过简单的selector机制希望pod能运行在label-key为zone，Value是central的nod
Pod Affinity
Pod Affinity是让Pod与指定Service的一组Pod在相同Node上运行，下图案例是希望serviceA 的pod和serviceB的pod能够调度在同一个区域，区域指定的是topologyKey“zone”，希望serviceA和serviceB的pod能够调度在同一个zone，在node1、node2、node3里，按照zone的value划分，node1属于一个组，node2与node3属于一个区域，因为node2的资源余量不足，serviceA 的pod最终调度在node3上，如此也符合serviceA 和serviceB在zone级别亲和的规则。
若将topologyKey从zone改成hostname,我们希望serviceA 的pod和serviceB的pod能够运行在同一个host上，因为node2没有剩余资源，serviceA没有办法按照这个规则筛选出合适的节点，则serviceA处于不可调度的状态。
Taints-tolerations
Taints-tolerations 是来自Node的反亲和配置，在一些场景里是非常实用的。
案例:有3个节点，node1有GPU资源，首先在集群提交一个普通的node，此时它是可
假设调度到node1,然后提交一个GPU需求的pod，因为node2与node2没有GPU资源，node1有GPU资源，但node1的memory已经耗尽，此时GPU的pod处于不可调度的状态。这个案例其实是不合理的，我们希望能够把有GPU的node1资源留给GPU的pod使用，但并没有达到预期效果。
在这个场景下，非常适合使用Taints
三、华为云CCE Volcano批量调度算法与应用场景详解
云原生批量计算面临的挑战：
1）作业管理缺失
- Pod级别调度，无法感知上层应用
- 缺少作业概念、缺少完善的生命周期的管理
- 缺少任务依赖、作业依赖支持
2）调度策略局限
- 不支持Gang-Scheduling、Fairshaing scheduling
- 不支持多场景的Resource reservation，backfill
- 不支持CPU/IO topology based scheduling
3）领域计算框架支持不足
- 1:1的operator部署运维复杂
- 不同框架对作业管理、并行计算等要求不同
- 计算密集，资源波动大，需要高级调度能力
4）资源规划复用、异构计算支持不足
- 缺少队列概念
- 不支持集群资源的动态规划以及资源复用
- 对异构资源支持不足
Volcano 帮助批量计算面对云原生的各种挑战
- Volcano是业界首个云原生批量计算平台
- 2019年6月上海KubeCon正式开源
- 2020年4月成为CNCF官方项目
- 2021年3月发布1.2版本
- 每3个月一个特性版本，最新版本v1.5.0
Volcano 总体架构和优势
Volcano优势：
- 高性能：提供队列调度、优先级调度、抢占、装箱、资源预留、拓扑调度等丰富的调度策略，在多种场景下提升应用性能
- 智能混合调度：支持在线、离线混合部署调度，提高整体资源利用效率
- 应用感知：感知应用类型和特点，针对大数据、AI、HPC负载提供完善的生命周期管理
- 集群联邦调度：支持多集群调度和作业分发，满足效率优先、成本优先等不同的场景诉求
- 大规模：支持大规模集群调度，单集群规模支持1w节点，100w容器
- 高扩展：插件化算法集成框架，提供两级插件扩展，方便二次开发，满足不同场景诉求
- 易运维：Volcano 作业提供统一接口，避免过多Operator带来的繁杂管理
- 社区成熟：CNCF首个批量计算平台，已支持众多的主流AI、大数
版权声明：本文遵循 CC 4.0 BY-SA 版权协议，若要转载请务必附上原文出处链接及本声明，谢谢合作！ 据、高性能计算框架，众多用户已应用于生产环境。
Volcano支持的一些典型调度算法包括Gang-scheduling、SLA、TDM、Preempt & Reclaim、DRF、FairShare、Task-Topology与MinResource等。
Namespace、Queue fair-share
Namespace与Queue的设计是解耦的关系，同一个namespace可以将任务提交到不同Queue，不同的namespace的任务也可以提交到同一个Queue，用户可以灵活使用。我们提供了3个级别的公平调度机制，Queue不同job之间的公平调度、Queue里不同namespace之间的公平调度与Queue与Queue之间的公平调度。
Task-Topology特性
- 3个作业的执行时间总和; 每个作业带2ps + 4workers
- 默认调度器执行时间波动较大
- 执行时间的提高量依据数据在作业中的比例而定
- 减少 Pod Affinity/Anti-Affinity，提高调度器的整体性能
Spark MinResource
在这个过程中，会存在一些问题：
- Spark driver和executor pod竞争节点资源，overcommit情况下引发死锁。
- 通过为Driver pod和Executor Pod 静态划分Dedicated节点解决，存在碎片率问题
Volcano里提供的MinResource的特性
- 通过为PodGroup预留minResource，防止OverCommit，合理规划并行度，解决资源竞争导致的死锁问题。
- 无需静态规划专有节点，减少资源碎片，相对于静态规划专有节点方案，性能提升30%+
参考文献
[1] https://github.com/volcano-sh/volcano
[2] https://volcano.sh/
[3] https://kubernetes.io/zh/docs/concepts/scheduling-eviction/kube-scheduler/