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

论文阅读成果和创新点
厦门大学数据库实验室
罗道文
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端统计分布:只需要一个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,若 ==
,
其实就是x*y=x*(y1+y2)=x*y1+x*y2
SAND_JOIN algoririthm
论文具体实现:
,建立哈希表,<key,tuplelist>的形式。
,从哈希表中检索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任务调度
思想:尽量将某个key分配给所有节点中该key最大的节点。
优点:减少数据量的传输。
“Hadoop’s framework adopts a pull scheduling strategy rather than a push one”
意思就是说JobTracker并不是把map和reduce任务push给TaskTracer,而是TaskTracker通过请求向JobTracker pull一个map或者reduce任务。
基于位置感知的red