map reduce | Notion

该工作提供了一个简单而强大的接口用于解决各种并发、容错问题等。

伪代码如下：

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函数会将同一单词的所有计数进行求和。

此外，用户需要编写代码来填充一个MapReduce规范对象，包括输入和输出文件的名称以及可选的调优参数。然后用户调用MapReduce函数，并将规范对象传递给它。

细节的流程如下：

用户程序中的MapReduce库首先将输入文件分割成M个大小通常为16兆字节到64兆字节（MB）的片段（通过可选参数由用户控制）。然后，在一组机器上启动多个程序副本。
其中一个程序副本是特殊的，即主节点（协调器）。其他副本是工作节点，由主节点分配工作。需要分配M个Map任务和R个Reduce任务。主节点选择空闲的工作节点，并为每个节点分配一个Map任务或Reduce任务。
被分配Map任务的工作节点读取相应输入片段的内容。它从输入数据中解析出键/值对，并将每对传递给用户定义的Map函数。Map函数产生的中间键/值对被缓存在内存中。
定期将缓冲的键/值对写入本地磁盘，并通过分区函数将其分为R个区域。这些缓冲的键/值对在本地磁盘上的位置被传回给主节点，主节点负责将这些位置转发给Reduce工作节点。
当Reduce工作节点收到主节点关于这些位置的通知时，它使用远程过程调用从Map工作节点的本地磁盘中读取缓冲数据。当Reduce工作节点读取完所有的中间数据后，它按中间键进行排序，以便将相同键的所有出现组合在一起。排序是必要的，因为通常许多不同的键映射到同一个Reduce任务。如果中间数据的量过大无法放入内存，则使用外部排序。
Reduce工作节点遍历排序后的中间数据，对于每个唯一的中间键，它将键和相应的中间值集合传递给用户的Reduce函数。Reduce函数的输出被追加到该Reduce分区的最终输出文件中。
当所有的Map任务和Reduce任务都完成后，主节点唤醒用户程序。此时，用户程序中的MapReduce调用返回到用户代码中。

主节点维护了几个数据结构。对于每个Map任务和Reduce任务，它存储任务的状态（空闲、进行中或已完成）以及工作机器的标识（对于非空闲任务）。

主节点是中间文件区域的位置从Map任务传播到Reduce任务的通道。因此，对于每个已完成的Map任务，主节点存储了该Map任务产生的R个中间文件区域的位置和大小。随着Map任务的完成，位置和大小信息的更新将逐步传递给正在进行Reduce任务的工作机器。

问题

Worker故障

有三种情况： 1、主节点定期向每个工作机器发送ping请求。如果在一定时间内没有收到工作机器的响应，主节点将标记该工作机器为故障。由该工作机器完成的任何Map任务都将重置回初始空闲状态，因此可以在其他工作机器上进行调度。类似地，正在故障的工作机器上进行的任何Map任务或Reduce任务也将重置为空闲状态，并且可以重新进行调度。

2、已完成的Map任务需要重新执行，因为它们的输出存储在故障机器的本地磁盘上，因此无法访问。已完成的Reduce任务不需要重新执行，因为它们的输出存储在全局文件系统中。