MapReduce将复杂的、运行于大规模集群上的并行计算过程高度抽象到了两个函数：Map和Reduce，这两个函数及其核心思想都源自函数式编程语言。
MapReduce设计的一个理念就是 “计算向数据靠拢” ，而不是“数据向计算靠拢",因为数据需要 大量的网络传输开销 ，尤其是在大规模数据环境下，这种开销尤为惊人，所以，移动计算要比移动数据更加经济。在这种理念下，一个集群中，只要有可能，MapReduce框架就会将Map程序就近地在HDFS数据所在的节点运行，即将计算节点和存储节点放在一起运行，从而减少了节点间的数据移动开销。
MapReduce框架采用了 Master/Slave架构，包括一个 Master和若干个 Slave Master上运行JobTracker，Slave上运行 TaskTracker。用户提交的每个计算作业，会被划分成若干个任务。
MapReduce模型的核心是Map函数和Reduce函数，二者都是由应用程序开发者负责具体实现的。
Map函数和Reduce函数都是以<key, value>作为输入，按一定的映射规则转换成另一个或一批<key, value>进行输出
比如，我们想编写一个MapReduce程序来统计一个文本文件中每个单词出现的次数
对于Map函数的输入**<k1,v1>而言，其具体输入数据就是<某一行文本在文件中的偏移位置，该行文本的内容>。用户可以自己编写Map函数处理过程，把文件中的一行读取后解析出每个单词，输出一批中间结果<单词，出现次数>**;
然后，把这些中间结果作为Reduce函数的输入，Reduce函数的具体处理过程也是由用户自己编写的，用户可以将相同单词的出现次数进行累加，输出每个单词出现的总次数。
大规模数据集的处理包括分布式存储和分布式计算两个核心环节。谷歌公司用分布式文件系统GFS实现分布式数据存储，用MapReduce实现分布式计算，而Hadoop则使用分布式文件系统HDFS实现分布式数据存储，用Hadoop MapReduce实现分布式计算。MapReduce的输入和输出都需要借助于分布式文件系统进行存储，这些文件被分布存储到集群中的多个节点上。
MapReduce的核心思想可以用**“分而治之”**来描述，也就是把一个大的数据集拆分成多个小数据块在多台机器上并行处理，也就是说，一个大的MapReduce作业，**首先会被拆分成许多个Map任务在多台机器上并行执行，**每个Map任务通常运行在数据存储的节点上，这样，计算和数据就可以放在一起运行，不需要额外的数据传输开销。
当Map任务结束后，会生成以<key,value>形式表示的许多中间结果。
然后，这些中间结果会被分发到多个Reduce任务在多台机器上并行执行，具有相同key的<key,value>会被发送到同一个Reduce任务那里，Reduce任务会对中间结果进行汇总计算得到最后结果，并输出到分布式文件系统中。
不同的Map任务之间不会进行通信，不同的Reduce任务之间爷不会发生任何信息交换；用户不能显式地从一台机器向另一台继机器发送消息，所有的数据交换都是通过MapReduce框架自身去实现的。
在MapReduce的整个执行过程中，Map任务的输入文件、Reduce任务的处理结果都是保存在分布式文件系统中的，而Map任务处理得到的中间结果则保存在本地存储中（如磁盘）。
Shuffle过程是MapReduce整个工作流程的核心环节，理解Shuffle过程的基本原理，对于理解MapReduce流程至关重要。
所谓Shuffle,是指对Map输出结果进行分区、排序、合并等处理并交给Reduce的过程。因此，Shuffle过程分为Map端的操作和Reduce端的操作。
①在Map端的Shuffle过程。Map的输出结果首先被写入缓存，当缓存满时，就启动溢写操作，把缓存中的数据写入磁盘文件，并清空缓存。当启动溢写操作时，首先需要把缓存中的数据进行分区，然后对每个分区的数据进行排序（Sort）和合并（Combine），之后再写入磁盘文件。每次溢写操作会生成一个新的磁盘文件，随着Map任务的执行，磁盘中就会生成多个溢写文件。在Map任务全部结束之前，这些溢写文件会被归并（Merge）成一个大的磁盘文件，然后，通知相应的Reduce任务来领取属于自己处理的数据。
②在Reduce端的Shuffle过程。Reduce任务从Map 端的不同 Map 机器领回属于自己处理的那部分数据，然后，对数据进行归并（Merge）后交给Reduce处理。
Map端的Shuffle过程包括4个步骤
Map任务的输入数据一般保存在分布式文件系统(如GFS或HDFS)的文件块中，这些文件块的格式是任意的，可以是文档，也可以是二进制格式的。Map任务接受<key,value>作为输入后，按一定的映射规则转换成一批<key,value>进行输出。
每个Map任务都会被分配一个缓存，Map的输出结果不是立即写入磁盘，而是首先写入缓存。在缓存中积累一定数量的Map输出结果以后，再一
次性批量写入磁盘，这样可以大大减少对磁盘I/O的影响。因为，磁盘包含机械部件，它是通过磁头移动和盘片的转动来寻址定位数据的，每次寻址的开销很大，如果每个Map输出结果都直接写人磁盘，会引入很多次寻址开销，而一次性批量写入，就只需要一次寻址，连续写入，大大降低了开销。需要注意的是，在写入缓存之前，key与value值都会被序列化成字节数组。
提供给MapReduce的缓存的容量是有限的，默认大小是100MB。随着Map任务的执行，缓存中Map结果的数量会不断增加，很快就会占满整个缓存，这时，就必须启动溢写（Spill）操作，把缓存中的内容一次性写入磁盘，并清空缓存。溢写的过程通常是由另外一个单独的后台线程来完成的，不会影响Map结果往缓存写人。但是，为了保证Map结果能够不停地持续写入缓存，不受溢写过程的影响，就必须让缓存中一直有可用的空间，不能等到全部占满才启动溢写过程，所以，一般会设置一个溢写比例，如0.8，也就是说，当100MB大小的缓存被填满80MB数据时，就启动溢写过程，把已经写入的80MB数据写入磁盘，剩余20MB空间供Map结果继续写入。
但是，在溢写到磁盘之前，缓存中的数据首先会被分区（Partition）。缓存中的数据是<key,value>形式的键值对，这些键值对最终需要交给不同的Reduce任务进行并行处理。MapReduce通过Partitioner接口对这些键值对进行分区，默认采用的分区方式是采用Hash函数对key进行哈希后再用Reduce任务的数量进行取模，可以表示成hash(key)modR。其中，R表示Reduce任务的数量，这样，就可以把Map输出结果均匀地分配给这R个Reduce任务去并行处理了。当然，
MapReduce也允许用户通过重载Partitioner接口来自定义分区方式。
对于每个分区内的所有键值对，后台线程会根据key对它们进行内存排序（Sort），排序是MapReduce 的默认操作。排序结束后，还包含一个可选的合并（Combine）操作。如果用户事先没有定义Combiner函数，就不用进行合并操作。如果用户事先定义了Combiner函数，则这个时候会执行合并操作，从而减少需要溢写到磁盘的数据量。
所谓**“合并”**，是指将那些具有相同key的<key,value>的value加起来，比如，有两个键值对<“xmu”,1>和<“xmu”,1>,经过合并操作以后就可以得到一个键值对<“xmu”,2>，减少了键值对的数量。这里需要注意，Map端的这种合并操作，其实和Reduce的功能相似，但是，由于这个操作发生在Map端，所以，我们只能称之为“合并”，从而有别于Reduce。不过，并非所有场合都可以使用Combiner,因为，Combiner的输出是Reduce任务的输入，Combiner绝不能改变Reduce
任务最终的计算结果，一般而言，累加、最大值等场景可以使用合并操作。
经过分区、排序以及可能发生的合并操作之后，这些缓存中的键值对就可以被写入磁盘，并清空缓存。每次溢写操作都会在磁盘中生成一个新的溢写文件，写入溢写文件中的所有键值对，都是经过分区和排序的。
每次溢写操作都会在磁盘中生成一个新的溢写文件，随着MapReduce任务的进行，磁盘中的溢写文件数量会越来越多。当然，如果Map输出结果很少，磁盘上只会存在一个溢写文件，但是，通常都会存在多个溢写文件。最终，在Map任务全部结束之前，系统会对所有溢写文件中的数据进行归并（Merge），生成一个大的溢写文件，这个大的溢写文件中的所有键值对，也是经过分区和排序的。 所谓 “归并”（Merge)，是指对于具有相同key的键值对，会被归并成一个新的键值对。具体而言，对于若干个具有相同key的键值对<k1,v1>,<k1,v2>…,会被归并成一个新的键值对<k1,<V1,V2,vn>>。
另外，进行文件归并时，如果磁盘中已经生成的溢写文件的数量超过参数
min.num.spills.for.combine的值时（默认值是3,用户可以修改这个值）。那么，就可以再次运行Combiner,对数据进行合并操作，从而减少写入磁盘的数据量。但是，如果磁盘中只有一两个溢写文件时，执行合并操作就会“得不偿失”，因为执行合并操作本身也需要代价，因此，不会运行Combiner。
经过上述4个步骤以后，Map端的Shuffle过程全部完成，最终生成的一个大文件会被存放在本地磁盘。这个大文件中的数据是被分区的，不同的分区会被发送到不同的Reduce任务进行并行处理。
JobTracker会一直监测Map任务的执行，当监测到一个Map任务完成后，就会立即通知相关的Reduce任务来“领取”数据，然后开始Reduce端的Shuffle过程。
相对于Map端而言，Reduce端的Shuffle过程非常简单，只需要从Map端读取Map结果，然后执行归并操作，最后输送给Reduce任务进行处理。
Map端的Shuffle过程结束后，所有Map输出结果都保存在Map机器的本地磁盘上，Reduce任务需要把这些数据“领取”（Fetch）回来存放到自己所在机器的本地磁盘上。因此，在每个Reduce任务真正开始之前，它大部分时间都在从Map端把属于自己处理的那些分区的数据“领取”过来。
每个Reduce任务会不断地通过RPC（Remote Procedure Call）向JobTracker询问Map任务是否已经完成；JobTracker监测到一个Map任务完成后，就会通知相关的Reduce任务来“领取”数据；一旦一个Reduce任务收到 JobTracker 通知，它就会到该Map任务所在机器上把属于自己处理的分区数据领取到本地磁盘中。一般系统中会存在多个Map机器，因此，Reduce任务会使用多个线程同时从多个Map机器领回数据。
从Map端领回的数据，会首先被存放在Reduce任务所在机器的缓存中，如果缓存被占满，就会像Map端一样被溢写到磁盘中。由于在Shuffle阶段，Reduce任务还没有真正开始执行，因此，这时可以把内存的大部分空间分配给Shuffle过程作为缓存。需要注意的是，系统中一般存在多个Map机器，所以，Reduce任务会从多个Map机器领回属于自己处理的那些分区的数据，因此，缓存中的数据是来自不同的Map机器的，一般会存在很多可以合并（Combine）的键值对。
当溢写过程启动时，具有相同key的键值对会被归并（Merge）,如果用户定义了Combiner,则归并后的数据还可以执行合并操作，减少写入磁盘的数据量。每个溢写过程结束后，都会在磁盘中生成一个溢写文件，因此，磁盘上会存在多个溢写文件。最终，当所有的Map端数据都已经被领回时，和Map端类似，多个溢写文件会被归并成一个大文件，归并的时候还会对键值对进行排序，从而使得最终大文件中的键值对都是有序的。当然，在数据很少的情形下，缓存就可以存储所有数据，就不需要把数据溢写到磁盘，而是直接在内存中执行归并操作，然后直接输出给Reduce任务。需
要说明的是，把磁盘上的多个溢写文件归并成一个大文件，可能需要执行多轮归并操作。每轮归并操作可以归并的文件数量是由参数io.sort.factor的值来控制的（默认值是10,可以修改）。
假设磁盘中生成了50个溢写文件，每轮可以归并10个溢写文件，则需要经过5轮归并，得到5个归并后的大文件。
磁盘中经过多轮归并后得到的若干个大文件，不会继续归并成一个新的大文件，而是直接输入给Reduce任务，这样可以减少磁盘读写开销。由此，整个Shuffle过程顺利结束。接下来，Reduce任务会执行 Reduce函数中定义的各种映射，输出最终结果，并保存到分布式文件系统中。
