1. Hellow hadoop~~!

Hadoop（某人兒子的一只虛擬大象的名字）是一個復雜到極致，又簡單到極致的東西。

說它復雜，是因為一個hadoop集群往往有幾十臺甚至成百上千臺low cost的計算機組成，你運行的每一個任務都要在這些計算機上做任務的分發，執行中間數據排序以及最后的匯總，期間還包含節點發現，任務的重試，故障節點替換等等等等的維護以及異常情況處理。誰叫hadoop集群往往都是由一些平民計算機組成，沒事兒罷個工什么的，實在是再尋常不過的事情。

而說其簡單，則是因為，上面說到的那些，你通通不用管，你所需要做的，就是寫一個程序，當然也可以是腳本，從標準輸入讀入一條數據，處理完之后，把結果輸出到標準輸出。

現在，或許你就明白了，hadoop就是一個計算模型。一個分布式的計算模型。

1.1Map和reduce

天下大事，分久必合、合久必分。

所謂分布式計算，就是把一大堆用于計算的數據材料切了，扔到多個鍋里面，該焯水的焯水，該油炸的油炸。然后都準備的差不多了，按著一定的先后順序，比如不好熟的先放，好熟的后放什么的，一塊下鍋炒成一盤菜出來，端出來上桌。

前面的步驟，就是map，分發。Map的作用就是把輸入數據打散，做簡單的處理，輸出。而hadoop則要先將中間數據排序，這個稱為shuffle，然后由reduce把中間數據合并到一起。將最終結果輸出。

舉個簡單的例子：公安局要根據數據庫內身份證號獲得全國每個地市人口數情況（好吧，這個應該是統計局做的），這個任務落到你的頭上了，你應該先把所有的身份證號導出到文件中，每行一個，然后把這些文件交給map。Map中的要做的就是截取身份證號的前面六位，把這六位數字直接輸出。然后hadoop會把這些身份證號的前六位排序，把相同的數據都排到一起，交給reduce，reduce判斷每次輸入的號碼是否與上一個處理的相同，相同則累加，不同則把之前的號碼，和統計的數值輸出。這樣，你就獲得了各地市的人口數統計。

下面這個圖就是map和reduce處理的圖示。

上圖是MapReduce的數據處理視圖。分為map，shuffle，reduce三個部分。各map任務讀入切分后的大規模數據進行處理并將數據作為一系列key:value對輸出，輸出的中間數據按照定義的方式通過shuffle程序分發到相應的reduce任務。Shuffle程序還會按照定義的方式對發送到一個reduce任務的數據進行排序。Reduce進行最后的數據處理。

MapReduce計算框架適用于超大規模的數據（100TB量級）且各數據之間相關性較低的情況。

1.2HDFS

之前，或許你聽說過NTFS，VFS，NFS等等等等，沒錯，HDFS就是hadoop file system。

為什么需要一種專門的文件系統呢？

這是因為hadoop使用過網絡松散（說其松散，是因為hadoop集群中的任意一個計算機故障了或是不相干了，都不會對集群造成影響）的組合到一起的。多個計算機需要一個統一的文件訪問方式。也就是根據一個路徑，不同的計算機可以定位同一個文件。

HDFS就是這樣一種分布式文件系統，提供了較好的容錯功能和擴展性。

1.3節點與槽位

Hadoop集群是由很多low cost的計算機組成的，這些計算機被稱為節點。組成hadoop的計算機通常都是全功能的，沒有特別的專門用于計算和存儲的部分。

這樣帶來的好處是明顯的，因為特別大的硬盤和特別快的cpu，總是意味著難以接受的價格。而且這樣一個配置“特別的”節點計算機掛掉了，找個他的替身將是很困難的事情。

計算節點和存儲節點統一的另一個好處是，任務在計算過程中產生的文件，可以直接放在本機的存儲節點上，減少網絡帶寬占用和延遲。

在衡量hadoop的map和reduce的處理能力的時候通常都是以槽位為單位的。槽位就是集群內每個計算機的cpu并發數（cpu數*核心數*超線程數）的總和。每個任務都會安排在一個槽位內允許，安排不到槽位的任務則會等待。

2. Hadoop應用實例：大規模數據的排序

Hadoop平臺沒有提供全局數據排序，而在大規模數據處理中進行數據的全局排序是非常普遍的需求。大量的將大規模數據任務切分成小數據規模的數據處理任務都必須先將大規模數據進行全局排序。例如處理兩組大的數據集的屬性合并，可以對兩組數據進行全局排序然后分解成一系列小的二路歸并問題實現。

2.1應用hadoop進行大規模數據全局排序的方法

使用hadoop進行大量的數據排序排序最直觀的方法是把文件所有內容給map之后，map不做任何處理，直接輸出給一個reduce，利用hadoop的自己的shuffle機制，對所有數據進行排序，而后由reduce直接輸出。

然而這樣的方法跟單機毫無差別，完全無法用到多機分布式計算的便利。因此這種方法是不行的。

利用hadoop分而治之的計算模型，可以參照快速排序的思想。在這里我們先簡單回憶一下快速排序。快速排序基本步驟就是需要現在所有數據中選取一個作為支點。然后將大于這個支點的放在一邊，小于這個支點的放在另一邊。

設想如果我們有N個支點（這里可以稱為標尺），就可以把所有的數據分成N+1個part，將這N+1個part丟給reduce，由hadoop自動排序，最后輸出N+1個內部有序的文件，再把這N+1個文件首尾相連合并成一個文件，收工。

由此我們可以歸納出這樣一個用hadoop對大量數據排序的步驟：

1） 對待排序數據進行抽樣；

2） 對抽樣數據進行排序，產生標尺；

3） Map對輸入的每條數據計算其處于哪兩個標尺之間；將數據發給對應區間ID的reduce

4） Reduce將獲得數據直接輸出。

這里使用對一組url進行排序來作為例子：

這里還有一點小問題要處理：如何將數據發給一個指定ID的reduce？hadoop提供了多種分區算法。這些算法根據map輸出的數據的key來確定此數據應該發給哪個reduce（reduce的排序也依賴key）。因此，如果需要將數據發給某個reduce，只要在輸出數據的同時，提供一個key（在上面這個例子中就是reduce的ID+url），數據就該去哪兒去哪兒了。

2.2注意事項

1) 標尺的抽取應該盡可能的均勻，這與快速排序很多變種算法均是強調支點的選取是一致的。

2) HDFS是一種讀寫性能很不對稱的文件系統。應該盡可能的利用其讀性能很強的特點。減少對寫文件和shuffle操作的依賴。舉例來說，當需要根據數據的統計情況來決定對數據的處理的時候。將統計和數據處理分成兩輪map-reduce比將統計信息合并和數據處理都放到一個reduce中要快速的多。

3. 總結

Hadoop實際是一種以數據為驅動的計算模型，結合MapReduce和HDFS，將任務運行在數據存放的計算節點上，充分利用了計算節點的存儲和計算資源，同時也大大節省了網絡傳輸數據的開銷。

Hadoop提供了簡便利用集群進行并行計算的平臺。各種可以隔離數據集之間相關性的運算模型都能夠在Hadoop上被良好應用。之后會有更多的利用Hadoop實現的大規模數據基礎計算方法的介紹。

---------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------
cite:http://stblog.baidu-tech.com/?p=397
-----------------------------------------------------------

Hadoop全局排序