《数据倾斜情况下基于MapReduce的Join算法优化.ppt》由会员分享，可在线阅读，更多相关《数据倾斜情况下基于MapReduce的Join算法优化.ppt（22页珍藏版）》请在三一办公上搜索。
1、数据倾斜情况下基于MapReduce的Join算法优化,报告人：蔡珉星厦大数据库实验室2014-08-16,遇到的问题,目录,优化思路-改进PartitionPartition在两表连接中的改进LEEN算法,Part 1,优化思路-改进Partition,MapReduce中的Partition：在Map端输出时，需要对key进行分区，来决定输出数据传输到哪个reducer上进行处理。默认的partition是通过哈希操作来决定分配到哪个reducer。哈希Partition的局限 哈希在数据均衡的情况下，可以很好的将数据平均到各个Reducer上，但在数据倾斜情况下，会导致某几个Key的值大
2、量集聚在单个Reducer上。,Partition,哈希实际上是一种针对键的分组均衡分配，不能保证数据量均衡分配,Reduce-side Join：Map-side Join(复制连接、半连接)对数据集要求较高，一般情况下Join操作是采用Reduce-side Join-重分区连接：将键相同的数据分到同一个reducer，再进行Join。优化重分区连接:区分大小数据集，将小数据集读取到内存中，再用小数据集来遍历大数据集。优化重分区连接的精髓就在于Reduce端用小数据集遍历大数据集，这部分已经没有什么改进空间。哪里还可以再改进？-Partition:优化重分区连接采用Hash paritio
3、n不能保证数据量均衡分配。,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%7
4、4-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,
5、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,6,6,6,6,9,10,10,5个Reducer，步进3 分区序列:3,5,6,6-键为6的有两个可选Reducer 3 和 4 R join S，对于键6，若 R.
6、6 S.6 可将所有的R.6传输到3和4上，然后S.6可以随机分配到3或4上,1000个A,两表连接中的改进,进一步的改进：虚拟范围分区 实际是N个Reducer，但假定分成*N 个分区(为整数)。例如Samples:1,3,4,4,5,5,6,6,6,6,6,6,9,10,10,11,11,11,15,16,5个ReducerJoin Partition:1,3,4,4,5,5,6,6,6,6,6,6,9,10,10,11,11,11,15,16=2，则分成2*5=10个分区Samples:1,3,3,4,5,5,6,6,6,6,6,6,9,10,10,11,11,11,15,16,10个R
7、educerJoin Partition:1,3,3,4,5,5,6,6,6,6,6,6,9,10,10,11,11,11,15,16采用虚拟范围分区，数据分配更加均衡处理方式:轮叫调度 或 当某一节点完成时，将下一剩余任务分配给该节点论文的实验结果表明虚拟范围分区优于简单范围分区,还有什么地方可以再优化？,Reduce阶段须在数据传输、合并完成后才能开始能否减少网络传输？,Part 2,LEEN算法,LEEN算法,针对Copy Phase的一些考虑,map和reduce任务可在同一个节点上，copy阶段，节点fetch的数据包括自身节点上的数据（不需要网络传输）和其他节点上的数据（需要网络传
8、输）。若为了降低网络传输，应尽量fetch自身节点的数据。但以自身数据量作为Partition依据，可能导致reduce端数据分配不均，如何平衡？,LEEN算法,数据实例：3个Data节点每个节点输出75个键值,22-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%)=151151/225=67%,LEEN算法,LEEN：异步map和reduce模式 Hadoop中的计算和数据传输是会重
9、叠的（如一个节点上运行多个map任务，一个map任务结束后，就会进行数据传输）。LEEN为了获知所有中间数值的分布情况，采用了异步map和reduce模式（先全部执行完map再执行reduce）。map阶段对每个中间键的结果进行缓存，而不是直接发送到相应的reducer。这样当map结束时，就有了所有的键分布信息（出现次数等），这些键将根据LEEN算法来进行分配（到reducer）。,LEEN算法,LEEN算法：平衡Locality和FairnessFairness(0):各个reduce分配的数据量的差异，越小越好；Locality(1):各个reduce分配的数据中，来自本地节点的数据，越
10、大越好；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-Locality)最小,LEEN算法,实验结果,总结,总结：优化的出发点是实现Reduce的负载均衡；优化的体现是Job完成的总时间；优化也可以从Hadoop的流程上考虑；PartitionCopy Phase,22,遇到的问题,Thanks.,
