MapReduce
优点：可在短时间内完成大量工作。缺点：算法必须经过重写，需要对系统工程有一定的理解。适用数据类型：数值型和标称型数据。
MapReduce是一个软件框架，可以将单个计算作业分配给多台计算机执行。它假定这些作业在单机上需要很长的运行时间，因此使用多台机器缩短运行时间。常见的例子是日常统计数字的汇总，该任务单机上执行时间将超过一整天。
尽管有人声称他们已经独立开发过类似的框架，美国还是把MapReduce的专利颁发给了Google。Google公司的Jeffrey Dean和Sanjay Ghemawat在2004年的一篇论文中第一次提出了这个思想，该论文的题目是“MapReduce：Simplified Data Processing on Large Clusters”1MapReduce的名字由函数式编程中常用的map和reduce两个单词组成。
1. J. Dean, S. Ghemawat, “MapReduce: Si mplified Data Processing on Large Cl usters,” OSDI ’04: 6th Symposium on Operating System Design and Implementa tion, San Francisco, CA, December, 2004.
MapReduce在大量节点组成的集群上运行。它的工作流程是：单个作业被分成很多小份，输入数据也被切片分发到每个节点，各个节点只在本地数据上做运算，对应的运算代码称为mapper，这个过程被称作map2阶段。每个mapper的输出通过某种方式组合（一般还会做排序）。排序后的结果再被分成小份分发到各个节点进行下一步处理工作。第二步的处理阶段被称为reduce阶段，对应的运行代码被称为reducer。reducer的输出就是程序的最终执行结果。
2 map、reduce一般都不翻译，sort、combine有人分别翻译成排序、合并。mapper和reducer分别是指进行map和reduce操作的程序或节点，key/value有人翻译成 键/值。这几个词，在本章均未翻译。——译者注
MapReduce的优势在于，它使得程序以并行方式执行。如果集群由10个节点组成，而原先的作业需要10个小时来完成，那么应用MapReduce，该作业将在一个多小时之后得到同样的结果。举个例子，给出过去100年内中国每个省每天的正确气温数据，我们想知道近100年中国国内的最高气温。这里的数据格式为：<province><data><temp>。为了统计该时段内的最高温度，可以先将这些数据根据节点数分成很多份，每个节点各自寻找本机数据集上的最高温度。这样每个mapper将产生一个温度，形如</"max/"><temp>，也就是所有的mapper都会产生相同的key：/"max/"字符串。最后只需要一个reducer来比较所有mapper的输出，就能得到全局的最高温度值。
注意：在任何时候，每个mapper或reducer之间都不进行通信3 。每个节点只处理自己的事务，且在本地分配的数据集上运算。
3.这是指mapper各自之间不通信，reducer各自之间不通信，而reducer会接收mapper生成的数据。——译者注
不同类型的作业可能需要不同数目的reducer。再回到温度统计的例子，虽然这次使用的数据集相同，但不同的是这里要找出每年的最高温度。这样的话，mapper应先找到每年的最大温度并输出，所以中间数据的格式将形如。此外，还需要保证所有同一年的数据传递给同一个reducer，这由map和reduce阶段中间的sort阶段来完成。该例中也给出了MapReduce中值得注意的一点，即数据会以key/value对的形式传递。这里，年代（year）是key，温度（temp）是value。因此sort阶段将按照年代把数据分类，之后合并。最终每个reducer就会收到相同的key值。
从上述例子可以看出，reducer的数量并不是固定的。此外，在MapReduce的框架中还有其他一些灵活的配置选项。MapReduce的整个编配工作由主节点（masternode）控制。这些主节点控制整个MapReduce作业编配，包括每份数据存放的节点位置，以及map、sort和reduce等阶段的时序控制等。此外，主节点还要包含容错机制。一般地，每份mapper的输入数据会同时分发到多个节点形成多份副本，用于事务的失效处理。一个MapReduce集群的示意图如图15-1所示。
图 15-1 MapReduce框架的示意图。在该集群中有3台双核机器，如果机器0失效，作业仍可以正常继续
图15-1的每台机器都有两个处理器，可以同时处理两个map或者reduce任务。如果机器0在map阶段宕机，主节点将会发现这一点。主节点在发现该问题之后，会将机器0移出集群，并在剩余的节点上继续执行作业。在一些MapReduce的实现中，在多个机器上都保存有数据的多个备份，例如在机器0上存放的输入数据可能还存放在机器1上，以防机器0出现问题。同时，每个节点都必须与主节点通信，表明自己工作正常。如果某节点失效或者工作异常，主节点将重启该节点或者将该节点移出可用机器池。
总结一下上面几个例子中关于MapReduce的学习要点：
- 主节点控制MapReduce的作业流程；
- MapReduce的作业可以分成map任务和reduce任务；
- map任务之间不做数据交流，reduce任务也一样；
- 在map和reduce阶段中间，有一个sort或combine阶段；
- 数据被重复存放在不同的机器上，以防某个机器失效；
- mapper和reducer传输的数据形式为key/value对。
Apache的Hadoop项目是MapReduce框架的一个实现。下一节将开始讨论Hadoop项目，并介绍如何在Python中使用它。