mapreduce.go源码浅析 MIT 6.824 Spring

时间:2017-07-13 13:43

这学期选了《分布式系统导论》,实验部分和MIT 6.824 Spring 2015 一样,请戳, 再加上对我来说很困难的课前reading以及课后作业,压力巨大:(

实验共分5部分,根据助教往年评分来看,难度呈线性递增。

由于MIT提供的代码是由go语言所写,所以在着手实验前,你需要了解一下go,我用的是 AN INTRODUCTION TO PROGRAMMING IN GO 链接, 很薄的小册子, 可以迅速了解go语言的基本语法。

6.824 Lab 1: MapReduce

实验要求, Part 1 需要完成一个完整Word Count程序中的map函数和reduce函数, 第一步当然是读提供的代码, 把mapreduce.go中RunSingle()流程读懂,知道map函数和reduce函数的输入和输出是什么, Part 1 基本就会做了。

下图是我画的RunSingle()简单流程图,以nMap=3,nReduce=2为例,输入一个文本文件,最后输出Word Count结果。
(注意其中Reduce()阶段的蓝线和黑线的不同,这是Word Count中我非常喜欢的一个trick)

示例

原来mapreduce也不是很神秘呢. 当然, 这里只是基于单机单线程顺序执行的Word Count。

Part II: Distributing MapReduce jobs

这部分用单机多线程模拟分布式mapreduce,主要是完成mapreduce/master.go中RunMaster()函数。 这部分需要用到goroutine和channel, 这也是go语言的强大之处,有了goroutine和channel,多线程的门槛不再高不可攀(起码对我来说 ~),
Word Count流程同Part 1:Split、Map、Reduce、Merge, 只不过此时的Map和Reduce阶段需要RunMaster()来分配给各个Worker来做,至于怎样分配Job、fault tolerance,便是我们需要考虑的问题了。我的思路主要受到Modify the MapReduce struct to keep track of any additional state (e.g., the set of available workers) 这句话的启发,于是我便在struct MapReduce中构造了一个availableworkers,用来记录某时刻那些处于空闲的Worker, 于是乎,对于每一个Job(mapjob或者reducejob),Master要么把它分配给availableworkers中处于空闲状态的Worker,要么分配给mr.registerChannel中新注册的Worker。

至于Part 3, 我在测试Part 2 代码时,发现Part 3 部分也通过了测试。冏。。。




总结, 虽然Part 2、3 代码通过了测试,其中还是有一个关键的地方必须改进,对于一个job, Master在决策分配给availableworker or registerChannel时,注意其中availableworker是map[string] *WorkerInfo类型,而registerChannel是channel类型,这。。。为了解决这个问题,我只好加了时间锁 =.= 一直觉得这个方法太不优美了。。。待我啃啃go语法,看看有没有什么好的方法吧。

注:Collaboration Policy中明确提到Please do not publish your code or make it available to future 6.824 students – for example, please do not make your code visible on github. so,我就不share code了。