講座總結｜解讀大數據世界中MapReduce的前世今生

講座嘉賓：Tim

講座鏈接：【太閣直播】解讀大數據世界中MapReduce的前世今生

講座總結：6Kunnnnn

何為MapReduce？網路上很多官方的定義都過於抽象難懂了，希望通過以下的講解，可以讓大家能更簡單地理解MapReduce的含義。

1. 背景：web檢索的簡單工作流程

MapReduce其實起源於web檢索，我們常見的web檢索可以簡單分為兩部分：獲取網頁內容並建立索引，和根據網頁索引來處理查詢關鍵詞。

第一，獲取網頁內容並建立索引。這一步的實現需要用到兩種程序，分別是：

1. Crawler，別名Spider，網頁爬蟲程序，用來爬取互聯網上的網頁內容

2. Indexer，索引器，對爬取下來的web內容建立索引，變成searchable content，這樣網頁就能被搜索了

需要解釋一下，什麼叫做索引器Indexer。我們可以簡單理解為，互聯網上每一個網頁就是一個document，每個document都包含了不同的word，而我們針對每一個word，建立一個word出現在哪些document的table。

如下圖，假設有document分別為1、2、3，裡面分別有abc、xyz、def等辭彙。而最終的Indexer結果就是將哪些word出現在哪些document ID中的映射保存下來，每一個word對應一個sorted list用來存儲document ID。

第二，根據網頁索引來處理查詢關鍵詞。如下圖，當索引器被建立好了之後，每當有網頁查詢query進來，就需要利用這些索引，來處理query的關鍵詞，找出那些同時含有這些關鍵詞的文檔。比如一個query裡面同時有abc和bbb，那麼含有這兩個關鍵字的文檔就是document 2。

2. MapReduce解決分散式web檢索問題

自從互聯網被創造後，被創建的網頁和網站變的越來越多，數量極為龐大。像Google這樣的web檢索巨頭如何保證能對互聯網上大部分的web進行檢索？答案就是並行parallel，或理解為數據量達到單機很難處理的程度，迫使採用運行多台機器來進行分散式計算。

如上圖，我們橫向上來看，每一台單機執行Crawler和Indexer任務，生成local index，最後匯總成global index。但是如果縱向上來看，Crawler和Indexer其實可以被分為兩個獨立的部分（因為他們的輸入輸出不同），而它們的中間聯繫就是，Crawler的輸出其實就是Indexer的輸入（web pages）。

所以如下圖，對於每一個web獲取＋建立索引的任務（Job），我們把其中從web page到local index的部分當作是Map階段，從local index匯聚到global index的部分當作是Reduce階段。

所以我們可以簡單理解為：MapReduce就是把複雜的分散式處理任務，簡化分解成Map和Reduce兩個階段。

這樣的programming model好處就是，我們能更簡單的進行分散式程序的設計和實現了。但是，雖然有很多的好處，在MapReduce中，我們還需解決分散式系統的常見問題。比如網路問題，磁碟問題，程序本身問題，而且如果分散式系統出了問題也會很難解決恢復。因此，也就有了上述圖片中的master的概念。簡單說，Master是一個專門用來管理這些分散式系統的機器。那麼，Master是如何進行分散式計算的管理呢？如下圖：

在一個分散式計算集群（cluster）中，實際運行任務的是Slave機器，也被稱之為DataNode（因為需要處理的data被存在了這些機器上），而Master機器負責任務的調度，也被稱之為NameNode，之所以這樣是因為它知道應該將哪個Task分配到哪個Slave機器上邊運行（知道Slave和Task的name）。具體細節，Master中有一個Task queue，存儲待執行的任務，每一個Slave有若干Task slots用來接收Master分配來的任務並執行。Master的Job Tracker和Slave的Task Tracker，用來監督每個Task執行情況，如果出現問題比如網路連接失敗，或者程序出錯，Master和Slave會有相應的措施來解決這些問題並恢復之前的任務進度。

所以，通過以上的任務調度方法，MR的厲害之處，就是把分散式系統的編程分成Map和Reduce兩部分，同時解決了頭疼的分散式計算問題。好處就是，開發者可以更多的注重程序的開發，而不需要太花時間解決分散式計算的種種問題。

當然，在MapReduce出現前互聯網web檢索還有別的解決方法，比如可以使用一台超級計算機來當作是super indexer，用來接受web pages作為輸入，來建立global index，或理解為「shipping data to software」。這樣做不是不行，但是把數量龐大的web pages傳送到super indexer那裡，僅僅是數據的傳送就需要花費大量的時間。相比之下，MapReduce的方法可以理解為「shipping software to data」，也就是，DataNode負責存儲數據，而NameNode負責將Task（software）傳送給DataNode來執行。這樣的方法，速度能提升好幾個數量級，何況和一台超級計算機相比，購買很多個普通商用計算機來進行分散式計算要划算得多，擴展性也強。如下圖：

此外，MapReduce更適合用來作non-Transactional的數據分析，也就是數據內容基本保持不變，而相比Transactional或者Real-time的數據就會持續的更新，每次數據分析都是按batch process，一次大量時間長。

3. MapReduce和HDFS

HDFS，Hadoop Distributed File Systems，是根據Google著名的GFS的論文實現的開源項目，其實Hadoop也是Google另外一篇MapReduce論文的具體實現。所以我們可以理解為Hadoop就是HDFS和MapReduce。

簡單說，HDFS解決了分散式系統很多問題，特別是數據副本replication和恢復recovery問題，它類似於UNIX系統，提供了很多文件系統的抽象介面，這樣廣大熟悉UNIX系統的人能夠很快上手。那麼MapReduce是如何與HDFS配合的呢？如下圖：

首先，在Map階段之前，Map程序的輸入需要進行一些操作。HDFS在存儲文件的時候，並沒有把一個文件當做一個整體，而是利用按照一定大小（默認為64MB）的chunk來保存文件，每一個chunk可能有一個或者多個文件，比如chunk1含有文件1、2和3的一部分，chunk2含有文件3的另一部分，以及其他文件。所以在從chunk讀入輸入文件之前，需要對這些chunk裡面的文件進行split，即將同一文件在不同chunk中的部分split到一起，再通過RecordReader來將文件讀成Key Value Pair的輸入交給Map程序。

之後，得到了每一台機器上的Map程序的輸出，需要將這些機器的輸出結果shuffling到不同機器的Reduce程序上進一步運算。首先一步就是進行Partition，或者理解為將不同台機器的輸出數據Group-By-Key，在對同一Key中所有數據Sort，之後的結果會被分配到不同機器上的Reduce程序中，這樣會進一步加快Reduce程序的速度。

4. MapReduce的擴展延伸

我們之前所討論的內容，實際上是第一代的MapReduce，基本是基於Google的論文實現的。在1.0中，Master負責了任務調度的全部工作，這樣的後果就是Master會很臃腫（功能太多），以及在同一個集群cluster上Master只能負責MapReduce相關的分散式計算的調度，無法負責別的程序。而現在更流行的是MapReduce 2.0，在1.0的基礎上進行了不少的改動，最大的變化就是YARN的引入。YARN全稱為Yet Another Resource Negotiator，主要功能就是替代NameNode的任務調度功能，主要的好處就是簡化了Master的工作量使得其不再過與臃腫，另一方面就是除了MapReduce之外，還可以在同一個集群上運行別的application，比如現在很流行的Spark。

而Spark，大家都說比MapReduce快很多，但是其底層的實現還是類似於MapReduce分散式的計算方式，但更多的是做出了很多的性能優化，特別就是RDD（Resilient Distributed Dataset）的引入，一種對分散式數據的抽象。傳統的MapReduce需要大量的磁碟讀寫操作和網路的傳輸，比如Split、RR、Partition等等，都會涉及將中間計算結果在不同機器之間網路傳輸並存到disk上作為之後pipeline的輸入的操作。但是Spark之所以快，是因為Spark採取的更多的是將RDD，也就是分散式數據保存到Memory里進行計算，而且是一種lazy evaluation計算方式，也就是必要的時候一口氣將內存中的某個計算過程pipeline執行完畢，而不是像MapReduce一樣，一步一步計算、每步都將中間結果保存到磁碟上、之後下一步再讀入的方式來進行，這樣會節省大量的disk IO時間。如果pipeline的某一個中間步驟失敗了，Spark有一個RDD的workflow圖，用來找回之前失敗的RDD從新計算，即便從新計算也很可能比磁碟IO的開銷要小很多，畢竟內存要比disk快很多。

但是Spark也並不一定能完全替代MapReduce，相比於MapReduce，Spark更適合real-time的數據處理，因為需要較快的響應速度，或者iterative演算法比如K-means，即不斷地對同一組數據進行同一個演算法的迭代處理，然而MapReduce更適合於數據量非常大的batch process，因為Spark對內存要求的確是比較的高。當然Spark並不一定需要依賴於HDFS上邊運行，也可以在別的distributed storage layer上。

總之，MapReduce從第一代，到第二代再到之後其他類似平台的發展，可以看出MapReduce的生命力，以及對分散式處理的巨大貢獻。而希望讀完這篇文章，大家也對MapReduce的前世今生有了大致的理解。

其它細節補充

對於互聯網crawler程序，之所以又叫做爬蟲spider，因為程序就好像在爬（traverse）互聯網。但存在一些獨立的網頁無法檢索到（比如公司內部網路）。而且爬網站需要選好seed網站，比如新浪門戶，因為有很多鏈接指向外部網路，但是百度可能就不適合爬網站的seed網站，因為缺少外部的鏈接。

分散式資料庫的CAP理論，針對不同領域需要有不同的取捨。比如銀行轉賬，需要保證一個cluster中，各個機器node之間銀行數據信息是consistent的，比如無論訪問哪個node的銀行賬單數據，結果都需要是一樣的，否則用戶可能得到錯誤賬單。然而search engine更強調available，就是要有在一定時間內有結果返回，不要讓用戶等待太久，雖然每次查詢的結果可能不都是consistent的數據。

BitTiger近期課程，火熱報名，免費試聽：

如何設計實現一個實時PokemonGo小精靈地圖？

互聯網公司職場進階不可不知的那些事兒

更多精彩，盡在矽谷高端線上教育社區BitTiger：請猛戳我

公眾號：論碼農的自我修養

微博：@太閣BitTiger

今日頭條：太閣BitTiger
推薦閱讀：