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

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

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

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

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