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

1、2013Skew-Aware Task Scheduling in Clouds云計算中傾斜度感知的任務(wù)調(diào)度李東生，陳宜興，理查德胡亥國防科技大學(xué)，計算機學(xué)院，并行與分布式處理國家實驗室，中國國立大學(xué)萊佛士商學(xué)院，新加坡dsli摘要：數(shù)據(jù)扭曲是 MapReduce 一樣的云系統(tǒng)中慢任務(wù)出現(xiàn)的一個重要原因。在本文中，我們提出了一個斜感知任務(wù)調(diào)度（ SATS）機制針對 MapReduce 類似系統(tǒng)的迭代應(yīng)用。該機構(gòu)利用迭代應(yīng)用中在相鄰迭代的數(shù)據(jù)分布的相似性，來減少數(shù)據(jù)扭曲造成的落伍的問題。它在當(dāng)前迭代的任務(wù)的執(zhí)行過程中收集數(shù)據(jù)的分布信息，并用這些信息來指導(dǎo)下一次迭代時任務(wù)的數(shù)據(jù)分割。我們在 HaL

2、oop 系統(tǒng)落實機制，在一個集群中部署。實驗結(jié)果表明，該機制可以處理數(shù)據(jù)扭曲，有效地提高負載平衡。關(guān)鍵詞：數(shù)據(jù)扭曲；任務(wù)調(diào)度；云計算；負載均衡1、簡介近年來云計算已經(jīng)成為一個有前途的技術(shù)，而且 MapReduce是最成功的一個大規(guī)模數(shù)據(jù)密集型云計算的實現(xiàn)平臺 1 - 3 。MapReduce的使用一個簡單的數(shù)據(jù)并行的編程模型，有兩個基本的操作，即， Map 和 Reduce操作。用戶可以根據(jù)應(yīng)用程序的要求自定義 Map 功能和 Reduce 功能。每個 map 任務(wù)取一片輸入數(shù)據(jù)，并產(chǎn)生一個用 Map 功能的 key/value 對的集合，這是初步地用 Reduce功能做 Reduce任務(wù)。這

3、種編程模型很簡單，但功能強大，許多大規(guī)模數(shù)據(jù)處理應(yīng)用程序可以由模型來表示。類 MapReduce的系統(tǒng)可以在云計算中自動調(diào)度多個分布在機器中的 Map 和/或 Reduce任務(wù)。作為同步步驟僅存在于 Map 階段和Reduce階段之間，任務(wù)執(zhí)行在相同的階段具有高平行度，并且因此并發(fā)性和系統(tǒng)的可擴展性可以被高度增強。 Hadoop4和它的變體（例如， HaLoop 5 和 Hadoop+ 6）是典型的類 MapReduce系統(tǒng)。由于在類 MapReduce 系統(tǒng)中 Map 和 Reduce階段之間存在同步步驟，在任一階段慢任務(wù)可能減慢整個工作的執(zhí)行。 這種慢任務(wù)在 Map 或 Reduce階段叫

4、做落后者。當(dāng)慢任務(wù)出來時， 整個工作的執(zhí)行時間會增加， 而資源的使用會被減少。最近，有研究 7-8 顯示該數(shù)據(jù)歪斜已經(jīng)成為了在 Map 或 Reduce階段出現(xiàn)慢任務(wù)的一個主要原因。 在許多科學(xué)計算和數(shù)據(jù)分析應(yīng)用中， 輸入的數(shù)據(jù)或中間數(shù)據(jù)的數(shù)據(jù)傾斜可能會導(dǎo)致嚴重的負載不平衡的問題。例如， PageRank 9用于大規(guī)模搜索工程是一種典型的執(zhí)行在類 MapReduce 系統(tǒng)上的應(yīng)用。該 PageRank應(yīng)用進行鏈接分析通過反復(fù)迭代其周邊鄰居的權(quán)重， 為在網(wǎng)頁的鏈接圖中的每個頂點 /網(wǎng)頁分配權(quán)重（等級）。研究 7 ，8 ，18 表明網(wǎng)頁鏈接圖的度是多傾斜的，一些頂點具有較大度的入邊。 由于 Map

5、Reducelike 系統(tǒng) 4 使用隨機哈希算法進行分區(qū)中間數(shù)據(jù)到 Reduce節(jié)點，節(jié)點代表著計算度較大的節(jié)點的權(quán)重的任務(wù)可能需要更多的時間來完成他們的任務(wù)， 從而成為該系統(tǒng)的慢任務(wù)。 而數(shù)據(jù)歪斜引起落伍問題已成為類似 MapReduce的系統(tǒng)中一個重要研究課題。在本文中，我們針對類似 MapReduce的系統(tǒng)提出了一個傾斜度感知任務(wù)調(diào)度（ SATS）機制。該 SATS 機制是基于觀察到許多在類似 MapReduce的系統(tǒng)中的應(yīng)用是迭代計算 5 ，如 PageRank9，機器學(xué)習(xí)應(yīng)用程序，遞歸關(guān)系查詢和社會網(wǎng)絡(luò)分析。 在迭代應(yīng)用程序中， 數(shù)據(jù)被迭代處理， 直到計算滿足收斂或停止?fàn)顟B(tài)，并在計算

6、時每個迭代可以是一個或多個 MapReduce工作。數(shù)據(jù)在兩個相鄰的迭代之間可能有相似性，并且在相鄰迭代的作業(yè)中的數(shù)據(jù)分布可能是相似的。如果數(shù)據(jù)的分布在一個 MapReduce工作執(zhí)行前能被獲得，我們可以正確地劃分數(shù)據(jù)到系統(tǒng)中的節(jié)點，以改善負載平衡?；谶@樣的思想， SATS 機制被設(shè)計成利用相鄰迭代中的數(shù)據(jù)分布的相似性， 以減少數(shù)據(jù)扭曲造成的落伍問題。 它收集在當(dāng)前迭代的任務(wù)執(zhí)行期間數(shù)據(jù)分布的信息， 并使用該信息， 引導(dǎo)下一個迭代時該數(shù)據(jù)的分布。由于數(shù)據(jù)偏移通常發(fā)生在 MapReduce工作中的 Reduce階段， SATS 機制重點在 MapReduce工作中的 Reduce階段的落后者問

7、題。本文的主要貢獻如下所示。首先，我們設(shè)計了一個傾斜感知任務(wù)調(diào)度機制，稱作 SATS，以處理在 MapReduce類似系統(tǒng)中的迭代應(yīng)用因數(shù)據(jù)傾斜造成的落后者問題。其次，我們實施 SATS 機制，建立基于 HaLoop5 的原型，一個開源的 MapReducelike 系統(tǒng)。最后，我們進行補償實驗來評估 SATS 機制，實驗結(jié)果表明，這 SATS 可以有效地改善負載平衡。本文的其余部分安排如下。 第 2 節(jié)討論了相關(guān)工作。 第 3 節(jié)示出了設(shè)計和實施 SATS 機制。第 4 節(jié)通過實驗評估該機制。第 5 節(jié)介紹的結(jié)論和未來的工作。2、相關(guān)工作A.MapReduce 類似的系統(tǒng)MapReduce1

8、是一種流行的針對數(shù)據(jù)密集型云計算系統(tǒng)的數(shù)據(jù)并行編程模型，由谷歌提出。 Hadoop4開源實現(xiàn) MapReduce模型，其中包括若干個子項目，如普通 Hadoop 和 HDFS3-4 。使用 MapReduce模型的云計算系統(tǒng)通常被稱為MapReduce的類似系統(tǒng)。MapReduce的類似系統(tǒng)將集群中所有節(jié)點劃分進入Master（即 JobTracker）和 Slave（即 TaskTracker），而且只有一個 Master，很多個 Slaves。Master 處理某些全球性的工作，如作業(yè)和任務(wù)調(diào)度， Slaves進行 Master 分配的工作，包括Map 工作和 Reduce工作。當(dāng)一個 M

9、ap 工作完成時，擁有相同 key 的中間 key/value 對根據(jù)數(shù)據(jù)分配方案將被分配到一個分區(qū)。在當(dāng)前版本的 Hadoop 中4 ，分區(qū)的數(shù)量和 Reduce節(jié)點的數(shù)量是相同的， 并且每個 Reduce節(jié)點處理來自所有被分配的 Map 節(jié)點的一個分區(qū)中的 key/value 對。在本文提出的 SATS 機制可以修改數(shù)據(jù)分配方案，以處理數(shù)據(jù)傾斜所造成的落后者問題。HaLoop5 是針對迭代應(yīng)用的 Hadoop 修改后的版本，如科學(xué)計算和數(shù)據(jù)分析應(yīng)用。 HaLoop 使用三個緩存，即 Reducer輸入緩存， Reducer輸出緩存和 Mapper 輸入緩存以提高性能。 Reducer輸入緩

10、存設(shè)計為存儲 Map 任務(wù)的輸出，提供數(shù)據(jù)供下一次迭代。 Reducer輸出緩存被設(shè)置為使所述固定點的計算變得更加容易。 Mapper 輸入緩存是用于 Map 任務(wù)的數(shù)據(jù)本地性。通過使用循環(huán)感知任務(wù)調(diào)度和輸入 /輸出緩存， HaLoop 可以顯著減少迭代應(yīng)用的執(zhí)行時間。提出的 SATS 機制在 HaLoop 系統(tǒng)中實現(xiàn)，并且其利用了任務(wù)在相鄰迭代中的中間數(shù)據(jù)的相似性以提高 Reducer 節(jié)點的負載均衡。B.MapReduce類似系統(tǒng)的調(diào)度調(diào)度是 MapReducelike 系統(tǒng)一個重要的研究課題。在 Hadoop 中有幾個默認的作業(yè)調(diào)度機制，例如， FIFO，計算能力調(diào)度，公平調(diào)度 10 。

11、由于 Hadoop 的調(diào)度可能會在異構(gòu)環(huán)境中導(dǎo)致嚴重的負載不均衡和性能下降， Longest Approxi-mate Time to End（LATE ）調(diào)度 11 的設(shè)計通過修改推測執(zhí)行策略處理了在異構(gòu)集群中的落后者問題，它可以減少Hadoop 一半的響應(yīng)時間。Ganesh Ananthanarayanan等人 12 對于落后者的問題將原因劃分為三類，包括具有不同的容量和可靠性的設(shè)備特性， 任務(wù)間具有不同帶寬、 擁堵和工作量的網(wǎng)絡(luò)特性（例如，數(shù)據(jù)扭曲造成的失衡）。他們提出 Mantri12 ，一種監(jiān)視任務(wù)和使用進程和資源感知技術(shù)精選落后者的機制， 包括重啟慢任務(wù)， 任務(wù)的網(wǎng)絡(luò)意識安置和保護

12、有價值任務(wù)的輸出。 具有實時進度報告， Mantri 在其時間周期的早期檢測落后者，并根據(jù)他們的原因采取適當(dāng)?shù)男袆?。?shù)據(jù)傾斜是在 MapReduce類似系統(tǒng)中執(zhí)行的許多應(yīng)用中的一個普遍現(xiàn)象7-8 ，13-15 。YongChul Kwon 等人 7 提出科學(xué)分析應(yīng)用即提取從數(shù)據(jù)集顯示出的顯著計算傾斜的特征。 Jimmy Lin8 觀察發(fā)生在許多 MapReduce工作中的落后者問題，提出它與數(shù)據(jù)集的數(shù)據(jù)偏移是相關(guān)的。 SkewReduce 7根據(jù)用戶定義的成本函數(shù)靜態(tài)優(yōu)化數(shù)據(jù)的分配， 但它取決于來自用戶的領(lǐng)域知識并被限制為特定的應(yīng)用程序。 SkewTune 13是一個針對用戶定義的 MapRe

13、duce程序的自動傾斜緩解機制。當(dāng)一個節(jié)點變?yōu)榭臻e時， SkewTune標(biāo)記任務(wù)最大的預(yù)期剩余處理時間，主動地重新分配掉隊的任務(wù)中未處理的輸入數(shù)據(jù)。LEEN 14 基于成本模型安排 keys 到 reduce任務(wù)中，而 TopCluster 15構(gòu)建了所有 reduce 的 keys 的直方圖來鑒定傾斜的 reduce keys?？傮w而言，上述的方法是對提出的SATS 機制互補的，這是第一個利用在迭代應(yīng)用中相鄰迭代的數(shù)據(jù)相似性來處理數(shù)據(jù)傾斜，提高 MapReduce 類似系統(tǒng)的負載均衡。3、 SATS 設(shè)計機制概述該 SATS 機制是一個運行時負載均衡的機制， 以減少迭代應(yīng)用程序中數(shù)據(jù)傾斜所造

14、成的落后者的概率。在 MapReduce框架的 Reduce階段，每個 Reducer節(jié)點處理一些 key/value 對，所以數(shù)據(jù)傾斜問題是不平衡的 key 分配的問題，即，有些 keys 比其他的有更多對應(yīng)的 key/value 對。另外，具有相同 key 的 key/value 對將在相同的 Reduce 節(jié)點被處理。因而 SATS 機制的基本單位是具有相同的 key的 key/value 對。在迭代應(yīng)用中， 在兩個相鄰迭代間的輸入數(shù)據(jù)往往存在著一定的相似性， 并且中間數(shù)據(jù)也可能有類似的關(guān)于 key/value 對的數(shù)據(jù)分布。舉例來說，在 PageRank 應(yīng)用的所有迭代中， 圖形數(shù)據(jù)集

15、是相同的， 只有頂點的權(quán)重變化。 頂點分布的程度在數(shù)據(jù)集中是永遠不會改變，并且輸入數(shù)據(jù)和 MapReduce作業(yè)的中間數(shù)據(jù)的數(shù)據(jù)分布是幾乎是相同的。因此，中間數(shù)據(jù)關(guān)于從當(dāng)前迭代的作業(yè)中提取出 key/value 對的分布信息可以被用來預(yù)測在下一次迭代時的數(shù)據(jù)分配。基于這樣的思想，在 SATS 機制是設(shè)計成利用在相鄰迭代的數(shù)據(jù)分布的相似性來減輕由數(shù)據(jù)傾斜造成的落后者問題同時增強了負載平衡。 該 SATS 機制收集當(dāng)前迭代中在作業(yè)執(zhí)行期間由 Map 任務(wù)產(chǎn)生的中間 key/value 對數(shù)據(jù)的分布信息，并利用該信息來指導(dǎo)下一次迭代的數(shù)據(jù)分配以提高 Reduce節(jié)點的負載均衡。 MapReduce類

16、似系統(tǒng)中 SATS 機制的組成部分如圖 1 所示， Map，Reduce和 JobTracker是MapReduce類似系統(tǒng)的通用組件。圖 1.MapReduce類似系統(tǒng)中 SATS 機制的組成部分SATS 機制由三個模塊實現(xiàn)：收集器模塊，控制器模塊，平衡器模塊。在MapReduce類似系統(tǒng)中，每個 Map 或 Reduce任務(wù)被分配的節(jié)點中有一個的TaskTracker工作。收集器模塊與 Reduce任務(wù)中的 TaskTracker運行，并收集在MapReduce作業(yè)的中間 key/value 對數(shù)據(jù)的分布信息。每個收集器模塊傳送上述數(shù)據(jù)分配信息聚集到平衡器模塊。平衡器模塊在 MapRedu

17、ce類似系統(tǒng)的 JobTracker子系統(tǒng)中工作，收集所有來自分布式收集器的數(shù)據(jù)分布信息，并計算中間key/value 對的全局分布，然后確定一個數(shù)據(jù)分配方案用于下一個迭代的作業(yè)來處理數(shù)據(jù)傾斜，提高 Reducer節(jié)點的負載平衡。平衡器模塊采用HLF 算法計算出的數(shù)據(jù)分配方案，稍后在C 部分描述。平衡器模塊確定數(shù)據(jù)分配方案后，它通知分布在控制器模塊的TaskTracker，它會在下一個迭代的方案中執(zhí)行 Map 任務(wù)。當(dāng)下一迭代的 Map 任務(wù)產(chǎn)生中間 key/value 對，它們將根據(jù)分配方案分割 key/value 對，而不是默認的 Hadoop/ HaLoop 中的 HashPartiti

18、oner 方案，然后將它們洗牌到 Reducer節(jié)點相應(yīng)地處理該數(shù)據(jù)傾斜并提高 Reducer節(jié)點的負載均衡。我們在 HaLoop5 系統(tǒng)中實現(xiàn)這些 SATS 機制中的模塊，并在下一個小節(jié)詳細說明了這些模塊。B.收集數(shù)據(jù)分布信息在 MapReduce類似系統(tǒng)中，中間數(shù)據(jù)以 key/value 對的形式產(chǎn)生，并且相同 key 的數(shù)據(jù)被洗牌到一個 Reducer節(jié)點。因此，數(shù)據(jù)分布信息是關(guān)于 keys 生成和它們的“權(quán)重”，即相關(guān)的 key/value 對的數(shù)量。該收集器模塊運行在分布式機器中 Reduce任務(wù)的每個 TaskTracker上，當(dāng) reduce任務(wù)在本地節(jié)點上執(zhí)行時，它計算 key

19、s 的權(quán)重。因為有許多在分布式系統(tǒng)中收集器模塊，他們應(yīng)該以keys和它們的權(quán)重的形式發(fā)送數(shù)據(jù)分發(fā)信息到運行了JobTracker的 Master 節(jié)點中的平衡器中。有幾種方法來傳輸分布式收集器模塊中的數(shù)據(jù)分配信息到MapReduce 類似系統(tǒng)中的 JobTracker。由于在 JobTracker和 TaskTracker之間有定期心跳消息，我們可以使用心跳消息捎帶數(shù)據(jù)分布信息，或者我們可以在需要時直接從TaskTracker到 JobTracker傳輸數(shù)據(jù)分布信息。然而，這些方法需要重寫或修改MapReduce類似系統(tǒng)的通訊機制， 它們可能影響該系統(tǒng)的通信執(zhí)行。 我們采取簡單、低權(quán)重的方法來

20、傳輸信息。如 MapReduce 類似系統(tǒng)通常使用 HDFS 3,4 分布式文件系統(tǒng)中，每個收集器模塊在 HDFS 文件系統(tǒng)寫入當(dāng)?shù)?reduce 任務(wù)的數(shù)據(jù)分布信息。 中間數(shù)據(jù)被存儲在 HaLoop 系統(tǒng)的源代碼的 Java 迭代中，并且收集器模塊讀入 Java 類迭代的 key/value 對并寫入本地數(shù)據(jù)分布信息 （即 keys 和它們的權(quán)重）到 HDFS 文件系統(tǒng)的指定目錄中。C.確定數(shù)據(jù)分配方案獲取全局數(shù)據(jù)的分布信息，平衡器模塊需要總結(jié)所有被運行 reduce 任務(wù)的TaskTracker中的收集模塊報告的數(shù)據(jù)分布信息。由于收集器模塊寫入本地數(shù)據(jù)的分布信息到 HDFS 文件系統(tǒng)中，平

21、衡器模塊可以從 HDFS 文件系統(tǒng)指定目錄中讀取報告在各種 Reducer節(jié)點中所有數(shù)據(jù)分配，然后計算 key/value 對的全局數(shù)據(jù)分配。收集 key/value 對的全局數(shù)據(jù)分布后，平衡器模塊應(yīng)該確定一個數(shù)據(jù)分配方案將 keys 分配給 Reducer節(jié)點。在 MapReduce類似系統(tǒng)中默認的HashPartitioner方案隨機地分配 keys 給 Reducer節(jié)點，可能會導(dǎo)致 Reducer節(jié)點的負載不均衡，因為在許多應(yīng)用中 keys 的權(quán)重是傾斜的。基于 keys 的權(quán)重聚集，在 SATS 機制中平衡器模塊使用傾斜感知數(shù)據(jù)分配方案，被稱為 HLF （Heaviest Load

22、First），以改善 Reducer節(jié)點的負載均衡，并處理應(yīng)用程序下一個迭代時的數(shù)據(jù)傾斜問題。HLF 算法是典型的 LPT（最長處理時間）調(diào)度算法的變體 16 ，其在最壞的情況下具有漸近復(fù)雜度 O（nlogn），其中 n 是分配的任務(wù)數(shù)， LPT 算法中任務(wù)完成時間不超過最佳任務(wù)結(jié)束時間的 133。LPT 算法假定所有任務(wù)的執(zhí)行時間事先已知，而 HLF 算法放緩假設(shè)來適應(yīng) MapReduce類似系統(tǒng)的環(huán)境。首先 LPT 以最長處理時間分配任務(wù)，而 HLF 先以最大的權(quán)重分配 keys 到 Reducer節(jié)點。因為中 MapReducelike 系統(tǒng)中計算時間往往是與中間數(shù)據(jù)的大小成比例的（即

23、keys 的權(quán)重），具有最大權(quán)重的 keys 需要最長計算時間。HLF ( S, N)S: keys 和它們的權(quán)重的集合N : Reducer節(jié)點的數(shù)量1 fori =1 to N do2L i 0 ;/ L i 是 Reducer節(jié)點 i 當(dāng)前的負載RSortKeyWeight(S);根據(jù)權(quán)重降序排序 keys4 while R null do5k FetchHead(R)/從 R 中取出 key k/ in R 中 key k 的權(quán)重最大R-R - k ;r FecthMinLoad( L);/取 reducer 節(jié)點 r 它的負載在所有Reducer節(jié)點中是最小的AssignTask(

24、r , k )將 key k 分配給 Reducer 節(jié)點 rL k 500 的頂點數(shù)最高的度最低的度as-skitter16964152380354551soc-LiveJournal1484757115106228891wiki-Talk239438524161000321B.實驗結(jié)果我們用 PageRank、后代查詢應(yīng)用程序和三個數(shù)據(jù)集評估 SATS 機制。PageRank應(yīng)用 5 由 3 MapReudce作業(yè)組成，其中包括 PageRank的數(shù)量，PageRank初始化和 PageRank的循環(huán)作業(yè)。 PageRank的循環(huán)作業(yè)是一個有兩個步驟的迭代作業(yè)，即 PageRank-Joi

25、n和 PageRank-Aggregate，PageRank循環(huán)作業(yè)的實驗結(jié)果被記錄。默認的哈希分配程序被用在作業(yè)的前兩步。后代查詢應(yīng)用 5 由兩個作業(yè)組成，包括 IterativeJoin 作業(yè)和 AggregateDelta 關(guān)系的作業(yè)。 IterativeJoin 作業(yè)是有兩個步驟的迭代作業(yè)， 即后代合并和后代消除重復(fù)。 我們用這些數(shù)據(jù)集運行PageRank和后代查詢應(yīng)用，并記錄 Reducer節(jié)點的負載分布和作業(yè)執(zhí)行時間。PageRank的應(yīng)用程序用 wiki-Talk 和 as-skitter 數(shù)據(jù)集執(zhí)行 20 次迭代，采用 13 個Reducer節(jié)點，而后代查詢應(yīng)用程序用 wiki

26、-Talk 和 soc-LiveJournal1 數(shù)據(jù)集執(zhí)行 5 次迭代，采用 7 個 Reducer節(jié)點。在 MapReduce類似系統(tǒng)中，在 Map 或者 Reduce階段該作業(yè)執(zhí)行時間是由具有最大負載的最慢節(jié)點確定的。 因此，我們使用稱為負載比的參數(shù)， 其等于一個迭代中最大負載除以 Reducer節(jié)點的平均負載的商，以評估 Reducer節(jié)點的負載均衡特性。圖 3 和 4 分別示出了用 wiki-Talk 數(shù)據(jù)集在 PageRank和后代查詢應(yīng)用程序的各個迭代中參數(shù)負載比的值。在圖中，original 指 HaLoop 中無修改的結(jié)果， SATS 指在原型系統(tǒng)中應(yīng)用SATS 機制的結(jié)果。

27、從圖3 和圖 4 中可以推斷出， SATS 機制可以有效地提高Reducer節(jié)點的負載均衡。圖 3. PageRank應(yīng)用程序中Reducer 節(jié)點的負載比圖 4. 后代查詢應(yīng)用程序中Reducer 節(jié)點的負載比5、總結(jié)在本文中，我們設(shè)計了一個傾斜度感知的任務(wù)調(diào)度機制，命名 SATS，針對MapReduce類似系統(tǒng)中的迭代應(yīng)用。 該 SATS 機制利用迭代應(yīng)用程序中相鄰迭代的數(shù)據(jù)分布相似性， 來減少中間數(shù)據(jù)的數(shù)據(jù)偏斜所造成的落后者問題。 該機制收集數(shù)據(jù)分配的信息， 并使用該信息引導(dǎo)下一次迭代的數(shù)據(jù)分配。 我們實現(xiàn)了基于 HaLoop 的 SATS 機制，在集群中部署原型系統(tǒng)。實驗證明該機制能夠

28、有效地改善負載均衡。 在今后的工作中， 我們將優(yōu)化原型系統(tǒng)的實現(xiàn)， 通過使用采樣機制降低 SATS 機制的執(zhí)行成本。致謝這項工作分別被贊助由中國國家自然科學(xué)基金會，批準號： 61222205，中國國家重點基礎(chǔ)研究發(fā)展計劃（973），批準號： 2011CB302600，以及 PR 中國的全國優(yōu)秀博士學(xué)位論文作者基金會（FANEDD ），批準號： 200953。參考文獻Jeffrey Dean, Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM, 5

29、1(1):107-113, 2008Xicheng Lu, Huaimin Wang, Ji Wang, Jie Xu, Dongsheng Li. Internetbased VirtualComputing Environment: Beyond the data center as a computer. FutureGeneration Computer System, 29(1): 309-322, 2013.Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. The Google File System.Proc.of SOSP 03,

30、 2003.Apache Hadoop Project. /.Yingyi Bu, Bill Howe, Magdalena Balazinska, Michael D. Ernst.HaLoop: Efficient Iterative Data Processing on Large Clusters. Proc. of VLDB10, 20J. Dittrich, J. Quiane-Ruiz, A. Jindal, Y. Kargin, V. Setty, and J. Schad. Hadoop+: Making a Yellow Elephant Run Like a Cheeta

31、h (Without It Even Noticing).Proc. of the VLDB Endowment, 3(1), 2010.YongChul Kwon, Magdalena Balazinska, Bill Howe, Jerome Rolia.Skew-Resistant Parallel Processing of Feature-Extracting Scientific User-Defined Functions. Proc. of ACM Symposium on Cloud computing, 2010Jimmy Lin. The Curse of Zipf an

32、d Limits to Parallelization: A Look at the Stragglers Problem in MapReduce. Proc. of 7th Workshop on Large-Scale Distributed Systems for Information Retrieval, 2009.S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Proc. of WWW 98, 1998.M. Zaharia, D. Borthakur, J. S. Sarma, K. Elmeleegy, S. Shenker, and I.Stoica. Job Scheduling for Multi-User MapReduce Clusters. Technical Report UCB/EECS-2009-55, University of California at Berkeley, April 2009.Matei Zaharia, Andy Konwinski, An