1. Hellow hadoop~~!

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

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

而說其簡單，則是因為，上面說到的那些，你通通不用管，你所需要做的，就是寫一個程序，當(dāng)然也可以是腳本，從標(biāo)準(zhǔn)輸入讀入一條數(shù)據(jù)，處理完之后，把結(jié)果輸出到標(biāo)準(zhǔn)輸出。

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

1.1Map和reduce

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

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

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

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

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

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

MapReduce計算框架適用于超大規(guī)模的數(shù)據(jù)（100TB量級）且各數(shù)據(jù)之間相關(guān)性較低的情況。

1.2HDFS

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

為什么需要一種專門的文件系統(tǒng)呢？

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

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

1.3節(jié)點與槽位

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

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

計算節(jié)點和存儲節(jié)點統(tǒng)一的另一個好處是，任務(wù)在計算過程中產(chǎn)生的文件，可以直接放在本機的存儲節(jié)點上，減少網(wǎng)絡(luò)帶寬占用和延遲。

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

2. Hadoop應(yīng)用實例：大規(guī)模數(shù)據(jù)的排序

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

2.1應(yīng)用hadoop進(jìn)行大規(guī)模數(shù)據(jù)全局排序的方法

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

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

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

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

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

1） 對待排序數(shù)據(jù)進(jìn)行抽樣；

2） 對抽樣數(shù)據(jù)進(jìn)行排序，產(chǎn)生標(biāo)尺；

3） Map對輸入的每條數(shù)據(jù)計算其處于哪兩個標(biāo)尺之間；將數(shù)據(jù)發(fā)給對應(yīng)區(qū)間ID的reduce

4） Reduce將獲得數(shù)據(jù)直接輸出。

這里使用對一組url進(jìn)行排序來作為例子：

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

2.2注意事項

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

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

3. 總結(jié)

Hadoop實際是一種以數(shù)據(jù)為驅(qū)動的計算模型，結(jié)合MapReduce和HDFS，將任務(wù)運行在數(shù)據(jù)存放的計算節(jié)點上，充分利用了計算節(jié)點的存儲和計算資源，同時也大大節(jié)省了網(wǎng)絡(luò)傳輸數(shù)據(jù)的開銷。

Hadoop提供了簡便利用集群進(jìn)行并行計算的平臺。各種可以隔離數(shù)據(jù)集之間相關(guān)性的運算模型都能夠在Hadoop上被良好應(yīng)用。之后會有更多的利用Hadoop實現(xiàn)的大規(guī)模數(shù)據(jù)基礎(chǔ)計算方法的介紹。

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

Hadoop全局排序