網(wǎng)絡(luò)常常成為稀缺的資源，表現(xiàn)在傳輸任務(wù)的耗時。
 在考慮任務(wù)的延遲的時候，我們分析MapReduce任務(wù)的三階段對總延遲的貢獻，分別考慮Map、Transfer、Reduce階段的延遲。可以由圖中數(shù)據(jù)來分析傳輸任務(wù)的耗時。
 我們在實驗中發(fā)現(xiàn)PageRank的中間數(shù)據(jù)傳輸會比map任務(wù)延遲大，這是由于傳輸?shù)牟黄胶夂椭虚g數(shù)據(jù)增加，最后導(dǎo)致傳輸成為瓶頸，同時我們也發(fā)現(xiàn)，這樣的任務(wù)通常會使得傳輸?shù)膬?yōu)化對整個任務(wù)的延遲帶來很好的改善。
 
一些機器的出錯同樣極大地增加了任務(wù)完成的延遲，一些關(guān)鍵的任務(wù)如Map等由于機器出錯導(dǎo)致需要重調(diào)度和重執(zhí)行，從而整個任務(wù)的進行依賴于此任務(wù)，導(dǎo)致最后成為瓶頸完成延遲增加。
不合理的分割通常導(dǎo)致負載不均衡，最后導(dǎo)致的是不能很好的并行和顯著增加延遲。
 
 如此圖所示，其中一臺機器分到的數(shù)據(jù)比較多，而其他數(shù)據(jù)都平均。經(jīng)過我們分析是由于鏈接的PowerLaw特性分布造成，使得使用的分割函數(shù)不能很好的達到負載均衡的目的，而最后Worker1也變成了瓶頸，導(dǎo)致延遲增加。

 還有其他若干問題，這里不一一列覺。我們認(rèn)為落后者的問題可以使用后備任務(wù)策略很好地解決，在下一章中我們實現(xiàn)了這一策略，并就我們的設(shè)計和評估做了說明。
開銷分析
 同4.2.1節(jié)中的機群設(shè)置，我們分析監(jiān)控和程序概要分析所帶來的代價和開銷。
 我們在系統(tǒng)實現(xiàn)的很多地方捎帶地記錄下任務(wù)的執(zhí)行時信息包括數(shù)據(jù)大小、任務(wù)類型和依賴關(guān)系、任務(wù)耗時、系統(tǒng)配置情況等等重要信息，以供系統(tǒng)監(jiān)控和分析。如果實現(xiàn)帶來了較大的開銷，那么在實際的使用中，監(jiān)控和分析將很難勝任應(yīng)用的需求。我們基本上是使用捎帶的做法來記錄關(guān)鍵信息，在進程間通信時使用文件作為管道，而C++的庫和系統(tǒng)對文件的API實現(xiàn)了很好的緩存處理，使得開銷能夠優(yōu)化，同時避免在復(fù)雜系統(tǒng)中使用其他進程間通信如發(fā)signal信號等同步策略而造成的復(fù)雜性和開銷過大的問題。
 我們通過關(guān)閉和打開系統(tǒng)監(jiān)控和程序的概要分析功能，來對開銷做出分析。結(jié)果如下表。
 表格 3-系統(tǒng)監(jiān)控框架開銷分析
 Type/Time secs Latency with Profile Latency without Profile Overhead
WordCount 132 102 22.7%
PennySort 270 213 21.1%
PageRank 140 105 25.0%
 
 后備任務(wù)調(diào)度策略
問題描述
 通過上一章的系統(tǒng)評估和性能分析，我們看到了由于部分落后機器而導(dǎo)致的任務(wù)延遲增大問題。在Map或者是Reduce階段，位于某臺機器上的某個子任務(wù)，由于各種原因而導(dǎo)致其顯著慢于同一個任務(wù)同種類型的其他子任務(wù)，從而導(dǎo)致整個任務(wù)的延遲顯著增大。
 由此系統(tǒng)評估和分析我們可以知道，本系統(tǒng)中的任務(wù)延遲存在此性能問題。接下來我們針對此問題改善系統(tǒng)的單任務(wù)延遲，并由此說明系統(tǒng)評估在其中起的重要作用。
 對于短任務(wù)的用戶來說，系統(tǒng)的單任務(wù)延遲時間是一個重要的衡量因素。因為短任務(wù)的用戶都希望系統(tǒng)能夠快速地對他們提交的任務(wù)做出回答，比如在日志分析、系統(tǒng)監(jiān)控、商務(wù)數(shù)據(jù)分析等等應(yīng)用中，這樣的任務(wù)是很常見的。Google的MapReduce也是主要用于短任務(wù)，根據(jù)MapReduce的論文，Google在2007年9月中提交的MapReduce任務(wù)的平均延遲時間是395秒。延遲時間對于SQL-like的系統(tǒng)和任務(wù)來說也很重要，比較在這些系統(tǒng)之上的語言如Pig、SCOPE等等，用它們描述的計算任務(wù)基本上都希望有好的延遲。同時，對于EC2這樣的應(yīng)用來說，單任務(wù)的延遲就顯得更加重要，因為EC2用戶的付費是按時間來計算的，如果使用的系統(tǒng)對單任務(wù)有更好的延遲，那無疑能夠有顯著的經(jīng)濟效應(yīng)。
 所以，使用Backup的調(diào)度策略，對于落后任務(wù)投機地使用后備任務(wù)，能夠極大地提交系統(tǒng)的單任務(wù)延遲時間，對于短任務(wù)來說，尤為如此。而對于較長的任務(wù)，后備任務(wù)的使用的效果就相對比較小。我們這一章的工作中，也將主要考慮改善短任務(wù)的延遲時間。
相關(guān)工作
MapReduce
 Google的論文中說明了他們在工作中這個問題的狀況。他們觀察到在任務(wù)的執(zhí)行最后過程中，經(jīng)常有一臺機器在運行這最后的幾個Map或Reduce任務(wù)時花費異常長的時間。他們也分析了可能的原因：這臺機器的硬盤狀況不好，可能會導(dǎo)致它的讀寫出現(xiàn)異常；或者是由于調(diào)度使得同一臺機器的負載過重而使得原先執(zhí)行的任務(wù)變慢；或者是任務(wù)程序中的bug問題等等。通常這樣的落后機器出現(xiàn)的概率是1/100。
 他們也使用了一些機制來啟動后備任務(wù)。他們的策略是這樣的，當(dāng)MapReduce的任務(wù)快結(jié)束時，他們對于還在運行的子任務(wù)啟用后備任務(wù)，原子任務(wù)或者后備任務(wù)中的其中一個結(jié)束就標(biāo)記這個子任務(wù)結(jié)束。他們同時采取了一些措施使得后備任務(wù)不會占用系統(tǒng)資源過多。根據(jù)文章的實驗，對于sort來說，啟用后備任務(wù)后，性能提高了44%。
Hadoop
 對于Hadoop2中的實現(xiàn)，針對此問題，分析代碼細節(jié)如下。
 如果一臺機器空閑的時候，Hadoop將選擇一個任務(wù)在其之上運行。選擇的方式如下：首先，失敗的任務(wù)優(yōu)先最高執(zhí)行，這是Hadoop的錯誤偵察機制，為了找到由于bug或者其他原因不斷失敗的任務(wù)并最終放棄；其次，沒有運行過的任務(wù)根據(jù)調(diào)度策略調(diào)度到此空閑機器上執(zhí)行；最后，如果前兩種情況都沒有發(fā)生，Hadoop選擇一個正在運行的任務(wù)投機執(zhí)行，而判斷的策略將在下面闡述。
 為了挑選出需要投機執(zhí)行的后備任務(wù)，Hadoop使用了一個進程分?jǐn)?shù)的值來進行判斷。進程分?jǐn)?shù)是一個在0到1之間的數(shù)值，它是由幾部分組成的。
 對于Map任務(wù)來說，進程分?jǐn)?shù)是該任務(wù)輸入數(shù)據(jù)占整個任務(wù)輸入數(shù)據(jù)的比值。而對于Reduce任務(wù)來說，這個值的獲取分三個階段考慮：
 1.copy階段，當(dāng)Reduce任務(wù)正在從Map任務(wù)拷貝數(shù)據(jù)的時候該值計入進程分?jǐn)?shù)，值為copy數(shù)據(jù)占整個Map數(shù)據(jù)的比例。
 2.sort階段，當(dāng)Map輸出的數(shù)據(jù)根據(jù)key來排序的時候該值計入進程分?jǐn)?shù)，值為sort數(shù)據(jù)占合并數(shù)據(jù)的比例。
 3.reduce階段，當(dāng)用戶定義的reduce函數(shù)正在對Map數(shù)據(jù)進行reduce操作時該值計入進程分?jǐn)?shù)，值為reduce數(shù)據(jù)占此階段數(shù)據(jù)的比例。
 然后，Hadoop對每種任務(wù)根據(jù)它們的平均進程分?jǐn)?shù)定義了一個閾值。Hadoop簡單地把閾值設(shè)為平均分?jǐn)?shù)減0.2。對于落后者的判斷，Hadoop發(fā)現(xiàn)如果一個任務(wù)的進程分?jǐn)?shù)低于此類任務(wù)的閾值，并且已經(jīng)運行了至少一分鐘，則這個任務(wù)被標(biāo)記為一個落后任務(wù)，需要執(zhí)行后備任務(wù)以加快任務(wù)的延遲。
 最后，Hadoop使用一個FIFO的隊伍來進行任務(wù)的調(diào)度。
異構(gòu)環(huán)境中后備任務(wù)調(diào)度
 在OSDI 08的這篇文章中[  Matei Zaharia Andy Konwinski Anthony D. Joseph Randy Katz Ion Stoica. Improving MapReduce Performance in Heterogeneous Environments, proceedings of OSDI, 2008.]，作者關(guān)注了在異構(gòu)的環(huán)境下后備任務(wù)的調(diào)度。在日常的應(yīng)用中，如Amazon的EC2這樣的按需式計算服務(wù)，或者是小型機構(gòu)的機房中，異構(gòu)的機群和環(huán)境都是很常見的。而Hadoop的調(diào)度基本上是基于同構(gòu)的環(huán)境來設(shè)計的。作者分析了Hadoop的設(shè)計并給異構(gòu)的環(huán)境中設(shè)計了新的調(diào)度策略。最后在200臺機器的EC2異構(gòu)機群中，提高了2倍的性能。
實現(xiàn)細節(jié)
 首先，我們考慮了Tplatform的實際情況：主要用于本實驗室小組的搜索引擎的研究信息處理，應(yīng)用程序的數(shù)據(jù)基本上是與機群規(guī)模匹配的數(shù)據(jù)集合，而任務(wù)集合基本上是搜索引擎相關(guān)的如網(wǎng)頁消重、網(wǎng)頁的實體分析、數(shù)據(jù)的挖掘等等。而機群的環(huán)境都是同構(gòu)的，所以我們考慮的是怎么在同構(gòu)的環(huán)境在針對這些中短任務(wù)進行后備任務(wù)策略的優(yōu)化。如下我們將細致討論實現(xiàn)細節(jié)。
整體框架
 我們從高層邏輯來闡述實現(xiàn)的細節(jié)。首先需要在Master端解決落后者的判定問題，對于一個正在Worker端執(zhí)行的子任務(wù)，其是否是落后者，需要Master綜合各方面信息分析后根據(jù)判定策略給出決策；其次，一旦該子任務(wù)被判定為落后者，具體的處理措施分析在Master和Worker端進行，需要保證Master端記錄任務(wù)的數(shù)據(jù)結(jié)構(gòu)的一致性和效率，以免Master變成整個系統(tǒng)的性能瓶頸，此外還需要保證Worker端的后備任務(wù)不會過多成為完全的冗余，避免系統(tǒng)由于后備任務(wù)策略的開銷反而低效。
 設(shè)計系統(tǒng)在執(zhí)行此策略的流程如下：
 （1）如果有一個Worker的機器出于空閑狀態(tài)，它向Master匯報為沒有任務(wù)在其上執(zhí)行，并且Master也沒有分配新的任務(wù)給它，此時Master啟動后備任務(wù)的策略，決定是否在此機器上執(zhí)行后備任務(wù)。
 （2）Master根據(jù)落后者的判定策略，選擇一個合適的后備任務(wù)在該Worker上執(zhí)行，或者Master根據(jù)策略認(rèn)為當(dāng)前系統(tǒng)不需要后備任務(wù)，這可能是因為沒有落后者或者是系統(tǒng)認(rèn)為此時的系統(tǒng)負載不合適執(zhí)行過多的后備任務(wù)。總之，此處將根據(jù)策略決定是否執(zhí)行，原則是能夠改善系統(tǒng)的性能同時保證開銷不會過大。
 （3）系統(tǒng)進行處理，分別在Master端和Worker端做出反應(yīng)，直至完成。
 我們在下面的小節(jié)中詳細闡述這三個步驟中的細節(jié)。
落后者判定策略
 落后者的判定是這個系統(tǒng)優(yōu)化中最重要的部分，如果系統(tǒng)誤將非落后任務(wù)判定為落后任務(wù)，那將造成不必要的開銷最終導(dǎo)致性能變差；如果系統(tǒng)沒有識別出落后者，那潛在的性能優(yōu)化空間并沒有得到填充，那優(yōu)化并沒有得到充分發(fā)揮。而如何決策使得上述兩個方面的折衷能夠得到同時滿足，一方面是根據(jù)最終系統(tǒng)運行的實際應(yīng)用程序而定的，另一方面是根據(jù)系統(tǒng)的實際狀況而決定的。根據(jù)上述分析，我們的應(yīng)用場景和系統(tǒng)是這樣的：在同構(gòu)的系統(tǒng)環(huán)境下面對中短任務(wù)的計算。
 首先，我們分析導(dǎo)致落后者出現(xiàn)的原因和表現(xiàn)行為。落后者可能因為多種原因出現(xiàn)，在Google的MapReduce論文中已經(jīng)有所提及。無論這些原因是什么，落后者出現(xiàn)后，它們的表現(xiàn)行為都是落后于正常子任務(wù)，根據(jù)短板效應(yīng)導(dǎo)致最后整個任務(wù)需要等待這個最慢的子任務(wù)才能算結(jié)束，從而增大了延遲。所以對于落后者的判定，要做的就是把它們和普通的正常子任務(wù)區(qū)分開來，知道哪些子任務(wù)的正常的，哪些是落后的。
 然后，對于子任務(wù)耗時的信息和完成進度和來說，我們可以分別在Master和Worker端獲取這些信息。
 最后，我們在Master匯總這兩方面的信息，確定性地給出判定的結(jié)果。
Master端：
我們有一個假設(shè)，那就是對于同一個任務(wù)的同種類型的子任務(wù)（Map或者Reduce，Transfer子任務(wù)會在Map做完后開始，我們不考慮對Transfer子任務(wù)投機地進行后備執(zhí)行）可能會在相同的時間內(nèi)完成。此假設(shè)認(rèn)為1.機群環(huán)境同構(gòu)；2.數(shù)據(jù)基本上均勻分布；3.計算時間和IO時間不會因為數(shù)據(jù)的值而發(fā)生劇烈的變化。如果這一系列假設(shè)不成立時，就有可能出現(xiàn)落后者問題。我們將在下面根據(jù)實驗說明在測試的基準(zhǔn)程序集合中，這樣的應(yīng)用程序負載下此假設(shè)是成立的，偶爾會因為各種原因使得假設(shè)失敗，這些情況就是落后者，需要做后備任務(wù)投機執(zhí)行以改善延遲。
所以，我們將根據(jù)系統(tǒng)監(jiān)控和程序的概要分析記錄下任務(wù)的Map子任務(wù)和Reduce子任務(wù)的平均完成時間，如果一個正在執(zhí)行的子任務(wù)比同任務(wù)同類型的其他子任務(wù)顯著地慢，那它可被判定為落后者。
Worker端：
對于正在Worker端執(zhí)行的子任務(wù)來說，Worker具有知道該子任務(wù)進行到什么地步的能力。我們用進度分?jǐn)?shù)來描述Worker正在執(zhí)行的任務(wù)處于什么狀態(tài)，進度分?jǐn)?shù)是一個從0到1的連續(xù)值。
在Map階段，由于TFS的默認(rèn)設(shè)置是一個chunk大小為64M，所以默認(rèn)的Map輸入數(shù)據(jù)大小為64M。我們根據(jù)Mapper讀入的數(shù)據(jù)大小來確定進度分?jǐn)?shù)。
在Reduce階段，需要先進行一個Sort的過程，因為Sort的完整性，我們簡化了此過程中進度分?jǐn)?shù)記錄。也就是說，在Sort的過程中，Worker認(rèn)為Sort還沒有完成，進度為0。整個Reduce階段的進度分?jǐn)?shù)由是否Sort完成和reduce進度兩部分組成，這兩部分的權(quán)值我們進行了簡單的權(quán)重分配。Sort階段在大數(shù)據(jù)時會進行多路歸并的外排，而reduce階段基本上是IO占主要的時間。同時，我們根據(jù)實驗的經(jīng)驗設(shè)置兩部分權(quán)重比例為1：1。最后根據(jù)權(quán)重計算出整個Reduce階段目前的進度分?jǐn)?shù)。
在Worker端記錄下各階段的進度分?jǐn)?shù)后，在本地由文件管道傳遞給和Master端通信的心跳進程，再由此進程通過心跳把進度和任務(wù)的相關(guān)情況捎帶傳給Master。
綜合：
對于需要判斷的正在執(zhí)行的子任務(wù)來說，一方面，Master通過記錄的以前執(zhí)行的同類型子任務(wù)的歷史信息可以知道平均耗時，一方面Master通過Worker每次心跳傳來的實時進度可以知道此子任務(wù)進行到什么進度。如果該子任務(wù)已經(jīng)顯著超過平均耗時水平或者根據(jù)進度明顯慢于同類型任務(wù)，那即可判定該子任務(wù)為落后者。
系統(tǒng)處理過程
 從兩方面來描述這一過程中系統(tǒng)的處理。
 首先是Master端，Master對一個子任務(wù)進行是否為落后者的判定后，需要修改Master端的數(shù)據(jù)結(jié)構(gòu)，以進行處理。
 如果不是落后者，那Master不作處理。
 如果落后者判定成功，Master修改數(shù)據(jù)結(jié)構(gòu)以記錄原始的子任務(wù)和新的后備子任務(wù)。初始化后備子任務(wù)的數(shù)據(jù)結(jié)構(gòu)，在和指定的Worker發(fā)送消息時將此新命令發(fā)出。
 在命令發(fā)出之后，Master還需要處理此子任務(wù)的結(jié)束。如果原始子任務(wù)和后備子任務(wù)其中一個完成，Master即認(rèn)為此子任務(wù)結(jié)束，并發(fā)停止執(zhí)行的命令給還未結(jié)束的Worker，以免浪費資源。
 然后是Worker端的處理。在這里的實現(xiàn)中，Worker對后備任務(wù)這一策略是透明的，如果Master發(fā)命令給Worker要求做一個任務(wù)，原始任務(wù)和后備任務(wù)在Worker看來是一樣的。
數(shù)據(jù)結(jié)構(gòu)細節(jié)
 同樣地，我們從Master和Worker兩方面來描述數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)細節(jié)。
 對于Master，在保證不規(guī)模修改實現(xiàn)接口的情況下，進行了如下的實現(xiàn)。
TaskInfo結(jié)構(gòu)：TaskInfo是記錄子任務(wù)信息的數(shù)據(jù)結(jié)構(gòu)，在之前的實現(xiàn)上添加了兩個域，用以標(biāo)明和區(qū)分后備子任務(wù)。
 /// if it is backup task: MAP/REDUCE only
 bool isBackup;
 /// for backup task: original task id
 int32_t originalTaskId;
 一個是標(biāo)明此任務(wù)是否為后備任務(wù)，一個是記錄原始任務(wù)的ID。
在TaskManager中添加兩個輔助的數(shù)據(jù)結(jié)構(gòu)，用來在添加后備任務(wù)以及判定完成情況時處理。
 /// task status map: record status of map/reduce tasks with each job, task is completed when either backup task or orginal task completed
 std::map<int32_t, std::map<int32_t, bool> > m_jobid2tasksIsCompleted;
 /// backup task map: one task only have a single backup task at one time
 std::map<int32_t, bool> m_taskid2backing;
 第一個map是記錄各個job中的task是否完成，如果有后備子任務(wù)，只要原始任務(wù)和后備子任務(wù)中其中一個完成就算此任務(wù)完成。
 第二個map是記錄各個任務(wù)是否有后備任務(wù)，在這里使用map是因為后備任務(wù)的查看和處理過程中需要經(jīng)常看原始任務(wù)的狀態(tài)，所以使用map避免Master端大規(guī)模的掃描任務(wù)隊列，成為性能瓶頸。此外，這里的一對一映射保證了一個原始子任務(wù)最多只有一個后備子任務(wù)，這是為了防止造成多個后備任務(wù)出現(xiàn)而造成開銷太大，或者是后備子任務(wù)再次成為落后者引起級聯(lián)反饋的效果后浪費系統(tǒng)的資源。
后備任務(wù)策略評估實驗
機群配置和任務(wù)準(zhǔn)備
 我們的機群配置如下。
 我們在后備任務(wù)策略的評估實驗中使用了一臺Master、十四臺Worker組成的MapReduce系統(tǒng)集群。所有的機器都是Dell 2850服務(wù)器，每臺機器配置為2顆Intel Xeon處理器，2GB內(nèi)存，6個7200 rpm SCSI硬盤組成一個RAID-0的邏輯卷。這些機器存放在兩個機架中，各有一臺Dell 2748 1Gbps交換機，機器通過一個1Gbps的全雙工以太網(wǎng)卡與交換機相連接，兩個機架通過一個Cisco千兆路由器鏈接。
 我們實驗使用的是PennySort程序來進行評估。生成了50M的Record，一共是4.8G大小的數(shù)據(jù)。
任務(wù)耗時趨同性分析
 我們首先分析在5.3.2節(jié)的設(shè)計中做出的假設(shè)在我們的環(huán)境和工作負載下是否合理。
 我們的假設(shè)是，對于同一個任務(wù)的同種類型的任務(wù)基本上會在相同的時間內(nèi)完成。
 我們對與選定的基準(zhǔn)程序集合的任務(wù)集合的耗時情況進行分析如下表，可以看到它們耗時的標(biāo)準(zhǔn)差和均值的比例并不高，說明這些任務(wù)基本上是在相同的時間內(nèi)完成的。
 
 表格 4-任務(wù)耗時趨同性分析
 CostTime(seconds)/Type PageRank PennySort WordCount
Avg. Map 4.6  118.1  118.1
Stdev. Map 0.8  4.3  8.7
Stdev/Avg. Map 16.3% 3.7% 10.0%
　 　 　 　
Avg.Reduce 34.6  469.3  33.1
Stdev. Reduce 0.9  17.6  9.2
Stdev/Avg. Reduce 2.6% 3.8% 27.7%
　 　 　 　
Avg. Transfer 1.0  1.0  1.8
Stdev. Transfer 0.3  0.2  0.5
Stdev/Avg. Transfer 26.7% 16.9% 29.2%
 
 從上表中我們可以看出，同一個任務(wù)的同種類型任務(wù)會趨向一致完成。表現(xiàn)在表中的數(shù)據(jù)有兩點：
任務(wù)平均耗時較長，但是標(biāo)準(zhǔn)差都很小，標(biāo)準(zhǔn)差和平均值的比值在10%以內(nèi)，表明這種類型的任務(wù)都趨向均值的時間結(jié)束，浮動的范圍很小；
任務(wù)的耗時標(biāo)準(zhǔn)差和平均值的比值在10%之上，但是耗時的絕對值比較小，如WordCount的傳輸任務(wù)平均耗時只是1.8秒左右，也可以認(rèn)為趨向一致完成這些任務(wù)。
 經(jīng)上述分析，我們驗證了在設(shè)計之初做出的假設(shè)，實驗說明我們的設(shè)計假設(shè)在我們的應(yīng)用環(huán)境中是合適的。
后備任務(wù)策略評估
 對于后備任務(wù)策略的評估，我們首先模擬出落后者的Worker，然后評估后備任務(wù)的效果。
 落后者的原因我們在前面的章節(jié)分析過，模擬要達到的目標(biāo)是讓落后者的Worker執(zhí)行原任務(wù)的時候會顯著變慢。我們從三方面來考慮模擬，一個是讓模擬的那臺機器額外地執(zhí)行一個計算密集型的程序；一個事讓其額外地執(zhí)行一個I/O密集型的程序；最后一種是模擬Worker運行中可能出現(xiàn)的異常而導(dǎo)致變慢，從而達到該機器在執(zhí)行MapReduce系統(tǒng)分配的任務(wù)時變慢。
 我們在下面列出模擬的程序和實現(xiàn)說明如下：
計算密集型
#include<cstdlib>
using namespace std;

int main()
{
    int count = 0;
    while(1){
        count ++;
        if(count % 1000000000 == 0){
            sleep(10);
        }
    }
    return 0;
}
 此程序利用死循環(huán)模擬計算密集型的任務(wù)，用來模擬機器因為同時并發(fā)執(zhí)行此種任務(wù)而導(dǎo)致落后的情況，其中的常數(shù)設(shè)置可以根據(jù)機器的性能和實際情況在實驗中調(diào)整。
I/O密集型
#include<cstdlib>
#include<fstream>
using namespace std;

int main()
{ 
 while(1){  
 const int BUFSIZE = 64 * 1024 *1024;
        char* buffer = new char[BUFSIZE];
        ofstream fout("ioBound.tmp", ios::out);
        fout.write(buffer, BUFSIZE * sizeof(char) );
        fout.flush();
        sleep(10);
    }
    return 0;
}
 此程序利用寫文件來模擬I/O密集型的任務(wù)，用來模擬機器因為同時并發(fā)執(zhí)行此種任務(wù)而導(dǎo)致落后的情況，其中的常數(shù)設(shè)置可以根據(jù)機器的性能和實際情況在實驗中調(diào)整。
異常模擬
 此外，我們根據(jù)可能發(fā)生的情況，還模擬了異常可能導(dǎo)致落后的情況。我們在一臺硬盤即將被寫滿的機器上做了這個實驗。當(dāng)Master把任務(wù)分配在這臺機器上時，由于硬盤無法寫入而導(dǎo)致異常，并可能導(dǎo)致機器成為落后者。
 然后我們針對PennySort這個任務(wù)，進行后備任務(wù)的評估。實驗分別在普通情況、模擬I、模擬II、模擬III（說明見上）上進行，考察的系統(tǒng)性能指標(biāo)是單任務(wù)的延遲。下圖是評估結(jié)果。
 從圖中可以看出，后備任務(wù)對落后者的改善很大。如果有落后者出現(xiàn)，基于模擬實驗可知，后備任務(wù)能夠有效地改善任務(wù)的延遲。
 同時，我們還可以分析得到，PennySort基本上也是一個I/O型瓶頸的任務(wù)，I/O密集型的落后者能夠較長時間拖任務(wù)的后腿；而計算型的卻不然，改善也不大。
 此外，我們注意到，異常也可能造成任務(wù)的延遲大幅增加。而在大規(guī)模數(shù)據(jù)中心內(nèi)，各種異常的出現(xiàn)是很正常的現(xiàn)象，這也說明了后備任務(wù)可以在大規(guī)模數(shù)據(jù)中心內(nèi)起到重要作用。
 
 
 

 系統(tǒng)優(yōu)化方向
 根據(jù)我們對系統(tǒng)的分析和評估，以及我們在Tplatform平臺的日常使用中的經(jīng)驗，除了已經(jīng)實現(xiàn)的后備任務(wù)策略，我們針對分析得出的其他系統(tǒng)優(yōu)化方向，進行分析和探討。
網(wǎng)絡(luò)傳輸問題
 在MapReduce的模型和體系結(jié)構(gòu)的實現(xiàn)中，需要進行網(wǎng)絡(luò)的傳輸任務(wù)，也就是在reduce階段需要把map生成的數(shù)據(jù)傳到reduce對應(yīng)的機器上。在這個階段很多應(yīng)用程序可能生成大量的中間數(shù)據(jù)，而經(jīng)過我們的之前的分析，網(wǎng)絡(luò)會成為MapReduce系統(tǒng)的性能瓶頸。所以，如果優(yōu)化網(wǎng)絡(luò)的傳輸，減少不必要的中間數(shù)據(jù)，也是一個直接和實際的系統(tǒng)優(yōu)化問題。
 在網(wǎng)絡(luò)傳輸?shù)膯栴}上，可以有不同的研究方向：
如何優(yōu)化機群的網(wǎng)絡(luò)傳輸，考慮在此環(huán)境下機器的路由和網(wǎng)絡(luò)層的優(yōu)化問題。已經(jīng)有一些研究工作在這個方向上進行，如DCell[  Chuanxiong Guo etc., DCell: A Scalable and Fault-Tolerant Network Structure for Data Centers, proceedings of SIGCOMM, 2008.]、Fat Tree[  Al-Fares, Loukissas, Vahdat, A Scalable, Commodity Data Center Network Architecture, proceedings of SIGCOMM, 2008.]。
如何通過優(yōu)化負載和任務(wù)等不同粒度上的調(diào)度，來優(yōu)化系統(tǒng)的網(wǎng)絡(luò)傳輸。
如何有效地利用應(yīng)用程序的數(shù)據(jù)特征，使得系統(tǒng)可以充分利用數(shù)據(jù)的時間和空間局部性，從而減少產(chǎn)生的中間數(shù)據(jù)，最后達到優(yōu)化網(wǎng)絡(luò)傳輸問題的目的。
 此外，還有其他方向和角度來考慮這個問題。從我們的日常使用經(jīng)驗來看，網(wǎng)絡(luò)通常是比硬盤I/O更容易成為瓶頸。
增加用戶和系統(tǒng)的交互
 在MapReduce的體系框架下，系統(tǒng)對用戶掩蓋了很多系統(tǒng)細節(jié)，同時簡單的計算模型也使得大量的并行細節(jié)對用戶來說并不透明。Google對于MapReduce的此設(shè)計目的在于掩蓋細節(jié)，使得用戶只是簡單的實現(xiàn)Map函數(shù)和Reduce函數(shù)，就可以進行大規(guī)模的數(shù)據(jù)處理。但是我們發(fā)現(xiàn)，在實際使用中過于簡單的模型和不透明也會帶來性能問題。用戶對系統(tǒng)的不了解可能造成重復(fù)計算或者浪費用戶的時間，用戶白白等待無效的計算等等情況。
 所以此方向我們需要研究的是，哪些系統(tǒng)實現(xiàn)細節(jié)是有必要對用戶掩蓋的，哪些系統(tǒng)實現(xiàn)細節(jié)如果用戶知道能夠使得一個專家級的用戶更好地控制系統(tǒng)和對應(yīng)用程序進行優(yōu)化。同時，我們還需要研究的是，在應(yīng)用程序?qū)用嫔蟻砜矗�哪些信息如果讓系統(tǒng)知道，能夠更好更高效地執(zhí)行應(yīng)用程序；此外，為了更好地讓系統(tǒng)了解應(yīng)用程序，系統(tǒng)應(yīng)該提供什么樣的接口或者配置讓用戶方便地和系統(tǒng)進行交互。
 總之，我們認(rèn)為，系統(tǒng)和用戶不應(yīng)該是孤立的，系統(tǒng)對用戶也不是完全透明的，同時系統(tǒng)對用戶的應(yīng)用程序也不是一無所知的。系統(tǒng)應(yīng)該多了解用戶的行為和應(yīng)用程序的特點，同時用戶也需要更了解系統(tǒng)。用戶和系統(tǒng)之間的交互應(yīng)該增加。
從數(shù)據(jù)庫領(lǐng)域看系統(tǒng)性能的其他提升空間
 關(guān)于MapReduce和分布式數(shù)據(jù)庫到底有什么不同，是目前人們爭論的一個焦點[  Andrew Pavlo. Erik Paulson. Alexander Rasin etc., A Comparison of Approaches to Large-Scale Data Analysis, proceedings of SIGMOD, 2009.]。數(shù)據(jù)庫通過很多年的發(fā)展對數(shù)據(jù)的存儲和計算，以及用戶使用的語言等等都做了大量的研究并發(fā)展了很多成熟的技術(shù)。但是在MapReduce這樣類似的“云計算”環(huán)境下，數(shù)據(jù)庫的技術(shù)是否在MapReduce系統(tǒng)的研究中可以參考和借鑒，哪些可以參考和借鑒，什么樣的任務(wù)是分布式數(shù)據(jù)庫難以勝任的，什么樣的任務(wù)是MapReduce難以勝任的，他們兩種體系的計算引擎的本質(zhì)區(qū)別到底是什么？這些都是亟待解決的問題，也是人們關(guān)心和爭論的焦點。
 我們針對其中的一些問題，可以進行研究。
 比如索引的使用，在分布式數(shù)據(jù)庫中是很正常和成熟的技術(shù)。MapReduce的系統(tǒng)中是不支持索引的，對于一些任務(wù)來說，如果使用MapReduce的框架來進行處理，將是比較低效的21。但是如何在MapReduce這樣的體系下使用索引還是一個需要研究的問題。
系統(tǒng)易用性
 我們通過日常的使用發(fā)現(xiàn)，MapReduce程序的編寫還是過于底層，通常一些簡單的任務(wù)如日志分析等等需要花費比較長的時間來編寫。對記錄層級的數(shù)據(jù)進行直接處理和使用文件系統(tǒng)作為底層存儲也會對易用性造成一些問題，現(xiàn)在有一些高層語言來處理這些問題，如Pig Latin3等，但是系統(tǒng)的易用性和語言的問題仍然是一個需要不斷研究的問題。
 總結(jié)
 我們介紹了我們的Tplatform的設(shè)計特點，包括TFS和MapReduce，并探討了由于我們設(shè)計的不同導(dǎo)致系統(tǒng)的性能優(yōu)化和設(shè)計折衷。
 然后我們分析了系統(tǒng)的評估目標(biāo)，包括從單任務(wù)延遲、總機器時間、平均結(jié)束時間、加速比、公平性、故障恢復(fù)穩(wěn)定性等多個方面來考察系統(tǒng)的性能和其他各方面表現(xiàn)。
 同時，我們并設(shè)計了一系列的基準(zhǔn)程序和數(shù)據(jù)，從MapReduce的系統(tǒng)體系結(jié)構(gòu)出發(fā)，考慮不同的程序和數(shù)據(jù)如計算密集型、I/O密集型、網(wǎng)絡(luò)密集型等來衡量MapReduce或者類似系統(tǒng)的上述評估目標(biāo)。
 為了達到分析和評估系統(tǒng)的目的，我們在系統(tǒng)中設(shè)計了性能的監(jiān)控和程序概要分析框架，用來收集系統(tǒng)的相關(guān)表現(xiàn)信息。通過對收集的數(shù)據(jù)進行分析，我們可以得到實驗的結(jié)果，并對系統(tǒng)進行分析和給出改善意見。我們還在實驗中分析了程序概要分析框架的開銷，實驗結(jié)果可以看到開銷不大。
 我們設(shè)計了一系列的實驗來對我們的Tplatform進行評估，分析系統(tǒng)中的實際情況。我們發(fā)現(xiàn)網(wǎng)絡(luò)常常成為MapReduce和類似系統(tǒng)的瓶頸，落后者對系統(tǒng)的延遲有很大的影響，系統(tǒng)對短任務(wù)的調(diào)度并不公平等等問題。
 通過實驗和分析，我們發(fā)現(xiàn)了當(dāng)前系統(tǒng)的這些問題，然后我們選取了落后者的問題進行改進。我們針對此問題實現(xiàn)了后備任務(wù)策略，落后者會顯著地造成延遲增大的性能問題。我們的模擬實驗表明，我們的后備任務(wù)能夠有效地改善這一問題。
 最后我們總結(jié)了在分析和日常使用中發(fā)現(xiàn)的問題，并提出了一系列的未來工作方向。

首頁 上一頁 1 2 下一頁 尾頁 2/2/2