模集群上基于預(yù)散列的連接處理和優(yōu)化

《模集群上基于預(yù)散列的連接處理和優(yōu)化》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、萬方數(shù)據(jù)計算機研究與發(fā)展ISSN1000—1239／CN11一I777／TPJournalofComputerResearchandDevelopment47(Suppl．)：146—153．2010大規(guī)模集群上基于預(yù)散列的連接處理和優(yōu)化常洞霞錢衛(wèi)寧周傲英(華東師范大學軟件學院上海200062)(wnqian@sei．ecnu．edu．cn)JoinProcessingandOptimizingBasedonPre—HashoverLargeClustersChangDongxia，QJanWeining，andZhouAoying(SoftⅡ)areEngineeringInsti

2、tute，EastChinaNormalUniversity，Shanghai200062)AbstractWiththeincreasingofdatasizeinmodernapplicationsandtheemergenceofcomplicatedprocessingneeds，thetraditionalcentralizedanddistributeddataprocessingtechnologiescan’tworkwell．Inthissituation，thelargescaleclustershavebeenusedwidelyindata-intensive

3、applicationsbecauseoftheirscalability，highavailabilityandfaulttolerance．Inthispaper，wehavethreecontributionstojoinprocessingandoptimizingoverlargeclusters．Firstly，weanalyzethebottleneckofHashjoinprocessingbasedonMap／Reduceframework．Secondly，weproposeamethodwhichusespre-HashtooptimizejoininMap／R

4、educe．Thirdly，weresearchtheoptimizationtechnologyofstarjoin．Andfromthecostmodelestimationandexperiments，ourmethodscanimprovethejoinefficiencyoverlargeclusterssignificantly．KeywordsMapReduce；Hashjoin；starjoin；index；optimize摘要隨著現(xiàn)代應(yīng)用中數(shù)據(jù)規(guī)模的迅速增長，以及復(fù)雜處理要求的出現(xiàn)，傳統(tǒng)的集中式和分布式數(shù)據(jù)處理技術(shù)已經(jīng)不能滿足需要；而大規(guī)模集群由于具有可伸縮性、高可

5、用性、容錯性的優(yōu)勢，逐漸為數(shù)據(jù)密集型應(yīng)用所廣泛使用．這里針對大規(guī)模集群上數(shù)據(jù)連接(join)操作的效率問題：1)分析了基于Map／Reduce框架的連接操作實現(xiàn)的效率瓶頸；2)提出了一種采用預(yù)散列(hash)的連接操作實現(xiàn)技術(shù)；3)研究了針對星型連接的優(yōu)化技術(shù)．代價模型分析與實驗顯示，此處提出的方法能夠有效提高連接操作的效率．關(guān)鍵詞MapReduce；散列連接；星型連接；索引；優(yōu)化中圖法分類號TP311．13；TP316．4在web應(yīng)用、科學計算和大型企業(yè)商務(wù)智能等應(yīng)用中，“大數(shù)據(jù)”(bigdata)問題日益嚴重，即數(shù)據(jù)規(guī)模迅速增加、處理要求越來越多、越來越復(fù)雜．數(shù)據(jù)規(guī)模和數(shù)據(jù)處理復(fù)

6、雜性的發(fā)展速度甚至超過了硬件處理能力的發(fā)展速度．因此，傳統(tǒng)的集中式或小規(guī)模分布式系統(tǒng)上的數(shù)據(jù)管理和處理技術(shù)，由于在可伸縮性、高可用性和容錯性等方面的限制，已經(jīng)無法適應(yīng)數(shù)據(jù)密集型計算應(yīng)用的環(huán)境．同時，大規(guī)模集群收疆日期；2010一06—25基金項目：國家自然科學基金項目(60833003)通信作者：錢衛(wèi)寧(wnqian@sei．ecnu．edu．cn)(cluster)通過冗余和并行處理，在性能和代價等方面顯示出明顯的優(yōu)勢．一些重要的互聯(lián)網(wǎng)計算平臺都采用或者提供大規(guī)模集群．這其中包括Google的GoogleFileSystemLll和Map／Reduce計算模型[z]、Amazon的

7、EC2計算平臺[31和S3存儲平臺[41等．本文研究大規(guī)模集群上，數(shù)據(jù)連接操作的實現(xiàn)與優(yōu)化技術(shù)．由于目前被廣泛接受和使用的Map／Reduce框架為了簡化并行程序設(shè)計，并不支持內(nèi)嵌萬方數(shù)據(jù)常洞霞等：大規(guī)模集群上基于預(yù)散列的連接處理和優(yōu)化147的合并(merge)和連接操作，因此如何提供高效的連接效率就成為大規(guī)模集群上數(shù)據(jù)處理的一個重要問題．本文針對這一問題，研究連接操作的實現(xiàn)技術(shù)，以及數(shù)據(jù)分析中常用的星型連接(star—join)優(yōu)化技術(shù)．1．相關(guān)工作Ma