MapReduce:SimplifiedDataProcessingonLargeClusters翻译资源-CSDN文库

MapReduce

4星 · 超过85%的资源需积分: 15 88 浏览量 2009-12-07 12:31:03 上传评论收藏 480KB PDF 举报

资源推荐

资源详情

资源评论

 第 1 页

超大集群的简单数据处理

收件人：

发件人：崮山路上走 9 遍

抄送：

日期： 2005-08-05

关于： MapReduce: Simplified Data Processing on Large Clusters

Jeffrey Dean Sanjay Ghemawat

jeff@google.com , sanjay@google.com

Google , Inc.

摘要

MapReduce 是一个编程模式，它是与处理/产生海量数据集的实现相关。用户指定一个 map 函数，

通过这个 map 函数处理 key/value（键/值）对，并且产生一系列的中间 key/value 对，并且使用 reduce

函数来合并所有的具有相同 key 值的中间键值对中的值部分。现实生活中的很多任务的实现都是基于

这个模式的，正如本文稍后会讲述的那样。

使用这样的函数形式实现的程序可以自动分布到一个由普通机器组成的超大几群上并发执行。

run-time 系统会解决输入数据的分布细节，跨越机器集群的程序执行调度，处理机器的失效，并且管

理机器之间的通讯请求。这样的模式允许程序员可以不需要有什么并发处理或者分布式系统的经验，

就可以处理超大的分布式系统得资源。

我们的 MapReduce 系统的实现运行在一个由普通机器组成的大型集群上，并且有着很高的扩展性：

一个典型的 MapReduce 计算处理通常分布到上千台机器上来处理上 TB 的数据。程序员会发现这样

的系统很容易使用：已经开发出来了上百个 MapReduce 程序，并且每天在 Google 的集群上有上千

个 MapReduce job 正在执行。

1 介绍

在过去的 5 年内，Google 的创造者和其他人实现了上百个用于特别计算目的的程序来出来海量的原

始数据，比如蠕虫文档，web 请求 log，等等，用于计算出不同的数据，比如降序索引，不同的图示

展示的 web 文档，蠕虫采集的每个 host 的 page 数量摘要，给定日期内最常用的查询等等。绝大部

分计算都是概念上很简洁的。不过，输入的数据通常是非常巨大的，并且为了能在合理时间内执行完

毕，其上的计算必须分布到上百个或者上千个计算机上去执行。如何并发计算，如何分布数据，如何

处理失败等等相关问题合并在一起就会导致原本简单的计算掩埋在为了解决这些问题而引入的很复

杂的代码中。

因为这种复杂度，我们设计了一种新的东西来让我们能够方便处理这样的简单计算。这些简单计算原

本很简单，但是由于考虑到并发处理细节，容错细节，以及数据分布细节，负载均衡等等细节问题，

而导致代码非常复杂。所以我们抽象这些公共的细节到一个 lib 中。这种抽象是源自 Lisp 以及其他很

多面向功能的语言的 map 和 reduce 概念。我们认识到大部分操作都和 map 操作相关，这些 map 操

作都是运算在输入记录的每个逻辑”record”上，并且 map 操作为了产生一组中间的 key/value 键值对,

MapReduce

 第 2 页

并且接着在所有相同 key 的中间结果上执行 reduce 操作，这样就可以合并适当的数据。我们得函数

模式是使用用户定义的 map 和 reduce 操作，这样可以让我们并发执行大规模的运算，并且使用重新

执行的方式作为容错的优先机制。

MapReduce 的主要贡献在于提供了一个简单强大的接口，通过这个接口，可以把大尺度的计算自动

的并发和分布执行。使用这个接口，可以通过普通 PC 的巨大集群，来达到极高的性能。

第二节讲述了基本的编程模式，并且给出了一些例子。第三节讲述了一个面向我们基于集群的计算环

境的 MapReduce 的实现。第四节讲述了一些我们建议的精巧编程模式。第五节讲述了在不同任务下

我们的 MapReduce 实现的性能比较。第六节讲述了在 Google 中的 MapReduce 应用以及尝试重写

了我们产品的索引系统。第七节讲述了相关工作和未来的工作。

2 编程模式

我们的运算处理一组输入的（input）键值对（key/valuepairs）,并且产生一组输出的（output）键值

对。MapReduce 函数库德用户用两个函数来表达这样的计算：Map 和 Reduce。

Map 函数，是用户自定义的的函数，处理输入的键值对，并且产生一组中间的（intermediate）键值

对。MapReduce 函数库稽核所有相同的中间键值键 I 的值，并且发送给 Reduce 函数进行处理。

Reduce 函数同样也是用户提供的，它处理中间键值 I，以及这个中间键值相关的值集合。这个函数

合并这些值，最后形成一个相对较小的值集合。通常一个单次 Reduce 执行会产生 0 个或者 1 个输出

值。提供给 Reduce 函数的中间值是通过一个 iterator 来提供的。这就让我们可以处理超过内存容量

的值列表。

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到其对应的计数器（在这个例子里就是’1’）.reduce

函数把特定单词的所有出现的次数进行合并。

此外，我们还要写代码来对 mapreduce specification 对象进行赋值，设定输入和输出的文件名，以

及设定一些参数。接着我们调用 MapReduce 函数，把这个对象作为参数调用过去。我们把

MapReduce 函数库（C++函数库）和我们的程序链接在一起。附件 1 有完整的这个例子的代码。

 第 3 页

2.2 类型

即使上边的例子是用字符串作为输入和输入出的，从概念上讲，使用者提供的 map 和 reduce 函数有

着如下相关类型：

map (k1,v1)  list(k2,v2)

reduce (k2,list(v2))  list(v2)

也就是，输入的键和值和输出的键值是属于不同的域的。进一步说，中间的键值是和输出的键值属于

相同的域的。（比如 map 的输出，就是作为 reduce 的输入）。

我们的 C++实现上，把字符串作为用户定义函数的输入和输出，由用户代码来自己识别字符串到合适

的类型。

2.3 其他例子

这里有一些简单有趣的例子，都可以简单的通过 MapReduce 计算模型来展示：

分布式 Grep：如果 map 函数检查输入行，满足条件的时候，map 函数就把本行输出。reduce

函数就是一个直通函数，简单的把中间数据输出就可以了。

URL 访问频率统计： map 函数处理 webpag 请求和应答（URL，1）的 log。Reduce 函数把所有

相同的 URL 的值合并，并且输出一个成对的（URL，总个数）。

逆向 Web-Link 图： map 函数输出所有包含指向 target URL 的 source 网页，用（target,source）

这样的结构对输出。Reduce 函数局和所有关联相同 target URL 的 source 列表，并且输出一个

(target,list(source))这样的结构。

主机关键向量指标（Term-Vector per Hosts）: 关键词向量指标简而言之就是在一个文档或者一

组文档中的重点次出现的频率，用(word,frequency)表达。map 函数计算每一个输入文档（主机名字

是从文档的 URL 取出的）的关键词向量，然后输出（hostname,关键词向量(Term-Vector)）。reduce

函数处理所有相同 host 的所有文档关键词向量。去掉不常用的关键词，并且输出最终的(hostname，

关键词向量)对。

逆序索引： map 函数分析每一个文档，并且产生一个序列（word，documentID）组。

reduce 函数处理指定 word 的所有的序列组，并且对相关的 document ID 进行排序，输出一个

(word,list(document ID))组。所有的输出组，组成一个简单的逆序索引。通过这种方法可以很容易保

持关键词在文档库中的位置。

分布式排序： map 函数从每条记录中抽取关键字，并且产生(key,record)对。reduce 函数

原样输出所有的关键字对。这个算法是与 4.1 节描述的分布式处理相关的，并且排序是在 4.2 节描述

的。

3 实现

MapReduce 接口可以有很多种不同的实现。应当根据不同的环境选择不同的实现。比如，一个实现

可以适用于小型的共享内存的机器，另一个实现可能是基于大型 NUMA 多处理器系统，还可能有为

大规模计算机集群的实现。

本届描述了 Google 广泛使用的计算环境：用交换机网络[4]连接的，由普通 PC 构成的超大集群。在

我们的环境里：

（1）每个节点通常是双 x86 处理器，运行 Linux,每台机器 2-4GB 内存。

剩余18页未读，继续阅读

评论收藏

内容反馈

ieyzc

2012-11-07

google发表的首次提出MapReduce思想的文章，此版本为PDF版本，易于打印保存，但是编辑略有不便。翻译有部分需要改进，总体不错，对于像了解学习MapReduce但讨厌英语的同志们有很好的帮助。

Beckham008

粉丝: 5
资源: 13

MapReduce: Simplified Data Processing on Large Clusters翻译

最新资源

MapReduce: Simplified Data Processing on Large Clusters翻译

MapReduce: Simplified Data Processing on Large Clusters中文版

MapReduce: Simplified Data Processing on Large Clusters 英文原文

MapReduce Simplified Data Processing

MapReduce: Simplified Data Processing on Large Clusters

MapReduce: Simpliﬁed Data Processing on Large Clusters

MapReduce_Simplified_Data_Processing_on_Large_Clusters

MapReduce-Simplified_Data_Processing_on_Large_Clusters中文版（免积分下载）

MapReduce-Simplified Data Processing on Large Clusters.pdf

MapReduce_ Simplified Data Processing on Large Clusters.pdf

MapReduce Simplified Data Processing on Large Clusters.pdf

论文：MapReduce: Simplified Data Processing on Large Clusters

MapReduce: Simplified Data Processing on Large Clusters.pdf

An Architecture for Fast and General Data Processing on Large Clusters

15、MapReduce-simplified-data-processing-on-large-clusters.pdf

learning-pyspark.pdf

互联网后台开发需要掌握什么？

MapReduce.pdf

google 新旧三驾马车MapReduce/Bigtable/GFS和Caffeine/Dremel/Pregel

HaLoop: Efficient Iterative Data Processing on Large Clusters

Google三大论文英文原版

python中map()函数的使用方法示例

python大作业 含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar

仿真电路以及操作方法

【纯干货啊】华为IPD流程管理(完整版).pptx

可编程语言标准IEC61131-3中文版.pdf

OFDM完整仿真过程与教程.zip

最新资源

python大作业含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar