关于集群调度发展的趋势分析

前言

最近由于项目结题加毕业开题，本人完成了一些集群调度Survey性质的文章，以此为契机，这里写一篇集群调度发展趋势的分析。由于本文属于博客性质，并非论文，这里不过多涉及细节，主要写集群调度的”势”。

本文主要参考学术论文UC Berkeley的Paper《Multi-agent Cluster Scheduling forScalability and Flexibility》，Google的Paper《Omega: flexible, scalable schedulers forlarge compute cluster》，开源系统Hadoop-Yarn、Mesos（UC Berkeley），以及国内工业界的调度系统Torca（腾讯）、飞天（阿里巴巴）。下表为本文主要参考资料。

=======================   华丽的分割线  =======================

正文

我们认为，目前集群调度发展的主要趋势是集群复用。

一、集群复用的驱动

近年来，由于数据类型和应用需求的多样性，科学界和工业界研发出多种专用的编程框架，用以简化集群编程，例如离线批处理框架MapReduce、流式计算框架Storm、内存迭代计算框架Spark、DAG计算框架Tez、图计算框架Pregel等。而且可以预见，新的计算框架很可能会继续出现。每种框架都专注于一类问题，没有单一的计算框架会成为所用应用场景的最佳选择。此外，在生产环境中，还需要部署某些通用服务，例如Web服务器、数据库服务器等，本文称之为“普通应用”（区别于计算框架）。这样计算框架和应用的多样性推动了一个新的趋势——集群复用，即在统一集群上运行多种计算框架或应用。

集群复用能带来诸多好处，主要有以下三点：

1、提高集群利用率

每种框架或应用有自身的负载变化规律，对资源的利用存在类似“波峰—波谷”的周期性变化。如果集群上只部署一种应用，则集群必须满足其“波峰”阶段的资源需求，但是框架或应用在大部分时间都并不处于“波峰”，造成严重的资源浪费。以图1为例，最初的部署方法是将Hadoop、Storm、MPI三种框架各自部署在不同的独立集群上，平均集群利用率较低，造成了明显的资源浪费。混合部署的方法将三种框架部署到同一集群上，由于不同框架的负载变化趋势不同，这种混合部署的方法可以提高集群资源的整体利用率。

图1 集群复用混合部署示意图

2、数据共享

不同框架或应用可能对于同批数据进行不同处理，这样就涉及到数据复用的问题。如果不采用集群复用的部署方式，每种框架部署在不同集群上，那么数据复用就需要迁移数据。在大数据时代，数据迁移代价极高，其示意图如图2（a）所示。如果采用集群复用的方式，不同框架部署在同一集群，可采用统一的分布式文件系统或NoSql产品，这样就避免了数据迁移，示意图如图2（b）所示。

（a）数据迁移                           （b）数据共享

图2 数据共享对比示意图

3、降低运维成本

不同计算框架部署在多个集群之上，需要对每各个框架分别管理，运维成本较高。集群复用可以将所有服务器看做一个整体，统一申请资源，自动化部署，提高系统易用性，降低运维成本。

二、集群复用下的集群调度与资源管理系统

在集群复用的背景下，集群管理系统不能再仅仅面向一种框架，而是应当支持多种计算框架和应用。集群管理系统也不应当仅仅具有调度功能，而是应当兼具调度和资源管理功能（这里所指“调度”不仅限于作业任务一级的调度，也包含框架一级的“元调度”，可参考Mesos的调度机制）。因此从功能完整性来看，集群管理系统的全称应当是“集群调度与资源管理系统”，这方面著名的开源系统包括Hadoop-Yarn和Mesos。不过，为了全文连贯，本文仍主要使用“集群调度系统”一词。

图3为集群生态系统的层次图，下层是统一的分布式文件系统，中间是集群调度系统，上层是各种框架和应用。集群调度系统主要负责作业调度和资源管理，这与操作系统的功能大体类似，因此集群调度系统亦可称为“集群操作系统”，更有噱头一些，我们也可以称之为“云操作系统”。

图3 集群生态系统层次图

集群生态系统的层次架构并非我一人空想，图4、图5分别是Hadoop-Yarn和Mesos的层次图，其基本层次架构类似。由此也可以印证目前开源系统确实聚焦在集群复用及其所带来的问题之上。

图4 (a) Hadoop架构层次演变

图4 (b) Hadoop-Yarn层次图

图5 Mesos层次图

三、集群复用带来的挑战

集群复用带来的主要挑战就是面向混合负载的调度问题，具体来说，就是集群调度系统如何兼容多种计算框架和应用。从兼容工作的角度来看，集群调度系统兼容Web Server、DataBase这类普通应用相对容易，调度系统可以将应用视为黑盒，不过问应用内部状态。在调度部署过程中，将应用作为一个任务（task），直接部署在合适的机器上。但是对于计算框架来说，集群调度的兼容工作具有更高的难度和更大的工作量。计算框架不是一个简单的单一体，其内部包含着大量的作业和任务，且作业和任务的数量会动态变化。如果将计算框架作为黑盒进行调度和管理，那么集群调度系统无法实时了解框架的任务数量和资源需求，管理粒度过大，容易造成资源浪费。因此，现有集群调度系统兼容计算框架都是建立在二者交互的基础之上（具体交互模式可能不同）。例如Mesos的resource offer机制，就是二者交互机制的典型代表。此外，Hadoop-Yarn、Google第一代调度系统Borg、第二代调度系统Omega、腾讯soso调度系统Torca和阿里云的飞天都是通过某种模式的交互，来实现集群调度系统与计算框架的兼容。

总体而言，面对多样化的计算框架和不断扩大的集群规模，集群调度系统需要考虑更为广泛的调度需求和调度策略，同时需要避免调度器称为整个系统的性能瓶颈。因此，现在学术界和工业界需要设计一种面向混合负载、具有良好灵活性（兼容性）和可拓展性的集群调度系统。

四、集群调度系统的分类与演变

本文依照Google的方法对集群调度系统进行分类，将之分为中央单一调度、两层调度和共享状态调度。

图6 三种调度架构的示意图

1、中央单一调度器（Monolithic scheduling）

最初的调度器是采用中央单一调度架构的，即系统具有一个单一的调度器，所有的调度工作都由中央调度器串行化地完成，其典型代表是Hadoop JobTracker。它的主要问在于其灵活性（兼容性）和可拓展性。由于只有一个调度器，它很难兼容多样化的调度需求，而且它只有一个调度队列（也可能有多个调度队列，但最终要在单一调度器上串行化执行），这使得调度器容易成为系统瓶颈，影响系统的可拓展性。

中央单一调度存在一种优化变种，即“多代码路径（multiple code path）的中央单一调度”。该调度机制为每种类型的作业提供一个单独的“代码路径”，对于不同作业调度器实际上运行的是不同的调度代码，这样就可以满足不同类型负载的调度需求和策略，在灵活性（兼容性）上有所改善，但是其可拓展性仍然受限。

这里特别说明一点，Hadoop-Yarn虽然看上去像是两级调度系统，但实际上属于中央单一调度。要确定Hadoop-Yarn是哪类调度系统，首先要明确“调度”的概念，调度就是为任务分配资源、为任务选择合适的机器，所以负责为任务选择机器的组件才是调度器。就Hadoop-Yarn来看，Yarn虽然具有Resource Manager和AppMaster，但是AppMaster只负责作业管理，完成调度的是单一组件Resource Manager，因此Hadoop-Yarn是中央单一调度系统。Omega论文也认为Yarn的属于单一调度器，其评价如下：“It might appear that YARN is a two-level scheduler, too. …But the application mastersprovide job-management services, not scheduling, so YARN is effectively amonolithic scheduler architecture.”

2、两层调度器（Two-Level scheduling）

为了解决中央单一调度器在兼容性和可拓展性上的缺陷，两层调度器应运而生。UC Berkeley提出的Mesos是其中的典型代表，计算框架运行在Mesos之上，Mesos向上层框架提供resource offer，上层框架根据Mesos提供的资源进行任务调度。Mesos Master是一个中心化的资源管理器，我们也可以将其看做“元调度器”，即对计算框架进行调度；上层框架的调度器实际为任务进行调度，因此Mesos属于两层调度系统。

Mesos可以同时为多种计算框架服务，每种框架的调度策略在自己的调度器中实现，因此Mesos具有良好的兼容性。但是Mesos也存在其问题。主要表现在以下两个方面：

1) 无全局资源视图

Mesos向框架提供resource offer，resource offer中只包含当前可用资源，因此框架只能看到局部资源视图，调度结果通常不具有全局最优性。对于约束调度或者挑剔调度（pickyscheduling），局部资源视图会限制其调度结果或者反应速度。此外，局部资源视图天然不支持抢占。

2) 悲观并发控制

Mesos定期向框架提供resource offer，这是一个串行化的过程。在任意时刻，Mesos只会将当前所有可用资源提供给一个框架，在该框架反馈后Mesos才会将可用资源提供给另一个框架。这种串行化相当于悲观并发控制，限制了系统并发性和可拓展性。

3、共享状态调度（Shared-state scheduling）

在正式介绍Omega之前，先说一点题外话。Omega一文中指出了Mesos的上述缺点（无全局资源视图、悲观并发控制），但是就像CAP理论一样，计算机领域具有很多折中与权衡的问题。Mesos的“缺点”也会避免一些问题，优缺点的权衡与取舍主要取决于系统的应用场景不同。根据Google的负载分析，工作负载大体上可以分为两类：终止型作业和服务型作业。终止型作业就是运行时间短、优先级较低、“尽力而为”的作业，例如MapReduce批处理作业；服务型作业是指在概念上一直运行的作业，例如Web Server和数据服务器，流式计算作业也可包括在内。Mesos主要针对终止型作业的应用场景，作业多为短任务，通常不需要抢占，不涉及挑剔调度，因此非全局的资源视图不会有太大问题。但是Google内部的应用场景是混合负载，即终止型作业和服务型作业的混合，这样Mesos的问题就成为了缺点，需要进行解决。

为了解决两层调度器在全局资源视图和并发控制方面的问题，Google提出了共享状态调度，其典型代表就是Google下一代调度系统Omega。运行在Omega之上的计算框架调度器具有全局资源视图，具有整个集群的完全访问权限。Omega元调度器维护着一个全局共有的集群状态，每个调度器具有一个私有集群状态副本。为增加系统的并发性，Omega采用乐观并发控制机制，运行在Omega上的计算框架调度器根据下述步骤进行调度：

1)  如果作业队列不为空，从中取出一个作业；

2)  同步：开始一个事务，同步私有集群状态副本和共有集群状态；

3)  调度：调度器尝试为作业中所有任务创建任务——资源分配，在这个过程中修改私有集群状态；

4)  提交：根据私有集群状态尝试提交作业事务到共有集群状态，作业事务可能成功或失败；

5)  如果作业事务提交失败，则将该作业重新加入作业队列，准备在未来事务中再次处理。

Omega采用乐观并发控制，但是在并发调度过程中，不同的任务可能会使用相同的资源，这样就引入了一个新问题——调度冲突。产生调度冲突后作业需要被重新调度，代价较高。Omega一文中对于冲突的建模和实验有过于简单之嫌，目前尚没有充分论据可以证明其调度冲突可控。Google自己对于Omega的评价也较为谨慎，只是称之为一种“可行的、具有吸引力的方法”（论文原文：shows that optimistic concurrency over shared state is a viable, attractive approach tocluster scheduling）。

五、从实用角度审视集群调度系统

根据上文分析，Omega的工作虽然富有启发性，但是尚未完善，还不够实用；Mesos缺少全局资源视图，不适用于工业界混合负载的应用场景（例如MapReduce + Web + DB）。纵观工业界，反而是中央单一调度器最为流行实用，其中就包括Google第一代调度系统Borg（Omega原文：Google’s current cluster scheduler iseffectively monolithic, although it has acquired many optimizations over theyears …），此外腾讯的Torca和阿里巴巴的飞天也属于中央单一调度系统。

当然，这些系统不是最原始的中央单一调度系统，而是进行了很多优化，例如支持多用户和多调度队列，尽可能提高其并发性，采用多代码路径，支持不同的调度需求和调度策略，提高其灵活性（兼容性）。不过，由于只有一个调度器，其可拓展性仍有一定限制。

最后再说一点，对于很多中小规模的组织而言，目前自己定制集群调度系统还是不太现实的。对于国内顶级互联网公司而言，他们正在构建和完善自己的集群调度系统，调度架构采用中央单一调度，并辅以多种优化。而对于业界领军者Google而言，他们已经开始着手解决中央单一调度架构的可拓展性等问题，提出新的调度模型，虽然还有待完善，但足见Google业务需求的庞大和工作的超前。