Mapreduce实现原理总结

一.首先，我们从客户端，JobTracker，TaskTracker这个层面来分析整个mapreduce过程

①.首先在客户端启动一个作业。

②.客户端向JobTracker申请一个作业号，这个作业号默认是以当前的时间组成的，可以通过mapreduce.job.name（2.0以后使用的参数）或mapred.job.name（1.0使用的参数）参数来指定作业的名字。

③.框架会将本次要执行的作业资源文件从本地复制到HDFS上面，复制的资源文件主要包括MapReduce打包的Jar文件（默认是10份），配置文件和客户端计算所得的输入划分信息。这些文件会被存放在一个名为JobID的文件夹下面。

④.JobTracker接收到作业以后，将其放入到一个作业队列中去，等待作业调度线程对其调用，当作业调度线程根据算法调度到该作业的时候（默认是FIFO机制），会根据划分信息为每一个划分信息创建一个map任务，然后创建的map任务分配给TaskTracker去执行；这里将map分配给TaskTracker的规则是：将map分配给当前任务要处理的数据存放位置对应的那个TaskTracker节点上去执行（这个就是数据本地化，移动任务执行位置，而不是移动数据位置，从而提高效率）

⑤.TaskTracker和JobTracker之间通过心跳机制保持联系，即TaskTracker每隔一段时间会向JobTracker汇报自己的运行情况；当最后一个任务完成时，JobTracker会将这个任务标记为“成功”，JobClient查询的时候会向相关的执行结果告知用户。

二.从shuffle和排序的角度来分析一下整个TaskTracker执行流程

   i>Map端执行流程

       ①.每个输入分片通过一个map任务来处理，map的输出暂时存入一个环形缓冲区中（该缓冲区默认大小为100M，阈值为80%），当缓冲区要溢出的时候，在本地系统中创建一个溢出文件，将溢出内容写入到该溢出文件中。

       ②.在写入本地磁盘之前，后台线程首先根据reduce任务的数目将数据划分成相同数目的分区，然后将要写入到本地磁盘的数据hash的方式写入一个分区中，然后对每个分区中的数据进行排序，如果有Combiner，则对排序后的数据做Combiner操作。

       ③.将分区中的数据拷贝到相应的reduce任务中。至此，map阶段完成

ii>Reduce端执行流程

        ①.Reduce端接收数据，如果数据很小的话，直接存入缓冲区，当缓冲区数据超过一定比例以后，就进行数据合并操作并溢写到磁盘。

        ②.随着溢写文件不断增多，后台线程将溢写的文件在进行一次合并，变为一个更大的文件。

        ③.最后一次将合并的结果输出到reduce函数中，reduce函数将相关处理结果写入HDFS中。