超大集群的简单数据处理

《超大集群的简单数据处理》由会员分享，可在线阅读，更多相关《超大集群的简单数据处理（19页珍藏版）》请在金锄头文库上搜索。

1、 第 1 页超大集群的简单数据处理收收件件人人：发发件件人人：崮山路上走9 遍抄抄送送：日日期期：2005-08-05关关于于：MapReduce: Simplified Data Processing on Large ClustersJeffrey Dean Sanjay G , Google , Inc.摘摘要要MapReduce 是一个编程模式，它是与处理 /产生海量数据集的实现相关。 用户指定一个map 函数， 通过这个map 函数处理key/value（键/值）对，并且产生一系列的中间key/value 对，并且使用 reduce 函数来合并所有的 具有相同key 值的中间键值对

2、中的 值部分。现实生活中的很多任务的实现 都是基于这个模式的，正如本文稍后会讲述的那样。使用这样的函数形式实现的程序可以自动分布到一个由普通机器组成的超大几群上并发执行。run- time 系统会解决输入数据的分布细节，跨越机器集群的程序执行调度，处理机器的失效，并且管 理机器之间的通讯请求。 这样的模式允许程序员可以 不需要有什么并发处理或者分布式系统的经验， 就可以处理超大的分布式系统得资源。我们的MapReduce 系统的实现运行在一个 由普通机器组成的大型集群上， 并且有着很高的扩展性： 一个典型的MapReduce 计算处理通常分布到上千台机器上来处理上 TB 的数据。程序员会发现这

3、 样的系统很容易使用： 已经开发出来了上百个MapReduce 程序，并且每天在Google 的集群上有 上千个MapReduce job 正在执行。1 介介绍绍在过去的5 年内，Google 的创造者和其他人实现了上百个用于特别计算目的的程序来出来海量的 原始数据，比如蠕虫文档， web 请求log，等等，用于计算出不同的数据，比如降序索引，不同的 图示展示的web 文档，蠕虫采集的每个host 的page 数量摘要，给定日期内最常用的查询等等。 绝 大部分计算都是概念上很简洁的。不过，输入的数据通常是非常巨大的，并且为了能在合理时间内 执行完毕，其上的计算必须分布到上百个或者上千个计算机上

4、去执行 。如何并发计算，如何分布数 据，如何处理失败等等相关问题合并在一起就会导致原本简单的计算掩埋在为了解决这些问题而 引入的很复杂的代码中。因为这种复杂度，我们设计了一种新的东西来让我们能够 方便处理这样的简单计算。这些简单计算 原本很简单，但是由于考虑到并发处理细节，容错细节，以及数据分布细节，负载均衡等等细节 问题，而导致代码非常复杂。 所以我们抽象这些公共的细节到一个lib 中。这种抽象是源自Lisp 以 及其他很多面向功能的语言的map 和reduce 概念。我们认识到大部分 操作都和map 操作相关，这 些map 操作都是运算在输入记录的每个逻辑”record”上，并且map 操

5、作为了产生一组中间的MapReduce 第 2 页key/value 键值对,并且接着在所有相同key 的中间结果上执行reduce 操作，这样就可以 合并适当的 数据。我们得函数模式是使 用用户定义的map 和reduce 操作，这样可以让我们并发执行大规模的 运算，并且使用重新执行的方式作为容错的优先机制。MapReduce 的主要贡献在于提供了一个简单强大的接口，通过这个接口，可以把大尺度的计算自 动的并发和分布执行。使用这个接口，可以通过普通 PC 的巨大集群，来达到极高的性能。第二节讲述了基本的编程模式，并且给出了一些例子。第三节讲述了一个面向我们基于集群的计 算环境的MapRedu

6、ce 的实现。第四节讲述了一些我们建议的精巧编程模式。 第五节讲述了在不同 任务下我们的MapReduce 实现的性能比较。第六节讲述了在Google 中的MapReduce 应用以及 尝试重写了我们产品的索引系统。第七节讲述了相关工作和未来的工作。2 编编程程模模式式我们的运算处理一组输入的（ input）键值对（key/valuepairs）,并且产生一组输出的（ output）键值 对。MapReduce 函数库德用户用两个函数来表达这样的计算： Map 和Reduce。Map 函数，是用户自定义的的函数，处理输入的键值对，并且产生一组中间的（intermediate）键 值对。MapR

7、educe 函数库稽核所有相同的中间键值键I 的值，并且发送给Reduce 函数进行处理。Reduce 函数同样也是用户提供的，它处理中间键值 I，以及这个中间键值相关的值集合。 这个函数 合并这些值，最后形成一个相对较小的值集合。 通常一个单次Reduce 执行会产生0 个或者1 个输 出值。提供给Reduce 函数的中间值是通过一个iterator 来提供的。这就让我们可以处理超过内存 容量的值列表。2.1 例例子子我们考虑这样一个例子，在很大的文档集合中通机每一个单词出现的次数。我们写出类似如下的伪 代码：map(String key, String value):/ key: docu

8、ment name/ value: document contentsfor each word w in value:EmitIntermediate(w, “1“);reduce(String key, Iterator values):/ key: a word/ values: a list of countsint result = 0;for each v in values:result += ParseInt(v);Emit(AsString(result);map 函数检查每一个单词，并且对每一个单词增加 1 到其对应的计数器（在这个例子里就是 1）. reduce 函数把特

9、定单词的所有出现的 次数进行合并。此外，我们还要写代码来 对mapreduce specification 对象进行赋值，设定输入和输出的文件名， 以 及设定一些参数。 接着我们调用MapReduce 函数，把这个对象作为参数调用过去。 我们把 MapReduce 函数库（C+函数库）和我们的程序链接在一起。附件 1 有完整的这个例子的代码。 第 3 页2.2 类类型型即使上边的例子是用字符串作为输入和输入出的，从概念上讲， 使用者提供的map 和reduce 函数 有着如下相关类型：map (k1,v1) list(k2,v2)reduce (k2,list(v2) list(v2)也就是，

10、输入的键和值和输出的键值是属于不同的域的 。进一步说，中间的键值是和 输出的键值属 于相同的域的。 （比如map 的输出，就是作为reduce 的输入）。我们的C+实现上，把字符串作为用户定义函数的输入和输出， 由用户代码来自己识别字符串到合 适的类型。2.3 其其他他例例子子这里有一些简单有趣的例子，都可以简单的通过 MapReduce 计算模型来展示：分分布布式式Grep：如果map 函数检查输入行，满足条件的时候， map 函数就把本行输出。 reduce 函数就是一个直通函数，简单的把中间数据输出就可以了。URL 访访问问频频率率统统计计：map 函数处理webpag 请求和应答（UR

11、L，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)表

12、达。map 函数计算每一个输入文档（主机名 字是从文档的URL 取出的）的关键词向量， 然后输出（hostname,关键词向量(Term-Vector)）。 reduce 函数处理所有相同host 的所有文档关键词向量。去掉不常用的关键词，并且输出最终的 (hostname，关键词向量)对。逆逆序序索索引引：map 函数分析每一个文档，并且产生一个序列（ word，documentID）组。 reduce 函数处理指定word 的所有的序列组，并且对相关的document ID 进行排序，输出一个 (word,list(document ID)组。所有的输出组，组成一个简单的逆序索引。通过这种

13、方法可以很容易 保持关键词在文档库中的位置。分分布布式式排排序序：map 函数从每条记录中抽取关键字，并且产生 (key,record)对。reduce 函 数原样输出所有的关键字对。 这个算法是与4.1 节描述的分布式处理相关的，并且排序是在 4.2 节 描述的。3 实实现现MapReduce 接口可以有很多种不同的实现。 应当根据不同的环境选择不同的实现。比如，一个实 现可以适用于小型的共享内存的机器，另一个实现可能是基于大型 NUMA 多处理器系统，还可能 有为大规模计算机集群的实现。本届描述了Google 广泛使用的计算环境：用交换机网络 4连接的，由普通PC 构成的超大集群。 在我们

14、的环境里：（1）每个节点通常是双x86 处理器，运行Linux,每台机器2-4GB 内存。 第 4 页（2）使用的网络设备都是常用的。一般在节点上使用的是 100M/或者千M 网络，一般情况下都 用不到一半的网络带宽。（3）一个cluster 中常常有成百上千台机器，所以，机器故障是家常便饭。（4）存储时使用的便宜的IDE 硬盘，直接放在每一个机器上。并且有一个分布式的文件系统来 管理这些分布在各个机器上的硬盘。 文件系统通过复制的方法来在不可靠的硬件上保证可 用性和可靠性。（5）用户向调度系统提交请求。每一个请求都包含一组任务，映射到这个计算机 cluster 里的一 组机器上执行。3.1

15、执执行行概概览览Map 操作通过把输入数据进行分区（ partition）（比如分为M 块），就可以分布到不同的机器上执 行了。输入块的拆成多块，可以并行在不同机器上执行。 Reduce 操作是通过对中间产生的key 的 分布来进行分布的，中间产生的key 可以根据某种分区函数进行分布（比如 hash(key) mod R）,分 布成为R 块。分区（R）的数量和分区函数都是由用户指定的。图1 是我们实现的MapReduce 操作的整体数据流。当用户程序调用MapReduce 函数，就会引起 如下的操作（图一中的数字标示和下表的数字标示相同）。1 用户程序中的MapReduce 函数库首先把输入

16、文件分成M 块，每块大概16M 到64M（可以通 过参数决定）。接着在cluster 的机器上执行处理程序。 第 5 页2 这些分排的执行程序中有一个程序比较特别，它是主控程序 master。剩下的执行程序都是作为 master 分排工作的worker。总共有M 个map 任务和R 个reduce 任务需要分排。 master 选择 空闲的worker 并且分配这些map 任务或者reduce 任务3 一个分配了map 任务的worker 读取并处理相关的输入小块。他处理输入的数据，并且将分析 出的key/value 对传递给用户定义的map 函数。map 函数产生的中间结果key/value 对暂时缓 冲到内存。4 这些缓冲到内存的中间结果将被定时刷写到本地硬盘， 这些数据通过分区函数分成R 个区。这 些中间结果在本地硬盘的位置信息将被发送回 master，然后这个master 负责把这些位置信息 传送给reduce 的worker。