用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），資料就該去哪兒去哪兒了。

注意事項

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

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