前言

花了几天功夫，断断续续做了下lab1。其实大部分时间都在看Go。非常非常简洁的一门语言。对并发的支持非常好。值得花时间学习。然而MapReduce并没想象的这么复杂。

MapReduce

主要思想很简单。主要由map和reduce两个函数组成。(玩过函数式编程的朋友，对这两个函数应该很熟悉)，数据从map输入，输出一系列键值对，再由reduce把输出的键值对根据键组合在一起。当然最有趣的地方是，这些操作都是异步的，在多个机器上运行，所以非常快。

实现步骤

  1. 把数据分成M份，分别是Mi
  2. 启动一个master对象，由它来控制如何分配调控
  3. master不断的挑出一个好的机器(worker)来对Mi进行执行map函数
  4. map函数返回一个 key/value 数组
  5. 然后把 key/value 数组分成R份存在本地，等待Reduce。当map全部完成后，每个Mi生R份结果。
  6. 从每个Mi中选择一份Ri。然后根据Key排序，把相同Key的Value合在一起，生成key/list(value)
  7. 开始reduce，输入list(value)。
  8. 最后会生成R份文件

最后的R份文件没必要直接合在一起。通常会把它们丢给下个MapReduce

lab

总体来说不难。实现步骤全在paper中讲的很清楚了

  • lab1 完成两个函数doMap和doReduce。doMap就是完成上面4,5两个步骤.doReduce是上
    面7,8两个步骤。注意这里不是异步，而是顺序执行
  • lab2 实现wordcount，只要完成了lab1，lab2就是手到擒来的事情。
  • lab3 略复杂一点。把上面map和reduce的操作变成异步。Go中有一个很有趣的东西，叫做channel可以起到很大帮助。类似于生产者消费者。这里不细讲。另外还需要一点RPC的知识。
  • lab4 处理worker失败的情况。如果失败就让别的worker重新执行这个任务。

具体代码放在mit-6.824

Reference

MapReduce (2004)