目标
本次lab要求实现一个简化的MapReduce系统。其中，master负责协调和分发任务，以及收集结果；worker负责实际执行map或reduce操作。
设计与实现
本次lab的设计中，master提供如下三个RPC。同时，设计只允许worker向master发送RPC请求，master不会向worker主动发起请求。
GetTask：worker通过调用该RPC来领取一个新任务，如果暂时没有新任务则阻塞，直到有新任务出现或没有更多任务。任务分为三种，map任务、reduce任务以及退出任务。在master中，该RPC通过读取一个channel来获得新任务，同时启动一个超时定时器（根据实验指导，超时时间设为10秒），在定时器超时后其能够将该未完成的新任务重新放回channel中，以便下一次worker调用此RPC时重试。如果该channel被master的其他组件关闭了，该RPC会返回一个“退出任务”，使得worker退出。FinishMapTask：worker通过该RPC来告知master其完成了一个map任务。master收到该RPC后，会记录map任务结果的标识（由于我们在底层使用一个共享的文件系统，这个标识就是文件名），以便分发reduce任务时使用。此外，master还会取消GetTask时设置的定时器，使得这个成功执行完毕的任务不再重试。FinishReduceTask：worker通过该RPC来告知master其完成了一个reduce任务。与上一个RPC类似，master收到该RPC后，会记录reduce任务结果的标识，以便返回给用户。此外，master同样会取消相应的定时器。
master的主goroutine流程如下：
- 根据用户输入的参数，产生若干map任务，并逐一放入channel中，以便worker在
GetTask时领取。 - 等待所有map任务执行完成，收集所有map任务结果的标识。worker在执行map任务的主要部分之后，还会将输出的键值对中间结果根据散列值分成
nReduce个部分，方便作为reduce任务的输入。 - 根据设计，master将会产生
nReduce个reduce任务。对于每一个新reduce任务，记录每个map任务的结果中该reduce任务需要的部分的标识，最后将这个新的reduce任务放入channel中，以便worker在GetTask时领取。 - 等待所有reduce任务执行完成，收集所有reduce任务结果的标识，关闭channel，并将结果返回给用户。
worker的主要工作流程如下：
- 通过
GetTask来获得新任务。 - 执行该任务。注意，该任务可能是“退出任务”。
- 执行完毕后，通过
FinishMapTask以及FinishReduceTask将结果返回给master。 - 回到第1步继续执行。
为了更清晰地展示master与worker交互的过程，下面给出一个可能的事件序列作为例子。例子中，nReduce取3，用户输入的参数为a.txt b.txt c.txt，2个worker。
- master开始执行，产生三个map任务，参数分别为
a.txt、b.txt、c.txt。 - worker 0通过
GetTask取得a.txt任务。 - worker 1通过
GetTask取得b.txt任务。 - worker 0不幸地崩溃了。
- worker 0重新启动，通过
GetTask取得c.txt任务。 - worker 1完成了
b.txt任务，产生了mr-1-0、mr-1-1、mr-1-2。 - worker 1的
GetTask调用阻塞。 - worker 0完成了
c.txt任务，产生了mr-2-0、mr-2-1、mr-2-2。 - worker 0的
GetTask调用阻塞。 a.txt任务的定时器超时，master重新产生该任务。- worker 1通过
GetTask取得a.txt任务。 - worker 1完成了
a.txt任务，产生了mr-0-0、mr-0-1、mr-0-2。 - worker 1的
GetTask调用阻塞。 - master发现三个map任务均已执行完毕，开始产生三个reduce任务0、1、2，参数分别为
mr-0-0 mr-1-0 mr-2-0、mr-0-1 mr-1-1 mr-2-1、mr-0-2 mr-1-2 mr-2-2。 - worker 0通过
GetTask取得0号reduce任务。 - worker 1通过
GetTask取得1号reduce任务。 - worker 0完成了0号reduce任务，产生了
mr-out-0。 - worker 0通过
GetTask取得2号reduce任务。 - worker 1完成了1号reduce任务，产生了
mr-out-1。 - worker 1的
GetTask调用阻塞。 - worker 0完成了2号reduce任务，产生了
mr-out-2。 - worker 0的
GetTask调用阻塞。 - master发现三个reduce任务均已执行完毕，关闭channel，将结果报告给用户。
- worker 0以及worker 1分别收到了“退出任务”，退出。
代码根据规定不予直接公开，可以与我联系，进行讨论。
发表评论