深入淺出MapReduce

歡迎回看本文原始視頻

今天我們來一起聊一聊MapReduce，這是Google三劍客其中一篇，是Google大神Jeffrey的文章。

那我們再看一下這三個在一起是什麼層次呢？最底層是文件系統GFS，往上是對文件的抽象，KeyValue以及上面邏輯層的推向就是Bigtable，我們今天講的就是上面的演算法MapReduce。

MapReduce

到底是什麼呢？它用來做什麼呢？

比如我們有1TB的數據，如何統計單詞數？如何建立倒排索引？這其實是很複雜的過程，如果有10TB，或者1PB數據怎麼辦呢？這時候單機就沒辦法做，變得很複雜需要想辦法來解決。很多人說這些可以自己單機寫，單機寫的過程甚至構建了一個MapReduce的系統，那怎麼把它做的很通用就是文章所講的事情。

什麼是Map和什麼是Reduce

Map的本質實際上是拆解，比如說有輛紅色的小汽車，有一群工人，把它拆成零件了，這就是Map。

那什麼是Reduce呢？Reduce就是組合，我們有很多汽車零件，還有很多其他各種裝置零件，把他們一陣拼裝，變成變形金剛，這就是Reduce。

什麼是MapReduce

統合來看，MapReduce就是你有很多各種各樣的蔬菜水果麵包（Input），有很多廚師，不同的廚師分到了不同的蔬菜水果麵包，自己主動去拿過來（Split），拿到手上以後切碎（Map），切碎以後給到不同的烤箱里，冷藏機里（Shuffle），冷藏機往往需要主動去拿，拿到這些東西存放好以後會根據不同的顧客需求拿不同的素材拼裝成最終的結果，這就是Reduce，產生結果以後會放到顧客那邊等待付費（Ticket），這個過程是Finalize。

所以MapReduce是六大過程，簡單來說：Input, Split, Map, Shuffle, Reduce, Finalize。

那如何統計1TB或1PB文件里的單詞數呢？

我們輸入很多文檔，文檔的每一行有很多不同的單詞，我們找不同的worker拿到自己手上，就是Split過程，那怎麼切分呢？每一行文檔就切分成單詞和它出現的次數，每次出現的次數是1，就寫1。接下來Shuffle就是把不同的單詞繼續放到同樣的盒子裡面，Bear放一起，Car放一起，這可以由Shuffle寫的時候演算法來決定。當然現在很多智能都不用做了，有時候還需要隨機採樣的方式來實現。等到這個結果以後，最後一步Reduce，就是把相同的數據放一起，比如Car有3個就寫3，River是2個就寫2，最後再放到一起，這樣便於提供服務，得到最終結果。大家可以看到最後箭頭指過來是亂序的，也就是說這個執行過程實際上是高度並行的，也不用等待每個都完成，所以說這是一個很好的優化過程。

寫一下代碼是怎樣的呢？

Map輸入每一行的ID是key，value是這一行的單詞。有這個結果以後就可以統計每個單詞出現的次數。Reduce輸入的還是各個單詞，但後面跟的是一個串，是在裡面出現的次數，1,1,1，我們把1加到一起就是sum的過程，這就是MapReduce的整個過程。輸出我們的關鍵詞和它的出現次數。

MapReduce怎麼建立倒排索引？

首先輸入很多的文檔，這裡面每一行的不是文檔編號了，我們要存它的文檔編號。拆解的時候我們加入新的概念，Worker，這裡有三個Worker，每個Worker負責1行，當然有很多數據時每個Worker可以負責多行，每個Worker就需要進行Map拆解，把每個單詞都拆成單詞和出現的文檔ID。接著Shuffle有兩個新Worker，他們把單詞一拆，一部分交個Worker4，一部分交給Worker5，讓他們去前面拿數據，拿到以後會排個序，這也是最基本的Shuffle過程。接著就是Reduce，把相同的東西合併到一起去，比如food出現在兩個文檔里，就是0和2。最終就是把這些結果放到一起去就可以讓我們查找了。

那什麼是倒排索引？倒排索引就是每個單詞出現在哪些文檔里，這樣就能快速檢索。最終外部輸入每行文檔的ID及內容，我們可以把它拆解成單詞出現在哪個文檔里。Reduce過程輸入是每個關鍵詞key，輸出是key出現在哪些文檔里就放到一起。

MapReduce架構是什麼呢？

首先，我們有用戶進程，它需要協調或者定義我們程序怎麼運行，當然它不是自己運行，實際上它會先想數據有多少，需要拆解成多少個Mapper，多少個Reducer去做。比如要找5個Mapper去做，就會把數據拆成5份，這樣會產生出很多很多Worker，會有Map Worker和Reduce Worker。但最重要的是還會產生一個Master Worker，這個和其他Worker等級是一樣的，只不過會做一些特殊事情，它會作為用戶的代理來協調整個過程，用戶就可以做其他事情。Master Worker會讓這個Worker去拿0號數據，一個Worker負責拿1號數據等等，這就是分配數據的過程。每個Worker會在本地把數據切分開吧，寫到本地的緩存或者硬碟上行。前面Map Worker做完了，Master讓Reduce Worker去拿數據，他們就會從各個Worker里拿到本地需要的數據，在本地做完Reduce以後將結果寫到最終的文件里就是Finalize。實際上，這個過程可以看到第一步切數據是Input，第二步是Map拿數據Split，第三步自己切分就是Map，第四步Reduce去拿數據是Shuffle，第五步Reducer自己去做數據的整合是Reduce，第六步輸出結果Finalize。

總結：

MapReduce本質就是分治法

會刷題也要學會解決生活中的真實問題，成為一個真正解決問題成長的人。

MapReduce六大過程：來洋蔥、拿洋蔥、切洋蔥、放洋蔥、拼洋蔥、送洋蔥

資料《MapReduce: Simplified Data Processing on Large Clusters》

https://pdos.csail.mit.edu/6.824/papers/mapreduce.pdf

歡迎了解BitTiger項目直通車，全面解決背景薄弱、項目不足、沒有面試等問題。

BitTiger直通車特色

• 三個月四個工業級別大項目，全面提升編程實力與簡歷背景
• 矽谷一線IT公司導師、了解痛點的助教，全方位指導及答疑
• 修改簡歷、模擬面試、職業諮詢，Career Service全程護航
• 獨家面試題庫精講、上百小時基礎及面試視頻資源助力求職

了解課程詳情