寫(xiě)完LAB2,3,4蛾坯； 再切回LAB1光酣。
不得不說(shuō)，LAB4 的B 部分真心難脉课。我的那些思考救军，背后都是大量的DEBUG，才得出的正確思路倘零。那些點(diǎn)也不是我一開(kāi)始就能想到的缤言。
言歸正傳，我們開(kāi)始MAP REDUCE的實(shí)現(xiàn)视事。
首先我們需要知道MAP REDUCE的框架胆萧，以及運(yùn)作原理。
我們通過(guò)一個(gè)WORD CNT的例子來(lái)看
MAP部分每臺(tái)機(jī)器選取各自的FILE俐东，分別處理按照SHARD的規(guī)則跌穗，導(dǎo)出到不同的文件。
REDUCE這邊值抓取自己負(fù)責(zé)的SHARD的文件然后做統(tǒng)計(jì)虏辫。
就是MIT 作業(yè)要求上說(shuō)的內(nèi)容
而整個(gè)MAP REDUCE 分為下圖這幾個(gè)步驟
首先INPUT蚌吸，就是用戶為指定一組輸入的文件集。然后不同機(jī)器取不同的文件砌庄，系統(tǒng)盡量做到每臺(tái)機(jī)器平分文件就是SPLIT羹唠。MAP就是從一個(gè)文件里讀，變成一個(gè)個(gè)單詞后娄昆，交給PARTITION SORT（MAP是用戶自己實(shí)現(xiàn)）
出去的時(shí)候是沒(méi)有序的佩微，但是都按照SHARD規(guī)則放到不同的文件里了。這邊MAP REDUCE框架會(huì)對(duì)文件做一次硬盤外排序保證后序的FETCH是有序的萌焰。
FETCH那邊 因?yàn)闀?huì)有多個(gè)文件OWN這個(gè)SHARD哺眯，他需要有序的讀，就需要使用K路歸并算法扒俯。
最后把有序的文件輸入給到REDUCE奶卓，REDUCE做WORD CNT統(tǒng)計(jì)一疯，最后寫(xiě)進(jìn)OUT文件里。
最后我們看下SYSTEM 的架構(gòu)是怎么樣的夺姑。
好了了解了MAP REDUCE的原理墩邀，我們就正式開(kāi)始寫(xiě)LAB了
第一步 讀作業(yè)要求到PART1
https://pdos.csail.mit.edu/6.824/labs/lab-1.html
第二步 閱讀代碼結(jié)構(gòu)
主要是先看COMMON_MAP, COMMON_REDUCE。
里面說(shuō)到要看GO IOUTILS
https://studygolang.com/articles/14669
第三步 設(shè)計(jì)DO MAP的步驟
大概實(shí)現(xiàn)思路如下：
1.read file content
2.call mapF to get []KeyValue
3.produce intermediate files by nReduce and reduceName
https://my.oschina.net/solate/blog/719702
4.foreach keyValue,ihash the key mod nReduce , use json.NewEncoder to write into a correct file
第四步 實(shí)現(xiàn)DOMAP
第五步 設(shè)計(jì)DO REDUCE 步驟
1.第一步 把幾個(gè)文件的內(nèi)容都讀到內(nèi)存里
2.第二步 排序
3.第三步 根據(jù)排序的KEY盏浙，調(diào)用REDUCE磕蒲，生成新的KEY VALUE PAIR寫(xiě)進(jìn)OUT FILE
第六步 實(shí)現(xiàn)DO REDUCE
第7步 跑測(cè)試
實(shí)現(xiàn)PART2 WORD CNT
首先閱讀作業(yè)說(shuō)明，以及HINT里給的幾個(gè)相關(guān)博客只盹。
切割出單詞需要FieldsFunc的用法
MAP就是切割單詞辣往，然后統(tǒng)計(jì)次數(shù)然后輸出的KEYVALUE[]
REDUCE就是把所有的統(tǒng)計(jì)結(jié)構(gòu)做匯總，求SUM殖卑。
第8步 閱讀PART 3文檔 并實(shí)現(xiàn)
然后構(gòu)建大概思路站削，需要去監(jiān)聽(tīng)registerChan上還沒(méi)有可用的WORKER，如果TASK還有多孵稽，來(lái)一個(gè)就分配一個(gè)许起。
分配的時(shí)候，為了并發(fā)菩鲜，需要單獨(dú)開(kāi)線程去發(fā)RPC园细，等回復(fù)。OK了之后接校，把TASK CNT -1猛频，隨后把這個(gè)WORKER重新放回registerChan
- You may find sync.WaitGroup useful.
這個(gè)用來(lái)看NTASK有沒(méi)有做完。這樣就不用去減TASK CNT了
第9步 閱讀PART 4文檔 并實(shí)現(xiàn)
根據(jù)文檔4的意思蛛勉，其實(shí)就是WORKER會(huì)掛掉鹿寻。掛掉的表現(xiàn)就是RPC響應(yīng)超時(shí)。這個(gè)時(shí)候MASTER就需要找一個(gè)新的WORKER
那么其實(shí)我們就需要先拿到RPC的RESPONSE诽凌。如果是OK按照原來(lái)邏輯走毡熏。如果不OK，可能是網(wǎng)絡(luò)超時(shí)侣诵，可能是節(jié)點(diǎn)掛了痢法。
無(wú)論是啥我們都需要通知另一個(gè)線程，讓他知道這個(gè)事情發(fā)生杜顺，他可以HANDLE.
從這點(diǎn)出發(fā)就會(huì)想到線程間通信在GO里是用CHANNEL來(lái)做财搁。
那么我就設(shè)定一個(gè)TIMEOUT CH，如果一個(gè)任務(wù)失敗了哑舒，我就通知這個(gè)CH 這個(gè)任務(wù)的ID號(hào)妇拯。
那么另外一個(gè)線程感知到了幻馁，就可以從這個(gè)CHANNEL里取到這個(gè)ID號(hào)洗鸵，隨后再找一個(gè)WORKER ADDR越锈，把這個(gè)任務(wù)分配給這個(gè)WORKER去做”毂酰基于上述思路甘凭。
代碼如下。
TEST -RACE來(lái)測(cè)會(huì)慢一下火邓。不過(guò)要求會(huì)更嚴(yán)格丹弱。
測(cè)試通過(guò)
第10步 實(shí)現(xiàn)倒排索引
真的很簡(jiǎn)單。一個(gè)文件铲咨，列出所有單詞躲胳，KEY是單詞，VALUE都是這個(gè)文件名
REDUCE更簡(jiǎn)單了纤勒，根據(jù)要求的格式輸出下坯苹。
尾聲
應(yīng)該是從4月28號(hào) 開(kāi)始寫(xiě)MIT 6.824的LAB。到今天全部寫(xiě)完 花了一個(gè)月不到幾天的時(shí)間摇天。
從LAB 2開(kāi)始寫(xiě)粹湃，寫(xiě)到4 ，4寫(xiě)完之后花了我整整1個(gè)周末和3個(gè)晚上（因?yàn)榘滋煲习啵┑臅r(shí)間去DEBUG 4B泉坐。相比LAB1为鳄，整個(gè)LAB從看需求到測(cè)試通過(guò)，幾乎都是BUG FREE腕让，估計(jì)就花了我2個(gè)小時(shí)就搞定了孤钦。
不得不說(shuō)還是收獲了不少東西。
也非常開(kāi)心纯丸，開(kāi)心的點(diǎn)不僅是所有部分全部測(cè)試至少200次正確司训。（為啥是200次測(cè)試，一個(gè)是有些測(cè)試1000次確實(shí)太耗時(shí)液南。另一個(gè)原因確保我的代碼的可靠性是2個(gè)9壳猜，0.99^200 = 0.1， 假設(shè)10%是低概率事件滑凉。所以200次都過(guò)统扳，可靠性應(yīng)該在99%之上的） 同時(shí)也覺(jué)得自己的代碼量還是很少的。（我的觀點(diǎn)是畅姊，實(shí)現(xiàn)同樣的功能在不破壞可讀性的基礎(chǔ)上咒钟，代碼越簡(jiǎn)潔越厲害）
最后代碼提交上GIT。
https://github.com/yixuaz/6.824-2018
