《厦门大学数据库实验室-蔡珉星-数据倾斜情况下基于》由会员分享,可在线阅读,更多相关《厦门大学数据库实验室-蔡珉星-数据倾斜情况下基于(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 Cloud中的算法LEEN给
4、出的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 获得一个分区序列。例如:
5、 Samples: 1, 3, 3, 4, 5, 5, 6, 6, 6, 6, 8, 9, 9, 10, 10, 5个Reducer,步进3分区序列: 3, 5, 6, 9Join Partition: key3 3 键为6的有两个可选Reducer解决: build relation: 随机选择一个可选Reducerprobe 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
6、个Reducer,步进3分区序列: 3, 5, 6, 6 - 键为6的有两个可选Reducer 3 和 4R join S,对于键6,若 R.6 29%30 - 40%17 - 22%,Partition后,本地数据所占的比例,81 - 36%103 - 46%41 - 18%,网络共需要传输的数据量: Total Map output (1 -Locality)81*(1-29%) + 103*(1-40%) + 41*(1-22%) = 151 151/225 = 67%,LEEN算法,LEEN:异步map和reduce模式Hadoop中的计算和数据传输是会重叠的(如一个节点上运行多个ma
7、p任务,一个map任务结束后,就会进行数据传输)。LEEN为了获知所有中间数值的分布情况,采用了异步map和reduce模式(先全部执行完map再执行reduce)。map阶段对每个中间键的结果进行缓存,而不是直接发送到相应的reducer。这样当map结束时,就有了所有的键分布信息(出现次数等),这些键将根据LEEN算法来进行分配(到reducer)。,LEEN算法,LEEN算法:平衡Locality和Fairness Fairness(0): 各个reduce分配的数据量的差异,越小越好; Locality(1): 各个reduce分配的数据中,来自本地节点的数据,越大越好;LEEN算法
8、- 启发式算法,目标:(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-Locality) 最小,LEEN算法,实验结果,总结,总结: 优化的出发点是实现Reduce的负载均衡; 优化的体现是Job完成的总时间; 优化也可以从Hadoop的流程上考虑; Partition Copy Phase,22,遇到的问题,Thanks.,