mapreduce算法的原理(阐述MapReduce算法执行流程)

执行MapReduce任务的机器有两个角色：JobTracker和TaskTracker。

JobTracker：管理和调度MapReduce的Job。

TaskTracker：执行MapReduce的Job。

在Hadoop中，每个MapReduce任务都被初始化为一个Job。

每个Job又可以分为两个阶段：Map阶段和Reduce阶段。这两个阶段分别用两个函数来表示，即Map函数和Reduce函数。

Map函数接收一个＜key,value＞形式的输入，然后产生同样为＜key,value＞形式的中间输出，Hadoop会负责将所有具有相同中间key值的value集合到一起传递给Reduce函数。

Reduce函数接收一个如＜key,(list of values)＞形式的输入，然后对这个value集合进行处理并输出结果，Reduce的输出也是＜key, value＞形式的。

InputSplit把输入数据传送给每个单独的Map, InputSplit存储的并非数据本身，而是一个分片长度和一个记录数据位置的数组。

InputFormat()方法是用来生成可供Map处理的＜key, value＞对的。当数据传送给Map时，Map会将输入分片传送到InputFormat()上，InputFormat()则调用getRecordReader()方法生成RecordReader，RecordReader再通过creatKey()、creatValue()方法创建可供Map处理的＜key, value＞对，即＜k1，v1＞。

InputFormat的默认值是TextInputFormat，它针对文本文件，按行将文本切割成InputSplit。在TextInputFormat中，每个文件的每行数据都会生成一条记录，每条记录表示成＜key, value＞形式：

key值是每个数据的记录在数据分片中的字节偏移量，数据类型是LongWritable；value值是每行的内容，数据类型是Text。 3、OutputFormat（）

默认的输出格式是TextOutputFormat，将每条记录以一行的形式存入文本文件。它的键和值可以是任意形式的，因为程序内部会调用toString()方法将键和值转换为String类型再输出。

Map()函数继承自MapReducebase，并且实现了Mapper接口，它有4种形式的参数，分别用来指定Map()的输入key值类型、输入value值类型、输出key值类型和输出value值类型。

本例中使用的是TextInputFormat 【InputFormat()用来生成可供Map处理的＜key, value＞对，InputFormat()默认值是TextInputFormat()【不需要我们自己设置，系统默认使用这个】】，它的输出key值是LongWritable类型，输出value值是Text类型，所以Map()的输入类型即为＜LongWritable,Text＞。

实现此接口类还需要实现Map()方法，Map()方法会负责具体对输入进行操作，在本例中，Map()方法对输入的行以空格为单位进行切分，然后使用OutputCollect收集输出的＜word，1＞，即＜k2，v2＞。

Reduce（）函数也继承自MapReducebase，需要实现Reducer接口。

Reduce（）函数以Map()的输出作为输入，因此Reduce（）的输入类型是＜Text,IneWritable＞。

Reduce（）的输出是单词和它的数目，因此，它的输出类型是＜Text,IntWritable＞。

Reduce（）函数也要实现Reduce（）方法，在此方法中，Reduce（）函数将输入的key值作为输出的key值，然后将获得的多个value值加起来，作为输出的value值。

负责控制及调度MapReduce的Job的是JobTracker，负责运行MapReduce的Job的是TaskTracker。MapReduce在运行时是分成Map Task和Reduce Task来处理的，而不是完整的Job。

简单的控制流大概是这样的：JobTracker调度任务给TaskTracker, TaskTracker执行任务时，会返回进度报告。JobTracker则会记录进度的进行状况，如果某个TaskTracker上的任务执行失败，那么JobTracker会把这个任务分配给另一台TaskTracker，直到任务执行完成。

这里更详细地解释一下数据流。上例中有两个Map任务及一个Reduce任务。数据首先按照TextInputFormat形式被处理成两个InputSplit，然后输入到两个Map中，Map程序会读取InputSplit指定位置的数据，然后按照设定的方式处理该数据，最后写入到本地磁盘中。如果Map程序在没来得及将数据传送给Reduce时就崩溃了（程序出错或机器崩溃），那么JobTracker只需要另选一台机器重新执行这个Task就可以了。Reduce会读取Map的输出数据，合并value，然后将它们输出到HDFS上。下面有一个更具体的图（WordCount执行时的数据流），如图3-3所示。

当一个可执行文件作为Mapper时，每一个Map任务会以一个独立的进程启动这个可执行文件，然后在Map任务运行时，会把输入切分成行提供给可执行文件，并作为它的标准输入（stdin）内容。

当可执行文件运行出结果时，Map从标准输出（stdout）中收集数据，并将其转化为＜key, value＞对，作为Map的输出。

Reduce与Map相同，如果可执行文件做Reducer时，Reduce任务会启动这个可执行文件，并且将＜key, value＞对转化为行作为这个可执行文件的标准输入（stdin）。

然后Reduce会收集这个可执行文件的标准输出（stdout）的内容。并把每一行转化为＜key, value＞对，作为Reduce的输出。