6.824: Distributed Systems

Posted by chinaljr on August 1, 2016

Programming Model

  • map
    • 将输入变成一堆 KV 对
    • 然后按照 Key 分组
    • pass them to the reduce function
  • Reduce
    • 把这些合并
    • 每个reduce function 产生0 or 1 个 结果
  • 想法简单,具体系统的实现需要根据环境的不同
  word1 word2 wordn
file1 x11 x12 x1n
file2 x21 x22 x2n
filem xm1 xm2 xmn
SUM sum1 sum2 sumn
  • map : 一行一行填表
  • reduce :合并每一行,生成最后一行

Implementation

  • master 保存每个 map-task 和 reduce-task 的状态
  • master 是 map-tasks 和 reduce-tasks 的桥梁

Fault Tolerance

  • Worker Failure
    • Master 不断询问 ,出错然后标记
    • 当前worker完成的内容需要重新算
      • map task 重算,因为outpur 位于 问题节点
      • reduce task 不用,因为output位于全局存储位置
  • Master Failure
    • 周期的 checkpoints
  • Semantics in the presense of Failure
    • 原子性

Locality

布局配置,影响网络资源的使用

Task Granularity

  • M 个 Map task
  • R 个 Reduce task
  • M 和 R 都远大于 worker 的数目
  • O(M+R) 的调度
  • O(M * R)的状态

Backup Tasks

  • straggler :运行的瓶颈,拖后腿
  • 速度过慢,然后新开一个新的backup-task , 两个其中之一结束就算结束