MapReduce过程详解（非常全）

MapReduce算法执行过程 核心思想：“分而治之”
（1）MapReduce框架使用InputFormat模块做Map前的预处理，比如验证输入的格式是否符合输入定义；然后，将输入的文件切分为逻辑上的多个InputSplit，InputSplit是MapReduce对文件进行处理和运算的实际单位（逻辑概念），每个InputSplit没有对文件进行实际切割，只是记录了要处理的数据的位置和长度。
（2）InputSplit是逻辑切分，所以需要通过RecordReader(RR)根据InputSplit的信息来处理InputSplit中的具体记录，加载数据并转换为合适Map任务读取的键值对，输入给Map任务。
（3）Map任务根据用户自定义的映射规则，输出一系列的作为中间结果。
（4）对Map的输出进行分区、排序、合并、归并等操作，得到形式的中间结果，再交给Reduce，此过程称为Shuffle。（Shuffle详解看下面）
（5）Reduce端以作为输入，执行用户定义的逻辑，输出结果给OutputFormat模块。
（6）OutputFormat会验证输出目录是否已经存在以及输出结果类型是否符合配置文件中的配置类型，如果都满足，就输出Reduce的结果到分布式文件系统中。

此图是MapReduce执行流程：

Shuffle详解

1、在Map端的Shuffle过程
（1）写入缓存
  每一个Map任务会被分配一个缓存，在缓存中积累一定数量的Map输出结果后，再批量写入磁盘，可减少磁盘的I/O影响。
       理解：磁盘包含机械部件，它时通过磁头移动和盘片的转动来寻址定位数据的，每次寻址的开销很大，如果每个Map输出结果都写入磁盘，会引入很多次寻址开销，而一次性批量写入，就只需要一次寻址，连续写入，大大降低了开销。注意：在写入缓存之前，key与value值会被序列化成字节数组
（2）溢写（分区、排序和合并）
   1）分区
   缓存中的数据先分区。缓存中的数据是键值对，通过Partitioner接口对这些键值对进行分区，默认的分区方式：采用hash函数对key进行哈希后再用Reduce任务的数量进行取模，表示为hash（key）mod R，这样就可以把Map的输出结果均匀的分配给Reduce任务区并行处理。也允许用户通过重载Partitioner接口来定义分区方式。
   2）排序（默认）
  每个分区内的键值对，后台线程会根据key，进行内存排序（Sort）
   3）合并（可选）
   如用户事先没有定义Combiner函数，就不用进行合并操作。如果定义了，会执行合并操作，从而减少了需要溢写到磁盘的数据量。
   “合并”是指具有相同key的的value加起来。如： , => 发生在Map端，有别与Reduce。Combiner的输出是Reduce的输入，Combiner不能改变Reduce任务最终的计算结果。
   3）溢写
   -MapReduce缓存的容量默认是100MB，随着Map任务不断增加，很快占满整个缓存，这时，就必须启动溢写（spill）把缓存的内容一次性写入磁盘，并清空缓存。
  默认溢写比例是80%，也就是说，当100MB的缓存被填满80%MB数据时，就启动溢写过程，把写入的80MB写入磁盘，剩余20MB供Map结果继续写入。
   每次溢写操作都会生成一个新的溢写文件，写入溢写文件中的所有键值对都是经过分区和排序的。
（3）文件归并
   Map任务全部结束前，系统会对所有溢写文件进行归并（Merge），生成一个大的溢写文件（键值对都经过分区和排序）
   “归并”指对于具有相同key的键值对归并成一个新的键值对。如 , => >。
   了解：进行归并时，如磁盘生成的溢写文件数量超过参数min.num.spills.for.combine的值时（默认是3，用户可以修改这个值），就可再次运行Combiner，对数据进行合并，减少磁盘的数据量。如果写磁盘中只有一两个溢写文件，就不会运行Combiner，因为执行合并操作本身也有代价。

2、在Reduce端的Shuffle过程
（1）”领取“数据
   Map端的Shuffle结束后，所有Map的输出结果都保存在Map机器的本地磁盘上，文件都是被分区的，不同的分区会被发送到不同的Reduce任务进行并行处理。
  每个Reduce任务会不断地通过RPC向JobTracker询问Map任务是否已经完成；JobTracker检测到一个Map任务完成后，就会通知相关的Reduce任务来"领取"数据；Reduce收到通知，就会从Map任务所在机器把属于自己的分区数据领取到本地磁盘。一般是Reduce任务使用多个线程通过是多个Map机器领回数据。
（2）归并数据
   Map端领取的数据会被存放在Reduce端的缓存中，如果缓存被占满，就会溢写到磁盘。缓存数据来自不同Map机器，会存在很多合并（Combiner）的键值对，当溢写启动时，相同key的键值对会被归并，如用户定义Combiner，则归并后的数据可以执行合并操作，减少写入磁盘数据量。一次溢写，生成一个溢写文件，溢写结束，磁盘上存在多个溢写文件。
   Map端数据都被领回时，多个溢写文件会被归并成一个大文件，归并时会进行排序。如果数据量很少就不需要进行溢写，直接在内存中执行归并操作。
   了解：把磁盘多个溢写文件归并成一个大文件可能需要执行多轮归并操作，每轮归并操作可以归并文件数量是由参数io.sort.factor的值来控制的（默认是10，可以修改）。假设磁盘中生成50个溢写文件，每轮可以归并10个溢写文件，则需要经过5轮归并，得到5个归并后的大文件。
（3）把数据输入给Reduce任务
   Reduce任务会执行Reduce函数中定义的各种映射，输出最终结果，保存在分布式文件系统中（比如GFS或HDFS）
   了解：磁盘多轮归并后得到若干个大文件，不会归并成一个新的大文件，而是直接输入给Reduce任务，可减少磁盘读写开销