搞架構的人，Google的架構論文是必看的，但好像大家都不願意去啃英文論文。故把自己的讀書筆記，加入自己的思考，分享給大家。
《MapReduce到底解決什麼問題？》做了簡介，這是第二篇，Google MapReduce優化啟示（中）。
什麼是MapReduce？
MapReduce這個程式設計模型解決什麼問題？
Google MapReduce是Google産出的一個程式設計模型，同時Google也給出架構實作。它能夠解決“能用分治法解決的問題”。
同時，前文以“統計大量文檔中單詞出現的個數”為例，例舉了如何“先分再合”的撰寫map與reduce來解決實際問題。
畫外音，強烈建議回顧一下前情提要：
《MapReduce到底解決什麼問題？》。
MapReduce的核心思路是：
- 并行
- 先分再合
下圖簡述了MR計算“詞頻統計”的過程。
從左到右四個部分，分别是：
輸入檔案
分：M個并行的map計算執行個體
合：R個并行的reduce計算執行個體
輸出結果
先看最後一步，reduce輸出最終結果。
可以看到，R個reduce執行個體并發進行處理，直接輸出最後的計數結果。
執行個體1輸出：(a, 256)(able, 128)(emacs, 1)
執行個體2輸出：(f*ck, 32768) (coding, 65535)
執行個體3輸出：(vim,65535)(x, 16)(zero, 258)
畫外音：這就是總結果，可以看到vim比emacs受歡迎很多。
需要了解的是，由于這是業務計算的最終結果，一個單詞的計數不會出現在兩個執行個體裡。即：如果(a, 256)出現在了執行個體1的輸出裡，就一定不會出現在其他執行個體的輸出裡。
畫外音：否則的話，還需要合并，就不是最終結果了。
再看中間步驟，map到reduce的過程。
可以看到，M個map執行個體的輸出，會作為R個reduce執行個體的輸入。
潛在問題一：每個map都有可能輸出(a, 1)，而最終結果(a, 256)必須由一個reduce輸出，那如何保證每個map輸出的同一個key，落到同一個reduce上去呢？
這就是“分區函數”的作用。
什麼是分區函數？
分區函數，是使用MapReduce的使用者需所實作的，決定map輸出的每一個key應當落到哪個reduce上的函數。
畫外音：如果使用者沒有實作，會使用預設分區函數。
以詞頻統計的應用為例，分區函數可能是：
(1) 以[a-g]開頭的key落到第一個reduce執行個體；
(2) 以[h-n]開頭的key落到第二個reduce執行個體；
(3) 以[o-z]開頭的key落到第三個reduce執行個體；
畫外音：有點像資料庫水準切分的“範圍法”。
分區函數實作要點是什麼？
為了保證每一個reduce執行個體都能夠差不多時間結束工作任務，分區函數的實作要點是：盡量負載均衡。
畫外音：即資料均勻分攤。
上述詞頻統計的分區函數，就不是負載均衡的，有些reduce執行個體處理的單詞多，有些reduce處理的單詞少，這樣就可能出現，所有reduce執行個體都處理結束，最後等待一個長尾reduce的情況。
對于詞頻統計，負載更為均衡的分區函數為：
hash(key) % 3
畫外音：有點像資料庫水準切分的“哈希法”。
潛在問題二：每個map都有可能輸出多個(a, 1)，這樣無形中增大了網絡帶寬資源，以及reduce的計算資源，有沒有辦法進行優化呢？
這就是“合并函數”的作用。
什麼是合并函數？
有時，map産生的中間key的重複資料比重很大，可以提供給使用者一個自定義函數，在一個map執行個體完成工作後，本地就做一次合并，這樣網絡傳輸與reduce計算資源都能節省很多。
合并函數在每個map任務結束前都會執行一次，一般來說，合并函數與reduce函數是一樣的，差別是：
合并函數執行map執行個體本地資料合并
reduce函數執行最終的合并，會收集多個map執行個體的資料
對于詞頻統計應用，合并函數可以将：
一個map執行個體的多個(a, 1)合并成一個(a, $count)輸出。
最後看第一個個步驟，輸入檔案到map的過程。
潛在問題三：如何确定檔案到map的輸入呢？
随意即可，隻要負載均衡，均勻切分輸入檔案大小就行，不用管分到哪個map執行個體。
畫外音：無論分到那個map都能正确處理。
結論
Google MapReduce實施了一系列的優化。
分區函數：保證不同map輸出的相同key，落到同一個reduce裡
合并函數：在map結束時，對相同key的多個輸出做本地合并，節省總體資源
輸入檔案到map如何切分：随意，切分均勻就行
希望大家對MapReduce的優化思路有一個了解，思路比結論更重要。
架構師之路-分享可落地的技術文章