大規(guī)模集群上的連接處理與優(yōu)化

《大規(guī)模集群上的連接處理與優(yōu)化》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、2011屆研究季2011MasterDegreeThesis嬲黜必Y190394省”UniversitvCode：l0269StlldentID：51081500003EastChinaNormalUniVersi夠JOINPRPCESSINGANDOPTIMIZING0NLARGECLUSTERSD印artment：SQ魚型塹曼量墜塹旦曼星丑壘g魚囟坐!曼Major：￡Q堡衛(wèi)墮!叢墨Q魚型塹星墊魚!b曼Q碰Domain：羔選墜旦壘±壘叢壘墜墾g星塑星壘!壘望魚Qi曼!亙墜旦l曼魚￡Q幽堅!i墜gSuperVisor：翌選i壘i塾gQi魚旦Applic

2、ant：旦Q壘g丕i墾∑)i≥!蟮2011．5華東師范大學學位論文原創(chuàng)性聲明鄭重聲明：本人呈交的學位論文《大規(guī)模集群上的連接處理與優(yōu)化》，是在華東師范大學攻讀碩左／博士(請勾選)學位期間，在導師的指導下進行的研究工作及取得的研究成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含其他個人已經(jīng)發(fā)表或撰寫過的研究成果。對本文的研究做出重要貢獻的個人和集體，均已在文中作了明確說明并表示謝意。作者簽名：日期：≯，／年}月；p日華東師范大學學位論文著作權(quán)使用聲明《大規(guī)模集群上的連接處理與優(yōu)化》系本人在華東師范大學攻讀學位期間在導師指／導下完成的’碩≠／博士(請勾選)學

3、位論文，本論文的研究成果歸華東師范大學所有。本’■-，人同意華東師范大學根據(jù)相關(guān)規(guī)定保留和使用此學位論文，并向主管部門和相關(guān)機構(gòu)如國家圖書館、中信所和“知網(wǎng)”送交學位論文的印刷版和電子版；允許學位論文進入華東師范大學圖書館及數(shù)據(jù)庫被查閱、借閱；同意學校將學位論文加入全國博士、碩士學V位論文共建單位數(shù)據(jù)庫進行檢索，將學位論文的標題和摘要匯編出版，采用影印、縮印或者其它方式合理復制學位論文。本學位論文屬于(請勾選)()1．經(jīng)華東師范大學相關(guān)部門審查核定的“內(nèi)部”或“涉密”學位論文宰，于導師簽名日解密，解密后適用上述授權(quán)。適用上述授權(quán)。木“涉密”學位論文應是

4、已經(jīng)華東師范大學學位評定委員會辦公室或保密委員會審定過的學位論文(需附獲批的《華東師范大學研究生申請學位論文“涉密”審批表》方為有效)，未經(jīng)上述部門審定的學位論文均為公開學位論文。此聲明欄不填寫的，默認為公開學位論文，均適用上述授權(quán))。艮爐卑一名吖簽≯№≯堂涸重碩士學位論文答辯委員會成員名單姓名職稱單位備注復旦大學計算機科學技術(shù)周水庚教授主席學院王曉玲教授華東師范大學軟件學院金澈清副教授華東師范大學軟件學院摘要隨著現(xiàn)代企業(yè)和互聯(lián)網(wǎng)應用中數(shù)據(jù)種類的迅速增多，各種各樣的數(shù)據(jù)規(guī)模已經(jīng)呈現(xiàn)出了指數(shù)級增長的趨勢。在數(shù)據(jù)增長的同時，更多復雜的處理要求也在出現(xiàn)。在W

5、曲應用中，逐漸出現(xiàn)了對大規(guī)模數(shù)據(jù)進行查詢和分析的任務(wù)。對于這種數(shù)據(jù)處理要求，不管是傳統(tǒng)的集中式還是分布式技術(shù)都不能提出有效和高效的解決方案。因為對海量的數(shù)據(jù)進行復雜的處理要求超出了傳統(tǒng)關(guān)系型數(shù)據(jù)庫的能力范圍之內(nèi)。相反地，大規(guī)模集群被越來越多地應用于數(shù)據(jù)密集型計算中。這主要歸于集群性能上的三個特點：(1)可伸縮性：集群可以按照不同應用的具體需求增加或減少執(zhí)行任務(wù)的機器節(jié)點。(2)容錯性：集群中數(shù)據(jù)一般會有3個備份。當原數(shù)據(jù)所在節(jié)點出現(xiàn)錯誤的時候，系統(tǒng)會終止當前節(jié)點上的所有操作，到一個有備份數(shù)據(jù)的節(jié)點上繼續(xù)執(zhí)行之前的操作。(3)高可用性：在程序訪問的集群節(jié)

6、點出現(xiàn)故障的時候，不中斷任務(wù)的執(zhí)行，從其他節(jié)點繼續(xù)當前任務(wù)，保證使集群的高可用性?；诖笠?guī)模集群的這些優(yōu)點，我們在上面進行了數(shù)據(jù)連接(join)操作的研究工作。連接是數(shù)據(jù)庫的經(jīng)典操作之二，它極好地解決了從有共同屬性的多表中提取信息的問題。因此連接算法一直在各種應用中發(fā)揮著極大的作用。本文主要有以下三方面的貢獻：1．本文比較了Map、Reduce和Shume三個階段在執(zhí)行連接算子時的代價，并對性能瓶頸進行了分析。文中在大規(guī)模集群的環(huán)境下，基于Map／Reduce編程模型，實現(xiàn)了直觀連接操作的過程。之后通過一系列的實驗測試，比較Map、Shufne和Red

7、uce這三個步驟的處理代價，并從中找出直觀連接算法實現(xiàn)的性能瓶頸在于Shufne過程中大量的數(shù)據(jù)傳輸。2．本文提出了一種預散列(hash)處理技術(shù)來優(yōu)化直觀連接算法的性能。預處理的時候，把輸入數(shù)據(jù)按照連接屬性的散列值重新排列，具有相同散列值的元組存放在一起。經(jīng)過預處理之后的數(shù)據(jù)在Shufne的過程中會減少數(shù)據(jù)傳輸?shù)拇螖?shù)，從而提高連接操作的性能。3．針對星型連接，本文提出了一種預散列索引分塊技術(shù)來提高星型連接的執(zhí)行效率。優(yōu)化算法在對數(shù)據(jù)進行預散列的過程中生成索引，然后利用索引在星型連接操作中過濾掉一些不必要的數(shù)據(jù)，減少Shuffle階段的傳輸數(shù)據(jù)量和Re

8、duce階段的計算量。從算法的代價模型與最后的實驗數(shù)據(jù)可以看出，本文所提出的兩種連接優(yōu)化方法都