论文阅读成果和创新点

1、厦门大学数据库实验室论文阅读成果和创新点罗道文2015-03-07SAND_JOIN algorithm基于Locality-Awa re的red u ce任务调度SAND_JOIN算法不足之处SAND_JOIN算法改进思想:在执行reducajoin连接之前f先运行一个job f统计键值的分布情况,即抽样思想，接着利用样本的犍值分布情 况,对所有数据进行分区。分为：简单范围分区和虚拟处理器范围分区。简单的范围分区思想:Map端采样:每个Mapper随机选取X个样本，有n个Mapper. Reduce端统计分布:只需要一 Reducer对样本所有key值统计分析， 构造出分区序列。简单的范围分

2、区(续)若执行的Join连接有N个Reduce,则可以根据步长Fx/N获得一个分区序列。 例如：Sampled,34,56,66,89,10,10,5个Reducer,步长为3, 分区序列为:3,5,6,9Join Partition: key<3 3<key<55<key<66<key<9 9<key1,3,34,5,56,6668,9,910,10倾斜情况：Samples: 1,3,(3) 4, 5,6, 6,(6, 6, 6,© 9, 10, 10, 5个Reducer,步进3 分区序列：3, 5, 6, 6->縫为6的渚两

3、个可选Reducer解决：build relation:随机选择一个可选Reducerprobe relation:需发送到每个可选Reducer适合一个大表一个小表的情况!倾斜键存在大小表的情况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和4Rjoins,对于键6,若 R.6 = S.6可将所有的S.6传输到3和4上，然后R.6可以随机分配到3或4上值为6Reducer4其实就是x*y=x*(y1 +y2)=x*y1 +x*

4、y2论文具体实现：1、将小表S加载到每一台机器，建立哈希表，vkey,tuplelis卜的形式。2当R表某个键值key分配到某个Reducer上时，从哈希表中检索key的 valuefl,即tuplelist,与R表中的元组做Join操作。Reducer3MapperMemoryReducer4Memory虚拟处理器范围分区实际是N个Reducer,但假定分成oTN个分区（a为整数）。 例如Samples: 1,3, 4, 4, 5, 5, 6, 6, 6, 6, 6, 6, 9, 10, 105 11,11,11,15, 16, 5个Reducer Join Partition: 1,3,4

5、,4, 5,5,6,6, 666,6, 9,10,10,11,11,11, 15,16 a二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个Reducer Join Partition: 1,3,3, 4, 5,5, 6,6, 6,6, 6,6, 9,10,10, 11, 11,11, 15,16 采用虚拟范围分区，数据分配更加均衡 处理方式:轮叫调度或当某一节点完成时，将下一剩余任务分配给该节点 论文的实验结果表明虚拟范围分区优于简单范围分区Locality-Aware 的 reduce 任务调度基于位置感知的reduce任务调度“Hadoop's framework adopts a pu/scheduling strategy rather than a push one”意思就是说JobTracker并不是把map和reduce任务push给 TaskTracer,而是 TaskTracker 通过请求JobTracker pull个 map 或 者reduce任务。思想：尽量将某个key分配给所有节点中该key最大的节点。优点：减少数据量的传输。Locality-Aware