外文翻譯--云計(jì)算中傾斜度感知的任務(wù)調(diào)度（譯文）

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

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

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

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

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

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

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

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

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

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

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

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

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

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