大數(shù)據(jù)背景下集群調(diào)度結(jié)構(gòu)與研究進(jìn)展

郝春亮 沈 捷 張 珩 武延軍 王 青 李明樹

1(中國(guó)科學(xué)院軟件研究所基礎(chǔ)軟件中心 北京 100190)

2(中國(guó)科學(xué)院大學(xué) 北京 100049)

3(帝國(guó)理工大學(xué)計(jì)算學(xué)院 倫敦 SW72AZ)

(chunliang@nfs.iscas.ac.cn)

20世紀(jì)70年代之前，計(jì)算任務(wù)所依賴的物理設(shè)備多為昂貴且專用的計(jì)算設(shè)備，罕有將多臺(tái)設(shè)備互聯(lián)的實(shí)際案例[1].至20世紀(jì)80年代初期，隨著微電腦的出現(xiàn)，單臺(tái)計(jì)算設(shè)備的體積和成本急劇下降，多臺(tái)電腦協(xié)同工作于同一區(qū)域之中的情況時(shí)有發(fā)生.因此，出現(xiàn)了比單臺(tái)電腦更為復(fù)雜的、利用局域網(wǎng)絡(luò)互聯(lián)多臺(tái)電腦資源的研究工作[2-4].這些早期對(duì)于多臺(tái)計(jì)算設(shè)備協(xié)作的研究開啟了對(duì)集群以及相關(guān)技術(shù)的探索，其中包括解決資源使用與任務(wù)分配的集群調(diào)度問題研究.

自20世紀(jì)80年代至今，集群自身以及其相關(guān)調(diào)度研究都經(jīng)歷了持續(xù)的發(fā)展.例如服務(wù)于高性能計(jì)算的集群調(diào)度研究以及與集群調(diào)度緊密關(guān)聯(lián)的網(wǎng)格調(diào)度研究都取得了長(zhǎng)足的進(jìn)展，并且誕生了大量的研究工作[5-6].這些調(diào)度研究工作是目前集群調(diào)度研究的基礎(chǔ).

在大數(shù)據(jù)背景下，集群調(diào)度面臨全新挑戰(zhàn).集群經(jīng)歷了規(guī)模由小到大、計(jì)算模型和計(jì)算需求由單一到復(fù)雜、計(jì)算設(shè)備由同構(gòu)到異構(gòu)等快速變化[7].正因?yàn)檫@些變化，集群調(diào)度研究的目標(biāo)和最終實(shí)現(xiàn)方式都出現(xiàn)了顯著差異，以至于目前出現(xiàn)了集中調(diào)度結(jié)構(gòu)、雙層調(diào)度結(jié)構(gòu)、分布式調(diào)度結(jié)構(gòu)、混合調(diào)度結(jié)構(gòu)多種調(diào)度結(jié)構(gòu)的分支，由此衍生了不同的研究方向.本文通過(guò)對(duì)目前大數(shù)據(jù)背景下不同集群調(diào)度結(jié)構(gòu)研究現(xiàn)狀與進(jìn)展的介紹與綜合分析，對(duì)各結(jié)構(gòu)中代表性工作涉及的主要研究?jī)?nèi)容以及技術(shù)方法進(jìn)行梳理;繼而對(duì)其各自的適用場(chǎng)景、優(yōu)劣、典型研究工作方向進(jìn)行歸納、總結(jié).在此基礎(chǔ)上，對(duì)未來(lái)集群調(diào)度的發(fā)展方向提出粗淺的看法.

1 集群調(diào)度結(jié)構(gòu)的資料來(lái)源與范圍

為了全面準(zhǔn)確地收集大數(shù)據(jù)背景下集群調(diào)度的典型調(diào)度方法、熱點(diǎn)研究方向以及代表性的研究工作，本文對(duì)下列數(shù)據(jù)來(lái)源進(jìn)行了詳細(xì)篩選:

1) 在IEEE，ACM，Springer，CNKI等搜索引擎中進(jìn)行文獻(xiàn)檢索.檢索使用的關(guān)鍵字包括“scheduling”，“cluster computing”，“decentralized”，“l(fā)ocality”，“fairness”，“task parallism”等.

2) 通過(guò)人工篩選的方式.剔除與研究問題無(wú)關(guān)的論文，保留問題相關(guān)、有代表性的高水平學(xué)術(shù)會(huì)議以及期刊論文(保留CCF推薦列表[8]A類、B類、Core列表[9]A*以及同水平的中文論文).

3) 參考所選論文中的引文，識(shí)別遺漏.通過(guò)以上篩選，獲得直接相關(guān)調(diào)度研究論文44篇(連同其他相關(guān)論文，如集群負(fù)載分析、計(jì)算模型研究等共78篇，連同其他引用合計(jì)96條).按照年份對(duì)直接相關(guān)論文進(jìn)行統(tǒng)計(jì)分析，獲得了年份與論文篇數(shù)的關(guān)系分布圖和年份與4種調(diào)度結(jié)構(gòu)發(fā)展的趨勢(shì)圖,如圖1所示:

Fig. 1 Numbers of selected publications arranged by year圖1 本文所選大數(shù)據(jù)背景下的集群調(diào)度論文按年份分布

從圖1可以發(fā)現(xiàn)，所選論文代表的總體趨勢(shì)是：集中調(diào)度結(jié)構(gòu)是最傳統(tǒng)的調(diào)度結(jié)構(gòu)，從2007年至今每年都有高水平的文章發(fā)表;雙層結(jié)構(gòu)以及分布式結(jié)構(gòu)是為了應(yīng)對(duì)集群以及計(jì)算環(huán)境變化產(chǎn)生的分支，最近幾年各有部分研究成果發(fā)表;混合結(jié)構(gòu)則是目前集群調(diào)度研究的新方向，是對(duì)調(diào)度結(jié)構(gòu)研究的前沿探索.

集群是通過(guò)冗余局域網(wǎng)絡(luò)互聯(lián)的計(jì)算資源，因此集群調(diào)度的研究重點(diǎn)是單一冗余局域網(wǎng)絡(luò)內(nèi)的資源使用和作業(yè)執(zhí)行；有別于基于廣域網(wǎng)絡(luò)的網(wǎng)格調(diào)度研究和云調(diào)度研究，可參考Mishra等人[10]和Qureshi等人[11]進(jìn)行的網(wǎng)格調(diào)度的綜述以及Bala等人[12]和陳康等人[13]對(duì)云調(diào)度的綜述.其中，部分云調(diào)度和集群調(diào)度的研究文獻(xiàn)多有交叉，難以精確分割，故本文的選文中也包括少量以云調(diào)度為主要方向的論文.

此外，本文關(guān)注大數(shù)據(jù)背景下的集群調(diào)度而非大數(shù)據(jù)技術(shù)本身.目前大數(shù)據(jù)計(jì)算有眾多計(jì)算模型，包括：面向批處理的MapReduce[14]，RDD[15]；面向數(shù)據(jù)庫(kù)的Tenzing[16]，SparkSQL[17]，Hive[18]；面向圖處理的Pregel[19]，Unicorn[20]等.他們各自有相關(guān)的研究文獻(xiàn)和實(shí)現(xiàn)原型，有些也包含了模型內(nèi)的任務(wù)調(diào)度設(shè)計(jì).目前集群調(diào)度關(guān)注的更多是對(duì)各模型的統(tǒng)一抽象以及整體決策，故本文有別于對(duì)大數(shù)據(jù)計(jì)算技術(shù)的綜述性文章[7].

目前與本文研究目標(biāo)類似的綜述文章例如Hussain等人[21]對(duì)集群、網(wǎng)格以及云計(jì)算中的作業(yè)執(zhí)行、運(yùn)維管理等多方面的調(diào)度研究進(jìn)行綜述;Schwarzkopf等人[22]包含了對(duì)2013年前集群調(diào)度結(jié)構(gòu)的綜述.上述論文都沒有深入討論在大數(shù)據(jù)背景下引發(fā)的集群調(diào)度結(jié)構(gòu)變化以及各結(jié)構(gòu)的具體設(shè)計(jì)內(nèi)容、特點(diǎn)和局限.與集群調(diào)度有關(guān)的集群能耗研究問題，由于主要解決的是成本和可靠性問題[23]，與集群調(diào)度結(jié)構(gòu)的關(guān)聯(lián)度較低，本文亦不做討論.

2 大數(shù)據(jù)背景下集群調(diào)度的背景、問題與結(jié)構(gòu)

2.1 大數(shù)據(jù)背景下的集群調(diào)度

近年來(lái)，互聯(lián)網(wǎng)中的數(shù)據(jù)量在持續(xù)迅速地增長(zhǎng).據(jù)統(tǒng)計(jì)，2013年度全球范圍內(nèi)新增和被復(fù)制的數(shù)據(jù)總量約為4.4 ZB，2020年預(yù)期將增長(zhǎng)至44 ZB[24].數(shù)據(jù)的大量累積和增長(zhǎng)歸功于各個(gè)企業(yè)和個(gè)人的數(shù)據(jù)相關(guān)實(shí)踐.以Facebook為例，每日用戶上傳圖片總數(shù)最多時(shí)可達(dá)3億張，每日內(nèi)容傳遞最多時(shí)可達(dá)25億條，每日可新增多達(dá)500 TB的數(shù)據(jù)總量[25].與之類似，Google的月搜索量多時(shí)可達(dá)1 000億次[26].針對(duì)持續(xù)積累的大數(shù)據(jù)，集群計(jì)算利用冗余局域網(wǎng)絡(luò)內(nèi)的大規(guī)模計(jì)算設(shè)備進(jìn)行感知、獲取、管理、處理和服務(wù).

在這種背景下，集群調(diào)度包括了對(duì)集群內(nèi)計(jì)算資源進(jìn)行統(tǒng)一抽象、同步計(jì)算資源使用情況、管理工作負(fù)載中的計(jì)算作業(yè)、分配各計(jì)算作業(yè)的計(jì)算任務(wù)、跟蹤任務(wù)執(zhí)行情況等工作.隨著數(shù)據(jù)量持續(xù)快速增長(zhǎng)，集群調(diào)度研究主要面臨2方面的挑戰(zhàn):

1) 因集群自身向著更大、更復(fù)雜的方向發(fā)展帶來(lái)的調(diào)度挑戰(zhàn).主流大數(shù)據(jù)集群在十?dāng)?shù)年間從幾十臺(tái)服務(wù)器發(fā)展到數(shù)千臺(tái)，業(yè)內(nèi)少數(shù)集群內(nèi)已經(jīng)容納了數(shù)萬(wàn)服務(wù)器[27].對(duì)這些節(jié)點(diǎn)上的資源進(jìn)行統(tǒng)一抽象、管理和同步的系統(tǒng)開銷逐漸增大.同時(shí)，集群計(jì)算設(shè)備的差異化也導(dǎo)致集群資源難以得到有效利用.

2) 數(shù)據(jù)處理方式和需求日益多樣、復(fù)雜，為工作負(fù)載的妥善管理和計(jì)算作業(yè)的合理分配帶來(lái)挑戰(zhàn).一方面集群任務(wù)吞吐量的上升擴(kuò)大了調(diào)度時(shí)需要面對(duì)的問題空間，同時(shí)增長(zhǎng)了需要進(jìn)行的決策計(jì)算和通信頻率，使整體負(fù)載管理變得困難;另一方面同一集群內(nèi)并存的大數(shù)據(jù)計(jì)算作業(yè)種類增多，不同作業(yè)之間的需求沖突以及執(zhí)行沖突為集群調(diào)度帶來(lái)多方面的難題.

2.2 大數(shù)據(jù)背景下集群調(diào)度的主要研究問題

為了應(yīng)對(duì)上述2個(gè)挑戰(zhàn)，研究者從不同的角度、不同的研究問題入手，改進(jìn)調(diào)度方法，由此也導(dǎo)致了集群調(diào)度結(jié)構(gòu)的變化.我們從現(xiàn)有文獻(xiàn)中分析得出，與集群調(diào)度結(jié)構(gòu)變化有關(guān)的主要研究問題如下.

與第1個(gè)挑戰(zhàn)，即集群硬件環(huán)境持續(xù)變化相關(guān)的主要研究問題包括4個(gè)：

1) 可擴(kuò)展性問題.為了應(yīng)對(duì)快速增長(zhǎng)的集群規(guī)模和數(shù)據(jù)規(guī)模，避免調(diào)度器本身成為瓶頸，并行可擴(kuò)展性(即去除調(diào)度邏輯中的關(guān)鍵路徑)成為當(dāng)前的重要研究問題.該問題又因?yàn)榧赫{(diào)度的本身特點(diǎn)區(qū)分為2個(gè)子問題，即將資源調(diào)度過(guò)程進(jìn)行并行可擴(kuò)展設(shè)計(jì)以及將任務(wù)管理過(guò)程進(jìn)行并行可擴(kuò)展設(shè)計(jì)(本文中弱可擴(kuò)展性指僅具備部分可擴(kuò)展設(shè)計(jì)的調(diào)度方法).

2) 資源異構(gòu)性問題.由于集群中計(jì)算設(shè)備的持續(xù)更新、擴(kuò)容，不同設(shè)備處理能力之間的區(qū)別在集群中可能存在顯著差異.例如CPU主頻及緩存差異、內(nèi)存主頻差異等.早期的大數(shù)據(jù)調(diào)度方法中將集群中所有同類型資源都進(jìn)行統(tǒng)一抽象，并不區(qū)分不同的CPU、內(nèi)存之間的可能區(qū)別.隨著新舊硬件之間的能力差別增加，集群調(diào)度需要識(shí)別并考慮資源異構(gòu)性.

3) 面向多線程的放置優(yōu)化問題.目前集群的常見服務(wù)器配置通常支持至少16并發(fā)線程[28].雖然單機(jī)內(nèi)各線程可以并行使用CPU資源，但不同線程普遍存在競(jìng)爭(zhēng)其他資源如硬盤、公用鎖等情況.因此提高單機(jī)并發(fā)度時(shí)通常會(huì)觀測(cè)到顯著的執(zhí)行時(shí)間變化.解決該問題不僅需要數(shù)據(jù)計(jì)算模型的改進(jìn)，同時(shí)也需要高效的調(diào)度方法.

4) 本地性問題.由于網(wǎng)絡(luò)帶寬和存儲(chǔ)設(shè)備吞吐速率之間的顯著差異，不同節(jié)點(diǎn)獲取集群內(nèi)同一數(shù)據(jù)分塊或其備份的時(shí)間代價(jià)顯著不同，因此產(chǎn)生了本地性問題.常見的3級(jí)網(wǎng)絡(luò)拓?fù)涞募哼壿嫿Y(jié)構(gòu)中將產(chǎn)生對(duì)應(yīng)的3級(jí)本地性，即同機(jī)器、同機(jī)架或不同機(jī)架.不同本地性級(jí)別的任務(wù)放置選擇將導(dǎo)致不同的任務(wù)執(zhí)行時(shí)間.

與第2個(gè)挑戰(zhàn)，即工作負(fù)載持續(xù)變化相關(guān)的主要研究問題包括6個(gè)：

1) 作業(yè)內(nèi)任務(wù)關(guān)聯(lián)問題.目前的大數(shù)據(jù)集群中通常運(yùn)行著大量不同的計(jì)算模型.例如 MapReduce[14]，RDD[15]，Tenzing[16]，SparkSQL[17]，Pregel[19]等.每一種計(jì)算模型中，作業(yè)的完成都依賴于作業(yè)內(nèi)部全部計(jì)算任務(wù)的完成.各計(jì)算任務(wù)因計(jì)算模型差異會(huì)存在不同的依賴關(guān)系，這種依賴關(guān)系需要在調(diào)度時(shí)進(jìn)行抽象表達(dá)以精確理解作業(yè)執(zhí)行邏輯，因此產(chǎn)生了作業(yè)內(nèi)任務(wù)關(guān)聯(lián)問題.

2) 延遲敏感任務(wù)問題.在諸多數(shù)據(jù)處理方式中，交互類作業(yè)處理是比較特殊的一類.由于用戶持續(xù)等待交互類作業(yè)處理的結(jié)果，因此需要調(diào)度器提供對(duì)此類延遲敏感作業(yè)的支持保證.調(diào)度延遲敏感作業(yè)有別于調(diào)度常見的批處理作業(yè)，需要調(diào)度器保證其完成時(shí)間最短而不是在限定時(shí)間或服務(wù)等級(jí)內(nèi)完成.

3) 放置約束問題.由于計(jì)算模型的不同，大數(shù)據(jù)集群中的不同計(jì)算任務(wù)對(duì)集群資源的依賴是不一致的.因此部分作業(yè)類型可以通過(guò)調(diào)度獲得“更適合”的節(jié)點(diǎn)，例如CPU密集型任務(wù)和I/O密集型任務(wù)分別適合執(zhí)行與更快速CPU與使用固態(tài)硬盤的服務(wù)器節(jié)點(diǎn).這類并不必須但推薦被調(diào)度于某類節(jié)點(diǎn)的需求被稱為軟約束;與之相對(duì)的，硬約束描述部分?jǐn)?shù)據(jù)處理作業(yè)必須運(yùn)行于特定類型的計(jì)算節(jié)點(diǎn)(如作業(yè)對(duì)GPU計(jì)算的需求).由于二者的相似性，本文將其統(tǒng)稱為放置約束.

4) 多資源調(diào)度問題.正是由于不同計(jì)算任務(wù)對(duì)資源的需求日趨復(fù)雜，大數(shù)據(jù)集群早期對(duì)資源進(jìn)行的單資源類型統(tǒng)一抽象可能降低集群的資源使用效率，因此需要考慮多資源調(diào)度優(yōu)化.

5) 主動(dòng)資源調(diào)整問題.在任務(wù)的執(zhí)行過(guò)程中，不僅是不同計(jì)算任務(wù)之間存在資源需求差異，即使是同一個(gè)計(jì)算任務(wù)，在其自身的完整執(zhí)行周期中對(duì)資源的需求也會(huì)發(fā)生變化.因此可以考慮主動(dòng)調(diào)整資源分配的方式提高集群資源的整體使用效率.

6) 公平性問題.由于不同的計(jì)算任務(wù)的提交者可能是來(lái)自于不同的人或組織，調(diào)度方法需要涉及公平性問題，保證不同提交者對(duì)集群的公平使用.

上述10個(gè)研究問題涵蓋了集群調(diào)度研究工作的主要調(diào)度考慮.通過(guò)分析上述問題可以對(duì)調(diào)度結(jié)構(gòu)的變化進(jìn)行描述和解釋.當(dāng)然，調(diào)度研究工作還涉及除以上所述研究問題之外的內(nèi)容，例如定價(jià)問題、設(shè)備可用性問題、硬件的故障預(yù)測(cè)等.這些問題由于與調(diào)度結(jié)構(gòu)變化的關(guān)聯(lián)較小，不在本文的敘述范圍內(nèi).

2.3 大數(shù)據(jù)背景下的不同集群調(diào)度結(jié)構(gòu)

如圖1所示，在大數(shù)據(jù)背景下，集群調(diào)度方法已逐漸分為4種結(jié)構(gòu)，即集中、雙層、分布式以及混合結(jié)構(gòu).4類調(diào)度結(jié)構(gòu)代表性論文與上述10個(gè)重要調(diào)度問題如表1所示.具體到每一種結(jié)構(gòu)中的論文與研究問題的對(duì)應(yīng)情況將在各小節(jié)分別列出(集中結(jié)構(gòu)、雙層結(jié)構(gòu)、分布式結(jié)構(gòu)、混合結(jié)構(gòu)分別見表2～5.所涉研究問題的多寡與論文的學(xué)術(shù)價(jià)值沒有嚴(yán)格的對(duì)等關(guān)系).從表1還可以獲得關(guān)于4種調(diào)度結(jié)構(gòu)的宏觀認(rèn)知：集中結(jié)構(gòu)與雙層結(jié)構(gòu)考慮更多的本地性、公平性等全局問題;分布式結(jié)構(gòu)研究考慮了更多的可擴(kuò)展性以及延遲敏感任務(wù);混合結(jié)構(gòu)研究仍處于結(jié)構(gòu)探索階段.

Table1 Scheduling Research Concerns Status in Each Scheduling Structure表1 不同調(diào)度結(jié)構(gòu)研究中所針對(duì)的調(diào)度問題統(tǒng)計(jì)

In this table, each integer indicate the amount of publications that consider specific scheduling concern. TP(total number of publication), SC(scalability), LO(locality), FA(fairness), PC(placement constraint), TD(task dependency), LJ(latency-sensitive job), RH(resource heterogeneity), MS(multi-resource scheduling), AA(allocation adjustment), MO(multi-thread optimization).

3 不同調(diào)度結(jié)構(gòu)的研究現(xiàn)狀

3.1 集中調(diào)度結(jié)構(gòu)

1) 大數(shù)據(jù)背景下集中調(diào)度結(jié)構(gòu)的產(chǎn)生

在大數(shù)據(jù)集群發(fā)展的初期，由于大數(shù)據(jù)計(jì)算自身處于發(fā)展探索階段，如HoD(Hadoop on demand)環(huán)境，使用當(dāng)時(shí)成熟的泛用集群調(diào)度方法是最直接且方便的方式.一種典型的方案是組合使用Torque資源管理工具以及Maui或Maob[29]調(diào)度器進(jìn)行調(diào)度.使用這種解決方案的主要目的是以最低的開發(fā)代價(jià)解決當(dāng)時(shí)的集群資源不足和多用戶共享問題.然而，它們的基本工作方式和特點(diǎn)并不符合以MapReduce為主的大數(shù)據(jù)計(jì)算邏輯，產(chǎn)生的問題例如無(wú)法處理數(shù)據(jù)本地性以及過(guò)高的調(diào)度開銷等.

在以上背景下，大數(shù)據(jù)計(jì)算平臺(tái)開始內(nèi)置集中結(jié)構(gòu)調(diào)度器.最具有代表性的是Hadoop1.X版本使用的集中結(jié)構(gòu)調(diào)度器：全部客戶的所有作業(yè)使用唯一提交入口，未獲得執(zhí)行的作業(yè)和任務(wù)暫存在隊(duì)列中；調(diào)度器統(tǒng)一收集作業(yè)執(zhí)行、計(jì)算節(jié)點(diǎn)狀態(tài)等信息并進(jìn)行作業(yè)狀態(tài)管理;集群資源的管理和決策也都在同一節(jié)點(diǎn)上進(jìn)行.在該調(diào)度結(jié)構(gòu)中，作業(yè)決策和資源管理2個(gè)部分都不具備并行的可擴(kuò)展性，只能通過(guò)在模塊內(nèi)部增加或修改代碼的方式進(jìn)行調(diào)度邏輯的擴(kuò)展或調(diào)整.在集中結(jié)構(gòu)的調(diào)度研究中，計(jì)算節(jié)點(diǎn)的資源通常被統(tǒng)一抽象成固定大小的資源槽(slot).相比HoD環(huán)境使用虛擬子集群的方式，資源槽更加細(xì)粒度、易操控.大數(shù)據(jù)環(huán)境的另一個(gè)主要計(jì)算平臺(tái)，Spark也內(nèi)置了完全類似Hadoop1.X的集中結(jié)構(gòu)調(diào)度器.Hadoop1.X以及Spark都可以根據(jù)不同調(diào)度側(cè)重地切換可插拔調(diào)度策略，例如FIFO，Capacity Schedule[30]，F(xiàn)air Scheduler[31]等.

在當(dāng)前的大數(shù)據(jù)計(jì)算環(huán)境下，Borg調(diào)度方法代表了集中調(diào)度結(jié)構(gòu)的前沿.谷歌公司目前使用Borg管理大部分核心集群，其覆蓋集群規(guī)模已經(jīng)達(dá)到10萬(wàn)節(jié)點(diǎn)級(jí).Borg改變了許多集中調(diào)度結(jié)構(gòu)的基本特性，例如使用資源配給(alloc)取代了普通集中調(diào)度結(jié)構(gòu)中的資源槽，使其支持多資源按需分配;采用了集群范圍的調(diào)度策略管控與評(píng)分機(jī)制;此外，雖然在單集群上使用集中調(diào)度結(jié)構(gòu)，但是Borg可以以集群為單位通過(guò)cells并行擴(kuò)展，從而進(jìn)行數(shù)據(jù)中心級(jí)的調(diào)度.

2) 集中調(diào)度結(jié)構(gòu)的相關(guān)研究

本文將所選的集中調(diào)度的代表性研究——對(duì)10個(gè)研究問題的涉及情況——進(jìn)行了整理.如表2所示，集中調(diào)度適合進(jìn)行性全局性的調(diào)度考量，例如考慮公平性、本地性、任務(wù)并行性等.具備完備集群信息的集中調(diào)度器可以對(duì)集群執(zhí)行狀態(tài)進(jìn)行有效推測(cè)，從而提供高精確度的調(diào)度方案.

集中調(diào)度結(jié)構(gòu)有利于公平性保證.在集中調(diào)度結(jié)構(gòu)中，最常見的公平性解決方法是使用傳統(tǒng)的Max-Min公平性模型[53].它約定了針對(duì)某種可以獲取的資源類型，不同的用戶或作業(yè)之間按照各自權(quán)重分配資源的方式.Max-Min公平性模型可以很好地用于及中調(diào)度結(jié)構(gòu)使用的資源槽.Max-Min公平性模型可以快速有效地工作，但是其自身也有很多局限性.例如，該公平性原則并不考慮各作業(yè)的執(zhí)行目標(biāo)，如結(jié)束時(shí)間限制，存在降低集群服務(wù)等級(jí)的風(fēng)險(xiǎn).因此，Ghodsi等人[43]將Max-Min公平性方法擴(kuò)展，形式化定義放置約束下的公平性問題并繼而給出了近似調(diào)度策略以及Choosy調(diào)度模塊.

集中調(diào)度結(jié)構(gòu)中本地性問題的難點(diǎn)在于，本地性需求常常與公平性發(fā)生沖突.按照心跳同步分發(fā)計(jì)算任務(wù)的嚴(yán)格公平性策略經(jīng)常會(huì)使計(jì)算本地性無(wú)法得到保證.使用Max-Min等嚴(yán)格公平策略保證公平性的情況下，集中調(diào)度模塊每次必須選出低資源占用的作業(yè)進(jìn)行策源分配.而該作業(yè)中未必包含了可以獲得較好數(shù)據(jù)本地性的計(jì)算任務(wù).因此，強(qiáng)行將資源分配給該用戶不僅會(huì)導(dǎo)致單個(gè)任務(wù)執(zhí)行的延遲，同時(shí)也會(huì)降低集群資源利用率.針對(duì)以上問題，在集中調(diào)度結(jié)構(gòu)下產(chǎn)生了多種解決思路.Isard等人[33]使用工作流抽象和最優(yōu)化求解方法解決本地性與公平性沖突，并依此設(shè)計(jì)了Quincy調(diào)度模塊.Zaharia等人[34]通過(guò)略微放松公平性的方法獲得本地性該進(jìn).其策略被稱為“延遲調(diào)度”，即如果對(duì)某一作業(yè)的資源分配過(guò)程中可以達(dá)到高本地性，則進(jìn)行資源分配;如果無(wú)法達(dá)到高本地性，那么就暫時(shí)放棄嚴(yán)格公平性.在集中調(diào)度結(jié)構(gòu)中，存儲(chǔ)策略與調(diào)度結(jié)合的研究方向也被證明是解決本地性問題的可行思路.Ananthanarayanan等人[35]認(rèn)為大數(shù)據(jù)集群中本地性問題的關(guān)鍵在于熱點(diǎn)數(shù)據(jù)，因而提出了主動(dòng)預(yù)測(cè)數(shù)據(jù)并發(fā)訪問量、識(shí)別熱點(diǎn)文件以及主動(dòng)備份熱點(diǎn)文件的方法.王強(qiáng)等人[54]在此基礎(chǔ)上提出了以訪問頻率和文件大小共同作為動(dòng)態(tài)調(diào)整備份數(shù)量依據(jù)的數(shù)據(jù)放置與任務(wù)調(diào)度方法，進(jìn)一步減少作業(yè)內(nèi)的數(shù)據(jù)傳輸時(shí)間.不同于一般的本地性研究，Ananthanarayanan等人[55]對(duì)集群計(jì)算中的本地性問題提出了前瞻性思考，認(rèn)為本地性的2個(gè)前置條件(磁盤帶寬高于網(wǎng)絡(luò)帶寬，磁盤讀寫時(shí)間在任務(wù)執(zhí)行總時(shí)長(zhǎng)里占據(jù)較大比重)的有效性逐漸減弱或消失.

Table 2 Scheduling Research Concerns Status in Centralised Scheduling Structure表2 調(diào)度問題統(tǒng)計(jì)-所選集中調(diào)度研究方法

In this table, check mark “√” indicate the specific concern is discussed in corresponding publication. YP(year of publishment),SC(scalability), LO(locality), FA(fairness), PC(placement constraint), TD(task dependency), LJ(latency-sensitive job), RH(resource heterogeneity), MS(multi-resource scheduling), AA(allocation adjustment), MO(multi-thread optimization).

集中調(diào)度結(jié)構(gòu)適合考慮非交互數(shù)據(jù)處理作業(yè)內(nèi)各任務(wù)的依賴關(guān)系.作業(yè)內(nèi)各任務(wù)之間最基本的一種依賴關(guān)系是任務(wù)并行性，即單個(gè)數(shù)據(jù)計(jì)算作業(yè)完成當(dāng)且僅當(dāng)其中的所有計(jì)算任務(wù)全部完成[35].任務(wù)并行性限制導(dǎo)致任何緩慢任務(wù)都會(huì)為作業(yè)帶來(lái)延遲.在集中調(diào)度結(jié)構(gòu)中緩解該問題的一種方法是主動(dòng)縮小任務(wù)粒度.Ousterhout等人[45]提出按照輸入數(shù)據(jù)大小切分任務(wù)的方法，通過(guò)縮小數(shù)據(jù)塊粒度形成大量同構(gòu)的子任務(wù).該方法不僅可以緩解因任務(wù)并行性引起的額外作業(yè)延時(shí)，也可以緩解異構(gòu)負(fù)載中長(zhǎng)任務(wù)阻塞資源隊(duì)列的問題.Ramakrishnan等人[41]則針對(duì)MapReduce模型中Reduce關(guān)鍵詞計(jì)算量不一致導(dǎo)致的并發(fā)延遲問題，提出了Reducer關(guān)鍵詞切分技術(shù).

在集中調(diào)度結(jié)構(gòu)中，通過(guò)主動(dòng)終止并重新調(diào)度緩慢任務(wù)也可以優(yōu)化作業(yè)內(nèi)的并發(fā)性延遲.這種主動(dòng)調(diào)整方法不可避免地導(dǎo)致任務(wù)的重復(fù)執(zhí)行和資源浪費(fèi).該類方法通常基于對(duì)作業(yè)中緩慢任務(wù)的精確識(shí)別.Hadoop平臺(tái)[56]的調(diào)度模塊內(nèi)置了推測(cè)任務(wù)執(zhí)行百分比、識(shí)別并重啟緩慢任務(wù)的特性.然而，由于不同類型任務(wù)之間可能存在的顯著差異[57]，基于執(zhí)行百分比的推測(cè)并不精確.Zaharia等人[32]認(rèn)為，面向任務(wù)執(zhí)行剩余時(shí)間的推測(cè)方式可以有效改進(jìn)緩慢任務(wù)的識(shí)別準(zhǔn)確度.他們繼而提出基于剩余時(shí)長(zhǎng)的主動(dòng)識(shí)別、終止并重啟緩慢任務(wù)的方法.Yadwadkar等人[49]提出可以通過(guò)靜態(tài)學(xué)習(xí)的方法在任務(wù)決策階段提前避免緩慢任務(wù).避免緩慢任務(wù)的另一個(gè)可行研究思路是任務(wù)克隆，通過(guò)在適當(dāng)位置啟動(dòng)完全一致的任務(wù)備份提高任務(wù)按期完成的概率.Ananthanarayanan等人[46]提出了針對(duì)交互作業(yè)的主動(dòng)任務(wù)克隆方法，并指出由于在主流工業(yè)負(fù)載中交互作業(yè)的總資源占用率相對(duì)較低，因此該方法的資源占用開銷相應(yīng)對(duì)整體系統(tǒng)的影響并不顯著.

單個(gè)作業(yè)內(nèi)的各個(gè)任務(wù)除了并行關(guān)系之外，還可能包含串行關(guān)系，抑或同時(shí)存在.Ahmad等人[58]針對(duì)Shuffle階段的任務(wù)依賴關(guān)系進(jìn)行分析，優(yōu)化其網(wǎng)絡(luò)使用、計(jì)算位置等調(diào)度選擇從而減少作業(yè)執(zhí)行總時(shí)長(zhǎng).在多種依賴條件同時(shí)作用的情況下，估算各個(gè)任務(wù)的執(zhí)行情況可以提高作業(yè)調(diào)度.集中調(diào)度結(jié)構(gòu)下最常見的估算方法是建立基于待處理數(shù)據(jù)大小的線性模型[59].李千目等人[60]基于這種線性估算模型提出了Max-D調(diào)度方法，并根據(jù)MapReduce作業(yè)中的任務(wù)關(guān)系對(duì)方法進(jìn)行了進(jìn)一步優(yōu)化.Coppa等人[61]提出了基于近鄰算法和統(tǒng)計(jì)曲線擬合的細(xì)粒度過(guò)程估算方法，改進(jìn)了線性分析模型的準(zhǔn)確度.

由于集中結(jié)構(gòu)可以獲取已經(jīng)到達(dá)的所有計(jì)算任務(wù)信息，因此對(duì)工作負(fù)載規(guī)劃的全局規(guī)劃成為可能.Ferguson等人[39]提出靜態(tài)推測(cè)方法幫助調(diào)度模塊保證作業(yè)需求的完成.結(jié)合推測(cè)正在執(zhí)行任務(wù)狀態(tài)以及到達(dá)作業(yè)狀態(tài)，該方法模擬未來(lái)一段時(shí)間的集群使用情況進(jìn)行調(diào)度規(guī)劃.Henzinger等人[36]提出了基于抽象精化技術(shù)的調(diào)度方法，該方法對(duì)各個(gè)計(jì)算作業(yè)內(nèi)部邏輯進(jìn)行梳理并對(duì)系統(tǒng)狀態(tài)進(jìn)行抽象、提煉，以此作為調(diào)度規(guī)劃的依據(jù).變動(dòng)頻繁、異構(gòu)的工作負(fù)載中，由于任務(wù)類型復(fù)雜多樣，現(xiàn)有任務(wù)的執(zhí)行狀態(tài)和即將到來(lái)的作業(yè)情況都更難預(yù)料.然而由于大數(shù)據(jù)環(huán)境的發(fā)展，集群中作業(yè)保持著復(fù)雜和差異化的趨勢(shì).Delimitrou等人[47]通過(guò)側(cè)寫分類對(duì)不同分類的計(jì)算任務(wù)進(jìn)行邏輯隔離，從而減少因?yàn)楫悩?gòu)性帶來(lái)的相互影響.Yao等人[51]則通過(guò)對(duì)既往集群運(yùn)行痕跡的累計(jì)和學(xué)習(xí)攫取可用的模式和調(diào)度依據(jù)，從而使Hadoop適應(yīng)不同類型的工作負(fù)載.對(duì)不同來(lái)源作業(yè)類型之間的相互影響，Leverich等人[62]則提出了不同種類作業(yè)之間沖突分析以及混合放置技術(shù).

3) 集中調(diào)度結(jié)構(gòu)目前的局限性

2013年Schwarzkopf等人[22]認(rèn)為集中調(diào)度結(jié)構(gòu)存在性能瓶頸和軟件工程復(fù)雜度過(guò)高問題，并以此為依據(jù)提出了基于共享狀態(tài)表的調(diào)度方法.同年Ousterhout等人[63]也描述了集中調(diào)度的針對(duì)低延遲任務(wù)的調(diào)度問題.表2印證了集中調(diào)度研究對(duì)可擴(kuò)展問題、低延遲調(diào)度任務(wù)以及早期研究對(duì)多資源調(diào)度的不足，在本節(jié)中分別分析如下：

① 不可擴(kuò)展問題.集中結(jié)構(gòu)的核心問題是不可擴(kuò)展，隨著集群計(jì)算以及集群自身的持續(xù)發(fā)展，容易導(dǎo)致性能問題以及軟件工程問題.在性能方面，由于集中調(diào)度器是工作負(fù)載和集群資源之間的唯一通路，因此其調(diào)度工作量與通信量會(huì)隨著集群中節(jié)點(diǎn)數(shù)量增加、單節(jié)點(diǎn)能力提升以及工作負(fù)載規(guī)模增長(zhǎng)而變化.調(diào)度器本身也部署于集群中的一個(gè)節(jié)點(diǎn)，其計(jì)算能力的提升僅僅依靠單節(jié)點(diǎn)計(jì)算能力提升.調(diào)度器自身處理能力的提升速度與其調(diào)度工作量的增長(zhǎng)之間不匹配，使調(diào)度器本身成為系統(tǒng)的潛在瓶頸，因此集中調(diào)度結(jié)構(gòu)能夠管理的集群規(guī)模一直受到質(zhì)疑.在軟件工程方面，在多個(gè)研究工作中，如Schwarzkopf等人[22]以及Vavilapalli等人[64]都詳述了集中調(diào)度的軟件工程困境，即在同一代碼模塊中不斷整合大量不同作業(yè)邏輯導(dǎo)致的高維護(hù)、更新開銷.直到2016年，在Verma等人[27]的研究中驗(yàn)證了通過(guò)合理的設(shè)計(jì)，集中調(diào)度結(jié)構(gòu)可以有效管理萬(wàn)規(guī)模的集群.這類前沿研究并未消除集中結(jié)構(gòu)造成系統(tǒng)性能和軟件工程問題的隱患.由于這些前沿工作大部分閉源，集中結(jié)構(gòu)在此方面的能力和發(fā)展還有待檢驗(yàn).

② 缺乏對(duì)延遲敏感作業(yè)的支持問題.任務(wù)敏感作業(yè)通常有2個(gè)需求，首先需要簡(jiǎn)單快速地調(diào)度邏輯以保證作業(yè)可以在最短時(shí)間內(nèi)完成，其次由于當(dāng)前的工業(yè)負(fù)載中任務(wù)敏感作業(yè)通常占負(fù)載中的多數(shù)，因此造成高吞吐需求[63].集中結(jié)構(gòu)由于自身限制難以滿足以上2種需求，因而多數(shù)集中結(jié)構(gòu)下的研究工作不考慮任務(wù)敏感作業(yè)，如表2所示.Delimitrou等人[47]雖然對(duì)延遲敏感任務(wù)的調(diào)度有所考慮，但是該研究所獲得的效果相較Sparrow等分布式調(diào)度器而言還有距離.2016年Gog等人[52]證明了在中等規(guī)模集群內(nèi)(幾百節(jié)點(diǎn))通過(guò)集中調(diào)度可以獲得與Sparrow類似甚至更低的作業(yè)延遲.集中結(jié)構(gòu)對(duì)任務(wù)敏感作業(yè)的支持能力有待未來(lái)進(jìn)一步研究.

除上述2個(gè)主要問題之外，早期的集中結(jié)構(gòu)調(diào)度研究罕有對(duì)多資源進(jìn)行支持.這種問題本身并不是集中調(diào)度自身的局限性，而更多的是歷史原因.早期的數(shù)據(jù)處理模型都使用了單類型資源抽象的方法，因此在2013年之前的調(diào)度研究普遍繼承了這種方式.之后隨著雙層結(jié)構(gòu)研究的流行，多資源調(diào)度成為主流，因此在集中結(jié)構(gòu)研究中也開始考慮多資源調(diào)度并引入相關(guān)設(shè)計(jì).

3.2 雙層調(diào)度結(jié)構(gòu)

1) 大數(shù)據(jù)背景下雙層調(diào)度結(jié)構(gòu)的產(chǎn)生

以Hadoop1.X為例，集中調(diào)度結(jié)構(gòu)中包含的僅僅是對(duì)MapReduce模型的支持，而不能支持其他同樣有廣泛需求的計(jì)算方式如BSP，RDD，MPI等.隨著大數(shù)據(jù)計(jì)算的不斷演化，在同一集群中使用多數(shù)據(jù)計(jì)算模型是必須且急迫的需求.另一方面，集中調(diào)度結(jié)構(gòu)中使用的資源槽抽象方法存在使用不靈活的情況.這些問題促生了雙層結(jié)構(gòu)的集群調(diào)度方法.

Hindman等人[65]率先提出了基于雙層調(diào)度結(jié)構(gòu)的Mesos調(diào)度平臺(tái).Mesos清楚地將調(diào)度結(jié)構(gòu)分為2層，Mesos資源管理層負(fù)責(zé)集群資源的決策和抽象，并以資源配給為單位分配給各平臺(tái);之后由各個(gè)平臺(tái)獨(dú)立在資源配給范圍內(nèi)進(jìn)行任務(wù)的分配.各平臺(tái)內(nèi)原本的調(diào)度器實(shí)際保留了作業(yè)管理職責(zé)，可以在獲得的配給資源范圍內(nèi)調(diào)整任務(wù)執(zhí)行.因?yàn)镠adoop，Spark，MPI等計(jì)算平臺(tái)的良好支持，Mesos在一段時(shí)間內(nèi)是多平臺(tái)環(huán)境資源調(diào)度的最好選擇.Hadoop繼而也在其2.0以及以后版本內(nèi)置了雙層調(diào)度方法Yarn[64].雖然Mesos和Yarn的論文都發(fā)表于2013年，但是在業(yè)界的應(yīng)用分別始于2011—2012年.2011年前者的項(xiàng)目從閉源變?yōu)殚_源，而后者則開始出現(xiàn)于2012年Hadoop的2.0.0-alpha版本中.

目前雙層調(diào)度結(jié)構(gòu)因Mesos，Yarn的廣泛使用成為了最常見的大數(shù)據(jù)集群調(diào)度結(jié)構(gòu).與二者相似的，F(xiàn)acebook出于對(duì)自身負(fù)載規(guī)模的考慮以及不滿足于Mesos與Yarn的執(zhí)行效率，提出了雙層結(jié)構(gòu)的調(diào)度方法Corona[66].Corona為了改進(jìn)作業(yè)調(diào)度延遲，以推送請(qǐng)求的通訊方式替代了常用的心跳匯總方式;因而降低了作業(yè)調(diào)度的必要延遲但是同時(shí)降低了結(jié)構(gòu)自身的可擴(kuò)展性.

2) 雙層調(diào)度結(jié)構(gòu)的相關(guān)研究

以Yarn和Mesos為代表，雙層調(diào)度結(jié)構(gòu)的良好兼容性首先體現(xiàn)在持續(xù)對(duì)更多計(jì)算模型的兼容以及對(duì)集中調(diào)度結(jié)構(gòu)中研究工作的兼容，Mesos目前可以支持的計(jì)算模型已經(jīng)多達(dá)幾十種，其中大數(shù)據(jù)處理計(jì)算模型包括Dpark，Hadoop，Hama，MPI，Spark，Storm等.

如表3所示，雙層結(jié)構(gòu)中的相關(guān)研究工作仍然延續(xù)了集中結(jié)構(gòu)下對(duì)本地型、公平性、放置約束和作業(yè)內(nèi)任務(wù)關(guān)聯(lián)這些全局調(diào)度考量的關(guān)注.集中調(diào)度結(jié)構(gòu)中的研究工作基本都可以在雙層調(diào)度環(huán)境下適用.本地性研究的發(fā)展如孫瑞琦等人[74]提出的基于以及虛擬機(jī)在線遷移技術(shù)[75]以及任務(wù)提交時(shí)虛擬機(jī)能力調(diào)整的高數(shù)據(jù)本地性調(diào)度方法.工作負(fù)載規(guī)劃研究的發(fā)展如Curino等人[69]提出了基于預(yù)約的、混合整數(shù)線性規(guī)劃的調(diào)度方法，該方法可以根據(jù)實(shí)際任務(wù)執(zhí)行狀態(tài)實(shí)時(shí)調(diào)整規(guī)劃方案.

Table 3 Scheduling Research Concerns Status in Two-layer Scheduling Structure表3 調(diào)度問題統(tǒng)計(jì)-所選雙層調(diào)度研究方法

In this table, check mark “√” indicate the specific concern is discussed in corresponding publication. YP(year of publishment),SC(scalability), LO(locality), FA(fairness), PC(placement constraint), TD(task dependency), LJ(latency-sensitive job), RH(resource heterogeneity), MS(multi-resource scheduling), AA(allocation adjustment), MO(multi-thread optimization).

雙層結(jié)構(gòu)相關(guān)研究工作的最大特點(diǎn)是對(duì)多資源調(diào)度的考慮.Mesos與Yarn為代表的雙層調(diào)度結(jié)構(gòu)將資源抽象單位由固定的資源槽改為了靈活的資源組合，因此產(chǎn)生了全新的多資源使用考量.Ghodsi等人[38]在Max-Min公平性模型的基礎(chǔ)上，提出了保障多資源公平性的DRF(dominant resource fairness)調(diào)度模型(該工作的基礎(chǔ)是在集中調(diào)度結(jié)構(gòu)中完成，繼而在雙層結(jié)構(gòu)調(diào)度器中獲得廣泛使用).DRF模型引入了占優(yōu)資源這個(gè)概念，并以各任務(wù)的占優(yōu)資源為公平性判斷的主要標(biāo)準(zhǔn)，從而在多資源考量的前提下保證公平性.在DRF調(diào)度模型的基礎(chǔ)上，Bhattacharya等人[76]完成了針對(duì)分層調(diào)度框架的多資源公平性方法.Wang等人[67]擴(kuò)展了DRF模型對(duì)異構(gòu)集群的支持，提出DRF-H模型.DRF-H模型展開了DRF模型中關(guān)于計(jì)算集群環(huán)境的討論，將多資源公平性模型由同構(gòu)集群假設(shè)擴(kuò)展到了異構(gòu)集群假設(shè).由于資源分配時(shí)只考慮占有資源這單一維度，因此DRF模型和DRF-H模型都很容易因資源碎塊化導(dǎo)致整體集群資源利用率較低.針對(duì)這一問題，王金海等人[77]定義并使用占優(yōu)熵以及占優(yōu)資源權(quán)重，進(jìn)而提出了基于占優(yōu)資源的多資源聯(lián)合公平分配算法，有效提升了集群整體資源利用率.

3) 雙層調(diào)度結(jié)構(gòu)目前的局限性

由于雙層調(diào)度結(jié)構(gòu)的核心資源調(diào)度邏輯仍然依賴不可擴(kuò)展的調(diào)度模塊完成，在保留了集中調(diào)度結(jié)構(gòu)一些缺點(diǎn)的同時(shí)，也引入了新的局限性，其主要的問題如下：

①弱可擴(kuò)展性問題.雙層調(diào)度的資源分配模塊本身仍然是可能的系統(tǒng)瓶頸.尤其是在近幾年隨著小規(guī)模、高吞吐的交互作業(yè)(例如交互查詢)的發(fā)展，負(fù)責(zé)進(jìn)行資源分配的線程容易被超載.同時(shí)，集群內(nèi)資源狀態(tài)同步仍然可能成為調(diào)度瓶頸.由于采用了可并行擴(kuò)展的任務(wù)管理方式，雙層結(jié)構(gòu)的可擴(kuò)展性要好于集中結(jié)構(gòu).隨著近期集中結(jié)構(gòu)對(duì)大規(guī)模集群萬(wàn)量級(jí)集群的調(diào)度成果[27]，雙層調(diào)度在大規(guī)模集群下的潛在性能問題可能會(huì)進(jìn)一步得到改善.

②任務(wù)敏感作業(yè)處理問題.與集中結(jié)構(gòu)的局限性類似，雖然分散的作業(yè)管理邏輯簡(jiǎn)化了調(diào)度流程，但是集中的資源管理仍然不利于任務(wù)敏感作業(yè)的處理.

③資源異構(gòu)性問題.相對(duì)于集中結(jié)構(gòu)，雙層結(jié)構(gòu)中對(duì)資源異構(gòu)性問題(同種資源之間的差異)的考慮顯著減少,如表3所示.根據(jù)Ousterhout等人[78]的研究，考慮多資源時(shí)不同資源的利用率和分配對(duì)集群調(diào)度的影響是不同的，而CPU是影響最大的因素.因而多資源的異構(gòu)與單資源不同不能僅考慮能力差異，還需考慮其對(duì)不同作業(yè)的影響程度等因素.相比而言，在集中結(jié)構(gòu)中考慮單資源調(diào)度的資源異構(gòu)性更容易，只需要考慮單一種類的資源執(zhí)行能力差異.

3.3 分布式調(diào)度結(jié)構(gòu)

1) 大數(shù)據(jù)背景下分布式調(diào)度結(jié)構(gòu)的產(chǎn)生

由于集中調(diào)度結(jié)構(gòu)和雙層調(diào)度結(jié)構(gòu)都使用了不可擴(kuò)展的集群資源分配模塊，因此二者公有了相關(guān)設(shè)計(jì)局限，如3.2節(jié)所述.主要體現(xiàn)在作業(yè)延遲和可擴(kuò)展性2個(gè)方面.

具體來(lái)說(shuō)，隨著大數(shù)據(jù)環(huán)境的發(fā)展，交互作業(yè)類型日趨繁雜，來(lái)自Dremel，Spark，Impala等模型的交互作業(yè)已經(jīng)成為了數(shù)據(jù)計(jì)算集群的重要組成部分，并開始在部分大數(shù)據(jù)集群中占據(jù)過(guò)半的作業(yè)總數(shù)[79].同時(shí)，交互作業(yè)的執(zhí)行時(shí)長(zhǎng)開始降至百微秒級(jí)或更小，因而需要相應(yīng)的遠(yuǎn)低于普通批處理作業(yè)所需的調(diào)度延遲[63].由于這些作業(yè)的交互屬性，提供更低延遲會(huì)直接提升集群使用者的滿意度，并且可以衍生全新的數(shù)據(jù)使用模式.然而，集中調(diào)度結(jié)構(gòu)以及雙層結(jié)構(gòu)的作業(yè)響應(yīng)時(shí)間難以滿足這種需求：由于使用了不可擴(kuò)展的集群資源分配模塊，調(diào)度決策的依次處理和計(jì)算資源信息的統(tǒng)一同步都為作業(yè)調(diào)度延遲設(shè)定了較高下限.此外，隨著集群規(guī)模的擴(kuò)大以及運(yùn)行任務(wù)的增加，在集中的資源分配模塊中可能出現(xiàn)調(diào)度線程自身滿載的情況.

以資源同步過(guò)程為例，集中調(diào)度結(jié)構(gòu)和雙層結(jié)構(gòu)中最常見的心跳同步機(jī)制會(huì)為作業(yè)增加基本延遲時(shí)間，因此為了降低延遲，必須增加各節(jié)點(diǎn)心跳頻率.然而增加心跳頻率會(huì)提高資源分配模塊的同步開銷，造成系統(tǒng)瓶頸，尤其是在當(dāng)前的千數(shù)量級(jí)節(jié)點(diǎn)的大規(guī)模集群環(huán)境下.同理，不采用心跳同步而主動(dòng)獲取資源狀態(tài)的方式[66]則會(huì)引發(fā)更嚴(yán)重的調(diào)度瓶頸問題.在以上背景下，研究者開始探尋使用可并行擴(kuò)展的集群資源分配模塊的可能性.

Schwarzkopf等人[22]實(shí)現(xiàn)了使用共享狀態(tài)表方法的分布式集群調(diào)度器Omega.共享狀態(tài)表方法的核心是使用多個(gè)獨(dú)立的調(diào)度器，其中每個(gè)都擁完整的作業(yè)管理、資源分配模塊以及對(duì)整個(gè)集群所有資源的使用權(quán)限.雖然調(diào)度器相互獨(dú)立，但是調(diào)度決策時(shí)使用的集群資源信息由統(tǒng)一的共享狀態(tài)表獲取.狀態(tài)表模塊負(fù)責(zé)同步集群計(jì)算資源信息并向各個(gè)調(diào)度器進(jìn)行定期推送，因此調(diào)度器決策過(guò)程中使用的集群狀態(tài)信息是不完全實(shí)時(shí)的.

Ousterhout[63]等人依據(jù)“The Power of Two”原則[80]設(shè)計(jì)了取樣集群調(diào)度器Sparrow，并驗(yàn)證了取樣方法在面對(duì)次秒級(jí)交互任務(wù)的有效性.與共享狀態(tài)表相同，取樣調(diào)度同樣可以使用多個(gè)同構(gòu)且獨(dú)立運(yùn)行的調(diào)度器.不同的是，取樣方法將資源狀態(tài)收集也交由各個(gè)調(diào)度器分別進(jìn)行，意味著取樣調(diào)度方法中不再有任何的邏輯關(guān)鍵路徑.如圖2所示.每次決策過(guò)程中，調(diào)度器都要先從集群中取樣選取固定數(shù)量的工作節(jié)者點(diǎn).該次調(diào)度分配的資源必須從所選節(jié)點(diǎn)中獲取;若所選節(jié)點(diǎn)中可用資源不足，則需要將任務(wù)安排至工作者隊(duì)列中.為負(fù)載均衡考慮，每次決策時(shí)都要重新取樣獲得新的工作節(jié)點(diǎn).Sparrow面向以Spark為主的快速數(shù)據(jù)計(jì)算環(huán)境，并已經(jīng)在Spark上衍生出可用的Sparrow分支版本.

Fig. 2 Demonstration of Sparrow scheduling process圖2 Sparrow調(diào)度方法示意

2) 分布式調(diào)度結(jié)構(gòu)的研究特點(diǎn)

如表4所示，分布式調(diào)度研究的基本特點(diǎn)之一就是其普遍的可擴(kuò)展性.比較特殊的是，共享狀態(tài)表方法(表4中Omega以及Apollo)由于唯一狀態(tài)表模塊的存在限制了該方法的可擴(kuò)展性，因此嚴(yán)格意義上來(lái)說(shuō)是介于分布式調(diào)度方法和混合調(diào)度方法之間的調(diào)度結(jié)構(gòu).采樣方法則是充分體現(xiàn)了分布式調(diào)度結(jié)構(gòu)的高可擴(kuò)展性特點(diǎn).在采樣方法的基礎(chǔ)上也可以添加額外的全局控制模塊[81]，從而以可擴(kuò)展性為代價(jià)改進(jìn)調(diào)度準(zhǔn)確性.由于高可擴(kuò)展性，當(dāng)多個(gè)分布式調(diào)度器同時(shí)運(yùn)行于系統(tǒng)中時(shí)，其中任意一個(gè)調(diào)度器的失效并不會(huì)影響系統(tǒng)整體的可用性.集群不需要如集中調(diào)度結(jié)構(gòu)或雙層調(diào)度結(jié)構(gòu)一樣啟用備用節(jié)點(diǎn)，而是僅需將失效節(jié)點(diǎn)的負(fù)載在其它調(diào)度器接入即可.因此分布式調(diào)度結(jié)構(gòu)在具有高可擴(kuò)展性同時(shí)也帶來(lái)了良好的可用性收益.

Table 4 Scheduling Research Concerns Status in Distributed Scheduling Structure表4 調(diào)度問題統(tǒng)計(jì)-所選分布式調(diào)度研究方法

In this table, check mark “√” indicate the specific concern is discussed in corresponding publication. YP(year of publishment),SC(scalability), LO(locality), FA(fairness), PC(placement constraint), TD(task dependency), LJ(latency-sensitive job), RH(resource heterogeneity), MS(multi-resource scheduling), AA(allocation adjustment), MO(multi-thread optimization).

分布式調(diào)度結(jié)構(gòu)具有低調(diào)度延遲的特點(diǎn).取樣方法和狀態(tài)表方法都可以為次秒級(jí)作業(yè)提供低至十毫秒級(jí)的調(diào)度延遲.在共享狀態(tài)表方法中，各個(gè)調(diào)度器隨時(shí)具有全部集群資源的狀態(tài)表，因此調(diào)度決策時(shí)并不需要進(jìn)行單獨(dú)的資源狀態(tài)同步.這種方法有效地降低了調(diào)度延遲.在高負(fù)載集群中，資源狀態(tài)表的非實(shí)時(shí)性可能引發(fā)決策沖突，帶來(lái)額外的調(diào)度延遲.Schwarzkopf等人[22]指出在谷歌生產(chǎn)環(huán)境中，這種沖突的處理代價(jià)在可接受的范圍內(nèi).而Boutin等人[82]則通過(guò)調(diào)度器間的同步協(xié)調(diào)算法以及工作者端任務(wù)隊(duì)列的使用減少?zèng)_突發(fā)生，進(jìn)一步改善作業(yè)延遲.取樣方法中，由于每次調(diào)度僅需要取樣幾個(gè)節(jié)點(diǎn)，且調(diào)度決策也只考慮這幾個(gè)節(jié)點(diǎn)的資源狀態(tài)，因此具備低通信開銷和本地計(jì)算開銷.Sparrow方法中作業(yè)延遲受次優(yōu)決策問題[85]影響.Delimitrou等人[83]通過(guò)2個(gè)技術(shù)減少取樣過(guò)程的次優(yōu)決策的產(chǎn)生:1)通過(guò)動(dòng)態(tài)調(diào)整取樣大小，主動(dòng)保證每次取樣中包含所需資源的概率;2)在難以獲得理想取樣結(jié)果時(shí)對(duì)任務(wù)采取準(zhǔn)入控制.

相較于集中和雙層調(diào)度結(jié)構(gòu)，分布式結(jié)構(gòu)中部分設(shè)計(jì)元素發(fā)生了顯著改變.最有代表性的是隊(duì)列變化，集中和雙層調(diào)度的隊(duì)列設(shè)計(jì)是在調(diào)度器端，而分布式調(diào)度設(shè)計(jì)中開始使用工作者端隊(duì)列.這種變化的原因是，當(dāng)使用調(diào)度器端隊(duì)列時(shí)，無(wú)法立即在工作者節(jié)點(diǎn)獲得資源的任務(wù)必須退回到調(diào)度器進(jìn)行隊(duì)列或重新調(diào)度，造成額外的延遲和通訊開銷.Rasley等人[71]指出工作節(jié)點(diǎn)隊(duì)列的使用有準(zhǔn)確度不高的局限性，且會(huì)將任務(wù)置入相對(duì)難以預(yù)測(cè)的執(zhí)行狀態(tài).他們針對(duì)工作者隊(duì)列進(jìn)行詳細(xì)分析、討論，提出了工作者端隊(duì)列的優(yōu)先級(jí)設(shè)計(jì)以及工作者與調(diào)度器隊(duì)列的平衡算法.

3) 分布式調(diào)度結(jié)構(gòu)目前的局限性

在目前的集群調(diào)度研究領(lǐng)域，分布式調(diào)度結(jié)構(gòu)仍然處于探索和發(fā)展的狀態(tài).伴隨著這種結(jié)構(gòu)突出的優(yōu)點(diǎn)，其自身的局限性也非常明顯，主要包括但不限于：

① 適用性問題.由于缺少集中調(diào)度模塊，分布式方法缺乏對(duì)作業(yè)和資源的全局控制.因此，不同的分布式調(diào)度方法或多或少地對(duì)調(diào)度問題進(jìn)行了簡(jiǎn)化折中.例如在共享狀態(tài)表方法中的樂觀沖突控制[22]，即是以默認(rèn)接受沖突和無(wú)效調(diào)度為基礎(chǔ)的折中.取樣方法則更為明顯，在目前的取樣方法中，仍只能采用單資源調(diào)度以保證取樣的準(zhǔn)確性[83].

② 全局調(diào)度考量問題.各自獨(dú)立的調(diào)度器設(shè)計(jì)使全局調(diào)度考量變得困難.例如取樣方法處理本地性必須直接選取高本地性節(jié)點(diǎn)進(jìn)行調(diào)度，因而嚴(yán)重破壞了由取樣隨機(jī)性帶來(lái)的負(fù)載均衡;而公平性、優(yōu)先級(jí)等調(diào)度考量則需要在工作者隊(duì)列中以局部調(diào)整的方式進(jìn)行.類似地，共享狀態(tài)表方法雖然表面上可以通過(guò)搶占配合狀態(tài)表進(jìn)行全局考量，但因此也會(huì)進(jìn)一步加劇任務(wù)的失敗和重調(diào)度概率.

③ 兼容性問題.除以上局限性問題之外，兼容性是分布式調(diào)度目前不能得到廣泛推廣而主要適用于特定集群的重要原因之一.分布式調(diào)度結(jié)構(gòu)不能直接繼承或者遷移使用集中結(jié)構(gòu)或雙層結(jié)構(gòu)的大多數(shù)研究成果，其原因是后者通常假設(shè)全局資源信息是天然具備的、且并不考慮不同調(diào)度器之間的資源分配沖突.更為重要的是，分布式調(diào)度結(jié)構(gòu)的部署意味著整體大數(shù)據(jù)集群系統(tǒng)的改變，包括數(shù)據(jù)處理代碼的重寫.而它不擅于進(jìn)行全局考量的天然缺點(diǎn)又限制了大數(shù)據(jù)集群對(duì)該調(diào)度結(jié)構(gòu)的需求，因此目前僅見于部分特別需求的大數(shù)據(jù)集群環(huán)境中.

3.4 混合調(diào)度結(jié)構(gòu)

1) 大數(shù)據(jù)背景下混合調(diào)度結(jié)構(gòu)的產(chǎn)生

混合調(diào)度結(jié)構(gòu)代表了在同一個(gè)集群調(diào)度方法中部署不同類型的集群資源分配模塊;使用不可擴(kuò)展的集中資源分配模塊進(jìn)行高準(zhǔn)確度全局調(diào)度的同時(shí)，使用可擴(kuò)展的資源分配模塊進(jìn)行低延遲調(diào)度.混合調(diào)度結(jié)構(gòu)是目前集群調(diào)度的前沿探索，旨在尋找最適合未來(lái)復(fù)雜集群環(huán)境的調(diào)度結(jié)構(gòu).相關(guān)工作主要出現(xiàn)在2014年之后，目前在實(shí)際集群中部署運(yùn)行較罕見，對(duì)該結(jié)構(gòu)的研究探索仍處于起步階段.混合結(jié)構(gòu)的誕生基于研究者對(duì)未來(lái)大數(shù)據(jù)集群工作負(fù)載的預(yù)期，即一定是交互與非交互作業(yè)混雜的.交互作業(yè)需要最小化調(diào)度延遲而非交互作業(yè)需要精確資源放置，這種場(chǎng)景通過(guò)其他調(diào)度結(jié)構(gòu)不易處理.如3.3節(jié)所述，分布式調(diào)度結(jié)構(gòu)具備不可替代的低延遲以及高可擴(kuò)展優(yōu)勢(shì).然而分布式調(diào)度由于缺乏全局控制機(jī)制也難以應(yīng)對(duì)需要特殊調(diào)度需求以及高調(diào)度準(zhǔn)確度的場(chǎng)景.分布式調(diào)度結(jié)構(gòu)的低延遲特性主要?dú)w功于其各自獨(dú)立工作且可并行擴(kuò)展的資源分配模塊.雖然在這些模塊之間建立協(xié)同機(jī)制可以幫助提高分布式調(diào)度結(jié)構(gòu)的準(zhǔn)確度，但同時(shí)也會(huì)增加其決策成本.

目前研究者認(rèn)為集中調(diào)度結(jié)構(gòu)或雙層調(diào)度結(jié)構(gòu)中的統(tǒng)一資源分配模塊與分布式調(diào)度結(jié)構(gòu)中的可擴(kuò)展資源分配模塊可以互補(bǔ)，通過(guò)二者的混合工作同時(shí)滿足不同類型作業(yè)執(zhí)行的需求，即可以同時(shí)提供高準(zhǔn)確度和低延遲調(diào)度.

Karanasos等人[86]組合了Yarn的雙層調(diào)度結(jié)構(gòu)以及通過(guò)協(xié)調(diào)器關(guān)聯(lián)的分布式調(diào)度結(jié)構(gòu)，提出混合結(jié)構(gòu)調(diào)度器Mercury.如圖3所示，Mercury通過(guò)對(duì)計(jì)算任務(wù)的再封裝以及調(diào)度邏輯區(qū)分，為系統(tǒng)提供了相互獨(dú)立的二元調(diào)度策略.使用者可以通過(guò)開發(fā)接口切換調(diào)度邏輯路徑，從而側(cè)重任務(wù)調(diào)度的實(shí)時(shí)性或精確性.在該方法中，分布式調(diào)度的協(xié)調(diào)器輔助集中調(diào)度模塊工作，確保實(shí)現(xiàn)全局調(diào)度考量.實(shí)際工作時(shí)，使用Mercury分布式調(diào)度模塊可以根據(jù)協(xié)調(diào)器提供的弱化集群負(fù)載信息進(jìn)行快速?zèng)Q策;使用集中調(diào)度模塊則需要與Yarn相同進(jìn)行資源需求審批以及分配的過(guò)程.

Fig. 3 Demonstration of Mercury scheduling process圖3 Mercury調(diào)度方法示意

Fig. 4 Demonstration of Hawk scheduling process圖4 Hawk調(diào)度方法示意

Delgado等人[87]通過(guò)整合集中調(diào)度和取樣調(diào)度形成混合結(jié)構(gòu)調(diào)度方法Hawk，如圖4所示.與Mercury不同的是，Hawk方法中并沒有協(xié)同控制器的存在，該調(diào)度方法中分成了獨(dú)立運(yùn)行的多個(gè)取樣調(diào)度器以及唯一的集中調(diào)度器，每個(gè)調(diào)度器都包含了作業(yè)管理以及資源分配模塊的職能.集中調(diào)度器與Spark的集中調(diào)度方法一致，使用心跳同步觸發(fā)調(diào)度過(guò)程并維護(hù)調(diào)度器端優(yōu)先級(jí)隊(duì)列.而取樣調(diào)取器則與Sparrow一致，調(diào)度過(guò)程由作業(yè)到達(dá)觸發(fā)并維持工作者端隊(duì)列.在該研究中同時(shí)提出了取樣偷取技術(shù)改進(jìn)取樣調(diào)度的次優(yōu)決策問題.

混合結(jié)構(gòu)目前的代表性工作較少，如表5所示.混合調(diào)度為延遲敏感任務(wù)提供的執(zhí)行支持不僅僅是通過(guò)優(yōu)先級(jí)以及搶占獲得的，而是通過(guò)2種不同調(diào)度器協(xié)作達(dá)到的執(zhí)行效率提升.混合結(jié)構(gòu)的調(diào)度仍處于前瞻性研究階段，因此目前的研究工作主要考慮延遲敏感任務(wù)與傳統(tǒng)任務(wù)并存的問題.

Table 5 Scheduling Research Concerns Status in Hybrid Scheduling Structure表5 調(diào)度問題統(tǒng)計(jì)-所選混合調(diào)度研究方法

In this table, check mark indicate the specific concern is discussed in corresponding publication. YP(year of publishment),SC(scalability), LO(locality), FA(fairness), PC(placement constraint), TD(task dependency), LJ(latency-sensitive job), RH(resource heterogeneity), MS(multi-resource scheduling), AA(allocation adjustment), MO(multi-thread optimization).

混合調(diào)度結(jié)構(gòu)理論上可以兼具集中結(jié)構(gòu)和分布式結(jié)構(gòu)的優(yōu)點(diǎn).該結(jié)構(gòu)的可擴(kuò)展性取決于集中調(diào)度器的使用頻率和使用方式.2種調(diào)度器協(xié)同工作時(shí)，混合結(jié)構(gòu)的可擴(kuò)展性介于集中結(jié)構(gòu)和分布式結(jié)構(gòu)之間，受限于集中調(diào)度器的使用頻率和決策邏輯；完全運(yùn)行交互作業(yè)時(shí)，所有作業(yè)都通過(guò)分布式調(diào)度器提交，混合調(diào)度結(jié)構(gòu)的調(diào)度方法等同于分布式結(jié)構(gòu)，具備良好的可擴(kuò)展性；當(dāng)所有作業(yè)都不通過(guò)分布式調(diào)度器提交時(shí)，混合調(diào)去結(jié)構(gòu)等同于集中(或雙層)調(diào)度結(jié)構(gòu).同時(shí)以集中調(diào)度器作為中心，全局資源信息可以向分布式調(diào)度器進(jìn)行廣播，以便于提高調(diào)度精確度.Delgado等人[88]提出了通過(guò)集中調(diào)度器向分布式調(diào)度器主動(dòng)推送延遲任務(wù)信息以改進(jìn)分布式調(diào)度延遲的方法.

混合結(jié)構(gòu)使用了不可擴(kuò)展的資源分配模塊，在集中調(diào)度結(jié)構(gòu)或雙層調(diào)度結(jié)構(gòu)下的研究成果和代碼大多可以被很好地兼容并方便地遷移.同時(shí)，分布式調(diào)度研究中產(chǎn)生的研究結(jié)果和代碼也可以直接套用到相應(yīng)的混合結(jié)構(gòu)中.例如Hawk中的資源分配模塊由于使用了取樣方法，可以方便地繼承Sparrow中的所有優(yōu)化機(jī)制.

2) 混合調(diào)度結(jié)構(gòu)目前的局限性

作為目前對(duì)于調(diào)度結(jié)構(gòu)的前沿探索，混合結(jié)構(gòu)調(diào)度的研究工作仍然處于初期的階段.它在理論上能夠帶來(lái)對(duì)于工業(yè)負(fù)載中復(fù)雜任務(wù)的支持，也兼具了分布式結(jié)構(gòu)的可擴(kuò)展特點(diǎn).但是，僅從目前的研究來(lái)看該結(jié)構(gòu)仍有比較強(qiáng)的局限性.

① 結(jié)構(gòu)復(fù)雜度問題.復(fù)雜的結(jié)構(gòu)帶來(lái)了更高的維持成本，混合調(diào)度結(jié)構(gòu)需要支付兩套調(diào)度系統(tǒng)的正常運(yùn)行開銷.同時(shí)，充分使用混合調(diào)度結(jié)構(gòu)必須有效使用其2個(gè)資源調(diào)度部分，因此使用者必須經(jīng)歷新的學(xué)習(xí)過(guò)程以及相關(guān)的代碼重寫.

② 資源分配沖突問題.使用分布式的資源分配邏輯本身會(huì)引起沖突，在此基礎(chǔ)上引入集中資源分配邏輯將會(huì)使沖突加劇.在現(xiàn)有的設(shè)計(jì)中集中模塊都負(fù)責(zé)調(diào)度優(yōu)先級(jí)較低的批處理任務(wù)，該部分任務(wù)在調(diào)度沖突時(shí)會(huì)被終止[86].引入集中資源分配模塊的目標(biāo)是高準(zhǔn)確性，因此需要實(shí)時(shí)獲知正確的集群計(jì)算資源狀態(tài).然而分布式調(diào)度模塊面向高吞吐的交互作業(yè)，其更為頻繁的資源分配很容易搶占集中資源分配的目標(biāo)計(jì)算資源.而提高集中調(diào)度的資源狀態(tài)同步頻率雖然可以緩解上述沖突，但會(huì)嚴(yán)重增加調(diào)度的必要開銷.因此混合調(diào)度結(jié)構(gòu)目前可能在某些實(shí)驗(yàn)條件下會(huì)有很好的執(zhí)行結(jié)果，但是其實(shí)際生產(chǎn)過(guò)程中的適用性仍有待后續(xù)發(fā)展和檢驗(yàn).

4 集群調(diào)度結(jié)構(gòu)的發(fā)展展望

當(dāng)前集群調(diào)度結(jié)構(gòu)研究仍然處于起步階段，新思路、新方法、新技術(shù)不斷涌現(xiàn)，各類調(diào)度結(jié)構(gòu)的研究?jī)?nèi)容、特性以及局限性都在變化之中.因此，哪種調(diào)度結(jié)構(gòu)最能應(yīng)對(duì)未來(lái)集群中大數(shù)據(jù)挑戰(zhàn)遠(yuǎn)無(wú)定論.

本文嘗試從3方面對(duì)集群調(diào)度結(jié)構(gòu)未來(lái)的研究發(fā)展方向進(jìn)行闡述：1)從文獻(xiàn)統(tǒng)計(jì)分析的角度總結(jié)各種調(diào)度結(jié)構(gòu)關(guān)注的熱點(diǎn)問題；2)通過(guò)著名研究團(tuán)隊(duì)的前沿研究工作分析各種調(diào)度結(jié)構(gòu)的發(fā)展趨勢(shì)；3)根據(jù)我們研究團(tuán)隊(duì)對(duì)集群調(diào)度的理解，對(duì)未來(lái)發(fā)展方向提出粗淺看法.

從文獻(xiàn)統(tǒng)計(jì)的角度看：在有關(guān)集中調(diào)度結(jié)構(gòu)的研究成果中，討論本地性和公平性文獻(xiàn)超過(guò)50%，從2014年，關(guān)注延遲敏感任務(wù)和多資源調(diào)度的文獻(xiàn)從無(wú)到有，分別達(dá)到43%和50%，如表2所示.因此，公平性、本地性、多資源調(diào)度和延遲敏感任務(wù)是其優(yōu)先考慮的研究問題.在雙層調(diào)度結(jié)構(gòu)研究成果中，本地性、公平性、放置約束、作業(yè)內(nèi)任務(wù)關(guān)聯(lián)以及多資源調(diào)度5個(gè)問題的文章都超過(guò)了50%，如表3所示.因此，上述5個(gè)問題是雙層結(jié)構(gòu)調(diào)度研究?jī)?yōu)先考慮的問題.在分布式調(diào)度研究成果中，除作業(yè)內(nèi)任務(wù)關(guān)聯(lián)與主動(dòng)資源調(diào)整問題之外，其余研究問題的文獻(xiàn)都超過(guò)了50%，如表4所示.因此，未來(lái)的分布式調(diào)度研究需要考慮全面，討論盡量多的研究問題.目前，有關(guān)混合結(jié)構(gòu)現(xiàn)有文獻(xiàn)較少，如表5所示，且對(duì)除延遲敏感作業(yè)與可擴(kuò)展性之外的問題討論不多.由此可知該方向尚處于起步階段，短期內(nèi)的研究仍會(huì)以結(jié)構(gòu)性探索為主.

從著名研究團(tuán)隊(duì)的前沿研究工作看：對(duì)于集中調(diào)度結(jié)構(gòu)，谷歌和劍橋前沿研究工作[27,52]打破了研究者對(duì)集中調(diào)度的固有認(rèn)知，展示出集中結(jié)構(gòu)對(duì)當(dāng)前以及未來(lái)大規(guī)模集群的調(diào)度能力和對(duì)延遲敏感作業(yè)的初步支撐能力.這2個(gè)方向可能是未來(lái)的研究熱點(diǎn).同時(shí)考慮到這2部分研究目前是閉源狀態(tài)，將它們進(jìn)行開源實(shí)現(xiàn)也具有重要意義.對(duì)于雙層調(diào)度結(jié)構(gòu)，近幾年開源項(xiàng)目Mesos開始選擇與Yarn差異化設(shè)計(jì)，逐漸支持跨平臺(tái)資源整合.此類雙層結(jié)構(gòu)未來(lái)可以很好地適用于集群衍生的一些計(jì)算場(chǎng)景，例如最近興起的霧計(jì)算[89]研究.對(duì)于分布式調(diào)度結(jié)構(gòu)，來(lái)自微軟和斯坦福的最新研究成果表明[82-83]，共享狀態(tài)表方法的并發(fā)沖突問題和取樣方法的精確度問題具有較大的應(yīng)用潛力與研究?jī)r(jià)值.除上述2方向外，本文認(rèn)為研究者可以嘗試將其他研究方向中已經(jīng)得到驗(yàn)證的協(xié)作機(jī)制，例如耳語(yǔ)機(jī)制[90]引入分布式調(diào)度研究，從而使各獨(dú)立調(diào)度器更高效地協(xié)同工作.最后，由于混合結(jié)構(gòu)的研究較少，尚處于起步階段，已在前文進(jìn)行了分析，在此不再贅述.

從我們研究團(tuán)隊(duì)的理解看:集群計(jì)算環(huán)境的整體改變(包括集群自身變化與新型工作負(fù)載出現(xiàn))通常是引起集群調(diào)度結(jié)構(gòu)不斷演化的主要原因.我們認(rèn)為機(jī)架級(jí)計(jì)算(rack-scale computing)在未來(lái)將取代現(xiàn)有的集群計(jì)算結(jié)構(gòu)(這同時(shí)也是微軟、英特爾等企業(yè)對(duì)集群計(jì)算共有的愿景)，即機(jī)架逐漸變成集群拓?fù)浣Y(jié)構(gòu)中的最下層[91].整合單機(jī)架內(nèi)資源，從軟、硬件角度拋棄傳統(tǒng)的服務(wù)器單位.從目前誕生的具備機(jī)架級(jí)計(jì)算特質(zhì)的原型[92-93]中可以預(yù)見，機(jī)架計(jì)算對(duì)集群調(diào)度的影響將是顛覆性的，新的方法甚至新的調(diào)度結(jié)構(gòu)也許會(huì)在該場(chǎng)景中產(chǎn)生.對(duì)當(dāng)前的普通集群調(diào)度研究者而言，機(jī)架級(jí)大數(shù)據(jù)集群的調(diào)度方法是相對(duì)空白但前景光明的研究領(lǐng)域;英特爾公司也已經(jīng)提供了開源的機(jī)架級(jí)資源整合工具[94]，使用者可以通過(guò)該工具在傳統(tǒng)集群上模擬機(jī)架計(jì)算，提前實(shí)現(xiàn)和驗(yàn)證在該場(chǎng)景下的調(diào)度方法與結(jié)構(gòu)設(shè)想.

5 結(jié)束語(yǔ)

大數(shù)據(jù)背景下的調(diào)度問題一直是集群計(jì)算中的熱點(diǎn)研究問題.目前國(guó)際上有多個(gè)在持續(xù)進(jìn)行相關(guān)研究工作的高水平研究機(jī)構(gòu)，不僅包括谷歌、微軟、Hotonworks，F(xiàn)acebook等大數(shù)據(jù)領(lǐng)域的領(lǐng)軍企業(yè)，還包括例如加州大學(xué)伯克利分校的NetSys實(shí)驗(yàn)室[95]、劍橋大學(xué)計(jì)算機(jī)系的系統(tǒng)研究組[96]等高校研究小組.他們各自有出色且成體系的調(diào)度研究工作，保證了該研究方向持續(xù)的業(yè)界發(fā)展和學(xué)術(shù)活力.也正因如此，在集群環(huán)境快速變化的今天，產(chǎn)生出了優(yōu)劣各異的調(diào)度結(jié)構(gòu)以及多樣的調(diào)度方法.相較于美國(guó)、歐洲而言，我國(guó)在該方向的調(diào)度研究處于相對(duì)較弱的階段.雖然不乏杰出的研究者從事相關(guān)工作，但是相對(duì)于我國(guó)大數(shù)據(jù)行業(yè)的整體體量來(lái)說(shuō)研究成果仍然較少.希望本文能為從事該方向研究的人員提供有益的參考.

[1] Fuchel K, Heller S. Consideration in the design of a multiple computer system with extended core storage[C] //Proc of the 1st ACM Symp on Operating System Principles. New York: ACM, 1967: 17.11-17.13

[2] Wulf W, Cohen E, Corwin W, et al. Hydra: The kernel of a multiprocessor operating system[J]. Communications of the ACM, 1974, 17(6): 337-345

[3] Ousterhout J K, Scelza D A, Sindhu P S. Medusa: An experiment in distributed operating system structure[J]. Communications of the ACM, 1980, 23(2): 92-105

[4] Rashid R F, Robertson G G. Accent: A communication oriented network operating system kernel[J]. ACM Sigops Operating Systems Review, 1981, 15(5): 64-75

[5] Dong Fangpeng, Gong Yili, Li Wei, et al. Research on resource discovery mechanisms in grids[J]. Journal of Computer Research and Development, 2003, 40(12): 1749-1755 (in Chinese)

(董方鵬, 龔奕利, 李偉, 等. 網(wǎng)格環(huán)境中資源發(fā)現(xiàn)機(jī)制的研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2003, 40(12): 1749-1755)

[6] Hovestadt M, Kao O, Keller A, et al. Scheduling in HPC resource management systems: Queuing vs Planning[J]. Genetica, 2003, 112-113(1): 445-461

[7] Wang Yuanzhuo, Jin Xiaolong, Cheng Xueqi. Network big data: Present and future[J]. Chinese Journal of Computers, 2013, 36(6): 1125-1138 (in Chinese)

(王元卓, 靳小龍, 程學(xué)旗. 網(wǎng)絡(luò)大數(shù)據(jù): 現(xiàn)狀與展望[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(6): 1125-1138)

[8] China Computer Federation. CCF Publication Ranking[OL]. [2016-07-20]. http://www.ccf.org.cn/sites/ccf/biaodan.jsp?contentId=2567518742937

[9] Computing Research and Education. Core Conf Ranking[OL]. [2016-07-20]. http://portal.core.edu.au/conf-ranks/

[10] Mishra M K, Patel Y S, Rout Y, et al. A survey on scheduling heuristics in grid computing environment[J]. International Journal of Modern Education and Computer Science, 2014, 6(10): 57-77

[11] Qureshi M B, Dehnavi M M, Min-Allah N, et al. Survey on grid resource allocation mechanisms[J]. Journal of Grid Computing, 2014, 12(2): 399-441

[12] Bala A, Chana I. A survey of various workflow scheduling algorithms in cloud environment[C] //Proc of the 2nd National Conf on Information and Communication Technology. Piscataway, NJ: IEEE, 2011: 26-30

[13] Chen Kang, Zheng Weimin. Cloud computing: System instances and current research[J]. Journal of Software, 2009, 20(5): 1337-1348 (in Chinese)

(陳康, 鄭緯民. 云計(jì)算: 系統(tǒng)實(shí)例與研究現(xiàn)狀[J]. 軟件學(xué)報(bào), 2009, 20(5): 1337-1348)

[14] Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113

[15] Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[C] //Proc of the 9th USENIX Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: 2-14

[16] Chattopadhyay B, Lin L, Liu W, et al. Tenzing a SQL implementation on the MapReduce framework[C] //Proc of the 37th Int Conf on Very Large Data Base. Berlin: Springer, 2011: 23-33

[17] Armbrust M, Xin R S, Lian C, et al. SparkSQL: Relational data processing in Spark[C] //Proc of the 2015 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2015: 1383-1394

[18] Thusoo A, Sarma J S, Jain N, et al. Hive: A warehousing solution over a Map-Reduce framework[J]. The VLDB Endowment, 2009, 2(2): 1626-1629

[19] Malewicz G, Austern M H, Bik A J, et al. Pregel: A system for large-scale graph processing[C] //Proc of the 2010 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 135-146

[20] Curtiss M, Becker I, Bosman T, et al. Unicorn: A system for searching the social graph[J]. Proceedings of the VLDB Endowment, 2013, 6(11): 1150-1161

[21] Hussain H, Malik S U R, Hameed A, et al. A survey on resource allocation in high performance distributed computing systems[J]. Parallel Computing, 2013, 39(11): 709-736

[22] Schwarzkopf M, Konwinski A, Abd-El-Malek M, et al. Omega: Flexible, scalable schedulers for large compute clusters[C] //Proc of the 8th ACM European Conf on Computer Systems. New York: ACM, 2013: 351-364

[23] Valentini G L, Lassonde W, Khan S U, et al. An overview of energy efficiency techniques in cluster computing systems[J]. Cluster Computing, 2013, 16(1): 3-15

[24] EMC Corporation. The digital universe of opportunities: Rich data and the increasing value of the Internet of things[OL]. [2016-12-02]. https://www.emc.com/leadership/digital-universe/2014iview/executive-summary.htm

[25] Facebook Corporation. The top 20 valuable Facebook statistics[OL]. [2016-12-21]. https://zephoria.com/top-15-valuable-facebook-statistics/

[26] Google Corporation. 2013 Founders’ Letter[OL]. [2016-09-18]. http://investor.google.com/corporate/2013/founders-letter.html

[27] Verma A, Pedrosa L, Korupolu M, et al. Large-scale cluster management at Google with Borg[C] //Proc of the 10th ACM European Conf on Computer Systems. New York: ACM, 2015: 18-34

[28] Amazon Corperation. EC2 Service[OL]. [2017-01-20]. https://aws.amazon.com/ec2/

[29] Maob. HPC Suite[OL]. [2016-08-12]. http://www.adaptive computing.com/products/hpc-products/moab-hpc-basic-edition/

[30] Hadoop Project. Capacity Scheduler[OL]. [2017-01-19]. https://hadoop.apache.org/docs/r1.2.1/capacity_scheduler.html

[31] Hadoop Project. Fair Scheduler[OL]. [2017-01-19]. https://hadoop.apache.org/docs/r1.2.1/fair_scheduler.html

[32] Zaharia M, Konwinski A, Joseph A D, et al. Improving MapReduce performance in heterogeneous environments[C] //Proc of the 8th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2008: 29-42

[33] Isard M, Prabhakaran V, Currey J, et al. Quincy: Fair scheduling for distributed computing clusters[C] //Proc of the 22nd ACM Symp on Operating Systems Principles. New York: ACM, 2009: 261-276

[34] Zaharia M, Borthakur D, Sen Sarma J, et al. Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling[C] //Proc of the 5th ACM European Conf on Computer Systems. New York: ACM, 2010: 265-278

[35] Ananthanarayanan G, Kandula S, Greenberg A G, et al. Reining in the outliers in Map-Reduce custers using Mantri[C] //Proc of the 9th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2010: 24-35

[36] Henzinger T A, Singh V, Wies T, et al. Scheduling large jobs by abstraction refinement[C] //Proc of the 6th ACM European Conf on Computer Systems. New York: ACM, 2011: 329-342

[37] Ananthanarayanan G, Agarwal S, Kandula S, et al. Scarlett: Coping with skewed content popularity in MapReduce clusters[C] //Proc of the 6th ACM European Conf on Computer Systems. New York: ACM, 2011: 287-300

[38] Ghodsi A, Zaharia M, Hindman B, et al. Dominant resource fairness: Fair allocation of multiple resource types[C] //Proc of the 8th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2011: 24-34

[39] Ferguson A D, Bodik P, Kandula S, et al. Jockey: Guaranteed job latency in data parallel clusters[C] //Proc of the 7th ACM European Conf on Computer Systems. New York: ACM, 2012: 99-112

[40] Tumanov A, Cipar J, Ganger G R, et al. Alsched: Algebraic scheduling of mixed workloads in heterogeneous clouds[C] //Proc of the 3rd ACM Symp on Cloud Computing. New York: ACM, 2012: 1-7

[41] Ramakrishnan S R, Swart G, Urmanov A. Balancing reducer skew in MapReduce workloads using progressive sampling[C] //Proc of the 3rd ACM Symp on Cloud Computing. New York: ACM, 2012: 16-29

[42] Mars J, Tang Liu. Whare-map: Heterogeneity in homogeneous warehouse-scale computers[C] //Proc of ACM SIGARCH Computer Architecture News. New York: ACM, 2013: 619-630

[43] Ghodsi A, Zaharia M, Shenker S, et al. Choosy: Max-min fair sharing for datacenter jobs with constraints[C] //Proc of the 8th ACM European Conf on Computer Systems. New York: ACM, 2013: 365-378

[44] Delimitrou C. Kozyrakis C. Qos-aware scheduling in heterogeneous datacenters with paragon[J]. ACM Trans on Computer Systems, 2013, 31(4): 12-25

[45] Ousterhout K, Panda A, Rosen J, et al. The case for tiny tasks in compute clusters[C] //Proc of the 14th Workshop on Hot Topics in Operating Systems. Berkeley, CA: USENIX Association, 2013: 12-18

[46] Ananthanarayanan G, Ghodsi A, Shenker S, et al. Effective straggler mitigation: Attack of the clones[C] //Proc of the 10th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2013: 185-198

[47] Delimitrou C, Kozyrakis C. Quasar: Resource-efficient and QoS-aware cluster management[C] //Proc of the 19th ACM Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2014: 127-144

[48] Venkataraman S, Panda A, Ananthanarayanan G, et al. The power of choice in data-aware cluster scheduling[C] //Proc of the 11th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2014: 301-316

[49] Yadwadkar N J, Ananthanarayanan G, Katz R. Wrangler: Predictable and faster jobs using fewer resources[C] //Proc of the 5th ACM Symp on Cloud Computing. New York: ACM, 2014: 1-14

[50] Zhang Qi, Zhani M F, Yang Yuke, et al. PRISM: Fine-grained resource-aware scheduling for MapReduce[J]. IEEE Trans on Cloud Computing, 2015, 3(2): 182-194

[51] Yao Yi, Tai Jianzhe, Sheng Bo, et al. LsPS: A job size-based scheduler for efficient task assignments in Hadoop[J]. IEEE Trans on Cloud Computing, 2015, 3(4): 411-424

[52] Gog I, Schwarzkopf M, Gleave A, et al. Firmament: Fast, centralized cluster scheduling at scale[C] //Proc of the 12th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2016: 99-115

[53] Hahne E L. Round-robin scheduling for max-min fairness in data networks[J]. IEEE Journal on Selected Areas in Communications, 1991, 9(7): 1024-1039

[54] Wang Qiang, Li Xiongfei, Wang Jing. A data placement and task scheduling algorithm in cloud computing[J]. Journal of Computer Research and Development, 2014, 51(11): 2416-2426 (in Chinese)

(王強(qiáng), 李雄飛, 王婧. 云計(jì)算中的數(shù)據(jù)放置與任務(wù)調(diào)度算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(11): 2416-2426)

[55] Ananthanarayanan G, Ghodsi A, Shenker S, et al. Disk-locality in datacenter computing considered irrelevant[C] //Proc of the 13th Workshop on Hot Topics in Operating Systems. Berkeley, CA: USENIX Association, 2011: 12-15

[56] Apache. Hadoop Project[OL]. [2017-01-20]. http://hadoop.apache.org/

[57] Reiss C, Tumanov A, Ganger G R, et al. Heterogeneity and dynamicity of clouds at scale: Google trace analysis[C] //Proc of the 3rd ACM Symp on Cloud Computing. New York: ACM, 2012: 7-19

[58] Ahmad F, Chakradhar S T, Raghunathan A, et al. Shufflewatcher: Shuffle-aware scheduling in multi-tenant Mapeduce clusters[C] //Proc of the 2014 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2014: 1-13

[59] Morton K, Balazinska M, Grossman D. ParaTimer: A progress indicator for MapReduce DAGs[C] //Proc of the 29th ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 507-518

[60] Li Qianmu, Zhang Shengxiao, Lu Lu, et al. A job scheduling algorithm and hybrid scheduling method on Hadoop platform[J]. Journal of Computer Research and Development, 2013, 50(Suppl1): 361-368 (in Chinese)

(李千目, 張晟驍, 陸路, 等. 一種Hadoop平臺(tái)下的調(diào)度算法及混合調(diào)度策略[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(增刊1): 361-368)

[61] Coppa E, Finocchi I. On data skewness, stragglers, and MapReduce progress indicators[C] //Proc of the 6th ACM Symp on Cloud Computing. New York: ACM, 2015: 139-152

[62] Leverich J, Kozyrakis C. Reconciling high server utilization and sub-millisecond quality-of-service[C] //Proc of the 9th European Conf on Computer Systems. Berkeley, CA: USENIX Association, 2014: 4-19

[63] Ousterhout K, Wendell P, Zaharia M, et al. Sparrow: Distributed, low latency scheduling[C] //Proc of the 24th ACM Symp on Operating Systems Principles. New York: ACM, 2013: 69-84

[64] Vavilapalli V K, Murthy A C, Douglas C, et al. Apache Hadoop YARN: Yet another resource negotiator[C] //Proc of the 4th ACM Symp on Cloud Computing. New York: ACM, 2013: 5-20

[65] Hindman B, Konwinski A, Zaharia M, et al. Mesos: A platform for fine-grained resource sharing in the data center[C] //Proc of the 8th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2011: 22-35

[66] Facebook Corperation. Under the hood: Scheduling MapReduce jobs more efficiently with Corona[OL]. [2017-01-10]. https://www.facebook.com/notes/facebook-engineering/under-the-hood-scheduling-mapreduce-jobs-more-efficiently-with-corona/10151142560538920

[67] Wang Wei, Li Baochun, Liang Ben. Dominant resource fairness in cloud computing systems with heterogeneous servers[C] //Proc of the 33rd IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2014: 583-591

[68] Cho B, Rahman M, Chajed T, et al. Natjam: Design and evaluation of eviction policies for supporting priorities and deadlines in MapReduce clusters[C] //Proc of the 4th ACM Symp on Cloud Computing. New York: ACM, 2013: 6-17

[69] Curino C, Difallah D E, Douglas C, et al. Reservation-based scheduling: If you’re late don’t blame us![C] //Proc of the 5th ACM Symp on Cloud Computing. New York: ACM, 2014: 1-14

[70] Grandl R, Ananthanarayanan G, Kandula S, et al. Multi-resource packing for cluster schedulers[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(4): 455-466

[71] Rasley J, Karanasos K, Kandula S, et al. Efficient queue management for cluster scheduling[C] //Proc of the 11th European Conf on Computer Systems. Berkeley, CA: USENIX Association, 2016: 36-48

[72] Grandl R, Kandula S, Rao S, et al. Graphene: Packing and dependency-aware scheduling for data-parallel clusters[C] //Proc of the 12th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2016: 81-97

[73] Grandl R, Chowdhury M, Akella A, et al. Altruistic scheduling in multi-resource clusters[C] //Proc of the 12th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2016: 65-70

[74] Sun Ruiqi, Yang Jie, Gao Zhan, et al. A resource scheduling approach to improving data locality for virtualized Hadoop cluster[J]. Journal of Computer Research and Development, 2014(Suppl2): 189-198 (in Chinese)

(孫瑞琦, 楊杰, 高瞻, 等. 一種提高虛擬化Hadoop系統(tǒng)數(shù)據(jù)本地性的資源調(diào)度方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014(增刊2): 189-198)

[75] Clark C G, Fraser K, Hand S, et al. Live migration of virtual machines[C] //Proc of the 2nd Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2005: 273-286

[76] Bhattacharya A A, Culler D, Friedman E, et al. Hierarchical scheduling for diverse datacenter workloads[C] //Proc of the 4th ACM Symp on Cloud Computing. New York: ACM, 2013: 1-15

[77] Wang Jinhai, Huang Chuanhe, Wang Jing, et al. A heterogeneous cloud computing architecture and multi-resource-joint fairness allocation strategy[J]. Journal of Computer Research and Development, 2015, 52(6): 1288-1302 (in Chinese)

(王金海, 黃傳河, 王晶, 等. 異構(gòu)云計(jì)算體系結(jié)構(gòu)及其多資源聯(lián)合公平分配策略[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(6): 1288-1302)

[78] Ousterhout K, Rasti R, Ratnasamy S, et al. Making sense of performance in data analytics frameworks[C] //Proc of the 10th USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2015: 293-307

[79] Chen Yanpei, Alspaugh S, Borthakur D, et al. Energy efficiency for large-scale MapReduce workloads with significant interactive analysis[C] //Proc of the 6th ACM European Conf on Computer Systems. Berkeley, CA: USENIX Association, 2012: 43-56

[80] Mitzenmacher M. The power of two choices in randomized load balancing[J]. IEEE Trans on Parallel & Distributed Systems, 2001, 12(10): 1094-1104

[81] Goder A, Spiridonov A, Wang Yin. Bistro: Scheduling data-parallel jobs against live production systems[C] //Proc of the 2015 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2015: 459-471

[82] Boutin E, Ekanayake J, Lin Wei, et al. Apollo: Scalable and coordinated scheduling for cloud-scale computing[C] //Proc of the 11th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2014: 285-300

[83] Delimitrou C, Sanchez D, Kozyrakis C. Tarcil: Reconciling scheduling speed and quality in large shared clusters[C] //Proc of the 6th ACM Symp on Cloud Computing. New York: ACM, 2015: 97-110

[84] Wang Ke, Liu Ning, Sadooghi I, et al. Overcoming Hadoop scaling limitations through distributed task execution[C] //Proc of 2015 IEEE Int Conf on Cluster Computing. Piscataway, NJ: IEEE, 2015: 236-245

[85] Hao Chunliang, Shen Jie, Zhang Heng, et al. Sparkle: Adaptive sample based scheduling for cluster computing[C] //Proc of the 5th Int Workshop on Cloud Data and Platforms. Berkeley, CA: USENIX Association, 2015: 1-6

[86] Karanasos K, Rao S, Curino C, et al. Mercury: Hybrid centralized and distributed scheduling in large shared clusters[C] //Proc of the 2015 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2015: 485-497

[87] Delgado P, Dinu F, Kermarrec A M, et al. Hawk: Hybrid datacenter scheduling[C] //Proc of the 2015 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2015: 499-510

[88] Delgado P, Didona D, Dinu F, et al. Job-aware scheduling in Eagle: Divide and stick to your probes[C] // Proc of the 7th ACM Symp on Cloud Computing. New York: ACM, 2016: 497-509

[89] Bonomi F, Milito R, Zhu Jiang, et al. Fog computing and its role in the Internet of things[C] //Proc of the 1st MCC Workshop on Mobile Cloud Computing. New York: ACM, 2012: 13-16

[90] Wuhib F, Stadler R, Spreitzer M. Gossip-based resource management for cloud environments[C] //Proc of the 2010 Int Conf on Network and Service Management. New York: ACM, 2010: 1-8

[91] Microsoft Corperation. Rack-scale Computing[OL]. [2017-01-20]. https://www.microsoft.com/en-us/research/project/rack-scale-computing/

[92] AMD Corperation. SeaMicro[OL]. [2017-01-20]. http://www.seamicro.com/

[93] HP Corperation. Moonshot system: The world’s first software define server[OL]. [2017-01-20]. http://h10032.www1.hp.com/ctg/Manual/c03728406.pdf

[94] Intel Corperation. Intel?Rack Scale Design[OL]. [2017-01-20]. http://www.intel.com/content/www/us/en/architecture-and-technology/rack-scale-design-overview.html

[95] University of California, Berkeley. NetSys Projects[OL]. [2017-01-20]. http://netsys.cs.berkeley.edu/projects/

[96] University of Cambridge. Opera Projects[OL]. [2017-01-21]. https://www.cl.cam.ac.uk/research/srg/opera/projects/