集群资源统一管理和调度技术综述

李永峰，周敏奇，胡华梁

（1．华东师范大学 软件学院，上海 200062；2．浙江理工大学 经济管理学院，杭州 310018）

0 引 言

近年来，随着互联网的快速发展，全球数据量正呈爆炸式增长，数据成为当今社会增长最快的资源之一．根据国际数据公司IDC的监测统计，2011年全球数据总量达到1．8ZB（1ZB等于1万亿GB），并且以每两年翻番的速度在增长．预计到2020年，全球数据总量将达到40ZB．

如此增长迅速、庞大复杂的数据资源，给传统的数据分析、处理技术带来了巨大的挑战．传统单台高性能服务器的数据处理能力已经不能满足大量的网络服务和越来越多的数据密集型应用的需求，取而代之的是商业服务器集群，它已经成为主要的数据分析平台．因此，更多的科研人员和互联网公司，包括Google、微软、Facebook等，致力于开发各种各样的分布式计算框架，用于支持不同类型的数据密集型应用，主要有MapReduce、Spark、Storm、S4等．这些计算框架诞生于不同公司或者实验室，各有所长，各自解决某一类特定领域的应用问题，如支持离线计算、在线计算、迭代式计算、流式计算、内存计算等．

新的应用不断涌现，新的计算框架也将不断产生，然而却不存在一种统一的计算框架能适合所有的应用场景．因此，大部分互联网公司往往需要部署和运行多个计算框架，从而为每个应用选择最优的计算框架．传统的Standalone部署模式，即每个计算框架部署在独立的集群上，不能充分利用集群计算资源，并且多个集群也可能导致数据冗余度增加．比较有效的方式是，让不同计算框架复用同一个集群，以提高集群利用率和减少大数据集备份的开销．

在此背景下，基于分布式计算的发展，产生了一种新型的服务计算模型：集群资源统一管理平台．集群资源统一管理平台（实际上就是资源统一管理系统）允许同时容纳和管理多种计算框架，使得人们更能充分利用集群资源．进一步说，将各个计算框架部署并运行在统一的资源管理平台上，可以实现框架的资源统一管理和分配，使多个计算框架共享一个集群，而不再是“一个计算框架一个集群”．这样就更能充分利用集群资源，降低运维成本和硬件成本．

虽然高性能计算（High Performance Computing，HPC）领域在集群管理方向已经有很多经典应用，然而高性能计算的集群环境不同于一般商用服务器搭建的集群，通常需要一些特殊的硬件，如Infiniband和SANs等．也就是说，高性能计算在调度资源时不需要考虑数据局部性；而在廉价的商用服务器搭建的集群上进行大数据分析，则既要考虑计算资源的复用，又要考虑数据资源的复用．

近年来，有一些同时考虑计算资源和数据资源复用的系统，典型代表有Apache YARN（Yet Another Resource Negotiator）［1］、Facebook Corona［2］和Berkeley Mesos［3］．这些开源的系统都是为了解决编程模型和计算框架多样化环境下，不同框架间的资源隔离和共享问题．目前已经有很多公司正在使用这些资源管理系统，比如Twitter、Facebook、豆瓣等．另外一类新兴的集群资源管理技术是云技术（Clouds）．云技术是通过提供一种低层次的资源抽象：虚拟机（Virtual Machines，VMs），对应用进行隔离，代表性的系统有Amazon EC2［4］和Eucalyputs［5］等．

本文的第1节介绍资源统一管理和调度的应用背景．第2节介绍多维度资源的表示模型及管理方案．第3节介绍资源调度模型的发展趋势以及各种调度技术．第4节总结全文并展望资源统一管理和调度的未来发展趋势．

1 应用背景

如前所述，共享集群是指多个不同系统（计算框架）部署和运行在同一个集群上．集群共享可以提高资源利用率，并降低系统硬件成本和运维成本．因此，考虑到资源利用率、运维成本和数据共享等因素，很多公司都希望采用共享集群技术将所有的系统部署到一个公共集群中，让不同的系统共享集群的资源，并能够对资源进行统一使用．

常见的共享集群的解决方案有两种：静态划分集群和划分虚拟机［6］．静态划分集群是指物理上将整个集群划分成不同子集群，每个框架独立地部署和运行于若干节点上，计算框架彼此之间没有任何联系．而划分虚拟机则是采用云技术将集群划分成多个虚拟机，然后将若干虚拟机分配给某一个框架．这两种共享集群的方式既不能提高集群利用率，也不能有效地共享数据．最主要的是共享集群解决方案和多种计算框架的资源分配粒度的不匹配．很多计算框架采用一种细粒度的资源共享模型，如Hadoop［7］、Dryad［8］，即将每个节点以资源槽（slot）形式划分和管理，且作业由多个短任务组成，每个任务执行需要申请匹配的slot．作业拆分成多个短任务，每个节点上允许运行多个任务，可以使作业获得较高的数据本地性，即每个作业很快地在其输入数据存储的节点上运行．此外，这种短任务形式使得计算框架获得高利用率和扩展性．但是，由于不同计算框架均是独立开发，很难跨框架间执行细粒度的集群和数据集的共享．

对于较小的数据量，静态划分集群可以很好地满足用户的需求．但是，随着数据量急剧增长，集群间的数据复制开销越来越大．伴随云技术的快速发展，为资源统一管理和调度提供了技术保证和条件．集群资源管理系统是集群系统软件的重要组成部分，它可以根据用户的需求，统一管理和调度集群的软、硬件资源，保证用户公平合理地共享资源，形成对用户透明的单一管理系统，提高资源的利用率和吞吐率，从而达到更高的总体性能．图1所示是一个典型的资源统一管理和调度的框架：资源统一管理系统已经不再局限于只支持一种计算框架，而是朝着对多种框架进行统一管理的方向发展．

相比于“一种计算框架一个集群”的模式，共享集群的模式存在如下三个优点．

（1）硬件共享，资源利用率高．如果每个框架一个集群，则往往由于应用程序的数量和资源需求的不均衡，使得在某段时间内，有些计算框架的资源紧张，而另外一些集群资源比较空闲．共享集群模式则通过多框架共享资源，使得集群中的资源得到更加充分的利用．

（2）人员共享，运维成本低．采用“一种计算框架一个集群”的模式，可能需要多个管理员来管理和维护集群，进而增加运维成本；而共享模式下，只需要少数几个管理员即可完成多个框架的统一管理．

（3）数据共享，数据复制开销低．随着数据量的暴增，跨集群的数据移动不仅需要花费更长的时间，且硬件成本也会随之增加；而共享集群可让多个框架共享数据和硬件存储资源，这将大大减少数据复制的开销．

简言之，集群资源统一管理系统需要支持多种计算框架，并需要具有扩展性、容错性和高资源利用率等几个特点．一个行之有效的资源统一管理系统需要包含资源管理、分配和调度等功能．下面将逐一对这几个功能进行阐述．

图1 资源统一管理与调度系统基本架构Fig．1 The architecture of resource uniform management and scheduling

2 集群资源管理

集群资源管理通常由两部分组成：资源表示模型和资源分配模型．因为这两部分是耦合在一起的，所以对集群资源管理进行优化时，则需要同时结合这两部分进行考虑．资源表示模型用于描述集群资源的组织方式，是集群资源统一管理的基础．狭义上来讲，计算资源是指具有计算能力的资源，如CPU和GPU等．但实际上，对系统计算有影响的资源都可以划分到计算资源的范畴，包括内存、磁盘大小、I／O和网络带宽等．合理的资源表示模型，可以有效地利用资源，提高集群的利用率．

2．1 基于slot的资源表示模型

集群中每个节点的资源都是多维的，包括CPU、内存、网络I／O和磁盘I／O等．为了简化资源管理问题，很多计算框架［7－8］，如Hadoop和Dryad，均引入“槽位”（slot）概念，并采用slot组织各个节点上的计算资源．实际上，基于slot的资源表示模型就是将各个节点上资源等量切分成若干份，每一份用一个slot表示，同时规定任务可以根据实际需求占用多个slot．通过引入“slot”这一概念，各个节点上的多维度资源被抽象成单一维度slot，这样可以把复杂的多维度资源分配问题转化成简单的slot分配问题，从而大大降低了资源管理问题的复杂度．

更进一步说，slot相当于任务运行“许可证”．一个任务只有得到该“许可证”后，才能获得运行的机会．这意味着，每个节点上的slot数量决定了该节点上最大允许的任务并发度．同时为了区分不同任务所用资源量的差异，如Hadoop的作业被分为Map Task和Reduce Task两种类型，slot则被分为Map slot和Reduce slot两种类型，并且分别只能被Map Task和Reduce Task使用．图2所示是一个典型的基于slot的资源管理模型：JobTracker主要负责资源管理和作业调度，而每个节点上对应一个TaskTracker，向JobTracker汇报节点上的资源，并负责管理和调度JobTracker分配的任务．

图2 基于slot的资源表示模型Fig．2 The resource representation model based on slot

基于slot的资源表示模型采用静态资源配置策略，即每个节点事先配置好可用的slot数目，一旦启动后就无法动态修改．考虑到实际应用场景中，不同作业对资源的需求往往具有较大差异，静态配置slot数量往往会导致节点上某些资源利用率过高或者过低．譬如，内存密集型作业往往会有很多Reduce Task，运行时会占用大量Reduce slot，节点上的内存被占用而无法启动Map Task，进而导致内存利用率较高，而CPU利用率则较低．为了解决该问题，文献［9］提出了一种动态调整节点上slot数量的方案．该方案假设在每个节点上有一个动态slot池，slot数量动态调整模块（SlotsAdjuster）则可以根据节点上的资源利用率动态调整slot数量，以便更合理地利用资源．这种基于动态的slot资源管理方案已经在阿里的“云梯”集群上投入了使用．

对于一个MapReduce应用程序而言，Map Task优先得到调度，而只有当Map Task完成数目达到一定比例（通常为5%）后，Reduce Task才开始获得调度机会．因此，从单个应用程序看，在开始运行时，Map slot资源紧张而Reduce slot空闲，而当Map Task全部运行完成后，Reduce slot紧张而Map slot空闲．很明显，这种区分slot类别的资源管理方案在一定程度上减低了slot的利用率．文献［10］提出了一种基于无类别slot资源管理方案，即不再区分Map slot和Reduce slot，而是只有一种slot，并让所有的任务共享所有slot，至于如何将这些slot分给不同任务，则完全由调度器来决定．

2．2 基于真实资源需求量的资源表示模型

采用上述基于无类别slot资源管理方案，集群中只有一种资源slot．因此，这就意味着各个节点上的slot是同质的，即一个slot实际上代表了相同的资源．然而，在实际应用环境中，用户应用程序对资源需求往往是多样化的、异构的．这种基于无类别slot的资源划分形式的划分粒度仍过于粗糙，很容易会造成节点的资源利用率过高或过低［11］．如，管理员事先划分好一个slot代表2GB内存和1个CPU，如果一个应用程序的任务只需要1GB内存，则会产生“资源碎片”，从而降低集群资源的利用率；同样，如果一个应用程序需要3GB内存，则会隐式地抢占其他任务的资源，从而产生资源抢占现象，可能导致集群利用率过高．因此，寻求一种更精细的资源划分方法显得极为重要．

回归资源分配的本质，即根据任务的资源需求为其分配集群中的各类资源．在实际系统中，资源本身就是多维度的，包括CPU、内存、磁盘和网络等，如果想要精确控制资源分配，基于slot的划分概念不再适用，最直接有效的方法是让任务直接向调度器申请自己需要的资源（比如某个任务可以申请1．5 GB内存和1个CPU），而调度器则按照任务实际需求为其精细地分配对应的资源量，不再简单地将一个slot分配给它，如图3所示，TaskTracker向JobTracker汇报节点上的详细的资源量（这里暂时只考虑CPUs，Memory），而Job－Tracker根据作业的真实需求量来分配任务．

图3 基于真实资源需求量的资源表示模型Fig．3 The resource representation model based on real demands for resource

对于任何共享集群的系统，资源分配都是一个至关重要的模块．一个最常用的分配策略是最大最小公平（max－min fairness）原则，最早是用于控制网络流量，以实现公平分配网络带宽［12］．最大最小公平策略的基本含义是使得资源分配的最小分配量尽可能最大，它可以防止任何网络流被“饿死”，同时在一定程度上尽可能增加每个流的速率．因此，最大最小公平被认为是一种很好权衡有效性和公平性的自由分配策略，在经济、网络领域有着广泛的应用，由其演变出来的加权最大最小公平模型广泛地被一些资源分配策略采用，如基于优先级、预留机制和限期的分配策略．最大最小公平模型同时也保证分配隔离，即用户确保接收自己的分配量而不考虑其他用户的需求［11］．

基于这些特点，大量的分配算法被提出来实现不同准确度的最大最小公平模型，譬如轮询、均衡资源共享［13］和加权公平队列［14］等．这些算法被应用于各种各样的资源分配上，包括网络带宽［15－17］、CPU［14，18］、内存［18］以及二级存储空间．但这些公平分配的工作主要集中在单一资源类型．同样，在多类型资源环境和需求异构化下，公平合理的分配策略也很重要．

为了支持多维度资源调度，越来越多的分配算法被提出［19－20］．文献［11］提出了一种主资源公平调度算法（Dominant Resource Fairness，DRF）．该算法扩展了最大最小公平算法，使其能够在保持分配公平前提下，支持多维度资源的调度．在DRF算法中，将所需份额（资源比例）最大的资源称为主资源，而DRF的基本设计思想则是将最大最小公平算法应用于主资源上，进而将多维资源调度问题转化为单维资源调度问题，即DRF总是最大化所有主资源占用量中最小的．由于DRF被证明非常适合应用于多资源和复杂需求的环境中，因此被越来越多的系统所采用，其中包括Apache YARN和Apache Mesos．

3 集群资源调度

资源调度是根据一定的资源使用规则，在不同资源使用者之间进行资源调整的过程．不同的计算任务对应着不同的资源使用者，每个计算任务在集群节点上对应于一个或多个进程（或者线程）．资源调度的目的是将用户任务分配到合适的资源上，使得在满足用户需求的前提下，任务完成时间尽量小，且资源利用率尽量高．

资源调度最终要实现时间跨度、服务质量、负载均衡、经济原则最优的目标．由于不同资源管理系统的架构不同，资源的管理和调度没有统一标准，基于各种调度模型的调度算法有很多．下面将逐一进行阐述．

3．1 资源调度模型

文献［21］将任务调度模型分为应用模型、计算平台模型和性能目标模型．应用模型涉及如何将应用划分为任务、如何考虑任务的属性特征等，典型的任务模型有依赖任务模型DAG、Map－Reduce任务模型以及流式作业；计算平台模型是对系统中的资源抽象，其中最重要的资源是计算机的计算资源和网络资源；性能指标模型可以分为基于系统的目标和基于用户的目标两类．基于系统的性能模型主要关注整个系统的资源利用率、吞吐量、效率和公平性等指标，而基于用户的性能指标包括应用的最短完成时间、周转时间、平均延迟和加权完成时间等指标．

资源管理调度模型按照调度实体之间的关系可以分为统一资源调度模型和多资源调度协作调度模型．按照资源的组织调度形式可分为集中调度模型、层次调度模型和非集中调度模型．而在近期，文献［22］公布了Google下一代集群管理系统Omega的设计细节，主要介绍了Google经历的三代资源调度器的架构，如图4所示，分别是中央式调度模型、双层调度模型和共享状态调度模型．

图4 Google提出的三种调度模型架构Fig．4 Schematic overview of the sceduling architextures proposed by Google

中央式调度模型（Monolithic Scheduler），即所有的资源由一个中央调度程序调度，所有系统可用的相关信息都被聚集在中心机上．其典型的代表是MRv1中JobTracker的实现：集群中所有节点的信息和其资源量都被统计后，存放于JobTracker中，资源的管理和作业的调度都放到JobTracker进程中完成［23］．这种设计方式的缺点很明显．首先，扩展性差，集群规模受限．JobTracker既要负责集群管理，还要负责作业调度，很难赶得上作业和任务数量的增长．其次，框架支持性差，任务单一．目前，MRv1只能支持MapReduce作业，而新兴的流式作业、迭代作业等的调度策略并不能嵌入在中央式调度器中．

文献［22］还提到了一种对中央式调度器的优化方案：将每种调度策略放到单独一个路径（模块）中，不同的作业由不同的调度策略进行调度．这种方案在作业量和集群规模较小时，能大大缩短作业响应时间．但由于所有策略仍在一个集中式的组件中，整个系统的扩展性并没有变得更好．

双层调度模型（Two－level Scheduler）则结合上述优化方案，采用分而治之策略（或策略下放机制）解决了中央式调度器的不足．双层调度器仍保留一个简化后的中央式调度器，但调度策略则下放到各个应用程序的调度程序来完成．当前比较有名的开源资源统一管理和调度系统Mesos［24］和YARN［25－26］均是采用双层调度模型．双层调度模型的特点是，各个计算框架调度器并不知道整个集群资源使用情况，只是被动地接收资源．即简化的中央式调度器仅负责管理资源，将可用的资源推送给各个框架，而框架自己选择使用还是拒绝这些资源；一旦框架接收到新资源后，再进一步调用自己的调度器将资源分配给其内部的各个应用（各个MapReduce作业），进而实现双层调度．

但是，双层调度模型也存在一些不足：①各个框架无法探知整个集群的实时资源使用情况，而对于一些应用，为之提供实时资源使用情况可以为之提供潜在的优化空间；②采用悲观锁，并发粒度小．双层资源调度模型采用悲观锁，即在中央调度器中对资源进行加锁控制．当资源调度器将可用资源推送给任意框架时，就会对这部分资源加全局锁，其他框架无法使用这部分资源（即使这部分资源并未被使用）．等到该框架返回资源使用情况后，中央调度器释放资源的全局锁，此时才能够将资源推送给其他框架使用，这大大限制了系统并发性．实际上在数据库领域，悲观锁与乐观锁争论一直不休，悲观锁通常采用锁机制控制并发，这会大大降低性能，而乐观锁则采用多版本并发控制（Multi－Version Concurrency Control，MVCC），典型代表有MySQL InnoDB，这种并发控制机制则可以大大提升性能．

为了克服双层调度模型的以上两个不足之处，Google提出一种基于共享状态的调度模型（Shared State Scheduler），并依据该模型研发下一代资源管理系统Omega［22］．共享状态调度是将双层调度中的中央式资源调度模块简化成一种持久化的共享数据，这里的“共享数据”实际上就是整个集群的实时资源使用信息．一旦引入共享数据后，共享数据的并发访问方式就成为该调度模型的核心，而Omega则采用了传统数据库中基于多版本的并发访问控制方式（也称“乐观锁”，MVCC，Multi－Version Concurrency Control），进而大大提升了系统并发性．

3．2 资源调度策略

在分布式计算领域中，资源分配问题实际上是一个任务调度问题．它的主要任务是根据当前集群中各个节点上的资源（包括CPU、内存和网络等资源）的剩余情况与各个用户作业的服务质量（Quality of Service，QoS）要求，在资源和作业／任务之间做出最优的匹配．由于用户对作业服务质量的要求是多样化的，因此，分布式系统中的任务调度是一个多目标优化问题，更进一步说，它是一个典型的NP－hard问题．

通常，分布式系统都会提供一个非常简单的调度机制：FIFO（First In First Out），即先来先服务．在该调度机制下，所有的用户作业都被提交到一个队列中，然后由调度器按照作业提交时间的先后顺序来选择将被执行的作业．

但随着分布式计算框架的普及，集群的用户量越来越大，不同用户提交的应用程序往往具有不同的服务质量要求，典型的应用有以下三种．

（1）批处理作业．这种作业往往耗时较长，对完成时间一般没有严格要求，如数据挖掘、机器学习等方面的应用程序．

（2）交互式作业．这种作业期望能及时返回结果，如SQL查询（Hive）．

（3）生产性作业．这种作业要求有一定量的资源保证，如统计值计算、垃圾数据分析等．

此外，不同应用程序对硬件资源的需求量也是不同的，如过滤／统计类作业一般为CPU密集型作业，而数据挖掘、机器学习的作业一般为I／O密集型作业．传统的FIFO调度算法虽然简单明了，但是它忽略了不同作业对资源的需求差异，严重时会影响作业的执行．因此，传统的FIFO调度策略不仅不能满足多样化需求，也不能充分利用硬件资源．

为了克服单队列FIFO调度器的不足，多种类型的多用户多队列调度器相继出现．这些调度策略允许管理员按照应用需求对用户或者应用程序分组，并为不同的分组分配不同的资源量，同时通过添加各种约束防止单个用户或应用程序独占资源，进而满足多样化的QoS需求．当前主要有两种多用户作业调度器的设计思路：第一种是在一个物理集群上虚拟多个子集群，典型的代表是HOD（Hadoop On Demand）调度器；另一种是扩展传统调度策略，使之支持多队列多用户，这样，不同的队列拥有不同的资源量，可以运行不同的应用程序，典型的代表是Yahoo！的Capacity Scheduler和Facebook的Fair Scheduler．

3．2．1 HOD（Hadoop On Demand）

HOD调度器［27］是一个在共享物理集群上管理若干个Hadoop集群的工具．用户可以通过HOD调度器在一个共享物理集群上搭建若干个独立的虚拟Hadoop集群，以满足不同的用途．比如，不同集群运行不同类型的应用程序．同时HOD调度器可使管理员和用户轻松地快速搭建和使用Hadoop．

HOD调度器的工作过程实现中依赖一个资源管理器来为之分配回收节点和管理各个节点上的作业运行情况，如监控作业运行、维护作业的运行状态等．而HOD只需在资源管理分配的节点上运行Hadoop守护进程和MapReduce作业即可．当前，HOD采用的资源管理器是开源的Torque资源管理器［28］．Torque资源管理器中也运行一个调度守护进程，默认情况下，调度守护进程采用FIFO调度机制，将所有作业存放到一个队列中，并按照到达先后顺序依次调度．需要注意的是，Torque中的调度机制是可插拔的，Torque还提供许多其他多种可选的调度机制．

3．2．2 Capacity Scheduler

Capacity Scheduler是由Yahoo！开发的多用户调度器，主要用来弥补已有HOD的不足之处．Capacity Scheduler以队列为单位划分资源，每个队列可以设定一定比例的资源最低保证和使用上限．同时，每个用户也可设定一定的资源使用上限以防止资源独占，而当一个队列的资源空闲时，可暂时将空闲资源共享给其他队列．

Capacity Scheduler通常采用三级调度策略，当集群中出现空闲资源时，调度器依次选择一个队列，选择该队列中的一个作业和该作业中的一个任务．队列的选择总是优先将资源分配给资源使用率最低的队列，即resourceoccupied／capacity最小的队列，其中resourceoccupied表示队列当前已经使用的资源数量，capacity为队列的资源容量；在队列内部，待调度的作业按照某种排序策略进行排序，如支持优先级或者FIFO等．当选择任务时，调度器会依次遍历排序的作业，并检查当前的资源量是否足以运行当前作业的一个任务．

Capacity Scheduler提供了对大内存任务的调度机制．默认情况下，假设所有任务是同质的，资源分配粒度也是固定的，而这并没有考虑那些内存密集型的任务．为了解决该问题，Capacity Scheduler可根据任务的内存需求量为其多分配一些资源，如果资源不够时，则通过资源预留机制为该作业预留资源，直到满足作业需求为止．同时为了提高任务的数据本地性，Capacity Scheduler采用了作业延迟调度策略：当选中一个作业后，如果在该作业中未找到满足数据本地性的任务，则调度器会让该作业跳过一定次数的调度机会，直到找到满足本地性的任务或者达到跳过次数上限为之．

3．2．3 Fair Scheduler

为了解决HOD调度算法产生的问题，Facebook也提出了公平调度算法（Fair Scheduling）［30］．图5所示是一个典型的公平调度模型．公平调度器与Capacity Scheduler类似，按资源池（类似于队列的概念）来组织作业，并把资源公平地分到这些资源池内．公平调度算法尽可能保证每个用户都获得相等的资源份额．当有新用户提交作业后，系统会将资源赋给这些新用户，从而使得每一个用户都能够获取等量的资源．除了提供公平共享方法之外，公平调度器允许赋给资源池最低共享资源保证，这能够确保特定用户、群组或者应用程序总能获得到足够的资源．当一个资源池包含作业时，该资源池至少能获得最低保证共享资源，但是当资源池不完全需要所拥有的保证共享资源时，额外的部分会在其他资源池间进行切分．

图5 公平调度模型Fig．5 Fair scheduling model

同Capacity Scheduler一样，公平调度器也采用三级调度策略：资源池选择、作业选择和任务选择，即依次选择一个合适的资源池，然后选择该资源池中的一个作业和该作业中的一个任务，但具体采用的策略稍有不同．资源池的选择在不同的条件下采用不同策略：当存在资源使用量小于最低保证资源量的资源池时，优先选择资源使用率最低的资源池，否则，选择作业权重比最小的资源池，作业权重比（jobWeight＝poolWeight／poolRunningJob－Num）最小意味着资源池分配的资源比例最低，选择作业权重比最小的资源池能最大化资源公平共享．选定一个资源池后，Fair Scheduler总是优先将资源分配给资源池中任务权重比最小的作业．而任务选择策略都考虑数据本地性，进而提高作业运行效率［30］．

Fair Scheduler也是一个多用户调度器，同样添加了多层级别的资源限制条件以更好地让多用户共享一个集群，比如资源池资源限制、用户作业数目限制等．然而，Fair Scheduler又增加了很多新的优化机制．譬如，为了提高数据本地性，Fair Scheduler采用了延时调度机制［31］，即当出现空闲资源时，如果选中的作业没有满足节点局本地化或机架局本地化的任务，则暂时把资源让给其他作业，直到找到一个满足数据本地性的任务或者达到一个时间阈值之后，此时不得不为之选择一个非本地性的任务．为了更好地实现延时调度，提高作业运行效率，Fair Scheduler采用双层延迟调度算法：为了找到一个节点本地化的任务最长可等待时间W1或者进一步等待时间W2找到一个机架本地化任务．

Fair Scheduler允许不同资源池间的资源抢占．当一个资源池有剩余资源时，Fair Scheduler会将这些资源暂时共享给其他资源池；而一旦该资源池有新的作业提交，调度器则为其回收资源．如果一段时间后该资源池仍得不到本属于自己的资源，则调度器会通过杀死任务的方式抢占资源．Fair Scheduler同时采用了两种资源抢占方式：最小资源量抢占和公平共享量抢占．最小资源量抢占是指一个资源池的最小资源量在一定时间内得不到满足，则会从其他超额使用资源的资源池中抢占资源；而公平共享量抢占是指如果一定时间内一个资源池的公平共享量的一半得不到满足，则该资源池也会从其他资源池中抢占．进行资源抢占时，调度器会选择超额使用资源的资源池，从中找到并杀掉启动时间最早的任务来释放资源，从而最小化工作的浪费．

同时，Fair Scheduler为用户提供了一个可扩展的负载均衡器，即可以将系统中的所有任务按照数量平均分配到各个节点上．表1从多个方面列举了Fair Scheduler与Capacity Scheduler两种调度器的异同．

表1 Fair Scheduler与Capacity Scheduler比较Tab．1 Fair Scheduler VS．Capacity Scheduler

目前，针对多用户共享集群的资源调度，围绕着Capacity Scheduling和Fair Scheduling衍生出很多改进算法［32－37］．还有一些关于任务调度的改进算法［31，38－39］，均采用就近原则，尽量把任务调度到所需数据所在的节点上执行．不同的调度算法，对应不同的期望值，譬如运行时间、资源利用率和吞吐量等．文献［40］中提出的一种自适应调度器（Adaptive Scheduler），是以用户期望运行时间为目标的调度器．该调度器根据每个作业会被分解成多个任务的事实，通过已经运行完成的任务的运行时间估算剩余任务的运行时间，进而使得该调度器能根据作业的进度和剩余时间动态地为作业分配资源，以期望作业在规定时间内完成．文献［41］的自学习调度器（Learning scheduler）是一种基于贝叶斯分类算法的资源感知调度器．与现有的调度器不同，该调度器将贝叶斯分类算法应用到资源分配中，根据节点上的资源使用情况和用户提交作业的资源利用率，利用模式分类器对节点和作业进行分类（“Bad”和“Good”两类）．调度器可以合理地任务调度到合适的节点上运行，从而加快作业完成时间．另外，还存在一种新的调度策略—动态优先级调度（Dynamic Priority Scheduler）［42］．该调度策略允许用户动态调整自己获取的资源量以满足其对服务质量的要求．

4 结 论

本文总结了共享集群技术的发展趋势，并介绍了共享集群的资源管理和调度技术．集群资源管理通常由两部分组成：资源表示模型和资源分配模型．在多类型资源的集群环境下，资源管理方案可以根据资源管理维度来划分为：基于slot的资源模型和基于真实资源需求的资源模型．基于slot的资源管理方案将多维度的资源抽象成一维slot，这样可以方便系统的分配与调度的实现．而基于真实资源需求的资源管理方案则能够提升集群资源的利用率，进而提升吞吐量．之后本文详细阐述了资源调度模型的发展过程，主要经历集中式调度模型、两层调度模型和共享状态的调度模型，并且每种调度模型都有与之对应的开源的资源管理系统．此外，本文分析和总结了现有的资源调度技术以及对应的改进版本，并对较为常用的调度策略进行了对比．

随着越来越多的资源管理系统开源化，资源管理和调度技术已经成为研究热点．接下来的研究工作主要集中在两个方向：支持更多类型的资源，和支持更多不同的计算框架．目前，资源管理技术还只限于CPU和内存两类资源，将来可以考虑网络I／O和磁盘I／O等．支持更多的计算框架则能充分利用集群资源．已开源的资源管理系统，如Apache YARN和Apache Mesos，都可以支持多种计算框架，但存在某些资源管理系统可能对某些框架不适合的问题．譬如，Spark，一种非常流行的内存计算（或者迭代式计算）框架并不能很好地介入YARN，原因在于YARN中的资源预留机制．所以，设计一个能同时支持多种计算框架的资源管理系统将面临巨大挑战，但也是工业界的一个迫切需求．

［1］Apache YARN［EB／OL］．http：／／hadoop．apache．org／docs／current／hadoop－yarn／hadoop－yarn－site／YARN．html．

［2］Facebook Corona［EB／OL］．https：／／github．com／facebook／hadoop－20／tree／master／src／contrib／corona．

［3］Apache Mesos［EB／OL］．http：／／mesos．apache．org．

［4］Amazon EC2［EB／OL］．http：／／aws．amazon．com／ec2．

［5］DANIEL N，RICHARD W，CHRIS G，et al．The Eucalyptus Open－Source Cloud－Computing System［C］．Proceedings of 9th International Symposium on Cluster Computing and the Grid（CCGrid 09）．Shanghai，China，2009．

［6］HINDMAN B，KONWINSI A，ZAHARIA M，et al．Mesos：A Platform for Fine－Grained Resource Sharing in the Data Center［C］．Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation（NSDI 2011）．Boston，2011．

［7］Apache Hadoop［EB／OL］．［2014－07－31］．http：／／hadoop．apache．org／．

［8］MICHAEL I，MIHAI B，YUAN Yu，et al．Dryad：distributed data－parallel programs from sequential building blocks［C］．Proceedings of the 2007 EuroSys Conference．Lisbon，Portugal，2007．

［9］梁 李 印．阿里Hadoop集 群 架 构 及 服 务 体 系［C／OL］／／Hadoop与 大 数 据 技 术 大 会（HBTC 2012）．http：／／hbtc2012．hadooper．cn，2012．

［10］MAO H，HU S Q，ZHANG Z Z，et al．A load－driven task scheduler with adaptive DSC for mapReduce［C］．Proceedings of IEEE／ACM International Conference on Green Computing and Communications（GreenCom2011），August 4－5，2011，Chengdu，China，2011．

［11］GHODSI A，ZAHRIA M，HINDMAN B，et al．Dominant resource fairness：fair allocation of multiple resource types［C］．Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation，NSDI，March 30－April 1，2011，Boston，2011．

［12］Max－min fairness［EB／OL］．http：／／en．wikipedia．org／wiki／Max－min＿fairness．

［13］WALDSPURGER C A，WEIHL W E．Lottery scheduling：flexible proportional－share resource management［C］．Proceedings of the first USENIX Symposium on Operating Systems Design and Implementation（OSDI），November 14－17，1994，Monterey，1994．

［14］DEMERS A，KESHAV S，SHENKER S．Analysis and simulation of a fair queueing algorithm［C］．Proceedings of the ACM Symposium on Communications Architectures ＆Protocols，1989．

［15］JON C R B，ZHANG H．WF2Q：worst＿case fair weighted fair queueing［C］．Proceedings of 15th IEEE INFOCOM＇96，March 24－28，1996，San Francisco，1996．

［16］PAWAN G．，GUO X G，HARRICK M V，et al．Start－time fair queueing：a scheduling algorithm for Integrated services packet switching networks［C］．Proceedings of the ACM SIGCOMM96 Conference on Applications．Stanford，USA，1996．

［17］STOICA I，SHENKER S，ZHANG H．Core－stateless fair queueing：qchieving qpproxinately fair bandwith allocations in high speed networks［C］．Proceedings of the ACM SIGCOMM1998 Conference on Applications．Vancouver，1998．

［18］CAPRITA B，CHAN W C，NIEH J，et al．Group ratio round－robin：O（1）proportional share scheduling for uniprocessor and multiprocessor systems［C］．Proceedings of the 2005 USENIX Annual Technical Conference．Anaheim，USA，2005．

［19］SUN X，SU S，XU P，et al．Multi－dimensional Resource Integrated Scheduling In a Shared Data Center［C］．Proceedings of 31st IEEE International Conference on Distributed Computing Systems Workshops（ICDCS2011 Workshops）．Minneapolis，USA，2011．

［20］JOE－WONG C，SEN S，LAN T，et al．Multi－Resource Allocation：Fairness－Efficiency Tradeoffs in a Unifying Framework［C］．Proceedings of the IEEE INFOCOM2012．2012，Orlando，USA，2012．

［21］钱琼芬，李春林，张小庆，等．云数据中心虚拟资源管理研究综述［J］．Application Research of Computers，2012（29）．

［22］SCHWARZKOPF M，KONWINSKI A，ABD－EL－MALEK M．Omega：flexible，scalable schedulers for large compute clusters［C］．Proceedings of Eighth Eurosys Conference 2013，EuroSys’13．Prague，2013．

［23］DEAN J，GHEMAWAT S．MapReduce：simplified data processing on large clusters［C］．Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation，OSDI．San Francisco，USA，2004．

［24］HINDMAN B，KONWINSI A，ZAHARIA M，et al．Mesos：aplatform for fine－grained resource sharing in the data center［C］．Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation，NSDI．Boston，USA，2011．

［25］MURTHY A C，DOUGLAS C，KONAR M，et al．Architecture of next generation Apache Hadoop MapReduce framework［R］．Technique report，Apache Hadoop，2011．

［26］VINOD K V，ARUN C M，CHRIS D，et al．Apache Hadoop YARN：yet another resource negotiator［C］．Proceedings of ACM Symposium on Cloud Computing．Santa Clara，CA，2013．

［27］Hadoop On Demand．http：／／hadoop．apache．org／docs／stable／hod＿scheduler．html．

［28］TORQUE Resource Manager．http：／／www．adaptivecomputing．com／products／open－source／torque／．

［29］Capacity Scheduler．http：／／hadoop．apache．org／docs／stable／capacity＿scheduler．html．

［30］ZAHRIA M，BORTHAKUR D，JOYDEEP S S，et al．Job scheduling for multi－user MapReduce cluster［R］．EECS Department，University of California，Berkeley，2009．

［31］ZAHRIA M，BORTHAKUR D，JOYDEEP S S，et al．Delay scheduling：a simple technique for achieving locality and fairness in cluster scheduling［C］．Proceedings of the 5th European conference on Computer systems．Paris，2010．

［32］王明阳，洪爵，冯圣中．面向多用户的集群资源部署策略［J］．Journal of Integration Technology，2013（3）：2－2．

［33］GUNHO L．Resource allocation and scheduling in heterogeneous cloud environments［D］．Electrical Engineering and Computer Sciences，Berkeley：University of California，2012．

［34］SHOKRIPOUR A，OTHMAN M，IBRAHIM H，et al．New method for scheduling heterogeneous multi－installment systems［C］．Proceedings of Future Generation Computer Systems，2012．

［35］GHANBARIA S，OTHMAN M．A priority based job scheduling algorithm in cloud computing［C］．Proceedings of Procedia Engineering，2012．

［36］SALEHHI M A，JAVADI B，BUYYA R．Preemption－aware admission control in a virtualized grid federation［C］．Proceedings of the 26th IEEE International Conference on Advanced Information Networking and Application（AINA2012），2012．

［37］SU W T，WU S M．Node capability aware resource provisioning in a heterogeneous cloud［C］．Proceedings of the 1st IEEE International Conference on Communications（ICCC2012），2012．

［38］ISARD M，VIJAYAN P，CURREY J，et al．Quincy：fair scheduling for distributed computing clusters［C］．Proceedings of the ACM SIGOPS22th Symposium on Operating Systems Principles，October 11－14，2009，Big Sky，Montana，2009．

［39］HUA Z J，XU X S，YANG S Q，et al．Research and implementation of local priority scheduling algorithm for MapReduce［C］．Proceedings of the 9th China Academic Communication Association Annual Meeting，2012．

［40］Adaptive Scheduler．http：／／issues．apache．org／jira／browse／MAPREDUCE－1380．

［41］Learning Scheduler．http：／／issues．apache．org／jira／browse／MAPREDUCE－1439．

［42］SANDHOLM T，LAI K．Dynamic proportional share scheduling in Hadoop［C］．Proceedings of the 15th Workshop on Job Scheduling Strategies for Parallel Processing，2010．