厦门大学数据库实验室MapReduce连接优化内容详解.ppt
《厦门大学数据库实验室MapReduce连接优化内容详解.ppt》由会员分享,可在线阅读,更多相关《厦门大学数据库实验室MapReduce连接优化内容详解.ppt(39页珍藏版)》请在启牛文库网上搜索。
1、厦门大学数据库实验室厦门大学数据库实验室 MapReduce 连接优化连接优化 报告人:李雨倩 导师:林子雨 2014.07.26连接技术简介连接技术简介基于传统基于传统 MapReduce 的连接的连接基于数据索引的连接基于数据索引的连接基于改进基于改进 MapReduce 的连接的连接连接技术比较连接技术比较 连接操作广泛应用于日志分析、联机分析处理及数据分析处理等方面。如果提高大数据连接计算速度,则可提高数据分析效率和用户体验度。下表对现有的MapReduce连接技术进行了分类与对比。连接技术简介连接技术简介基于传统基于传统 MapReduce 的连接的连接基于数据索引的连接基于数据索引
2、的连接基于改进基于改进 MapReduce 的连接的连接基于传统基于传统 MapReduce 的连接的连接 这类算法主要通过实现map函数、reduce函数及之间的数据流传递,来完成数据连接运算。对于这方面的研究主要集中于两表等值连接、两表非等值连接(又称连接)、两表相似度连接、多表等值连接(星型连接、链式连接)、多表非等值连接等问题。标准重分区算法标准重分区算法welcome to use these PowerPoint templates, New Content design, 10 years experience算法回顾算法回顾 标准重分区算法由一个标准重分区算法由一个MapRed
3、uce作业来完成连接运算。两个表的数作业来完成连接运算。两个表的数据都由据都由 Mapper 读入,根据查询条件进行过滤读入,根据查询条件进行过滤intermediate,生成,生成keyintermediate/valueintermediate对,其中对,其中 key是待连接列的数值,是待连接列的数值,valueintermediate则由用于标记数据来自哪个表的标签和记录值组成。在混洗则由用于标记数据来自哪个表的标签和记录值组成。在混洗过程中,具有相同连接值的数据会被分到同一个过程中,具有相同连接值的数据会被分到同一个Reducer上。上。Reducer根据标签将数据分为两个集合,再完成
4、连接运算。标准重分区算法在根据标签将数据分为两个集合,再完成连接运算。标准重分区算法在Reducer上需要将数据全部装载到内存中,可能会造成内存溢出。另外,上需要将数据全部装载到内存中,可能会造成内存溢出。另外,当存在数据倾斜时,标准重分区算法容易造成数据分布不均,以及连接当存在数据倾斜时,标准重分区算法容易造成数据分布不均,以及连接速度缓慢和计算资源分布不均等问题。速度缓慢和计算资源分布不均等问题。改进的标准重分区算法改进的标准重分区算法welcome to use these PowerPoint templates, New Content design, 10 years experi
5、ence算法回顾算法回顾 为了解决标准重分区算法需要占用较大内存的问题,改进的标准为了解决标准重分区算法需要占用较大内存的问题,改进的标准重分区算法进行了以下优化:生成重分区算法进行了以下优化:生成 keyintermediate/valueintermediate对时,对时,keyintermediate值由待连接列的数值与表的标签共同构成,这样可以使值由待连接列的数值与表的标签共同构成,这样可以使一个表的数据都排在另一个表的前面。在混洗阶段,通过自定义的一个表的数据都排在另一个表的前面。在混洗阶段,通过自定义的partition函数来使含有同一连接值的数据仍然分到同一个函数来使含有同一连接
6、值的数据仍然分到同一个Reducer上。在上。在Reduce阶段,在内存中缓存较小的表,另一表以流式方式读阶段,在内存中缓存较小的表,另一表以流式方式读入并进行连接操作。入并进行连接操作。广播算法广播算法welcome to use these PowerPoint templates, New Content design, 10 years experience算法回顾算法回顾 广播算法将待连接的两个表中较小的表以广播的方式传输广播算法将待连接的两个表中较小的表以广播的方式传输到另一个表所在节点上,然后在该节点上进行连接操作。广到另一个表所在节点上,然后在该节点上进行连接操作。广播算法只需
7、要一个无播算法只需要一个无Reduce的的MapReduce作业就可以完成,作业就可以完成,省去了数据混洗与排序的过程。当两表数据量相差很大时,省去了数据混洗与排序的过程。当两表数据量相差很大时,广播算法具有很高的效率。然而当待连接的两个表都很大时,广播算法具有很高的效率。然而当待连接的两个表都很大时,广播算法效率很低。广播算法效率很低。半连接算法半连接算法welcome to use these PowerPoint templates, New Content design, 10 years experience算法回顾算法回顾 半连接算法使用三个半连接算法使用三个 MapReduce作
8、业来完成运算,第一作业来完成运算,第一个个MapReduce 作业生成第一个表作业生成第一个表S的连接值文件。第二个的连接值文件。第二个MapReduce作业利用前一步生成的连接值文件,采用类似作业利用前一步生成的连接值文件,采用类似广播算法的方法对第二个表广播算法的方法对第二个表R的数据进行过滤。第三个的数据进行过滤。第三个MapReduce作业利用过滤后的作业利用过滤后的R表数据,采用广播算法进行表数据,采用广播算法进行连接。连接。分片半连接算法分片半连接算法welcome to use these PowerPoint templates, New Content design, 10
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 厦门大学 数据库 实验室 MapReduce 连接 优化 内容 详解