第四讲处理框架
数据并行的分治策略(MapReduce Processing)
• 映射（Map）:
– 将数据分割为“碎片”或者“裂片”，将它们分配给工作节点，工作节点来计算子问题的解。
• 化简（Reduce）:
– 收集，合并子问题的解
• 易于使用
– 开发者集中于问题
– MapReduce系统解决细节
Map Reduce的基本编程模型
• Map:
– map(in_key,in_value)
                ->list(out_key,intermediate value)
• 处理输入的键值对
• 生成中间结果集
• Reduce:
– reduce(out_key,list(intermediate_value))
               ->list(out_value)
• 对于某个键，合并它所有的值
• 生成合并后的结果值集合
执行步骤
• Map函数，通过将输入数据分割成M块，来被分布式地调用
– 通常每个数据块16MB或者64MB
– 取决于GFS的数据块大小
• 输入数据由不同的服务器来并行的处理
• Reduce函数，通过将中间结果分割成R块，来被分布式地调用
• 用户挑选的数字应满足 M >> # servers, R > # servers
– 很大的M值能够有助于负载均衡，以及从失败中恢复
– 每R个调用，对应一个输出文件，所以R值不应该太大

MapReduc故障处理
• 工作节点故障：
– 控制节点通过周期性的心跳来检测故障
– 重新执行
• 控制节点故障：
– 可以解决，但是目前还没有解决（控制节点故障可能性很低）
• 健壮性：曾经丢失1800个节点中的1600个，但是任务仍然完成了。
MapReduce优点
• 分布式过程完全透明
– 没有一行的分布式编程（既方便，又保证正确性）
• 自动的容错性
– 操作的确定性保证了故障的任务可以在其他地方再次运行
– 保存的中间结果保证了只需要重新运行故障的reduce节点
• 自动的规模缩放
– 由于操作是没有副作用的，所以它们可以动态地被分发到任何数量的机器
• 自动的负载均衡
– 及时移动任务，投机性地执行慢的任务（称为stragglers）
MapReduce缺点
1. 极其严格的数据流
其他流持续的加入
2. 常见的操作必须手写代码
•比如 Join, filter, projection, aggregates, sorting, distinct
3. 语义隐藏在map-reduce函数中
• 维护，扩展，优化都比较困难

优化: 连接两个偏态分布
• 如果很多值都有同样的键的话，就会有问题
• Skew join对数据进行采样，来找到高频值
• 在reducer中进一步的分割他们
碎片复制连接（Fragment-Replicate Join）
• 对称哈希连接，对输入数据重分割
• 如果size(data set 1) >> size(data set 2)
– 复制数据集2到数据集1的分片中
• 转化为map-only的任务
– 打开数据集2为“slide file”
其他类似框架
• Sawzall
– 基于MapReduce的数据处理语言
– 在聚合之后，严格的过滤结构
• Hive
– 基于MapReduce的类似SQL的语言
• DryadLINQ
– 基于Dryad的类似SQL的语言