12.28 大數據基石——Hadoop與MapReduce原理

近兩年AI成了最火熱領域的代名詞，各大高校紛紛推出了人工智能專業。但其實，人工智能也好，還是前兩年的深度學習或者是機器學習也罷，都離不開底層的數據支持。對於動輒數以TB記級別的數據，顯然常規的數據庫是滿足不了要求的。今天，我們就來看看大數據時代的幕後英雄——Hadoop。

Hadoop這個關鍵詞其實有兩重含義，最早它其實指的就是單純的分佈式計算系統。但是隨著時代的發展，Hadoop系統擴大，如今hadoop已經是成了一個完整的技術家族。從底層的分佈式文件系統（HDFS）到頂層的數據解析運行工具（Hive、Pig），再到分佈式系統協調服務（ZooKeeper）以及分佈式數據庫（HBase），都屬於Hadoop家族，幾乎涵蓋了大半大數據的應用場景。在Spark沒有流行之前，Hadoop一直是大數據應用中的絕對主流，即使是現在，依舊有大量的中小型公司，還是依靠Hadoop搭建大數據系統。

如今的Hadoop雖然家族龐大，但是早年Hadoop的結構非常簡單，幾乎只有兩塊，一塊是分佈式文件系統，這個是整個數據的支撐，另一個就是MapReduce算法。

分佈式文件系統

大數據時代，數據的量級大規模增長，動輒以TB甚至PB計。對於這麼海量的數據，如果我們還使用常規的方法是非常困難的。因為即使是 O(n) 的算法，將所有的數據遍歷一遍，所消耗的時間也肯定是以小時計，這顯然是不能接受的。不僅如此，像是MySQL這樣的數據庫對於數據規模也是有限制的，一旦數據規模巨大，超過了數據庫的承載能力，那幾乎是系統級的噩夢（重要的數據不能丟棄，但是現在的系統無法支撐）。

既然我們把數據全部存儲在一起，會導致系統問題，那麼我們可不可以把數據分成很多份分別存儲，當我們需要處理這些數據的時候，我們對這些分成許多小份的數據分別處理，最後再合併在一起？

答案當然是可行的，Hadoop的文件系統正是基於這個思路。

在HDFS當中，將數據分割成一個一個的小份。每個小份叫做一個存儲塊，每個存儲塊為64MB。這樣一個巨大的文件會被打散存儲在許多存儲塊當中。當我們需要操作這些數據的時候，Hadoop會同時起動許多個執行器（executor）來併發執行這些存儲塊。理論上來說，執行器的數量越多，執行的速度也就越快。只要我們有足夠多的執行器，就可以在短時間內完成海量數據的計算工作。

但是有一個小問題，為什麼每個存儲塊偏偏是64MB，而不是128MB或者256MB呢？

原因也很簡單，因為數據存儲在硬盤上，當我們查找數據的時候，CPU其實是不知道數據究竟存放在什麼地方的。需要有一個專門的程序去查找數據的位置，這個過程被稱為尋址。尋址的時候會伴隨著硬盤的高速旋轉。硬盤的旋轉速度是有限的，自然我們查找文件的速度也會存在瓶頸。如果存儲塊太小，那麼存儲塊的數量就會很多，我們尋址的時間就會變長。

如果存儲塊設置得大一些行不行？也不行，因為我們在執行的時候，需要把存儲塊的數據拷貝到執行器的內存裡執行。這個拷貝伴隨著讀寫和網絡傳輸的操作，傳輸數據同樣耗時不少。存儲塊過大，會導致讀寫的時間過長，同樣不利於系統的性能。根據業內的說法，希望尋址的耗時佔傳輸時間的1%，目前的網絡帶寬最多可以做到100MB/s，根據計算，每個存儲塊大約在100MB左右最佳。也許是程序員為了湊整，所以選了64MB這個大小。

目前為止，我們已經搞清楚了Hadoop內部的數據存儲的原理。那麼，Hadoop又是怎麼併發計算的呢？這就下一個關鍵詞——MapReduce出場了。

MapReduce

嚴格說起來MapReduce並不是一種算法， 而是一個計算思想

先說map，MapReduce中的map和Java或者是C++以及一些其他語言的map容器不同，它表示的意思是映射。負責執行map操作的機器（稱作mapper）從HDFS當中拿到數據之後，會對這些數據進行處理，從其中提取出我們需要用到的字段或者數據，將它組織成key->value的結構，進行返回。

為什麼要返回key->value的結構呢？直接返回我們要用到的value不行嗎？

不行，因為在map和reduce中間，Hadoop會根據key值進行排序，將key值相同的數據歸併到一起之後，再發送給reducer執行。也就是說，key值相同的數據會被同一個reducer也就是同一臺機器處理，並且key相同的數據連續排列。reducer做的是通過mapper拿到的數據，生成我們最終需要的結果。

Sample

這個過程應該不難理解， 但是初學者可能面臨困惑，為什麼一開始的時候，要處理成key-value結構的呢？為什麼又要將key值相同的數據放入一個reducer當中呢，這麼做有什麼意義？

這裡，我們舉一個例子，就清楚了。

MapReduce有一個經典的問題，叫做

<code>def map(text):  
\tfor line in text:    
  \twords = line.split(' ')    
\t\tfor w in words:      
    \tprint(w, 1)/<code>

這樣當然還是不夠的，我們還需要把相同的單詞聚合起來，清點一下看看究竟出現了多少次，這個時候就需要用到reducer了。reducer也很簡單，我們讀入的是map輸出的結果。由於key相同的數據都會進入同一個reducer當中，所以我們不需要擔心遺漏，只需要直接統計就行：

<code>def reduce(text):  
\twordNow = None  
\ttotCount = 0  
\tfor line in text:    
  \telements = line.split(' ')    
\t\tword, count = elements[0], int(elements[1])    
\t\t// 碰到不同的key，則輸出之前的單詞以及數量    
\t\tif word != wordNow:        
    \t\tif wordNow is not None:          
\t\t\t\t\tprint(wordNow, totCount)         

\t\t\t\t\twordNow = word
\t\t\t\t\ttotCount=1    
\t\t// 否則，更新totCount    
\t\telse:      
    \ttotCount += count/<code>

如果我們map的結果不是key-value結構，那麼Hadoop就沒辦法根據key進行排序，並將key相同的數據歸併在一起。那麼我們在reduce的時候，同一個單詞就可能出現在不同的reducer當中，這樣的結果顯然是不正確的。

當然，如果我們只做一些簡單的操作，也可以捨棄reduce階段，只保留map產出的結果。

現在看MapReduce的思想其實並不複雜，但是當年大數據還未興起的時候，MapReduce橫空出世，既提升了計算性能，又保證了結果的準確。一舉解決了大規模數據並行計算的問題，回想起來，應該非常驚豔。雖然如今技術更新，尤其是Spark的流行，搶走了Hadoop許多榮光。但MapReduce的思想依舊在許多領域廣泛使用，比如Python就支持類似的MapReduce操作，允許用戶自定義map和reduce函數，對數據進行並行處理。

不過，MapReduce也有短板，比如像是數據庫表join的操作通過MapReduce就很難實現。而且相比於後來的Hive以及Spark SQL來說，MapReduce的編碼複雜度還是要大一些。但不管怎麼說，瑕不掩瑜，對於初學者而言，它依舊非常值得我們深入瞭解。

閱讀更多 承志的算法課堂 的文章

關鍵字: MapReduce 幕後英雄 數據庫