原文發(fā)表于2019-02-28,。

雖然Google的MapReduce論文很老了（十多年）,，但只要還沒看，就值得一看,。

概要

MapReduce是一種重視容錯(cuò)性的分布式并行計(jì)算模式,，它把分布式并行計(jì)算分為map和reduce兩個(gè)階段：

• map: 把輸入數(shù)據(jù)集切分成很多份（1份可包含很多records），傳給map函數(shù)做轉(zhuǎn)換處理（每次處理1條record,，得出1條結(jié)果）,，結(jié)果集被輸出到文件
• reduce: 讀取map的結(jié)果集，傳給reduce函數(shù)做歸約處理（每次處理1條record,，更新一條共享的結(jié)果）,，結(jié)果集被輸出到文件

數(shù)據(jù)通常是key-value格式的,，像HashMap，key關(guān)聯(lián)著value,。key是連接map和reduce的紐帶,，reduce通過key來拉取相關(guān)的map結(jié)果，把關(guān)聯(lián)某個(gè)key的一批values歸約成一個(gè)收斂的結(jié)果,。

每臺(tái)機(jī)器是一個(gè)node,。map和reduce都可以在很多worker node上運(yùn)行。1個(gè)任務(wù)=1個(gè)函數(shù) 1組輸入數(shù)據(jù),，任務(wù)被分配到worker node上運(yùn)行,。有一個(gè)中央的調(diào)度器，叫做master node,，來進(jìn)行全局調(diào)度,，給worker node分配任務(wù)。

示意圖就不貼了,，到處可見的WordCount例子也不寫了,，別人寫過的我一般不寫。請(qǐng)參考網(wǎng)絡(luò)資料,。例如這篇就挺好：https://mr-dai./mapreduce_summary/

參考好了嗎,？繼續(xù)吧！

優(yōu)化

論文指出它是為大量廉價(jià)機(jī)器組成的環(huán)境而設(shè)計(jì)的,，環(huán)境特點(diǎn)是：機(jī)器特別多,，機(jī)器性能參差不齊,，有的機(jī)器會(huì)突然壞掉,。論文的很多優(yōu)化都是在解決這種環(huán)境所特有的問題，這在當(dāng)時(shí)是開創(chuàng)性的,，因?yàn)橐话愕姆植际讲⑿屑夹g(shù)都還在研究一組性能均等的高性能機(jī)器,，不能容忍某臺(tái)機(jī)器變慢或故障。現(xiàn)在工業(yè)界都是用MapReduce的方式在搞,，因?yàn)槎鄶?shù)企業(yè)的環(huán)境都是論文里說的這種,。

Google推出MapReduce論文時(shí)已經(jīng)考慮周密了，給出了很多優(yōu)化點(diǎn)：
Map階段:

1. 一開始先把輸入數(shù)據(jù)集切分成M片,，每片一般16~64MB
2. map完成時(shí)通知master,，master記錄所有map的完成情況和文件位置
3. map tasks要切得小而多，建議遠(yuǎn)大于機(jī)器數(shù),，容易負(fù)載均衡（3個(gè)task分給2個(gè)node,，均衡度肯定不如13個(gè)task分給2個(gè)node）
4. map tasks盡量分配到靠近數(shù)據(jù)的node，以節(jié)省帶寬
5. 用combine函數(shù)做本地預(yù)合并,，以減小map的輸出結(jié)果集
   Reduce階段：
6. reducer從mapper node下載輸入文件
7. reduce先寫臨時(shí)文件,，完成時(shí)用原子的文件重命名操作
8. reduce用lazy iterator讀取輸入,，以節(jié)省內(nèi)存

全階段：

1. map輸出到本地文件，reduce輸出到全局文件
2. map和reduce都可有多個(gè)副本同時(shí)重復(fù)執(zhí)行,，誰快就用誰的結(jié)果（即使有個(gè)副本突然變慢,，也有別的副本在跑）
3. 總有一些落后進(jìn)程，增加百分之幾的備用資源,，就能加速掃除長(zhǎng)尾,，節(jié)省百分之幾十的時(shí)間
4. 調(diào)度器盡量把任務(wù)分配給空閑的worker，因此速度快的worker自然會(huì)處理更多tasks
5. 遇到錯(cuò)誤的record,，寫標(biāo)記到master,，再有task遇到時(shí)跳過它

注釋：
這種“總有一些落后進(jìn)程”的現(xiàn)象叫做尾部延遲放大(tail delay amplification)，分布式數(shù)據(jù)庫執(zhí)行查詢的scatter/gatter模式也有此問題,。
Google的解法相當(dāng)于task rebalance,，來個(gè)比喻：讓先進(jìn)員工幫助落后員工完成積壓的任務(wù)，以保證全團(tuán)隊(duì)的項(xiàng)目按時(shí)完成,。
我們要知道,，“計(jì)算易移動(dòng)，數(shù)據(jù)難移動(dòng)”,，我們總是傾向于把計(jì)算移動(dòng)到另一處,，而不是把數(shù)據(jù)移過去。
MapReduce就是移動(dòng)了計(jì)算,，并且把計(jì)算盡可能移動(dòng)到數(shù)據(jù)附近,。task rebalance只移動(dòng)計(jì)算，無需移動(dòng)數(shù)據(jù),，所以才管用,。
而分布式數(shù)據(jù)庫在執(zhí)行查詢時(shí)，把計(jì)算分發(fā)到data node上,，如果有的data node反應(yīng)慢,，就沒有辦法，因?yàn)閿?shù)據(jù)不好移,。