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完結了，歡迎胖友們批評讨論