从Kubernetes理解调度
在当今的计算领域，随着集群规模的扩大和对快速响应变化需求的期望，传统的单体集群调度架构面临着诸多挑战。这些挑战限制了新功能的部署速度，降低了效率和资源利用率，最终可能制约集群的进一步发展。为应对这些问题，谷歌提出了一种新颖的调度架构：Omega。该架构利用并行性、共享状态和无锁的乐观并发控制，旨在提高调度的灵活性和可扩展性。
调度器简介
最早的调度器是单机系统里的批处理调度器，通过对计算机资源的分时复用来增加资源的利用率。
调度器是指在大规模计算集群中负责将作业（jobs）分配到机器上，这个过程称为调度（scheduling）。文章指出，随着集群规模的增长和工作负载的多样化，调度问题变得更加复杂。调度器需要考虑不同的需求和策略，例如资源利用率、用户指定的放置约束、快速决策制定以及公平性和业务重要性等。
单机调度器的演变，可以总结出调度器设计的三个基本需求：
- 资源的有效利用
- 信号的实时响应
- 调度策略的灵活配置
这三个需求，某些场景下会相互掣肘，很难同时满足。
相比单机系统，在分布式系统中，还存在以下的一些困难：
集群资源状态同步：单机系统里，利用共享内存和锁机制可以很好的实现资源状态同步，保证任务的并发运行。但是在分布式系统中，网络通讯的不可靠性，使得在所有机器上达成状态的一致性非常困难。我们甚至不能保证所有机器上基准时钟的一致性。
容错性问题：单机系统里，任务规模、资源规模有限，出错的概率和成本比较低，但是分布式系统集群规模可能非常大，任务之间的依赖关系更加复杂，出错的概率大大增加，出现错误以后，恢复的成本也很高。调度器层面，对于错误的识别和恢复能力要足够快速准确。
可扩展性：分布式系统里，任务的类型远比单机系统下要多，不同任务的调度需求是不同的，一套调度器很难适应所有情况，同时待调度的资源规模不断扩大，可能存在上千、上万个节点；一方面要应对资源的不稳定，一万个节点，每天故障一个是很正常的概率，另一方面，要处理多元的调度需求，对调度器的可扩展性提出了很高的需求。
谷歌的论文《Omega: flexible, scalable schedulers for large compute clusters 》里把分布式系统的调度器分为了三种类型，这里简单介绍下。
单体调度器 (monolithic scheduler)
单体调度器（Monolithic Scheduler） 是一种集中式的调度架构，广泛应用于大规模计算集群中。它使用单一的、集中式的调度算法来处理所有作业，通常在高性能计算（HPC）环境中较为常见。以下是单体调度器的详细介绍：
核心思想 单体调度器的核心思想是：
- 集中式调度：所有调度决策由一个中央调度器完成，调度器负责管理整个集群的资源，并将任务分配到合适的机器上。
- 单一调度算法：调度器使用单一的调度算法来处理所有类型的作业，无论是批处理作业还是服务作业。
架构设计 单体调度器的架构设计相对简单，主要包括以下组件：
- 中央调度器：负责整个集群的资源管理和任务调度。调度器维护集群的全局状态，并根据调度算法做出调度决策。
- 作业队列：所有作业请求首先进入作业队列，调度器按照一定的优先级顺序从队列中取出作业并进行调度。
- 资源管理器：调度器负责管理集群中的所有资源（如CPU、内存、存储等），并根据作业的需求分配资源。
工作流程 单体调度器的工作流程如下：
- 作业提交：用户提交作业到调度器，作业进入作业队列。
- 调度决策：调度器从作业队列中取出作业，并根据调度算法和集群的当前状态做出调度决策。
- 资源分配：调度器将作业分配到合适的机器上，并分配所需的资源。
- 任务执行：作业在分配的机器上执行，调度器监控任务的执行状态。
- 资源释放：任务完成后，调度器释放资源，并将资源重新分配给其他作业。
优点 单体调度器具有以下优点：
- 简单性：由于所有调度决策由一个中央调度器完成，架构相对简单，易于理解和实现。
- 全局视图：调度器可以访问整个集群的状态，能够做出全局最优的调度决策。
- 一致性：由于使用单一的调度算法，调度器可以确保所有作业按照相同的策略进行调度，避免不同调度器之间的策略冲突。
局限性 尽管单体调度器具有一定的优势，但它也面临一些挑战和局限性：
- 扩展性差：随着集群规模的增加，调度器的负载也会增加，调度器可能成为系统的瓶颈。调度器的处理能力限制了集群的扩展性。
- 灵活性不足：由于使用单一的调度算法，调度器难以支持不同类型的作业和复杂的调度策略。添加新的调度策略或修改现有策略可能会非常困难。
- 头阻塞问题（Head-of-Line Blocking）：如果调度器在处理一个耗时较长的作业时，其他作业可能会被阻塞在队列中，导致作业的等待时间增加。
- 单点故障：由于所有调度决策由一个中央调度器完成，调度器成为系统的单点故障。如果调度器出现故障，整个集群的调度功能将受到影响。
集中式的调度器的特点：
- 适合批处理任务和吞吐量较大、运行时间较长的任务
- 调度算法只能全部内置在核心调度器当中，灵活性和策略的可扩展性不高
- 状态同步比较容易且稳定，这是因为资源使用和任务执行的状态被统一管理，降低了状态同步和并发控制的难度
- 由于存在单点故障的可能性，集中式调度器的容错性一般，有些系统通过热备份 Master 的方式提高可用性
- 由于所有的资源和任务请求都要由中央调度器处理，集中式调度器的可扩展性较差，容易成为分布式系统吞吐量的瓶颈
目前采用该方式的调度器：
- 单机操作系统：windows、Linux、macOS
- Hadoop YARN Resource Manager + Node Manager + Application manager
现在的分布式系统中，一般会存在多个stand-by调度器实例，用于替补主调度器实例。降低单点故障的影响。
两层式调度 (two-level scheduler)
集中式调度器的缺点在于可扩展性比较差，容错性比较低，容易出现性能瓶颈。
通过资源层面的分区+分层，可以解决这些问题，这就是两层式调度的解决思路：
在双层调度器当中，资源的使用状态同时由分区调度器和中央调度器管理，但是中央调度器一般只负责宏观的大规模的资源分配， 因此业务压力较小。分区调度器负责管理自己分区的所有资源和任务，一般只有当所在分区资源无法满足需求时， 才将任务冒泡到中央调度器处理。
相比集中式调度器，双层调度器某一分区内的资源分配和工作安排可以由具体的任务本身进行定制， 因此大大增强了使用的灵活性，可以同时对高吞吐和低延迟的两种场景提供良好的支持。每个分区可以独立运行， 降低了单点故障导致系统崩溃的概率，增加了可用性和可扩展性。但是反过来也导致状态同步和维护变得比较困难。
两级调度器（Two-level Scheduler） 是一种常见的集群调度架构，主要用于大规模计算集群中。它将资源分配和任务调度分为两个层次：资源管理器（Resource Manager） 和 调度框架（Scheduler Frameworks）。这种架构的代表系统包括 Mesos 和 Hadoop-on-Demand（HOD）。以下是两级调度器的详细介绍：
核心思想 两级调度器的核心思想是将资源分配和任务调度分离为两个层次：
- 第一层：资源管理器：负责全局资源的分配和管理，动态地将集群资源分配给不同的调度框架。
- 第二层：调度框架：每个调度框架负责在分配到的资源上调度具体的任务或作业。 通过这种分层设计，两级调度器可以在一定程度上实现并行调度，同时保持资源分配的全局控制。
架构设计 两级调度器的架构设计包括以下两个主要组件：
资源管理器（Resource Manager）：
- 资源管理器是中央协调者，负责管理整个集群的资源。
- 它动态地将资源分配给不同的调度框架，通常以“资源提供（Resource Offers）”的形式进行。资源提供包含当前未使用的资源。
- 资源管理器通过某种公平性算法（如Dominant Resource Fairness, DRF）来决定资源的分配顺序和大小。
调度框架（Scheduler Frameworks）
- 每个调度框架负责在分配到的资源上调度具体的任务或作业。
- 调度框架可以独立实现不同的调度策略，适用于不同类型的作业（如批处理作业、服务作业等）。
- 调度框架只能看到资源管理器分配给它的资源，而不能看到整个集群的状态。
工作流程 两级调度器的工作流程如下：
- 资源分配：资源管理器根据集群的当前状态和公平性算法，将资源分配给各个调度框架。
- 资源提供：资源管理器以“资源提供”的形式将可用资源提供给调度框架。调度框架可以选择接受或拒绝这些资源。
- 任务调度：调度框架在接受的资源上调度具体的任务或作业。调度框架可以根据自己的策略决定如何分配这些资源。
- 资源释放：任务完成后，调度框架将资源释放回资源管理器，资源管理器可以再次将这些资源分配给其他调度框架。
优点 两级调度器具有以下优点：
- 并行性：多个调度框架可以并行工作，每个框架独立调度自己的任务，避免了单体调度器的串行瓶颈。
- 灵活性：不同的调度框架可以实现不同的调度策略，适用于不同类型的作业。
- 资源隔离：资源管理器可以确保资源在不同调度框架之间的公平分配，避免某些框架占用过多资源。
局限性 尽管两级调度器具有一定的优势，但它也面临一些挑战和局限性：
- 资源可见性有限：调度框架只能看到资源管理器分配给它的资源，而不能看到整个集群的状态。这使得调度框架难以处理需要全局信息的复杂调度需求（如资源抢占、故障容忍等）。
- 悲观并发控制：资源管理器在分配资源时会锁定资源，直到调度框架做出调度决策。这种悲观并发控制机制限制了并行性，尤其是在调度决策时间较长的情况下。
- 资源碎片化：由于资源管理器只能提供当前未使用的资源，调度框架可能无法获得足够的资源来调度大型作业，导致资源碎片化和次优的资源利用率。
- 不适合长任务：两级调度器假设任务较短且资源释放频繁，但在实际生产环境中，许多任务（如服务作业）运行时间较长，资源释放不频繁，这会导致资源锁定时间过长，影响其他调度框架的调度效率。
两层式调度器的例子：
- Golang runtime的Groroutine 协程调度器。在这一模型下，一个进程内部的资源就相当于一个分区，分区内的资源由运行时提供的调度器预先申请并自行管理。 运行时环境只有当资源耗尽时才会向系统请求新的资源，从而避免频繁的系统调用。
- Mesos。Mesos会把资源进行分区，一个区对应一个framework，在framework内部，由framework自行决定资源的分配与任务的调度，而framework整体，会向Mesos调取器申请资源。
- spark drizzle。原本spark使用一个集中式的调度器来调度和执行基于DAG模型的计算任务。Driver 向 Scheduler申请资源，然后由节点上的Executor进程负责任务的执行。后续为了优化流计算过程中调度器带来的延迟问题，改使用两层的调度模型。
Mesos是在k8s之前，应用的最广泛的调度系统，也是谷歌那篇论文里，重要的比对对象，它的调度原理，在《Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center 》论文里有详细的说明。目前公开的mesos支持的最大的集群规模达到数万台机器节点(推特内部的生产环境，约8万台机器)。
略微展开一下，Mesos内部的调度过程：
- 与一般通过 Master 请求资源不同，Mesos 提出了 Framework 的概念，每个 Framework 相当于一个独立的调度器 (例如spark，yarn)， 可以实现自己的调度策略
- Resource Offer机制。Master 掌握对整个集群资源的的状态，通过 Offer (而不是被动请求) 的方式通知每个 Framework 可用的资源有哪些。
- Resource Accept。Framework 根据自己的需求决定要不要占有 Master Offer 的资源，如果占有了资源，这些资源接下来将完全由 Framework 管理
- Framework 通过灵活分配自己占有的资源调度任务并执行，这一步就与Mesos无关了
注意，这里Mesos的资源是主动给出去的，不是被动的等framework来申请，而是主动的把资源定期推送给framework, 供framework选择，framework有任务执行，资源不足时，并不能主动申请，只有接受到offer的时候，才可以挑选适合的资源来接受(Accept)，剩余的offer就拒绝掉(reject),如果一直没有合适的资源，就会等下一轮master提供的offer。
Mesos这样的resource offer机制，有一些不足：
- 发offer的过程是悲观并发的(就和谷歌论文里的图也提到了)，同一时间只会给一个framework提供offer，任何一个framework的决策效率会影响整个集群的决策效率。这点可以通过设置决策超时时间来规定一个上线，但是治标不治本。
- 推送机制，会导致很多无效的推送。不是所有framework都需要资源，但是mesos master并不能感知到这一点。这一点可以通过framework自己的状态来避免，比如通过一个标注位来标记自己此刻不缺资源。
其实mesos在选择哪些framework发offer的机制上，是有一套自己的算法的，这里就不赘述了。根据mesos上面论文中自己的描述，mesos比较适合调度短任务，因为他们认为在企业里，数据中心的资源百分之80都是被短任务消耗调的(数据实时查询、日志流式计算、大数据计算)，有多短呢？论文里给了一个数据：
Most jobs are short (the median being 84s long), and the jobs are composed of fine-grained map and reduce tasks (the median task being 23s)
共享状态式调度 (shared state scheduler)
结合前面的内容，调度器要做的事情有两个：
- 追踪系统里资源分配和使用的状态
- 根据资源状态，调度任务，追踪任务执行的状态
在集中式调度器里，这两个状态都由中心调度器管理，并且一并集成了调度功能。
双层调度器模式里，这两个状态分别由中央调度器和次级调度器管理。
集中式调度器可以容易地保证全局状态的一致性但是可扩展性不够， 双层调度器对共享状态的管理较难达到好的一致性保证，也不容易检测资源竞争和死锁。
Shared-state scheduler（共享状态调度器） 是本文提出的新型调度架构，旨在解决现有调度器（如单体调度器和两级调度器）在扩展性、灵活性和性能方面的不足。该架构的核心思想是通过共享集群状态和无锁的乐观并发控制（optimistic concurrency control）来实现高并行性和灵活性。以下是共享状态调度器的详细介绍：
- 核心思想
共享状态调度器的核心思想是：
- 共享集群状态：每个调度器都可以访问整个集群的状态，而不是像两级调度器那样只能看到部分资源。
- 乐观并发控制：调度器在做出调度决策时，假设不会与其他调度器发生冲突。如果冲突发生，调度器会重新尝试调度，而不是通过锁定机制来避免冲突。
- 架构设计
共享状态调度器的架构设计包括以下几个关键组件：
- Cell State（单元状态）：这是集群资源分配的全局状态，存储在一个持久化的数据存储中。每个调度器都有一个本地的、频繁更新的副本，用于做出调度决策。
- Schedulers（调度器）：每个调度器独立运行，可以访问整个集群的状态。调度器根据本地副本做出调度决策，并在决策完成后通过原子提交（atomic commit）更新全局状态。
- Optimistic Concurrency Control（乐观并发控制）：当多个调度器同时尝试更新全局状态时，只有一个调度器的提交会成功，其他调度器需要重新同步状态并重新尝试调度。
这种架构基本上沿袭了集中式调度器的模式，通过将中央调度器肢解为多个服务以提供更好的伸缩性。 这种调度器的核心是共享的集群状态，因此可以被称为共享状态调度器。
Omega在状态的管理里，引入了事务的概念。如果将数据库储存的数据看作共享状态， 那么数据库就是是共享状态管理的最成熟、最通用的解决方案！事务更是早已被开发者们熟悉而且证明非常成熟和好用的并发抽象。
优点 共享状态调度器具有以下优点：
- 高并行性：多个调度器可以同时工作，互不干扰，避免了单体调度器的串行瓶颈和两级调度器的资源锁定问题。
- 灵活性：每个调度器可以独立实现不同的调度策略，且可以访问整个集群的状态，从而做出更优的调度决策。
- 可扩展性：通过乐观并发控制，调度器可以在冲突发生时重新尝试调度，避免了悲观锁定的开销，从而支持更大规模的集群和更复杂的调度需求。
挑战 共享状态调度器面临的主要挑战是冲突处理。由于多个调度器可以同时访问和更新全局状态，冲突是不可避免的。为了解决这个问题，共享状态调度器采用了以下策略：
- 增量事务：调度器可以选择接受部分成功的更新，从而减少冲突的影响。
- 全或无事务：对于需要严格保证的任务（如Gang Scheduling），调度器可以使用全或无事务，确保所有任务要么全部调度成功，要么全部失败。
- 冲突检测与重试：调度器在冲突发生时重新同步状态并重新尝试调度，从而避免资源浪费和死锁。
Omega 将集群中资源的使用和任务的调度看作数据库中的条目，在一个应用执行的过程当中， 调度器可以分步请求多种资源，当所有资源依次被占用并使任务执行完成，这个 Transaction 就会被成功 Commit。
Omega 的设计借鉴了很多数据库设计的思路，比如:
- Transaction 设计保留了一般事务的诸多特性，如嵌套 Transaction 或者 Checkpoint。 当资源无法获取或任务执行失败，事务将会被回滚到上一个 Checkpoint 那里
- Omega 可以实现传统数据库的死锁检测机制，如果检测到死锁，可以安全地撤销一个任务或其中的一些步骤
- Omega 使用了乐观锁，也就是说申请的资源不会立刻被加上排他锁，只有需要真正分配资源或进行事务提交的时候才会检查锁的状态， 如果发现出现了 Race Condition 或其他错误，相关事务可以被回滚
- Omega 可以像主流数据库一样定义 Procedure ，这些 Procedure 可以实现一些简单的逻辑， 用于对用户的资源请求进行合法性的验证(如优先级保证、一致性校验、资源请求权限管理等)
直观的体验就是：借助事务机制，Omega对于状态的管理更加游刃有余，且随着分布式数据库与分布式事务的发展和成熟，可行性问题也得到了解决。
Omega的缺点也很明显：实现起来非常复杂。
那么，各位觉得，kubernetes的调度器，属于上面的哪一种调度方式？
kube-scheduler功能回顾
简单了解了调度器的架构简史，回到k8s调度器本身，在研究它的实现之前，首先需要从功能上对它有一个基本的认识。
这里我们所说的功能，都是指k8s默认调度器的功能。
kubernetes里，调度的最小单元是Pod。每个pod的配置里，都指定了资源的最小值与最大值。每个机器节点都相当于一个资源池，供pod消耗。
所以k8s里，调度器最简单的需求就是：给待调度的pod找到一个符合它最低资源需要的node。
进一步，默认的资源字段里只提供了CPU和Memory，而一些pod会有比较特殊的资源需求，举个例子：GPU资源、本地化的存储资源需求。这类资源目前在默认的k8s集群里，没有量化索取的方式，只能通过给node打标签来标记node，然后在pod上设置nodeselector字段，进行节点过滤。
但是打标签的方式还是不够灵活，在正常的语义里，我们在筛选时，可以有两种强弱关系：必须(不)、可以(不)。打标签只能提供必须(不)的语义，不能提供should的语义，因此，又产生了另一种方式：NodeAffinity 节点亲和性。
亲和性调度，有两个选项：
- RequiredDuringSchedulingIgnoredDuringExecution: 类似nodeSelector的硬性限制，必须被满足的条件
- PreferredDuringSchedulingIgnoredDuringExecution: 强调优先满足指定规则，相当于软限制，多个优先级规则还可以设置权重，以定义执行的先后顺序；IgnoredDuringExecution的意思是： 如果一个Pod所在的节点在Pod运行期间标签发生了变更， 不再符合该Pod的节点亲和性需求， 则系统将忽略Node上Label的变化， 该Pod能继续在该节点运行
并且，
- 如果同时定义了nodeSelector和nodeAffinity，必须两个条件都满足才能调度
- 如果nodeAffinity指定了多个nodeSelectorTerms，匹配其中一个即可
- 一个nodeSelectorTerm中有多个matchExpressions,则都满足才行调度
亲和性是根据pod的情况，看node是否符合被调度的需要，反过来，node也可以表明自己拒绝某些pod的调度，这就是污点(Taints)和容忍(Tolerations)机制：
- node上可以设置某些taints，即污点
- pod上可以设置tolerations（容忍）,标记自己可以容忍某些污点
只有Pod明确声明能够容忍这些污点， 否则无法在Node上运行。 Toleration是Pod的属性，让Pod能够（注意，只是能够，而非必须）运行在标注了Taint的Node上。
这里，调度器需要考虑node的nodeSelector与亲和性、反亲和性、污点需要 也就是需要考虑node与pod之间的关系。
再进一步，除了要考虑pod与node之间的关系，pod与pod之间本身也会存在错综复杂的关系。例如，同一个应用的pod尽量分散部署，避免单点故障，数据处理中，同一类批处理任务为了满足本地性的需要，可以部署在同一个节点上。
这个需求，可以通过Pod Affinity、antiAffinity来实现，也就是pod的亲和性、反亲和性。和节点亲和性含义类似，打字太累，这里感兴趣的自己去看吧。
所以，调度器需要满足pod亲和、反亲和的需要。
以上，就是一个调度器必须具备的基本功能了，但是还不够，还有一类异常情况没有考虑：集群资源不足时，怎么调度？
这也是调度器最后一块功能需求：驱逐（eviction）和抢占（Preemption）。
我们可以定义优先等级，并给pod打上标记，某些pod是高优先的，哪些是次要的，这一步仅仅依赖调度器不太行了：
- 驱逐eviction：由kubelet来负责，很好理解，kubelet守土有责，自己的节点资源不够了，就会看哪个pod是低优的，主动把他干掉。scheduler只负责调度，不负责调度后擦屁股，所以驱逐也没法让调度器去处理，从职责分离的角度去考虑，这样安排也是合理的。
- 抢占Preemption：这一步发生在调度阶段，如果调度器在调度一个pod的时候，发现没有足够的资源满足该pod，调度器就会重新审视目前现有的pod，比较正在运行的pod与当前待调度pod的优先级，如果当前的pod优先级更高，调度器就会发起抢占操作。
所以，调度器最后一个需求就是：资源不足情况下的抢占操作。
罗里吧嗦一堆，汇总一下默认调度器具有的功能：
- 给待调度的pod找到一个符合它最低资源需要的node。
- 调度器需要考虑pod与node之间的关系
- 调度器需要考虑pod与node上正在运行的pod之间的关系
- 资源不足的情况下，抢占现有低优先级pod的资源
说了这么多，会到上面提到的问题。
kubernetes的调度器，属于上面的哪一种调度方式？
Kubernetes 的调度器主要属于一种单体调度器（Monolithic Scheduler），但它借鉴了一些两级调度器和 Omega 的设计理念，具体分析如下：
为什么说 Kubernetes 属于单体调度器？ 核心调度逻辑集中在单个组件 Kubernetes 的默认调度器（kube-scheduler）是一个集中式组件，负责将所有未绑定到节点的 Pod 分配到适合的节点上。它按照一组全局的调度策略（如资源需求、节点容量、优先级等）进行调度决策，这符合单体调度器的定义。
顺序调度 默认情况下，kube-scheduler会对每个待调度的 Pod 逐一评估适合的节点并进行绑定。这种调度方式是单一的，不像 Omega 那样支持多调度器并行操作。
借鉴两级调度器的特性 尽管 Kubernetes 默认使用单体调度器，但它引入了多租户调度的支持，可以通过创建多个自定义调度器来实现类似两级调度的效果：
多个调度器可以协作调度特定的工作负载，例如通过 schedulerName 指定 Pod 使用不同的调度器。 这类似 Mesos 的分层资源调度模型，只不过 Kubernetes 的核心调度器依然是单体式的，多个调度器之间没有共享资源管理器。