MIT 6.824-Lab1
本文最后更新于 2024年6月7日 下午
前言
早在保研时,对分布式感兴趣的我想要涉猎一些这个领域的知识,于是在网络上搜寻相关的学习资料,就发现了很多前辈都推荐学习者阅读一下谷歌的三大论文——MapReduce、GFS、BigTable,此外还推荐了一个课程——MIT 6.824,这是一个关于分布式系统的课程,授课的教师是大名鼎鼎的蠕虫病毒的发明者——Robert Morris,听这样的大牛讲课本身就是一种享受,并且在听了两节课之后,觉得老师讲的确实透彻且深刻,并且在如今2020年,老师上课时大部分的讲解都是使用板书完成的,这点显得尤为难得,以上这些让我这听惯了国内PPT课堂的学生耳目一新。
实验
在听了两节课之后,我开始动手进行本课的第一个实验——实现一个简单的MapReduce系统。由于我事先阅读过MapReduce论文,加之第一个实验较为简单,因此我并没有倒在lab1面前,但前前后后还是花了中秋节的三天时间才搞定这个实验,并通过了全部8个测试点。
简单描述一下该实验的要求:
- 实验中要求实现的系统包含两部分:
worker
和coordinator
,worker
负责完成任务,coordinator
负责将任务分配给worker
。会存在多个worker
同时工作来模拟并行,但coordinator
只存在一个。通常来说分布式系统中的每个worker
应该存在于多台主机之上,并通过网络RPC
进行通信,但由于是实验,因此没有多机进行模拟,所以将worker
们都运行在一台主机上,依然通过RPC
通信,但使用的是UNIX SOCK
的方式。 - 系统的输入是一系列文件,仿照
Map-Reduce
论文中的思路,进行单词统计等一系列操作。实验需要通过的功能点主要有以下8个测试点:- word count(单词计数)
- indexer(单词来自文件统计)
- map parallelism (map 任务并行测试)
- reduce parallelism(reduce 任务并行测试)
- job count (任务计数)
- early exit (是否有
worker
在全部任务完成前退出) - crash (
worker
崩溃后任务可以正常完成)
- 详细要求见网页。
文件目录
-
main
:主文件夹-
mrcoordinator.go
:coordinator 的启动文件 -
mrworker.go
:worker的启动文件 -
mrsequential.go
:实验串行模拟版本注:以上文件需要在不同的终端启动
-
test-mr.sh
:测试实验是否通过的shell
脚本
-
-
mr
:worker 和 coordinator 具体实现的文件夹coordinator.go
worker.go
rpc.go
:worker 和 coordinator 通信的实现
-
mrapps
:每对Map-Reduce操作的具体实现文件夹- …
尝试
version 1
一开始我抱着有些畏惧的心态去完成这个实验,目标是实现单词计数的功能,由于整个系统的输入是一系列文件,所以我简单地使worker
向coordinator
获取文件的列表,然后为每一文件单独开启一个协程用于map
任务,每个协程将其结果写入中间文件,由于系统规定了reduce
任务的数量,因此在map
任务结束后,启用规定数量的协程去执行reduce
任务即可。
使用这个方式,通过了单词计数的测试没有问题,但是在indexer
的测试却行不通了,由于系统是通过test-mr.sh
进行测试的,因此我开始浏览shell
脚本的内容。发现了在测试脚本中,会启动多个worker
来完成map
任务,也就是说是多个worker
共同完成任务,这与我一开始认为的一个worker
通过开启多个协程完成任务的想法相悖,所以代码需要进行修改。
(1个worker
同时启动N
个任务)
version 2
从上文,我明白了应该是多个进程共同完成任务。因此将实现思路改为,每个worker
通过RPC
向coordinator
获取任务(文件),获取到后开启协程去完成每个任务。 通过这个改动,我通过了indexer
测试。但是在parallelism
测试中却Fail
了。这意味着程序的实现还是错误的。
(m
个worker
同时启动N/m
个任务)
version 3
接着我分析了parallelism
测试中的测试原则,测试原则为worker
在map
阶段通过创建一个文件名为mr-worker
+PID
的文件,在map
结束后删除该文件,通过统计存在几个特定文件名的数量,来判断同时运行的worker
数量。由于在version 2
版本中,一个worker
启动了多个协程来执行map
操作,每个协程在执行时会同时操作一个文件,所以会出现重复删除一个文件的情况,导致程序崩溃。
因此,需要将一个worker
启动多个协程的方式改掉,改为每个worker
每次只执行一个map
任务。这次可以通过测试了。
version 4
最后难住我的测试点是崩溃测试,在worker
崩溃后系统能否依然正确执行,得出正确的结果,一个完备的系统设计无疑是应该具备容错的能力的。
worker
执行前会向coordinator
获取相应的任务,获取任务后,若在执行过程中发生崩溃,那意味着该任务没有被成功执行,需要coordinator
检测出失败的任务,然后将任务重新分配给worker
。
这里我采用了在coordinator
中引入协程同时记录任务执行状态的记录的方式,在coordinator
将任务分配给worker
后,启动协程进行倒计时,若在规定的时间内任务并没有执行完成,那么即认为任务失败,coordinator
会重新分配任务。
逻辑
worker
1 |
|
coordinator
1 |
|
rpc
1 |
|