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 ***
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
