Map-Reduce计算原理

综述

在单机下统计文件内各个元素的出现次数是简单的，但是当文件占用空间很大或文件数量很多使得单机处理效率差时，如何拓展至多台机器共同解决问题，这是一个很值得研究很需要去解决的问题。在单机下很容易处理的问题，在集群下却不一定是容易的，主要包括这些问题：
(1) 如何将一个大任务划分成小任务
(2) 如何将小任务的结果整合成大任务的结果
(3) 如何减少数据流动，提高工作效率
(4) 如何将用户的逻辑代码发送给集群的工作机器，即识别需要这套逻辑的机器并将相应逻辑指令发送给该机器执行

提交任务

客户端提交任务后，会将需要处理的文件存入HDFS。HDFS是一个分布式文件存储系统，可以看作是集群共同维护一个文件系统和存储数据，有一些机器负责存储元数据，即记录数据的基本信息，数据存储在哪台机器，有哪些备份，备份存储在哪里等等；有一些机器负责存储数据。集群中会有一些中心节点负责接收客户端提交的业务代码，这些中心节点会给集群其他节点分配任务，包括：
(1) 确定哪些机器拥有哪些数据
(2) 若机器A拥有数据片段A，则将操作数据片段A的代码指令发送给机器A，机器A开始使用业务代码处理数据片段A
(3) 确定某些机器的输出需要接着传递给哪些机器进一步处理得到最终输出
(4) 收集最终输出，反馈给客户端

输入分片

输入分片就是将用户提交的大文件划分后存入HDFS。在处理任务时，为了减少数据在集群之间的流动，采用计算向数据靠拢的策略，将业务代码发送给拥有数据片段的机器，机器接收到业务代码就可以使用代码逻辑在本地处理数据了，处理后得到的计算结果，在中央节点调控下会接着做一些处理并发送给下一阶段需要进一步处理的机器

Map操作

Map操作是对文件片段的第一步操作，下面以统计字符串出现次数的任务为例。首先大文件存入了HDFS被分成了许多小文件片段，拥有片段A的机器会对片段A执行Map操作，拥有片段B的机器会对片段执行Map操作。在统计字符串出现次数的任务中，Map操作可以被设计成对本地文件片段分词并生成键值对，即对每个分词生成一个键值对，键是字符串，值是1表示出现一次。Map操作后续还可以接着做一些操作，比如将相同键值的统计值进行合并，比如apple出现了3次，将三个合并成。Map操作后需要确定每个键值对需要接着发送给哪些机器进行统计汇总，比如机器1得到键值对，机器2得到键值对，则需要有一台机器将这两个键值对合并成，所以可以根据键的哈希值将键值对分配到下一步的机器，这样拥有相同的键的元素就会发送到相同的机器进行汇总。

Reduce操作

Map操作是得到对小任务的处理结果，而Reduce操作则负责将小任务的处理结果整合成大任务的处理结果，继续以统计字符串出现次数的任务为例。从上一步的讲解中，我们已经可以知道，所有的键值对都被发送到了同一台机器，这样在这台机器只需要简单所有键值对值的和就可以得到每个键的最终统计结果了。

总结

Map-Reduce操作是二阶段操作，当需要处理多阶段时可能需要一些精心设计，或者是将多阶段通过巧妙设计转成二阶段一次Map-Reduce操作解决，或者是分多次Map-Reduce操作解决。这是Map-Reduce计算框架的一个缺点，另一个缺点是Map-Reduce只能使用Map操作和Reduce操作解决问题，有一些问题不一定可以很好地转变成使用Map操作和Reduce操作可以解决的形式，所以后来又有了Spark的计算框架。