参考资料： Hadoop权威指南第四版第七章
一、MapReduce是个what？
首先说下Hadoop 的四大组件：
HDFS：分布式存储系统。
MapReduce：分布式计算系统。
YARN： hadoop 的资源调度系统。
Common： 以上三大组件的底层支撑组件，主要提供基础工具包和 RPC 框架等。
Mapreduce 是一个分布式运算程序的编程框架，是用户开发“基于 hadoop的数据分析 应用”的核心框架。
Mapreduce 核心功能是将用户编写的业务逻辑代码和自带默认组件整合成一个完整的分布式运算程序，并发运行在一个 hadoop 集群上。
二、 MapReduce作业运行流程
你可以在 Job 对象上面调用 submit() 方法或者 waitForCompletion() 方法来运行一个 MapReduce 作业。这些方法影藏了背后大量的处理过程。下面我们来揭开 Hadoop 背后运行一个作业的步骤。整个过程如下图所示(后面会对每一个步骤讲解)：
从整体层面上看，有五个独立的实体：
- 客户端，提交 MapReduce 作业。
- YARN 资源管理器（YARN resource manager），负责协调集群上计算机资源的分配。
- YARN 节点管理器（YARN node manager），负责启动和监视集群中机器上的计算容器（container）。
- MapReduce的 application master，负责协调MapReduce 作业的任务。MRAppMaster 和 MapReduce 任务运行在容器中，该容器由资源管理器进行调度（schedule）[此处理解为划分、分配更为合适] 且由节点管理器进行管理。
- 分布式文件系统（通常是 HDFS），用来在其他实体间共享作业文件。
作业提交（Job Submission）
在 Job 对象上面调用 submit() 方法，在内部创建一个 JobSubmitter 实例，然后调用该实例的 submitJobInternal() 方法（图1步骤1）。如果使用waitForCompletion() 方法来进行提交作业，该方法每隔 1 秒轮询作业的进度，如果进度有所变化，将该进度报告给控制台（console）。当作业成功完成，作业计数器被显示出来。否则，导致作业失败的错误被记录到控制台。
JobSubmitter所实现的作业提交过程如下：
- 向资源管理器请求一个 application ID，该 ID 被用作 MapReduce 作业的 ID(步骤2)。
- 检查作业指定的输出（output）目录。例如，如果该输出目录没有被指定或者已经存在，作业不会被提交且一个错误被抛出给 MapReduce 程序
为作业计算输入分片（input splits）。如果分片不能被计算（可能因为输入路径（input paths）不存在），该作业不会被提交且一个错误被抛出给 MapReduce 程序。 - 拷贝作业运行必备的资源，包括作业 JAR 文件，配置文件以及计算的输入分片，到一个以作业 ID 命名的共享文件系统目录中(步骤3)。作业 JAR 文件以一个高副本因子（a high replication factor）进行拷贝（由 mapreduce.client.submit.file.replication 属性控制，默认值为 10），所以在作业任务运行时，在集群中有很多的作业 JAR 副本供节点管理器来访问。
- 通过在资源管理器上调用 submitApplication 来提交作业(步骤4)。
作业初始化（Job Initialization）
当资源管理器接受到 submitApplication() 方法的调用，它把请求递交给 YARN 调度器（scheduler）。调度器分配了一个容器（container），资源管理器在该容器中启动 application master 进程，该进程被节点管理器管理（步骤5a 和 5b）。
MapReduce 作业的 application master 是一个 Java 应用，它的主类是 MRAppMaster。它通过创建一定数量的簿记对象（bookkeeping object）跟踪作业进度来初始化作业(步骤6)，该簿记对象接受任务报告的进度和完成情况。接下来，application master 从共享文件系统中获取客户端计算的输入分片(步骤7)。然后它为每个分片创建一个 map 任务，同样创建由 mapreduce.job.reduces 属性控制的多个reduce 任务对象（或者在 Job 对象上通过 setNumReduceTasks() 方法设置）。任务ID在此时分配。
Applcation master 必须决定如何运行组成 MapReduce 作业的任务。如果作业比较小，application master 可能选择在和它自身运行的 JVM 上运行这些任务。这种情况发生的前提是，application master 判断分配和运行任务在一个新的容器上的开销超过并行运行这些任务所带来的回报，据此和顺序地在同一个节点上运行这些任务进行比较。这样的作业被称为 uberized，或者作为一个 uber 任务运行。
一个小的作业具有哪些资格？默认的情况下，它拥有少于 10 个 mapper，只有一个 reducer，且单个输入的 size 小于 HDFS block 的。（注意，这些值可以通过 mapreduce.job.ubertask.maxmaps, mapreduce.job.ubertask.maxreduces, mapreduce.job.ubertask.maxbytes 进行设置）。Uber 任务必须显示地将 mapreduce.job.ubertask.enable 设置为 true
最后，在任何任务运行之前， application master 调用 OutputCommiter 的 setupJob() 方法。系统默认是使用 FileOutputCommiter，它为作业创建最终的输出目录和任务输出创建临时工作空间（temporary working space）。
任务分配（Task Assignment）
如果作业没有资格作为 uber 任务来运行，那么 application master 为作业中的 map 任务和 reduce 任务向资源管理器请求容器(步骤8)。首先要为 map 任务发送请求，该请求优先级高于 reduce 任务的请求，因为所有的 map 任务必须在 reduce 的排序阶段（sort phase）能够启动之前完成。reduce 任务的请求至少有 5% 的 map 任务已经完成才会发出(可配置)。
reduce 任务可以运行在集群中的任何地方，但是 map 任务的请求有数据本地约束（data locality constraint），调度器尽力遵守该约束（try to honor）。在最佳的情况下，任务的输入是数据本地的（data local）-- 也就是任务运行在分片驻留的节点上。或者，任务可能是机架本地的（rack local），也就是和分片在同一个机架上，而不是同一个节点上。有一些任务既不是数据本地的也不是机架本地的，该任务从不同机架上面获取数据而不是任务本身运行的节点上。对于特定的作业，你可以通过查看作业计数器（job's counters）来确定任务的位置级别（locality level）。
请求也为任务指定内存需求和 CPU 数量。默认，每个 map 和 recude 任务被分配 1024 MB的内存和一个虚拟的核（virtual core）。这些值可以通过如下属性（mapreduce.map.memory.mb, mapreduce.reduce.memory.mb, mapreduce.map.cpu.vcores, mapreduce.reduce.cpu.vcores）在每个作业基础上进行配置（遵守 Memory settings in YARN and MapReduce 中描述的最小最大值）。
任务执行
一旦资源调度器在一个特定的节点上为一个任务分配一个容器所需的资源，application master 通过连接节点管理器来启动这个容器(步骤9a 和9b)。任务通过一个主类为 YarnChild 的 Java 应用程序来执行。在它运行任务之前，它会将任务所需的资源本地化，包括作业配置，JAR 文件以及一些在分布式缓存中的文件(步骤10)。最后，它运行 map 或者 reduce 任务(步骤11)。
YarnChild 在一个指定的 JVM 中运行，所以任何用户自定义的 map 和 reduce 函数的 bugs（或者甚至在 YarnChild）都不会影响到节点管理器 -- 比如造成节点管理的崩溃或者挂起。
每个任务能够执行计划（setup）和提交（commit）动作，它们运行在和任务本身相同的 JVM 当中，由作业的 OutputCommiter 来确定。对于基于文件的作业，提交动作把任务的输出从临时位置移动到最终位置。提交协议确保当推测执行可用时，在复制的任务中只有一个被提交，其他的都被取消掉。
进度和状态的更新
MapReduce 作业是长时间运行的批处理作业（long-running batch jobs），运行时间从几十秒到几小时。由于可能运行时间很长，所以用户得到该作业的处理进度反馈是很重要的。
作业和任务都含有一个状态，包括运行状态、maps 和 reduces 的处理进度，作业计数器的值，以及一个状态消息或描述（可能在用户代码中设置）。这些状态会在作业的过程中改变。那么它是如何与客户端进行通信的？
当一个任务运行，它会保持进度的跟踪（就是任务完成的比例）。对于 map 任务，就是被处理的输入的比例。对于 reduce 任务，稍微复杂一点，但是系统任然能够估算已处理的 reduce 输入的比例。通过把整个过程分为三个部分，对应于 shuffle 的三个阶段。例如，如果一个任务运行 reducer 完成了一半的输入，该任务的进度就是 5/6，因为它已经完成了 copy 和 sort 阶段（1/3 each）以及 reduce 阶段完成了一半（1/6）。
MapReduce 的进度组成
进度不总是可测的，但是它告诉 Hadoop 一个任务在做的一些事情。例如，任务的写输出记录是有进度的，即使不能用总进度的百分比（因为它自己也可能不知道到底有多少输出要写，也可能不知道需要写的总量）来表示进度报告非常重要，Hadoop 不会使一个报告进度的任务失败（not fail a task that's making progress）。如下的操作构成了进度：
- 读取输入记录（在 mapper 或者 reducer 中）。
- 写输出记录（在 mapper 或者 reducer 中）。
- 设置状态描述（由 Reporter 的或 TaskAttempContext 的 setStatus() 方法设置）。
- 计数器的增长（使用 Reporter 的 incrCounter() 方法 或者 Counter 的 increment() 方法）。
- 调用 Reporter 的或者 TaskAttemptContext 的 progress() 方法。
任务有一些计数器，它们在任务运行时记录各种事件，这些计数器要么是框架内置的，例如：已写入的map输出记录数，要么是用户自定义的。
当 map 或 reduce 任务运行时，子进程使用 umbilical 接口和父 application master 进行通信。任务每隔三秒钟通过 umbilical 接口报告其进度和状态（包括计数器）给 application master，application master会形成一个作业的聚合视图。
在作业执行的过程中，客户端每秒通过轮询 application master 获取最新的状态（间隔通过 mapreduce.client.progressmonitor.polinterval 设置）。客户端也可使用 Job 的 getStatus() 方法获取一个包含作业所有状态信息的 JobStatus 实例，过程如下：
作业完成（Job Completion）
当 application master 接受到最后一个任务完成的通知，它改变该作业的状态为 “successful”。当 Job 对象轮询状态，它知道作业已经成功完成，所以它打印一条消息告诉用户以及从 waitForCompletion() 方法返回。此时，作业的统计信息和计数器被打印到控制台。
Application master 也可以发送一条 HTTP 作业通知，如果配置了的话。当客户端想要接受回调时，可以通过 mapreduce.job.end-notification.url 属性进行配置。
最后，当作业完成，application master 和作业容器清理他们的工作状态（所以中间输入会被删除），然后 OutputCommiter 的 commitJob() 方法被调用。作业的信息被作业历史服务器存档，以便日后用户查询。
三、MapReduce计算流程
先把图放出来，后面的讲解都能在这个图上有体现。
计算流程是：输入分片 ---> map阶段 ---> combiner阶段(可选) ---> shuffle阶段 ---> reduce阶段
1. 输入分片（input split）：
在进行map计算之前，mapreduce会根据输入文件计算输入分片（input split），每个输入分片（input split）针对一个map任务，输入分片（input split）存储的并非数据本身，而是一个分片长度和一个记录数据的位置的数组，输入分片（input split）往往和hdfs的block（块）关系很密切，假如我们设定hdfs的块的大小是64mb，如果我们输入有三个文件，大小分别是3mb、65mb和127mb，那么mapreduce会把3mb文件分为一个输入分片（input split），65mb则是两个输入分片（input split）而127mb也是两个输入分片（input split），换句话说我们如果在map计算前做输入分片调整，例如合并小文件，那么就会有5个map任务将执行，而且每个map执行的数据大小不均，这个也是mapreduce优化计算的一个关键点。[分块分片的参考：Hadoop分块与分片介绍及分片和分块大小相同的原因]
Hadoop分块和分片
默认分片大小与分块大小是相同的原因
hadoop在存储有输入数据（HDFS中的数据）的节点上运行map任务，可以获得高性能，这就是所谓的数据本地化。所以最佳分片的大小应该与HDFS上的块大小一样，因为如果分片跨越2个数据块，对于任何一个HDFS节点（Hadoop系统保证一个块存储在一个datanode上，基本不可能同时存储这2个数据块），分片中的另外一块数据就需要通过网络传输到map任务节点，与使用本地数据运行map任务相比，效率则更低！
小结：分块优化，减少网络传输数据，使用本地数据运行map任务。
2. map阶段：就是程序员编写好的map函数了，因此map函数效率相对好控制，而且一般map操作都是本地化操作也就是在数据存储节点上进行；
3. combiner阶段：combiner阶段是程序员可以选择的，combiner其实也是一种reduce操作，因此我们看见WordCount类里是用reduce进行加载的。Combiner是一个本地化的reduce操作，它是map运算的后续操作，主要是在map计算出中间文件前做一个简单的合并重复key值的操作，例如我们对文件里的单词频率做统计，map计算时候如果碰到一个hadoop的单词就会记录为1，但是这篇文章里hadoop可能会出现n多次，那么map输出文件冗余就会很多，因此在reduce计算前对相同的key做一个合并操作，那么文件会变小，这样就提高了宽带的传输效率，毕竟hadoop计算力宽带资源往往是计算的瓶颈也是最为宝贵的资源，但是combiner操作是有风险的，使用它的原则是combiner的输入不会影响到reduce计算的最终输入，例如：如果计算只是求总数，最大值，最小值可以使用combiner，但是做平均值计算使用combiner的话，最终的reduce计算结果就会出错。
小结：combine时一个本地化的reduce操作，对相同的key做一个合并操作，提高带宽的利用率
4. shuffle阶段：
将map的输出作为reduce的输入的过程就是shuffle了，这个是mapreduce优化的重点地方。这里我不讲怎么优化shuffle阶段，讲讲shuffle阶段的原理，因为大部分的书籍里都没讲清楚shuffle阶段。Shuffle一开始就是map阶段做输出操作，一般mapreduce计算的都是海量数据，map输出时候不可能把所有文件都放到内存操作，因此map写入磁盘的过程十分的复杂，更何况map输出时候要对结果进行排序，内存开销是很大的，map在做输出时候会在内存里开启一个环形内存缓冲区，这个缓冲区专门用来输出的，默认大小是100mb，并且在配置文件里为这个缓冲区设定了一个阀值，默认是0.80（这个大小和阀值都是可以在配置文件里进行配置的），同时map还会为输出操作启动一个守护线程，如果缓冲区的内存达到了阀值的80%时候，这个守护线程就会把内容写到磁盘上，这个过程叫spill，另外的20%内存可以继续写入要写进磁盘的数据，写入磁盘和写入内存操作是互不干扰的，如果缓存区被撑满了，那么map就会阻塞写入内存的操作，让写入磁盘操作完成后再继续执行写入内存操作，前面我讲到写入磁盘前会有个排序操作，这个是在写入磁盘操作时候进行，不是在写入内存时候进行的，如果我们定义了combiner函数，那么排序前还会执行combiner操作。每次spill操作也就是写入磁盘操作时候就会写一个溢出文件，也就是说在做map输出有几次spill就会产生多少个溢出文件，等map输出全部做完后，map会合并这些输出文件。这个过程里还会有一个Partitioner操作，对于这个操作很多人都很迷糊，其实Partitioner操作和map阶段的输入分片（Input split）很像，一个Partitioner对应一个reduce作业，如果我们mapreduce操作只有一个reduce操作，那么Partitioner就只有一个，如果我们有多个reduce操作，那么Partitioner对应的就会有多个，Partitioner因此就是reduce的输入分片，这个程序员可以编程控制，主要是根据实际key和value的值，根据实际业务类型或者为了更好的reduce负载均衡要求进行，这是提高reduce效率的一个关键所在。到了reduce阶段就是合并map输出文件了，Partitioner会找到对应的map输出文件，然后进行复制操作，复制操作时reduce会开启几个复制线程，这些线程默认个数是5个，程序员也可以在配置文件更改复制线程的个数，这个复制过程和map写入磁盘过程类似，也有阀值和内存大小，阀值一样可以在配置文件里配置，而内存大小是直接使用reduce的tasktracker的内存大小，复制时候reduce还会进行排序操作和合并文件操作，这些操作完了就会进行reduce计算了。
小结：
- shuffle是mapreduce优化的重点地方；
- 环形内存缓冲区 ：因此map写入磁盘的过程十分的复杂，更何况map输出时候要对结果进行排序，内存开销是很大的，所以开启环形内存缓冲区专门用于输出；默认是100MB，阈值是0.8；
- spill(溢写)：缓冲区>80%，写入磁盘；溢写前先排序，后合并，写入磁盘；
- Partition：Partitioner操作和map阶段的输入分片（Input split）很像，Partitioner会找到对应的map输出文件，然后进行复制操作，作为reduce的输入；
- reduce阶段：和map函数一样也是程序员编写的，最终结果是存储在hdfs上的。
Split是怎么划分的？
参考FileInputFormat类中split切分算法和host选择算法介绍
五、 关于MapReduce运行过程的一些疑问？
1. map阶段的溢写疑问？
MapReduce 的Shuffle阶段的溢写阶段，分两类：1、环形缓冲区的数据到达80%时，就会溢写到本地磁盘，当再次达到80%时，就会再次溢写到磁盘，
直到最后一次，不管环形缓冲区还有多少数据，都会溢写到磁盘。然后会对这多次溢写到磁盘的多个小文件进行合并，减少Reduce阶段的网络传输。
2.就是没有达到80%map阶段就结束了，这时直接把环形缓冲区的数据写到磁盘上，供下一步合并使用。
2.MapReduce中如何处理跨行的Block和InputSplit？
FileInputFormat对文件的切分是严格按照偏移量来的，因此一行记录比较长的话，可能被切分到不同的InputSplit。但这并不会对Map造成影响，尽管一行记录可能被拆分到不同的InputSplit，但是与FileInputFormat关联的RecordReader被设计的足够健壮，当一行记录跨InputSplit时，其能够到读取不同的InputSplit，直到把这一行记录读取完成。我们拿最常见的TextInputFormat举例分析如何处理跨行InputSplit的，TextInputFormat关联的是LineRecordReader。
其读取文件是通过LineReader（in就是一个LineReader实例）的readLine方法完成的。关键的逻辑就在这个readLine方法里，这个方法主要的逻辑归纳起来是3点:
A 总是从buffer里读取数据,如果buffer里的数据读完了,先加载下一批数据到buffer。
B 在buffer中查找"行尾"，将开始位置至行尾处的数据拷贝给str(也就是最后的Value)。若为遇到"行尾",继续加载新的数据到buffer进行查找。
C 关键点在于:给到buffer的数据是直接从文件中读取的，完全不会考虑是否超过了split的界限，而是一直读取到当前行结束为止。
更通俗的解释是：如果map按照split读取数据时发现最后一行数据没有遇到\n换行符，则会去下一个split中读取数据直到遇到\n为止，第二个map读取数据时会查看上个map的split数据的最后一行是不是\n，若果不是说明本split的第一行数据已经被读取，自己从第二行开始读取；
