亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

hadoop的1TB排序

系統(tǒng) 4014 0
原文鏈接: http://www.javaeye.com/topic/709986

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》中一張圖,更有利于理解了:

hadoop的1TB排序

*** THE END ***

hadoop的1TB排序


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!??!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 久久久国产精品免费 | 国产一级特黄aa毛片 | 在线观看片成人免费视频 | 成人不卡 | 91精品全国免费观看 | 99热这里只有精品国产免费 | 综合久色| 九九99香蕉在线视频免费 | 欧美高清理论片在线观看 | 91视频老司机| 久久国产片 | 成人免费视频国产 | 国内精品七七久久影院 | 色婷婷婷丁香亚洲综合不卡 | 亚洲阿v天堂在线观看2017 | 成人三级毛片 | 毛片直接看 | 日韩中文字幕精品久久 | 成人午夜精品网站在线观看 | 在线免费一级片 | 26uuu最新地址| 久久国产精品自在自线 | 国产一区亚洲二区三区 | 日本爱爱免费视频 | 毛片电| 亚欧中文字幕 | 老司机午夜精品视频 | 精品欧美成人bd高清在线观看 | 久久综合香蕉久久久久久久 | 四虎永久免费地址ww417 | 久久草在线视频国产一 | 毛片1级| 香港aa三级久久三级不卡 | 99热久久国产精品免费观看 | 久久久一级 | 99九九国产精品免费视频 | 女人18级毛片久久 | 色播影音| 91官网| 精品欧美一区二区精品久久 | 香蕉网站狼人久久五月亭亭 |