论文阅读成果和创新点

1、论文阅读成果和创新点论文阅读成果和创新点厦门大学数据库实验室厦门大学数据库实验室罗道文罗道文2015-03-07 SAND_JOIN algorithm目目 录录 基于基于Locality-Aware的的reduce任务调度任务调度 SAND_JOIN算法算法不足之处不足之处 SAND_JOIN算法改进算法改进SAND_JOIN algoririthm简单的范围分区思想：在执行reduce-join连接之前，先运行一个job，统计键值的分布情况，即抽样思想，接着利用样本的键值分布情况，对所有数据进行分区。分为：简单范围分区和虚拟处理器范围分区。思想：Map端采样：每个Mapper随机选取X个样

2、本，有n个Mapper。 Reduce端统计分布：只需要一个Reducer对样本所有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 relat

3、ion: 需发送到每个可选Reducer 适合一个大表一个小表的情况！ 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*y2SAND_JOIN algoririthm论文具体实现： 1.将小表

4、S加载到每一台机器，建立哈希表，的形式。 2.当R表某个键值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,1

5、1, 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个ReducerJoin Partition: 1,3,3, 4, 5,5, 6,6, 6,6, 6,6, 9,10,10, 11, 11,11, 15,16 采用虚拟范围分区，数据分配更加均衡 处理方式: 轮叫调度 或 当某一节点完成时，将下一剩余任务分配给该节点 论文的实验结果表明虚拟范围分区优于简单范围分区SAND_JOIN algoririthmLocality-Aware的的reduce任务调度任务调度思想：尽量将某个key分配给所有节点中该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-Awa