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

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

1(中國科學院軟件研究所基礎軟件中心 北京 100190)

2(中國科學院大學 北京 100049)

3(帝國理工大學計算學院 倫敦 SW72AZ)

(chunliang@nfs.iscas.ac.cn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

上述10個研究問題涵蓋了集群調(diào)度研究工作的主要調(diào)度考慮.通過分析上述問題可以對調(diào)度結(jié)構(gòu)的變化進行描述和解釋.當然，調(diào)度研究工作還涉及除以上所述研究問題之外的內(nèi)容，例如定價問題、設備可用性問題、硬件的故障預測等.這些問題由于與調(diào)度結(jié)構(gòu)變化的關聯(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個重要調(diào)度問題如表1所示.具體到每一種結(jié)構(gòu)中的論文與研究問題的對應情況將在各小節(jié)分別列出(集中結(jié)構(gòu)、雙層結(jié)構(gòu)、分布式結(jié)構(gòu)、混合結(jié)構(gòu)分別見表2～5.所涉研究問題的多寡與論文的學術價值沒有嚴格的對等關系).從表1還可以獲得關于4種調(diào)度結(jié)構(gòu)的宏觀認知：集中結(jié)構(gòu)與雙層結(jié)構(gòu)考慮更多的本地性、公平性等全局問題;分布式結(jié)構(gòu)研究考慮了更多的可擴展性以及延遲敏感任務;混合結(jié)構(gòu)研究仍處于結(jié)構(gòu)探索階段.

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

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

在以上背景下，大數(shù)據(jù)計算平臺開始內(nèi)置集中結(jié)構(gòu)調(diào)度器.最具有代表性的是Hadoop1.X版本使用的集中結(jié)構(gòu)調(diào)度器：全部客戶的所有作業(yè)使用唯一提交入口，未獲得執(zhí)行的作業(yè)和任務暫存在隊列中；調(diào)度器統(tǒng)一收集作業(yè)執(zhí)行、計算節(jié)點狀態(tài)等信息并進行作業(yè)狀態(tài)管理;集群資源的管理和決策也都在同一節(jié)點上進行.在該調(diào)度結(jié)構(gòu)中，作業(yè)決策和資源管理2個部分都不具備并行的可擴展性，只能通過在模塊內(nèi)部增加或修改代碼的方式進行調(diào)度邏輯的擴展或調(diào)整.在集中結(jié)構(gòu)的調(diào)度研究中，計算節(jié)點的資源通常被統(tǒng)一抽象成固定大小的資源槽(slot).相比HoD環(huán)境使用虛擬子集群的方式，資源槽更加細粒度、易操控.大數(shù)據(jù)環(huán)境的另一個主要計算平臺，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]等.

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

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

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

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

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

Table 2 Scheduling Research Concerns Status in Centralised Scheduling Structure表2 調(diào)度問題統(tǒng)計-所選集中調(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)各任務的依賴關系.作業(yè)內(nèi)各任務之間最基本的一種依賴關系是任務并行性，即單個數(shù)據(jù)計算作業(yè)完成當且僅當其中的所有計算任務全部完成[35].任務并行性限制導致任何緩慢任務都會為作業(yè)帶來延遲.在集中調(diào)度結(jié)構(gòu)中緩解該問題的一種方法是主動縮小任務粒度.Ousterhout等人[45]提出按照輸入數(shù)據(jù)大小切分任務的方法，通過縮小數(shù)據(jù)塊粒度形成大量同構(gòu)的子任務.該方法不僅可以緩解因任務并行性引起的額外作業(yè)延時，也可以緩解異構(gòu)負載中長任務阻塞資源隊列的問題.Ramakrishnan等人[41]則針對MapReduce模型中Reduce關鍵詞計算量不一致導致的并發(fā)延遲問題，提出了Reducer關鍵詞切分技術.

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

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

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

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

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

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

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

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

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

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

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

Hindman等人[65]率先提出了基于雙層調(diào)度結(jié)構(gòu)的Mesos調(diào)度平臺.Mesos清楚地將調(diào)度結(jié)構(gòu)分為2層，Mesos資源管理層負責集群資源的決策和抽象，并以資源配給為單位分配給各平臺;之后由各個平臺獨立在資源配給范圍內(nèi)進行任務的分配.各平臺內(nèi)原本的調(diào)度器實際保留了作業(yè)管理職責，可以在獲得的配給資源范圍內(nèi)調(diào)整任務執(zhí)行.因為Hadoop，Spark，MPI等計算平臺的良好支持，Mesos在一段時間內(nèi)是多平臺環(huán)境資源調(diào)度的最好選擇.Hadoop繼而也在其2.0以及以后版本內(nèi)置了雙層調(diào)度方法Yarn[64].雖然Mesos和Yarn的論文都發(fā)表于2013年，但是在業(yè)界的應用分別始于2011—2012年.2011年前者的項目從閉源變?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出于對自身負載規(guī)模的考慮以及不滿足于Mesos與Yarn的執(zhí)行效率，提出了雙層結(jié)構(gòu)的調(diào)度方法Corona[66].Corona為了改進作業(yè)調(diào)度延遲，以推送請求的通訊方式替代了常用的心跳匯總方式;因而降低了作業(yè)調(diào)度的必要延遲但是同時降低了結(jié)構(gòu)自身的可擴展性.

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

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

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

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

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

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

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

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

③資源異構(gòu)性問題.相對于集中結(jié)構(gòu)，雙層結(jié)構(gòu)中對資源異構(gòu)性問題(同種資源之間的差異)的考慮顯著減少,如表3所示.根據(jù)Ousterhout等人[78]的研究，考慮多資源時不同資源的利用率和分配對集群調(diào)度的影響是不同的，而CPU是影響最大的因素.因而多資源的異構(gòu)與單資源不同不能僅考慮能力差異，還需考慮其對不同作業(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)都使用了不可擴展的集群資源分配模塊，因此二者公有了相關設計局限，如3.2節(jié)所述.主要體現(xiàn)在作業(yè)延遲和可擴展性2個方面.

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

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

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

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

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

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

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

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

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

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

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

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

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

③ 兼容性問題.除以上局限性問題之外，兼容性是分布式調(diào)度目前不能得到廣泛推廣而主要適用于特定集群的重要原因之一.分布式調(diào)度結(jié)構(gòu)不能直接繼承或者遷移使用集中結(jié)構(gòu)或雙層結(jié)構(gòu)的大多數(shù)研究成果，其原因是后者通常假設全局資源信息是天然具備的、且并不考慮不同調(diào)度器之間的資源分配沖突.更為重要的是，分布式調(diào)度結(jié)構(gòu)的部署意味著整體大數(shù)據(jù)集群系統(tǒng)的改變，包括數(shù)據(jù)處理代碼的重寫.而它不擅于進行全局考量的天然缺點又限制了大數(shù)據(jù)集群對該調(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)代表了在同一個集群調(diào)度方法中部署不同類型的集群資源分配模塊;使用不可擴展的集中資源分配模塊進行高準確度全局調(diào)度的同時，使用可擴展的資源分配模塊進行低延遲調(diào)度.混合調(diào)度結(jié)構(gòu)是目前集群調(diào)度的前沿探索，旨在尋找最適合未來復雜集群環(huán)境的調(diào)度結(jié)構(gòu).相關工作主要出現(xiàn)在2014年之后，目前在實際集群中部署運行較罕見，對該結(jié)構(gòu)的研究探索仍處于起步階段.混合結(jié)構(gòu)的誕生基于研究者對未來大數(shù)據(jù)集群工作負載的預期，即一定是交互與非交互作業(yè)混雜的.交互作業(yè)需要最小化調(diào)度延遲而非交互作業(yè)需要精確資源放置，這種場景通過其他調(diào)度結(jié)構(gòu)不易處理.如3.3節(jié)所述，分布式調(diào)度結(jié)構(gòu)具備不可替代的低延遲以及高可擴展優(yōu)勢.然而分布式調(diào)度由于缺乏全局控制機制也難以應對需要特殊調(diào)度需求以及高調(diào)度準確度的場景.分布式調(diào)度結(jié)構(gòu)的低延遲特性主要歸功于其各自獨立工作且可并行擴展的資源分配模塊.雖然在這些模塊之間建立協(xié)同機制可以幫助提高分布式調(diào)度結(jié)構(gòu)的準確度，但同時也會增加其決策成本.

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

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

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

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

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

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

Table 5 Scheduling Research Concerns Status in Hybrid Scheduling Structure表5 調(diào)度問題統(tǒng)計-所選混合調(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)點.該結(jié)構(gòu)的可擴展性取決于集中調(diào)度器的使用頻率和使用方式.2種調(diào)度器協(xié)同工作時，混合結(jié)構(gòu)的可擴展性介于集中結(jié)構(gòu)和分布式結(jié)構(gòu)之間，受限于集中調(diào)度器的使用頻率和決策邏輯；完全運行交互作業(yè)時，所有作業(yè)都通過分布式調(diào)度器提交，混合調(diào)度結(jié)構(gòu)的調(diào)度方法等同于分布式結(jié)構(gòu)，具備良好的可擴展性；當所有作業(yè)都不通過分布式調(diào)度器提交時，混合調(diào)去結(jié)構(gòu)等同于集中(或雙層)調(diào)度結(jié)構(gòu).同時以集中調(diào)度器作為中心，全局資源信息可以向分布式調(diào)度器進行廣播，以便于提高調(diào)度精確度.Delgado等人[88]提出了通過集中調(diào)度器向分布式調(diào)度器主動推送延遲任務信息以改進分布式調(diào)度延遲的方法.

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

[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]. 計算機研究與發(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)

(王元卓, 靳小龍, 程學旗. 網(wǎng)絡大數(shù)據(jù): 現(xiàn)狀與展望[J]. 計算機學報, 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)

(陳康, 鄭緯民. 云計算: 系統(tǒng)實例與研究現(xiàn)狀[J]. 軟件學報, 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)

(王強, 李雄飛, 王婧. 云計算中的數(shù)據(jù)放置與任務調(diào)度算法[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平臺下的調(diào)度算法及混合調(diào)度策略[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]. 計算機研究與發(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)云計算體系結(jié)構(gòu)及其多資源聯(lián)合公平分配策略[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/