GoogleMapReduce中文版资源-CSDN文库

Google

需积分: 10 64 浏览量 2018-08-17 22:46:34 上传评论收藏 186KB DOCX 举报

资源推荐

资源详情

资源评论

Google MapReduce 中文版

译者: alex



摘要

MapReduce 是一个编程模型，也是一个处理和生成超大数据集的算法模型的相关实现。

用户首先创建一个 Map 函数处理一个基于 key/value pair 的数据集合，输出中间的基于

key/value pair 的数据集合；然后再创建一个 Reduce 函数用来合并所有的具有相同中间

key 值的中间 value 值。现实世界中有很多满足上述处理模型的例子，本论文将详细描述

这个模型。



MapReduce 架构的程序能够在大量的普通配置的计算机上实现并行化处理。这个系统在

运行时只关心：如何分割输入数据，在大量计算机组成的集群上的调度，集群中计算机的

错误处理，管理集群中计算机之间必要的通信。采用 MapReduce 架构可以使那些没有并

行计算和分布式处理系统开发经验的程序员有效利用分布式系统的丰富资源。



我们的 MapReduce 实现运行在规模可以灵活调整的由普通机器组成的集群上：一个典型

的 MapReduce 计算往往由几千台机器组成、处理以 TB 计算的数据。程序员发现这个系

统非常好用：已经实现了数以百计的 MapReduce 程序，在 Google 的集群上，每天都有

1000 多个 MapReduce 程序在执行。

1、介绍

在过去的 5 年里，包括本文作者在内的 Google 的很多程序员，为了处理海量的原始数据，

已经实现了数以百计的、专用的计算方法。这些计算方法用来处理大量的原始数据，比如

文档抓取（类似网络爬虫的程序）、Web 请求日志等等；也为了计算处理各种类型的衍生

数据，比如倒排索引、Web 文档的图结构的各种表示形势、每台主机上网络爬虫抓取的页

面数量的汇总、每天被请求的最多的查询的集合等等。大多数这样的数据处理运算在概念

上很容易理解。然而由于输入的数据量巨大，因此要想在可接受的时间内完成运算，只有

将这些计算分布在成百上千的主机上。如何处理并行计算、如何分发数据、如何处理错误

所有这些问题综合在一起，需要大量的代码处理，因此也使得原本简单的运算变得难以处

理。



为了解决上述复杂的问题，我们设计一个新的抽象模型，使用这个抽象模型，我们只要表

述我们想要执行的简单运算即可，而不必关心并行计算、容错、数据分布、负载均衡等复

杂的细节，这些问题都被封装在了一个库里面。设计这个抽象模型的灵感来自 Lisp 和许多

其他函数式语言的 Map 和 Reduce 的原语。我们意识到我们大多数的运算都包含这样的操

作：在输入数据的“逻辑”记录上应用 Map 操作得出一个中间 key/value pair 集合，然后在

所有具有相同 key 值的 value 值上应用 Reduce 操作，从而达到合并中间的数据，得到一

个想要的结果的目的。使用 MapReduce 模型，再结合用户实现的 Map 和 Reduce 函数，

我们就可以非常容易的实现大规模并行化计算；通过 MapReduce 模型自带的“再次执行”

（re-execution）功能，也提供了初级的容灾实现方案。



这个工作(实现一个 MapReduce 框架模型)的主要贡献是通过简单的接口来实现自动的并行

化和大规模的分布式计算，通过使用 MapReduce 模型接口实现在大量普通的 PC 机上高

性能计算。



第二部分描述基本的编程模型和一些使用案例。第三部分描述了一个经过裁剪的、适合我

们的基于集群的计算环境的 MapReduce 实现。第四部分描述我们认为在 MapReduce 编

程模型中一些实用的技巧。第五部分对于各种不同的任务，测量我们 MapReduce 实现的

性能。第六部分揭示了在 Google 内部如何使用 MapReduce 作为基础重写我们的索引系统

产品，包括其它一些使用 MapReduce 的经验。第七部分讨论相关的和未来的工作。

2、编程模型

MapReduce 编程模型的原理是：利用一个输入 key/value pair 集合来产生一个输出的

key/value pair 集合。MapReduce 库的用户用两个函数表达这个计算：Map 和 Reduce。



用户自定义的 Map 函数接受一个输入的 key/value pair 值，然后产生一个中间 key/value

pair 值的集合。MapReduce 库把所有具有相同中间 key 值 I 的中间 value 值集合在一起后

传递给 reduce 函数。



用户自定义的 Reduce 函数接受一个中间 key 的值 I 和相关的一个 value 值的集合

Reduce 函数合并这些 value 值，形成一个较小的 value 值的集合。一般的，每次 Reduce

函数调用只产生 0 或 1 个输出 value 值。通常我们通过一个迭代器把中间 value 值提供给

Reduce 函数，这样我们就可以处理无法全部放入内存中的大量的 value 值的集合。

2.1、例子

例如，计算一个大的文档集合中每个单词出现的次数，下面是伪代码段：

map(String key, String value):

 // 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 函数把 Map 函数产生的每一个特定的词的计数累加起来。



另外，用户编写代码，使用输入和输出文件的名字、可选的调节参数来完成一个符合

MapReduce 模型规范的对象，然后调用 MapReduce 函数，并把这个规范对象传递给它。

用户的代码和 MapReduce 库链接在一起(用 C++实现)。附录 A 包含了这个实例的全部程

序代码。

2.2、类型

尽管在前面例子的伪代码中使用了以字符串表示的输入输出值，但是在概念上，用户定义

的 Map 和 Reduce 函数都有相关联的类型：

map(k1,v1) ->list(k2,v2)

 reduce(k2,list(v2)) ->list(v2)

比如，输入的 key 和 value 值与输出的 key 和 value 值在类型上推导的域不同。此外，中间

key 和 value 值与输出 key 和 value 值在类型上推导的域相同。

（alex 注：原文中这个 domain 的含义不是很清楚，我参考 Hadoop、KFS 等实现，map

和 reduce 都使用了泛型，因此，我把 domain 翻译成类型推导的域）。

我们的 C++中使用字符串类型作为用户自定义函数的输入输出，用户在自己的代码中对字

符串进行适当的类型转换。

2.3、更多的例子

这里还有一些有趣的简单例子，可以很容易的使用 MapReduce 模型来表示：

 分布式的 Grep：Map 函数输出匹配某个模式的一行，Reduce 函数是一个恒等函数，

即把中间数据复制到输出。

 计算 URL 访问频率：Map 函数处理日志中 web 页面请求的记录，然后输出

(URL,1)。Reduce 函数把相同 URL 的 value 值都累加起来，产生(URL,记录总数)结

果。

 倒转网络链接图：Map 函数在源页面（source）中搜索所有的链接目标（target）并

输出为(target,source)。Reduce 函数把给定链接目标（target）的链接组合成一个列

表，输出(target,list(source))。

 每个主机的检索词向量：检索词向量用一个(词,频率)列表来概述出现在文档或文档集

中的最重要的一些词。Map 函数为每一个输入文档输出(主机名,检索词向量)，其中

主机名来自文档的 URL。Reduce 函数接收给定主机的所有文档的检索词向量，并把

这些检索词向量加在一起，丢弃掉低频的检索词，输出一个最终的(主机名,检索词向

量)。

 倒排索引：Map 函数分析每个文档输出一个(词,文档号)的列表，Reduce 函数的输入

是一个给定词的所有（词，文档号），排序所有的文档号，输出(词,list（文档号）)。

所有的输出集合形成一个简单的倒排索引，它以一种简单的算法跟踪词在文档中的位

置。

 分布式排序：Map 函数从每个记录提取 key，输出(key,record)。Reduce 函数不改变

任何的值。这个运算依赖分区机制(在 4.1 描述)和排序属性(在 4.2 描述)。

3、实现

MapReduce 模型可以有多种不同的实现方式。如何正确选择取决于具体的环境。例如，

一种实现方式适用于小型的共享内存方式的机器，另外一种实现方式则适用于大型 NUMA

架构的多处理器的主机，而有的实现方式更适合大型的网络连接集群。

本章节描述一个适用于 Google 内部广泛使用的运算环境的实现：用以太网交换机连接、

由普通 PC 机组成的大型集群。在我们的环境里包括：

1.x86 架构、运行 Linux 操作系统、双处理器、2-4GB 内存的机器。

2.普通的网络硬件设备，每个机器的带宽为百兆或者千兆，但是远小于网络的平均带宽的

一半。（alex 注：这里需要网络专家解释一下了）

3.集群中包含成百上千的机器，因此，机器故障是常态。

4.存储为廉价的内置 IDE 硬盘。一个内部分布式文件系统用来管理存储在这些磁盘上的数

据。文件系统通过数据复制来在不可靠的硬件上保证数据的可靠性和有效性。

5.用户提交工作（job）给调度系统。每个工作（job）都包含一系列的任务（task），调度

系统将这些任务调度到集群中多台可用的机器上。

3.1、执行概括

通过将 Map 调用的输入数据自动分割为 M 个数据片段的集合，Map 调用被分布到多台机

器上执行。输入的数据片段能够在不同的机器上并行处理。使用分区函数将 Map 调用产

生的中间 key 值分成 R 个不同分区（例如，hash(key) mod R），Reduce 调用也被分布到

多台机器上执行。分区数量（R）和分区函数由用户来指定。

图 1 展示了我们的 MapReduce 实现中操作的全部流程。当用户调用 MapReduce 函数时，

将发生下面的一系列动作（下面的序号和图 1 中的序号一一对应）：

1.用户程序首先调用的 MapReduce 库将输入文件分成 M 个数据片度，每个数据片段的大

小一般从 16MB 到 64MB(可以通过可选的参数来控制每个数据片段的大小)。然后用户程

序在机群中创建大量的程序副本。（alex：copies of the program 还真难翻译）

2.这些程序副本中的有一个特殊的程序–master。副本中其它的程序都是 worker 程序，由

master 分配任务。有 M 个 Map 任务和 R 个 Reduce 任务将被分配，master 将一个 Map 任

务或 Reduce 任务分配给一个空闲的 worker。

3.被分配了 map 任务的 worker 程序读取相关的输入数据片段，从输入的数据片段中解析

出 key/value pair，然后把 key/value pair 传递给用户自定义的 Map 函数，由 Map 函数生

成并输出的中间 key/value pair，并缓存在内存中。

剩余19页未读，继续阅读

评论收藏

内容反馈

MHuiG

粉丝: 19
资源: 10

Google MapReduce中文版

最新资源

Google MapReduce中文版

Google MapReduce-中文版

GoogleMapReduce中文版

Google MapReduce 中文版

Mapreduce中文版

mapreduce中文版

Google MapReduce中文版.pdf

Google MapReduce中文版 pdf

Google+MapReduce中文版

Google MapReduce(二)

Google-Bigtable中文版、Google-File-System中文版、Google-MapReduce中文版

MapReduce中文版

Google-MapReduce中文版.doc

Google_MapReduce论文中文版

Google-MapReduce中文版_1.0.zip

google 论文 mapreduce 中文版

Google_MapReduce中文版-系统架构

MapReduce中文版.pdf

MapReduce中文版.rar

Google MapReduce 论文中文版

MapReduce 中文版论文

Google MapReduce论文中文版

Google技术之MapReduce

Google MapReduce(四)

Google MapReduce(三)

VM虚拟机去虚拟化 玩游戏多开 过检测 tp vmp cf dnf

VMware-VMRC-12.0.4-21740317

ipmitool-1.8.11-2.x86-64.vib

CentOS 7.9 最小化安装 kubernetes（k8s）1.25.3（免费下载）

最新资源

VM虚拟机去虚拟化玩游戏多开过检测 tp vmp cf dnf