MapReduce 是google提出的一套计算框架。灵感来源于一些函数式语言。Map 指的是对一个数组所有的元素，全都执行一遍Map函数，得到一个解的数组；Reduce指的是给定一个数组，对数组里的元素两两进行Reduce操作，最后得到一个解。现在在python里面就有map reduce的用法。这里google把它应用到分布式系统里来了，用来处理大规模的数据问题。

1. 编程模型

跟传统的map reduce的方式很像。唯一区别就是强制要求map的输入为String, String，前者为文件名；后者为文件里的一行。reduce的输入输出也都是String，因为所有的中间结果都是存在文件上的（GFS）。

1
2
3
4
5
6
7
8
9
10
map(String key, String value):
	for each word in value:
		EmitIntermediate(word, "1")


reduce(String key, Iterator values):
	int result = 0;
	for each v in values:
		result+= ParseInt(v)
	Emit(AsString(result))

一些编程实例

分布式grep: 文件中一行如果匹配，输出；
url访问频率:
倒转网络链接图： Map 中emit (target, source), Reduce中合并成(taget, list(source))
倒排索引: 输出(词， list(文档号))
分布式排序:

2. 实现

这里的实现指的是针对一个分布式环境。

概括

  1. 将数据分成M份；然后创建大量的程序副本。
  2. 有一个master程序和很多worker程序。M个map任务和R个reduce任务。
  3. Map函数生成中间的key/value 对，存在内存中。
  4. key/value pair分为R个区域。周期性地写到本地磁盘；位置会被传给master节点，转发给Reduce Worker。
  5. Reduce worker读取远程的缓存数据，并对key进行排序，使得相同的key会被聚合在一起。
  6. 对于每个唯一的key，作为参数传递给Reduce函数；输出会被追加到所属分区的文件
  7. 所有的任务结束之后，唤醒主程序，结束。

结束之后，会有R个输出文件。因为每个Reduce任务产生一个输出。

容错

worker

master周期性地ping worker。失效地话任务会被安排给其他worker。已完成的Map需要重新执行（因为输出文件在本地），Reduce不用，因为输出是在GFS上的。

Map任务迁移之后，master会通知所有的Reduce任务，读数据时候来源变了。

master

现在的实现是重启整个任务。

备用任务

因为MapReduce需要在中间有一个同步，所以如果有落后者，会卡住整个进程。所以在每个阶段接近结束的时候，如果有空余的资源，会重新执行那些还在中间状态的任务。

3. 技巧

分区函数

可以用来控制key->分区的划分，默认是对key做hash。

顺序保证

保证给定的分区中key/value是按照key的值增量顺序处理的。

Combiner函数

可以在Map的时候，进行Combine，减少传递到Reduce时候的数据量。

输入输出的类型

前面说过Map函数的输入时文件中的一行；实际上可以自己实现一个reader函数，然后提供Map的输入输出。