MapReduce是一种分布式并行编程框架。
在计算机发展史上的"摩尔定律"：CPU的性能每隔18个月就可以翻一番。然而，从2005年起，摩尔定律逐渐失效，因为CPU制作工艺存在上限、性能不可能无限提升。但是数据增长的速度符合大数据摩尔定律。数据量快速增加和CPU性能缓慢发展之间产生了矛盾，因此人们寻找出数据处理能力提升的两条路线：1.单核CPU到双核到四核到八核。2.分布式并行编程。
分布式并行编程：借助一个集群通过多台机器同时处理大规模数据集，可以获得海量计算能力。
分布式并行编程模型MapReduce是谷歌公司最先提出的，Hadoop MapReduce是它的开源实现，并进行了许多优化处理，使用门槛更低。
事实上，在谷歌公司提出MapReduce之前，已经有相关的并行编程框架了。比如MPI（消息传递接口）就是一种非常典型的并行编程框架。那么为什么还要提出MapReduce呢？与传统并行编程框架相比的优势是什么？
MapReduce向编程人员屏蔽了整个分布式程序运行的相关底层细节，编程人员无需掌握分布式并行编程的细节。
MapReduce将复杂的、运行在大规模集群上的并行计算过程高度的抽象到两个函数：Map和Reduce。
MapReduce的策略：“分而治之”。把一个存储在分布式文件系统中的非常庞大的数据集，切分成非常多独立的分片（split），然后为每一个分片单独的启动一个map任务，最终通过多个map任务，实现并行的在多个机器上进行任务处理。
MapReduce的理念：“计算向数据靠拢”，而非数据向计算靠拢（要完成一次数据分析的时候，选择一个计算节点，把运行数据分析的程序放到计算节点上运行；然后把它所涉及的数据，全部从各个不同节点上面拉过来，传输到计算发生的地方。）
而计算向数据靠拢，在集群中选出机器作为map机器，这些机器负责相关的数据处理分析。HDFS中以块为单位存储，数据块被存储在不同的机器上，假设MapReduce想分析机器A上的数据，它会寻找离机器A最近的map机器进行处理（理想情况下这两台机器在一起），实现在数据节点上执行计算，最终把结果汇总到任务协调节点，最终提交给用户。这样做减少了大量的网络传输开销，也提高了分布式处理的性能。
MapReduce的架构：Master/Slave架构。包括一个Master服务器（运行作业跟踪器JobTracker、负责整个作业的调度和处理以及失败和恢复）和若干个Slave服务器（运行负责具体任务执行的组件TaskTracker，负责接收JobTracker给它发的作业处理指令、完成具体的任务处理）。
Hadoop框架是用Java开发的，但是MapReduce可以支持不同语言编写。
5.1.3Map和Reduce函数
Map函数的输入是键值对，输出是键值对列表。中间如何处理、如何输出是用户自定义的。
Reduce的输入是一个键以及一堆值的列表（value-list），输出是键值对（value）。
MapReduce体系结构主要包括四个部分：客户端Client、作业跟踪器JobTracker、TaskTracker和Task。
MapReduce体系结构主要包括四个部分：
- 客户端Client：
用户可以通过Client，将编写的MapReduce程序提交到JobTracker端。
用户可以通过Client提供的接口，查看当前提交作业的运行状态（在Hadoop集群中，应用程序表现为作业的形式，一个作业通常包含多个Task）。 - 作业跟踪器JobTracker：
负责资源的监控和作业的调度。
监控底层所有TaskTracker以及当前运行的Job的健康状况，一旦探测到失败的情况，就把这个任务转移到其他节点继续执行。
还要跟踪任务的执行进度、资源使用量等信息，并将这些信息发送给任务调度器TaskScheduler（TaskScheduler负责将Task分配到空闲的指定TaskTracker上去执行，并且允许用户自定义任务分配模块） - 任务跟踪器TaskTracker：
执行具体的相关任务，一般接受JobTracker发送过来的命令。
会将本节点上资源的使用情况、任务的运行进度通过"心跳"（heartbeat）的方式，周期性的发送给JobTracker。JobTracker可以根据受到的命令执行相应操作，比如启动新任务、杀死任务等。
TaskTracker会将本节点上的资源（CPU、内存等）进行等量划分，划分成多个"slot"。slot是一种资源调度单位，分为map类型的slot（分配给map任务）和reduce类型的slot（分配给reduce任务），两种slot类型之间不通用。只有当机器上有空闲的slot时，才能把任务Task分配执行。
Hadoop调度器负责将各个TaskTracker上的空闲slot分配给Task使用。 - 任务Task：
Task分为Map Task和Reduce Task，都是由TaskTracker启动的。
在一台机器上可以同时运行两种类型的任务。
大规模数据集保存在分布式文件系统（通常是HDFS）中，分布式的存储在不同的机器节点，为了实现分布式并行处理，需要对大规模数据集进行分片操作，每一个分片单独启动一个map任务，这中间需要把map输出结果进行排序、归并、合并（这个过程称为Shuffle），Shuffle过程结束后，将结果发送到不同reduce上进行数据处理，处理结束后再输出给分布式文件系统。
注意，在这个过程中：
1.不同的Map任务之间不会进行通信。
2.不同的Reduce任务之间不会发生任何信息交换。
3.用户不能显式的从一台机器向另一台机器发送消息。
4.所有的数据交换都是通过MapReduce框架自身去实现的。
虽然图中只给出了两个节点，但实际中节点是非常多的。在执行时，首先从分布式文件中加载文件，由InputFormat对输入进行格式验证、把大的数据集切分成多个分片（split），注意这种切分只是逻辑上的定义而非物理切分。接着让记录阅读器RR（RecordReader）根据分片的位置和长度信息，从分布式文件系统中各个块把相关分片读出，输出的
分片（Split）
InputFormat会把大的数据集切分成多个分片（split）。split是一个逻辑概念，它只包含一些元数据信息，比如数据起始位置、数据长度、数据所在节点等。
在下图中，一个文件在HDFS中可能分成很多块（block）进行存储，这个块是物理意义上的块。分片却分成了4个split，比如split1横跨block1和二分之一的block2。因此，分片和分块是两个不同的概念。
Map任务的数量
每次产生一个分片的时候，就会产生一个Map任务。因此有多少个分片就会产生多少个Map任务。一旦分片过多，Map任务在切换过程中会消耗大量管理资源。而分片过少，并行度过少，达不到提升效率的目的。因此，理想的分片策略是，将一个块的大小作为一个分片的大小。
Reduce任务的数量
最优的Reduce任务的个数取决于集群中可用的Reduce任务槽（slot）的数目。集群中有很多TaskTracker，每个TaskTracker都会将资源划分成多个slot，一部分slot会划分给Reduce使用，称为Reduce slot。
通常设置比Reduce任务槽数目稍微小一些的Reduce任务个数，这样可以预留一些系统资源处理可能发生的错误。
数据保持在分布式文件系统中，数据输入后需要进行分片处理，每一个分片启动一个Map任务（包含用户的处理逻辑），Map输出的键值对并不是直接发送给Reduce，而是直接写入缓存中。当缓存满了的时候，再发生溢写（分区、排序、合并），将缓存中的数据溢写到磁盘中，生成磁盘文件，同时把缓存清空。
把缓存中的数据溢写到磁盘中时，还要发生分区、排序、以及可能发生的合并操作。并且溢写会发生多次，生成多个磁盘文件，要把多个磁盘文件归并成一个大的磁盘文件。在这个大的磁盘文件中，包含了所有键值对。得到大的磁盘文件之后，会通过Reduce任务将数据取走。
Reduce任务会把属于自己的数据分区从不同的Map机器上拿到本地的机器上去，然后执行归并、合并操作。
一个完整的Shuffle过程包含：Map端的Shuffle过程、Reduce端的Shuffle过程。
Map端的Shuffle过程分为四大步骤。
1.输入数据和执行Map任务：大规模数据集存储在分布式文件系统中，文件存储格式可能是文本、二进制，都可以通过RR生成满足Map任务需要的
2.写入缓存：每次都直接写入磁盘的话，会带来大量寻址开销。因此让每个Map任务的输出都写入缓存中。
3.溢写（分区、排序、合并）：当缓存满了之后（设置溢写比例为0.8，将80MB作为门槛值，一旦达到80MB将写入磁盘，防止影响Map正常运行），启动溢写过程。溢写过程中，还需要进行分区、排序，还有可能产生合并操作。因为Map输出的键值对列表需要分配给多个不同的Reduce任务进行处理，因此要进行分区，比如有4个Reduce任务就分成4个区，每个区会有对应的Reduce任务取走数据（分区默认采用哈希函数）。分区之后还要进行排序，排序是默认的操作，根据字典序排序，无需用户干预。排序之后可能发生合并（combine），合并是为了减少溢写到磁盘中的数据量。
4.文件归并：数据写入磁盘后，会生成磁盘文件。随着溢写的多次发生，磁盘上会生成多个磁盘文件。在Map任务全部结束之前，系统会进行归并，得到一个大的文件存放在本地磁盘。文件在归并时，如果溢写文件数量大于预定值（默认是3），则可以再次启动Combiner，少于预定值则不需要。JobTracker会一直监测Map任务的执行，并通知相应的Reduce任务来领取数据。
区分：合并（combine）和归并（merge）
给定两个键值对<“a”,1>和<“a”,1>
执行合并操作，将得到<“a”,2>
执行归并操作，将得到<“a”,<1,1>>
Reduce任务通过RPC向JobTracker询问Map任务是否已经完成，若完成则领取数据。
Reduce从其他Map任务所在机器，领取属于自己处理的分区。由于这些分区来自不同的Map机器，所以要先归并、再合并，写入磁盘。
多个溢写文件被归并成一个或多个大文件，文件中的键值对是排序的。
当数据很少时，无需溢写到磁盘，直接在缓存中归并，然后输出给Reduce即可。
1.程序部署：从集群中挑选机器，一个机器作为Master，其他机器作为Worker。
2.分配Map任务、分配Reduce任务：集群中有很多Worker，选出Worker中的一部分分配Map任务、另外一部分分配Reduce任务。对于执行Map任务的机器，需要输入数据，通常是非常大的文件，因此要对大数据集进行分片（0~M），分片后从集群中执行Map任务的机器中挑选出空闲的机器进行分片的数据处理。
3.读数据：从分布式文件系统各个分片中把数据读入，生成
4.本地写数据：缓存中的数据写满后要溢写到磁盘，生成一个大的文件，包含多个分区。这些数据最终要发送给远端的Reduce任务处理。
5.远程读数据：负责执行Reduce任务的机器从各个相关的Map任务所在机器上领取数据，进行相关处理。
6.写数据：将Reduce任务处理后的相关结果写入输出文件（分布式文件系统HDFS）中。
注意：输入来自分布式文件系统，输出写入分布式文件系统。然而，中间过程的数据不写入到分布式文件系统。比如Map任务的处理结果直接写入本地磁盘。
举例：
注意，MapReduce不是万能的，不适用数据集结果之间存在依赖的情况。只有能够满足"分而治之"的任务才能用MapReduce。
首先，要检查WordCount程序任务能否采用MapReduce解决？
可以。因为可以将包含单词的大文件，切分成多个分片进行独立统计，再把统计结果进行汇总。
问题是，一个大的文本文件需要转换成
Map输出的结果要经过Shuffle才能发给Reduce任务，这里假设用户没有定义Combine时的操作，即没有发生合并。
如果用户定义了Combine，过程示意图如下：
可以使用MapReduce解决各种计算问题：
用MapReduce实现关系的自然连接
假设有关系R(A,B)和关系S(B,C)，想对二者进行自然连接操作。
首先，使用Map过程，将来自R的每个元组转换成一个键值对
同理，把来自S的每个元组
所有键（B值）相同的元组被发送到同一个Reduce进程中，Reduce将来自关系R和S的、具有相同属性B值的元组进行合并。
Reduce进程的输出则是连接后的元组，输出被写到一个单独的输出文件中。
具体实例如下：
