基于hadoop的连接算法中数据倾斜问题的研究

《基于hadoop的连接算法中数据倾斜问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中圈料孽敢求犬誊硕士学位论文基于hadOOp的连接算法中数据倾斜问题的研究作者姓名：学科专业：导师姓名：完成时间：吴磊计算机软件与理论李京教授二0一四年四月川删Ⅲ

2、

3、JII川㈣Ⅷ㈣I

4、

5、

6、

7、舢Y2590255U11iVersityofScieIlcea11dTechll0109yofChillaAdissertationf．ormasterdegreeResearehonDataSkewinjoinbaseonhadoopAuthor：Speciality：Supervisor：LeiⅥ厂uCoumput

8、erScienceProf．JingLiFinishedTime：April，2014中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：三龃签字日期：寥f丫：F：印中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权

9、按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。作者签名：装垄羔导师签名：签字日期：为忖F2c}签字日期：一旱盟塑摘要时至今日，随着各项科学技术的飞速发展，大数据处理的需求日益增长。hadoopm印／reduce作为一个并行数据处理框架，被越来越多的应用到分布式数据处理当中。

10、map／reduce是一个高效的，可扩展的，高容错的并行编程模型，并且十分易于使用。连接操作作为数据处理中一种十分重要的操作，在传统数据库中已经得到了很多的研究，由于map／reduce自身框架的原因，它并不能很好地支持连接操作。如今已经有很多map／reduce框架下的连接算法，但是这些算法大多没有很好地处理数据倾斜问题，当数据倾斜存在时，会导致数据分布不均匀，降低了分布式算法的执行效率。本文首先简要的介绍了数据倾斜问题的影响。然后针对两表等值连接提出了分区连接算法，该算法基于分而治之的思想将倾斜数据和

11、非倾斜数据区别对待，结合了传统连接算法、广播连接算法等算法思想，很好的解决了数据倾斜情况下任务负载分布不均匀的问题。接着，针对多表等值连接中的数据倾斜问题，我们利用范围哈希以及单轮map／reduce任务完成多表连接的算法，均匀了数据处理的负载，较好地解决了数据倾斜的影响。最后，我们根据算法进行了一系列实验，通过我们的算法和传统的连接算法，证明了算法的实用性。关键词：大数据，map／reduce，连接算法，数据倾斜ABSTRACTNow，withtherapiddevelopmentofsciencean

12、d七echn0109y)thegrowingdemandforb逗dataisprocessing．Hadoopmap／reducehaSbeenusedmoreandmoreindistributeddataprocessingasaparaUeldataprocessingframework．Map／reduceisae伍cient，scalable，highlyfault—tolerantparallelprogrammingmodel．AnditisveryeaSytouse．Thejoinisa

13、nimportantoperatorindataprocessingwllichhasbeenstudieda10tintraditionaldatabase．Becauseofthemap／reduceframeworkitself，itcannotsupportjoinoperatorperfectly．Therearemallyjoinakorithmsformap／reduce，butmostofthemhaveprobleminhandlingdataskewproblem．Dataskewwi

14、UresultinunevendistributionofdataandreducetheeⅡiciencyofthedistributedalgorithm．Firstly，thisarticleintroducestheimpactofdatasl【ewproblem．Secondly，wreproposedepartingjoinforthejoinoft’votables．Thisalgorithmtakesdi圩er