分布式的 Grep(UNIX 工具程序, 可做文件内的字符串查找):如果输入行匹
配给定的样式,map 函数就输出这一行.reduce 函数就是把中间数据复制到输
出.
计算 URL 访问频率:map 函数处理 web 页面请求的记录,输出
(URL,1).reduce 函数把相同 URL 的 value 都加起来,产生一个(URL,记录总
数)的对.
倒转网络链接图:map 函数为每个链接输出(目标,源)对,一个 URL 叫做目标,
包含这个 URL 的页面叫做源.reduce 函数根据给定的相关目标 URLs 连接所有
的源 URLs 形成一个列表,产生(目标,源列表)对.
每个主机的术语向量:一个术语向量用一个(词,频 率)列表来概述出现在一个
文档或一个文档集中的最重要的一些词.map 函数为每一个输入文档产生一个
(主机名,术语向量)对(主机名来自文档的 URL).reduce 函数接收给定主机的所
有文档的术语向量.它把这些术语向量加在一起,丢弃低频的术语,然后产生一个
最终的(主机名,术语向量)对.
倒排索引:map 函数分析每个文档,然后产生一个(词,文档号)对的序
列.reduce 函数接受一个给定词的所有对,排序相应的文档 IDs,并且产生一个
(词,文档 ID 列表)对.所有的输出对集形成一个简单的倒排索引.它可以简单的增
加跟踪词位置的计算.
分布式排序:map 函数从每个记录提取 key,并且产生一个(key,record)
对.reduce 函数不改变任何的对.这个计算依赖分割工具(在 4.1 描述)和排序属
性(在 4.2 描述).
3 实现
MapReduce 接口可能有许多不同的实现.根据环境进行正确的选择.例如,
一个实现对一个共享内存较小的机器是合适的,另外的适合一个大 NUMA 的多
处理器的机器,而有的适合一个更大的网络机器的集合.
这部分描述一个在 Google 广泛使用的计算环境的实现:用交换机连接的普
通 PC 机的大机群.我们的环境是:
1.Linux 操作系统,双处理器,2-4GB 内存的机器.
2.普通的网络硬件,每个机器的带宽或者是百兆或者千兆,但是平均小于全部
带宽的一半.
3.因为一个机群包含成百上千的机器,所有机器会经常出现问题.
4.存储用直接连到每个机器上的廉价 IDE 硬盘.一个从内部文件系统发展起
来的分布式文件系统被用来管理存储在这些磁盘上的数据.文件系统用复制的方
式在不可靠的硬件上来保证可靠性和有效性.
5.用户提交工作给调度系统.每个工作包含一个任务集,每个工作被调度者映
射到机群中一个可用的机器集上.
3.1 执行预览
通过自动分割输入数据成一个有 M 个 split 的集,map 调用被分布到多台机
器上.输 入的 split 能够在不同的机器上被并行处理.通过用分割函数分割中间
key,来形成 R 个片(例如,hash(key) mod R),reduce 调用被分布到多台机器
上.分割数量(R)和分割函数由用户来指定.