外文翻譯--云計算中傾斜度感知的任務調度（譯文）

1、中文 中文 7290 字出處： 出處：Li D, Chen Y, Hai R H. Skew-Aware Task Scheduling in Clouds[C]//Service Oriented System Engineering (SOSE), 2013 IEEE 7th International Symposium on. IEEE, 2013: 341-346.2013Skew-Aware Task Scheduling

2、in Clouds云計算中傾斜度感知的任務調度 云計算中傾斜度感知的任務調度李東生，陳宜興，理查德·胡亥國防科技大學，計算機學院，并行與分布式處理國家實驗室，中國國立大學萊佛士商學院，新加坡dsli@nudt.edu.cn摘要：數(shù)據(jù)扭曲是 摘要：數(shù)據(jù)扭曲是 MapReduce 一樣的云系統(tǒng)中慢任務出現(xiàn)的一個重要原因。 一樣的云系統(tǒng)中慢任務出現(xiàn)的一個重要原因。在本文中，我們提出了一個斜感知任務調度（ 在本文中，我們提出了一個斜感

3、知任務調度（SATS）機制針對 ）機制針對 MapReduce 類似系統(tǒng)的迭代應用。該機構利用迭代應用中在相鄰迭代的數(shù)據(jù)分布的相似性， 似系統(tǒng)的迭代應用。該機構利用迭代應用中在相鄰迭代的數(shù)據(jù)分布的相似性，來減少數(shù)據(jù)扭曲造成的落伍的問題。它在當前迭代的任務的執(zhí)行過程中收集數(shù) 來減少數(shù)據(jù)扭曲造成的落伍的問題。它在當前迭代的任務的執(zhí)行過程中收集數(shù)據(jù)的分布信息，并用這些信息來指導下一次迭代時任務的數(shù)據(jù)分割。我們在 據(jù)的分布信息，并用這些信息來指

4、導下一次迭代時任務的數(shù)據(jù)分割。我們在 HaLoop 系統(tǒng)落實機制，在一個集群中部署。實驗結果表明，該機制可以處理 系統(tǒng)落實機制，在一個集群中部署。實驗結果表明，該機制可以處理數(shù)據(jù)扭曲，有效地提高負載平衡。 數(shù)據(jù)扭曲，有效地提高負載平衡。關鍵詞：數(shù)據(jù)扭曲；任務調度；云計算；負載均衡 關鍵詞：數(shù)據(jù)扭曲；任務調度；云計算；負載均衡1、簡介 簡介近年來云計算已經成為一個有前途的技術，而且 MapReduce 是最成功的一個大規(guī)模數(shù)據(jù)密集型云計算

5、的實現(xiàn)平臺[1] - [3]。MapReduce 的使用一個簡單的數(shù)據(jù)并行的編程模型，有兩個基本的操作，即，Map 和 Reduce 操作。用戶可以根據(jù)應用程序的要求自定義 Map 功能和 Reduce 功能。每個 map 任務取一片輸入數(shù)據(jù)，并產生一個用 Map 功能的 key/value 對的集合，這是初步地用 Reduce 功能做 Reduce 任務。這種編程模型很簡單，但功能強大，許多大規(guī)模數(shù)據(jù)處理 應用程序可以由模型來表示。類

6、 MapReduce 的系統(tǒng)可以在云計算中自動調度多個分布在機器中的 Map 和/或 Reduce 任務。作為同步步驟僅存在于 Map 階段和 Reduce 階段之間，任務執(zhí)行在相同的階段具有高平行度，并且因此并發(fā)性和系統(tǒng)的可擴展性可以被高度增強。 Hadoop[4]和它的變體（例如，HaLoop [5]和 Hadoop++ [6]）是典型的類 MapReduce 系統(tǒng)。由于在類 MapReduce 系統(tǒng)中 Map 和 Reduce 階

7、段之間存在同步步驟，在任 一階段慢任務可能減慢整個工作的執(zhí)行。這種慢任務在 Map 或 Reduce 階段叫做落后者。當慢任務出來時，整個工作的執(zhí)行時間會增加，而資源的使用會被 減少。最近，有研究[7]-[8]顯示該數(shù)據(jù)歪斜已經成為了在 Map 或 Reduce 階段出現(xiàn)慢任務的一個主要原因。在許多科學計算和數(shù)據(jù)分析應用中，輸入的數(shù)據(jù)或 中間數(shù)據(jù)的數(shù)據(jù)傾斜可能會導致嚴重的負載不平衡的問題。例如，PageRank [9] 用于大規(guī)模搜索工

8、程是一種典型的執(zhí)行在類 MapReduce 系統(tǒng)上的應用。該PageRank 應用進行鏈接分析——通過反復迭代其周邊鄰居的權重，為在網頁的 鏈接圖中的每個頂點/網頁分配權重（等級）。研究[7]，[8]，[18]表明網頁鏈接圖的度是多傾斜的，一些頂點具有較大度的入邊。由于 MapReducelike 系統(tǒng)[4] 使用隨機哈希算法進行分區(qū)中間數(shù)據(jù)到 Reduce 節(jié)點，節(jié)點代表著計算度較大的任務調度和輸入/輸出緩存，HaLoop 可以顯著減

9、少迭代應用的執(zhí)行時間。提出 的 SATS 機制在 HaLoop 系統(tǒng)中實現(xiàn)，并且其利用了任務在相鄰迭代中的中間數(shù)據(jù)的相似性以提高 Reducer 節(jié)點的負載均衡。 B.MapReduce 類似系統(tǒng)的調度調度是 MapReducelike 系統(tǒng)一個重要的研究課題。在 Hadoop 中有幾個默認的作業(yè)調度機制，例如，F(xiàn)IFO，計算能力調度，公平調度[10]。由于 Hadoop 的調度可能會在異構環(huán)境中導致嚴重的負載不均衡和性能下降，Long

10、est Approxi- mate Time to End（LATE）調度[11]的設計通過修改推測執(zhí)行策略處理了在異構集群中的落后者問題，它可以減少 Hadoop 一半的響應時間。Ganesh Ananthanarayanan 等人[12]對于落后者的問題將原因劃分為三類，包括具有不同的容量和可靠性的設備特性，任務間具有不同帶寬、擁堵和工作量的網絡特性（例如，數(shù)據(jù)扭曲造成的失衡）。他們提出 Mantri[12]，一種監(jiān)視任務和使用進程

11、和資源感知技術精選落后者的機制，包括重啟慢任務，任務 的網絡意識安置和保護有價值任務的輸出。具有實時進度報告，Mantri 在其時間周期的早期檢測落后者，并根據(jù)他們的原因采取適當?shù)男袆?。?shù)據(jù)傾斜是在 MapReduce 類似系統(tǒng)中執(zhí)行的許多應用中的一個普遍現(xiàn)象[7]-[8]，[13]-[15]。YongChul Kwon 等人[7]提出科學分析應用即提取從數(shù)據(jù)集顯示出的顯著計算傾斜的特征。 Jimmy Lin[8]觀察發(fā)生在許多 Map

12、Reduce 工作中的落后者問題，提出它與數(shù)據(jù)集的數(shù)據(jù)偏移是相關的。SkewReduce [7]根據(jù)用戶定義的成本函數(shù)靜態(tài)優(yōu)化數(shù)據(jù)的分配，但它取決于來自用戶的領域知識并被 限制為特定的應用程序。SkewTune [13]是一個針對用戶定義的 MapReduce 程序的自動傾斜緩解機制。當一個節(jié)點變?yōu)榭臻e時，SkewTune 標記任務最大的預期剩余處理時間，主動地重新分配掉隊的任務中未處理的輸入數(shù)據(jù)。LEEN [14]基 于成本模型安排

13、keys 到 reduce 任務中，而 TopCluster [15]構建了所有 reduce 的 keys 的直方圖來鑒定傾斜的 reduce keys?？傮w而言，上述的方法是對提出的 SATS 機制互補的，這是第一個利用在迭代應用中相鄰迭代的數(shù)據(jù)相似性來處理數(shù)據(jù)傾斜，提高 MapReduce 類似系統(tǒng)的負載均衡。3、SATS 設計 設計A.機制概述該 SATS 機制是一個運行時負載均衡的機制，以減少迭代應用程序中數(shù)據(jù)傾斜所造成的落后

14、者的概率。在 MapReduce 框架的 Reduce 階段，每個 Reducer 節(jié)點處理一些 key/value 對，所以數(shù)據(jù)傾斜問題是不平衡的 key 分配的問題， 即，有些 keys 比其他的有更多對應的 key/value 對。另外，具有相同 key 的key/value 對將在相同的 Reduce 節(jié)點被處理。因而 SATS 機制的基本單位是具有 相同的 key 的 key/value 對。在迭代應用中，在兩個相鄰迭代間的輸

15、入數(shù)據(jù)往往存在著一定的相似性，并且中間數(shù)據(jù)也可能有類似的關于 key/value 對的數(shù)據(jù)分布。舉例來說，在 PageRank 應用的所有迭代中，圖形數(shù)據(jù)集是相同的，只有頂點的權重變化。頂 點分布的程度在數(shù)據(jù)集中是永遠不會改變，并且輸入數(shù)據(jù)和 MapReduce 作業(yè)的中間數(shù)據(jù)的數(shù)據(jù)分布是幾乎是相同的。因此，中間數(shù)據(jù)關于從當前迭代的作業(yè) 中提取出 key/value 對的分布信息可以被用來預測在下一次迭代時的數(shù)據(jù)分配?；谶@樣的思想，在