厦门大学数据库实验室 论文阅读成果和创新点 罗道文 2015-03-07
基于Locality-Aware的reduce任务调度 目 录 SAND_JOIN algorithm 基于Locality-Aware的reduce任务调度 SAND_JOIN算法不足之处 SAND_JOIN算法改进
SAND_JOIN algoririthm 思想：在执行reduce-join连接之前，先运行一个job，统计键值的分布情况，即抽样思想，接着利用样本的键值分布情况，对所有数据进行分区。 分为：简单范围分区和虚拟处理器范围分区。 简单的范围分区 思想：Map端采样：每个Mapper随机选取X个样本，有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: key≤3 3<key≤5 5<key≤6 6<key≤9 9<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 解决: build relation: 随机选择一个可选Reducer probe relation: 需发送到每个可选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*y2
SAND_JOIN algoririthm 论文具体实现： 1.将小表S加载到每一台机器，建立哈希表，<key,tuplelist>的形式。 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个Reducer Join 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个分区 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] · 采用虚拟范围分区，数据分配更加均衡 · 处理方式: 轮叫调度 或 当某一节点完成时，将下一剩余任务分配给该节点 · 论文的实验结果表明虚拟范围分区优于简单范围分区
SAND_JOIN algoririthm
Locality-Aware的reduce任务调度 “Hadoop’s framework adopts a pull scheduling strategy rather than a push one” 意思就是说JobTracker并不是把map和reduce任务push给TaskTracer,而是TaskTracker通过请求向JobTracker pull一个map或者reduce任务。 思想：尽量将某个key分配给所有节点中该key最大的节点。 优点：减少数据量的传输。
Locality-Aware的reduce任务调度 TTi:Tasktracker i JT:JobTracker PRi:TTj:表示TTj产生的数据分配给Ri.
Thanks for listening