大规模集群上的连接处理与优化

《大规模集群上的连接处理与优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2011届研究季2011MasterDegreeThesis嬲黜必Y190394省”UniversitvCode：l0269StlldentID：51081500003EastChinaNormalUniVersi够JOINPRPCESSINGANDOPTIMIZING0NLARGECLUSTERSD印artment：SQ鱼型堑曼量坠堑旦曼星丑垒g鱼囟坐!曼Major：￡Q堡卫堕!丛墨Q鱼型堑星垫鱼!b曼Q碰Domain：羔选坠旦垒±垒丛垒坠垦g星塑星垒!垒望鱼Qi曼!亘坠旦l曼鱼￡Q幽坚!i坠gSuperVisor：翌选i垒i塾gQi鱼旦Applic

2、ant：旦Q垒g丕i垦∑)i≥!蟮2011．5华东师范大学学位论文原创性声明郑重声明：本人呈交的学位论文《大规模集群上的连接处理与优化》，是在华东师范大学攻读硕左／博士(请勾选)学位期间，在导师的指导下进行的研究工作及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。作者签名：日期：≯，／年}月；p日华东师范大学学位论文著作权使用声明《大规模集群上的连接处理与优化》系本人在华东师范大学攻读学位期间在导师指／导下完成的’硕≠／博士(请勾选)学

3、位论文，本论文的研究成果归华东师范大学所有。本’■-，人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和相关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版；允许学位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全国博士、硕士学V位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。本学位论文属于(请勾选)()1．经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文宰，于导师签名日解密，解密后适用上述授权。适用上述授权。木“涉密”学位论文应是

4、已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位论文(需附获批的《华东师范大学研究生申请学位论文“涉密”审批表》方为有效)，未经上述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用上述授权)。艮炉卑一名吖签≯№≯堂涸重硕士学位论文答辩委员会成员名单姓名职称单位备注复旦大学计算机科学技术周水庚教授主席学院王晓玲教授华东师范大学软件学院金澈清副教授华东师范大学软件学院摘要随着现代企业和互联网应用中数据种类的迅速增多，各种各样的数据规模已经呈现出了指数级增长的趋势。在数据增长的同时，更多复杂的处理要求也在出现。在W

5、曲应用中，逐渐出现了对大规模数据进行查询和分析的任务。对于这种数据处理要求，不管是传统的集中式还是分布式技术都不能提出有效和高效的解决方案。因为对海量的数据进行复杂的处理要求超出了传统关系型数据库的能力范围之内。相反地，大规模集群被越来越多地应用于数据密集型计算中。这主要归于集群性能上的三个特点：(1)可伸缩性：集群可以按照不同应用的具体需求增加或减少执行任务的机器节点。(2)容错性：集群中数据一般会有3个备份。当原数据所在节点出现错误的时候，系统会终止当前节点上的所有操作，到一个有备份数据的节点上继续执行之前的操作。(3)高可用性：在程序访问的集群节

6、点出现故障的时候，不中断任务的执行，从其他节点继续当前任务，保证使集群的高可用性。基于大规模集群的这些优点，我们在上面进行了数据连接(join)操作的研究工作。连接是数据库的经典操作之二，它极好地解决了从有共同属性的多表中提取信息的问题。因此连接算法一直在各种应用中发挥着极大的作用。本文主要有以下三方面的贡献：1．本文比较了Map、Reduce和Shume三个阶段在执行连接算子时的代价，并对性能瓶颈进行了分析。文中在大规模集群的环境下，基于Map／Reduce编程模型，实现了直观连接操作的过程。之后通过一系列的实验测试，比较Map、Shufne和Red

7、uce这三个步骤的处理代价，并从中找出直观连接算法实现的性能瓶颈在于Shufne过程中大量的数据传输。2．本文提出了一种预散列(hash)处理技术来优化直观连接算法的性能。预处理的时候，把输入数据按照连接属性的散列值重新排列，具有相同散列值的元组存放在一起。经过预处理之后的数据在Shufne的过程中会减少数据传输的次数，从而提高连接操作的性能。3．针对星型连接，本文提出了一种预散列索引分块技术来提高星型连接的执行效率。优化算法在对数据进行预散列的过程中生成索引，然后利用索引在星型连接操作中过滤掉一些不必要的数据，减少Shuffle阶段的传输数据量和Re

8、duce阶段的计算量。从算法的代价模型与最后的实验数据可以看出，本文所提出的两种连接优化方法都