数据倾斜情况下基于MapReduce的Join算法优化

1、数据倾斜情况下基于MapReduce的Join算法优化遇到的问题遇到的问题目录优化思路优化思路 - 改进改进PartitionPartition在两表连接中的改进在两表连接中的改进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 2Partition在两表连接中的改进在两表连接中的改进两表连接中的改进两表连接中的改进 数据实例：数据实例：3个Data节点每个节点输出75个键值81 - 36%103 - 46%41 - 18%即便可以采用优化重分区，但在即便可以采用优化重分区，但在Partition时已经造成了数据分配倾斜！时已经造成了数据分配倾斜！两表连接中的改进两表连接中的改进 均衡均衡Partition 论文LEEN LocalityFairn

4、ess- 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端统计分布：只需要一个Reduce

5、r，此时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: key3 3key5 5key6 6key9 9 键为6的有两个可选Reducer 解决: build relation: 随机选择一个可选Reducer p

6、robe relation: 需发送到每个可选Reducer R join S - R: probe, S: build?两表连接中的改进两表连接中的改进 倾斜键存在大小表的情况倾斜键存在大小表的情况 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 3 和和 4 R join S，对于键6，若 R.6 29%30 - 40%17 - 22%Partition后，本地数据所占的比例后，本地数据所占的比例81 - 36%103 -

7、46%41 - 18%网络共需要传输的数据量：网络共需要传输的数据量： Total Map output (1 -Locality) 81*(1-29%) + 103*(1-40%) + 41*(1-22%) = 151151/225 = 67%LEEN算法算法 LEEN：异步：异步map和和reduce模式模式 Hadoop中的计算和数据传输是会重叠的（如一个节点上运行多个map任务，一个map任务结束后，就会进行数据传输）。 LEEN为了获知所有中间数值的分布情况，采用了异步map和reduce模式（先全部执行完map再执行reduce）。 map阶段对每个中间键的结果进行缓存，而不是直接

8、发送到相应的reducer。 这样当map结束时，就有了所有的键分布信息（出现次数等），这些键将根据LEEN算法来进行分配（到reducer）。LEEN算法算法 LEEN算法：平衡算法：平衡Locality和和FairnessFairness(0): 各个reduce分配的数据量的差异，越小越好；Locality(1): 各个reduce分配的数据中，来自本地节点的数据，越大越好； LEEN算法 - 启发式算法，启发式算法，目标：(Fairness/Locality)的最小值。 其他思路：其他思路： 因素: Fairness、Locality哪个对Job结果影响更大？(0.2/0.4与0.4/0.8哪个更优?) 体现: 集群的计算能力与网络能力。 通用表达式: T = DATA*diff_time_per_data*Fairness + DATA*trans_time_per_data*(1-Locality) 目标: diff_time_per_data*Fairness + trans_time_per_data*(1-Locali