2.1　MapReduce设计思想

现在让我们来做一个游戏：假如你和朋友玩牌，但是不知道这一摞牌够不够54张。大家都知道，一副牌中，有13张红桃，13张黑桃，13张方块，13张梅花，外加两张王牌。

那么你会怎么数呢？有两种方式：

第一种，你一个人从头到尾数一遍，并逐个记录下多少张红桃、多少张黑桃、多少张方块、多少张梅花，以及王牌的张数。

第二种，你将牌分发给你和你的牌友们，让他们“并行”地数，“并行”地统计，然后他们把结果反馈给你，你最后总结牌友们反馈的结果。

你会采用哪一种方法呢？第一种是比较“勤快”的人采取的“愚蠢”的做法，第二种则是“懒惰”的人采取的“聪明”的做法。你可能会说，不就54张牌吗，一会儿就数完了，没必要动脑筋统计汇总。是的，那假如有上千张牌、上万张牌又该如何操作呢？

近些年，人们一直争论一个富有哲学色彩的问题：是懒惰推动了科技进步，还是科技进步助长了懒惰呢？笔者认为，从某种角度来讲，科技进步弥补了人类的懒惰，所以懒惰并不见得是件坏事。有数据表明，懒惰的人一般创新意识比较强。

第一种方法是一种串行的方法，相对来说，比较浪费时间，但操作相对简单，不用沟通，不用协调，不用总结。在我们的例子中只有54张牌，如果有540张、5400张呢？

第二种方法是一种并行的方法，相对于第一种方法来说省时，但是增加了不必要的麻烦，比如分发、沟通、反馈、总结。这其实就是MapReduce的思想概要。

之前说过，Hadoop的核心思想来源于Google的两篇论文。Google的那篇MapReduce论文里说：Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional languages。大致意思是，MapReduce的灵感来源于函数式语言（比如Lisp）中的内置函数map和reduce。这句话提到了MapReduce思想的渊源。Lisp是一种列表处理语言（List Processing），是一种应用于人工智能处理的符号式语言，由MIT的人工智能专家、图灵奖获得者John McCarthy于1958年设计发明。所以，从某种层面上讲，MapReduce的思想早在1958年就被提出来了。

简单来说，在函数式语言里，Map表示对一张列表（List）中的每个元素进行计算，Reduce表示对一张列表中的每个元素进行迭代计算。在MapReduce里，Map处理的是原始数据，自然是杂乱无章的，每条数据之间没有依赖关系，简单地说就是：你是你，我是我，你Map的时候不影响我，我Map的时候不影响你。到了Reduce阶段，数据是以key后面跟着若干个value来组成的，这些value有相关性，至少它们都在一个key下面，于是就符合函数式语言里Map和Reduce的基本思想了。这样我们就可以将MapReduce理解为：把一堆杂乱无章的数据按照某种特征归纳起来，然后处理并得到最后的结果。Map面对的是杂乱无章的、互不相关的数据，它解析每个数据，从中提取出key和value，也就是提取数据的特征。

为了简化起见，我们可以将MapReduce分为两个经典的函数。

• 映射（Mapping）：对集合里的每个目标应用同一个操作。在上面的例子中，我们需要把每张牌“数”一遍，并且分别映射到红桃、黑桃、方块、梅花的张数中。经过Mapping之后，会输出一个key/value对。例如，红桃：4张；黑桃：6张，等等。

• 化简（Reducing）：相当于遍历集合中的元素返回一个汇总的结果。在上面的例子中，将各位牌友的反馈结果汇总，最后计算出是否是54张牌。注意，这里是按照相同的key进行汇总的，即黑桃：××张；红桃：××张，等等，黑桃、红桃等在这里充当了“key”。

具体分析，Hadoop MapReduce用于超大规模的数据处理时，精华的思想有以下三个。

1. 并行化

三个臭皮匠赛过诸葛亮，这句古语其实就有并行计算的思想在里面，诸葛亮的计谋再厉害，也比不过三个臭皮匠并行思考。同样的道理，三台性能一般的机器，其并行计算的速度也可能超过一台强悍的服务器级别的机器的计算速度。

那么，什么样的计算任务可以进行并行化计算？如果大数据可以分为具有同样计算过程的数据块，并且这些数据块之间不存在数据依赖关系，则提高处理速度的最好办法就是并行计算。

在并行计算中，一次可执行多个指令的算法，目的是提高计算速度，以及通过扩大规模求解问题，解决大型而复杂的计算问题。其实并行计算可分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多台处理器并发地执行计算。并行计算的基本思想是用多台处理器来协同求解同一个问题，即将被求解的问题分解成若干部分，各部分均由一台独立的处理器来并行计算。并行计算系统既可以是专门设计的、含有多台处理器的超级计算机，也可以是以某种方式互连的若干台独立计算机构成的集群。通过并行计算集群完成数据的处理，再将处理的结果返回给用户。

并行计算的第一个重要问题是如何划分计算任务或者计算数据，以便对划分的子任务或数据块同时进行计算。划分得均匀与否直接关系到大数据的处理速度。当然，结合一些均衡的调度算法，可以使得集群中的机器都能发挥最大的作用，减少闲置或者等待的时间。但在一些场合下，数据之间存在相互依赖关系，或者数据出现迭代算法，恰好无法划分。顺便提及一句，在类似这样的场合，推荐使用Spark，因为Spark在具有迭代的场合性能上要比Hadoop MapReduce强出许多。

Map和Reduce都是并行执行的，如图2-1所示。

各个map函数对所划分的数据进行并行处理，从不同的输入数据产生不同的中间结果输出。各个reduce函数也各自进行并行计算，各自负责处理不同的中间结果数据集合。在进行reduce处理之前，必须等到所有的map函数执行完，因此，在进入reduce前需要有一个同步障（Barrier）；这个阶段也负责对map函数的中间结果数据进行收集整理（Aggregation & Shuffle），以便reduce更有效地计算最终结果。最终汇总所有reduce函数的输出结果即可获得最终结果。

2. 抽象化

MapReduce将编程框架抽象化或者模型化。在整个框架中只有两个模型：Mapper与Reducer。在以往的并行计算方法中，缺少高层并行编程模型，在解决实际问题时，程序员的思维一直停留在方法、函数这个层面，并没有把方法和函数抽象化。为了克服这一缺陷，MapReduce借鉴了Lisp函数式语言中的思想，用map和reduce两个函数提供了高层的并行编程抽象模型，如图2-2所示。

MapReduce定义了如下所示的Map和Reduce两个抽象的编程接口，由用户去编程实现：

输入：键值对(k1; v1)表示的数据。

处理：文档数据记录（如文本文件中的行或数据表格中的行）将以键值对形式传入map函数；map函数将处理这些键值对，并以另一种键值对形式输出处理的一组键值对中间结果[(k2; v2)]。

输出：键值对[(k2; v2)]表示的一组中间数据。

输入：由map输出的一组键值对[(k2; v2)] 将被进行合并处理，将同样主键下的不同数值合并到一张列表[v2]中，故reduce的输入为(k2; [v2])，其中[v2]可以理解为一张列表。

处理：对传入的中间结果列表数据进行某种整理或进一步处理，并产生最终的某种形式的结果输出[(k3; v3)]。

输出：最终处理结果[(k3; v3)]。

值得一提的是，Map和Reduce为程序员提供了一个清晰的操作接口抽象描述，在MapReduce使用过程中架构清晰明了，如果出现接口问题，也比较容易定位。

3. 架构统一，隐藏细节

MapReduce统一架构，为程序员隐藏系统层细节。在之前的并行计算方法中，缺少统一的计算框架支持，程序员需要考虑数据存储、划分、分发、结果收集、错误恢复等诸多细节。为此，MapReduce设计并提供了统一的计算框架，为程序员隐藏了绝大多数系统层面的处理细节。MapReduce提供一个统一的计算框架，可完成计算任务的划分和调度、数据的分布存储和划分、处理数据与计算任务的同步、结果数据的收集整理（sorting、combining、partitioning等）、系统通信、负载平衡、计算性能优化处理、处理系统节点出错检测和失效恢复等。

MapReduce通过抽象模型和计算框架把需要做什么与具体怎么做区分开来，为程序员提供一个抽象和高层的编程接口与框架。程序员仅需关心其应用层的具体计算问题，以及编写少量的处理应用本身计算问题的程序代码。如何具体完成这个并行计算任务所相关的诸多系统层细节被隐藏起来，交给计算框架去处理：从分布代码的执行，到大到数千小到单个节点集群的自动调度使用。