1、1TB（或1分鐘）排序的冠軍
作為分布式數據處理的框架，集群的數據處理能力究竟有多快？或許1TB排序可以作為衡量的標準之一。

1TB排序，就是對1TB（1024GB，大約100億行數據）的數據進行排序。2008年， Hadoop贏得1TB排序基準評估第一名 ，排序1TB數據耗時209秒。后來， 1TB排序被1分鐘排序所取代 ，1分鐘排序指的是在一分鐘內盡可能多的排序。 2009年，在一個1406個節點組成的hadoop集群，在59秒里對500GB完成了排序；而在1460個節點的集群，排序1TB數據只花了62秒 。

這么驚人的數據處理能力，是不是讓你印象深刻呢？呵呵

下面我們來看看排序的過程吧。

2、排序的過程

1TB的數據？100億條數據？都是什么樣的數據呢？讓我們來看幾條：

      .t^#\|v$2\         0AAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDDEEEEEEEEEEFFFFFFFFFFGGGGGGGGGGHHHHHHHH
75@~?'WdUF         1IIIIIIIIIIJJJJJJJJJJKKKKKKKKKKLLLLLLLLLLMMMMMMMMMMNNNNNNNNNNOOOOOOOOOOPPPPPPPP
w[o||:N&H,         2QQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTTTTUUUUUUUUUUVVVVVVVVVVWWWWWWWWWWXXXXXXXX
^Eu)

    

描述一下：每一行，是一條數據。每一條，由2部分組成，前面是一個由10個隨即字符組成的key，后面是一個80個字符組成的value。

排序的任務：按照key的順序排。

那么1TB的數據從何而來？答案是用程序隨即生成的，用一個只有map，沒有reduce的MapReduce job，在整個集群上先隨即生成100億行數據。然后，在這個基礎上，再運行排序的MapReduce job，以測試集群排序性能。

3、排序的原理

先說明一點，熟悉MapReduce的人都知道：排序是MapReduce的天然特性！在數據達到reducer之前，mapreduce框架已經對這些數據按鍵排序了。

所以，在這個排序的job里，不需要特殊的Mapper和Reducer類。用默認的
IdentityMapper和IdentityReducer即可。

既然排序是天然特性，那么1TB排序的難點在哪里呢？？答：100億行的數據隨即分散在1000多臺機器上，mapper和reducer都是Identity的，這個難點就在MapReduce的shuffle階段！關鍵在如何取樣和怎么寫Partitioner。

好在這個排序的源代碼已近包含在 hadoop 的examples里了，下面我們就來分析一下。

4、取樣和partition的過程

面對對這么大量的數據，為了partition的更均勻。要先“取樣”：

1) 對Math.min(10, splits.length)個split（輸入分片）進行隨機取樣，對每個split取10000個樣，總共10萬個樣
2) 10萬個樣排序，根據reducer的數量(n)，取出間隔平均的n-1個樣
3) 將這個n-1個樣寫入partitionFile(_partition.lst，是一個SequenceFile)，key是取的樣，值是nullValue
4) 將partitionFile寫入DistributedCache

接下來，正式開始執行MapReduce job：
5) 每個map節點：
a.根據n-1個樣，build一棵類似于B-數的“索引樹”：

• 每個非葉子節點，都有256個子節點。
• 不算根節點的非葉子節點有1層，加上根節點和葉子節點，共3層。
• 非葉子節點代表key的“byte path”
• 每個葉子節點代表key的前2個bytes path
• 葉子節點上，保存的是partition number的范圍，有多少個reducer就有多少partition number

b.前綴相同的key，被分配到同一個葉子節點。
c.一個子節點上，可能有多個reducer
d.比第i個樣小的key，被分配到第i個reducer，剩下的被分配到最后一個reducer。

6) 針對一個key，partition的過程：

a. 首選判斷key的第1個byte，找到第1層非葉子節點
b. 再根據key的第2個byte，葉子節點
c. 每個葉子節點可能對應多個取樣(即多個reducer)，再逐個和每個樣比較，確定分配給哪一個reducer

5、圖解partition的“索引樹”

對上面的文字描述可能比較難理解，etongg 同學建議我畫個圖。所有才有了下面這些文字。感謝etongg和大家對本帖的關注。

“索引樹”的作用是為了讓key快速找到對應的reducer。下圖是我畫的索引樹示意圖：

對上面的圖做一點解釋：
1、為了簡單，我只畫了A、B、C三個節點，實際的是有256個節點的。
2、這個圖假設有20個reducer（下標0到19），那么我們最終獲得n-1個樣，即19個樣（下標為18的為最后一個樣）
3、圖中的圓圈，代表索引樹上的節點，索引樹共3層。
4、葉子節點下面的長方形代表取樣數組。紅色的數字代表取樣的下標。
5、每個節點都對應取樣數組上的一個下標范圍（更準備的說，是對應一個partition number的范圍，每個partition number代表一個reducer）。這個范圍在途中用藍色的文字標識。

前面文中有一句話：
比第i個樣小的key，被分配到第i個reducer，剩下的被分配到最后一個reducer

這里做一個小小的糾正，應該是：
小于或者等于第i個樣的key，被分配到第i個reducer，剩下的被分配到最后一個reducer。

下面開始partition：
如果key以”AAA”開頭，被分配到第“0”個reducer。
如果key以”ACA”開頭，被分配到第“4”個reducer。
如果key以”ACD”開頭，被分配到第“4”個reducer。
如果key以”ACF”開頭，被分配到第“5”個reducer。

那么，
如果key以”ACZ”開頭，被分配到第幾個reducer？？
答案是：被分配到第“6”個reducer。

同理，
如果key以”CCZ”開頭，被分配到第“19”個reducer，也就是最后一個reducer。

6、為什么不用HashPartitioner？

還需要再說明的一點：
上面自定義的Partitinoner的作用除了快速找到key對應的reducer，更重要的一點是：這個Partitioner控制了排序的總體有序！

上文中提到的“排序是MapReduce的天然特性！”這句話有點迷惑性。更準確的說，這個“天然特性”只保證了：a) 每個map的輸出結果是有序的； b) 每個reduce的輸入是有序的（參考下面的圖）。而1TB的整體有序還需要靠Partitioner的幫助！

Partitioner控制了相似的key(即前綴相同)落在同一個reducer里，然后mapreduce的“天然特性”再保證每個reducer的輸入（在正式執行reduce函數前，有一個排序的動作）是有序的！

這樣就理解了為什么不能用HashPartitioiner了。因為自定義的Partitioner要保證排序的“整體有序”大方向。

另外，推薦一篇關于partitioner博文： Hadoop Tutorial Series, Issue #2: Getting Started With (Customized) Partitioning

再貼《Hadoop.The.Definitive.Guide》中一張圖，更有利于理解了：

*** THE END ***