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

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

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

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

2、排序的過程

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

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

    

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

排序的任務(wù)：按照key的順序排。

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

3、排序的原理

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

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

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

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

4、取樣和partition的過程

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

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

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

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

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

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

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

5、圖解partition的“索引樹”

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

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

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

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

這里做一個小小的糾正，應(yīng)該是：
小于或者等于第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對應(yīng)的reducer，更重要的一點是：這個Partitioner控制了排序的總體有序！

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

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

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

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

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

*** THE END ***