6.824Lecture1-MapReduce

Posted on Edited on In ,

Backgorund

  • big data
  • lots of kv data stuctures, like inverted index

Method

Abstract view

  • split files from GFS to disks
  • master分配worker执行map任务，生成k,v值，存入disk，map回传disk地址给master
  • master传递地址给reduce worker，reduce worker使用RPC读disk数据
  • sort by key, 并将所有values聚合
  • reduce
  • master返回reduce结果给GFS

Fault tolerance

  • fail -> rerun: worker rerun不会产生其他问题
  • worker fault: Master 周期性的 ping 每个 Worker，如果指定时间内没回应就是挂了。将这个 Worker 标记为失效，分配给这个失效 Worker 的任务将被重新分配给其他 Worker；
  • master fault: 中止整个 MapReduce 运算，重新执行。

Performance

  • bandwidth: 尽量保持worker和其执行的文件在同一台机器上，会相近的机器
  • slow workers: 吊起执行快的作为backup worker，取最先执行完的worker

Cons

  • 实时性
  • 复杂需求时需要大量相互依赖的mr逻辑 -》难开发，难调试

Refs

作为一种范式，而非产品？