MapReduce:Simplified Data Processing on Large Clusters
知识点：
- 容错性，master write periodic checkpoints。如果没有，就重新开始map-reduce任务。
- map,reduce tasks fail, reshedule。
- 任务的粒度：map,reduce task numbers>> 机器的数目
- 如果某台机器速度太慢，但又不是fail状态。解决机制可以是运行这个任务在其它已经完成的机器上
- 如果需要写额外的文件，依赖于application writer来让这side-effect原子和幂等元。
- 有些bac recored让机器crash。可以接受跳过一些坏的记录。每个worker 进程安装了一个signal handler捕捉 segmentation ciolations 和bus errors。
3.1 Execute Overview
- 首先划分文件成每块64MB。在a cluster of machines 上开始这些程序。
- the master的程序的复制是特殊的，其余workers由master分配任务。M个map task和R个reduce task要分配。
- 被分配map任务的worker读入数据，把结果存在内存中
- 周期性，内存中结果写到本地磁盘，划分成R块由划分函数。在本地磁盘这些buffered pairs的位置传回到master，master负责转发这些位置到reduce workers。
- 当master统治reduce worker位置，用remote procedure calls从map workers的磁盘读取缓存数据。当一个reduce work读取所有的中间值，排序中间值，这样所有的相同key被分组到一块。
- reduce worker在排序的中间值中遍历，对于每个遇到的中间键值，传递键值和对应的值到用户的Reduce函数。Reduce函数的输出结果增加到这个reduce partition的最终划分。
- 当所有的map任务和reduce任务都结束，mapreduce结束，把结果返回给用户。
3.2 Master Data structures
对于每个map,reduce任务，存储状态(idle, in-progress, or completed)，鉴别工作机器。
master是道题中间文件区域的位置从map任务传递到reduce任务。因此，对于每个完成的map任务，master存储R个中间文件位置有map任务产生的。
3.3 Fault Tolerance
Work failure
master ping每个worker周期性地。如果在一定时间内没有反应，master认为worker fails。任意由该worker完成的任务都重新设置成idle状态，master负责调度这些任务在其它机器上。相似的，reduce任务失败了也需要重新调度。
完成的任务也需要重新调度因为他们的输出存储在失败机器的本地磁盘上，因此不可以被获取。完成的reduce tasks不需要被重新调度因为结果存储在一个全局的文件系统中。
4.6 Skipping bad records
4.8 status information
可以告诉用户当前执行状况。
4.9 计数器
提供计数功能来统计各种事件的次数。