



下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 互聯(lián)網(wǎng)+農(nóng)業(yè)模式推動(dòng)農(nóng)民脫貧致富的路徑探索
- 大數(shù)據(jù)技術(shù)在農(nóng)業(yè)保險(xiǎn)中的應(yīng)用前景
- 2025至2030落袋機(jī)行業(yè)項(xiàng)目調(diào)研及市場(chǎng)前景預(yù)測(cè)評(píng)估報(bào)告
- 綠色生態(tài)平價(jià)護(hù)膚套裝行業(yè)趨勢(shì)預(yù)測(cè)與市場(chǎng)分析
- 2025至2030全球及中國網(wǎng)絡(luò)招聘行業(yè)項(xiàng)目調(diào)研及市場(chǎng)前景預(yù)測(cè)評(píng)估報(bào)告
- 2025至2030中國自家制面粉行業(yè)市場(chǎng)占有率及投資前景評(píng)估規(guī)劃報(bào)告
- 2025至2030中國自動(dòng)燙金機(jī)行業(yè)市場(chǎng)占有率及投資前景評(píng)估規(guī)劃報(bào)告
- 2025至2030中國自動(dòng)化稅務(wù)軟件行業(yè)市場(chǎng)深度研究及發(fā)展前景投資可行性分析報(bào)告
- 現(xiàn)代物流園區(qū)規(guī)劃與管理
- 2025至2030中國腺嘌呤核苷行業(yè)市場(chǎng)占有率及投資前景評(píng)估規(guī)劃報(bào)告
- 第七章城市軌道交通屏蔽門設(shè)備接口68課件
- 國家開放大學(xué)漢語言文學(xué)本科《中國現(xiàn)代文學(xué)專題》期末紙質(zhì)考試第三大題分析題庫2025春期版
- 成都大學(xué)附屬中學(xué)英語新初一分班試卷含答案
- 創(chuàng)新創(chuàng)業(yè)大賽項(xiàng)目商業(yè)計(jì)劃書模板
- 2025年1月國家開放大學(xué)漢語言文學(xué)本科《心理學(xué)》期末紙質(zhì)考試試題及答案
- 糖尿病酮癥酸中毒疑難病例護(hù)理
- 居民生活垃圾轉(zhuǎn)運(yùn)投標(biāo)方案(技術(shù)方案)
- 《智慧園藝》課程教學(xué)大綱
- 2025年上半年工作總結(jié)及下半年工作計(jì)劃簡單版(2篇)
- 企業(yè)道路交通安全宣傳
- 635MPa級(jí)熱軋帶肋高強(qiáng)鋼筋應(yīng)用技術(shù)規(guī)程
評(píng)論
0/150
提交評(píng)論