论文阅读成果和创新点.ppt

论文阅读成果和创新点厦门大学数据库实验室罗道文2015-03-07SAND_JOINalgorithm目录基于Locality-Aware的reduce任务调度SAND_JOIN算法不足之处SAND_JOIN算法改进SAND_JOINalgoririthm简单的范围分区思想:在执行reduce-join连接之前,先运行一个job,统计键值的分布情况,即抽样思想,接着利用样本的键值分布情况,对所有数据进行分区。分为:简单范围分区和虚拟处理器范围分区。思想:Map端采样:每个Mapper随机选取X个样本,有n个Mapper。Reduce端统计分布:只需要一个Reducer对样本所有key值统计分析,构造出分区序列。SAND_JOINalgoririthm若执行的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]JoinPartition:key≤33<key≤55<key≤66<key≤99<key[1,3,3][4,5,5][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:需发送到每个可选Reducer适合一个大表一个小表的情况!SAND_JOINalgoririthm倾斜键存在大小表的情况Samples:[1,3,3,4,5,5,6,6,6,6,6,6,9,10,10],5个Reducer,步进3分区序列:[3,5,6,6]->键为6的有两个可选Reducer3和4RjoinS,对于键6,==,*y=x*(y1+y2)=x*y1+x*y2SAND_JOINalgoririthm论文具体实现:,建立哈希表,<key,tuplelist>的形式。,从哈希表中检索key的value值,即tuplelist,与R表中的元组做Join操作。SAND_JOINalgoririthm虚拟处理器范围分区实际是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个ReducerJoinPartition:[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]·采用虚拟范围分区,数据分配更加均衡·处理方式:轮叫调度或当某一节点完成时,将下一剩余任务分配给该节点·论文的实验结果表明虚拟范围分区优于简单范围分区SAND_JOINalgoririthmLocality-Aware的reduce任务调度思想:尽量将某个key分配给所有节点中该key最大的节点。优点:减少数据量的传输。“Hadoop’sframeworkadoptsapullschedulingstrategyratherthanapushone”意思就是说JobTracker并不是把map和reduce任务push给TaskTracer,而是TaskTracker通过请求向JobTrackerpull一个map或者reduce任务。基于位置感知的reduce任务调度Locality-Aware的reduce任务调度TTi:TasktrackeriJT:JobTrackerPRi:TTj:表示TTj产生的数据分配给Ri.