MapReduce
使用MapReduce框架只要实现一个Map函数和一个Reduce函数，Map函数实现映射，接受一个key-value并转换为多个键值对；Reduce是一个化简函数，接收一个key和对应的vallue，然后组成一组新的value输出出去。
map(k1, v1) -> list(k2, v2)
reduce(k2, list(v2)) -> list(v3)Map函数的输出结果被MapReduce进行一个混洗操作，将Key相同的value整合到一个列表，传给reduce函数。
将key按序排列，不是必须的，而是为了方便技术实现。要合并相同的key，利用硬盘进行外排序是最简单、没有内存限制的key分组办法。
为了隐藏分布式的存在，需要处理3个问题
- 服务器间协同与容错
- 性能问题：它与GFS都非常容易遇到网络性能瓶颈
- 易用性：用于debug
MapReduce 协同
mapreduce通常与gfs在同一个集群，集群中有一个调度系统scheduler。运行一个MapReduce任务就是将整个任务提交给调度系统，让其分配Map函数和Reduce函数，以及让master在不同硬件运行。
运行流程：
- 找到GFS对应路径，将路径下所有数据进行分片Split，通常每个片大小64MB，也是GFS一个块大小。然后MapReduce在集群上启动多个程序的fork进程
- 这些进程中有一个特殊的master进程，其余都是worker。有M个map任务和R个reduce任务分配给worker处理。master进程复制找到空闲的worker并分配任务。并不是每个任务创建一个新进程，而是给worker分配任务，所以一个worker进程可能顺序执行多个map或reduce任务
- map-worker读取分片，将其变为key-value形式，等Map计算完后生成新的key-value缓冲在内存
- 缓冲的键值对定期写入本地硬盘，按照一个分区函数分为R个不同区域。这些本地文件位置被worker传给master，再由master将数据地址传给reduce-worker
- reduce-worker通过RPC从map-worker的磁盘上抓取数据（map和reduce程序没有直接通信），reduce-worker将中间文件根据key排序，这样相同key的value数据放到一起，也就是shuffle过程
- reduce-worker执行Reduce函数，将结果输出到这个reduce分片的最终输出文件中
- 所有map reduce完成后，master唤醒启动MapReduce的用户程序，执行剩余用户程序
这是一个Master-Slave架构，worker间不直接通信，而是通过master转达。reducer在取数据时也是得到master传递的数据在mapper的地址，直接到数据所在地址去拿，而非reduce通过rpc调用map所在worker获取数据。
Hadoop1.0中调度系统承担了master的角色，即JobTracker对象，负责分配任务和沟通。worker就是TaskTracker，负责执行map和reduce。这时JobTracker成为了单点瓶颈。
Hadoop2.0中将JobTracker拆分成了调度任务的Resource Manager和监控单个MapReduce任务执行的Application Master，架构变的与论文相同
容错 Fault Tolerance
重新运行 + 写Checkpoints
- worker失效：master定期ping每个worker，没有响应则换个节点重新运行任务。
- master失效：当做整个任务失败，需要重新提交任务。一个简单解决方案是，master定时将信息作为一个个Checkpoint写入硬盘
性能优化
为了减少网络传输的数据，将程序运行的位置选择数据附近。GFS知道每个Block的数据在哪台服务器上，将任务分到其上的worker，如果没有则在离他近的、有worker的服务器分配任务。
Reduce与map间也传输数据，使用用户自定义的Combiner函数将map输出结果合并以减小带宽。一台机器上的多个worker进程的结果也可以合并。
