論文閱讀成果和創(chuàng)新點(diǎn)

1、論文閱讀成果和創(chuàng)新點(diǎn)論文閱讀成果和創(chuàng)新點(diǎn)廈門大學(xué)數(shù)據(jù)庫實(shí)驗(yàn)室廈門大學(xué)數(shù)據(jù)庫實(shí)驗(yàn)室羅道文羅道文2015-03-07 SAND_JOIN algorithm目目 錄錄 基于基于Locality-Aware的的reduce任務(wù)調(diào)度任務(wù)調(diào)度 SAND_JOIN算法算法不足之處不足之處 SAND_JOIN算法改進(jìn)算法改進(jìn)SAND_JOIN algoririthm簡單的范圍分區(qū)思想：在執(zhí)行reduce-join連接之前，先運(yùn)行一個(gè)job，統(tǒng)計(jì)鍵值的分布情況，即抽樣思想，接著利用樣本的鍵值分布情況，對(duì)所有數(shù)據(jù)進(jìn)行分區(qū)。分為：簡單范圍分區(qū)和虛擬處理器范圍分區(qū)。思想：Map端采樣：每個(gè)Mapper隨機(jī)選取X個(gè)樣

2、本，有n個(gè)Mapper。 Reduce端統(tǒng)計(jì)分布：只需要一個(gè)Reducer對(duì)樣本所有key值統(tǒng)計(jì)分析，構(gòu)造出分區(qū)序列。 SAND_JOIN algoririthm若執(zhí)行的Join連接有N個(gè)Reduce,則可以根據(jù)步長n*x/N獲得一個(gè)分區(qū)序列。例如： Sample:1,3,3,4,5,5,6,6,6,6,8,9,9,10,10,5個(gè)Reducer，步長為3， 分區(qū)序列為:3,5,6,9 Join Partition: key3 3key5 5key6 6key9 9 鍵為6的有兩個(gè)可選Reducer 解決: build relation: 隨機(jī)選擇一個(gè)可選Reducer probe relat

3、ion: 需發(fā)送到每個(gè)可選Reducer 適合一個(gè)大表一個(gè)小表的情況！ SAND_JOIN algoririthm傾斜鍵存在大小表的情況 Samples: 1, 3, 3, 4, 5, 5, 6, 6, 6, 6, 6, 6, 9, 10, 10, 5個(gè)Reducer，步進(jìn)3 分區(qū)序列: 3, 5, 6, 6 - 鍵為6的有兩個(gè)可選Reducer 3 和 4 R join S，對(duì)于鍵6，若 R.6 = S.6 可將所有的S.6傳輸?shù)?和4上，然后R.6可以隨機(jī)分配到3或4上其實(shí)就是x*y=x*(y1+y2)=x*y1+x*y2SAND_JOIN algoririthm論文具體實(shí)現(xiàn)： 1.將小表

4、S加載到每一臺(tái)機(jī)器，建立哈希表，的形式。 2.當(dāng)R表某個(gè)鍵值key分配到某個(gè)Reducer上時(shí)，從哈希表中檢索key的value值，即tuplelist,與R表中的元組做Join操作。SAND_JOIN algoririthm虛擬處理器范圍分區(qū) 實(shí)際是N個(gè)Reducer，但假定分成 *N 個(gè)分區(qū)(為整數(shù))。 例如Samples: 1, 3, 4, 4, 5, 5, 6, 6, 6, 6, 6, 6, 9, 10, 10, 11, 11, 11, 15, 16, 5個(gè)ReducerJoin Partition: 1,3,4,4, 5,5,6,6, 6,6,6,6, 9,10,10,11,11,1

5、1, 15,16 = 2，則分成2*5=10個(gè)分區(qū)Samples: 1, 3, 3, 4, 5, 5, 6, 6, 6, 6, 6, 6, 9, 10, 10, 11, 11, 11, 15, 16, 10個(gè)ReducerJoin Partition: 1,3,3, 4, 5,5, 6,6, 6,6, 6,6, 9,10,10, 11, 11,11, 15,16 采用虛擬范圍分區(qū)，數(shù)據(jù)分配更加均衡 處理方式: 輪叫調(diào)度 或 當(dāng)某一節(jié)點(diǎn)完成時(shí)，將下一剩余任務(wù)分配給該節(jié)點(diǎn) 論文的實(shí)驗(yàn)結(jié)果表明虛擬范圍分區(qū)優(yōu)于簡單范圍分區(qū)SAND_JOIN algoririthmLocality-Aware的的reduce任務(wù)調(diào)度任務(wù)調(diào)度思想：盡量將某個(gè)key分配給所有節(jié)點(diǎn)中該key最大的節(jié)點(diǎn)。 優(yōu)點(diǎn)：減少數(shù)據(jù)量的傳輸。“Hadoops framework adopts a pull scheduling strategy rather than a push one” 意思就是說JobTracker并不是把map和reduce任務(wù)push給TaskTracer,而是TaskTracker通過請(qǐng)求向JobTracker pull一個(gè)map或者reduce任務(wù)?；谖恢酶兄膔educe任務(wù)調(diào)度Locality-Awa