1简介什么是调度？通常所谓的日程安排与时间有关。例如，我今天的日程很紧（如图1所示）。时间作为唯一不可逆的资源，一般会被分成多个时间片来使用。就计算机而言，由于CPU的速度要快得多，所以有CPU时间片的调度，可以让多个任务运行在同一个CPU上。然而，这是一种错觉。在某个时刻，CPU仍然在运行一个单一的任务。图1时间片的划分为了同时运行更多的任务，或者多个处理器共同完成一个任务目标，就需要一个协调器——这就变成了分布式系统，单个数据中心或者一个小区域一般，这是集群。如果让一个分布式系统运行多个任务，各个任务必然会在分布式系统中争夺资源，时间调度就发展为资源调度。从宏观上看，调度主题包括单机操作系统、C/S系统、B/S系统、P2P系统、集群系统、分布式系统等，以及网络协议栈和存储协议栈的各种调度机制.本文主要总结了集群调度发展的三个阶段：宏调度、二级调度和共享状态调度，并比较了三者的优缺点。2集群调度2.1宏调度（Monolithicschedulers）宏调度：在同一个代码模块中实现调度策略，单实例，无并行性。在HPC（高性能计算）领域很常见。图2Hadoop1和MapReduce的宏调度架构如图2所示。以MapReduce为例，一个名为JobTracker的Master进程是所有MapReduce任务的中央调度器。每个节点运行一个TaskTracker进程来管理每个节点上的任务。每个TaskTracker都必须与Master节点上的JobTracker进行通信，并接受JobTracker的控制。与大多数资源管理器类似，MapReduce的JobTracker支持两种调度策略，Capacity调度策略和Fair调度策略。在JobTracker中，资源调度和作业管理都在一个进程中实现。这种设计方法的缺点是可扩展性差：首先，集群规模有限；第二，新的调度策略很难集成到现有的代码中，比如之前只支持batchjobs，现在支持streamingjobs，streamingjobs要嵌入centralscheduler的调度策略是一个困难的任务。2.2静态分区调度器基于静态分区的资源划分和调度在云计算中也称为调度。通过在云平台中分配定义虚拟机角色，实现对资源采集的整体控制。业务系统通常部署在专门的、静态划分的集群的子集上——将集群划分为不同的部分以支持不同的业务。现在企业级云计算大多采用这样一种有计划、经济的资源分配方式——在系统部署前做好容量规划和资源分配2.3两级调度（Two-levelscheduling）处理宏调度和集群静态分区A这些限制的直接解决方案是两层调度。通过引入中央协调组件来确定每个子集群需要分配的资源量，可以动态调整分配给每个调度器（框架调度器）的资源。两层调度本质上是将调度中的资源分配和任务分配分开，将部分决策权交给应用框架，解决了不同应用框架的异构需求问题。如图3所示，YARN为不同的上层应用框架提供了统一的资源调度层。本节后面的Mesos介绍会详细介绍二层调度的需求背景。图3Hadoop1和MapReduce的宏调度架构每个框架的调度器不知道整个集群的资源使用情况，只是被动地接收资源。中央协调组件只将可用资源推送给各个框架，框架自己选择使用或拒绝这些资源。一旦框架（如JobTracker）接收到新的资源，它进一步将资源分配给它内部的应用程序（每个MapReduce作业），从而实现两层调度。两层调度器有两个缺点。首先，每个框架都无法知道整个集群的实时资源使用情况。二是使用悲观锁，并发粒度小。2.3.1YARNYARN全称为ApacheHadoopNextGenerationComputePlatform，这是hadoop1和hadoop2最大的区别，如图4所示。图4Hadoop2.0中引入YARNHadoop2（MRv2）的基本思路是划分功能JobTracker分为两个独立的进程：全局资源管理ResourceManager和各个进程监控和调度的ApplicationMaster。这个过程可以是Map-Reduce中的任务，也可以是DAG中的任务。图5Hadoop2.0中引入YARN在YARN的设计中，集群中可以有多个ApplicationMaster，每个ApplicationMaster可以有多个Container（比如图5中有两个ApplicationMaster，红色和蓝色。红色有3个Container，蓝色的有一个容器）。关键是ApplicationMasters不是ResourceManager的一部分，减轻了中央调度器的压力，每个ApplicationMasters都可以动态调整自己控制的容器。ResourceManager是一个纯粹的调度器（不监控和跟踪进程的执行状态，也不负责重启失败的进程），其唯一目的是管理多个应用程序之间的可用资源（以Container为粒度）。ResourceManager是资源分配的绝对权威。如果ResourceManager是Master，那么NodeManager就是它的slave。ResourceManager也支持调度策略的插件，CapacityScheduler和FairScheduler就是这样的插件。ApplicationMaster负责任务的提交，通过协商和协商从ResourceManager获取Container形式的资源（负责协商获取适合自己应用需求的Container）。然后跟踪进程的运行状态。ApplicationMasters是针对特定的应用程序的，可以根据不同的应用程序编写不同的ApplicationMasters。例如，“YARN包含一个分布式Shell框架，可在集群的多个节点上运行shell脚本。”此外，ApplicationMaster还提供自动重启服务。ApplicationMaster可以理解为应用程序可以自行实现的接口库。ApplicationMasters请求和管理容器。容器指定了一个应用在某个主机上可以使用多少资源（包括内存、CPU等），类似于HPC调度中的资源池。一旦ApplicationMaster从ResourceManager获得资源，它就会联系NodeManager来启动一个特定的任务。例如，如果使用MapReduce框架，这些任务可能是Mapper和Reducer进程。不同的框架会有不同的流程。NodeManager是每台机器上的框架代理，负责机器上的Container，监控可用资源（CPU、内存、磁盘、网络）。并将资源状态报告给ResourceManager。从表面上看，YARN也是一个二层调度。在YARN中，资源请求从ApplicationMaster发送到一个中央全局调度器，中央调度器根据应用程序的需要在集群中的多个节点上分配资源。但是YARN中的ApplicationMaster只提供任务管理服务，并不是真正的二层调度器。所以，YARN本质上还是一个宏调度架构。到目前为止，YARN只支持资源类型（内存）调度。Hadoop2（MRv2）的API是向后兼容的，支持Map-Reduce的任务只需要重新编译就可以在Hadoop2（MRv2）上运行。2.3.2随着大量Mesos分布式计算框架（Hadoop、Giraph、MPI等）的出现，每个计算框架都需要管理自己的计算集群。这些计算框架往往会把任务分成很多小任务，让计算贴近数据，从而提高集群的利用率。但是这些框架都是独立开发的，应用框架之间不可能共享资源。图像的表示如图6所示。图6集群的静态分区和动态共享我们希望多个应用程序框架可以运行在同一个集群上。Mesos提供了一个公共资源共享层，多个不同的应用程序框架可以在该层上运行。图像的表示如图7所示。图7Mesos为不同的应用框架提供了统一的调度接口，但是我们不想使用简单的静态分区方式，如图8所示。图8Mesos对于集群静态分区的英文定义是：“Mesos，它是一个开源平台，用于在多个不同的集群计算框架之间进行细粒度的资源共享。”Mesos最大的优势就是提高了集群的利用率。可以很好的隔离产品环境和实验环境，可以并发运行多个框架。其次，数据可以跨多个集群共享。第三，可以降低维护成本。Mesos最大的挑战是如何支持大量的应用程序框架。因为每个框架都有不同的调度要求：编程模型、通信范式、任务依赖和数据放置。此外，Mesos的调度系统需要能够扩展到数千个节点并运行数百万个任务。由于集群中的所有任务都依赖于Mesos，因此调度系统必须具有容错性和高可用性。Mesos的设计决策（设计理念）：不对所有任务使用集中的、精心设计的（应用需求、可用资源、组织策略）、全局调度策略。而是将调度任务委托给应用框架（将调度和执行功能交给应用框架）。Mesos声称：这样的设计策略可能无法实现全局最优调度，但在实际运行中却出奇的好，可以让应用框架达到近乎最优的目标。声称的优点主要有两个：应用程序框架的演化独立性和Mesos的简单性。Mesos的主要组件包括Master守护进程、Slave守护进程和运行在Slave上的Mesos应用程序（也称为框架）（如图9所示）。Master根据相应的策略（公平调度、优先级调度等）决定给每个应用分配多少资源。模块化架构支持多种策略。资源报价是资源的抽象表示。基于此资源，应用程序框架可以在集群中的节点上实例化和分配报价并运行任务。每个Resourceoffer都是一个分布在多个节点上的免费资源列表。Mesos根据一定的算法策略（如公平调度）决定可以分配多少资源给应用框架，由应用框架决定使用（接受）哪些资源和运行哪些任务。Mesos上运行的应用框架由两部分组成：应用调度器和运行在从机上的代理。应用程序调度程序向Mesos注册。Master决定向注册的框架提供多少资源，应用调度器决定使用Master分配的哪些资源。调度完成后，applicationscheduler将接受的资源发送给Mesos，以确定使用哪些slaves。那么应用框架中任务的执行就可以在slave上运行了。Mesos在任务小且寿命短时效果很好（每个任务经常产生它持有的资源）。图9Mesos调度框架在Mesos中，中央资源分配器动态划分集群并将资源分配给不同的调度程序框架。资源可以以“offers”的形式在不同的调度框架之间任意分配，其中offers代表当前可用的资源。为了避免不同调度框架对同一资源的申请发生冲突，资源分配器一次只允许分配给一个调度框架。在调度决策过程中，资源分配器本质上起到了锁的作用。因此，Mesos中的并发调度是一种悲观策略。Master使用资源提供机制在多个框架之间以细粒度的方式共享资源。每个资源提供免费资源列表分布在多个奴隶上。Master根据公平方法或优先方法决定为每个应用程序框架提供多少资源。第三轮可以以可插拔模块的形式自定义策略。拒绝机制：拒绝Mesos提供的资源计划。为了保持接口的简洁，Mesos不允许应用框架指定资源需求的限制信息，而是允许应用框架拒绝Mesos提供的资源方案。如果应用框架遇到不满足其需求的资源提供者，它将拒绝等待。Mesos声称拒绝机制可以支持任意复杂的资源约束，同时保持可扩展性和简单性。拒绝机制的一个问题是应用程序框架可能需要很长时间才能收到满足其需求的解决方案。由于Mesos不知道应用程序框架的要求，Mesos可能会向多个应用程序框架发送相同的资源解决方案。因此，引入了过滤器机制：Mesos中的一个调度框架使用过滤器来描述它期望被服务的资源类型（允许应用程序框架设置一个过滤器来指示应用程序框架将始终拒绝某些类型的资源）。因此，它不需要访问整个集群，它只需要访问它提供给的节点。这种策略的缺点是它不能支持抢占和基于整个集群状态的策略：一个调度框架不知道分配给其他调度框架的资源。Mesos提供了资源存储策略来支持Gang调度。例如，一个应用程序框架可以指定一个它可以运行的节点的白名单。这不是动态集群分区吗？Mesos进一步解释了过滤器机制：过滤器只是一种资源分配模型的性能优化解决方案，应用程序框架最终决定哪些任务在哪些节点上运行。图10Mesos调度流程Mesos任务调度流程如图10所示，具体流程如下：Slave1向Master报告自己有4个CPU和4GB空闲内存，Master的分配模块会通知framework1根据相应的分配策略。使用所有可用资源。Master将slave1上的可用资源发送给framework1（以resourceoffer的形式）。框架的调度器响应Master调度器：准备在slave上运行两个任务，使用的资源是：第一个任务<2CPUs,1GBRAM>，第二个任务<1CPUs,2GBRAM>。***，Master将任务发送给slave，然后将相应的资源分配给framework的executor。执行者然后启动两个任务。由于slave1上还有1个CPU和1GB内存没有分配，分配模块可以分配资源给framework2。另外，MesosMaster的Allocation模块是可插拔的。使用ZooKeeper实现MesosMaster的Failover。2.4共享状态调度在共享状态调度中，每个调度器都可以访问整个集群状态。当多个调度程序同时更新集群状态时，使用乐观并发控制。共享状态调度可以解决两层调度的两个问题：悲观并发控制带来的并行限制和调度框架对整个集群资源的可见性。乐观并发控制带来的问题是，当乐观假设不成立时，需要重新调度。为了克服两层调度器的上述两个缺点（Omega论文主要关注这个问题），Google开发了下一代资源管理系统Omega，Omega是一个基于共享状态的调度器，它结合了两层调度器中的集中资源调度模块被简化为一些持久化的共享数据（状态）和这些数据的验证码，而这里的“共享数据”其实就是整个集群实时的资源使用信息。一旦引入共享数据，共享数据的并发访问方式就成为系统设计的核心，而Omega采用的是传统数据库中基于多版本的并发访问控制方式（也称为“乐观锁”，MVCC,Multi-VersionConcurrencyControl），大大提高了Omega的并发能力。Omega中没有中央资源分配器，调度器自己做出资源分配决策。2.4.1Omega宏调度的缺点是难以添加调度策略和特殊实现，不能随着集群的扩展而扩展。两层调度确实可以提供灵活性和并行性，但其资源可见性在实践中比较保守，难以适应一些挑剔的任务和一些需要访问整个集群资源的任务。Omega的解决方案是提出一种新的并行调度框架：基于共享状态、无锁、乐观并发控制、可扩展。如图11所示，Omega中没有中央资源分配器，所有资源分配决策均由应用程序调度器自行制定。Omega维护着一个资源分配状态信息的主副本，称为单元状态。每个应用程序调度程序都维护一个本地私有的、经常更新的单元状态副本，用于做出调度决策。调度器可以看到世界上所有的资源，并根据权限和优先级，正确请求所需要的资源。当调度程序决定资源计划时，以原子方式更新共享单元状态：大多数情况下提交会成功（这是乐观的方法）。当发生冲突时，调度决策将以事务方式失败。无论调度成功还是失败，调度器都会重新同步本地cell状态和sharedcell状态。然后，如有必要，重新启动调度过程。Omega的调度器是完全并行的，不需要等待其他调度器。为了避免冲突造成饥饿，Omega调度器采用增量调度——Acceptallbuttheconflictthings，可以避免资源囤积。如果使用allornothing策略，则可以使用Gang调度（一个作业的所有任务要么一起调度，要么都不调度，调度器必须再次尝试调度整个作业。）。群调度等待所有资源准备好后才提交整个任务，造成资源囤积。每个应用程序调度器都可以实现自己的调度策略。但他们必须就资源分配和任务优先顺序达成一致。具有两层调度的中央资源管理器使这变得容易。这是一个有待进一步讨论的开放话题：谷歌认为公平性不是关键要求，每个调度器只满足自己的业务需求。因此，限制每个应用程序调度器的资源上限和任务提交上限。图11Omega调度框架2.4对比分析集群调度的主要目标是提高集群的利用率和效率。如图12所示，共有三种调度方式。如图13所示，共有三种调度方式。图12三种调度方法的比较单体调度器对所有任务使用中央调度算法。它的缺点是不易增加新的调度策略，也不能随着集群的扩展而扩展。两级调度器本质上是将调度中的资源分配和任务分配分开。使用动态资源管理器为多个并行调度框架提供计算资源或存储资源。每个调度框架都拥有整个资源的一个子集。为什么是动态资源管理器？它是相对于静态集群分区而言的。我们可以静态地将集群划分为几个zone来服务于不同的应用。上面的动态资源管理器完成了让静态分区动态工作的工作。由于两层调度无法处理难以调度的挑剔任务，也无法根据整个集群的状态进行决策，因此谷歌引入了共享状态调度架构。共享状态调度程序使用无锁乐观并发控制算法。这种架构被用在谷歌的下一代调度系统Omega中。相比之下，二级调度器本质上是悲观调度算法。在Omega看来，Mesosoffer机制本质上是一种动态过滤机制，使得MesosMaster提供给应用框架的只是资源池的一个子集。当然，这个子集可以扩展成一个完整的集合，即Share状态，但它的接口仍然是悲观策略。在Omega看来，YARN中的ApplicationMasters只是提供了一个任务管理服务，并不是真正的二层调度器。其次，YARN目前只支持一种资源类型。另外，YARN中的ApplicationMaster虽然可以请求特定节点的资源，但具体策略并不明确。几种调度策略对比如图13：图13调度策略对比（包括静态分区）3接下来工作集群调度技术还在开发中，OSDI16会发布一些关于调度的最新文章，包括Google'sRapid:Fast,CentralizedClusterSchedulingatScale，后面会支持attention。资源感知调度。使用机器学习从历史负载变化中预测资源需求模型，为调度决策提供依据。【本文为专栏作家施施原创文章。转载请通过作者微信获得授权公众号Butianys(butianys)】点此阅读作者更多好文
