scheduler-设计与实现

目标

调度器的核心目标是: 将 workload bind 到 resource【workload --bind--> resource】，结合各类信息，将这一目标做到最优。

历史

其他补充：

1. mesos 的出现有其历史背景：mesos 出现在 hadoop 等框架出现不久而且在快速进化的过程中，多个框架混用一个集群提高资源利用效率是其想要解决的主要问题；而"大一统" 的框架一是由于复杂，二是由于难以满足各种框架快速发展的要求，三是各种框架本身就有复杂的调度逻辑，移植到统一大框架工作量巨大。所以 mesos 提出的是 两级模型 的思路，提供一个 thin layer，进行上层的 resource offer, 再委托给 具体的 framework 进行更细致的调度。然而这个目标实现得似乎并不成功，mesos下最成功的框架是 Marathon, 用于管理容器应用 (这是 kubernetes的强项), 而目标想要纳入的 hadoop/yarn 等框架却没有被成功的融入, 比如 myriad 目标是让 yarn 跑在 mesos 上，这个项目似乎没有被大规模采用, Spark 支持直接运行在 mesos 上，但是随着 kubernetes 的兴起和 spark 对 kubernetes的支持，对 spark on kubernetes 的搜索热度也高于 on mesos.
2. mesos resource offer 的流程: - Slave1 向 Master 报告，有4个CPU和4 GB内存可用 - Master 发送一个 Resource Offer 给 Framework1 来描述 Slave1 有多少可用资源 (图里面没有体现的两个细节：1. FrameWork 可以 reject Resource Offer，因为资源不满足需求；2. FrameWork 可以带一些 filter 参数，提高 master resource offer 的效率) - FrameWork1 中的 FW Scheduler会答复 Master，我有两个 Task 需要运行在 Slave1，一个 Task 需要<2个CPU，1 GB内存=””>，另外一个Task需要<1个CPU，2 GB内存=””> - 最后，Master 发送这些 Tasks 给 Slave1。然后，Slave1还有1个CPU和1 GB内存没有使用，所以分配模块可以把这些资源提供给 Framework2
   

   image
3. omega 的提出是为了解决 mesos 的一些问题，比如只对短时任务的效果比较好；framwork 没有全局视角（看不到 all cluster state），因此很难实现抢占或其他一些需要了解全局资源和 peer framwork的调度。和 mesos 的主要不同是让 scheduler 自己决策，而不是约束框架，然后用一种乐观的方式来解决冲突。
4. omega 的评估使用的是模拟的结果，他的实际意义有点可疑。omega 看上去是一个将复杂问题简化的好办法，但是实际应用也容易受质疑：缺乏全局的 policy 的能力真的可接受吗，比如 Fairness。preemption 看上去很难实现，比如 service job 的优先级一般较高，但是 service job 对 batch job 无感知，怎么做 preemption 呢？
5. borg 中的概念和 kubernetes 非常相似，论文中描述的实现方式也和 kubernetes 的实现基本相同。比如：描述性的语法，Quota 管理，准入控制，健康检查，调度方式等等，在 k8s 中均得到了体现。borg 作为一个内部使用的调度系统更为全面和细致，而 kubernetes 作为一个专注于调度的系统并没有携带如日志、监控、账号等方案，而是要用户自行搭配。从核心部分来看 k8s 继承了 borg 的一些先进理念，并修复了其中的设计问题(如 group workload 的方式单一； 任务总是共享机器 ip；复杂的 api-其实kubernetes 的api 也在变得非常复杂)，有理由相信，k8s 至少和 borg 一样先进。
6. borg 中的 borglet 使用一种 stateless link shard 的组件来降低 borglet 对于 master 更新机器资源的压力，而这种 节点 agent 和 master 之间的压力在 kubernetes 中也很大。在 kubernetes 使用 nodeRelease/bookmark 等机制优化这种压力。
7. borg 对于调度的压力提出了一些优化策略，如 Score caching（缓存打分结果，出发 node 和 task 有变化）; Equivalence classes （同样需求的一组 task 只打分一次）; Relaxed randomization(寻找局部最优解)

任务的属性

1. 优先级/稳定性要求 （多大程度允许被抢占/重新调度）：
   • 优先级抢占的基础。优先级的划分应该被很好的定义，考虑这样一种情况，高优先级的任务 a 抢占了优先级稍微低一些的任务 b，任务b被重新调度，又可能去抢占优先级更低的任务 c，带来了任务的不稳定。
   • 低优先级的 quota 被 oversell 有助于提高资源的整体利用率
2. Locality 要求:
   • 希望 node 属于/不属于 nodeList a (或者 node 有某种特殊标签或者属性) (在 kubernetes 中叫做 nodeAffinity/node-AntiAffinity)
   • 希望 node 上面没有/有 某种属性的 workload (在 kubernetes 中叫做 podAffinity/podAntiAffinity)
3. 资源需求/隔离性需求
   • 资源需求消耗 quota
   • 资源的需求有多种类别，这些资源需求的影响会影响 Locality
   • 资源的需求可能是 mandatory的 也可能是 preferred的，举个例子，一些任务可能必须要 gpu 才能允许，另一些任务则是希望最好有 gpu，没有也能接受
   • 尽管调度的单位一般是 node，但是：
     • 资源的需求不一定是 node 关联的资源，比如云盘
     • 资源的需求可能比 node 更细节，比如希望有多个 cpu core 并且在同一 numa node
4. Gang 要求：
   • 需要至少 R*n 的资源才能被调度，如 mpi 任务
   • 还是少量资源也可以运行，逐步调度，如 无状态多副本服务，Hadoop 任务
5. 资源需求是否会动态变化：一段时间的 warm up 之后需求更多的资源（横向扩容和纵向扩容，对于调度器来说，横行扩容似乎可以转换为单实例的调度问题，但是纵向扩容调度器不得不重新有感知的介入）
6. 任务的预期运行时间/需求的调度时间（紧急程度）:
   • 比如 service job (这里采用 omega 里面的分类 service job / batch job) 的运行时间一般比较长，那么对于调度时间的要求并不高，相反的，花费更多时间得到一个最好的决策更重要，因为这个决策可能影响 service job 运行几周甚至几个月.
   • 任务预期运行时间和 quota 以及优先级都有关系，预期会长时间运行的任务可能支付更多费用，也更希望被稳定的运行

集群视角

1. 如何分布 workload
   • 希望均匀分布资源需求还是尽可能的集中/或者在某部分集中？（均匀分布有利于得到高的资源利用率和更好的决策，对于 burstable 的任务也更友好，缺点是可能带来资源碎片，比如需要使用整台机器资源的任务可能无法被调度，而且在云环境下，部分集中的策略有利于节点资源的弹性伸缩，好的分布策略应该是两者的结合）
   • 是否需要对大集群进行逻辑分区，以便得到更好的决策？
2. 资源预留 （以及预期资源利用率）

实现

这部分可以参考 kubernetes 1.15 之后的 scheduer 新实现

1. 配额: 配额是用于评估 workload 能否被 admit 的判断条件，因此他的执行优先级比较高，即条件不满足就直接 reject，不进入后面的排序计算环节
2. 调度阶段：在kubernetes 新的调度器实现中，调度被分成了两个主要的 cycle 【sheduling cycle; binding cycle】 每个 cycle 有若干阶段， 定义了丰富扩展点接口，开发者可以通过实现扩展点所定义的接口来实现插件，将插件注册到扩展点。 - sheduling cycle - Queue sort：优先排序，QueueSort插件只能Enable一个 - PreFilter：PreFilter类似于调度流程启动之前的预处理，可以对Pod的信息进行加工。同时PreFilter也可以进行一些预置条件的检查，去检查一些集群维度的条件，判断否满足pod的要求 - Filter：Filter插件是scheduler v1版本中的Predicate的逻辑，用来过滤掉不满足Pod调度要求的节点。为了提升效率，Filter的执行顺序可以被配置，这样用户就可以将可以过滤掉大量节点的Filter策略放到前边执行，从而减少后边Filter策略执行的次数，例如我们可以把NodeSelector的Filter放到第一个，从而过滤掉大量的节点。Node节点执行Filter策略是并发执行的，所以在同一调度周期中多次调用过滤器 - PostFilter：用于处理当Pod在Filter阶段失败后的操作，例如抢占，Autoscale触发等行为。 - PreScore：主要用于在Score之前进行一些信息生成。此处会获取到通过Filter阶段的节点列表，我们也可以在此处进行一些信息预处理或者生成一些日志或者监控信息。 - Scoring：根据 Scoring 扩展点定义的策略挑选出最优的节点。分为打分和归一化两个阶段 - Reserve：此处会对调度结果进行缓存，如果在后边的阶段发生了错误或者失败的情况，会直接进入Unreserve阶段，进行数据回滚 - Permit：开发者可以定义自己的策略在Permit节点进行拦截，根据条件对经过此阶段的Pod进行allow、reject和wait的3种操作 - binding cycle - PreBind: 预绑定插件用于执行 Pod 绑定前所需的任何工作。例如，一个预绑定插件可能需要提供网络卷并且在允许 Pod 运行在该节点之前将其挂载到目标节点上 - Bind: 调用apiserver提供的接口，将pod绑定到对应的节点上 - PostBind: 这是个信息性的扩展点。绑定后插件在 Pod 成功绑定后被调用。这是绑定周期的结尾，可用于清理相关的资源
   

   image
3. 过滤/打分策略，这些策略在新的 kubernetes sheduler 实现中以内置插件的形式被体现。如果有其他打分策略的需求可以参考实现自定义的插件。内置的 过滤/打分插件可以分为几类
   • 过滤出满足资源/标签条件的节点，比如 nodeName, label, cpu, 磁盘，cpu 内存等: 这类插件包括:
     • TaintToleration: 污点和容忍
     • NodeName：检查 Pod 指定的节点名称与当前节点是否匹配
     • NodePorts：检查 Pod 请求的端口在节点上是否可用
     • NodeUnschedulable：过滤 .spec.unschedulable 值为 true 的节点
     • NodeResourcesFit：检查节点是否拥有 Pod 请求的所有资源
     • NodeResourceLimits：选择满足 Pod 资源限制的节点
     • VolumeBinding：检查节点是否有请求的卷，或是否可以绑定请求的卷，类似的有 VolumeRestrictions/VolumeZone/NodeVolumeLimits/EBSLimits/GCEPDLimits/AzureDiskLimits/CinderVolume
     • NodeLabel：根据配置的 标签 过滤节点和/或给节点打分
   • 根据及节点亲和性/Pod 亲和性/ SelectorSpread/ 资源的亲和性 等策略影响 workload 的分配布局:
     • SelectorSpread: 对于属于 Services、 ReplicaSets 和 StatefulSets 的 Pod，偏好跨多个节点部
     • NodePreferAvoidPods: 基于节点的 注解 scheduler.alpha.kubernetes.io/preferAvoidPods 打分
     • NodeAffinity: 实现了节点选择器 和节点亲和性
     • PodTopologySpread: 实现了 Pod 拓扑分布
     • NodeResourcesBalancedAllocation: 调度 Pod 时，选择资源使用更为均衡的节点
     • NodeResourcesLeastAllocated: 选择资源分配较少的节点
     • NodeResourcesMostAllocated: 选择已分配资源多的节点
     • InterPodAffinity: 实现 Pod 间亲和性与反亲和性
     • ServiceAffinity: 检查属于某个 Service 的 Pod 与配置的标签所定义的节点集是否适配。 这个插件还支持将属于某个 Service 的 Pod 分散到各个节点。
     • ImageLocality：选择已经存在 Pod 运行所需容器镜像的节点。实现的扩展点：Score。
4. 重调度/抢占：
   • 一个调度决策当前是合理的，但是一段时间之后可能不再合理，应该能有重新调度和抢占的能力
   • 一个 workload 申请的资源可能是一个区间，workload 保证可以使用下限资源，有可能使用上限资源，但是有更高优先级的 workload 申请资源时，对这种超出其下限资源使用量的 workload 要有能力进行资源回收 (revoke)

其他细节

1. 快速分发文件 (p2p) 与缓存：如容器使用的镜像文件（程序二进制），或者数据密集型应用需要使用的数据可能比较大，需要快速分发文件的能力
2. Master 的实现是否单主，单主有平行扩容的问题，有点是单机效率足够高，在有限的机器大小下，单主已经是不错的选择。几篇论文中的设计如 borg，mesos 也都是单 master + 多 slave 设计。borg 的经验告诉我们，中心化并不一定是一个性能瓶颈（数万节点，上万任务的调度频率）。虽然单主，但是一些核心的孤立责任可以分割到不同的单元，比如 kubernetes 的 api-server; control-manager; sheduler 都是单独的组件.

评估

1. 效率：调度的速度和吞吐 (速度不是越快越好，当任务得不到 prefer的资源，比如数据 locality，那么或许等待一段时间得到的决策更好)
2. 资源使用率
3. 稳定性：重新调度的比例（eviction rate，根据 borg 的数据显示 eviction 的主要来源是 preemption，其次是 machine shutdown ）
4. Workload 的评价指标：如 workload 的评价，比如 prefer的资源是否得到了满足，或者 workload 自身的表现, 性能，吞吐，延迟等
5. 准确性：考虑到优先级的 "fairness"

融合

• borg 的数据认为，大集群/共享集群能代码资源的节约，而共享带来的竞争导致的对运行程序的影响则很小，可以接受。所以调度的目标往往是尽可能在使用共享集群进行多种任务的混合部署。
• mesos/omega 是这种混合部署的方案之一，他们采用一种允许多种调度框架存在，给予约束或者解决竞争的方式来协调他们的存在。borg/kubernetes 则是另一种方式，即调度只有一个中心，但是这个调度允许以一些方式来扩展以满足不同的需求。
• 以 yarn 为代表的离线任务调度框架和以 kubernetes 为代表的（主要用于）在线任务调度框架如何融合是一个要解决的问题。 yunikorn/volcano 是解决这个问题的两个方案，代表了融合的几个方向
  1. 扩展 kubernetes 调度器实现对离线任务的调度，yarn 任务提交改为向 kubernetes 提交任务（需要适配），kubernetes 调度器以及扩展统一管理，意味着 yarn/离线任务 调度逻辑的移植。目前 kubernetes 的扩展能力/方式已经足够应对比较复杂的调度场景了。
  2. 统一的 调度上层，类似 mesos/omega 或者 yunikorn 的方式，协调子调度器的关系，统一的调度层需要被精巧的设计，这种设计必须同时考虑灵活性、简洁性、功能性。
  3. 重写整个 union sheduler 取代 kubernetes 和 yarn 的调度，意味着 对 kubernetes 调度和 yarn 调度逻辑的移植，和方式 i 有小的区别，更为灵活也带来了更高的复杂度和兼容压力，但是如果只考虑 kubernetes 和 yarn，这种方式也较为可行。

------------------------
     union sheduler
------------------------
 kubernetes     yarn
--------     -----------


------------------------
kubernetes with extender/custom scheduler
------------------------
 在线任务      离线任务
--------     -----------

参考

• Mesos, Omega, Borg: A Survey
• mesos-架构
• mesos 论文
• borg 论文
• omega 论文
• 进击的Kubernetes调度系统（一）：Scheduling Framework
• 进击的Kubernetes调度系统（二）：支持批任务的Coscheduling/Gang scheduling
• Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling
• Borg: Google内部的大型集群管理系统
• kubernetes 调度器文档
• Kubernetes增强型调度器Volcano算法分析
• Volcano介绍及其在深度学习场景下的应用