处理框架

复习：GFS里几个重要的观点

• 数据存储于成千上百的服务器中，大数据块减少元数据开销
• 使用商用硬件->失败是很正常的（失败是不可避免的，所以买便宜的硬件）
• 没有复杂的一致性模型（单写者，数据只能添加，避免互相等待）

数据并行化（DLP）
若干硬盘上的大量数据，可以被并行化的操作（比如搜索文档）
Embarassingly Parallel
例子 词频统计
dog dog is is dog dog is cat is cat is dog it it is .....
different splits
GFS已经解决的问题：数据分块存储 并行？
写入这个计数会有问题
问题？
共享的状态

• 吞吐量（多个进程同时改变）
• 同步（同时修改需要锁）
  小粒度的通信让元数据管理变得更复杂
  失败的机器
  共享的状态太大
  如果最终结果失败，重算？
  其他问题：易用性、通用性 应该用什么样的抽象层次

Map Reduce Processing
数据并行的分治策略

• Map 将数据分割为shards或者splits，将它们分配给工作节点，工作节点来计算子问题的解。
• 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 (String input_key,String input_value):
    //input_key:document name
    //input_value document contents
    localCount = CountLocally(input_value)
    for each count:
        Emit(word,count); //Produce count of words

reduce(String word, Iterator intermediate_values):
    //word the word(in the intermediate key;
    //intermediate_values: a list of counts;
    int result = 0;
    for each v in intermediate_values:
        result += v;
    Emit(word,result);

map 结果中的键和值与reduce输入的键和值类型相同

Map Reduce 执行过程

执行步骤：

• 将输入数据分割成M块，在每块上分布式地调用map() 通常每个数据块为64MB 或128MB，取决于GFS数据块大小。
• 输入数据由不同的服务器并行处理
• 通过将中间结果分割成R块，对每块分布式调用Reduce()

选择Map和Reduce的分块数量
M和R的数量由用户指定

• M >> # servers, R > # servers
• 很大的M值有助于负载均衡，以及快速恢复

• 每个Reduce()调用，对应一个单独的输出文件，所以R值不应该太大
  洗牌过程（通过key来分组）
  Map1 emit（key，value） shard_id = partition(key)
  Reduce 找到对应shard_id的数据 -> shuffle
  Merge sort key words 得到 key, iterator()

  
  image.png

image.png

Map Reduce 性能优化与容错

Map Reduce冗余执行

• 整个任务完成时间由最慢的节点决定的
• 解决方案：在接近结束时，生成冗余任务：谁先完成，谁获胜；也叫做投机（speculative）执行
• 影响：极大地缩短任务完成时间。资源增加3%，大型任务速度提高30%

MapReduce 故障处理

• 计算节点故障 控制节点通过周期性的心跳来检测故障；重新执行
• 主节点故障 可以解决，单目前没有解决（控制节点故障可能性很低）
• 健壮性 MapReduce论文报告：曾经丢失1800个节点中的1600个，但是任务仍然正确完成。

Map Reduce理解要点

• 同样的细粒度操作（Map&Reduce）重复作用于大数据
• 操作必须是确定性的
• 操作必须是幂等的、没有副作用的
• 只有shuffle过程中才有通信（其实读取hdfs过程中也涉及到了通信）
• 操作（Map&Reduce）的输出存储于硬盘上

MapReduce用来做什么？

• Google
  • 为Google Search建立索引
  • 为Google News进行文章聚类
  • 统计性的机器翻译
• Yahoo：
  • 为Yahoo Search建立索引
  • 为Yahoo Mail进行垃圾检测
• Facebook
  • 数据挖掘
  • 广告优化
  • 垃圾检测