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

1、隨著現(xiàn)代企業(yè)和互聯(lián)網(wǎng)應(yīng)用中數(shù)據(jù)種類的迅速增多，各種各樣的數(shù)據(jù)規(guī)模已經(jīng)呈現(xiàn)出了指數(shù)級(jí)增長的趨勢(shì)。在數(shù)據(jù)增長的同時(shí)，更多復(fù)雜的處理要求也在出現(xiàn)。在Web應(yīng)用中，逐漸出現(xiàn)了對(duì)大規(guī)模數(shù)據(jù)進(jìn)行查詢和分析的任務(wù)。對(duì)于這種數(shù)據(jù)處理要求，不管是傳統(tǒng)的集中式還是分布式技術(shù)都不能提出有效和高效的解決方案。因?yàn)閷?duì)海量的數(shù)據(jù)進(jìn)行復(fù)雜的處理要求超出了傳統(tǒng)關(guān)系型數(shù)據(jù)庫的能力范圍之內(nèi)。
　　 相反地，大規(guī)模集群被越來越多地應(yīng)用于數(shù)據(jù)密集型計(jì)算中。這主要?dú)w于集

2、群性能上的三個(gè)特點(diǎn)：(1)可伸縮性：集群可以按照不同應(yīng)用的具體需求增加或減少執(zhí)行任務(wù)的機(jī)器節(jié)點(diǎn)。(2)容錯(cuò)性：集群中數(shù)據(jù)一般會(huì)有3個(gè)備份。當(dāng)原數(shù)據(jù)所在節(jié)點(diǎn)出現(xiàn)錯(cuò)誤的時(shí)候，系統(tǒng)會(huì)終止當(dāng)前節(jié)點(diǎn)上的所有操作，到一個(gè)有備份數(shù)據(jù)的節(jié)點(diǎn)上繼續(xù)執(zhí)行之前的操作。(3)高可用性：在程序訪問的集群節(jié)點(diǎn)出現(xiàn)故障的時(shí)候，不中斷任務(wù)的執(zhí)行，從其他節(jié)點(diǎn)繼續(xù)當(dāng)前任務(wù)，保證使集群的高可用性。
　　 基于大規(guī)模集群的這些優(yōu)點(diǎn)，我們?cè)谏厦孢M(jìn)行了數(shù)據(jù)連接(join)

3、操作的研究工作。連接是數(shù)據(jù)庫的經(jīng)典操作之一，它極好地解決了從有共同屬性的多表中提取信息的問題。因此連接算法一直在各種應(yīng)用中發(fā)揮著極大的作用。
　　 本文主要有以下三方面的貢獻(xiàn)：
　　 1.本文比較了Map、Reduce和Shuffle三個(gè)階段在執(zhí)行連接算子時(shí)的代價(jià)，并對(duì)性能瓶頸進(jìn)行了分析。文中在大規(guī)模集群的環(huán)境下，基于Map/Reduce編程模型，實(shí)現(xiàn)了直觀連接操作的過程。之后通過一系列的實(shí)驗(yàn)測(cè)試，比較Map、Shuff

4、le和Reduce這三個(gè)步驟的處理代價(jià)，并從中找出直觀連接算法實(shí)現(xiàn)的性能瓶頸在于Shuffle過程中大量的數(shù)據(jù)傳輸。
　　 2.本文提出了一種預(yù)散列(hash)處理技術(shù)來優(yōu)化直觀連接算法的性能。預(yù)處理的時(shí)候，把輸入數(shù)據(jù)按照連接屬性的散列值重新排列，具有相同散列值的元組存放在一起。經(jīng)過預(yù)處理之后的數(shù)據(jù)在Shuffle的過程中會(huì)減少數(shù)據(jù)傳輸?shù)拇螖?shù)，從而提高連接操作的性能。
　　 3.針對(duì)星型連接，本文提出了一種預(yù)散列索引分塊