用户自定义的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)并输出为