以下为看 Google MapReduce 论文的笔记，后续有实践和看其他资料会慢慢补全。
0. 介绍
因为有大量的任务需要分布式运行，为了避免编写分布式程序需要在程序中引入大量的任务分发和容错处理的代码，MapReduce 诞生了。计算、容错、数据分布、负载均衡等复杂的细节都被封装在一个库中。
执行过程
- 分割文件给 Worker，在每个 Worker 上复制一个文件
- 分配到 Map 任务的节点执行 Map 生成 key/value pair
- Map 执行分区函数分成 R 个区域写入本地磁盘，通知 Master 写的位置
- Reduce 节点通过 Master 给的信息读取 Map 节点上的文件，然后对内容进行排序，拿出相同 key 的 pair 放入 Reduce 函数中，Reduce 函数输出被追加到所属分区的输出文件中
1. 容错处理
worker 故障
map Worker 则重新执行或者重新调度到新的节点并且通知其他全部，reduce worker 因为结果直接被写入分区中，所以直接重新运行或者分发到新的节点，甚至不用处理（如果已经写入完成了）。
master 容错
master 每隔一段时间就会把快照写入磁盘，因为只有一个 Master，失效了就要终止运算重启 master 从检查点恢复，重新运行程序。
2. 加速措施
任务数量
map 拆分成了 M 个片段、把 reduce 拆分成 R 个片段执行。理想情况下，M 和 R 应当比集群中 worker 的机器数量要多得多。但是 master 需要执行 O(M + R) 次调度，所以 MR 也不能过大。
根据文件每块是 64 M，因为 Master 调度的时候会考虑文件保存的位置，所以我们更倾向于按照文件大小来定制 Map 的数量，这样能节省一些网络传输。
落伍者处理
有时候某个节点出了问题会导致整个任务的调度出问题，比如说可能 Master 在这个节点上又调度了其他任务，或者机器出现故障。
当一个任务处于将要完成的状态的时候（比如说剩下一个 Map 操作），Master 会调度其他的机器来执行这个 Map 任务作为备份任务，无论是正在执行的机器完成了还是备份机器完成了，这个任务都能完成。
一般这样只会多消耗百分之几的资源，但是减少时间效果显著。
3. 扩展函数，加速运行 trick
分区函数
默认的分区函数是 hash，有时候比如说 url 想要把同一域名下的 url 放在同一个分区就可以自定义分区函数。
Combiner 函数
有时候会出现类似于数据倾斜这样的问题，比如说统计词频中，the 占了一大部分，这一大部分被分发到一个 reduce 里，会导致速度降低，用 Combiner 函数在 Map 处理的时候就统计好词频，
统计出结果为（the, 1000）而不是 1000 条 （the, 1），避免向本地写入和传输很大的文件。
4. 总结
约束编程模式使得并行和分布式计算非常容易， 也易于构造容错的计算环境；其次，网络带宽是稀有资源。大量的系统优化是针对减少网络传输量为目的的： 本地优化策略使大量的数据从本地磁盘读取，中间文件写入本地磁盘、并且只写一份中间文件也节约了网络 带宽；第三，多次执行相同的任务可以减少性能缓慢的机器带来的负面影响（alex 注：即硬件配置的不平衡）， 同时解决了由于机器失效导致的数据丢失问题。
本文由 鸡米 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Nov 22,2019