模集群上基于预散列的连接处理和优化

《模集群上基于预散列的连接处理和优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据计算机研究与发展ISSN1000—1239／CN11一I777／TPJournalofComputerResearchandDevelopment47(Suppl．)：146—153．2010大规模集群上基于预散列的连接处理和优化常洞霞钱卫宁周傲英(华东师范大学软件学院上海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摘要随着现代应用中数据规模的迅速增长，以及复杂处理要求的出现，传统的集中式和分布式数据处理技术已经不能满足需要；而大规模集群由于具有可伸缩性、高可

5、用性、容错性的优势，逐渐为数据密集型应用所广泛使用．这里针对大规模集群上数据连接(join)操作的效率问题：1)分析了基于Map／Reduce框架的连接操作实现的效率瓶颈；2)提出了一种采用预散列(hash)的连接操作实现技术；3)研究了针对星型连接的优化技术．代价模型分析与实验显示，此处提出的方法能够有效提高连接操作的效率．关键词MapReduce；散列连接；星型连接；索引；优化中图法分类号TP311．13；TP316．4在web应用、科学计算和大型企业商务智能等应用中，“大数据”(bigdata)问题日益严重，即数据规模迅速增加、处理要求越来越多、越来越复杂．数据规模和数据处理复

6、杂性的发展速度甚至超过了硬件处理能力的发展速度．因此，传统的集中式或小规模分布式系统上的数据管理和处理技术，由于在可伸缩性、高可用性和容错性等方面的限制，已经无法适应数据密集型计算应用的环境．同时，大规模集群收疆日期；2010一06—25基金项目：国家自然科学基金项目(60833003)通信作者：钱卫宁(wnqian@sei．ecnu．edu．cn)(cluster)通过冗余和并行处理，在性能和代价等方面显示出明显的优势．一些重要的互联网计算平台都采用或者提供大规模集群．这其中包括Google的GoogleFileSystemLll和Map／Reduce计算模型[z]、Amazon的

7、EC2计算平台[31和S3存储平台[41等．本文研究大规模集群上，数据连接操作的实现与优化技术．由于目前被广泛接受和使用的Map／Reduce框架为了简化并行程序设计，并不支持内嵌万方数据常洞霞等：大规模集群上基于预散列的连接处理和优化147的合并(merge)和连接操作，因此如何提供高效的连接效率就成为大规模集群上数据处理的一个重要问题．本文针对这一问题，研究连接操作的实现技术，以及数据分析中常用的星型连接(star—join)优化技术．1．相关工作Ma