MIT 6.824 (2022) Lab 1: MapReduce解题思路与问题总结

写在前面：

• 尊重课程的要求，未公开源码。
• 本文主要是给有需要的小伙伴一些提示，避开一些弯路和坑。
• 只是分享我的思路，我的解题方案。一家之言，难免有错漏，请多指教。

如果你问我做题花了多久，我只能回答很久很久：思考怎么开始动手花了很久；调试花了很久。
但我想，小伙伴们应该跟我一样，主要目的是学习，而不是为了交作业。所以，多长时间不重要，有没有收获才重要。

第一只拦路虎

按照课程说明（见文末链接：说明与提示，下文简称“说明与提示”），执行第一个go命令go build -race -buildmode=plugin ../mrapps/wc.go就失败了：-buildmode=plugin not supported on windows/amd64。
有点挫败，也有点失望，对Windows失望。

刚好近期学习了Docker，试验下来发现Docker+MIT6.824课程简直绝配：

• 编译环境随便选，即使你在Windows上开发，也可以让你的代码在Ubuntu环境下编译和运行
• 源码下载下来，相同包下的相同函数会编译报错（GoLand)，相同的目录下（mrapps）有多个main函数也会报错。这样就无法在GoLand中调试代码

从何处入手？

在“说明与提示”中有这么一条：

可以像这样开始：修改mr/worker.go的Worker()函数，通过RPC向调度进程请求一个任务。然后修改调度进程，返回一个尚未开始的Map任务的文件名。再然后修改工作进程去读取这个文件，并调用Map函数，就像main/mrsequential.go里一样。

虽然有了这条提醒，我也知道就应该从这里开始，可我还是不知道该怎么入手。
于是在B站的评论里找了几条留言，有人分享了他们的解法。有两篇感觉不错（见文末链接：参考1/参考2），虽然不完全同意他们的做法，但都给了我一些启发。

第一个非常离谱的错误

说是错误，不如说是认识。之前，RPC只是听说过，没有实际开发过。涉及到状态一致性问题，想当然地认为是可以通过锁（Mutex）来解决。但试验下来发现，RPC根本获取不到锁。为此还专门去Stack Overflow提问了，惨遭2个down-vote，不过还是有好心的大哥回答了，简直醍醐灌顶啊：锁是进程之间的啊，而RPC是服务之间的。极端地想（其实也很正常，只是当前这个作业是运行在同一台机器上）RPC服务发生在A机器和B机器之间，光用Mutex或者chan怎么可能保证A/B机器上数据的一致性？ 所以，当worker完成工作时，并不能通过更新状态来告知coordinator工作已完成。需要worker来通知它（callback）。

用什么容器做任务池？

“说明与提示”中说道：当任务池没有任务再碰到请求时，需要等待。可以用sync.Cond来实现。
这个类型没用过啊。于是又去Stack Overflow上找例子来参考，例子中使用的是map，所以就用map做任务池。

type Coordinator struct {
	// Map
	numMapWorkers       int
	mapCond             *sync.Cond
	availableMapWorkers map[int]()*MapWrapper // 各种状态都放一起是不行的。锁不好控制
	runningMapWorkers   map[int]()*MapWrapper // 留着，在callback时判断其是否为有效的正在运行的任务有用
	finishedMapWorkers  map[int]()*MapWrapper // 已完成的，Reduce请求任务时有用

	// Reduce
	numReduceWorkers       int
	reduceCond             *sync.Cond
	availableReduceWorkers map[int]()*ReduceWrapper
	runningReduceWorkers   map[int]()*ReduceWrapper
	finishedReduceWorkers  map[int]()*ReduceWrapper
}

什么时候去请求任务？怎么请求？

答案：for循环。
嗯，就是这么 简单粗暴 大道至简。

不过，请求中一定要加停顿time.Sleep()。否则，所有的任务可能都被某一个worker进程请求了，导致 reduce parallelism test 失败。

在判断工作进程完成还是超时时，用阻塞等待还是自旋等待？

这两种方案我来来回回换了几遍。
最终选择了自旋等待。这名词也熟悉，也能提高CPU利用率。
而阻塞等待，对象一直持有锁，影响其他进程对其状态的更新。

怎么判断一个任务被重置/舍弃了？

• 一个任务T被分给了w1
• w1工作了10s还没有完成
• 任务T被重新分配给w3
• 15s的时候，w1任务完成了，但已经晚了。它的工作成果应该被全部舍弃

怎么实现呢？
首先想到的就是term，课程里也有介绍。我也是这么做的。每次请求带个term（也可以理解为计数器），如果被重置，则+1。当工作进程完成callback的时候，比较term是否相同，不同就结束了，不需要后续处理。 但一直有个根本问题没发现。每次修修补补都没到根子上。直到发现“超时”和“完成callback”有可能同时完成，仔细地思考和追踪才发现了问题。
一定要先判断worker的状态，再判断term。
以前只判断了term。

关于term，还有个地方要注意。 按上面的思路，Worker类型里应该有个Term值。 这样会有个问题，会形成竟态。
读：由于Worker里有Term字段，所以任务请求时通过rpc会读取这个字段
写：任务超时重新分配时，需要更新Term

想了很久没想明白。也试了几种不同的方法都失败了。 最后用分开2个字段的方式解决了。
一个封装类型Wrapper，这里的Term主要用来更新和比较（作为基准），有锁。
Worker里的Term，在请求时，将Wrapper.Term赋值给它；在callback时，用来和Wrapper的Term比较。

MapWorker struct {
	FileName           string
	InterTempFileNames []()string // 每个Map产生和Reduce任务总数一样的临时文件
	ID                 int
	Status             workerStatus
	BeginTime          time.Time // 观察执行时间
	EndTime            time.Time
	Term               int
}
MapWrapper struct {
	mu     sync.Mutex
	worker *MapWorker
	term   int //用于比较和更新
	done   chan bool
}

测试脚本是不是有问题？它覆盖所有情况了吗？

先给自己的怀疑精神点个赞。

当你word-count的测试通过了，reduce parallelism/crash等测试总是失败时，你可能会怀疑测试脚本是不是有问题：机器的不同，性能的不同，覆盖不全等等。

一次次地希望，又一次次地失望。
总是觉得这个改完应该就可以了。但是并没有。
不是没解决问题，就是又冒出了新的问题。
我越发怀疑是不是他的测试脚本有问题（飘了。。）

结果，随着接近终点（代码快完成了），越测试，会越发感叹测试脚本的正确和神奇。它说不通过，那肯定是某个地方的代码写错了，即使这错误只是偶尔出现。
测试脚本是真用心了。Respect！

TODO

本文整理于./test-mr-many.sh 10测试通过之时。还有很多想重构和试验的地方。

• 让MapWorker和ReduceWorker实现同一个接口。这样的话，在获得任务后，不用判断是Map任务还是Reduce任务，直接worker.DoWork()就行了
• 使用chan作为任务池的容器
• 使用WaitGroup来判断任务是否全部完成

相关链接：

• http://www.youngzy.com/blog/2022/06/mit-6-824-lab-mr-2022/
  翻译作业的说明和提示。
• https://ziannchen.work/2022/mit-6.824-lab1-mapreduce/
  参考1
• https://zhuanlan.zhihu.com/p/260752052
  参考2
• https://stackoverflow.com
  程序员离不开的网站。文中出现了太多次，值得放个链接。