

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
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ù)分配?;谶@樣的思想,在
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 外文翻譯--云計算中傾斜度感知的任務調度(譯文).doc
- 外文翻譯--云計算中傾斜度感知的任務調度
- 外文翻譯--云計算中傾斜度感知的任務調度(譯文).doc
- 外文翻譯--云計算中傾斜度感知的任務調度
- 外文翻譯--云計算中傾斜度感知的任務調度(英文)
- 外文翻譯--云計算中傾斜度感知的任務調度(英文).pdf
- 外文翻譯--云計算中傾斜度感知的任務調度(英文).pdf
- 高架橋墩柱傾斜度的變形監(jiān)測
- 高架橋墩柱傾斜度的變形監(jiān)測
- 基于DVFS和熱量感知的移動云計算任務調度研究.pdf
- 金屬工件表面傾斜度及最大高度差在線測量系統(tǒng).pdf
- 云計算環(huán)境中任務調度算法研究.pdf
- 云計算任務調度研究.pdf
- 正畸拔除第二前磨牙對第三磨牙傾斜度的影響.pdf
- 云計算中任務調度算法的優(yōu)化與研究.pdf
- 工程專業(yè)資料為什么傾斜度及巖石完整性加大嵌巖深度?
- 云計算中基于交叉熵方法的任務調度研究.pdf
- 基于無線傳感器網絡的輸電線路傾斜度在線監(jiān)測系統(tǒng)設計與開發(fā).pdf
- 平均生長型青少年不同矢狀骨面型切牙與磨牙傾斜度研究.pdf
- 成人骨性Ⅱ類錯(牙合)畸形不同垂直骨面型的磨牙傾斜度研究.pdf
評論
0/150
提交評論