特别说明
这是一个由simviso团队所组织进行的基于mit分布式系统课程翻译的系列，由知秋带领和其他成员一起翻译的课程以及课程当中涉及的论文翻译。
本文章参与人员
| 参与人员 | 参与范围 |
|---|---|
| 知秋 | 审校 |
| 虚生花 | 翻译 |
概要
MapReduce是一种编程模型，它是一种用于处理和生成大型数据集的实现。用户通过指定一个用来处理键值对(Key/Value)的map函数来生成一个中间键值对集合。然后，再指定一个reduce函数， 它用来合并所有的具有相同中间key的中间value 。现实生活中有许多任务可以通过该模型进行表达，具体案例会在论文中展现出来。
以这种函数式风格编写的程序能够在一个大型商用机器集群上自动并行执行。这个系统在运行时只关心：如何分割输入数据，在大量计算机所组成的集群上的调度问题，集群中计算机的故障处理，管理集群中计算机之间的必要通信。使用MapReduce编程模型可以让那些没有并行计算和分布式系统开发经验的程序员有效的使用分布式系统的资源。
我们实现的MapReduce可以在一个大型的商用计算机集群上运行，并且具备高度扩展性：一个标准的MapReduce计算可以在数千台机器上处理TB级的数据。程序员会觉得该系统易于使用。目前在谷歌已经实现了数以百计的MapReduce程序，在谷歌的集群上，每天都有1000多个MapReduce的工作在执行。
1 简介
在过去五年里，作者以及许多其他在谷歌工作的人已经实现了数百种用于特殊目的的计算。它们可以用来处理大量原始数据，例如：爬取的文档，网页请求日志等等。并以此来计算出各种衍生数据，例如：倒排索引，Web文档的各种图表示，每台主机所抓取页面数的摘要，以及特定某天中最频繁的查询集等等。大部分这种计算从概念上来讲都很简单。但是，输入的数据量通常非常巨大，并且为了能在一个合理的时间内完成，计算任务也不得不分配给成百上千台机器去执行。如何并行化计算，分配数据以及处理故障的问题，所有的问题都纠缠在一起，这就需要大量的代码来对它们进行处理。因此，这也使得原本简单的计算变得极为复杂，而且难以处理。
为了应对这种复杂性，我们设计了一种新的抽象，它可以让我们表达我们所试图执行的简单计算，但该库中隐藏了并行化，容错，数据分发以及负载均衡这些混乱的细节。我们这种抽象的设计灵感来源于Lisp和许多其他函数式语言中存在的map和reduce原语。我们意识到，大多数计算都涉及到对输入中的每个逻辑记录进行_map_操作，以便于计算出一个中间键值对的集合。然后，为了恰当的整合衍生数据，我们对共用相同键的所有值进行_reduce_操作。通过使用具备用户所指定的_map_和_reduce_操作的函数式模型，这使得我们能够轻松并行化大型计算，并且使用重新执行的结果作为容错的主要机制。
这项工作的主要贡献在于提供了一个简单而强大的接口，该接口可实现大规模计算的自动并行化和分布式执行。通过使用该接口的实现，从而在大型商用计算机集群上获得了高性能。
本文的第2章节描述了该基础编程模型并给出了一些案例。第3章节则是关于我们针对集群的计算环境所量身定制的MapReduce接口的实现。第4章节介绍了我们所找到的对于该编程模型的一些有用改进。第5章节则是关于我们通过一系列任务对我们所实现的MapReduce进行的性能测试。第6章节则探索了MapReduce在谷歌中的一些应用，这其中包括了我们使用它来重写我们的索引系统的一些经验。第7章节讨论了一些相关以及日后要做的工作。
2 编程模型
该计算任务将一个键值对集合作为输入，并生成一个键值对集合作为输出。MapReduce这个库的用户将这种计算任务以两个函数进行表达，即Map和Reduce。
由用户所编写的Map函数接收输入，并生成一个中间键值对集合。MapReduce这个库会将所有共用一个键的值组合在一起，并将它们传递给Reduce函数。
Reduce函数也是由用户所编写。它接受一个中间键以及该键的值的集合作为输入。它会将这些值合并在一起，以此来生成一组更小的值的集合。通常每次调用Reduce函数所产生的值的结果只有0个或者1个。中间值通过一个迭代器来传递给用户所编写的Reduce函数。这使得我们可以处理这些因为数据量太大而无法存放在内存中的存储值的list列表了。
2.1 案例
我们可以思考下这样一个场景，我们要从大量的文档中计算出每个单词的出现次数。用户将会编写出类似于下方伪代码的代码：
map(Stringkey,Stringvalue):
// key: document name
// value: document contents
for each word w in value:
EmitIntermediate(w,"1");
reduce(String key,Iterator values):
// key: a word
// values: a list of counts
int result =0;
for each v in values:
result += ParseInt(v);
Emit(AsString(result));map函数会返回一个单词加上它出现的次数的键值对（在这个例子中，返回的出现次数就是1）。reduce函数会将该单词的出现次数统计在一起。
此外，用户通过编写代码，传入输入和输出文件的名字，以及可选的调节参数来创建一个符合MapReduce模型规范的对象。接着，用户调用MapReduce函数，并将这个对象传入该函数。用户的代码和MapReduce库（该库是由C++实现的）链接在一起，附录A中会提供该案例的完整代码。
2.2 类型
尽管在前面的伪代码中的输入和输出的类型都是String，但是从概念上来说，用户所提供的map和reduce函数都有相关联的类型。
map(k1,v1) -->list(k2,v2)
reduce(k2,list(v2)) -->list(v2)例如，输入的键和值与输出的键和值来自于不同的地方。此外，中间的键和值与输出的键和值在类型上相同。
在我们的C++实现中，我们使用String类型作为用户所定义的函数的输入和输出的类型，用户在自己的代码中对字符串进行适当的类型转换。
2.3 更多案例
此处有一些可以很容易使用MapReduce模型来表示的简单例子：
分布式过滤器：Map函数会发出（emit）匹配某个规则的一行。Reduce函数是一个恒等函数，即把中间数据复制到输出。（虚生花注：恒等函数是数学中是一种没有任何作用的函数，它的输入等于输出，即f(x)=x）。
计算URL的访问频率：map函数用来处理网页请求的日志，并输出(URL,1)。reduce函数则用于将相同URL的值全部加起来，并输出(URL, 访问总次数)这样的键值对结果。
倒转网络链接图：map函数会在源页面中找到所有的目标URL，并输出<target, source>这样的键值对。reduce函数会将给定的目标URL的所有链接组合成一个列表，输出<target, list(source)>这样的键值对。
每台主机上的检索词频率：term（这里是指搜索系统里的某一项东西，这里指检索词）vector（这里指数组）将一个文档或者是一组文档中出现的最重要的单词概括为_<单词，频率>_ 这样的键值对列表，对于每个输入文档，map函数会输出这样一对键值对<hostname, term vector>（其中hostname是从文档中的URL里提取出来的）。Reduce函数接收给定主机的所有每一个文档的term vector。它会将这些term vector加在一起，并去除频率较低的term，然后输出一个最终键值对<hostname, term vector>。
倒排索引：map函数会对每个文档进行解析，并输出<word, 文档ID>这样的键值对序列。reduce函数所接受的输入是一个给定词的所有键值对，接着它会对所有文档ID进行排序，然后输出<word, list(文档ID)>。所有输出键值对的集合可以形成一个简单的倒排索引。我们能简单的计算出每个单词在文档中的位置。
分布式排序：map函数会从每条记录中提取出一个key，然后输出<key, record>这样的键值对。reduce函数对这些键值对不做任何修改，直接输出。这种计算任务依赖分区机制（详见章节4.1）以及排序属性（详见章节4.2）。
有疑问加站长微信联系（非本文作者）
