6.824 Lab1 MapReduce

前前后后做了15个小时, 看到PASSED ALL 30 TESTING TRIALS的那一刻, 太爽!

概述

这个实验要求实现经典论文MapReduce的模型。MapReduce在Google内部是跑在一个服务器集群里的, 这些服务器共享一个分布式文件系统GFS。这个实验只要求实现运行在本机多个进程上的、本地文件系统上的MapReduce模型, 省去了与分布式文件系统的交互 (要做负载均衡这个很重要, 而且应该很麻烦) 。

实现过程流水账

先读论文花了3h左右, 内心活动: 这论文真简单。

然后开始实现。我并不会go语言, 官网那个tour我也就做了一点点, 事实证明全做完比较省时间。第一次写的代码全是if-else, 我还没有加入容错机制的时候代码已经复杂到我读不懂了。内心活动: 工业界实现这玩意的人是神仙吧! 然后我把3个小时码的200多行代码全都回滚掉了:-(

第二次写代码之前, 我决定写一个类似于有限状态自动机的东西。事实证明这个模型还不错, 让我的思路变得比较清晰, 并且便于拓展。然后花了2h画图+搭框架, 就是只写了一堆switch-case, 每种状态对应的转移和转移前需要进行的操作的注释。然后就头晕, 下班了。

今天是第三次碰这个东西, 今天如果再自闭我可能就要对这实验产生心理阴影了。好在我上次的DFA没啥大问题, 只是有些corner case没想到, 缝缝补补搞了一段时间。终于把注释转换成了代码, 最戏剧性的一刻来了: 开码10小时后我终于进行了第一次编译! 我以为会得到巨长无比的报错, 结果报错就八九行。然后就是改完一行错再出现一行错, 改完 “最后一行” 错之后又蹦出来十几个错误, 改了若干年……通过编译之后, 他在起始状态就出错了……然后又改了若干年, 终于输出了结果。

第一个教训: 把语言学明白, 勤编译勤测试。

我查看输出文件的前三行 (共两万行) , 发现与标准输出一样! 然后高兴地去跑测试脚本, 结果第一个正确性测试点就挂了……

第二个教训: 测试要认真严谨。

然后又改了若干年, 期间多次翻阅论文, 发现人家写进论文的东西都是经过取舍和迭代的, 还是非常精华的。后来就是无限改bug, 调试, 按下不表。终于在今天码代码的第8小时通过了所有测试!

做的不错的地方

  1. 画DFA
  2. 头脑不清楚的时候出门转转, 可以花掉长达20分钟的时间, 但是回来之后你就复活了!

想要做得更好的地方

  1. 阶段性编译、测试。例如我的DFA设计好了, 这时候就可以测试下转移有没有问题, 然后再在转移前后加功能。
  2. 有设计测试点的能力。对于这个实验, 我是用户, 而且一定程度上可以说是赶时间, 所以用老师的脚本来测试、调试没有什么错。但是一旦成为真正意义上的开发者, bug都要自己找 (不提开源社区之类) , 需要有能力设计若干测试来检验自己的代码在各方面的正确性/性能。这确实需要写一些 “没用的” 代码, 但是它们通常很简单, 而且很有用 (如算法竞赛里的对拍程序和暴力程序) 。例如, 我尽管知道各个操作的时间/空间复杂度, 但还是不知道我这个实现并发性如何, 究竟有多少CPU时间是overhead。
  3. 证明我的DFA的正确性
  4. Challenge
  5. 阅读老师的测试脚本, 学习写脚本