Presentation is loading. Please wait.

Presentation is loading. Please wait.

基于位置感知和负载均衡 MapReduce的Join算法优化 汇报人:黄梓铭 厦大数据库实验室 2015-3-7.

Similar presentations


Presentation on theme: "基于位置感知和负载均衡 MapReduce的Join算法优化 汇报人:黄梓铭 厦大数据库实验室 2015-3-7."— Presentation transcript:

1 基于位置感知和负载均衡 MapReduce的Join算法优化 汇报人:黄梓铭 厦大数据库实验室

2 目录页 CONTENTS PAGE P1.Reduce-side Join P2.已有的研究方法 P3.我的创新点 P4.总结

3 Reduce-side Join

4 Reduce-side Join 以id为key连接 表A 表B

5 Mapreduce的Join过程

6 所以我们主要就是要通过设计新的partition函数来替换掉已有的hash函数,已解决负载不均衡的问题。接下来我们看看已有的研究成果。
Hadoop现有的划分方法以组为单位进行划分,具有相同键的所有记录被分配到同一个Reducer进行处理.这种划分方法没有考虑每个组内包含的记录数目。比如partition函数是通过hash函数来觉决定分区结果。如果是数据均衡情况下,分区效果还是很理想的。但是在数据倾斜的情况下,就会出现一些较大key值被分配到同一个Reducer上照成负载的不均衡。比如下面这个例子。 所以我们主要就是要通过设计新的partition函数来替换掉已有的hash函数,已解决负载不均衡的问题。接下来我们看看已有的研究成果。

7 已有研究方法

8 基于动态划分的负载均衡方法 论文《一种基于动态划分的MapReduce负载均衡方法》提出一种基于动态划分的方法

9 基于动态划分的负载均衡方法 从图中可以看到样本信息包含5个组,每组的记录数分别为20,18,10,9,3,根据算,法1,我们可以得到Reducer0分配到的样本组为<0,20>,Reducer1,分配到的样本组有2个,分别为<1,18>和<4,3>,Reducer2分配到的样本组为<2,10>和<5,9>.每个Reducer处理的记录总数分别为20,21和19,负载非常均衡. 论文《LEEN LocalityFairness- Aware Key Partitioning for MapReduce in the Cloud》

10 LEEN算法 论文《LEEN LocalityFairness- Aware Key Partitioning for MapReduce in the Cloud 》 该算法是对于每一个key通过一个最优化的方法将其分配到最合适的分块,从而达到reducer的负载均衡。不仅考虑了locality并且解决了数据倾斜(fairness)的问题,即它寻求的是一种(fairness/locality)的最小值

11 LEEN算法 论文《LEEN LocalityFairness- Aware Key Partitioning for MapReduce in the Cloud 》 % % %

12 谢谢指导!


Download ppt "基于位置感知和负载均衡 MapReduce的Join算法优化 汇报人:黄梓铭 厦大数据库实验室 2015-3-7."

Similar presentations


Ads by Google