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

《数据倾斜情况下基于MapReduce的Join算法优化.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、数据倾斜情况下基于MapReduce的Join算法优化报告人：蔡珉星厦大数据库实验室2014-08-16遇到的问题目录优化思路-改进PartitionPartition在两表连接中的改进LEEN算法Part1优化思路-改进PartitionMapReduce中的Partition：在Map端输出时，需要对key进行分区，来决定输出数据传输到哪个reducer上进行处理。默认的partition是通过哈希操作来决定分配到哪个reducer。哈希Partition的局限哈希在数据均衡的情况下，可以很好的将

2、数据平均到各个Reducer上，但在数据倾斜情况下，会导致某几个Key的值大量集聚在单个Reducer上。Partition哈希实际上是一种针对键的分组均衡分配，不能保证数据量均衡分配Reduce-sideJoin：Map-sideJoin(复制连接、半连接)对数据集要求较高，一般情况下Join操作是采用Reduce-sideJoin-重分区连接：将键相同的数据分到同一个reducer，再进行Join。优化重分区连接:区分大小数据集，将小数据集读取到内存中，再用小数据集来遍历大数据集。优化重分区连接的

3、精髓就在于Reduce端用小数据集遍历大数据集，这部分已经没有什么改进空间。哪里还可以再改进？-->Partition:优化重分区连接采用Hashparition不能保证数据量均衡分配。Join算法优化思路优化重分区连接采用Hashparition，不能保证数据量均衡分配Part2Partition在两表连接中的改进两表连接中的改进数据实例：3个Data节点每个节点输出75个键值81->36%103->46%41->18%即便可以采用优化重分区，但在Partition时已经造成了数据分配倾斜！两表连接

4、中的改进均衡Partition论文《LEENLocalityFairness-AwareKeyPartitioningforMapReduceintheCloud》中的算法LEEN给出的Partition：74->33%74->33%77->34%获知键值的分布两表连接中的改进获知键值的分布–采样在执行Reducer-sideJoin之前，先运行一个Job，统计数据分布情况。采样开销应尽可能少，同时保证准确性。Partition方式:简单范围分区Map端采样：每个Mapper随机取x个Sample，有

5、n个Mapper。Reduce端统计分布：只需要一个Reducer，此时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]JoinPartition:key≤33

6、6,6,6,6][8,9,9][10,10]倾斜情况: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解决:buildrelation:随机选择一个可选Reducerproberelation:需发送到每个可选ReducerRjoinS->R:probe,S:build?两表连接中的改进倾斜键存在大小表的情况Samples:[1,3,3,4,5,5,6,6,6,6,6,6,9,

7、10,10],5个Reducer，步进3分区序列:[3,5,6,6]->键为6的有两个可选Reducer3和4RjoinS，对于键6，若R.6<

8、ition:[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个ReducerJoinPartition:[1,3,3],[4],[5,5],[6,6],[6,6],[6,6],[9,10,10],[11],[11,11],[15,16]采用虚拟