MIT6.824-1

Heeler-Deer

发布于 2023-03-10 06:39:36

93400

代码可运行

文章被收录于专栏：HD-学习笔记HD-学习笔记

运行总次数：0

代码可运行

阅读须知

MIT 6.824的实验难度较大，且据我推测是每年都会有改动。学习6.824的正确姿势应该是先去观看公开课，找到官方的课程时间安排表，里面附带学习资料。即在阅读论文后上课、上完公开课后在做实验。

实验的具体完成时间可以参看课程时间安排表的due

如果你不会go，强烈建议在Go学习go,语法简单，很快就能学会的。

环境搭建

推荐视频：b站

2020课程时间安排表： MIT

实验代码仓库：

git clone git://g.csail.mit.edu/6.824-golabs-2020 6.824

实验采用的开发语言为go，建议在linux下开发，同时建议使用goland这个IDE，go的环境手动配置还是有点麻烦的

当然，我选择在万能的vscode上开发——个人认为vscode的Go插件做的还是很不错的。

vscode配置go建议参考：知乎

注意go升级环境时需要将旧版本全部删除在覆盖到原先的路径下。新旧版本同时存在容易出错。

下载实验代码后目录结构如下：

Map and Reduce

该实验要求我们实现一个统计单词数量的系统，该系统具有 一个master,多个reduce。具体要求可查看lab1的实验指导要求

其中，map作用为统计每个文件的各自单词数量，reduce则将map的结果整合起来，如下图：

我们首先按照指导书所示，测试环境能否运行代码里已有的文件：

#生成wc.so文件，此文件用于统计单词数量，后续也需要wc.so
go build -buildmode=plugin ../mrapps/wc.go

#删除mr-out开头的文件
rm mr-out*

#以连续的map_reduce方式统计pg*开头的文本文件的单词，此次运行生成的文件即后续测试lab1是否正确的标准
go run mrsequential.go wc.so pg*.txt

#查看生成的文件
more mr-out-0

如果一切正常，就可以看到：

之后，指导书讲解了检验我们代码运行正确与否的方式。

./src/main/mrmaster.go会调用我们实现的./src/mr/master.go文件

./src/main/mrworker.go则会调用我们实现的./src/mr/worker.go文件

我们的代码编写工作都在./src/mr里面

显然，实验一的重点在于如何设计master,worker,使得master在调度多个worker时能够无误的分配map and reduce任务。

这对于master的要求为：

两个分别对应map,reduce的结构体，存储执行该任务的文件id、worker的id。考虑到任务执行需要设置一个超时时间，还需要记录该任务对应的开始时间
一个从map转换到reduce的函数
map以及reduce对应的用于分配任务的函数，使worker能够参与任务的函数
考虑到系统稳健性，需要一个删除超时任务的函数

对于worker,需要考虑以下几点：

分别对应于map,reduce的请求任务、参与任务、执行任务函数
写入文件的函数

考虑到master和worker通过rpc通信，还需要满足对应于rpc的调用函数

Master

master需要存储map以及reduce任务，我们需要一个 一一对应的数据结构（存储fileid以及总数），不仅如此，还要存储该fileid对应的任务是否完成，即：

type MAPSET struct {
	mapbool map[interface{}]bool   //fileid对应的bool的T/F表示该fileid是否完成
	count   int                    //总数
}

上述结构体只能用于存储已完成的map/reduce任务信息，因为对于未完成的任务，出于稳健性考虑，我们需要一个满足线性出入的数据结构——stack,queue或者链表。分配任务时，必须加锁，虽然将锁加在数据结构里容易导致外部代码未加锁时程序死锁（讲师原话——程序员必须在需要用到锁的地方有意识的加锁而不是依赖数据结构的锁），但考虑到这是我们自己实现的数据结构，我们可以直接将锁加入里面。

//伪码
type STACK struct{
    mutex *Mutex
    stack *Stack
}

那么对于master,我们的数据结构将被设计为：

//伪码
type Master struct{
    filenames []string //所有文件
    cur_worker_id //当前worker的id
    map_done bool //map完成与否
    reduce_done  bool //reduce完成与否
    unsolved_map_tasks *STACK
    solved_map_task *MAPSET
    unsolved_reduce_tasks *STACK
    solved_reduce_task *MAPSET
    mutex *Mutex //锁
    map_task_begin_second int  //开始时间
    map_task_file_id    int    //文件id
    map_task_worker_id   int  //worker id
    reduce_task_begin_second int
    reduce_task_file_id    int
    reduce_task_worker_id   int
}

以map为例，我们着重介绍分配任务、加入任务以及从map转换到reduce这三个函数

考虑分配map任务，我们需要考虑以下几点：

任务已经完成，则发送mapdone的消息同时释放锁（有请求则需要先加锁在判断）
任务刚好完成，则调用前文第二点提到的map到reduce转换函数，释放锁
可以分配任务，记录数据，分配任务

对于加入map任务，则需要考虑任务是否超时，是否能够分配

对于从map到reduce的转换函数，我们只需要将fileid加入unsolved_reduce_task对应的结构体即可

Worker

对于worker,我们需要一个结构体存储其id,是否完成、进行map/reduce,对应于map/reduce的函数，同时，对于map/reduce,我们需要各自的请求、参与、执行函数，此处不再细讲。

Debug&Test

由于该实验内容较多，因此我建议在master,worker的每一个函数的每一个分支内部加入输出语句，便于定位错误。

如log.Printf("all map tasks Done,do reduce tasks")，同时，在调用测试脚本之前，先在src/main目录下，执行以下语句：

#将master的输出写入master.txt文件
go run mrmaster.go pg-*.txt 1&>master.txt

#生成wc.so,每次都要执行
go build -buildmode=plugin ../mrapps/wc.go

#执行worker,将输出写入worker.txt文件
go run mrworker.go wc.so 1&> worker.txt