本文来自于北京邮电大学2018年硕士论文的整理，作者李战。论文主要分为如下四部分

一、集群调度架构总结

1）中央式架构

最原始，k8s，swarm均是该调度方式。

由于所有任务都由唯一的调度器处理，处理这种异构工作负载对调度器的要求很高。不同应用程序对于集群资源的偏好不同，为了满足这些应用程序的需求，需要调度器开发针对性的调度策略

 

2）两层式架构

由一级调度器resource manager和对应于特定工作负载的二级调度器组成，Mesos和后期的YARN采用这种方式。不同的是资源由Mesos一级调度主动提供给二级调度，而YARN是被动

缺点：二级调度无法获取集权的全局信息，无法进行抢占式调度

3）共享状态架构

半分布式调度架构，集群中若干调度器，每个调度器维护一个全局状态的副本，每种不同的工作负载对应一个应用程序级别的调度器。

当一个应用发生状态变更后，对应的调度器会发起一个事务向其他调度更新集群状态。这个更新事务是并发运行的，若有其他应用引发了相互冲突的状态变化，则会导致更新失败。

缺点：调度器只是在被动等待更新事务，总是按照过时的集群状态进行调度，因此无法达到资源调度的最优解，资源利用效率受到很大影响

4）分布式架构

相比之前的共享状态架构，分布式进一步去中心化，每个调度器独立处理接收到的任务，集群调度任务可以交给任一调度器，每个调度器可以将任务放在集群中的任何位置

缺点：

完全放弃了中央控制与调度器之间的协调，分布式调度架构只能采用一些简单的调度策略：分布式调度器通常基于简单的“槽”概念，将每台机器划分为ｎ个统一的槽（slot），并放置ｎ个并行任务，这种做法无法满足不同工作负载对资源的偏好需求；简单的排队机制（如Sparrow中的FIFO）限制了调度的灵活性，无法为任务设置优先级；放弃中央控制使得一些全局调度策略，如多用户公平，无法实现。

5）混合式

将分布式架构与其他架构（如中央式架构）相结合，在弥补分布式架构调度逻辑简单的同时，解决集群调度决策吞吐量的问题。混合式架构中，优先级低、运行时间短的批处理任务由分布式调度器处理，而其他任务则由中央式调度器处理。

二、任务调度算法

基于最小费用流的调度，与队列相比，降低系统资源使用，减少费用

该文将集群调度问题看作网络中的流量从顶点开始，经过一系列有向弧和中间节点，最终进入汇点的过程。顶点代表任务，中间节点代表作业、物理机等。由于流量经过的每条边都有对应的费用，所以待解决的调度问题就演化成在给定策略下求解费用最小路径的问题

使用了cost-scalingpush-relabel算法求解最小流问题，因为时间复杂度低

三、Docker资源分配优化算法

每个应用程序分配的物理资源可以根据应用程序的需求，数据中心中的实时工作负载和可用资源动态缩小或扩展。文章设计了一个基于Docker的容器集群资源分配算法（简称DRA）来为EC（执行容器）的布局和任务分配计算一个可行的解决方案。DRA算法以分布式方式在每台PC上独立运行，以从有限数量的Docker引擎获取资源状态，并做出资源分配决策。

第四部分为基于前两种算法设计的新的容器编排框架，是基于k8s的改进。