MIT6.824 lab1 mapreduce 项目记录

lab1 mapreduce任务描述

实现一个分布式 MapReduce，由两个程序组成：master 和 worker。只有一个master进程，以及一个或多个并行执行的worker进程。在真实的系统中，worker将在一堆不同的机器上运行，但在本实验中，我们在一台机器上运行它们。Workers 将通过 RPC 与 Master 对话。每个worker进程都会向master进程请求一项任务，从一个或多个文件读取任务的输入，执行任务，并将任务的输出写入一个或多个文件。

MapReduce介绍

MapReduce是论文中提出的一种大数据计算框架，谷歌根据他们的计算业务，将大数据计算抽象成一系列Map操作和Reduce操作，基于MapReduce任务调度集群，数据分析人员只需要编写基本的Map函数和Reduce函数即可在大规模集群上运行分布式计算，无需考虑具体的分布式调度过程。

本实验是编写一个MapReduce分布式任务调度服务，整体为Master/Worker架构。首先Master启动，根据输入文件列表拆分为X个Map任务和Y个Reduce任务。Worker启动后定时通过rpc向Master发生心跳消息，Master初次收到新Worker消息会创建并返回WorkerID，并将Worker加入到空闲Worker队列中。Worker节点是支持动态扩容的。

任务执行阶段

对于Map任务，Master不断从空闲Worker队列中取出Worker节点，并当下一次心跳时将Map的输入文件位置。

Reduce任务数量等信息发生给Worker，Worker收到任务并开始执行。

Map函数的输入是文件的每一行，输出是kv列表，Worker对输出结果进行shuffle，利用hash函数运算k并对Reduece任务的数量取模，结果追加到X_Y.tmp中间文件中。当前Worker的Map任务执行完成后，会通过心跳将输出文件列表发送给master。Master将此Worker再放入空闲队列等待下次调度。当所有Map任务执行完成，Master将所有中间文件夹根据Reduce任务号进行分组，再把Reduce任务分配给Worker，Worker收到文件列表会先全部读取，排序，将相同key和value的列表传入Reduce函数，reduce结果追加到以Reduce任务号结尾结果文件中。并将结果返回Master，Master确认所有Reduce任务结束，整个任务执行完毕。