基于位置感知和负载均衡mapreduce的join算法优化

《基于位置感知和负载均衡mapreduce的join算法优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于位置感知和负载均衡MapReduce的Join算法优化汇报人：黄梓铭厦大数据库实验室2015-3-7目录页CONTENTSPAGEP1.Reduce-sideJoinP2.已有的研究方法P3.我的创新点P4.总结Reduce-sideJoinReduce-sideJoin表A表B以id为key连接Mapreduce的Join过程Ｈａｄｏｏｐ现有的划分方法以组为单位进行划分，具有相同键的所有记录被分配到同一个Ｒｅｄｕｃｅｒ进行处理．这种划分方法没有考虑每个组内包含的记录数目。比如partition函数是通过hash函数来觉决定分区结果。如果是数据均衡情况下，分区效果还是很理想的。但是在数据倾

2、斜的情况下，就会出现一些较大key值被分配到同一个Reducer上照成负载的不均衡。比如下面这个例子。所以我们主要就是要通过设计新的partition函数来替换掉已有的hash函数，已解决负载不均衡的问题。接下来我们看看已有的研究成果。已有研究方法基于动态划分的负载均衡方法论文《一种基于动态划分的MapReduce负载均衡方法》提出一种基于动态划分的方法基于动态划分的负载均衡方法论文《LEENLocalityFairness-AwareKeyPartitioningforMapReduceintheCloud》从图中可以看到样本信息包含５个组，每组的记录数分别为20,18,10,9,3，根据算

3、,法１，我们可以得到Ｒｅｄｕｃｅｒ０分配到的样本组为<０，20>，Ｒｅｄｕｃｅｒ１,分配到的样本组有２个，分别为<1,18>和<4,3>，Ｒｅｄｕｃｅｒ２分配到的样本组为<2,10>和<5,9>．每个Ｒｅｄｕｃｅｒ处理的记录总数分别为２０，２１和１９，负载非常均衡．LEEN算法论文《LEENLocalityFairness-AwareKeyPartitioningforMapReduceintheCloud》该算法是对于每一个key通过一个最优化的方法将其分配到最合适的分块，从而达到reducer的负载均衡。不仅考虑了locality并且解决了数据倾斜（fairness）的问题，即它寻求的是一

4、种(fairness/locality)的最小值LEEN算法论文《LEENLocalityFairness-AwareKeyPartitioningforMapReduceintheCloud》7444%7450%7746%谢谢指导！