厦门大学数据库实验室-蔡珉星-数据倾斜情况下基于.ppt

数据倾斜情况下 基于MapReduce的Join算法优化 报告人：蔡珉星 厦大数据库实验室 2014-08-16 遇到的问题 目录 优化思路 - 改进Partition Partition在两表连接中的改进 LEEN算法 Part 1 优化思路 - 改进Partition MapReduce中的Partition： 在Map端输出时，需要对key进行分区，来决定输出数据传输到哪个reducer上进行处理。 默认的partition是通过哈希操作来决定分配到哪个reducer。 哈希Partition的局限 哈希在数据均衡的情况下，可以很好的将数据平均到各个Reducer上，但在数据倾斜情况下，会导致某几个Key的值大量集聚在单个Reducer上。 Partition 哈希实际上是一种针对键的分组均衡分配，不能保证数据量均衡分配 Reduce-side Join： Map-side Join(复制连接、半连接)对数据集要求较高，一般情况下Join操作是采用Reduce-side Join - 重分区连接：将键相同的数据分到同一个reducer，再进行Join。 优化重分区连接: 区分大小数据集，将小数据集读取到内存中，再用小数据集来遍历大数据集。 优化重分区连接的精髓就在于Reduce端用小数据集遍历大数据集，这部分已经没有什么改进空间。哪里还可以再改进？ -- Partition: 优化重分区连接采用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 Cloud》中的算法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，可以根据步长 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: key≤3 3key≤5 5key≤6 6key≤9 9key [1,3,3] [4,5,5] [6,6,6,6] [8,9,9] [10,10] 倾斜情况: Samples: [1, 3, 3, 4, 5, 5, 6, 6, 6, 6, 6, 6, 9, 10, 10], 5个Reducer，步进3 分区序列: [3, 5, 6, 6] - 键为6的有两个可选Reducer 解决: build relation: 随机选择一个可选Reducer probe relation: 需发送到每个可选Reducer R join S - R: probe, S: build? 两表连接中的改进 倾斜键存在大小表的情况 Samples: [1, 3, 3, 4, 5, 5