Mapreduce
论文地址: MapReduce: Simplified Data Processing on Large Clusters
Mapreduce分布式编程模型，理解起来比较简单，主要总结一下模型+实现细节
编程模型
将任务划分为Map和Reduce两个阶段由用户实现，每个阶段输入输出key-value对（形象理解可以看论文中的例子）
- Map 输入key-value，经过处理输出新的中间 key-value对，由MapReduce执行程序，将相同中间key聚集发送给某一个reduce执行程序
- Reduce 输入一个中间key和key对应的value列表，reduce执行具体聚集操作后，获得最终的输出key-value
实现
基本执行流程包括
- 将输入文件划分为m份（16-64mb），对应m个map任务。在集群上启动多份应用程序
- 其中一个master程序，将map任务和reduce任务分配给空闲的worker(不同的worker可能是一台机器)
- map任务程序首先执行，读取对应的文件块，将输出中间键值对缓存在内存中
- 每隔一段时间，map worker将缓存中的中间键值对存储到本地磁盘（根据key->reduce的映射进行partition）。这些中间键值对的地址，将传给master worker,供reduce worker远程读取
- reduce worker由master唤醒后，通过RPC读取映射到本reduce worker的中间键值对输出
- 当属于某个reduce worker的中间键值对读取完成后，按照中间键值排序，对不同的key分组处理，也就是所谓的reduce输入key-value list
- 所有reduce程序完成后，结束mapreduce过程
总结一下，就是map->partition->sort->reduce
容错
为map和reduce任务定义了执行状态存储在master结点中，通过状态实现容错，每个任务的状态为
- idle 等待处理
- in-progress 处理中
- completed 处理完成
master定期ping所有执行或者执行过任务的worker，若worker失效，将worker上执行过的所有任务（in-progress或者completed）状态设置为idle，等待分配给其他worker处理。
- 若mapreduce任务执行在类似GFS的文件系统上，则complete类型任务不需要重新执行，因为输出文件不仅仅存储在失效的worker上
- 每当一个map任务重新执行后，需要通知所有的reduce任务该map任务的新执行
性能
- map任务分配任务时遵循“靠近输入文件的原则”，首先考虑分配在包含输入文件的机器上，其次考虑靠近存储文件的机器上（移动计算比移动数据更有效）
- 用一些backup worker，替代拖后腿的worker，提升系统效率下限
- map和reduce任务数量M和R要比机器数量大得多，以更好地负载均衡（每个workerp平均一个任务都分不到，谈何负载均衡?）和恢复错误（没太理解？）
问题思考
如何把map任务的输出分配给R个reduce worker（partition）
原则：相同key必须分配到同一个reduce worker
最简单方式就是使用key的哈希值进行映射
既然有了partition，为什么要combiner?
- 相同key值的key-value对可能很多(例如wordcount)，通过网络传播对带宽压力较大，
- 在map端先进行一部分的reduce操作，合并重复key，也能一定程度减轻reduce的计算压力
直觉上为什么mapreduce能解决分布式计算问题？
从程序角度看，不管的单机还是分布式，其本质都是程序读取输入->程序计算->程序输出结果，我要实现分布式程序，无非要实现 分布计算 = 单机计算
- 程序输入： 分布式文件存储在不同机器上，自然而然能够想到多个map程序读取文件的操作
- 程序计算：难点在于分布式读入文件，我如何实现等价于单机计算的效果？我觉得这就reduce设计巧妙地地方，文件的分块不等于计算的逻辑分块，通过map—>reduce程序的计算，实际上将文件的分块映射到计算的逻辑分块
- 程序输出： reduce输出实际逻辑子问题的输出->实际问题的输出（这一点我还没想明白，类似于归并排序 reudce制作到了归没有做并）
以wordcount为例，讲一下我的理解
- 文件分块：整个文本文件->子文本文件块 （问题数据规模上分布）
- 计算逻辑分块：统计每个不同字的字数->单独统计每个字的字数（问题逻辑规模上分布）
map解决每个文本文件内字数的统计，reduce解决每个字字数统计
总结
mapreduce只看理论理解还是太表面，还是需要写代码实战，学到了继续深化吧