首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
AI面试、笔试、校招、雇品
HR免费试用AI面试
最新面试提效必备
登录
/
注册
慢慢来吧啦啦啦
门头沟学院 C++
关注
已关注
取消关注
@努力学习的阿新:
MIT 6.824(2020) Lab1文档翻译
前言 大家好,这里是阿新。 MIT 6.824 是麻省理工大学开设的一门关于分布式系统的明星课程,共包含四个配套实验,实验的含金量很高,十分适合作为校招生的项目经历,在文章《2022 双非应届 CS 硕士校招上岸字节跳动(校招总结)》中,我也将其推荐给了各位读者。但由于课程是全英的,实验说明也是全英的,实验过程中还需要阅读相关的英文文献,很多同学(包括曾经的笔者)受困于英语,对其望而却步。因此,笔者决定开启系列文章:MIT 6.824(Spring 2020)实验文档翻译。来尝试为大家翻译实验的说明文档和相关论文的关键部分,同步更新的还有系列带做文章,以期能够帮助各位读者顺利完成该课程实验。 本文对 MIT 6.824 Lab 1:MapReduce 的说明文档进行了全文翻译。需要注意的是文中的 job 和 task,其中,job 是指整个 MapReduce 计算,表示的是任务整体,而 task 则是指一次 Map/Reduce 调用,表示的是任务局部,一个完整的 MapReduce job 由一些 Map task 和 Reduce task 组成,笔者无法找到两个中文词汇来很好的描述两者之间的关系,因此并未翻译。同时,由于笔者水平有限,如有翻译不恰当的地方还请各位批评指正。 以下为原文翻译。 作者:MIT 6.824 Staff | 译者:阿新 依据 CC BY 3.0 US 许可证进行授权 许可证链接:https://creativecommons.org/licenses/by/3.0/us/deed.zh 原文链接:http://nil.csail.mit.edu/6.824/2020/labs/lab-mr.html 引言 本实验的目标是引导您构建一个 MapReduce 系统,您需要实现两个程序:worker 和 master。其中 worker 进程负责处理文件读写操作以及调用 Map/Reduce 函数处理 Task。而 master 进程则负责为 worker 进程分配 Task 并处理崩溃的 worker 进程。您构建的系统与MapReduce 论文中所描述的系统类似。 协作政策 除了我们提供给您的代码外,您必须独立完成实验要求的代码。实现过程中杜绝参考其他同学和前几年课程实验的解决方案。允许您与同学讨论,但不允许您抄袭他们的代码。之所以设立这条规则,是因为我们认为只有独立完成实验,您的能力才会得到最大的提升。 请不要公布您的代码,也不要让它被选修 6.824 的学生通过某种方式获取到。github.com中的仓库权限默认是公开的,除非您将仓库权限设为私有,否则请勿用其存储实验代码。保存代码可以使用MIT 的 Github,但请确保您创建的是私有仓库。 软件 本实验(以及 6.824 的其他实验)使用的编程语言是Go语言,如果您不熟悉 Go 语言,其官方网站上有很多教程供您学习。我们将使用 1.13 版本的 Go 语言来评判您的代码,因此您也应该使用这一版本(译者注:笔者所用的 Go 语言版本为 1.17.7,编辑此文章时已经完成了 Lab 2A,无异常)。另外,如果您要查看计算机中已有的 Go 语言版本,可以执行go version命令。 我们推荐您在自己的机器上完成实验,这样您就可以使用您熟悉的环境,比如工具,文本编辑器等。另外,您也可以在 Athena 上完成实验。 macOS 您可以使用Homebrew来安装 Go 语言。安装好 Homebrew 后,执行brew install go命令即可。 Linux 根据您使用的 Linux 发行版,您可以从相应的软件包库中下载最新版的 Go 语言,比如在 Ubuntu 中可以执行apt install golang命令来安装 Go 语言。此外,您还可以从 Go 语言的官方网站中手动下载二进制包(译者注:Go 语言官网需要***才能访问,如果无法***的话,可以在Go 语言中文网中下载)。首先,确保您使用的是 64 位的 Linux 内核(uname -a会提示"x86_64 GNU/Linux"),然后执行如下命令即可: $ wget -qO- https://dl.google.com/go/go1.13.6.linux-amd64.tar.gz | sudo tar xz -C /usr/local 如果是国内的同学,可以执行如下命令: $ wget -qO- https://studygolang.com/dl/golang/go1.13.6.linux-amd64.tar.gz | sudo tar xz -C /usr/local 需要确保/usr/local/bin在您的环境变量PATH中。 Windows 实验可能无法直接运行于 Windows 上。如果您敢于尝试,可以试试Windows Subsystem for Linux,并执行上述 Linux 命令(译者注:笔者做实验用的是 VSCode+WSL2+Golang 1.17.7,需要注意的是一定要用 WSL2,否则无法使用 VSCode 调试 Go 程序)。否则还是乖乖使用 Athena 吧。 Athena 您可以通过ssh {your kerberos}@athena.dialup.mit.edu命令登录公共 Athena 主机。一旦登录成功,便可通过如下命令获取 1.13 版本的 Go 语言: $ setup ggo 开始 您将使用git(版本控制系统)拉取实验初始版本代码。如果您不熟悉 git,可以通过查阅Git-Book和Git User Manual自行学习。执行以下命令,即可从远端拉取 6.824 的初始实验代码: $ git clone git://g.csail.mit.edu/6.824-golabs-2020 6.824$ cd 6.824$ lsMakefile src$ 在src/main/mrsequential.go中,我们为您实现了一个简单的顺序 MapReduce。由于使用的是单进程,因此该程序同一时刻仅能执行一个 Map/Reduce task。此外,我们还为您提供了多组处理不同 task 的 Map/Reduce 应用程序代码:如mrapps/wc.go中包含单词计数所需的 Map/Reduce 方法,mrapps/indexr.go中包含计算文档索引的 Map/Reduce 方法。您可以执行以下命令来运行单词计数的顺序版本 MapReduce: $ cd ~/6.824$ cd src/main$ go build -buildmode=plugin ../mrapps/wc.go$ rm mr-out*$ go run mrsequential.go wc.so pg*.txt$ more mr-out-0A 509ABOUT 2ACT 8... mrsequential.go所需的输入数据来自名为pg-xxx.txt的文本文件,输出则保存在文件mr-out-0中。 您可以从mrsequential.go中随意借鉴您需要的代码,同时也可以阅读mrapps/wc.go来了解 MapReduce 的应用程序代码长啥样。 您的任务 您的任务是实现一个分布式的 MapReduce 系统,该系统由两个程序组成:master 和 worker,在系统运行期间共包含一个 master 进程和多个并行运行的 worker 进程。在实际应用的 MapReduce 系统中,worker 进程运行在很多不同的机器上,而在本实验中,您只需要在一台机器上运行它们即可。worker 进程和 master 进程之间使用 RPC 通信。每个 worker 进程需完成以下工作:向 master 进程请求 task,从若干文件中读取输入数据,执行 task,并将 task 的输出写入到若干文件中。master 进程除了为 worker 进程分配 task 外,还需要检查在一定时间内(本实验中为 10 秒)每个 worker 进程是否完成了相应的 task,如果未完成的话则将该 task 转交给其他 worker 进程。 我们为您提供了一些上下文代码。master 程序和 worker 程序的 main 函数入口分别位于main/mrmaster.go和main/mrworker.go中,不要修改这些文件,您应该将您需要实现的代码写在mr/master.go,mr/worker.go和mr/rpc.go中。 下面说明如何运行您写的代码,以单词计数应用程序为例。首先,执行以下命令以确保被构建的单词计数插件是最新版: $ go build -buildmode=plugin ../mrapps/wc.go cd 到src/main/中,运行 master 程序: $ rm mr-out*$ go run mrmaster.go pg-*.txt 其中pg-*.txt参数是文件路径,这些文件中保存着 master 程序的输入数据;每个文件都可以作为单个 Map task 的输入。 在其他若干窗口中,您可以运行如下命令来执行一个或多个 worker 进程: $ go run mrworker.go wc.so 当 worker 进程和 master 进程执行完毕后,可以显示 mr-out-*中的内容以查看程序输出。如果您的实验代码没有错误的话,经过排序后的输出结果应与mrsequential.go的输出相同,如下所示: $ cat mr-out-* | sort | moreA 509ABOUT 2ACT 8... main/test-mr.sh是我们为您提供的测试脚本。当给定pg-xxx.txt作为输入时,该脚本会检查您实现的 MapReduce 系统对两个不同类型的 Job(单词计数和计算文档索引)是否产生了正确的输出。该脚本也会检查您实现的 MapReduce 系统的 worker 进程在处理 Map task 和 Reduce task 时是否是并行运行的,以及您的系统是否能正确处理发生崩溃的 worker 进程。 如果您现在运行测试脚本,它将会挂起,因为 master 并没有被实现: $ cd ~/6.824/src/main$ sh test-mr.sh*** Starting wc test. 您可以将mr/master.go中Done函数内的ret := false语句修改为 true 来使主程序立刻退出,您将会得到如下输出: $ sh ./test-mr.sh*** Starting wc test.sort: No such file or directorycmp: EOF on mr-wc-all--- wc output is not the same as mr-correct-wc.txt--- wc test: FAIL$ 测试脚本期望对于每个 reduce task,都会生成一个被命名为mr-out-X的输出文件。空的mr/master.go和mr/worker.go不会生成这些文件(也少做了很多其他事情),进而导致测试失败。 当将全部代码实现完毕后,运行测试脚本后的输出应该看起来像这样: $ sh ./test-mr.sh*** Starting wc test.--- wc test: PASS*** Starting indexer test.--- indexer test: PASS*** Starting map parallelism test.--- map parallelism test: PASS*** Starting reduce parallelism test.--- reduce parallelism test: PASS*** Starting crash test.--- crash test: PASS*** PASSED ALL TESTS$ 您也会看到一些来自 Go RPC 包输出的错误,看起来像这样: 2019/12/16 13:27:09 rpc.Register: method "Done" has 1 input parameters; needs exactly three 忽略这些信息即可。 一些规则: map 阶段应将中间键分割为不同的桶(译者注:中间键指的是 MapReduce 论文中的 intermediate key,这句话的意思是将 map Task 的输出以某种形式保存为 reduce 函数能够读取的输入),方便后续nReduce个 reduce task 读取,而nReduce则是main/mrmaster.go传递给MakeMaster的参数; worker 进程应把第 X 个 reduce task 的输出保存到文件mr-out-X中; mr-out-X中每行都应该是调用一次 Reduce 函数的输出,应该按照 Go 语言的"%v %v"的格式生成,也即 key 和 value,如在main/mrsequential.go中注释"this is the correct format"的位置所示。如果您的实现和这一格式相差太多,测试脚本将会执行失败; 您需要修改的文件为:mr/worker.go,mr/master.go和mr/rpc.go。尽管您可以暂时地修改其他文件来辅助您测试,但请确保其他文件被还原为初始状态(原始版本)后您的程序仍能正常工作,我们将会使用原始版本的代码进行评判; woker 进程应该将 Map 函数的输出(intermediate key)保存在当前目录的文件中,使得后续 worker 进程可以读取它们并将其作为 Reduce task 的输入; 当 MapReduce Job 被计算完毕后,main/mrmaster.go希望您实现的mr/master.go中的Done()方***返回 true。这样mrmaster.go就能知道 Job 已经顺利完成,进程即可退出; 当 MapReduce job 被做完后,worker 进程就应该退出。实现这一功能的一种笨方法就是令 woker 程序检查call()函数的返回值:如果 woker 进程无法和 master 进程通信,那么 worker 进程就可以认为整个 Job 已经全被做完了,自己也就可以退出了。当然是否这么做还是要取决于您的设计,您也可以设计一个”please exit“的伪任务,当 worker 进程收到这一任务,就自动退出(译者注:笔者就是这么做的,看起来更优雅一些)。 提示 如果您觉得无从下手,可以从修改mr/worker.go中的Worker()函数开始,在函数中首先实现以下逻辑:向 master 发送 RPC 来请求 task。然后修改 master:将文件名作为尚未开始的 map task 响应给 worker。然后修改 worker:读取文件并像mrsequential.go程序一样,调用 Map 方法来处理读取的数; MapReduce 应用程序的 Map/Reduce 函数被保存在以.so结尾的文件中,在运行时使用 Go plugin 包读取; 如果您改变了mr/文件夹中的文件,并且该文件也被用到,那您需要将该文件使用类似于go build -buildmode=plugin ../mrapps/wc.go的命令重新编译成 MapReduce 插件; 本实验要求 worker 进程使用同一个文件系统,因此所有的 worker 进程必须运行于一台机器上。如果想要让 worker 程序运行在不同的机器上,那您需要为他们提供一个全局的文件系统,比如 GFS; 一个命名中间文件的合理形式是mr-X-Y,其中 X 是 Map task 的编号,Y 是 Reduce task 编号; worker 程序处理 Map task 的代码中需要一种将中间键值对存储为文件的方式,也需要一种在处理 Reduce task 时能从文件中正确读回键值对的方式。一种可能的实现是使用 Go 语言的encoding/json包。将键值对写入 JSON 文件的代码如下: enc := json.NewEncoder(file) for _, kv := ... { err := enc.Encode(&kv) 从 JSON 文件中读回键值对的代码如下: dec := json.NewDecoder(file) for { var kv KeyValue if err := dec.Decode(&kv); err != nil { break } kva = append(kva, kv) } 在 worker 中处理 map Task 的部分,对于一个给定键,您可以使用ihash(key)函数(在worker.go中)来选择它属于哪一个 reduce task; 您可以将mrsequential.go中一些功能的代码拿来直接用,比如:读取 map task 的输入文件,在调用 Map 方法和调用 Reduce 方法之间对中间键值对进行排序,以及存储 Reduce 函数的输出到文件。 作为一个 RPC 服务器,master 进程将是并发的,因此不要忘记给共享资源加锁。 可以执行命令go build -race和go run -race来使用 Go 语言的 race detector,在test.sh中有一条注释为您展示如何为测试开启 race detector; worker 进程有时需要等待,比如在最后一个 map task 处理完之前,worker 不能开始对 reduce task 的处理。实现这一功能的一种可能方案是 worker 进程周期性的向 master 请求 task,在每次请求间使用time.Sleep()阻塞一段时间。另一种可能的方案是 master 在收到 rpc 请求后额外开启一个 RPC 处理线程,在这个线程中执行循环等待(也可以使用time.Sleep()和sync.Cond),这样使得阻塞的 RPC 不会影响 master 响应其他 RPC; master 进程无法可靠的区分崩溃的 worker 进程、活着但因某些原因停止运行的 worker 进程和正在运行但太慢导致无法使用的 worker 进程。这一问题最好的解决方案是令 master 等待一段时间,如果某个 worker 进程在这段时间(在本实验中,这段时间被设置为 10 秒)内没有完成相应的 task,就放弃继续等待并将该 task 重新分配给其他 worker。之后,master 应该假设这个 worker 进程已经死亡了(当然,它可能还活着); 为了测试容错,您可以使用mrapps/crash.go插件,它在 Map 和 Reduce 函数中增加了随机退出功能; 为了确保没人能看到被崩溃进程写了一半的文件,MapReduce 论文提到了一个小技巧,那就是使用临时文件,一旦该文件完全写完,就自动重命名。您可以使用ioutil.TempFile创建临时文件,并使用os.Rename去自动重命名它。 test-mr.sh将会在子目录mr-tmp中运行所有的进程,因此如果有错误发生并且您想查看中间输出文件的话,可以查看这一目录中的文件。 提交步骤 注意:在正式提交前,请运行test-mr.sh。 使用命令make lab1命令打包您的实验代码并将其上传到班级的提交网站,其网址为:https://6824.scripts.mit.edu/2020/handin.py/。 第一次提交时您可能需要通过以下方式之一进行登录:1. 使用您的 MIT 证书;2. 通过 email 申请一个 API key。一旦登录成功,您的 API key(XXX)将会被显示,在控制台中输入以下命令上传 lab1 时会用到这一 API key: $ cd ~/6.824$ echo XXX > api.key$ make lab1 注意:检查提交网站以确保您的实验代码已经成功提交! 提示:您可能提交了多次。我们将会使用时间戳来检查您的提交是否是最新的。 公众号:努力学习的阿新
点赞 27
评论 3
全部评论
推荐
最新
楼层
暂无评论,快来抢首评~
相关推荐
08-10 15:50
华南理工大学 算法工程师
阿里云笔试
算法太恐怖了,一道博弈论,一道环上问题,,,要不是学过sg函数,这把就要爆零了
投递阿里云等公司10个岗位
点赞
评论
收藏
分享
08-08 08:42
美团_HR
美团投递指南
如果感觉自己准备的有七八成的学历比较好且算法能力还ok的同学,可以选择做第一批8月9号的笔试,因为美团有三个志愿的机会,挂了之后会转入第二第三志愿。即使三个志愿都用完了,只要你的面评不会到不了及格线,后续还有其他部门继续捞起来的,所以越早进入面试流程机会越多。(前提是不要留下不好的面评)准备的有七八成的学历比较好且算法水平比较一般的同学,建议是参与8/23的笔试。准备的比较差的同学,对于正式批,一定不要随随便便的去进入笔试和面试流程,这里强调一下,有个七八成就可以放心笔面试了,不是说要准备的多完美。但是如果连笔面的及格线都到不了的,基本上就是一轮游,面评差的三个志愿甚至只有一次面试机会,第二第...
投递美团等公司10个岗位
点赞
评论
收藏
分享
07-08 17:56
门头沟学院 C++
快手面试官加我微信?
兄弟们我是28届双非本,本来想着投投简历试试,完全没想着会有什么好结果,简历上写了两个烂大街的项目,结果上午投的快手,下午就有人加我微信说是要内推我,这是不是骗子啊
程序员小白条:
铁骗子啊,牛客看到起码三位数了,笑死了
投递快手等公司10个岗位
点赞
评论
收藏
分享
08-04 22:44
江西财经大学 Java
上海某小厂,做完一道场景题就oc了,这是啥情况呀,鼠鼠害怕被骗到缅北
牛客59349152...:
没有让你做出个前后端页面,然后又不要你就知足了吧😂
点赞
评论
收藏
分享
08-10 17:14
OPPO_运营管理_HR
鹅厂这么活
整体感觉:温和儒雅,攻击性不像阿里和字节那么强 1. 腾讯每个月会给员工发30Q币,用这30Q币可以给自己买一个腾讯视频会员和一个QQ音乐会员。 2. 每月1号可以领取体验福利,别问我的王者荣耀10级vip怎么来,反正没花一分钱 3. 一些特殊日子时,公司都会发一些福利。比如之前QQ音乐周年纪念日,给全体腾讯员工一年的绿钻会员 4. 在腾讯也不需要怎么买衣服了,每隔一段时间就会发些文化衫,光文化衫都穿不过来了。除了发衣服,也会有各种大礼包,比如本子、包、贴纸、公仔、吃的 5. 腾讯内部有一个Q米系统非常棒,每年都会给员工发放2000左右(不同职级不一样) 6. 腾讯自己创造了一个孝顺长辈节,每...
腾讯公司福利 921人发布
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
点赞
收藏
分享
评论
提到的真题
返回内容
全站热榜
更多
1
...
25年秋招精心整理的最新互联网大厂笔面试题集合
2.6W
2
...
暑期实习转正自评,你就这么写!
9409
3
...
字节秋招-后端开发-一面
8864
4
...
26届秋招建议
5656
5
...
26秋招-拓竹嵌入式软件面经
5560
6
...
字节秋招意向
5318
7
...
本华为OD终于翻身!(百度后端面经)
4360
8
...
影石嵌入式驱动开发面经
3597
9
...
字节二面-半技术半聊天?
3219
10
...
亚信科技java实习面经
2548
创作者周榜
更多
正在热议
更多
#
我的秋招“寄”录
#
14457次浏览
185人参与
#
你最近一次加班是什么时候?
#
72755次浏览
365人参与
#
去哪儿旅行秋招
#
223644次浏览
3173人参与
#
实习的内耗时刻
#
16578次浏览
229人参与
#
我的AI电子员工
#
10135次浏览
66人参与
#
你上一次给父母打电话是什么时候
#
7217次浏览
73人参与
#
腾讯大前端岗位热招中
#
14911次浏览
164人参与
#
大城市找工作会更容易吗
#
43793次浏览
351人参与
#
规定下班时间vs实际下班时间
#
10905次浏览
88人参与
#
独居后,你的生活是更好了还是更差了?
#
5826次浏览
91人参与
#
工作上你捅过哪些篓子?
#
8028次浏览
53人参与
#
被AI治愈的瞬间
#
63939次浏览
634人参与
#
每个月的工资都是怎么分配的?
#
59371次浏览
593人参与
#
面试被问期望薪资时该如何回答
#
268087次浏览
1539人参与
#
秋招想进国企该如何准备
#
81399次浏览
442人参与
#
入职第二天,午饭怎么解决
#
26606次浏览
76人参与
#
奇葩时刻大赏
#
57171次浏览
237人参与
#
得物求职进展汇总
#
103815次浏览
830人参与
#
吉利求职进展汇总
#
76951次浏览
386人参与
#
那些我实习了才知道的事
#
221396次浏览
1740人参与
#
国央企薪资爆料
#
105810次浏览
556人参与
#
你觉得材料多少算高薪
#
22344次浏览
149人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务