资源管理与任务调度系统Mesos论文及架构详细解读

0. 前言

关于资源管理与任务调度系统出现的背景、发展历程及一些基础知识可以参考博客集群资源管理与任务调度系统综述
Mesos2007年诞生于UC Berkeley，并在Twitter和Airbnb公司中得到实践和巩固，其论文发表于2011年的NSDI，目标是构建一个数据中心可扩展的全局资源管理器。
论文原文：http://static.usenix.org/events/nsdi11/tech/full_papers/Hindman_new.pdf

目前在资源管理与任务调度系统中，影响力比较大比较经典的几个系统分别是YARN、Mesos、Borg、Omeag、Apollo、Sparrow，Kubernetes。目前工业界中大部分集群资源管理和任务调度系统都吸纳了这些系统中的思想，并根据实际的业务场景进行改进，例如阿里伏羲调度系统可以看做是YARN的变体，腾讯云VSTation则吸纳了Omega中的思想。总的来看影响最大的系统当属YARN和Mesos，目前两者均已开源。Borg对调度系统的指导作用很大，但是目前是谷歌的闭源内部系统。Omega和Sparrow目前仅是学术研究并没有真正在线上实践。Apollo主要是微软针对短作业设计的一个调度系统，目前也闭源。Kubernetes主要对容器进行编排，开源。下面就针对Mesos的论文和一些实践来讨论其设计原理，下文思路主要按照论文中的思路进行。

1. Abstract & Introduction

Mesos是一个基于资源供应的两层调度器，通过一个细粒度的管理器为集群计算框架（Hadoop，MPI）分配资源，集群计算框架决定接受资源的量并将任务运行在其上。结果表明在不同集群架构*享集群时可以扩展到50000个节点并对故障有弹性。
背景：

• 大背景。随着数据增长，集群成为主要的计算平台，随着业务场景的多元化，各种针对不同场景的计算框架相继出现例如：MR，Dryad，Pregel等；
• 小背景。新的计算框架会继续出现，没有一个通用的计算框架可以适配所有的应用程序。期望在同一个集群中运行多种计算框架以提升集群资源利用率以及共享访问大型数据集降低多个计算集群中数据重复而导致的代价；
• 目前解决方案缺点。 目前针对多计算框架的解决方案：静态划分集群和实用VM，这些方案的缺点在于不能实现高利用率且不能有效进行数据共享，根本原因在于这些方案的分配粒度和计算框架的分配粒度不匹配。例如：Hadoop框架中，一个job由很多task构成，一个task由很多instance构成，这些任务被分配到计算节点的slot中，任务的短暂性以及一个节点上能够运行多个任务的能力允许作业能够实现高的数据本地化；
• 面临挑战。Mesos想要实现高可扩展性和高效性面临以下挑战：（1）每个计算框架有自己的调度需求、编程模型、同行模型、任务依赖和数据存放；（2）调度系统必须能够支持上千个节点，支持上百万个任务运行；（3）Mesos是系统的中心，必须可容错和高可用；
• 可行解分析。对于Mesos来说一个可行的方案是实现一个*调度器，输入框架要求、资源可用性和组织策略，然后对所有任务计算出一个全局调度。但是这样做存在一些挑战：（1）复杂性，系统需要提供一个丰富的API来支持不同的计算框架，并完成一个针对百万个任务的在线优化问题，会对扩展性和恢复能力造成消极影响；（2）新的计算框架不断出现，需要不断增加接口；（3）许多框架实现了自己的调度逻辑，将其移植到全局调度器中需要昂贵的重构过程；
• 所采用的方法。Mesos提出了一种新的方法，将具体的调度过程委派给计算框架，并抽象出一个资源供给层。Mesos按照一定的分配策略（DRF）决定分配多少资源给计算框架，计算框架决定接受哪些资源并运行任务。虽然该模型不能实现全局最优调度，但是在生产实践中运行的很好，对于集群框架可以实现近乎完美的数据本地性，且实现简单高效，高可扩展对故障鲁棒。
• 一些优化。 Mesos也对使用者提供了一些其他优化。（1）组织只使用一种框架也能使用Mesos运行多个集群框架实例，或者运行多个版本的集群框架，这种方式可以很好的隔离生产环境和实验环境。（2）使得对新框架的实验变得简单，能够快速进行实验。
• 目前实现。用1万行C++代码实现了Mesos，可以扩展5万个节点，利用ZooKeeper实现容错，并且创建了一个新的计算框架Spark，针对机器学习类负载其性能是Hadoop的10倍。
• 总结：Mesos优势：（1）支持在一个集群中运行多个计算框架；（2）实现简单，高扩展，高可用；

2. Target Environment

Facebook的Hadoop集群用来运行商业智能、垃圾邮件，广告优化以及一些实验性的机器学习任务。为了满足这些作业的需求，采用公平调度器，利用工作负载的细粒度特征来分配资源，但是这以为着智能运行Hadoop任务。如果现在需要针对某个业务开发一个更加高效的计算框架例如MPI，那么需要单独创建一个MPI类型的集群，并向其中导入T级别的数据，这种情况在雅虎和Facebook都是存在。因此Mesos旨在针对多个计算框架提供细粒度的共享来保证这些使用场景。

3. Architecture

3.1 设计哲学

由于集群计算框架高度多样化并且发展迅速，重要的设计哲学是定义一个最小的接口提供资源分配功能，而将任务调度和执行控制交给计算框架。这样做：（1）允许计算框架根据多样的问题实现多样的方法并独立发展这些解决方案；（2）保持了Mesos的简单，最小化系统变化率使得Mesos保持扩展性和鲁棒性。同时也希望可以有更高层的库（例如容错）出现来对Mesos等调度系统提供支持。

3.2 综述

上图是mesos的架构图，主要包括master节点、slave节点以及用于可用性保证的zookeeper。master通过资源供给的方式将资源细粒度的分配给计算框架，在每个计算框架中可以有更细粒度的调度和分配策略。

每一种运行在mesos上的计算框架都需要包含scheduler（用于资源获取和再分配）和executor（用于任务执行）。master按照一定策略为计算框架分配资源，计算框架决定获取哪些资源并将需要执行的任务描述发送给master。

上图是一个简单的资源分配模型，主要包括下面过程：

• slave1将自己的空闲资源列表发送给master；
• master触发资源调度将资源分配给framework1；
• framework根据自身情况选择所要接受的资源，并将需要执行的任务描述发送给master；
• master告知slave1运行任务；
• master将剩余的资源分配给framework2；

为了保证调度接口最简洁，mesos不允许计算框架描述其资源需求和约束。而是做了两个优化：（1）计算框架可以根据自身情况拒绝分配的资源，这一方面保证了对复杂资源约束的支持另外保证了mesos的简单可扩展；（2）为防止因资源拒绝而导致的效率问题，计算框架可以设置过滤器，例如一个计算框架爱可以指定任务运行的白名单；这里需要强调的是：（1）过滤器只是一种优化模型，计算框架有最终的决定权；（2）对于一些细粒度的任务（hadoop）在没有过滤器的情况下表现异常好，还发现了延迟调度策略，通过等待一定的时间来获取存储他们数据的节点，在1-5秒的等待时间内可以得到一个近乎最优的数据本地化。

3.3 资源分配

Meos资源分配模块是可插拔的，不同的组织可以根据不同的需求修改它，目前实现了两种分配，一种是基于最大最小的公平策略，一种是严格的优先级策略。

通常情况下mesos假设集群中都是短任务，这样新的计算框架可以快速得到资源份额。但是集群中还存在长任务，例如爬虫或一些贪婪的计算框架，这时候分配模块也会采用杀死任务的方式来解决，但是在杀死之前为了减少影响会给计算框架一个清理的期限。这里有两个机制需要阐明：

• 对于某些计算框架杀死一个任务影响较小，但是对于有相互依赖的任务如MPI，杀死一个任务影响巨大，因此我们通过让分配模块暴露一个“被保证的分配”给每个计算框架。如果一个集群框架得到的资源在它被保证的分配之下，那么它的所有任务不应该被杀死，如果它得到的资源在它被保证的分配之上，它所有的任务都可能被杀死。
• 为了决定什么时候触发撤销，mesos必须要知道哪些框架需要更多的资源，所以框架可以通过API来报告他们的资源兴趣。

3.4 隔离

• 提供了一个可插拔的隔离模块支持多个隔离机制；
• 目前使用LXC进行资源隔离，可以限制进程树对CPU、内存、网络带宽和IO的使用；

3.5 让资源供给可扩展和鲁棒

为了提高可扩展性和鲁棒性，主要有下面三个机制：

• 提供过滤器机制，目前支持两种“提供在列表中的节点”和“提供至少包含R资源的节点”，过滤器使用布尔值存储，master可以进行快速评测；
• mesos根据框架在集群中的份额来分配资源，这可以推动计算框架做出快速响应；
• 如果没有收到响应，mesos会撤销供应，并将资源重新分配给其他框架；

3.6 容错

容错主要包括master容错、节点和executor容错和调度器容错。

• master是mesos的核心，将其设计为软状态，因此一个master进程可以根据slave节点和调度器上的信息重建。并且基于zookeeper采用热备的方式运行多个master节点。
• 对于节点和executor错误，错误信息会报告给框架调度器，由调度器选择策略进行处理；
• 对于调度器错误，mesos允许框架注册多个调度器，但是框架内部调度器之间的状态共享由框架维护；

3.7 API总结

4. mesos表现

4.1 定义、度量和假设

三个指标：

• 框架等待时间：一个新的框架得到资源的时间；
• 任务完成时间：一个任务的完成时间
• 系统资源利用率
  工作负载有两个维度的描述：
• 弹性的和死板的。例如Hadoop不需要获取全部的资源就可以快速运行和释放资源。而MPI则需要获取全部的资源才能进行计算，并且在计算过程中不能扩展或缩减资源量。
• 同构时间分布和异构时间分布。（任务执行时间相同和不同）
  资源区分：
• 强制性。框架只有获取了这部分资源才能运行。
• 建议性。框架获取了这部分资源可以运行的更好，但是在其他节点上也可以运行。
  假设：
• 框架要求的强制性资源不会超过其保证的资源份额；
• 任务有相同的资源需求，运行在相同的机器槽，每个框架一个job

4.2 同构任务

假设一个集群中有n个槽和一个分配了K个槽的f框架，任务执行时间分配场数执行时间和指数执行时间，平均执行时间为T，通过计算可以得出：

• 框架等待时间：常数分布时为T，指数分布时为Tlnk;
• 作业完成时间：一个弹性的作业的预测的完成时间最多是(1+β)T，这是作业同时得到它的全部槽的完成时间即为T，任务的平均期限。死板的作业对于具有常量执行时间的任务具有相似的完成时间，但是对于指数型的作业会展现出更高的完成时间，即，(lnK + β)T。这是因为会花费平均TlnK长度的时间来得到它全部的槽，并且开始执行作业。
• 资源利用率：弹性框架因为可以充分利用集群中的每个槽利用率为1，而死板的框架只能等待获取所有资源后才能运行，所以资源利用率低。

4.3 位置偏好

目前系统没有考虑位置偏好，但是实际环境下框架会有位置偏好且会随时间变化。因此考虑两种场景：

• 存在一个系统配置，框架可以获取到其偏好的资源；
• 没有这种配置；

对于第一种情况，不管初始配置如何，系统最多在时间T内可以将资源合理的分配给框架。
对于第二种情况，我们可以采用加权公平分配策略，权重是不同计算框架所需资源份额占所有计算框架所需份额的比值。因此当有一个可用的槽时，mesos将其分配给不同框架的概率为该框架所需资源份额和所有计算框架所需份额的比值。4.2中的结论同样成立。

4.4 异构任务

如果存在长任务和短任务，可能会因为长任务的执行而导致短任务需要较长的等待时间。但是只要长任务的比例不是特别接近1且每个计算节点存在多个槽时，这种情况就会缓解。例如：长任务比例为0.5，一个计算节点包含8个槽，那么该计算节点全被长任务占据的概率为0.4%,0.5的八次方。

此外mesos提供了一些优化机制：

• 在每个节点上为短任务预留资源；
• 每个节点上的资源和最大任务联系起来并给定一个期限，如果超出期限将被杀死；

4.5 框架建议

• 短任务：（1）短任务可以快速分配到资源并执行；（2）及时某个任务出现错误，会把影响降低到最小；
• 弹性扩展：（1）可以快速执行作业；（2）弹性伸缩能够允许框架随时释放未使用的资源；
• 不接受未知资源：不要接受不能使用的资源；

这些建议一方面有助于任务的快速运行减少延迟，另外可以提高系统的资源利用率。这些建议也被广泛的运用到各种框架中，因为短且无依赖的任务能够简化负载均衡和故障恢复。

4.6 分布式调度的限制

• 碎片化：当任务有异构资源需求时，不能很好优化装箱问题。计算集群中运行更大的节点和在节点中运行更小的任务可以有更高的资源利用率。此外，如果系统中被短任务占满，那么长任务会因为分配不到资源而饿死，这时候需要在slave节点上提供一个最小的供给大小，当没有达到这个数量时不进行分配。
• 相互依赖的框架约束：两种框架之间存在反亲和性，来自两个框架的任务不能共存。可以证明这些在实际场景中是罕见的，但是这样的任务确实存在。
• 框架复杂性：使用资源供给可能会使集群调度更加复杂。但是可以证明这种复杂度不是繁重的：（1）无论是*式还是分布式系统，框架都需要传达他们的需求；（2）许多调度策略都是在线算法，因为框架不能够预测任务的执行时间和一些幽灵问题，这些策略使用资源供给可以简单地实现。

5. 实现

1万行C++代码实现，支持C++、Python、Java框架，基于角色的编程模型，使用zookeeper进行选举，使用LXC对CPU和内存进行隔离，实现了四个框架Hadoop，Torque,MPI和Spark。

5.1 Hadoop移植

1500行代码，Hadoop和mesos天然契合，做了下面改变：

• 写了一个Hadoop调度器来连接mesos，监控任务运行；
• 使用延迟调度来达到更好的数据本地行；
• 在计算节点设置共享文件服务以保证map和reduce之间的数据传输

5.2 Torque和MPI移植

360行Python代码修改Torque集群资源管理器；
200行Python代码修改MPI

5.3 Spark框架

Spark使用Mesos的executor长期运行的特性，来在每个executor中缓存内存中的一片数据集，然后在之后的多次迭代中使用缓存的数据。这种缓存是使用一种可容错的方式实现的：如果一个节点丢失，Spark能够记住如何重新计算在这个节点上的数据。

6. 评测

评测部分只针对关键的结果进行分析，详细结果可以查看原论文。

6.1 微基准测试

负载;

• Hadoop实例，混合运行着基于Facebook上的工作负载的小作业和大作业。选用hive benchmark中的负载，大多为小作业，在25分钟内间隔14秒提交100个任务，包含上图负载。
• 大型Hadoop负载混合，一个包含2400个任务的IO密集型文本搜索作业，在前一个任务完成后提交后一个作业，顺次执行。
• spark运行5个迭代的机器学习作业（交替最小二乘法，协同过滤算法），间隔2分钟提交作业。
• MPI，负载来自SPEC MPI2007benchmark，6个小作业2个大作业，每个作业都是24个并行任务，在特定时刻提交这两个任务到两个集群。
  对比：
  静态划分和mesos调度，时间：半个小时
  
  
  结果：
• 资源利用率提高
• 任务执行时间缩短

6.2 开销

MPI负载采用LINPACK的benchmark
Hadoop采用wordcount
没有mesos VS有mesos 50.9S和51.8秒 160秒和166秒

6.3 延迟调度实现数据本地化

负载：scan100G的文件的Hadoop任务，采用没有延迟、1S延迟和5S延迟调度。
结果：静态分区具有很低的数据本地行；没有延迟调度的mesos提高了数据本地行；1S延迟调度数据本地化达到90%;5S则达到95%。

6.4 Spark实验

通过在Hadoop和Spark上运行相同的机器学习任务，负载都为29G的数据文件，迭代30轮，spark比Hadoop执行时间提高了10倍。

6.5 可扩展性

在1万到5万个节点之间，启动一个任务的延迟开销小于1S。

6.6 错误恢复

包含200–4000个slave后台进程，杀死活动的主节点之后计算恢复的平均时间MTTR是所有的slave节点和集群框架连接到第二个主节点的时间。在所有的测试用例中，MTTR在4-8s之间，而其中3s的置信区间达到95%。

6.7 性能隔离

使用容器来隔离MediaWiki网络服务（包含大量运行PHP的Apache进程）和一个“hog”应用程序（包含256个无限循环轮转的进程）的CPU的使用只表现出30%的请求延迟的增加，而不用容器运行这两个程序会导致550%的请求延迟的增加。

7. 总结

• mesos提出了一种新的资源管理框架，基于资源供给的方式可以支持多种不同计算框架运行在同一个集群中，这是开创性的。
• mesos适合于短作业调度
• mesos也存在一些缺点：调度不是全局最优的；并发度不高；*调度器存在单点瓶颈；无法支持资源抢占；DRF调度策略过于理想；