1、,论文阅读成果和创新点,厦门大学数据库实验室,罗道文,2015-03-07,SAND_JOIN algorithm,目 录,基于Locality-Aware的reduce任务调度,SAND_JOIN算法不足之处,SAND_JOIN算法改进,SAND_JOIN algoririthm,简单的范围分区,思想：在执行reduce-join连接之前，先运行一个job，统计键值的分布情况，即抽样思想，接着利用样本的键值分布情况，对所有数据进行分区。分为：简单范围分区和虚拟处理器范围分区。,思想：Map端采样：每个Mapper随机选取X个样本，有n个Mapper。 Reduce端统计分布：只需要一个Red
2、ucer对样本所有key值统计分析，构造出分区序列。,SAND_JOIN algoririthm,若执行的Join连接有N个Reduce,则可以根据步长n*x/N获得一个分区序列。例如： Sample:1,3,3,4,5,5,6,6,6,6,8,9,9,10,10,5个Reducer，步长为3， 分区序列为:3,5,6,9 Join Partition: key3 3key5 5key6 6key9 9 键为6的有两个可选Reducer 解决: build relation: 随机选择一个可选Reducer probe relation: 需发送到每个可选Reducer 适合一个大表一个小表的
3、情况！,SAND_JOIN algoririthm,倾斜键存在大小表的情况 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 = S.6 可将所有的S.6传输到3和4上，然后R.6可以随机分配到3或4上,其实就是x*y=x*(y1+y2)=x*y1+x*y2,SAND_JOIN algoririthm,论文具体实现： 1.将小表S加载到每一台机器，建立哈希表，的形式。 2.当R表某个
4、键值key分配到某个Reducer上时，从哈希表中检索key的value值，即tuplelist,与R表中的元组做Join操作。,SAND_JOIN algoririthm,虚拟处理器范围分区,实际是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个分区S
5、amples: 1, 3, 3, 4, 5, 5, 6, 6, 6, 6, 6, 6, 9, 10, 10, 11, 11, 11, 15, 16, 10个ReducerJoin Partition: 1,3,3, 4, 5,5, 6,6, 6,6, 6,6, 9,10,10, 11, 11,11, 15,16 采用虚拟范围分区，数据分配更加均衡 处理方式: 轮叫调度 或 当某一节点完成时，将下一剩余任务分配给该节点 论文的实验结果表明虚拟范围分区优于简单范围分区,SAND_JOIN algoririthm,Locality-Aware的reduce任务调度,思想：尽量将某个key分配给所有节
6、点中该key最大的节点。 优点：减少数据量的传输。,“Hadoops framework adopts a pull scheduling strategy rather than a push one” 意思就是说JobTracker并不是把map和reduce任务push给TaskTracer,而是TaskTracker通过请求向JobTracker pull一个map或者reduce任务。,基于位置感知的reduce任务调度,Locality-Aware的reduce任务调度,TTi:Tasktracker iJT:JobTrackerPRi:TTj:表示TTj产生的数据分配给Ri.,Thanks for listening,
