mapreduce复制连接的代码_6.824 Lab1: MapReduce

（2020.3.31更新：本文基于2018版的6.824写成，之后文章均基于2020版。相对于20版，18版lab1更像是在抽象出的框架里填空，所以20版的难度更大一些，但学习效果也会好很多）

lab1是填空补完一个单机的mapreduce框架，如果不会go的话，开始会觉得有些艰难，因为既要理清mapReduce的代码思路，又要熟悉go的api。但这些对成熟的程序员胖友应该不成问题，对半生不熟的胖友，写下来会觉得提升很大。

这些都熟悉之后，lab1还需要注意有两点：(1)实验的容错机制相比论文非常简单，做完后需要好好温习下论文是怎么做的；(2)part 3,4部分，有一些并发细节需要注意。这种细节有的可能跑一两次就出错，有的可能跑几万次也不一定出错。在之后的lab，需要实现的系统会更复杂，这种细节如果不注意搞错的话会很让人头疼。

Part 1

doMap是mapReduce框架的一部分，每执行一次doMap，就在其内部执行一次mapF。doMap将mapF包装起来，使mapF只关心自定的业务逻辑。doMap做了以下几件事：

1.读取当前mapTask被分配的原始文件，转换成字符串

2.调用mapF，获得KeyValue数组

3.新建nReduce个中间文件，用reduceName生成文件名

4.遍历mapF生成的数组，根据KeyValue的key的hash值，用json的格式，将KeyValue写入到对应文件里

func 
           

doReduce和doMap的作用一样：

1.读取当前reduceTask对应的所有中间文件

2.以json的格式，反序列化得到KeyValue，根据KeyValue的key存储到map中，把相同key值的value放到数组中

3.新建outFile

4.按key遍历map，调用reduceF，得到key对应的最终value，以json将{key,value}写入到最终的输出文件中

func 
           

Part 2

mapF对输入的字符串进行最基本的分词，遍历分词后数组，每个词记一次加到最终的数组里

func 
           

reduceF累加当前词出现的次数，可以优化为 return strconv.Itoa(len(values))

func 
           

Part 3

前两个part是串行执行，这个part需要实现并行调度

1.master启动rpcServer，accept worker的连接，新起goroutine把已经注册的worker的address放进chan里

2.先后调用两次schedule，mapPhase和reducePhase各一次，每一次都要将所有任务并行分发给works。这里用goroutine调用rpc，因为goroutine的特性，不需要担心新建过多的线程占用cpu资源

3.声明WaitGroup，使schedule在所有调用worker rpc的goroutine全部结束再退出

4.遍历ntasks，每次从registerChan的取出一个worker的address，调用rpc，结束后再把address放回chan，以避免woker总数量小于ntasks。注意：(1)wg.Done()要在放回address前调用，否则最后几个子goroutine会因为没有goroutine从chan取出阻塞，无法调用Done()，使主goroutine一直阻塞在Wait()，最终全部阻塞死锁；(2)要将cur作为参数传到goroutine中，否则取得的cur可能是下个循环的cur值

5.所有woker都完成后退出

func 
           

Part 4

实验的rpc同步返回，goroutine验证返回结果，失败则取新的worker进行分配。两点保证了这种worker容错：(1)doMap和doReduce是无状态的，即函数式；(2)doMap和doReduce结果的产生有原子性，要么不存在，要么只存在一份完整的。

func 
           

Part 5 倒排索引

选择在mapF进行 词-文档 的去重

func 
           

reduceF对 文档名数组 排序，输出

func 
           

最终生成的倒排索引如下：

{"Key":"l","Value":"4 pg-dorian_gray.txt,pg-huckleberry_finn.txt,pg-sherlock_holmes.txt,pg-tom_sawyer.txt"}
{"Key":"beckoned","Value":"2 pg-grimm.txt,pg-sherlock_holmes.txt"}
{"Key":"Avenue","Value":"1 pg-sherlock_holmes.txt"}
{"Key":"placed","Value":"7 pg-being_ernest.txt,pg-dorian_gray.txt,pg-frankenstein.txt,pg-grimm.txt,pg-metamorphosis.txt,pg-sherlock_holmes.txt,pg-tom_sawyer.txt"}
{"Key":"clenching","Value":"1 pg-dorian_gray.txt"}
           

至此lab1完结了，欢迎胖友们批评讨论