MapReduce Simplified Data Processing on Large Clusters(翻译版)

）键值

对。

MapReduce

函数库稽核所有相同的中间键值键

I

的值，并且发送给

Reduce

函数进行处理。

Reduce

函数同样也是用户提供的，它处理中间键值

I

，以及这个中间键值相关的值集合。这个函数

合并 这些值，

最后形成一个相对较小的值集合。

通常一个单次

Reduce

执行会产生

0

< br>个或者

1

个输出

值。提供给

Reduce

函数的中间值是通过一个

it erator

来提供的。这就让我们可以处理超过内存容量

的值 列表。

2.1

例子

我们 考虑这样一个例子，

在很大的文档集合中通机每一个单词出现的次数。

< br>我们写出类似如下的伪代

码：

map(String key, String value):

reduce(String key, I

terator values):

map

函 数检查每一个单词，

并且对每一个单词增加

1

< br>到其对应的计数器

（在这个例子里就是

’

1

’

）

.reduce

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

此外，我们还要写代码来对

mapreduce specif ication

对象进行赋值，设定输入和输出的文件名，以

及 设定一些参数。接着我们调用

MapReduce

函数，把这个 对象作为参数调用过去。我们把

MapReduce

函数库（< /p>

C++

函数库）和我们的程序链接在一起。附件

< br>1

有完整的这个例子的代码。

// key: a word

// values: a list of counts

int result = 0;

for each v in values:

result += ParseInt(v);

// key: document name

// value: document contents

for each word w in value:

EmitIntermediate(w,

Emit(AsString(result));

?

第

2

页

2.2

类型

即使上边的例子是用字符串作为输入和输入出的，

map

和

reduce

函数有

着如下相关类型：

map (k1,v1)

?

list(k2,v2)

?

list(v2)

reduce (k2,list(v2))

也 就是，

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

中间的键值是和输出的键值属于

相同的域的。（比如

map< /p>

的输出，就是作为

reduce

的输入） 。

我们的

C++

实现上，

把字符串作为用户定义函数的输入和输出，

由用户 代码来自己识别字符串到合适

的类型。

2.3

其他例子

这里有一些简单有趣的例子，都可以简单的通过

MapReduce

计算模型来展示：

分布式

Gre p

：

如果

m ap

函数检查输入行，满足条件的时候，

map

函数就把本行输出。

reduce

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

URL

访问频率统计：

map

函数处理

webpag

请求和应答

（

URL

，

1

）

的

log

。

Reduce

函数把所有

相同的

URL

的值合并，并且输出一个成对的（

URL

，总个数）。

逆向

Web-Link

图：

map

函数输出所有包含指向

target URL

的

source

网页，

用

（

target,source

）

这样的结构 对输出。

Reduce

函数局和所有关联相同

< br>target URL

的

source

< br>列表，并且输出一个

(target,list(source))

这样的结构。

主机关键向量指标（

Term-Vector per Hosts

）

:

关键词向量指标简而 言之就是在一个文档或者一

组文档中的重点次出现的频率，用

( word,frequency)

表达。

map

函数计算每一个输入文档（主机名字

是从文档的

URL

取出的）

的关键词向量，

然后输出

（

hostname,

关键词向量