在分布式架构下，当待执行的任务较多，并且任务存在优先级的情况下，当我们需要执行多个任务时，通常需要满足优先级高的任务，在分布式体系下需要一个分布式调度算法来协调资源去执行任务。这就需要我们了解分布式调度的架构和算法，本篇文章介绍常见的3种分布式调度算法，也会对目前主流的分布式调度算法Borg、Mesos、Omega进行描述和对比。
单体调度架构
分布式系统中的单体调度是指，一个集群中只有一个节点运行调度进程，该节点对集群中的其他节点具有访问权限，可以搜集其他节点的资源信息、节点状态等进行统一管理，同时根据用户下发的任务对资源的需求，在调度器中进行任务与资源匹配，然后根据匹配结果将任务指派给其他节点处理。
单体调度架构.png
K8s使用的就是单体调度算法，首先K8s将任务资源设计了一个任务资源模型包含CPU 核数、内存、硬盘空间、硬盘访问速度、TCP 端口等。所有的任务调度都是根据所有应用节点的资源情况和任务资源模型进行匹配，根据匹配结果进行任务分派。
K8s Borg调度器单体调度算法分为三步：
-
可行性检查，在可行性检查阶段，调度器会找到一组满足任务资源要求，且有足够可用资源的机器。每个节点上的可用资源，包括已经分配给低优先级任务但可以抢占的资源。
-
评分阶段，评分算法有最差匹配算法和最佳匹配算法。
最差匹配算法，该算法的核心是将任务尽量分散到不同的机器上。该算法的问题在于，它会导致每个机器都有少量的无法使用的剩余资源。
最佳匹配算法，把机器上的任务塞得越满越好。这样就可以“空”出一些没有用户作业的机器（它们仍运行存储服务），来直接放置大型任务。
- 任务分配阶段，根据前面的评分算法按照评分排序分配任务到合适的应用节点进行任务处理。
两层调度架构
分布式系统中的两层调度是指，调度器有两层管理模块，一层调度器只负责资源管理和分配，另外一层调度器负责任务与资源的匹配。Scheduler-1 表示第一层调度，负责收集和管理集群中的资源信息；Scheduler-2 表示第二层调度，Scheduler-1 会将集群资源发送给 Scheduler-2（这里的集群资源非全量），然后 Scheduler-2 根据任务的资源需求和 Scheduler-1 发送的资源信息进行任务匹配和调度。
两层调度架构.png
Apache Mesos使用了两层调度算法，对Borg这样的单体算法进行了优化，提高了调度对不同任务的调度扩展性，Mesos有两个调度算法一个是最小公平算法一个是主导资源公平算法。
最小公平算法
最小公平算法遵循3大原则：
1）按照用户对资源需求量递增的顺序进行空闲资源分配；
2）不存在用户得到的资源超过自己需求的情况；
3）对于分配的资源不满足需求的用户，所获得的资源是相等的。
在执行资源分配时，最大最小公平算法按照上述 3 条原则进行多次迭代，每次迭代中资源均平均分配，如果还有剩余资源，就进入下一次迭代，一直到所有用户资源得到满足或集群资源分配完毕，迭代结束。
最小公平算法.png
主导资源公平算法
最大最小公平算法采用了绝对公平的方式分配资源，会导致大量的资源浪费，所以Mesos推荐使用主导资源公平算法。
针对多种资源的需求，主导资源公平算法首先计算已经分配给用户的每一种资源的占用率，比如已经分配的 CPU 占总资源量的多少，已经分配的内存占总资源量的多少。所有资源占用率中的最大值称作该用户的主导资源占用率，而主导资源占用率对应的资源就是用户的主导资源。
主导资源公平算法.png
共享状态调度架构
通过将单体调度器分解为多个调度器，每个调度器都有全局的资源状态信息，多个调度器需要共享集群状态，包括资源状态和任务状态等，从而实现最优的任务调度，提供了更好的可扩展性。
共享状态调度架构为了提供高可用性和可扩展性，将集群状态之外的功能抽出来作为独立的服务。
1）State Storage 模块（资源维护模块）负责存储和维护资源及任务状态，以便 Scheduler 查询资源状态和调度任务；
2）Resource Pool 即为多个节点集群，接收并执行 Scheduler 调度的任务；
3） Scheduler 只包含任务调度操作，而不是像单体调度器那样还需要管理集群资源等。
共享状态调度架构.png
Google Omega共享调度算法
Omega 使用事务管理状态的设计思想，将集群中资源的使用和任务的调度类似于基于数据库中的一条条事务（Transaction）一样进行管理。显然，数据库是一个共享的状态，对应 Omega 中的 Cell State，而每个调度器都要根据数据库的信息（即集群的资源信息）去独立完成自己的任务调度策略。
omega共享调度.png
在一个应用执行的过程中，调度器会将一个 Job 中的所有 Task 与 Resource进行匹配，可以说 Task 与 Resource 之间是进行多对多匹配的。其间，调度器会设置多个Checkpoint 来检测 Resource 是否都已经被占用，只有这个 Job 的所有 Task 可以匹配到可用资源时，这个 Job 才可以被调度。
三种调度架构对比
3种调度对比.png
上面图中描述了3种调度架构，单体调度的节点资源状态、任务状态都是集中管理调配；两层调度将不同任务的调度器从单体调度节点中拆离出来，这样后续再增加新类型的任务可以配套增加一套调度器用来做任务匹配分发；共享状态调度引入了资源状态全局共享机制，所有的调度器都可以看到集群中全局资源情况。具体多维度对比如下表：
| 单体调度 | 两层调度 | 共享状态调度 | |
|---|---|---|---|
| 调度架构 | 集中式结构：一个中央调度器 | 树形结构：一个中央调度器，多个第二层调度器 | 分布式结构：多个对等调度器 |
| 调度形式 | 单点集中调度 | Resource Offer | Transaction |
| 调度单位 | Task | Task | Task |
| 任务调度的并发性 | 无并发 | 悲观并发调度 | 乐观并发调度 |
| 是否是全局最有调度 | 是 | 否 | 是 |
| 系统并发性 | 低 | 中 | 高 |
| 调度效率 | 低 | 中 | 高 |
| 系统可扩展性 | 低 | 中 | 高 |
| 是否开源 | 是 | 是 | 否 |
| 适用场景 | 小规模集群，适用于业务类型比较单一的场景 | 中等规模集群，适用于同时具有多种业务类型的场景 | 大规模集群，适用于同时具有多种业务类型的场景 |
| 类型应用 | Borg | Mesos | Omega |
网友评论