集群資源統(tǒng)一管理和調(diào)度技術(shù)綜述

李永峰，周敏奇，胡華梁

（1．華東師范大學(xué) 軟件學(xué)院，上海 200062；2．浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院，杭州 310018）

0 引 言

近年來(lái)，隨著互聯(lián)網(wǎng)的快速發(fā)展，全球數(shù)據(jù)量正呈爆炸式增長(zhǎng)，數(shù)據(jù)成為當(dāng)今社會(huì)增長(zhǎng)最快的資源之一．根據(jù)國(guó)際數(shù)據(jù)公司IDC的監(jiān)測(cè)統(tǒng)計(jì)，2011年全球數(shù)據(jù)總量達(dá)到1．8ZB（1ZB等于1萬(wàn)億GB），并且以每?jī)赡攴乃俣仍谠鲩L(zhǎng)．預(yù)計(jì)到2020年，全球數(shù)據(jù)總量將達(dá)到40ZB．

如此增長(zhǎng)迅速、龐大復(fù)雜的數(shù)據(jù)資源，給傳統(tǒng)的數(shù)據(jù)分析、處理技術(shù)帶來(lái)了巨大的挑戰(zhàn)．傳統(tǒng)單臺(tái)高性能服務(wù)器的數(shù)據(jù)處理能力已經(jīng)不能滿足大量的網(wǎng)絡(luò)服務(wù)和越來(lái)越多的數(shù)據(jù)密集型應(yīng)用的需求，取而代之的是商業(yè)服務(wù)器集群，它已經(jīng)成為主要的數(shù)據(jù)分析平臺(tái)．因此，更多的科研人員和互聯(lián)網(wǎng)公司，包括Google、微軟、Facebook等，致力于開(kāi)發(fā)各種各樣的分布式計(jì)算框架，用于支持不同類型的數(shù)據(jù)密集型應(yīng)用，主要有MapReduce、Spark、Storm、S4等．這些計(jì)算框架誕生于不同公司或者實(shí)驗(yàn)室，各有所長(zhǎng)，各自解決某一類特定領(lǐng)域的應(yīng)用問(wèn)題，如支持離線計(jì)算、在線計(jì)算、迭代式計(jì)算、流式計(jì)算、內(nèi)存計(jì)算等．

新的應(yīng)用不斷涌現(xiàn)，新的計(jì)算框架也將不斷產(chǎn)生，然而卻不存在一種統(tǒng)一的計(jì)算框架能適合所有的應(yīng)用場(chǎng)景．因此，大部分互聯(lián)網(wǎng)公司往往需要部署和運(yùn)行多個(gè)計(jì)算框架，從而為每個(gè)應(yīng)用選擇最優(yōu)的計(jì)算框架．傳統(tǒng)的Standalone部署模式，即每個(gè)計(jì)算框架部署在獨(dú)立的集群上，不能充分利用集群計(jì)算資源，并且多個(gè)集群也可能導(dǎo)致數(shù)據(jù)冗余度增加．比較有效的方式是，讓不同計(jì)算框架復(fù)用同一個(gè)集群，以提高集群利用率和減少大數(shù)據(jù)集備份的開(kāi)銷．

在此背景下，基于分布式計(jì)算的發(fā)展，產(chǎn)生了一種新型的服務(wù)計(jì)算模型：集群資源統(tǒng)一管理平臺(tái)．集群資源統(tǒng)一管理平臺(tái)（實(shí)際上就是資源統(tǒng)一管理系統(tǒng)）允許同時(shí)容納和管理多種計(jì)算框架，使得人們更能充分利用集群資源．進(jìn)一步說(shuō)，將各個(gè)計(jì)算框架部署并運(yùn)行在統(tǒng)一的資源管理平臺(tái)上，可以實(shí)現(xiàn)框架的資源統(tǒng)一管理和分配，使多個(gè)計(jì)算框架共享一個(gè)集群，而不再是“一個(gè)計(jì)算框架一個(gè)集群”．這樣就更能充分利用集群資源，降低運(yùn)維成本和硬件成本．

雖然高性能計(jì)算（High Performance Computing，HPC）領(lǐng)域在集群管理方向已經(jīng)有很多經(jīng)典應(yīng)用，然而高性能計(jì)算的集群環(huán)境不同于一般商用服務(wù)器搭建的集群，通常需要一些特殊的硬件，如Infiniband和SANs等．也就是說(shuō)，高性能計(jì)算在調(diào)度資源時(shí)不需要考慮數(shù)據(jù)局部性；而在廉價(jià)的商用服務(wù)器搭建的集群上進(jìn)行大數(shù)據(jù)分析，則既要考慮計(jì)算資源的復(fù)用，又要考慮數(shù)據(jù)資源的復(fù)用．

近年來(lái)，有一些同時(shí)考慮計(jì)算資源和數(shù)據(jù)資源復(fù)用的系統(tǒng)，典型代表有Apache YARN（Yet Another Resource Negotiator）［1］、Facebook Corona［2］和Berkeley Mesos［3］．這些開(kāi)源的系統(tǒng)都是為了解決編程模型和計(jì)算框架多樣化環(huán)境下，不同框架間的資源隔離和共享問(wèn)題．目前已經(jīng)有很多公司正在使用這些資源管理系統(tǒng)，比如Twitter、Facebook、豆瓣等．另外一類新興的集群資源管理技術(shù)是云技術(shù)（Clouds）．云技術(shù)是通過(guò)提供一種低層次的資源抽象：虛擬機(jī)（Virtual Machines，VMs），對(duì)應(yīng)用進(jìn)行隔離，代表性的系統(tǒng)有Amazon EC2［4］和Eucalyputs［5］等．

本文的第1節(jié)介紹資源統(tǒng)一管理和調(diào)度的應(yīng)用背景．第2節(jié)介紹多維度資源的表示模型及管理方案．第3節(jié)介紹資源調(diào)度模型的發(fā)展趨勢(shì)以及各種調(diào)度技術(shù)．第4節(jié)總結(jié)全文并展望資源統(tǒng)一管理和調(diào)度的未來(lái)發(fā)展趨勢(shì)．

1 應(yīng)用背景

如前所述，共享集群是指多個(gè)不同系統(tǒng)（計(jì)算框架）部署和運(yùn)行在同一個(gè)集群上．集群共享可以提高資源利用率，并降低系統(tǒng)硬件成本和運(yùn)維成本．因此，考慮到資源利用率、運(yùn)維成本和數(shù)據(jù)共享等因素，很多公司都希望采用共享集群技術(shù)將所有的系統(tǒng)部署到一個(gè)公共集群中，讓不同的系統(tǒng)共享集群的資源，并能夠?qū)Y源進(jìn)行統(tǒng)一使用．

常見(jiàn)的共享集群的解決方案有兩種：靜態(tài)劃分集群和劃分虛擬機(jī)［6］．靜態(tài)劃分集群是指物理上將整個(gè)集群劃分成不同子集群，每個(gè)框架獨(dú)立地部署和運(yùn)行于若干節(jié)點(diǎn)上，計(jì)算框架彼此之間沒(méi)有任何聯(lián)系．而劃分虛擬機(jī)則是采用云技術(shù)將集群劃分成多個(gè)虛擬機(jī)，然后將若干虛擬機(jī)分配給某一個(gè)框架．這兩種共享集群的方式既不能提高集群利用率，也不能有效地共享數(shù)據(jù)．最主要的是共享集群解決方案和多種計(jì)算框架的資源分配粒度的不匹配．很多計(jì)算框架采用一種細(xì)粒度的資源共享模型，如Hadoop［7］、Dryad［8］，即將每個(gè)節(jié)點(diǎn)以資源槽（slot）形式劃分和管理，且作業(yè)由多個(gè)短任務(wù)組成，每個(gè)任務(wù)執(zhí)行需要申請(qǐng)匹配的slot．作業(yè)拆分成多個(gè)短任務(wù)，每個(gè)節(jié)點(diǎn)上允許運(yùn)行多個(gè)任務(wù)，可以使作業(yè)獲得較高的數(shù)據(jù)本地性，即每個(gè)作業(yè)很快地在其輸入數(shù)據(jù)存儲(chǔ)的節(jié)點(diǎn)上運(yùn)行．此外，這種短任務(wù)形式使得計(jì)算框架獲得高利用率和擴(kuò)展性．但是，由于不同計(jì)算框架均是獨(dú)立開(kāi)發(fā)，很難跨框架間執(zhí)行細(xì)粒度的集群和數(shù)據(jù)集的共享．

對(duì)于較小的數(shù)據(jù)量，靜態(tài)劃分集群可以很好地滿足用戶的需求．但是，隨著數(shù)據(jù)量急劇增長(zhǎng)，集群間的數(shù)據(jù)復(fù)制開(kāi)銷越來(lái)越大．伴隨云技術(shù)的快速發(fā)展，為資源統(tǒng)一管理和調(diào)度提供了技術(shù)保證和條件．集群資源管理系統(tǒng)是集群系統(tǒng)軟件的重要組成部分，它可以根據(jù)用戶的需求，統(tǒng)一管理和調(diào)度集群的軟、硬件資源，保證用戶公平合理地共享資源，形成對(duì)用戶透明的單一管理系統(tǒng)，提高資源的利用率和吞吐率，從而達(dá)到更高的總體性能．圖1所示是一個(gè)典型的資源統(tǒng)一管理和調(diào)度的框架：資源統(tǒng)一管理系統(tǒng)已經(jīng)不再局限于只支持一種計(jì)算框架，而是朝著對(duì)多種框架進(jìn)行統(tǒng)一管理的方向發(fā)展．

相比于“一種計(jì)算框架一個(gè)集群”的模式，共享集群的模式存在如下三個(gè)優(yōu)點(diǎn)．

（1）硬件共享，資源利用率高．如果每個(gè)框架一個(gè)集群，則往往由于應(yīng)用程序的數(shù)量和資源需求的不均衡，使得在某段時(shí)間內(nèi)，有些計(jì)算框架的資源緊張，而另外一些集群資源比較空閑．共享集群模式則通過(guò)多框架共享資源，使得集群中的資源得到更加充分的利用．

（2）人員共享，運(yùn)維成本低．采用“一種計(jì)算框架一個(gè)集群”的模式，可能需要多個(gè)管理員來(lái)管理和維護(hù)集群，進(jìn)而增加運(yùn)維成本；而共享模式下，只需要少數(shù)幾個(gè)管理員即可完成多個(gè)框架的統(tǒng)一管理．

（3）數(shù)據(jù)共享，數(shù)據(jù)復(fù)制開(kāi)銷低．隨著數(shù)據(jù)量的暴增，跨集群的數(shù)據(jù)移動(dòng)不僅需要花費(fèi)更長(zhǎng)的時(shí)間，且硬件成本也會(huì)隨之增加；而共享集群可讓多個(gè)框架共享數(shù)據(jù)和硬件存儲(chǔ)資源，這將大大減少數(shù)據(jù)復(fù)制的開(kāi)銷．

簡(jiǎn)言之，集群資源統(tǒng)一管理系統(tǒng)需要支持多種計(jì)算框架，并需要具有擴(kuò)展性、容錯(cuò)性和高資源利用率等幾個(gè)特點(diǎn)．一個(gè)行之有效的資源統(tǒng)一管理系統(tǒng)需要包含資源管理、分配和調(diào)度等功能．下面將逐一對(duì)這幾個(gè)功能進(jìn)行闡述．

圖1 資源統(tǒng)一管理與調(diào)度系統(tǒng)基本架構(gòu)Fig．1 The architecture of resource uniform management and scheduling

2 集群資源管理

集群資源管理通常由兩部分組成：資源表示模型和資源分配模型．因?yàn)檫@兩部分是耦合在一起的，所以對(duì)集群資源管理進(jìn)行優(yōu)化時(shí)，則需要同時(shí)結(jié)合這兩部分進(jìn)行考慮．資源表示模型用于描述集群資源的組織方式，是集群資源統(tǒng)一管理的基礎(chǔ)．狹義上來(lái)講，計(jì)算資源是指具有計(jì)算能力的資源，如CPU和GPU等．但實(shí)際上，對(duì)系統(tǒng)計(jì)算有影響的資源都可以劃分到計(jì)算資源的范疇，包括內(nèi)存、磁盤(pán)大小、I／O和網(wǎng)絡(luò)帶寬等．合理的資源表示模型，可以有效地利用資源，提高集群的利用率．

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

集群中每個(gè)節(jié)點(diǎn)的資源都是多維的，包括CPU、內(nèi)存、網(wǎng)絡(luò)I／O和磁盤(pán)I／O等．為了簡(jiǎn)化資源管理問(wèn)題，很多計(jì)算框架［7－8］，如Hadoop和Dryad，均引入“槽位”（slot）概念，并采用slot組織各個(gè)節(jié)點(diǎn)上的計(jì)算資源．實(shí)際上，基于slot的資源表示模型就是將各個(gè)節(jié)點(diǎn)上資源等量切分成若干份，每一份用一個(gè)slot表示，同時(shí)規(guī)定任務(wù)可以根據(jù)實(shí)際需求占用多個(gè)slot．通過(guò)引入“slot”這一概念，各個(gè)節(jié)點(diǎn)上的多維度資源被抽象成單一維度slot，這樣可以把復(fù)雜的多維度資源分配問(wèn)題轉(zhuǎn)化成簡(jiǎn)單的slot分配問(wèn)題，從而大大降低了資源管理問(wèn)題的復(fù)雜度．

更進(jìn)一步說(shuō)，slot相當(dāng)于任務(wù)運(yùn)行“許可證”．一個(gè)任務(wù)只有得到該“許可證”后，才能獲得運(yùn)行的機(jī)會(huì)．這意味著，每個(gè)節(jié)點(diǎn)上的slot數(shù)量決定了該節(jié)點(diǎn)上最大允許的任務(wù)并發(fā)度．同時(shí)為了區(qū)分不同任務(wù)所用資源量的差異，如Hadoop的作業(yè)被分為Map Task和Reduce Task兩種類型，slot則被分為Map slot和Reduce slot兩種類型，并且分別只能被Map Task和Reduce Task使用．圖2所示是一個(gè)典型的基于slot的資源管理模型：JobTracker主要負(fù)責(zé)資源管理和作業(yè)調(diào)度，而每個(gè)節(jié)點(diǎn)上對(duì)應(yīng)一個(gè)TaskTracker，向JobTracker匯報(bào)節(jié)點(diǎn)上的資源，并負(fù)責(zé)管理和調(diào)度JobTracker分配的任務(wù)．

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

基于slot的資源表示模型采用靜態(tài)資源配置策略，即每個(gè)節(jié)點(diǎn)事先配置好可用的slot數(shù)目，一旦啟動(dòng)后就無(wú)法動(dòng)態(tài)修改．考慮到實(shí)際應(yīng)用場(chǎng)景中，不同作業(yè)對(duì)資源的需求往往具有較大差異，靜態(tài)配置slot數(shù)量往往會(huì)導(dǎo)致節(jié)點(diǎn)上某些資源利用率過(guò)高或者過(guò)低．譬如，內(nèi)存密集型作業(yè)往往會(huì)有很多Reduce Task，運(yùn)行時(shí)會(huì)占用大量Reduce slot，節(jié)點(diǎn)上的內(nèi)存被占用而無(wú)法啟動(dòng)Map Task，進(jìn)而導(dǎo)致內(nèi)存利用率較高，而CPU利用率則較低．為了解決該問(wèn)題，文獻(xiàn)［9］提出了一種動(dòng)態(tài)調(diào)整節(jié)點(diǎn)上slot數(shù)量的方案．該方案假設(shè)在每個(gè)節(jié)點(diǎn)上有一個(gè)動(dòng)態(tài)slot池，slot數(shù)量動(dòng)態(tài)調(diào)整模塊（SlotsAdjuster）則可以根據(jù)節(jié)點(diǎn)上的資源利用率動(dòng)態(tài)調(diào)整slot數(shù)量，以便更合理地利用資源．這種基于動(dòng)態(tài)的slot資源管理方案已經(jīng)在阿里的“云梯”集群上投入了使用．

對(duì)于一個(gè)MapReduce應(yīng)用程序而言，Map Task優(yōu)先得到調(diào)度，而只有當(dāng)Map Task完成數(shù)目達(dá)到一定比例（通常為5%）后，Reduce Task才開(kāi)始獲得調(diào)度機(jī)會(huì)．因此，從單個(gè)應(yīng)用程序看，在開(kāi)始運(yùn)行時(shí)，Map slot資源緊張而Reduce slot空閑，而當(dāng)Map Task全部運(yùn)行完成后，Reduce slot緊張而Map slot空閑．很明顯，這種區(qū)分slot類別的資源管理方案在一定程度上減低了slot的利用率．文獻(xiàn)［10］提出了一種基于無(wú)類別slot資源管理方案，即不再區(qū)分Map slot和Reduce slot，而是只有一種slot，并讓所有的任務(wù)共享所有slot，至于如何將這些slot分給不同任務(wù)，則完全由調(diào)度器來(lái)決定．

2．2 基于真實(shí)資源需求量的資源表示模型

采用上述基于無(wú)類別slot資源管理方案，集群中只有一種資源slot．因此，這就意味著各個(gè)節(jié)點(diǎn)上的slot是同質(zhì)的，即一個(gè)slot實(shí)際上代表了相同的資源．然而，在實(shí)際應(yīng)用環(huán)境中，用戶應(yīng)用程序?qū)Y源需求往往是多樣化的、異構(gòu)的．這種基于無(wú)類別slot的資源劃分形式的劃分粒度仍過(guò)于粗糙，很容易會(huì)造成節(jié)點(diǎn)的資源利用率過(guò)高或過(guò)低［11］．如，管理員事先劃分好一個(gè)slot代表2GB內(nèi)存和1個(gè)CPU，如果一個(gè)應(yīng)用程序的任務(wù)只需要1GB內(nèi)存，則會(huì)產(chǎn)生“資源碎片”，從而降低集群資源的利用率；同樣，如果一個(gè)應(yīng)用程序需要3GB內(nèi)存，則會(huì)隱式地?fù)屨计渌蝿?wù)的資源，從而產(chǎn)生資源搶占現(xiàn)象，可能導(dǎo)致集群利用率過(guò)高．因此，尋求一種更精細(xì)的資源劃分方法顯得極為重要．

回歸資源分配的本質(zhì)，即根據(jù)任務(wù)的資源需求為其分配集群中的各類資源．在實(shí)際系統(tǒng)中，資源本身就是多維度的，包括CPU、內(nèi)存、磁盤(pán)和網(wǎng)絡(luò)等，如果想要精確控制資源分配，基于slot的劃分概念不再適用，最直接有效的方法是讓任務(wù)直接向調(diào)度器申請(qǐng)自己需要的資源（比如某個(gè)任務(wù)可以申請(qǐng)1．5 GB內(nèi)存和1個(gè)CPU），而調(diào)度器則按照任務(wù)實(shí)際需求為其精細(xì)地分配對(duì)應(yīng)的資源量，不再簡(jiǎn)單地將一個(gè)slot分配給它，如圖3所示，TaskTracker向JobTracker匯報(bào)節(jié)點(diǎn)上的詳細(xì)的資源量（這里暫時(shí)只考慮CPUs，Memory），而Job－Tracker根據(jù)作業(yè)的真實(shí)需求量來(lái)分配任務(wù)．

圖3 基于真實(shí)資源需求量的資源表示模型Fig．3 The resource representation model based on real demands for resource

對(duì)于任何共享集群的系統(tǒng)，資源分配都是一個(gè)至關(guān)重要的模塊．一個(gè)最常用的分配策略是最大最小公平（max－min fairness）原則，最早是用于控制網(wǎng)絡(luò)流量，以實(shí)現(xiàn)公平分配網(wǎng)絡(luò)帶寬［12］．最大最小公平策略的基本含義是使得資源分配的最小分配量盡可能最大，它可以防止任何網(wǎng)絡(luò)流被“餓死”，同時(shí)在一定程度上盡可能增加每個(gè)流的速率．因此，最大最小公平被認(rèn)為是一種很好權(quán)衡有效性和公平性的自由分配策略，在經(jīng)濟(jì)、網(wǎng)絡(luò)領(lǐng)域有著廣泛的應(yīng)用，由其演變出來(lái)的加權(quán)最大最小公平模型廣泛地被一些資源分配策略采用，如基于優(yōu)先級(jí)、預(yù)留機(jī)制和限期的分配策略．最大最小公平模型同時(shí)也保證分配隔離，即用戶確保接收自己的分配量而不考慮其他用戶的需求［11］．

基于這些特點(diǎn)，大量的分配算法被提出來(lái)實(shí)現(xiàn)不同準(zhǔn)確度的最大最小公平模型，譬如輪詢、均衡資源共享［13］和加權(quán)公平隊(duì)列［14］等．這些算法被應(yīng)用于各種各樣的資源分配上，包括網(wǎng)絡(luò)帶寬［15－17］、CPU［14，18］、內(nèi)存［18］以及二級(jí)存儲(chǔ)空間．但這些公平分配的工作主要集中在單一資源類型．同樣，在多類型資源環(huán)境和需求異構(gòu)化下，公平合理的分配策略也很重要．

為了支持多維度資源調(diào)度，越來(lái)越多的分配算法被提出［19－20］．文獻(xiàn)［11］提出了一種主資源公平調(diào)度算法（Dominant Resource Fairness，DRF）．該算法擴(kuò)展了最大最小公平算法，使其能夠在保持分配公平前提下，支持多維度資源的調(diào)度．在DRF算法中，將所需份額（資源比例）最大的資源稱為主資源，而DRF的基本設(shè)計(jì)思想則是將最大最小公平算法應(yīng)用于主資源上，進(jìn)而將多維資源調(diào)度問(wèn)題轉(zhuǎn)化為單維資源調(diào)度問(wèn)題，即DRF總是最大化所有主資源占用量中最小的．由于DRF被證明非常適合應(yīng)用于多資源和復(fù)雜需求的環(huán)境中，因此被越來(lái)越多的系統(tǒng)所采用，其中包括Apache YARN和Apache Mesos．

3 集群資源調(diào)度

資源調(diào)度是根據(jù)一定的資源使用規(guī)則，在不同資源使用者之間進(jìn)行資源調(diào)整的過(guò)程．不同的計(jì)算任務(wù)對(duì)應(yīng)著不同的資源使用者，每個(gè)計(jì)算任務(wù)在集群節(jié)點(diǎn)上對(duì)應(yīng)于一個(gè)或多個(gè)進(jìn)程（或者線程）．資源調(diào)度的目的是將用戶任務(wù)分配到合適的資源上，使得在滿足用戶需求的前提下，任務(wù)完成時(shí)間盡量小，且資源利用率盡量高．

資源調(diào)度最終要實(shí)現(xiàn)時(shí)間跨度、服務(wù)質(zhì)量、負(fù)載均衡、經(jīng)濟(jì)原則最優(yōu)的目標(biāo)．由于不同資源管理系統(tǒng)的架構(gòu)不同，資源的管理和調(diào)度沒(méi)有統(tǒng)一標(biāo)準(zhǔn)，基于各種調(diào)度模型的調(diào)度算法有很多．下面將逐一進(jìn)行闡述．

3．1 資源調(diào)度模型

文獻(xiàn)［21］將任務(wù)調(diào)度模型分為應(yīng)用模型、計(jì)算平臺(tái)模型和性能目標(biāo)模型．應(yīng)用模型涉及如何將應(yīng)用劃分為任務(wù)、如何考慮任務(wù)的屬性特征等，典型的任務(wù)模型有依賴任務(wù)模型DAG、Map－Reduce任務(wù)模型以及流式作業(yè)；計(jì)算平臺(tái)模型是對(duì)系統(tǒng)中的資源抽象，其中最重要的資源是計(jì)算機(jī)的計(jì)算資源和網(wǎng)絡(luò)資源；性能指標(biāo)模型可以分為基于系統(tǒng)的目標(biāo)和基于用戶的目標(biāo)兩類．基于系統(tǒng)的性能模型主要關(guān)注整個(gè)系統(tǒng)的資源利用率、吞吐量、效率和公平性等指標(biāo)，而基于用戶的性能指標(biāo)包括應(yīng)用的最短完成時(shí)間、周轉(zhuǎn)時(shí)間、平均延遲和加權(quán)完成時(shí)間等指標(biāo)．

資源管理調(diào)度模型按照調(diào)度實(shí)體之間的關(guān)系可以分為統(tǒng)一資源調(diào)度模型和多資源調(diào)度協(xié)作調(diào)度模型．按照資源的組織調(diào)度形式可分為集中調(diào)度模型、層次調(diào)度模型和非集中調(diào)度模型．而在近期，文獻(xiàn)［22］公布了Google下一代集群管理系統(tǒng)Omega的設(shè)計(jì)細(xì)節(jié)，主要介紹了Google經(jīng)歷的三代資源調(diào)度器的架構(gòu)，如圖4所示，分別是中央式調(diào)度模型、雙層調(diào)度模型和共享狀態(tài)調(diào)度模型．

圖4 Google提出的三種調(diào)度模型架構(gòu)Fig．4 Schematic overview of the sceduling architextures proposed by Google

中央式調(diào)度模型（Monolithic Scheduler），即所有的資源由一個(gè)中央調(diào)度程序調(diào)度，所有系統(tǒng)可用的相關(guān)信息都被聚集在中心機(jī)上．其典型的代表是MRv1中JobTracker的實(shí)現(xiàn)：集群中所有節(jié)點(diǎn)的信息和其資源量都被統(tǒng)計(jì)后，存放于JobTracker中，資源的管理和作業(yè)的調(diào)度都放到JobTracker進(jìn)程中完成［23］．這種設(shè)計(jì)方式的缺點(diǎn)很明顯．首先，擴(kuò)展性差，集群規(guī)模受限．JobTracker既要負(fù)責(zé)集群管理，還要負(fù)責(zé)作業(yè)調(diào)度，很難趕得上作業(yè)和任務(wù)數(shù)量的增長(zhǎng)．其次，框架支持性差，任務(wù)單一．目前，MRv1只能支持MapReduce作業(yè)，而新興的流式作業(yè)、迭代作業(yè)等的調(diào)度策略并不能嵌入在中央式調(diào)度器中．

文獻(xiàn)［22］還提到了一種對(duì)中央式調(diào)度器的優(yōu)化方案：將每種調(diào)度策略放到單獨(dú)一個(gè)路徑（模塊）中，不同的作業(yè)由不同的調(diào)度策略進(jìn)行調(diào)度．這種方案在作業(yè)量和集群規(guī)模較小時(shí)，能大大縮短作業(yè)響應(yīng)時(shí)間．但由于所有策略仍在一個(gè)集中式的組件中，整個(gè)系統(tǒng)的擴(kuò)展性并沒(méi)有變得更好．

雙層調(diào)度模型（Two－level Scheduler）則結(jié)合上述優(yōu)化方案，采用分而治之策略（或策略下放機(jī)制）解決了中央式調(diào)度器的不足．雙層調(diào)度器仍保留一個(gè)簡(jiǎn)化后的中央式調(diào)度器，但調(diào)度策略則下放到各個(gè)應(yīng)用程序的調(diào)度程序來(lái)完成．當(dāng)前比較有名的開(kāi)源資源統(tǒng)一管理和調(diào)度系統(tǒng)Mesos［24］和YARN［25－26］均是采用雙層調(diào)度模型．雙層調(diào)度模型的特點(diǎn)是，各個(gè)計(jì)算框架調(diào)度器并不知道整個(gè)集群資源使用情況，只是被動(dòng)地接收資源．即簡(jiǎn)化的中央式調(diào)度器僅負(fù)責(zé)管理資源，將可用的資源推送給各個(gè)框架，而框架自己選擇使用還是拒絕這些資源；一旦框架接收到新資源后，再進(jìn)一步調(diào)用自己的調(diào)度器將資源分配給其內(nèi)部的各個(gè)應(yīng)用（各個(gè)MapReduce作業(yè)），進(jìn)而實(shí)現(xiàn)雙層調(diào)度．

但是，雙層調(diào)度模型也存在一些不足：①各個(gè)框架無(wú)法探知整個(gè)集群的實(shí)時(shí)資源使用情況，而對(duì)于一些應(yīng)用，為之提供實(shí)時(shí)資源使用情況可以為之提供潛在的優(yōu)化空間；②采用悲觀鎖，并發(fā)粒度?。p層資源調(diào)度模型采用悲觀鎖，即在中央調(diào)度器中對(duì)資源進(jìn)行加鎖控制．當(dāng)資源調(diào)度器將可用資源推送給任意框架時(shí)，就會(huì)對(duì)這部分資源加全局鎖，其他框架無(wú)法使用這部分資源（即使這部分資源并未被使用）．等到該框架返回資源使用情況后，中央調(diào)度器釋放資源的全局鎖，此時(shí)才能夠?qū)①Y源推送給其他框架使用，這大大限制了系統(tǒng)并發(fā)性．實(shí)際上在數(shù)據(jù)庫(kù)領(lǐng)域，悲觀鎖與樂(lè)觀鎖爭(zhēng)論一直不休，悲觀鎖通常采用鎖機(jī)制控制并發(fā)，這會(huì)大大降低性能，而樂(lè)觀鎖則采用多版本并發(fā)控制（Multi－Version Concurrency Control，MVCC），典型代表有MySQL InnoDB，這種并發(fā)控制機(jī)制則可以大大提升性能．

為了克服雙層調(diào)度模型的以上兩個(gè)不足之處，Google提出一種基于共享狀態(tài)的調(diào)度模型（Shared State Scheduler），并依據(jù)該模型研發(fā)下一代資源管理系統(tǒng)Omega［22］．共享狀態(tài)調(diào)度是將雙層調(diào)度中的中央式資源調(diào)度模塊簡(jiǎn)化成一種持久化的共享數(shù)據(jù)，這里的“共享數(shù)據(jù)”實(shí)際上就是整個(gè)集群的實(shí)時(shí)資源使用信息．一旦引入共享數(shù)據(jù)后，共享數(shù)據(jù)的并發(fā)訪問(wèn)方式就成為該調(diào)度模型的核心，而Omega則采用了傳統(tǒng)數(shù)據(jù)庫(kù)中基于多版本的并發(fā)訪問(wèn)控制方式（也稱“樂(lè)觀鎖”，MVCC，Multi－Version Concurrency Control），進(jìn)而大大提升了系統(tǒng)并發(fā)性．

3．2 資源調(diào)度策略

在分布式計(jì)算領(lǐng)域中，資源分配問(wèn)題實(shí)際上是一個(gè)任務(wù)調(diào)度問(wèn)題．它的主要任務(wù)是根據(jù)當(dāng)前集群中各個(gè)節(jié)點(diǎn)上的資源（包括CPU、內(nèi)存和網(wǎng)絡(luò)等資源）的剩余情況與各個(gè)用戶作業(yè)的服務(wù)質(zhì)量（Quality of Service，QoS）要求，在資源和作業(yè)／任務(wù)之間做出最優(yōu)的匹配．由于用戶對(duì)作業(yè)服務(wù)質(zhì)量的要求是多樣化的，因此，分布式系統(tǒng)中的任務(wù)調(diào)度是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，更進(jìn)一步說(shuō)，它是一個(gè)典型的NP－h(huán)ard問(wèn)題．

通常，分布式系統(tǒng)都會(huì)提供一個(gè)非常簡(jiǎn)單的調(diào)度機(jī)制：FIFO（First In First Out），即先來(lái)先服務(wù)．在該調(diào)度機(jī)制下，所有的用戶作業(yè)都被提交到一個(gè)隊(duì)列中，然后由調(diào)度器按照作業(yè)提交時(shí)間的先后順序來(lái)選擇將被執(zhí)行的作業(yè)．

但隨著分布式計(jì)算框架的普及，集群的用戶量越來(lái)越大，不同用戶提交的應(yīng)用程序往往具有不同的服務(wù)質(zhì)量要求，典型的應(yīng)用有以下三種．

（1）批處理作業(yè)．這種作業(yè)往往耗時(shí)較長(zhǎng)，對(duì)完成時(shí)間一般沒(méi)有嚴(yán)格要求，如數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等方面的應(yīng)用程序．

（2）交互式作業(yè)．這種作業(yè)期望能及時(shí)返回結(jié)果，如SQL查詢（Hive）．

（3）生產(chǎn)性作業(yè)．這種作業(yè)要求有一定量的資源保證，如統(tǒng)計(jì)值計(jì)算、垃圾數(shù)據(jù)分析等．

此外，不同應(yīng)用程序?qū)τ布Y源的需求量也是不同的，如過(guò)濾／統(tǒng)計(jì)類作業(yè)一般為CPU密集型作業(yè)，而數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)的作業(yè)一般為I／O密集型作業(yè)．傳統(tǒng)的FIFO調(diào)度算法雖然簡(jiǎn)單明了，但是它忽略了不同作業(yè)對(duì)資源的需求差異，嚴(yán)重時(shí)會(huì)影響作業(yè)的執(zhí)行．因此，傳統(tǒng)的FIFO調(diào)度策略不僅不能滿足多樣化需求，也不能充分利用硬件資源．

為了克服單隊(duì)列FIFO調(diào)度器的不足，多種類型的多用戶多隊(duì)列調(diào)度器相繼出現(xiàn)．這些調(diào)度策略允許管理員按照應(yīng)用需求對(duì)用戶或者應(yīng)用程序分組，并為不同的分組分配不同的資源量，同時(shí)通過(guò)添加各種約束防止單個(gè)用戶或應(yīng)用程序獨(dú)占資源，進(jìn)而滿足多樣化的QoS需求．當(dāng)前主要有兩種多用戶作業(yè)調(diào)度器的設(shè)計(jì)思路：第一種是在一個(gè)物理集群上虛擬多個(gè)子集群，典型的代表是HOD（Hadoop On Demand）調(diào)度器；另一種是擴(kuò)展傳統(tǒng)調(diào)度策略，使之支持多隊(duì)列多用戶，這樣，不同的隊(duì)列擁有不同的資源量，可以運(yùn)行不同的應(yīng)用程序，典型的代表是Yahoo！的Capacity Scheduler和Facebook的Fair Scheduler．

3．2．1 HOD（Hadoop On Demand）

HOD調(diào)度器［27］是一個(gè)在共享物理集群上管理若干個(gè)Hadoop集群的工具．用戶可以通過(guò)HOD調(diào)度器在一個(gè)共享物理集群上搭建若干個(gè)獨(dú)立的虛擬Hadoop集群，以滿足不同的用途．比如，不同集群運(yùn)行不同類型的應(yīng)用程序．同時(shí)HOD調(diào)度器可使管理員和用戶輕松地快速搭建和使用Hadoop．

HOD調(diào)度器的工作過(guò)程實(shí)現(xiàn)中依賴一個(gè)資源管理器來(lái)為之分配回收節(jié)點(diǎn)和管理各個(gè)節(jié)點(diǎn)上的作業(yè)運(yùn)行情況，如監(jiān)控作業(yè)運(yùn)行、維護(hù)作業(yè)的運(yùn)行狀態(tài)等．而HOD只需在資源管理分配的節(jié)點(diǎn)上運(yùn)行Hadoop守護(hù)進(jìn)程和MapReduce作業(yè)即可．當(dāng)前，HOD采用的資源管理器是開(kāi)源的Torque資源管理器［28］．Torque資源管理器中也運(yùn)行一個(gè)調(diào)度守護(hù)進(jìn)程，默認(rèn)情況下，調(diào)度守護(hù)進(jìn)程采用FIFO調(diào)度機(jī)制，將所有作業(yè)存放到一個(gè)隊(duì)列中，并按照到達(dá)先后順序依次調(diào)度．需要注意的是，Torque中的調(diào)度機(jī)制是可插拔的，Torque還提供許多其他多種可選的調(diào)度機(jī)制．

3．2．2 Capacity Scheduler

Capacity Scheduler是由Yahoo！開(kāi)發(fā)的多用戶調(diào)度器，主要用來(lái)彌補(bǔ)已有HOD的不足之處．Capacity Scheduler以隊(duì)列為單位劃分資源，每個(gè)隊(duì)列可以設(shè)定一定比例的資源最低保證和使用上限．同時(shí)，每個(gè)用戶也可設(shè)定一定的資源使用上限以防止資源獨(dú)占，而當(dāng)一個(gè)隊(duì)列的資源空閑時(shí)，可暫時(shí)將空閑資源共享給其他隊(duì)列．

Capacity Scheduler通常采用三級(jí)調(diào)度策略，當(dāng)集群中出現(xiàn)空閑資源時(shí)，調(diào)度器依次選擇一個(gè)隊(duì)列，選擇該隊(duì)列中的一個(gè)作業(yè)和該作業(yè)中的一個(gè)任務(wù)．隊(duì)列的選擇總是優(yōu)先將資源分配給資源使用率最低的隊(duì)列，即resourceoccupied／capacity最小的隊(duì)列，其中resourceoccupied表示隊(duì)列當(dāng)前已經(jīng)使用的資源數(shù)量，capacity為隊(duì)列的資源容量；在隊(duì)列內(nèi)部，待調(diào)度的作業(yè)按照某種排序策略進(jìn)行排序，如支持優(yōu)先級(jí)或者FIFO等．當(dāng)選擇任務(wù)時(shí)，調(diào)度器會(huì)依次遍歷排序的作業(yè)，并檢查當(dāng)前的資源量是否足以運(yùn)行當(dāng)前作業(yè)的一個(gè)任務(wù)．

Capacity Scheduler提供了對(duì)大內(nèi)存任務(wù)的調(diào)度機(jī)制．默認(rèn)情況下，假設(shè)所有任務(wù)是同質(zhì)的，資源分配粒度也是固定的，而這并沒(méi)有考慮那些內(nèi)存密集型的任務(wù)．為了解決該問(wèn)題，Capacity Scheduler可根據(jù)任務(wù)的內(nèi)存需求量為其多分配一些資源，如果資源不夠時(shí)，則通過(guò)資源預(yù)留機(jī)制為該作業(yè)預(yù)留資源，直到滿足作業(yè)需求為止．同時(shí)為了提高任務(wù)的數(shù)據(jù)本地性，Capacity Scheduler采用了作業(yè)延遲調(diào)度策略：當(dāng)選中一個(gè)作業(yè)后，如果在該作業(yè)中未找到滿足數(shù)據(jù)本地性的任務(wù)，則調(diào)度器會(huì)讓該作業(yè)跳過(guò)一定次數(shù)的調(diào)度機(jī)會(huì)，直到找到滿足本地性的任務(wù)或者達(dá)到跳過(guò)次數(shù)上限為之．

3．2．3 Fair Scheduler

為了解決HOD調(diào)度算法產(chǎn)生的問(wèn)題，F(xiàn)acebook也提出了公平調(diào)度算法（Fair Scheduling）［30］．圖5所示是一個(gè)典型的公平調(diào)度模型．公平調(diào)度器與Capacity Scheduler類似，按資源池（類似于隊(duì)列的概念）來(lái)組織作業(yè)，并把資源公平地分到這些資源池內(nèi)．公平調(diào)度算法盡可能保證每個(gè)用戶都獲得相等的資源份額．當(dāng)有新用戶提交作業(yè)后，系統(tǒng)會(huì)將資源賦給這些新用戶，從而使得每一個(gè)用戶都能夠獲取等量的資源．除了提供公平共享方法之外，公平調(diào)度器允許賦給資源池最低共享資源保證，這能夠確保特定用戶、群組或者應(yīng)用程序總能獲得到足夠的資源．當(dāng)一個(gè)資源池包含作業(yè)時(shí)，該資源池至少能獲得最低保證共享資源，但是當(dāng)資源池不完全需要所擁有的保證共享資源時(shí)，額外的部分會(huì)在其他資源池間進(jìn)行切分．

圖5 公平調(diào)度模型Fig．5 Fair scheduling model

同Capacity Scheduler一樣，公平調(diào)度器也采用三級(jí)調(diào)度策略：資源池選擇、作業(yè)選擇和任務(wù)選擇，即依次選擇一個(gè)合適的資源池，然后選擇該資源池中的一個(gè)作業(yè)和該作業(yè)中的一個(gè)任務(wù)，但具體采用的策略稍有不同．資源池的選擇在不同的條件下采用不同策略：當(dāng)存在資源使用量小于最低保證資源量的資源池時(shí)，優(yōu)先選擇資源使用率最低的資源池，否則，選擇作業(yè)權(quán)重比最小的資源池，作業(yè)權(quán)重比（jobWeight＝poolWeight／poolRunningJob－Num）最小意味著資源池分配的資源比例最低，選擇作業(yè)權(quán)重比最小的資源池能最大化資源公平共享．選定一個(gè)資源池后，F(xiàn)air Scheduler總是優(yōu)先將資源分配給資源池中任務(wù)權(quán)重比最小的作業(yè)．而任務(wù)選擇策略都考慮數(shù)據(jù)本地性，進(jìn)而提高作業(yè)運(yùn)行效率［30］．

Fair Scheduler也是一個(gè)多用戶調(diào)度器，同樣添加了多層級(jí)別的資源限制條件以更好地讓多用戶共享一個(gè)集群，比如資源池資源限制、用戶作業(yè)數(shù)目限制等．然而，F(xiàn)air Scheduler又增加了很多新的優(yōu)化機(jī)制．譬如，為了提高數(shù)據(jù)本地性，F(xiàn)air Scheduler采用了延時(shí)調(diào)度機(jī)制［31］，即當(dāng)出現(xiàn)空閑資源時(shí)，如果選中的作業(yè)沒(méi)有滿足節(jié)點(diǎn)局本地化或機(jī)架局本地化的任務(wù)，則暫時(shí)把資源讓給其他作業(yè)，直到找到一個(gè)滿足數(shù)據(jù)本地性的任務(wù)或者達(dá)到一個(gè)時(shí)間閾值之后，此時(shí)不得不為之選擇一個(gè)非本地性的任務(wù)．為了更好地實(shí)現(xiàn)延時(shí)調(diào)度，提高作業(yè)運(yùn)行效率，F(xiàn)air Scheduler采用雙層延遲調(diào)度算法：為了找到一個(gè)節(jié)點(diǎn)本地化的任務(wù)最長(zhǎng)可等待時(shí)間W1或者進(jìn)一步等待時(shí)間W2找到一個(gè)機(jī)架本地化任務(wù)．

Fair Scheduler允許不同資源池間的資源搶占．當(dāng)一個(gè)資源池有剩余資源時(shí)，F(xiàn)air Scheduler會(huì)將這些資源暫時(shí)共享給其他資源池；而一旦該資源池有新的作業(yè)提交，調(diào)度器則為其回收資源．如果一段時(shí)間后該資源池仍得不到本屬于自己的資源，則調(diào)度器會(huì)通過(guò)殺死任務(wù)的方式搶占資源．Fair Scheduler同時(shí)采用了兩種資源搶占方式：最小資源量搶占和公平共享量搶占．最小資源量搶占是指一個(gè)資源池的最小資源量在一定時(shí)間內(nèi)得不到滿足，則會(huì)從其他超額使用資源的資源池中搶占資源；而公平共享量搶占是指如果一定時(shí)間內(nèi)一個(gè)資源池的公平共享量的一半得不到滿足，則該資源池也會(huì)從其他資源池中搶占．進(jìn)行資源搶占時(shí)，調(diào)度器會(huì)選擇超額使用資源的資源池，從中找到并殺掉啟動(dòng)時(shí)間最早的任務(wù)來(lái)釋放資源，從而最小化工作的浪費(fèi)．

同時(shí)，F(xiàn)air Scheduler為用戶提供了一個(gè)可擴(kuò)展的負(fù)載均衡器，即可以將系統(tǒng)中的所有任務(wù)按照數(shù)量平均分配到各個(gè)節(jié)點(diǎn)上．表1從多個(gè)方面列舉了Fair Scheduler與Capacity Scheduler兩種調(diào)度器的異同．

表1 Fair Scheduler與Capacity Scheduler比較Tab．1 Fair Scheduler VS．Capacity Scheduler

目前，針對(duì)多用戶共享集群的資源調(diào)度，圍繞著Capacity Scheduling和Fair Scheduling衍生出很多改進(jìn)算法［32－37］．還有一些關(guān)于任務(wù)調(diào)度的改進(jìn)算法［31，38－39］，均采用就近原則，盡量把任務(wù)調(diào)度到所需數(shù)據(jù)所在的節(jié)點(diǎn)上執(zhí)行．不同的調(diào)度算法，對(duì)應(yīng)不同的期望值，譬如運(yùn)行時(shí)間、資源利用率和吞吐量等．文獻(xiàn)［40］中提出的一種自適應(yīng)調(diào)度器（Adaptive Scheduler），是以用戶期望運(yùn)行時(shí)間為目標(biāo)的調(diào)度器．該調(diào)度器根據(jù)每個(gè)作業(yè)會(huì)被分解成多個(gè)任務(wù)的事實(shí)，通過(guò)已經(jīng)運(yùn)行完成的任務(wù)的運(yùn)行時(shí)間估算剩余任務(wù)的運(yùn)行時(shí)間，進(jìn)而使得該調(diào)度器能根據(jù)作業(yè)的進(jìn)度和剩余時(shí)間動(dòng)態(tài)地為作業(yè)分配資源，以期望作業(yè)在規(guī)定時(shí)間內(nèi)完成．文獻(xiàn)［41］的自學(xué)習(xí)調(diào)度器（Learning scheduler）是一種基于貝葉斯分類算法的資源感知調(diào)度器．與現(xiàn)有的調(diào)度器不同，該調(diào)度器將貝葉斯分類算法應(yīng)用到資源分配中，根據(jù)節(jié)點(diǎn)上的資源使用情況和用戶提交作業(yè)的資源利用率，利用模式分類器對(duì)節(jié)點(diǎn)和作業(yè)進(jìn)行分類（“Bad”和“Good”兩類）．調(diào)度器可以合理地任務(wù)調(diào)度到合適的節(jié)點(diǎn)上運(yùn)行，從而加快作業(yè)完成時(shí)間．另外，還存在一種新的調(diào)度策略—?jiǎng)討B(tài)優(yōu)先級(jí)調(diào)度（Dynamic Priority Scheduler）［42］．該調(diào)度策略允許用戶動(dòng)態(tài)調(diào)整自己獲取的資源量以滿足其對(duì)服務(wù)質(zhì)量的要求．

4 結(jié) 論

本文總結(jié)了共享集群技術(shù)的發(fā)展趨勢(shì)，并介紹了共享集群的資源管理和調(diào)度技術(shù)．集群資源管理通常由兩部分組成：資源表示模型和資源分配模型．在多類型資源的集群環(huán)境下，資源管理方案可以根據(jù)資源管理維度來(lái)劃分為：基于slot的資源模型和基于真實(shí)資源需求的資源模型．基于slot的資源管理方案將多維度的資源抽象成一維slot，這樣可以方便系統(tǒng)的分配與調(diào)度的實(shí)現(xiàn)．而基于真實(shí)資源需求的資源管理方案則能夠提升集群資源的利用率，進(jìn)而提升吞吐量．之后本文詳細(xì)闡述了資源調(diào)度模型的發(fā)展過(guò)程，主要經(jīng)歷集中式調(diào)度模型、兩層調(diào)度模型和共享狀態(tài)的調(diào)度模型，并且每種調(diào)度模型都有與之對(duì)應(yīng)的開(kāi)源的資源管理系統(tǒng)．此外，本文分析和總結(jié)了現(xiàn)有的資源調(diào)度技術(shù)以及對(duì)應(yīng)的改進(jìn)版本，并對(duì)較為常用的調(diào)度策略進(jìn)行了對(duì)比．

隨著越來(lái)越多的資源管理系統(tǒng)開(kāi)源化，資源管理和調(diào)度技術(shù)已經(jīng)成為研究熱點(diǎn)．接下來(lái)的研究工作主要集中在兩個(gè)方向：支持更多類型的資源，和支持更多不同的計(jì)算框架．目前，資源管理技術(shù)還只限于CPU和內(nèi)存兩類資源，將來(lái)可以考慮網(wǎng)絡(luò)I／O和磁盤(pán)I／O等．支持更多的計(jì)算框架則能充分利用集群資源．已開(kāi)源的資源管理系統(tǒng)，如Apache YARN和Apache Mesos，都可以支持多種計(jì)算框架，但存在某些資源管理系統(tǒng)可能對(duì)某些框架不適合的問(wèn)題．譬如，Spark，一種非常流行的內(nèi)存計(jì)算（或者迭代式計(jì)算）框架并不能很好地介入YARN，原因在于YARN中的資源預(yù)留機(jī)制．所以，設(shè)計(jì)一個(gè)能同時(shí)支持多種計(jì)算框架的資源管理系統(tǒng)將面臨巨大挑戰(zhàn)，但也是工業(yè)界的一個(gè)迫切需求．

［1］Apache YARN［EB／OL］．http：／／hadoop．a(chǎn)pache．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．a(chǎn)pache．org．

［4］Amazon EC2［EB／OL］．http：／／aws．a(chǎn)mazon．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．a(chǎn)pache．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］梁 李 ?。⒗颒adoop集 群 架 構(gòu) 及 服 務(wù) 體 系［C／OL］／／Hadoop與 大 數(shù) 據(jù) 技 術(shù) 大 會(huì)（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］錢(qián)瓊芬，李春林，張小慶，等．云數(shù)據(jù)中心虛擬資源管理研究綜述［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．a(chǎn)pache．org／docs／stable／hod＿scheduler．html．

［28］TORQUE Resource Manager．http：／／www．a(chǎn)daptivecomputing．com／products／open－source／torque／．

［29］Capacity Scheduler．http：／／hadoop．a(chǎn)pache．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］王明陽(yáng)，洪爵，馮圣中．面向多用戶的集群資源部署策略［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．a(chǎn)pache．org／jira／browse／MAPREDUCE－1380．

［41］Learning Scheduler．http：／／issues．a(chǎn)pache．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．