基于累計工作量的在線大數據分析作業調度算法

李葉飛 徐超 許道強 鄒云峰 張曉達 錢柱中

摘 要：針對Hadoop和Spark等大數據分析系統中無先驗知識任務的高效執行問題，設計了基于累計工作量（CRW）的任務調度器CRWScheduler。該調度器根據CRW將任務在低權重隊列與高權重隊列間切換;在為作業分配資源時，同時考慮到作業所在的隊列和其瞬時占用資源量，無需作業先驗知識即顯著提升系統性能。基于Apache Hadoop YARN實現了CRWScheduler原型，在28個節點的基準測試集群上的實驗表明，與YARN的公平調度機制相比，作業流時間（JFT）平均降低21%，其中95百分位的作業流時間（JFT）最多降低了35%，并且在與任務級調度程序協作時可獲得進一步的性能提升。

關鍵詞：數據分析系統;作業流時間;公平性;饑餓避免

中圖分類號：?TP316.4

文獻標志碼：A

Online task scheduling algorithm for big data analytics based on cumulative running work

LI Yefei1， XU Chao2， XU Daoqiang3， ZOU Yunfeng2， ZHANG Xiaoda1， QIAN Zhuzhong1

1.Department of Computer Science and Technology， Nanjing University， Nanjing Jiangsu 210023， China ;

2.Electric Power Research Institute， State Grid Jiangsu Electric Power Company Limited， Nanjing Jiangsu 210000， China ;

3.State Grid Jiangsu Electric Power Company Limited， Nanjing Jiangsu 210000， China

Abstract：?A Cumulative Running Work （CRW） based task scheduler CRWScheduler was proposed to effectively process tasks without any prior knowledge for big data analytics platform like Hadoop and Spark. The running job was moved from a low-weight queue to a high-weight one based on CRW. When resources were allocated to a job， both the queue of the job and the instantaneous resource utilization of the job were considered， significantly improving the overall system performance without prior knowledge. The prototype of CRWScheduler was implemented based on Apache Hadoop YARN. Experimental results on 28-node benchmark testing cluster show that CRWScheduler reduces average Job Flow Time （JFT） by 21% and decreases JFT of 95th percentile by up to 35% compared with YARN fair scheduler. Further improvements can be obtained when CRWScheduler cooperates with task-level schedulers.

Key words：?data analytics system; Job Flow Time （JFT）; fairness; starvation-free

0 引言

在現代主流分布式大數據分析系統（例如Apache Hadoop、Apache Spark、Apache Tez）中，作業是由一系列任務構成的，可表示為有向無環圖（Directed Acyclic Graph， DAG），其中每個頂點表示一個任務，邊表示任務之間輸入與輸出的依賴關系。為提升資源利用率，作業之間會共享集群資源[1-3]。用戶級公平性確保所有用戶都能夠在共享集群中獲得資源[4-10]。然而，從用戶的角度看，除了可以獲得的資源量，如何高效地利用已分配的資源來快速完成其作業同樣是一個重要問題。作業完成效率一般用作業流時間（Job Flow Time， JFT）來刻畫，其值定義為作業完成時間減去作業提交時間。本文針對分布式大數據分析系統的作業調度問題，研究任務調度算法，在確保用戶之間公平性以及無饑餓的前提下，加速DAG作業的完成。

即使是在離線場景（offline setting）中，最小化平均作業流時間的DAG調度問題都是NP難的。而Hadoop和Spark中的默認集群調度機制將資源劃分為固定大小的資源塊（Slots），例如〈2個CPU內核， 1GB內存〉，并將資源塊提供給作業。在此過程中調度器并未考慮作業的執行進展情況，使得作業完成時間變長[4，10-11]。為此，Carbyne[12]和Graphene[13]等優化的作業調度機制將不同的任務分類以提高集群整體的吞吐率，同時根據初始的作業量（所有任務正在處理的時間總和）以短作業優先（Shortest Job First， SJF）[14]的方式調度DAG作業，從而減少了平均作業流時間。一方面，短作業優先的策略會導致長作業饑餓，損害作業級的公平性;另一方面，這種調度機制預先假設已知作業的全部先驗知識，如：DAG的結構和任務處理時間。對于一些重復出現的作業確實可以在當前集群中預測其特征[15-17]，但在一般的情況下，由于集群的動態性（任務中斷、推測執行）等難以預先獲取完全的作業信息，從而限制了這些調度機制的實用性[2-3]。

LAS （Least-Attained Service）[17]是一種基于作業提交后已展現的運行信息來進行調度的策略，由于它不需要提前獲取完全信息，具有更強的實用性;并且，當作業的工作量服從重尾分布時，LAS能近似最優策略的性能[3]。但傳統LAS策略僅考慮了計算量一個維度，而大數據處理作業對CPU與內存的消耗具有同等重要的地位。為此，本文基于LAS思想，提出了支持多類型資源（CPU、內存等）的非饑餓集群調度機制CRWScheduler。CRWScheduler基于主資源[4]的累計運行工作量（Cumulative Running Work， CRW）來預測作業的總工作量，從而無需提前獲取作業特征，即可減少平均作業流時間。

通過使用權重多隊列架構，CRWScheduler將基于CRW的啟發式算法（有利于重尾分布）和先進先出（First In First Out， FIFO）思想（有利于輕尾分布）組合起來。每個作業基于其CRW會被分配到特定的隊列中， CRW較小的作業隊列被設置較低的權重;而在分配資源時，CRWScheduler首先按照“分數”將隊列進行排序，然后依據分數遞增的順序分配資源。分數的計算同時依賴隊列中作業當前占用資源的情況和隊列的權重。一方面，當前不占用資源的隊列其分數為0，有最高優先級獲得新資源，又由于每個隊列中作業為先進先出，進而避免了作業出現饑餓的情況。另一方面，由于CRW較小的隊列的權重較小，相比有相同資源的隊列有更高的優先級獲得新資源。這樣做模擬了短作業優先的策略，降低了平均作業流時間。有別于PIAS （Practical Information-Agnostic flow Scheduling）[18]和Aalo[19-20]等其他基于LAS策略的網絡流調度機制，CRWScheduler避免了PIAS等調度機制導致作業饑餓的問題，也克服了Aalo等機制需要無限分割資源，但并不能實際滿足DAG作業的最小資源需求的缺陷。

本文基于Apache Hadoop YARN （Yet Another Resource Negotiator）[21]實現了CRWScheduler，并將系統部署在28個節點的集群中。通過全面的工作負載測試結果顯示，與公平調度相比，CRWScheduler的平均作業流時間縮短了10%～35%，而其中95百分位的作業流時間縮短了21%～35%。

1 研究現狀

大數據分析系統

目前的數據分析系統大致可分為資源管理和計算框架兩類。資源管理平臺，如Apache YARN[21]和Apache Mesos[7]。從物理機器抽象出資源，使彈性計算框架易于構建和有效運行。研究人員和從業人員已經開發出了多種易于編程的框架，如Apache Tez[1]、MapReduce[2]、Dryad[3]和Apache Spark[3]。這些框架通常將作業看成DAG，從而使得它們可以表達對資源的偏好和約束。吳信東等[22]比較了MapReduce和Spark在不同場景中的性能。

大數據分析的任務調度

延遲調度[10]和Quincy[23]通過調度單個任務以更接近于其輸入數據，從而提高單個任務的數據本地性。ShuffleWatcher[24]提高了階段（stage）之間的shuffle局部性;Tetris[15]確保多臺機器能更好地打包任務;Corral[16]同時考慮了結合數據和計算位置的優化。這些工作集中于任務調度級別，同時CRWScheduler能夠更好地與其協作。

對于調度一個單獨的作業，列表調度和工作竊取調度[25]是常見的異步優化方案，比如對于多個DAG作業共享一個并行多主機集群，LAPS （Latest Arrival Processor Sharing）[26]有良好的性能，然而并沒有得到應用。文獻[13]中證明了短作業優先（SJF）算法與LAPS有相近的性能，并且不涉及參數。王習特等[27]提出了基于序列的任務調度策略SEQ（SEQuence-based task scheduling strategy）來最大化集群運行作業的收益。本文驗證了CRWScheduler能夠在無先驗知識的情況下達到近似于SJF的性能。

2 DAG作業調度

首先形式化地定義DAG作業調度問題以及一些相關的概念，然后量化分析實際生產中的工作負載，最后用一個例子展示基于CRW的調度機制所獲得的性能提升。

2.1 問題定義

本節定義DAG作業調度問題，之后給出問題的計算復雜度，最后形式化地定義累計運行工作量（CRW）。

假設一個用戶在時刻0提交了若干個作業J，每個作業包含若干個任務，crij表示第i個作業的第j個任務對于資源r的需求量。假設dij表示相應任務的處理時間，且dij并未考慮持續時間內位置環境的影響。Dij表示表示作業i中任務j的依賴任務集合，只有當Dij中的任務全部完成，作業i中任務j才能被調度執行。整個集群包含機器的集合為P，每臺機器s包含資源r的容量為prs。假設Aij代表作業i中任務j分配的機器，Bij表示任務分配發生的時間，Itij指示在時刻t，作業i的任務j是否在集群上運行。

定義1? 作業i的流時間為其到達時間與其最后一個任務完成時間的間隔時間，即：max j∈i {t>0 | Itij>0}。

約束條件：

1）在任何時刻，一臺機器上的所有任務使用的資源總和不得超過當前機器相應資源的容量：

r，t，s∈P，∑ Aij=s crij·ltij≤Prs

（1）

2）調度器不能在一個任務還未完成前中斷任務：

Itij= 1，?? Bij≤t≤Bij+dij0， 其他

（2）

3）一個任務只有等到其所依賴的任務全部執行完才能被調度執行：

Bij≥max k∈Dij {Bik+dik}

（3）

目標函數：最小化平均作業流時間（即最小化作業流時間之和）：

∑ i∈J max j∈i {t>0 | Itij>0}

（4）

定理1? 滿足上述目標（4）和約束條件（1）～（3）的DAG作業調度問題為NP難問題。

證明? 通過證明該問題的一個特殊情況是NP難來證明該問題的計算復雜性。對于所有作業中的任務，假設Dij為空集且任務的執行時間為1;假設在0時刻共有 | P | 個箱子。若能夠將所有任務打包起來所需的箱子數小于 | P | ，那么所有作業的完成時間為1;否則在1時刻開啟另外 | P | 個箱子，來判斷是否能將剩余的任務打包。因為判斷最少的箱子數是NP難的[20]，故DAG作業調度問題是NP難的。

注意到即使沒有任務位置偏好，DAG作業調度問題仍然為NP難。鑒于NP難問題的復雜度[28]，本文在考慮非饑餓的同時尋找有效的啟發式方法以最小化平均流時間。

為了論述方便，預先定義以下概念。

定義2? 作業i的總工作量（Original Work）是指對于特定資源，任務需求與任務處理時間的乘積與集群資源容量的最大比率，即：

R（i）=max r? 1 ∑ s∈P prs ∑ j∈i crij·dij

定義3? 作業i在t時刻的當前運行任務數為：

CR（i，t）=∑ j∈i Itij

定義4? 作業i在t時刻的累計運行工作量（Cumulative Running Work， CRW）是指對于每種資源，該作業已經完成的任務和正在運行任務中對該資源的需求量和可用量比值的最大值，即：

RW（i，τ）=max r? 1 ∑ s∈P prs ∑ j∈i ∑ t≤τ crij·Irij

2.2 工作負載分析

如表1所示，Yahoo！采集了在2500個節點的集群中的作業所使用資源（以Slot數量計算）的情況。作業的資源使用情況在實際生產中滿足重尾分布[29]：即大部分的作業都屬于輕量級，它們只占用少量的集群資源;小部分繁重的作業占據著大部分的集群資源。

在重尾分布中，一個作業已經完成的程度將是其實際工作的一個好的預測值[13]。在本文所討論的場景中，CRW很好地近似了作業總工作量，因此基于CRW的調度機制（CRW較小的作業優先）在實際負載工作中近似于短作業優先（SJF）。

2.3 典型實例分析

圖1以具體的例子顯示了現有調度器的缺陷：公平調度器（fair scheduler）總是將資源分配給當前資源占有量最少的作業[30];容量調度器（capacity scheduler）根據作業提交時間分配資源[31];SJF[14]能夠實現最優的調度，但是它依賴于作業提交時完全的先驗的作業特性。

假設用戶在時刻0提交作業A和B，在時刻1提交作業C。每個任務需要1個單位的處理時間，每個任務有不同的資源需求。假設所有資源的總量為1。作業流時間定義為從作業的提交時間到作業最后一個任務完成的時間間隔。基于固定資 源塊（每個slot的資源為〈0.5， 0.5〉）的公平調度器以實時最大 最小公平（max-min fairness）的方式為作業分配資源[30]。公平調度器作用下的平均作業流時間為17/3，而容量調度器導致平均流時間也為17/3。考慮已知DAG結構和細粒度任務需求，SJF調度策略將會根據其總工作量逆序調用作業，使得平均作業流時間為5。基于CRW的調度器將資源分配給具有最小累計運行工作量的作業。在時刻1，基于CRW的調度器將為作業C分配2個任務，而不是1個，因為作業A、B、C在時刻1的CRW分別為0.4、0.5、0。基于CRW的調度器可使得平均作業流時間為16/3。在這個例子中，基于CRW的調度器不需要先驗的作業特性，但能夠近似最優的調度器，實現更低的平均作業流時間。

基于此，本文試圖根據作業的累計運行工作量設計在線的動態調度器來分配資源以保證無饑餓的同時減少平均作業流時間。

3 基于CRW的作業調度機制

如圖2所示，在分配資源時，用戶級調度機制根據用戶在集群中的份額排序。公平調度機制為最小（內存）份額的用戶提供資源[10]，然而主資源公平的調度機制（Dominate Resource Fairness， DRF）將其擴展為考慮多類資源（如CPU、內存）[4]。任務調度器嘗試提高任務的數據本地性[10]，或者最小化集群資源碎片[15]，或者根據任務依賴約束進行分類[12]。CRWScheduler位于用戶之間的調度和任務調度之間，將每個用戶內部的作業作為輸入，試圖縮短平均作業流時間。

3.1 權重多隊列框架

在多個DAG作業共享多臺機器的場景中，作業到達和離開的時間都是在線的，難以獲得完整的作業信息，因此最短作業優先原則實際上是無法實施的。因此，依據2.2節分析和定義4，累計工作量是作業總工作量的良好的預測值，一個直觀的啟發式方法是基于累計運行工作量的思想近似最短作業優先。

在t時刻，為作業i賦予分數CR（i， t） * CRW（i， t），按照分數非遞減的方式分配資源。這樣做的目的是在保證饑餓不發生的前提下減少平均作業流時間：因為饑餓作業的分數為0（因為CR（i， t）=0），在分配資源時具有最高的優先級;并且，較低CRW的作業有較高的優先級，又因為CRW可以很好地評估一個作業的總工作量，所以這個啟發式方法有助于最小化平均作業流時間。

然而，對于滿足輕尾的作業分布，上述啟發式算法實際上就退化成了作業之間公平共享資源，這并不能最小化平均作業流時間。例如，兩個相同的作業等待調度執行，其中一個作業被選中執行，這個作業的分數提高了，將導致另一個作業被調度執行，因此，兩個作業的完成時間都變成了最優時間的兩倍。而在這種情況下，FIFO調度策略能最小化平均完成時間。因此，本文算法通過權重多隊列框架將基于CRW的機制和FIFO策略組合起來，具體介紹見3.2節。

3.2 DAG作業調度CRWScheduler

本文通過將基于CRW的啟發式思想和FIFO的啟發式思想綜合起來考慮，引入權重多隊列框架（Weighted Multi-Queue Framework，WMQF）。CRWScheduler基于運行中作業的CRW值將其劃分到相應的隊列Q1，Q2，…，Qn中去。在隊列Qi中的作業的CRW值屬于[Qi-1.th，Qi.th]，其中Qi.th是隊列Qi的閾值同時滿足Qi+1.th>Qi.th;且 Q0.th=0。CRWScheduler從Q1到Qn以遞減的方式設置隊列權重Qi.weight。一個作業的CRW值隨著其任務在集群中執行單調遞增，一旦其CRW值超出所在隊列的閾值，當前作業將從當前隊列轉移到下一個隊列。

CRWScheduler實時記錄每個作業的CRW值，同時在必要時調整作業所在的隊列。當一個作業周期性地向集群報告其心跳時，將調用UPDATECRW：為作業分配新的slot（Cn）以執行其任務，同時返回完成后的slot（Cr）給集群調度器。當作業更新后的CRW值超出隊列的閾值時，該作業將會轉移到下一個隊列（代碼第7）行）。

Qr.score=Qr.weight· 1 ?| Qr | ??∑ i∈Qr CR（i，τ）

（5）

算法1

DAG作業調度CRWScheduler。

程序前

procedure UPDATECRW（JOB i， Cn， Cr）

//在作業向集群報告其心跳時調用

1）

R ←當前累計運行資源向量

2）

k←作業i的隊列index

3）

在新分配的slot Cn中啟動任務

4）

fo r c∈Cr∪Cn do：

5）

R +=c· r? （time.Now-c.lastUpdateTime）

6）

if? max（ R ）>Qk..th then

7）

將作業i從隊列Qk轉移到Qk+1

procedure CRWSCHEDULE（NODE n）

//在機器向集群報告其心跳時調用

8）

wh ile n has free resources do

9）

decide user u to offer resources to

10）

jobList=SCOREDLIST（u）

11）

offer resources to jobList

procedure SCOREDLIST（USER u）

//將作業排序

12）

n←用戶u所在的隊列數

13）

fo r i=1 to n do：

14）

使用式（5）計算Qi.score

15）

根據score對隊列進行排序

16）

jlist←連接有序隊列中的作業

17）

return jlist

程序后

CRWScheduler維持了用戶級別的公平性（代碼第9）行），并在每個用戶內部調度作業。當一臺機器周期性地報告其心跳時，CRWSchduler被調用，同時將重新分配資源。通過設置權重隨隊列索引遞減，CRWScheduler使用式（5）計算每個隊列的分數（代碼第14）行），其中∑ i∈ Q r CR（i，τ）表示的是隊列Qr中當前所有作業正在運行的任務數量之和， | Qr | 表示的是隊列Qr中當前的作業的數量。也就是說，Qr.score為隊列中當前運行任務的平均值與隊列權重的乘積。按照Qr.score非遞減的順序排序可使得CRWSchduler為重尾作業分布保留了基于CRW的啟發式特性：因為有較低CRW的作業所在隊列的權重較大，導致其作業排在jlist前面;與此同時，也保證了FIFO思想在輕尾作業分布中的優勢，即在同一隊列中的作業是FIFO的，從而使CRWScheduler有效地防止了隊列和作業中饑餓現象的發生，同時縮短了平均作業流時間。

3.3 CRWScheduler的實現

Tez[1]、Hadoop[21]和Spark[32]等經典的數據分析系統將集群功能劃分為多個角色，包括集群管理器（resource manager）、節點管理器（node manager）與作業管理器（job manager），圖3中帶“+”的部分為CRWScheduler在已有架構上的修改與擴展。為了保證系統的擴展性、性能以及可靠性，類YARN的數據分析系統[10]將集群功能劃分為若干個不同的守護進程。本文通過如下修改將CRWScheduler整合到Apach Hadoop YARN框架（Hadoop 2.6）中。集群管理器為每個用戶管理多個隊列框架，同時在資源分配中實現CRWScheduler。節點管理器進行slot分配的同時追蹤slot的運行時間。作業管理器負責增加自身的CRW值，并在必要時使用UPDATECRW調整其所在的隊列。

對Apache Hadoop YARN框架所做的修改并不影響原有調度器的可擴展性，因為CRWScheduler在分配資源時將隊列排序，而原有的調度器是直接對作業進行排序。CRWScheduler在作業更新時增加了累計運行工作計算，這是一個工作量適中的操作，同時實驗結果也顯示這一花銷并不會影響系統的性能。

4 實驗評估

4.1 實驗配置

本文在28個節點的集群中運用各種類型的工作負載評估CRWScheduler，并且以仿真的方式在更大的集群中評測CRWScheduler的開銷。

集群中的每個節點采用2核CPU，4GB內存，1Gb/s NIC網卡，運行Ubuntu14.04系統。

對比方法：將CRWScheduler與Hadoop 2.6中實現的調度算法進行對比。為了與公平調度器[10]和DRF調度器[4]相比較，CRWScheduler替換了這些調度機制中的作業調度組件，同時保留了用戶之間的調度組件。同樣將CRWScheduler與容量調度器[4]相比較。本文利用延遲調度機制[10]作為默認的任務調度機制。

性能指標：主要關注于提升作業流時間（平均作業流時間或者絕大多數作業流時間）和作業吞吐量。

測試負載：使用Apach Spark來生成運行在YARN上的DAG作業。評估中使用的作業來源于如下數據分析應用：WordCount、TPC-H基準、迭代機器學習以及PageRank。如表2所示，對于每一類工作負載，數據集大小仿照真實生產環境的集群按比例縮放（Yahoo！[8]和Facebook[10]）。對于作業的分布，設置46%、40%和14%分別為小型、中型、大型的作業，這與實際應用中作業的分布相似[10]。

4.2 實驗結果

本文首先討論CRWScheduler在多用戶環境下相比現有調度策略在性能上的提升，同時集中分析對于單用戶作用吞吐率的提升效果，之后將隔離提交作業以模擬輕尾工作負載，最后評估經過修改的架構與初始架構相比所產生的額外開銷。

1）多用戶環境實驗。假設有7個用戶，為每個用戶生成300個作業。圖4顯示了當CRWScheduler與公平調度器協作（CRWScheduler-fair）以及與DRF調度器協作（CRWScheduler-DRF）時的性能提升，所有的指標均按公平調度標準化。 圖4（a）顯示，與fair scheduler相比，CRWScheduler-fair處理小型、中型、大型作業的平均JFT分別減少了14、21和10個百分點，對于所有的作業而言，JFT平均減少了16個百分點;與DRF調度器相比，CRWScheduler-DRF處理小型、中型、大型作業的平均JFT分別減少了10、22以及10個百分點，對于所有的作業而言，JFT平均減少15個百分點。圖4（b）描述了95百分位的作業流時間的提升效果。

2）單用戶環境實驗。為了突出在資源競爭激勵的環境下CRWSheduler對性能的提升，設置的實驗環境為：單用戶每隔20s提交一次作業。對每種調度策略進行1h的實驗，并分別統計其吞吐量。如表3所示，CRW公平調度策略相于單純的公平調度策略吞吐量提升了32%，CRWSheduler-DRF調度策略相比DRF吞吐量提升了45%。

3）輕尾作業分布。實驗為每個尺寸的作業生成100個作業，并且分開提交到服務器集群。容量調度程序在這些輕尾作業分布中進行最優調度。圖5顯示，CRWScheduler的調度效果近似于容量調度器，因為CRWSchduler能保持作業在相同的隊列中進行FIFO調度，所以優于公平調度。

4）額外開銷：使用300節點集群進行仿真實驗，每個機架有30臺服務器，同時生成10000個作業，計算從節點中作業處理和更新的平均時間。表4顯示，對于每個作業心跳的額外開銷在0.05ms以內，這對于集群管理者來說可以忽略不計。在節點心跳中，公平調度器直接對運行中的作業排序，而CRWScheduler首先對隊列進行排序，之后通過合并有序的隊列得到有序的作業列表，從而使得CRWScheduler在資源分配時能達到更短的響應時間。

表格中的“事件平均處理時間”是算法的開銷，而“更短的響應時間”是指之前實驗中作業流時間這個指標，確認表述正確

5 結語

目前的DAG作業調度機制都需要預先獲得完整的作業信息，但在大量實際應用中難以實現。為此，本文提出了累計運行工作量（CRW），以估算作業總工作量，并設計了CRWScheduler調度器。它基于作業的CRW值將當前運行的作業劃分成多個隊列，同時考慮作業瞬時資源占用率以及不同的隊列權重，不僅能縮短平均作業流時間，也抑制了“饑餓”現象。而通過保持作業在每個隊列中的FIFO順序，CRWSheduler還提高了輕尾作業分布的性能。本文基于Apache Hadoop YARN實現了CRWSchduler原型系統，通過部署在28個節點的集群中進行多類型數據分析應用的測試。實驗結果顯示，相比YARN的公平調度機制，CRWScheduler將平均作業流時間縮短21%，而95百分位的作業流時間縮短35%。然而，當前任務執行時的資源使用是隧道化的，同一時刻會同時使用多種資源。多任務同時運行在同一物理機上時會造成不可預知的資源競爭，從而難以對任務執行時間建模。元任務（monotask）是將任務劃分成更小的粒度，每個元任務只消耗一種資源（磁盤、網絡和內存等）。通過將每個任務劃分成元任務，能夠更好地對任務和作業的執行時間建模。下一步擬研究針對元任務的調度機制，以進一步提高集群的資源利用率和作業性能。

參考文獻

[1]?Apache Software Foundation. Apache Tez [EB/OL]. [2017-12-21]. http：//tez.apache.org/.

[2]?DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters [C]// Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation. Berkeley， CA： USENIX Association， 2004， 6： 10-10.

[3]?ISARD M， BUDIU M， YU Y， et al. Dryad： distributed data-parallel programs from sequential building blocks [C]// Proceedings of the 2nd ACM Special Interest Groups in Operating Systems （SIGOPS）/European Conference on Computer Systems. New York： ACM， 2007： 59-72.

[4]?ZAHARIA M， CHOWDHURY M， DAS T， et al. Resilient distributed datasets： a fault-tolerant abstraction for in-memory cluster computing [C]// Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation. Berkeley， CA： USENIX Association， 2012： 15-28.

[5]?GHODSI A， ZAHARIA M， HINDMAN B， et al. Dominant resource fairness： Fair allocation of multiple resource types [C]// Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation. Berkeley， CA： USENIX Association， 2011： 323-336.

[6]?GHODSI A， ZAHARIA M， SHENKER S， et al. Choosy： max-min fair sharing for datacenter jobs with constraints [C]// Proceedings of the 8th ACM European Conference on Computer Systems. New York： ACM， 2013： 365-378.

[7]?HINDMAN B， KONWINSKI A， ZAHARIA M， et al. Mesos： A platform for fine-grained resource sharing in the data center [C]// Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation. Berkeley， CA： USENIX Association， 2011： 295-308.

[8] ?VAVILAPALLI V K， MURTHY A C， DOUGLAS C， et al. Apache hadoop YARN： yet another resource negotiator [C]// Proceedings of the 4th Annual Symposium on Cloud Computing. New York： ACM， 2013： 1-16.

[9]?WANG W， LIANG B， LI B. Multi-resource fair allocation in heterogeneous cloud computing systems [J]. IEEE Transactions on Parallel and Distributed Systems， 2015， 26（10）： 2822-2835.

[10]?ZAHARIA M， BORTHAKUR D， SARMA J S， et al. Delay scheduling： a simple technique for achieving locality and fairness in cluster scheduling [C]// Proceedings of the 5th ACM European Conference on Computer Systems. New York： ACM， 2013： 265-278.

[11]?Apache Software Foundation. Hadoop MapReduce Next Generation — Fair Scheduler [EB/OL]. [2018-10-21]. http：//tinyurl.com/j9vzsl9.

[12]??GRANDL R， CHOWDHURY M， AKELLA A， et al. Altruistic? scheduling in multi-resource clusters [C]// Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation. Berkeley， CA： USENIX Association， 2016： 65-80.

[13]?GRANDL R， KANDULA S， RAO S， et al. Graphene： packing and dependency-aware scheduling for data-parallel clusters [C]// Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation. Berkeley， CA： USENIX Association， 2016： 81-97.

[14]?AGRAWAL K， LI J， LU K， et al. Scheduling parallel DAG jobs online to minimize average flow time [C]// Proceedings of the 27th annual ACM-SIAM Symposium on Discrete algorithms. Philadelphia， PA： Society for Industrial and Applied Mathematics， 2016： 176-189.

[15]?FERGUSON A D， BODIK P， KANDULA S， et al. Jockey： guaranteed job latency in data parallel clusters [C]// Proceedings of the 7th ACM European Conference on Computer Systems. New York： ACM， 2012： 99-112.

[16]?GRANDL R， ANANTHANARAYANAN G， KANDULA S， et al. Multi-resource packing for cluster schedulers [C]// Proceedings of the 2014 ACM Conference on SIGCOMM. New York： ACM， 2014： 455-466.

[17]??JALAPARTI V， BODIK P， MENACHE I， et al. Network-aware ?scheduling for data-parallel jobs： Plan when you can [C]// Proceedings of the 2015 ACM Conference on SIGCOMM. New York： ACM， 2015： 407-420.

[18]?RAI I A， URVOY-KELLER G， BIERSACK E W. Analysis of LAS scheduling for job size distributions with high variance [C]// Proceedings of the 2003 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. New York： ACM， 2003： 218-228.

[19]?BAI W， CHEN L， CHEN K， et al. Information-agnostic flow scheduling for commodity data centers [C]// Proceedings of the 12th USENIX Symposium on Networked Systems Design and Implementation. Berkeley， CA： USENIX Association， 2015： 455-468.

[20]?CHOWDHURY M， STOICA I. Efficient coflow scheduling without prior knowledge[C]// Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. New York： ACM， 2015： 393-406.

[21]?Apache Software Foundation. Apache Hadoop NextGen MapReduce （YARN） [EB/OL]. [2017-12-21]. http：//tinyurl.com/zyy8kbc.

[22]?吳信東，嵇圣硙.MapReduce與Spark用于大數據分析值比較[J].軟件學報，2018，29（6）：1770-1791. （WU X D， JI S W. Comparive study on MapReduce and Spark for bid data analytics [J]. Journal of Software， 2018， 29（6）： 1770-1791.）

[23]?ISARD M， PRABHAKARAN V， CURREY J， et al. Quincy： fair scheduling for distributed computing clusters [C]// Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles. New York： ACM， 2009： 261-276.

[24]?AHMAD F， CHAKRADHAR S， RAGHUNATHAN A， et al. Shufflewatcher： Shuffle-aware scheduling in multi-tenant mapreduce clusters [C]// USENIX Proceedings of 2014 USENIX Annual Technical Conference. Berkeley， CA： USENIX Association， 2014： 1-12.

[25]??BLUMOFE R D， LEISERSON C E. Scheduling multithreaded computations by work stealing [J]. Journal of the ACM. 1999， 46（5）： 720-748.

[26]?EDMONDS J， PRUHS K. Scalably scheduling processes with arbitrary speedup curves [J]. ACM Transactions on Algorithms， 2012， 8（3）： 256-265. [C]// Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms. New York： ACM， 2009： 685-692.

[27]?王習特，申德榮，于戈，等.MapReduce集群中最大收益問題的研究[J].計算機學報，2015，38（1）：109-121. （WANG X T， SHEN D R， YU G， et al. Research on maximum benefit problem in a MapReduce cluster [J]. Chinese Journal of Computers， 2015， 38（1）： 109-121.）

[28]?VAZIRANI V V. Approximation Algorithms [M]. Berlin： Springer， 2003： 74-78.

https：//www.logobook.ru/prod_show.php？object_uid=11146016

[29]?NAIR J， WIERMAN A， ZWART B. The fundamentals of heavy-tails： properties， emergence， and identification [C]// Proceedings of the ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems. New York： ACM， 2013： 387-388.

[30]?WIKIPEDIA. Max-min fairness [EB/OL]. [2017-12-21]. http：//tinyurl.com/krkdmho.

[31]?Apache Software Foundation. Hadoop MapReduce Next Generation — Capacity Scheduler [EB/OL]. [2018-12-01]. http：//tinyurl.com/j739ojm.

[32]?Apache Software Foundation. Apache Spark [EB/OL]. [2018-11-07]. http：//spark.apache.org/.