数据倾斜情况下基于MapReduceJoin算法优化.ppt
《数据倾斜情况下基于MapReduceJoin算法优化.ppt》由会员分享,可在线阅读,更多相关《数据倾斜情况下基于MapReduceJoin算法优化.ppt(22页珍藏版)》请在三一文库上搜索。
1、数据倾斜情况下 基于MapReduce的Join算法优化,报告人:蔡珉星 厦大数据库实验室 2014-08-16,遇到的问题,目录,优化思路 - 改进Partition Partition在两表连接中的改进 LEEN算法,Part 1,优化思路 - 改进Partition,MapReduce中的Partition: 在Map端输出时,需要对key进行分区,来决定输出数据传输到哪个reducer上进行处理。 默认的partition是通过哈希操作来决定分配到哪个reducer。 哈希Partition的局限 哈希在数据均衡的情况下,可以很好的将数据平均到各个Reducer上,但在数据倾斜情况下,
2、会导致某几个Key的值大量集聚在单个Reducer上。,Partition,哈希实际上是一种针对键的分组均衡分配,不能保证数据量均衡分配,Reduce-side Join: Map-side Join(复制连接、半连接)对数据集要求较高,一般情况下Join操作是采用Reduce-side Join - 重分区连接:将键相同的数据分到同一个reducer,再进行Join。 优化重分区连接: 区分大小数据集,将小数据集读取到内存中,再用小数据集来遍历大数据集。 优化重分区连接的精髓就在于Reduce端用小数据集遍历大数据集,这部分已经没有什么改进空间。哪里还可以再改进? Partition: 优化
3、重分区连接采用Hash parition不能保证数据量均衡分配。,Join算法优化思路,优化重分区连接采用Hash parition,不能保证数据量均衡分配,Part 2,Partition在两表连接中的改进,两表连接中的改进,数据实例: 3个Data节点 每个节点输出75个键值,81 - 36% 103 - 46% 41 - 18%,即便可以采用优化重分区,但在Partition时已经造成了数据分配倾斜!,两表连接中的改进,均衡Partition 论文LEEN LocalityFairness- Aware Key Partitioning for MapReduce in the Clou
4、d中的算法LEEN给出的Partition:,74 - 33% 74 - 33% 77 - 34%,获知键值的分布,两表连接中的改进,获知键值的分布 采样 在执行Reducer-side Join之前,先运行一个Job,统计数据分布情况。 采样开销应尽可能少,同时保证准确性。 Partition方式: 简单范围分区 Map端采样:每个Mapper随机取x个Sample,有n个Mapper。 Reduce端统计分布:只需要一个Reducer,此时n*x个Sample已是排好序的。,两表连接中的改进,Partition方式: 简单范围分区(续) 若执行的Join有N个Reducer,可以根据步长
5、n*x/N 获得一个分区序列。 例如: Samples: 1, 3, 3, 4, 5, 5, 6, 6, 6, 6, 8, 9, 9, 10, 10, 5个Reducer,步进3 分区序列: 3, 5, 6, 9 Join Partition: key3 3 键为6的有两个可选Reducer 解决: build relation: 随机选择一个可选Reducer probe relation: 需发送到每个可选Reducer R join S - R: probe, S: build?,两表连接中的改进,倾斜键存在大小表的情况 Samples: 1, 3, 3, 4, 5, 5, 6, 6,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 倾斜 情况 基于 MapReduceJoin 算法 优化
链接地址:https://www.31doc.com/p-3184519.html