1. Hellow hadoop~~!

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

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

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

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

1.1Map和reduce

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

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

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

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

下面這個(gè)圖就是map和reduce處理的圖示。

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

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

1.2HDFS

之前，或許你聽(tīng)說(shuō)過(guò)NTFS，VFS，NFS等等等等，沒(méi)錯(cuò)，HDFS就是hadoop file system。

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

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

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

1.3節(jié)點(diǎn)與槽位

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

這樣帶來(lái)的好處是明顯的，因?yàn)樘貏e大的硬盤和特別快的cpu，總是意味著難以接受的價(jià)格。而且這樣一個(gè)配置“特別的”節(jié)點(diǎn)計(jì)算機(jī)掛掉了，找個(gè)他的替身將是很困難的事情。

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

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

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

Hadoop平臺(tái)沒(méi)有提供全局?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ù)集的屬性合并，可以對(duì)兩組數(shù)據(jù)進(jìn)行全局排序然后分解成一系列小的二路歸并問(wèn)題實(shí)現(xiàn)。

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

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

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

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

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

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

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

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

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

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

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

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

2.2注意事項(xiàng)

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

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

3. 總結(jié)

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

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

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

Hadoop全局排序