Mit6.5840 Lab1笔记 | NotionNext BLOG

type

status

date

slug

summary

算法

MapReduce假设有一些输入，这些输入被分割成大量的不同的文件或者数据块

在这个分布式系统中，包含一个Map函数和一个Reduce函数

Map

一个Map函数会为上面被分割成的文件或者数据块进行处理，一个map只处理一个数据块

输入：拆分的文件或者数据块
输出：key-value组成的列表

这些输出又被叫做中间输出

emit函数

由MapReduce框架提供
效果是在worker服务器磁盘中创建文件，文件中包含Map函数的输出

Reduce函数

Reduce函数：一个Reduce函数会收集每个机器上的Map函数的输出

注意是按照key进行收集，遍历每一个机器收集相同key的中间输出
MapReduce框架会为每一个key调用一次Reduce函数
参数

key：一个Map中间输出的key
value：Map输出中相同key对应的value列表

也有emit函数，但是功能是将输出写到共享文件服务中

代码实现

代码实现方面，参考了https://hezephyr.github.io/posts/05.mit-6.58406.824-lab1mapreduce-设计实现的在taskInfo方面的实现，这个师傅的实现架构非常清晰易懂，便于学习

本人的github仓库：https://github.com/thanyi/mit6.5840

框架分析

Map和Reduce

首先，在Lab1提供的代码中，已经实现了Map函数和Reduce函数，我们需要的是构造底层的框架，可以让这两个函数在分布式环境中可以运行。（这里假设您已经看过MapReduce论文，知道了它相关的原理知识）

这里列出Map和Reduce函数（位于mrapps/wc.go ）

可以看出，Lab1的Map函数和Reduce函数的逻辑分别是

Map函数：输入一个文件名和内容，将其中的每一个单词构建一个{<word>:”1”} 的结构

Reduce函数：输入Key和这个key对应的”1“的列表，输出其列表长度

文件架构

Lab1中能修改的文件包括mr/coordinator.go , mr/rpc.go 以及mr/worker.go

这三个文件分别代表Worker端，Master端，还有对于RPC的协议的定义

Master端的注册函数：

同时在main/mrworker.go，main/mrcoordinator.go 文件中包含了Worker和Master（代码中叫Coordinator）创建初始化的逻辑

mrworker.go

main/mrcoordinator.go

当我们每次运行测试时，都需要进行

RPC端

定义通信时候的协议

Master端

首先需要定义Coordinator 这个结构体，这个结构体应该包括

其中最重要的是MapTaskInfos和 ReduceTaskInfos这两个的TaskInfo结构体切片，Coordinator通过利用这两个切片将任务赋予不同的worker，并且还能进行记录

以下是TaskInfo信息

同时因为是维护的Task列表，所以当worker每次请求的时候，逻辑都是遍历任务列表查看状态，并赋予worker任务，同时注意加锁。

当Worker的任务结束，会告诉Master端任务完成

Worker端

Worker端运行逻辑分为几个步骤：

向Master申请任务

获取任务，查看任务类型为Map任务还是Reduce任务，亦或是Wait任务和Done任务

若是Done任务，代表Master端全部任务处理完成，则Worker执行Exit(0)

根据任务类型进行Map逻辑或是Reduce逻辑

结束任务，向Master报告任务完成

同时是以循环的方式进行上述步骤

算法

Map