2024谷歌MapReduce：简化⼤型集群上的数据处理.docx

PAGE

PAGE10

MapReduce：简化大型集群上的数据处理

抽象的

MapReduce是一种编程模型及相关实现，用于处理和生成大型

数据集。用户指定一个map函数来处理键/值对生成一组中间键/值

对，以及一个合并所有中间

与同一个中间键关联的值。许多

现实世界的任务可以用这个模型来表达，如下所示

在报纸上。

用这种函数式风格编写的程序会自动并行化，并在大型商用机器集群上执行。运行时系统负责

给定的一天等。大多数这样的计算在概念上是直截了当的。然而，输入数据通常是

很大，计算必须分布在

数百或数千台机器才能完成

合理的时间。如何并行计算、分发数据和处理

故障合谋掩盖了原始的简单计算，需要处理大量复杂的代码

这些问题。

为了应对这种复杂性，我们设计了一种新的

抽象使我们能够表达我们试图执行的简单计算，但隐藏了并行化、容错、数据分布等复杂细节

对输入数据进行分区、在一组机器上调度程序的执行、处理机器故障以及管理所需的机器间

通信。这使得程序员无需任何

具有并行和分布式系统经验，能够轻松利用大型分布式系统的资源。

我们的MapReduce实现运行在大型商用机器集群，具有高度的可扩展性：

典型的MapReduce计算需要在数千台机器上处理数TB的数据。程序员

以及库中的负载?衡。我们的抽象受到Lisp中存在的map和Reduce原语的启发

以及许多其他函数式语言。我们意识到

我们的大部分计算都涉及对输入中的每个逻辑“记录”应用映射操作，以便

计算一组中间键/值对，然后对所有共享的值应用归约操作

相同的密钥，以便适当地组合派生数据。我们使用具有用户指定的映射和减少操作的功能模型，使我们能够轻松地并行化大型计算并使用重新执行

发现该系统易于使用：已实施了数百个MapReduce程序，并在Google集群上执行了上千个MapReduce作业

每天。

简介

在过去五年中，作者和其他许多人谷歌已经实施了数百个特殊用途处理大量原始数据的计算，

例如抓取的文档、Web请求日志等计算各种派生数据，例如倒数

索引，图形结构的各种表示网络文档，页数摘要

每个主机抓取的查询，

作为容错的主要机制。

这项工作的主要贡献是一个简单而强大的接口，实现自动并行化

和大规模计算的分布相结合实现该接口并实现

在大型商用PC集群上实现高性能。第2节描述了基本的编程模型和

给出了几个例子。第3节描述了针对MapReduce接口的实现

我们的基于集群的计算环境。第4节描述了编程模型的几个改进

我们发现很有用。第5节有性能我们对各种实施情况的测量

任务。第6节探讨了MapReduce在

Google包括我们使用它的经验作为基础

重写我们的生产索引系统。第7节讨论了相关工作和未来工作。

2.2类型

编程模型

计算采用一组输入键/值对，并且

尽管前面的伪代码是用

字符串输入和输出，概念上是映射和减少用户提供的函数有关联的

类型：

产生一组输出键/值对。

map

（k1，v1）→列表（k2，v2）

MapReduce库将计算表达为两个

函数：Map和Reduce。

Map由用户编写，它接受一个输入对并生成一组中间键/值对。MapRe?duce库将与同一中间键I相关的所有中间值分组在一起，并将它们传递给

Reduce(k2,list(v2))→list(v2)

即输入的键和值来自不同的

域比输出键和值更重要。此外，

中间键和值与输出键和值来自同一域。

到Reduce函数。

Reduce函数也是由用户编写的，它接受中间密钥I和该密钥的一组值。它

将这些值合并在一起以形成可能更小的值集。通常只有零个或一个输出值

每次Reduce调用都会产生一个中间值。中间值通过迭代器提供给用户的Reduce函数。这使我们能够处理太长的列表值

大到可以装入内存。

我们的C++实现将字符串传递到用户定义的函数并将其留给用户代码

在字符串和适当类型之间进行转换。

2.3更多示例

以下是一些有趣的程序的简单示例

可以很容易地表达为MapReduce计算。

示例

考虑在大量文档中计算每个单词出现次数的问题。用户将编写类似于以下伪代码的代码：

分布式Grep：map函数会在以下情况下发出一行：

匹配提供的模式。reduce函数是一个

身份函数仅将所提供的中间数据复制到输出。

映射（字符串键，字符串值）：

//键：文档名称

//值：文档内容

对于值中的每个单词w：

发射中间体（w，“1”）；

减少（字符串键，迭代器值）：

//关键：一个单词

//值：计数列表

int结果=0;

对于值中的每个v：

结果+=ParseInt(v);

发出（AsStrin