首页

/

归档

/

友链

/

Github

/

模拟面试

/

独立黑客

/

资料

/

订阅

/

RSS

/

关于我


MapReduce 论文阅读

MIT 6.824

Prelude> map (+1) [1..10]
[2,3,4,5,6,7,8,9,10,11]
Prelude> foldl (+) 0 [1..10]
55
Prelude>

execution overview

1. MapReduce先把数据分拆成16-64M之间的大小,然后fork自身,成为worker和master

2. master将会分配任务给worker们

3. 被分配执行map任务的程序读取被切割的文件块。调用用户的map函数,将其产生的
键值对存在内存里

4. 内存中的键值对会被持久化到硬盘上。然后将路径返回给master。

5. master将路径告知给执行reduce任务的程序,根据key将上一个环节的键值对排序
(因为数据量可能非常大以至于不能全部放在内存里)

6. 执行reduce任务的程序遍历排序后的键值对然后调用用户的reduce函数。将其返回值
追加到最终文件中。所以最终会产生n个输出文件,n为用户指定的reduce任务的数量。

7. 所有任务完成后,MapReduce返回,然后开始执行用户的其他代码。

Lab

// doMap
for _, kv := range mapF(inFile, string(contents)) {
    i := ihash(kv.Key) % nReduce
    encs[i].Encode(&kv)
}

// doReduce
mergeFileName := mergeName(jobName, reduceTaskNumber)
mergeFile, err := os.Create(mergeFileName)
for {
    if call(worker, "Worker.DoTask", doTaskArgs, nil) {
        wg.Done()
        break
    } 
}
for {
    if call(worker, "Worker.DoTask", doTaskArgs, nil) {
        wg.Done()
        break
    } else {
        worker = <-registerChan
    }
}

总结:好玩儿!