前言

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

MapReduce

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

实现步骤

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

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

lab

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

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

具体代码放在mit-6.824

Reference

MapReduce (2004)