- 論壇徽章:
- 0
|
<DIV><A href="http://blog.chinaunix.nethttp://blog.chinaunix.net/attachment/201101/20/25098298_1295516660l888.png" target=_blank></A>摘要：
<P style="TEXT-INDENT: 2em">MapReduce是一個編程模型以及用來處理和生成大數(shù)據(jù)集的一個相關(guān)實現(xiàn)。用戶通過描述一個map函數(shù)，處理一組key/value對進而生成一組key/value對的中間結(jié)果，然后描述一個reduce函數(shù)，將具有相同key的中間結(jié)果進行歸并。正如論文所表明的，很多現(xiàn)實世界中的任務都可以用這個模型來表達。 </P>
<P style="TEXT-INDENT: 2em">以這種函數(shù)式風格寫出來的程序在一個由普通機器組成的集群上自動的進行并行化和執(zhí)行。由一個運行時系統(tǒng)來關(guān)注輸入數(shù)據(jù)的劃分細節(jié)，在機器集合上的程序執(zhí)行調(diào)度，處理機器失敗以及管理所需要的機器間的通信。這就允許那些沒有并行分布式系統(tǒng)編程經(jīng)驗的程序員很容易的使用大型分布式系統(tǒng)的資源。 </P>
<P style="TEXT-INDENT: 2em">我們的MapReduce實現(xiàn)運行在一個有很多普通機器組成的集群上，而且具有高擴展性：一個典型的MapReduce計算將會在一個數(shù)千臺機器的集群上處理很多T的數(shù)據(jù)。對于程序員來說，這個系統(tǒng)很好用，目前已經(jīng)有數(shù)百個MapReduce程序?qū)崿F(xiàn)，在google的集群上每天有上千個MapReduce job在跑。 </P>
<P style="TEXT-INDENT: 2em">1.導引</P>
<P style="TEXT-INDENT: 2em">在過去的五年來，作者和google的其他工程師已經(jīng)實現(xiàn)了數(shù)百了用于特殊目的在大量原始數(shù)據(jù)(比如爬蟲爬的文檔，web訪問日志等等)上進行的運算。為了計算各種類型的衍生數(shù)據(jù)：比如倒排索引，網(wǎng)頁文檔的圖結(jié)構(gòu)的各種不同表示，每個host的網(wǎng)頁數(shù)，給定的一天中最常查詢集合。大部分這樣的計算在概念上都是很直接的。然而由于輸入數(shù)據(jù)通常是很龐大的，因此為了能在合理的時間內(nèi)結(jié)束，計算就不得不分布在成百上千臺機器上執(zhí)行。如何并行化計算，分布數(shù)據(jù)，處理錯誤都會使得原本簡單的計算需要大量額外的代碼去處理這些問題。</P>
<P style="TEXT-INDENT: 2em"> 為了應對這種復雜性，我們設計了一種抽象，使得我們可以表達我們需要執(zhí)行的這種簡單的運算，而將并行化，容錯，數(shù)據(jù)分布，負載平衡這樣的細節(jié)封裝在庫里。我們的抽象源于Lisp以及其他函數(shù)式編程語言中的map-reduce原語。我們發(fā)現(xiàn)我們大部分的計算都是首先在輸入的每條記錄上執(zhí)行一個map操作以產(chǎn)生一個key/value的中間結(jié)果集合，然后為了得到相應的派生數(shù)據(jù)，對那些具有相同key的值應用一個reduce操作。通過使用由用戶描述的map和reduce操作組成的函數(shù)式模型，使得我們很容易的進行計算并行化，同時使用重新執(zhí)行作為基本的容錯機制。</P>
<P style="TEXT-INDENT: 2em">文章的主要貢獻就是提供了一個允許對大規(guī)模計算進行自動并行化以及數(shù)據(jù)分布的簡單有力的接口。同時提供了一個可以在普通pc機組成的大集群上達到很高的性能針對該接口的實現(xiàn)。</P>
<P style="TEXT-INDENT: 2em">第2節(jié)描述了基本的編程模型并且給出了幾個簡單例子。第3節(jié)描述了一個面向我們的基于集群的計算環(huán)境的該接口的實現(xiàn)。第4節(jié)描述了該模型中我們認為很有用的幾個概念。第5節(jié)對我們的實現(xiàn)通過幾個task進行了測試。第6節(jié)介紹了MapReduce在google內(nèi)部的使用，包括使用它重寫我們的產(chǎn)品索引系統(tǒng)的一些經(jīng)驗。第7節(jié)討論了相關(guān)的以及未來的工作。</P>
<P style="TEXT-INDENT: 2em"> 2.編程模型</P>
<P style="TEXT-INDENT: 2em">計算有一個key/value輸入對集合，產(chǎn)生一系列的輸出key/value對。Mapreduce庫的用戶通過兩個函數(shù)：Map和Reduce來表達這個計算。</P>
<P style="TEXT-INDENT: 2em"> Map，由用戶編寫，有一個輸入對，產(chǎn)生一集key/value對的中間結(jié)果。Mapreduce庫將具有相同key(比如I)的那些中間值組織起來，然后將它們傳給Reduce函數(shù)。</P>
<P style="TEXT-INDENT: 2em"> Reduce函數(shù)，也是由用戶編寫，接受一個中間值key(比如I)，以及對應于該key的value集合作為輸入。它將這些value歸并起來形成一個可能更小的value集合。通常每個Reduce調(diào)用產(chǎn)生0個或者1個輸出值。中間值的value集合是通過一個迭代器來提供給用戶的Reduce函數(shù)。這允許我們能處理那些太大以至于無法一次放入內(nèi)存的value列表。</P>
<P style="TEXT-INDENT: 2em"> 2.1例子</P>
<P style="TEXT-INDENT: 2em">考慮在一個大文檔集合中計算單詞出現(xiàn)頻率的問題。用戶可以用類似如下偽代碼的方式來編寫代碼。</P>
<P style="TEXT-INDENT: 2em">map(String key, String value):<BR> // key: document name<BR> // value: document contents<BR> for each word w in value:<BR> EmitIntermediate(w, "1"); </P>
<P style="TEXT-INDENT: 2em">reduce(String key, Iterator values):<BR> // key: a word<BR> // values: a list of counts<BR> int result = 0;<BR> for each v in values:<BR> result += ParseInt(v);<BR> Emit(AsString(result));</P>
<P style="TEXT-INDENT: 2em">Map函數(shù)輸出每個單詞及其相應出現(xiàn)次數(shù)(在這個簡單例子中，就是1)reduce函數(shù)將所有的次數(shù)加起來然后為每一個單詞輸出它。</P>
<P style="TEXT-INDENT: 2em"> 另外用戶還需要向一個MapReduce描述對象中填寫輸入輸出文件名稱以及一些可選的參數(shù)。然后用戶調(diào)用Mapreduce函數(shù)，將該描述對象傳給它。用戶代碼需要鏈接Mapreduce庫(采用c++實現(xiàn))。附錄A包含該例子的完整代碼。</P>
<P style="TEXT-INDENT: 2em"> 2.2類型</P>
<P style="TEXT-INDENT: 2em">盡管前面的例子是以字符串類型作為輸入輸出，概念上來說用戶提供的map和reduce函數(shù)有如下的類型關(guān)聯(lián)；</P>
<P style="TEXT-INDENT: 2em">Map: (k1,v1) -> list(k2,v2)</P>
<P style="TEXT-INDENT: 2em">Reduce: (k2,list(v2)) -> list(v2)</P>
<P style="TEXT-INDENT: 2em">即輸入的key和value與輸出的key value來自于不同的域，另外中間結(jié)果的key value與輸出的key value具有相同的域。｛->前后分別代表了輸入輸出，所以list(k2,v2)代表了中間結(jié)果，可以看到中間結(jié)果與Reduce的key value名稱都是k2,v2,以表示它們具有相同的域。也就是說k1和k2，v1和v2所代表的實際含義可能是不同的，比如url訪問頻率計數(shù),map的輸入就是<logname,log>,而中間結(jié)果與reduce則是<url,出現(xiàn)次數(shù)>｝</P>
<P style="TEXT-INDENT: 2em"> 我們的用戶程序以字符串形式傳遞給或者接受自用戶定義函數(shù)，將字符串與相應類型的轉(zhuǎn)換交給用戶代碼處理。</P>
<P style="TEXT-INDENT: 2em">2.3更多的實例</P>
<P style="TEXT-INDENT: 2em">下面有一些可以使用MapReduce進行計算的簡單而有趣的例子。</P>
<P style="TEXT-INDENT: 2em"> 分布式Grep：map函數(shù)輸出該行如果它與給定的模式匹配。Reduce函數(shù)只需要將給定的中間結(jié)果輸出。</P>
<P style="TEXT-INDENT: 2em"> url訪問頻率計數(shù)：map函數(shù)處理網(wǎng)頁訪問日志，輸出<URL,1>。Reduce函數(shù)將相同URL的value加起來，然后輸出<URL,total count>對。</P>
<P style="TEXT-INDENT: 2em"> 網(wǎng)頁鏈接逆向圖：map函數(shù)輸入<target,source>對表示從網(wǎng)頁source到target URL的一條鏈接。Reduce函數(shù)將給定Target URL的所有source URL連接到一塊，然后輸出<target,list(source)>。</P>
<P style="TEXT-INDENT: 2em"> Host短語向量：一個term vector是指出現(xiàn)在一個文檔或者文檔集合中的最重要的單詞的<word,frequency>對列表。Map函數(shù)對每一個文檔輸出<hostname,term vector>(host是從該文檔對應的url中抽取出來)。Reduce函數(shù)接受到一個給定host的所有文檔的term vector。它將這些term vector合并，并扔掉不常出現(xiàn)的那些terms，然后輸出一個最終的<hostname,term vector>對。</P>
<P style="TEXT-INDENT: 2em"> 倒排索引：map函數(shù)解析每個文檔，輸出一個<word,docid>對序列。Reduce函數(shù)接受一個給定word的所有序列，對相應的docid進行排序，輸出一個<word,list(docid)>。所有的輸出對集合就形成了一個簡單的倒排索引。通過很簡單的改動，我們就可以讓這個計算同時記住單詞的在文檔中的出現(xiàn)位置。</P>
<P style="TEXT-INDENT: 2em"> 分布式排序：map函數(shù)從每條記錄中提取key，然后簡單的輸出<key,record>對。Reduce函數(shù)原樣地輸出所有的對。該計算依賴于4.1節(jié)描述的劃分功能以及4.2節(jié)描述的排序?qū)傩浴?lt;/P>
<P style="TEXT-INDENT: 2em"> 3.實現(xiàn)</P>
<P style="TEXT-INDENT: 2em">對于MapReduce接口可以有很多不同的實現(xiàn)。正確的選擇依賴于環(huán)境。比如一個實現(xiàn)可能適用于小型共享內(nèi)存機器，另一個可能適用于一個大的NUMA多處理機，另一個適用于更大的通過網(wǎng)絡互聯(lián)的集群。</P>
<P style="TEXT-INDENT: 2em"> 本節(jié)描述一個面向google內(nèi)部廣泛使用的計算環(huán)境(由普通pc通過以太網(wǎng)交換機連接而成的大集群)的實現(xiàn)。在我們的環(huán)境里：</P>
<P style="TEXT-INDENT: 2em">1. 機器主要是運行l(wèi)inux的雙核x86處理器，每臺機器具有2-4GB內(nèi)存</P>
<P style="TEXT-INDENT: 2em">2. 使用通用的網(wǎng)絡硬件：在機器級別上，通常不是100Mbps就是1Gbps，平均下來，整體的等分帶寬要低些。</P>
<P style="TEXT-INDENT: 2em">3. 集群由成百上千臺機器組成，因此失敗變得很普通</P>
<P style="TEXT-INDENT: 2em">4. 存儲是由連接到單個機器上的廉價的IDE硬盤提供的。一個內(nèi)部開發(fā)的分布式文件系統(tǒng)被用來管理存儲在硬盤上的數(shù)據(jù)。文件系統(tǒng)通過備份來為不可靠的硬件提供可用性和可靠性。</P>
<P style="TEXT-INDENT: 2em">5. 用戶提交job到調(diào)度系統(tǒng)。每個job由一組task組成，job被調(diào)度系統(tǒng)映射到集群中的一組可用機器集合上去執(zhí)行。</P>
<P style="TEXT-INDENT: 2em"> 3.1 執(zhí)行概覽</P>
<P style="TEXT-INDENT: 2em">通過自動將輸入數(shù)據(jù)劃分為M個片段，使得Map調(diào)用可以跨越多個機器執(zhí)行。這些輸入片段可以被不同的機器并行處理。Reduce調(diào)用的分布，是通過使用一個劃分函數(shù)(比如hash(key) mod R)將中間結(jié)果的key的值域空間劃分為R個片段。片段的個數(shù)R以及劃分函數(shù)都是由用戶描述的。</P>
<P style="TEXT-INDENT: 2em"> 圖1展示了一個MapReduce操作在我們的實現(xiàn)中的整體流程。當用戶程序調(diào)用MapReduce函數(shù)時，將會產(chǎn)生如下的動作序列(圖中的標號與如下描述中的數(shù)字相對應)：</P>
<P style="TEXT-INDENT: 2em"><A href="http://blog.chinaunix.nethttp://blog.chinaunix.net/attachment/201101/20/25098298_1295516532Hxdh.png" target=_blank><IMG src="http://blog.chinaunix.nethttp://blog.chinaunix.net/attachment/201101/20/25098298_1295516532Hxdh.png" border=0 ; .load="imgResize(this, 650);"></A></P>
<P style="TEXT-INDENT: 2em"></P>
<P style="TEXT-INDENT: 2em">1. 用戶程序中的MapReduce庫首先將輸入文件切分為M個片段(每個片段大小通常是16MB到64MB，該大小用戶可以通過一個配置參數(shù)控制)。然后在一組機器集上啟動該程序的所有拷貝。</P>
<P style="TEXT-INDENT: 2em">2. 在這些程序拷貝中有一個是特殊的：the master。其余的是稱為worker，由master為它們分配任務�？偣灿蠱個map task和R個reduce task需要分配。Master選擇空閑的worker，給它們每個分配一個map或者reduce task。</P>
<P style="TEXT-INDENT: 2em">3. 被分配了map task的worker讀取相應的輸入片段內(nèi)容。它從輸入中解析出key/value對的集合，將每個對傳遞給用戶定義的map函數(shù)處理。由map函數(shù)生成的中間結(jié)果被緩存在內(nèi)存里。</P>
<P style="TEXT-INDENT: 2em">4. 被緩存的那些對，通過劃分函數(shù)被分成R個區(qū)域，然后周期性的被寫入本地磁盤。然后將這些緩存對在本地磁盤上的位置返回給master，master再負責將這些位置信息傳遞給reduce worker。</P>
<P style="TEXT-INDENT: 2em">5. 當一個reduce worker被master通知了這些位置信息后，它就使用RPC調(diào)用去map worker的本地磁盤里讀取這些緩沖數(shù)據(jù)。當一個reduce worker已經(jīng)讀取了所有的緩沖數(shù)據(jù)后，它就將它們根據(jù)key值進行排序，以讓具有相同key值的被組織在一塊。排序是需要的因為通常很多不同的key值會被映射到同一個reduce task。如果中間結(jié)果的數(shù)據(jù)量太大以至于無法放入內(nèi)存，就需要進行外排序。</P>
<P style="TEXT-INDENT: 2em">6. Reduce worker在排好序的中間結(jié)果數(shù)據(jù)上迭代，對于碰到的每個唯一的中間key值，它就將該key值，以及與它對應的value集合傳遞給用戶定義的reduce函數(shù)。該reduce函數(shù)的輸出會被append到這個reduce worker的最終輸出文件上。</P>
<P style="TEXT-INDENT: 2em">7. 當所有的map task和reduce task完成后，master喚醒用戶程序。這時用戶程序從MapReduce調(diào)用里返回。</P>
<P style="TEXT-INDENT: 2em"> 成功完成后，MapReduce執(zhí)行結(jié)果將會產(chǎn)生R個輸出文件(一個reduce task對應一個，文件名由用戶指定)。通常，用戶不需要將這R個輸出文件合并為一個文件，它們通常會作為另一個MapReduce調(diào)用的輸入�；蛘咄ㄟ^另一個可以處理輸入是劃分為多個文件的分布式應用程序來使用它們。</P>
<P style="TEXT-INDENT: 2em"> 3.2 master數(shù)據(jù)結(jié)構(gòu)</P>
<P style="TEXT-INDENT: 2em">Master保存了幾個數(shù)據(jù)結(jié)構(gòu)。對于每個map和reduce task，它會保存它們的狀態(tài)(空閑,處理中，完成)以及worker所在機器的標識(針對非空閑task)。｛注意task與work之間的關(guān)系，不是一對一的，一個worker可能處理多個task｝</P>
<P style="TEXT-INDENT: 2em"> Master是將中間結(jié)果文件位置從map task傳遞到reduce task的渠道。因此對于每個完成的map task，master會保存由它產(chǎn)生的R個中間結(jié)果文件的大小及位置。當map task結(jié)束后，將會收到對于這些位置和大小信息的更新。這些信息又會被逐步推送給那些包含正在處理中的reduce task的worker。</P>
<P style="TEXT-INDENT: 2em"> 3.3 容錯</P>
<P style="TEXT-INDENT: 2em">因為MapReduce庫是設計用來幫助在成百上千臺集群上處理大量數(shù)據(jù)的，所以這個庫就必須能夠優(yōu)雅地容忍機器失敗。</P>
<P style="TEXT-INDENT: 2em"> Worker失敗</P>
<P style="TEXT-INDENT: 2em">Master周期性的ping每個worker。如果在一定時間內(nèi)沒有收到某個worker的響應，就會把它標記為失敗。由該worker執(zhí)行完成的那些map task{注意reduce task不需要}都必須重置為空閑狀態(tài)。這樣，它們就又可以被調(diào)度到其他的worker上重新執(zhí)行。類似的，那些該woker上執(zhí)行中的任何map reduce task{注意reduce task也需要}，必須重置為空閑狀態(tài)，重新加入調(diào)度。</P>
<P style="TEXT-INDENT: 2em">已經(jīng)完成的map task需要重新執(zhí)行，是因為它們的輸出被存儲在失敗的那臺機器的本地磁盤上，因此就變成了不可訪問的。已經(jīng)完成的reduce task不需要重新執(zhí)行，是因為它們的輸出存放在一個全局文件系統(tǒng)上。</P>
<P style="TEXT-INDENT: 2em">當一個map task首先由work A執(zhí)行，然后又有worker B執(zhí)行(因為A失敗了)。所有正在執(zhí)行reduce task的worker都會收到該重新執(zhí)行的通知。任何已經(jīng)不能從worker A讀數(shù)據(jù)的reduce task都將會從worker B讀取。</P>
<P style="TEXT-INDENT: 2em"> MapReduce可以很有效的應對大規(guī)模的worker失敗。比如，在一個MapReduce操作期間，在一個運行中的集群上的網(wǎng)絡維護可能導致80臺機器幾分鐘內(nèi)同時無法訪問。MapReduce master簡單的重新執(zhí)行那些不可達機器上的任務。繼續(xù)推進整個計算過程，最后完成該MapReduce操作。</P>
<P style="TEXT-INDENT: 2em"> Master失敗</P>
<P style="TEXT-INDENT: 2em">很容易讓master寫入上面描述的數(shù)據(jù)結(jié)構(gòu)的周期性檢查點。如果master死掉后，就可以從上次的檢查點狀態(tài)開始啟動一個新的拷貝。然而，由于只有一個master，而且它的失敗也是不太可能的{很明顯如果有多個master，那么失敗的概率就會大大上升}，因此在我們當前的實現(xiàn)中，如果master失敗我們就結(jié)束MapReduce計算。在這種情況下，客戶端可以進行檢查，如果需要可以重試它們的MapReduce操作。</P>
<P style="TEXT-INDENT: 2em">失敗出現(xiàn)時語義</P>
<P style="TEXT-INDENT: 2em">當用戶提供的map和reduce函數(shù)，針對它們的輸入是一個確定性函數(shù)時，我們的分布式實現(xiàn)應該與整個程序串行執(zhí)行時產(chǎn)生相同的輸出。</P>
<P style="TEXT-INDENT: 2em"> 我們通過map和reduce task輸出的原子性提交來實現(xiàn)這個屬性。每個執(zhí)行中的task將它們的輸出寫入私有的temp文件里。一個Reduce task產(chǎn)生一個這樣的文件，一個map task產(chǎn)生R個這樣的文件。當一個map task完成后，worker會給master發(fā)送一個包含這個R個temp文件名稱的消息。如果master收到一個已經(jīng)完成的map task的完成消息，它會忽略該消息。否則，它會將這個R個文件的名稱記錄在自己的一個數(shù)據(jù)結(jié)構(gòu)中。</P>
<P style="TEXT-INDENT: 2em">當reduce task完成后，reduce worker會自動把temp輸出文件重命名為最終的輸出文件。如果相同的reduce task在多個機器上執(zhí)行，多個重命名操作將會在同一個最終輸出文件上執(zhí)行。我們依賴于底層文件系統(tǒng)提供的原子性的重命名操作來保證最終的文件系統(tǒng)中只會包含一個reduce task執(zhí)行產(chǎn)生的數(shù)據(jù)。</P>
<P style="TEXT-INDENT: 2em"> map和reduce函數(shù)是確定性的以及等價于相同情況下串行執(zhí)行結(jié)果的語義，主要優(yōu)點是使得程序員可以很容易地理解程序的行為。當map和reduce操作不是確定性的時候，我們提供了雖然弱些但是仍然合理的語義。在出現(xiàn)不確定性操作時，一個特殊的reduce task R1的輸出等價于該非確定性程序針對R1的串行執(zhí)行輸出。但是對于另一個reduce task R2，就可能對應另一個不同的非確定性程序的串行執(zhí)行結(jié)果。</P>
<P style="TEXT-INDENT: 2em"> 考慮map task M和reduce task R1和R2.讓e(Ri)代表已經(jīng)完成的Ri的執(zhí)行過程。語義可能會變得更弱，因為e(R1)可能讀取了M某次執(zhí)行的輸出結(jié)果，而e(R2)可能讀取了M另一次執(zhí)行的輸出。{首先M是不確定性的，其次M可能被重新執(zhí)行過，這樣R1 R2雖然讀的是同一個task的輸出，但是可能讀取了不同的輸出結(jié)果}。</P>
<P style="TEXT-INDENT: 2em"> 3.4 局部性</P>
<P style="TEXT-INDENT: 2em">在我們的計算環(huán)境中，網(wǎng)絡帶寬是相對寶貴的。我們通過利用輸入數(shù)據(jù)(由GFS管理)是存儲在機器的本地磁盤上的這一事實來節(jié)省網(wǎng)絡帶寬。GFS將每個文件劃分為64MB大小的塊，每個塊的幾個副本存儲在不同的機器上。MapReduce master充分考慮輸入文件的位置信息，盡量將一個map task調(diào)度到包含相應的輸入數(shù)據(jù)副本的那個機器上。如果不行，就嘗試將map task調(diào)度到該task的輸入數(shù)據(jù)附近的那些機器(比如讓worker所在的機器與包含該數(shù)據(jù)的機器在同一個網(wǎng)絡交換機上)。當在一個集群上運行一個具有很多worker的大型MapReduce操作時，大部分的輸入數(shù)據(jù)都是從本地讀取的，很少消耗網(wǎng)絡帶寬。</P>
<P style="TEXT-INDENT: 2em"> 3.5 任務粒度</P>
<P style="TEXT-INDENT: 2em">如上所述，我們將map階段劃分為M個片段，將reduce階段劃分為R個片段。理想情況下，M和R都應當遠遠大于運行worker的機器數(shù)目。讓每個worker執(zhí)行很多不同的task可以提高動態(tài)負載平衡，也能加速worker失敗后的恢復過程：它已經(jīng)完成的很多map task可以傳給所有其他機器。在我們的實現(xiàn)中M和R到底可以多大，有一些實際的限制。因為master必須進行O(M+R)個調(diào)度決定以及在內(nèi)存中保存O(M*R)個狀態(tài)｛即每個map task的R個輸出文件的位置信息，總共M個task，所以是M*R｝。 (但是關(guān)于內(nèi)存使用的常數(shù)因子是很小的：O(M*R)個狀態(tài)大概由每個map task/reduce 對的一字節(jié)數(shù)據(jù)組成)。</P>
<P style="TEXT-INDENT: 2em"> 另外，R通常會被用戶限制，因為每個reduce task的輸出在不同的輸出文件中。在實際中，我們通常這樣選擇M：使每個獨立task輸入數(shù)據(jù)限制在16MB到64MB之間(這樣上面所說的本地化優(yōu)化是最有效的)。我們讓R大概是我們將要使用的worker機器的幾倍。我們通常這樣執(zhí)行MapReduce操作，在有2000個worker機器時，讓M = 20000,R = 5000。</P>
<P style="TEXT-INDENT: 2em"> 3.6 備份任務</P>
<P style="TEXT-INDENT: 2em">一個影響MapReduce操作整體執(zhí)行時間的最常見的因素是”掉隊者”(花費相當長時間去完成MapReduce操作中最后剩下的極少數(shù)的那幾個task的那臺機器)。有很多原因可以導致掉隊者的出現(xiàn)。比如：具有一塊壞硬盤的機器可能會經(jīng)歷頻繁的可修正錯誤而使得IO性能從30MB/s降低到1MB/s。集群調(diào)度系統(tǒng)可能會將那些引發(fā)CPU 內(nèi)存 本地磁盤或者網(wǎng)絡帶寬等資源競爭的task調(diào)度到同一臺機器上。我們最近見過的一個錯誤是由于機器初始化代碼中的一個bug引起的處理器緩沖失靈，使得受影響的機器上的計算性能降低了一百倍。</P>
<P style="TEXT-INDENT: 2em"> 我們有一個可以緩解這種掉隊者問題的通用機制。當MapReduce操作接近尾聲的時候，master會備份那些還在執(zhí)行中的task。只要該task的主本或者其中的一個副本完成了，我們就認為它完成了。通過采用這種機制，我們只使計算資源的利用率增長了僅僅幾個百分點，但是明顯地降低了完成整個MapReduce操作所需的時間。比如，在5.3節(jié)描述的排序例子中，如果不啟用這個機制，整個完成時間將會增長53%。</P>
<P style="TEXT-INDENT: 2em"> 4.概念</P>
<P style="TEXT-INDENT: 2em">盡管通過簡單書寫map和reduce函數(shù)提供的基本功能對于我們大部分的應用來說足夠了，我們也發(fā)現(xiàn)了其中的一些擴展也很有用。這一節(jié)，我們就來描述下它們。</P>
<P style="TEXT-INDENT: 2em"> 4.1 劃分函數(shù)</P>
<P style="TEXT-INDENT: 2em">MapReduce用戶指定他們期望的reduce task(也可以說輸出文件)的數(shù)目R。任務產(chǎn)生的數(shù)據(jù)通過在中間結(jié)果的key上使用一個劃分函數(shù)被劃分開。系統(tǒng)提供一個使用hash的默認的劃分函數(shù)(比如 “hash(key) mod R”)。然而在某些情況下，使用關(guān)于key的其他函數(shù)進行劃分更有用。比如有時候輸入是URL，我們希望來自相同host的輸入可以存放在相同的輸出文件上。為了支持這種情況，MapReduce庫的用戶必須提供一個特殊的劃分函數(shù)。比如使用”hash(Hostname(urlkey)) mod R”作為劃分函數(shù)，就可以讓來自相同host的所有URL落在同一個輸出文件上。</P>
<P style="TEXT-INDENT: 2em"> 4.2 排序保證</P>
<P style="TEXT-INDENT: 2em">我們保證在一個給定的劃分內(nèi)，作為中間結(jié)果的key/value對是按照key值的增序進行處理的。這種有序化保證可以讓每個劃分的輸出文件也是有序的。而這在輸出文件格式需要支持按照key的有效的隨機查找時非常有用，或者輸出用戶也會發(fā)現(xiàn)讓對這些數(shù)據(jù)進行排序會很方便。</P>
<P style="TEXT-INDENT: 2em"> 4.3 合并函數(shù)</P>
<P style="TEXT-INDENT: 2em">某些情況下，map task產(chǎn)生的中間結(jié)果有很多具有相同key的重復值，而且用戶指定的reduce函數(shù)又滿足交換率和結(jié)合率。一個很好的例子就是2.1節(jié)里描述的wordcount的例子。因為單詞頻率的分布傾向于遵循Zipf分布，每個map task將會產(chǎn)生成百上千個相同的記錄比如<the,1>這樣的。而所有的這些又將會通過網(wǎng)絡傳遞給一個reduce task，然后通過reduce函數(shù)將它們累加起來。我們允許用戶描述一個combiner函數(shù)，在數(shù)據(jù)通過網(wǎng)絡發(fā)送之前對它們進行部分的歸并。</P>
<P style="TEXT-INDENT: 2em"> Combiner函數(shù)在每個執(zhí)行map task的機器上這些。通常用來實現(xiàn)combiner和reduce函數(shù)的代碼是相同的。唯一的不同在MapReduce庫如何處理它們的輸出。一個reduce函數(shù)的輸出將會被寫到最終的輸出文件，而combiner函數(shù)的輸出會被寫到一個將要發(fā)送給reduce task的中間結(jié)果文件中。</P>
<P style="TEXT-INDENT: 2em">4.4 輸入和輸出類型</P>
<P style="TEXT-INDENT: 2em">MapReduce庫提供了幾種不同格式的輸入數(shù)據(jù)支持。比如”text”輸入模式：將每一行看做一個key/value對，key是該行的offset，value是該行的內(nèi)容。另一個支持的模式是一個根據(jù)key排序的key/value對的序列。每個輸入類型知道如何將它們自己通過有意義的邊界劃分，然后交給獨立的map task處理(比如text模式，會保證劃分只會發(fā)生在行邊界上)。用戶可以通過提供一個reader接口的實現(xiàn)來支持新的輸入類型。對于大多數(shù)用戶來說，僅僅使用那些預定義的輸入類型就夠用了。</P>
<P style="TEXT-INDENT: 2em"> 一個reader并不是必須從文件讀數(shù)據(jù)。比如可以簡單的定義一個從數(shù)據(jù)庫或者是內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)中讀記錄的reader。</P>
<P style="TEXT-INDENT: 2em"> 與之類似，我們也提供一組輸出類型用于控制輸出數(shù)據(jù)格式，同時用戶也很容易添加對于新的輸出類型的支持。</P>
<P style="TEXT-INDENT: 2em"> 4.5 副作用</P>
<P style="TEXT-INDENT: 2em">MapReduce的用戶發(fā)現(xiàn)某些情況下，在map和reduce操作中順便產(chǎn)生一個文件作為額外的輸出會很方便。這些的副作用是原子性以及冪等性依賴于應用程序編寫者。通常應用程序編寫者會寫一個temp文件，一旦它已經(jīng)生成完畢再將它原子性的重命名。</P>
<P style="TEXT-INDENT: 2em"> 我們并不為單個task產(chǎn)生的多個輸出文件提供原子性的兩階段提交。因此那些具有跨文件一致性需求的產(chǎn)生多個輸出文件的task應當是確定性的。這個限制在實際中還沒有引起什么問題。</P>
<P style="TEXT-INDENT: 2em"> 4.6 跳過壞記錄</P>
<P style="TEXT-INDENT: 2em">有時候用戶代碼中的一些bug會導致Map或者Reduce函數(shù)在處理某個特定記錄時一定會crash。這樣的bug會使得MapReduce操作無法車成功完成。通常的處理方法是修復這個bug，但是有時候這樣做顯得并不靈活。因為bug可能是存在于第三方的庫里，但是源代碼是不可用的。而且有時候忽略一些記錄是可以接受的，比如在一個大數(shù)據(jù)集上進行統(tǒng)計分析時。我們提供了一種可選的執(zhí)行模式，在該模式下，MapReduce庫會檢測那些記錄引發(fā)了該crash，然后跳過它們繼續(xù)前進。</P>
<P style="TEXT-INDENT: 2em"> 每個worker進程安裝了一個信號處理器捕獲那些段錯誤和總線錯誤。在調(diào)用用戶Map或者Reduce操作之前，MapReduce庫使用一個全局變量存儲該參數(shù)的序列號。如果用戶代碼產(chǎn)生了一個信號，信號處理器就會發(fā)送一個包含該序列號的”last gasp”的UDP包給master。當master發(fā)現(xiàn)在同一記錄上發(fā)生了不止一次失敗后，當它在相應的Map或者Reduce task重新執(zhí)行時，它就會指出該記錄應該被跳過。</P>
<P style="TEXT-INDENT: 2em"> 4.7 本地化執(zhí)行</P>
<P style="TEXT-INDENT: 2em">在Map和Reduce函數(shù)上進行調(diào)試會變得很有技巧，因為實際的計算發(fā)生在分布式系統(tǒng)上，通常是幾百臺機器，而且工作分配是有master動態(tài)決定的。為了降低debug，profile的難度以及進行小規(guī)模測試，我們開發(fā)了一個MapReduce庫的變更實現(xiàn)，讓MapReduce操作的所有工作在本地計算機上可以串行執(zhí)行。用戶可以控制將計算放在特殊的map task上執(zhí)行。用戶通過使用一個特殊的flag調(diào)用它們的程序，然后就可以簡單的使用他們的調(diào)試和測試工具(比如gdb)。</P>
<P style="TEXT-INDENT: 2em"> 4.8 狀態(tài)信息</P>
<P style="TEXT-INDENT: 2em">Master運行一個內(nèi)部的http服務器，然后發(fā)布一些用戶可以查看的狀態(tài)頁面。這些狀態(tài)頁面展示了計算的進度，比如已經(jīng)有多少任務完成，多少還在執(zhí)行中，輸入字節(jié)數(shù)，中間數(shù)據(jù)的字節(jié)數(shù)，輸出的字節(jié)數(shù)，處理速率等等。該頁面也會包含指向每個task的標準錯誤和標準輸出文件的鏈接。用戶可以使用這些數(shù)據(jù)來預測該計算還要花費多少時間，是否還需要為該計算添加更多的資源。計算遠遠低于預取時，這些頁面也可以用來發(fā)現(xiàn)這些情況。</P>
<P style="TEXT-INDENT: 2em"> 另外，更高級別的狀態(tài)頁會展示那些worker失敗了，當它們失敗時在處理哪些map和reduce task。在診斷用戶代碼中的bug時，這些信息都是很有用的。</P>
<P style="TEXT-INDENT: 2em"> 4.9 計數(shù)器</P>
<P style="TEXT-INDENT: 2em">MapReduce庫提供了一些計數(shù)器設施來計算各種事件的發(fā)生。比如用戶代碼可能想計算處理的單詞的總數(shù)，或者被索引的德語文檔的個數(shù)等等。 </P>
<P style="TEXT-INDENT: 2em">為了使用這些設施，用戶代碼需要創(chuàng)建一個命名計數(shù)器對象然后在Map 和/或 Reduce函數(shù)中累加這些計數(shù)器。比如：</P>
<P style="TEXT-INDENT: 2em">Counter* uppercase;</P>
<P style="TEXT-INDENT: 2em">uppercase = GetCounter("uppercase");</P>
<P style="TEXT-INDENT: 2em">map(String name, String contents):</P>
<P style="TEXT-INDENT: 2em">for each word w in contents:</P>
<P style="TEXT-INDENT: 2em">if (IsCapitalized(w)):</P>
<P style="TEXT-INDENT: 2em">uppercase->Increment();</P>
<P style="TEXT-INDENT: 2em">EmitIntermediate(w, "1");</P>
<P style="TEXT-INDENT: 2em"> 來自獨立worker機器的計數(shù)器的值將會周期性的發(fā)送給master(通過對master的ping的響應捎帶過去)。Master將那些成功的map和reduce task的計數(shù)器值聚集，當MapReduce操作結(jié)束后，將它們返回給用戶代碼。當前的計數(shù)器值也會在master的狀態(tài)頁面上顯示出來，這樣用戶就可以看到計算的實時進展。在計算計數(shù)器值時，master會忽略掉那些重復執(zhí)行的相同map或者reduce task的值，以避免重復計數(shù)。(重復執(zhí)行可能是由于備份任務的使用或者是task失敗引發(fā)的重新執(zhí)行而引起的。)</P>
<P style="TEXT-INDENT: 2em"> 一些計數(shù)器值是由MapReduce庫自動維護的，比如已經(jīng)處理的輸入key/vaule 對的個數(shù)，已經(jīng)產(chǎn)生的輸出key/vaule 對的個數(shù)。</P>
<P style="TEXT-INDENT: 2em"> 用戶發(fā)現(xiàn)計數(shù)器設施對于MapReduce操作的行為的完整性檢查是非常有用的。比如，在某些MapReduce操作中，用戶代碼可能想確定已產(chǎn)生的輸出對的數(shù)目是否剛好等于已處理的輸入對數(shù)目，或者已經(jīng)被處理的德語文檔在已處理的文檔中是否在一個合理的比例上。</P>
<P style="TEXT-INDENT: 2em">5.性能</P>
<P style="TEXT-INDENT: 2em">在本節(jié)中我們將通過運行在大集群的機器上的兩個計算來測量MapReduce的性能。一個計算在大概1TB的數(shù)據(jù)中搜索給定模式的文本。另一個計算對接近1T的數(shù)據(jù)進行排序。 </P>
<P style="TEXT-INDENT: 2em">這兩個程序就可以代表MapReduce用戶所寫的實際程序中的大部分子集：一類是將數(shù)據(jù)從一種表現(xiàn)形式轉(zhuǎn)換為另一種表現(xiàn)形式的程序，另一類就是從一個大數(shù)據(jù)集合中抽取少量感興趣的數(shù)據(jù)集。 </P>
<P style="TEXT-INDENT: 2em">5.1 集群配置</P>
<P style="TEXT-INDENT: 2em">所有的程序都是在一個由將近1800臺機器組成的集群上執(zhí)行。每臺機器有2個打開了超線程的2G Intel Xeon處理器，4GB內(nèi)存，2個160GB IDE硬盤，一個gigabit 以太網(wǎng)鏈路。這些機器安排在一個兩級的樹形交換網(wǎng)絡上，根節(jié)點具有接近100-200 Gbps的總體帶寬。所有機器具有相同的配置，因此在任意兩個機器間的往返時間小于1ms。 </P>
<P style="TEXT-INDENT: 2em">在4GB內(nèi)存中，大概1-1.5G內(nèi)存預留給在集群上運行的其他task。程序在一個周末的下午執(zhí)行，此時cpu 硬盤 網(wǎng)絡接近空閑。</P>
<P style="TEXT-INDENT: 2em"> 5.2 Grep</P>
<P style="TEXT-INDENT: 2em">Grep程序通過掃描10^10個100字節(jié)的記錄，查找一個很少出現(xiàn)的三字符模式(該模式出現(xiàn)在92337個記錄里)。輸入被劃分為近似64MB大小的片段(M=15000)，整個輸出被放在一個文件中(R=1)。</P>
<P style="TEXT-INDENT: 2em"> <A href="http://blog.chinaunix.nethttp://blog.chinaunix.net/attachment/201101/20/25098298_1295516660l888.png" target=_blank><IMG src="http://blog.chinaunix.nethttp://blog.chinaunix.net/attachment/201101/20/25098298_1295516660l888.png" border=0 ; .load="imgResize(this, 650);"></A></P>
<P style="TEXT-INDENT: 2em"></P>
<P style="TEXT-INDENT: 2em">圖2展示了整個計算的處理過程。Y軸表示輸入數(shù)據(jù)的掃描速率。伴隨這安排用于進行該MapReduce操作的機器數(shù)的增多，該速率也在逐漸攀升，當有1764個worker被分配該任務后達到了30GB/s的峰值。當map task結(jié)束后，該速率開始下降，大概在80秒的時候基本上降為0。整個計算過程花費了接近150秒，這包括一分鐘的啟動時間(這個開銷主要是由將程序傳輸給所有worker，與GFS交互以打開1000個輸入文件以及得到本地化優(yōu)化所需要的信息造成的)。</P>
<P style="TEXT-INDENT: 2em"> 5.3 排序</P>
<P style="TEXT-INDENT: 2em">排序程序?qū)?0^10個100字節(jié)的記錄進行排序(接近1TB數(shù)據(jù))。這個程序根據(jù)TeraSort Benchmark進行了建模。</P>
<P style="TEXT-INDENT: 2em"> 排序程序總共由不到50行用戶代碼組成。Map函數(shù)只有3行，將10字節(jié)長的排序用key值從一個文本行中抽取出來，然后輸出該key，以及原始的文本行，作為中間結(jié)果key/value對。我們使用內(nèi)建的Identity函數(shù)作為reduce操作。該函數(shù)將中間結(jié)果不過任何改變地輸出。最后的排好序的結(jié)果寫到一個具有2個副本的GFS文件集合上(即該程序?qū)a(chǎn)生2TB的輸出)。</P>
<P style="TEXT-INDENT: 2em"> 與之前的類似，輸入數(shù)據(jù)被劃分為64MB的片段(M=15000)。排好序的輸出被劃分為4000個輸出(R=4000)。劃分函數(shù)使用key的字節(jié)表示來將它們劃分為R個片段。</P>
<P style="TEXT-INDENT: 2em"> 對于該benchmark的劃分函數(shù)建立在對于key值分布的了解上。對于一個通常的排序問題里，我們會增加一個預先進行的MapReduce操作，該操作會收集key值的采樣值，然后使用這些key值的采樣來計算最終排序序列的劃分點。</P>
<P style="TEXT-INDENT: 2em"> <A href="http://blog.chinaunix.nethttp://blog.chinaunix.net/attachment/201101/20/25098298_12955171706jJE.png" target=_blank><IMG src="http://blog.chinaunix.nethttp://blog.chinaunix.net/attachment/201101/20/25098298_12955171706jJE.png" border=0 ; .load="imgResize(this, 650);"></A></P>
<P style="TEXT-INDENT: 2em"></P>
<P style="TEXT-INDENT: 2em">圖3(a)展示了該排序程序的一個正常的處理過程。左上角的圖表示輸入速率。峰值速率大概是13GB/s，由于所有的map task在200秒前都結(jié)束了，所以該速率下降的很快�？梢钥吹剑斎胨俾室∮趃rep。這是因為排序的map task花費了大概一半的時間和IO帶寬將中間結(jié)果寫入到本地硬盤上。而與之相比，grep的中間結(jié)果輸出幾乎可以忽略不及。</P>
<P style="TEXT-INDENT: 2em"> 左邊中間的圖展示了數(shù)據(jù)從Map task向reduce task的網(wǎng)絡傳輸速率。當?shù)谝粋�map task完成后，shuffling就開始了。圖中的第一個峰值是由于第一批的1700個reduce task都啟動后產(chǎn)生的(整個MapReduce操作被分配給大概大概1700個機器，每個機器同一時刻最多執(zhí)行一個Reduce task)。大體上在300秒的時候，這一批的reduce task結(jié)束，然后啟動了剩余的reduce task的shffling過程。大概在600秒時，這些shuffling才結(jié)束。</P>
<P style="TEXT-INDENT: 2em"> 左邊最底下的圖形展示了reduce task將排好序的數(shù)據(jù)寫入最終輸出文件的速率。在第一次的shuffling的結(jié)束與數(shù)據(jù)寫入開始之間存在一個延時，是因為機器此時正忙著對中間數(shù)據(jù)進行排序。寫入過程在一段時間內(nèi)大概持續(xù)著大概2-4GB/s的速率。所有的寫入大概在850秒的時候結(jié)束。假設啟動的花費，整個計算花費了891秒。這接近于當前Terasort benchmark的最快結(jié)果1057秒。</P>
<P style="TEXT-INDENT: 2em"> 另外需要指出的是：輸入速率比shuffle速率和輸出速率高是因為我們的本地化優(yōu)化(大部分的數(shù)據(jù)都是從本地硬盤讀取的，這就繞過了網(wǎng)絡帶寬的限制)。Shuffle速率比輸出速率高是因為輸出階段要寫兩份拷貝(保存兩份是為了可靠性和可用性){這兩份拷貝是需要耗費網(wǎng)絡帶寬的}。寫兩個副本是因為這是我們的底層文件系統(tǒng)提供的可靠性和可用性機制。如果底層文件系統(tǒng)使用了erasure code而不是副本，對于寫數(shù)據(jù)的網(wǎng)絡帶寬需求將會減少。</P>
<P style="TEXT-INDENT: 2em"> 5.4 任務備份的影響</P>
<P style="TEXT-INDENT: 2em">在圖3(b),我們展示了一個沒有開啟任務備份的排序程序的執(zhí)行過程。執(zhí)行流類似與我們在圖3(a)里看到的那樣。除了在繁重的寫活動出現(xiàn)后出現(xiàn)了一個長尾。在960秒時，只剩下5個reduce task還沒有完成。然而這些掉隊者，在300秒后才完成。整個計算花費了1283秒，增加了44%。</P>
<P style="TEXT-INDENT: 2em">5.5 機器失敗</P>
<P style="TEXT-INDENT: 2em">圖3(c),展示了我們在計算執(zhí)行幾分鐘后，殺掉1746個worker里面的200個后的執(zhí)行過程。底層的集群調(diào)度器，立刻重啟在這些機器上的worker進程(因為只是進程被殺掉了，機器仍然是可用的)。</P>
<P style="TEXT-INDENT: 2em"> 死掉的worker作為負的輸入速率進行顯示，因為前面以及完成的map task的工作都消失了需要重新執(zhí)行。Map task的重新執(zhí)行相對較快。加上啟動時間，整個計算過程在933秒的時候結(jié)束，僅僅比正常情況下的執(zhí)行時間增加了5%。</P>
<P style="TEXT-INDENT: 2em"> 6. 經(jīng)驗</P>
<P style="TEXT-INDENT: 2em">在2003年2月，我們寫出了第一版的MapReduce庫，2007年8月對它進行了很多包括本地化優(yōu)化，跨機器的任務執(zhí)行的動態(tài)負載平衡等等在內(nèi)的改進。從那時起，我們欣喜的發(fā)現(xiàn)MapReduce庫可以如此廣泛地應用在我們工作中的各種問題上。目前它已經(jīng)在google內(nèi)部應用在廣泛的領(lǐng)域上： </P>
<P style="TEXT-INDENT: 2em">大規(guī)模機器學習問題</P>
<P style="TEXT-INDENT: 2em">用于Google新聞和購物的聚類問題</P>
<P style="TEXT-INDENT: 2em">找到最流行的查詢詞</P>
<P style="TEXT-INDENT: 2em">為了實驗或者產(chǎn)品從網(wǎng)頁中抽取屬性(比如為了本地化搜索從大量網(wǎng)頁中抽取地理位置)</P>
<P style="TEXT-INDENT: 2em">大規(guī)模圖形計算</P>
<P style="TEXT-INDENT: 2em"> <A href="http://blog.chinaunix.nethttp://blog.chinaunix.net/attachment/201101/20/25098298_129551728250Wb.png" target=_blank><IMG src="http://blog.chinaunix.nethttp://blog.chinaunix.net/attachment/201101/20/25098298_129551728250Wb.png" border=0 ; .load="imgResize(this, 650);"></A></P>
<P style="TEXT-INDENT: 2em"></P>
<P style="TEXT-INDENT: 2em">圖4展示了過去的時間里，提交到我們的源代碼管理系統(tǒng)中的MapReduce程序的數(shù)目。從2003年的0到2004年9月接近900個。MapReduce之所以如此成功，是因為它使得在半小時內(nèi)寫出一個簡單地可以在數(shù)千臺機器上跑的程序成為可能。這大大加速了我們的開發(fā)和原型周期。此外，它還使得沒有分布式或者并行系統(tǒng)編程經(jīng)驗的程序員可以很容易地使用大量的計算資源。</P>
<P style="TEXT-INDENT: 2em"> <A href="http://blog.chinaunix.nethttp://blog.chinaunix.net/attachment/201101/20/25098298_1295517332kaAM.png" target=_blank><IMG src="http://blog.chinaunix.nethttp://blog.chinaunix.net/attachment/201101/20/25098298_1295517332kaAM.png" border=0 ; .load="imgResize(this, 650);"></A><A href="http://blog.chinaunix.nethttp://blog.chinaunix.net/attachment/201101/20/25098298_1295517285ML1Q.png" target=_blank></A></P>
<P style="TEXT-INDENT: 2em"> 在每個job結(jié)束時，MapReduce庫還會記錄該job使用的計算資源的統(tǒng)計信息。表1，我們展示了2004年8月，在google內(nèi)部運行MapReduce job的一個子集的一些統(tǒng)計信息。</P>
<P style="TEXT-INDENT: 2em"></P>
<P style="TEXT-INDENT: 2em">6.1 大規(guī)模索引</P>
<P style="TEXT-INDENT: 2em">目前為止，我們一個最重要的MapReduce應用就是用它完全重寫了產(chǎn)品索引系統(tǒng)，該系統(tǒng)為google的網(wǎng)頁搜索服務產(chǎn)生所需要的數(shù)據(jù)結(jié)果。索引系統(tǒng)以一個由爬蟲抓取的存儲在GFS上的很大的文檔集合作為輸入，總共數(shù)據(jù)量要超過20TB。索引流程由5到10個MapReduce操作組成。通過使用MapReduce(而不是使用之前版本的索引系統(tǒng)所使用的自適應的分布式傳輸)有如下幾個優(yōu)點：</P>
<P style="TEXT-INDENT: 2em">索引代碼很簡單，少而且容易理解。因為用于容錯，分布和并行化的代碼都隱藏在了MapReduce庫中。比如，我們通過使用MapReduce將原來的一個計算過程的代碼量從3800行降低到了700行。</P>
<P style="TEXT-INDENT: 2em"> MapReduce庫的性能以及足夠好了，這樣我們就能將不相關(guān)地計算分離，而不是為了降低額外的傳輸費用而將它們合在一塊。這使得我們很容易改變索引處理過程。比如過去在舊系統(tǒng)中可能需要幾個月才能完成的變更，現(xiàn)在在新的系統(tǒng)中幾天就可以完成。</P>
<P style="TEXT-INDENT: 2em"> 索引處理流程變得很容易操作。因為大部分由于機器失敗，慢機器以及網(wǎng)絡引發(fā)的問題都由MapReduce庫自動處理掉了，不需要進行額外的干預。另外也很容易通過給索引系統(tǒng)增加新機器來提高性能。</P>
<P style="TEXT-INDENT: 2em"> </P>
<P style="TEXT-INDENT: 2em">7. 相關(guān)工作</P>
<P style="TEXT-INDENT: 2em">已經(jīng)有很多系統(tǒng)提供了嚴格的編程模型，使用了很多限制來進行計算的并行化。MapReduce模型可以看做是基于我們的在現(xiàn)實中的海量計算經(jīng)驗，對這些模型的一個簡化和提煉。更重要的是，我們提供了一個可以擴展到數(shù)千個處理器上的容錯實現(xiàn)。與之相比，大部分的并行處理系統(tǒng)只是在小規(guī)模集群上實現(xiàn)的，將機器錯誤處理交給程序員。</P>
<P style="TEXT-INDENT: 2em"> 大同步模型和一些MPI實現(xiàn)為簡化程序員編寫并行程序提供了更高級別的抽象。這些系統(tǒng)與MapReduce的一個關(guān)鍵不同就是MapReduce使用了一個限制性的編程模型來為用戶程序提供自動地并行化和透明的容錯機制。</P>
<P style="TEXT-INDENT: 2em"> 我們的本地化優(yōu)化策略主要源于這樣的一些技術(shù)，比如active disks，在那里為了降低IO或者網(wǎng)絡的數(shù)據(jù)傳輸，計算被放到那些靠近本地硬盤的處理元素中執(zhí)行。我們是在由少量硬盤直接連接的PC上運行而不是在一個磁盤控制處理器上運行，但是策略是類似的。</P>
<P style="TEXT-INDENT: 2em"> 我們的任務備份機制類似于Charlotte系統(tǒng)中使用的eager調(diào)度機制。簡單eager調(diào)度機制的一個缺點是如果給定的task引發(fā)了重復的失敗，整個計算就無法完成。我們通過跳過壞記錄的方式解決了這樣的問題。</P>
<P style="TEXT-INDENT: 2em"> MapReduce實現(xiàn)依賴于內(nèi)部開發(fā)的一個集群管理系統(tǒng)，它負責在一個機器集合上分布調(diào)度用戶任務。盡管不是本文關(guān)注的重點，該集群管理系統(tǒng)類似于Condor。</P>
<P style="TEXT-INDENT: 2em"> 作為MapReduce庫的一部分的排序設施在操作過程上類似于Now-sort。源機器(map task)將數(shù)據(jù)劃分進行排序，然后將每份傳遞給一個R個reduce worker中的一個。每個reduce worker在本地進行排序(如果可能的話就僅使用內(nèi)存排序)。當然NOW-sort并不包含使得我們的庫應用廣泛的Map和Reduce函數(shù)。</P>
<P style="TEXT-INDENT: 2em"> Rive提供了一個進程間通過分布式隊列進行數(shù)據(jù)傳輸?shù)木幊棠Ｐ�。像MapReduce一樣，River盡量提高系統(tǒng)的平均性能，即使是由于硬件異構(gòu)或者系統(tǒng)擾動出現(xiàn)了非對稱的情況。River通過仔細的硬盤和網(wǎng)絡傳輸調(diào)度來達到平衡的完成時間。MapReduce使用了不同的策略。通過限制編程模型，MapReduce框架能將問題劃分為大量的細粒度task。這些task可以在可用的worker上進行動態(tài)的調(diào)度，這樣跑的快的worker就可以處理更多的task。該編程模型也允許我們在job快結(jié)束的時候調(diào)度task進行冗余的執(zhí)行，這樣大大減少了非對稱出現(xiàn)時的完成時間。</P>
<P style="TEXT-INDENT: 2em"> BAD-FS有一個與MapReduce完全不同的編程模型。與MapReduce不同，它的目標是降低在廣域網(wǎng)上的job的執(zhí)行時間。但是，它們具有兩個基本的相同點：1.都采用了冗余執(zhí)行從失敗導致數(shù)據(jù)丟失中快速恢復 2.都采用了本地化優(yōu)化以降低數(shù)據(jù)在網(wǎng)絡上的傳輸。</P>
<P style="TEXT-INDENT: 2em"> TACC是一個設計用戶簡化構(gòu)建高可用網(wǎng)絡服務的系統(tǒng)。與MapReduce類似，它依賴于重新執(zhí)行作為實現(xiàn)容錯的一個機制。</P>
<P style="TEXT-INDENT: 2em"> 8. 總結(jié)</P>
<P style="TEXT-INDENT: 2em">MapReduce編程模型已經(jīng)因各種目的在google內(nèi)部成功使用。我們將這種成功歸為幾個原因。首先，模型很容易使用，即使對于沒有分布式編程經(jīng)驗的程序員來說也是，因為它隱藏了并行化，容錯，本地化優(yōu)化，負載平衡的細節(jié)。第二，大量的問題可以簡單地用MapReduce計算來表達。比如MapReduce被用來為google的網(wǎng)頁搜索服務，排序，數(shù)據(jù)挖掘，機器學習很多其他的系統(tǒng)生成數(shù)據(jù)。第三，我們開發(fā)了一個可以擴展到數(shù)千臺機器上MapReduce實現(xiàn)。該實現(xiàn)可以充分利用機器的資源，因此很適合用來處理在google碰到的很多大規(guī)模計算問題。</P>
<P style="TEXT-INDENT: 2em"> 通過這項工作我們也學到了很多。首先，通過限制編程模型可以使計算的并行化和分布很簡單，同時也能讓它容錯。第二，網(wǎng)絡帶寬是一種稀缺資源。我們系統(tǒng)中大量的優(yōu)化都是為了降低網(wǎng)絡傳輸數(shù)據(jù)量：本地化優(yōu)化允許我們從本地磁盤上讀數(shù)據(jù)，將單份拷貝的中間數(shù)據(jù)寫入本地磁盤節(jié)省了網(wǎng)絡帶寬。第三，冗余執(zhí)行能用來降低慢機子的影響，以及用來處理機器失敗和數(shù)據(jù)丟失。</P>
<P style="TEXT-INDENT: 2em"> </P>
<P style="TEXT-INDENT: 2em">致謝：</P>
<P style="TEXT-INDENT: 2em">……</P>
<P style="TEXT-INDENT: 2em">MapReduce從GFS上讀取輸入數(shù)據(jù)以及寫出輸出數(shù)據(jù)，因此我們要感謝…在開發(fā)GFS上的工作…我們還要感謝…在開發(fā)MapReduce使用的集群管理系統(tǒng)上的工作……</P>
<P style="TEXT-INDENT: 2em">本文轉(zhuǎn)自 <A href="http://duanple.blog.163.com/blog/static/709717672010923203501/" target=_blank>http://duanple.blog.163.com/blog/static/709717672010923203501/</A></P>
<P style="TEXT-INDENT: 2em">另一個翻譯版本及英文原文附件請見本博客另一篇翻譯轉(zhuǎn)載</P>
<P style="TEXT-INDENT: 2em"> </P></DIV> |
|
免費注冊
發(fā)表于 2011-12-19 13:54