内容简介:MIT 6.824总结:好玩儿!
MIT 6.824
-
Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key.
-
Map接受用户输入然后产生一系列的键值对。
key1, key2, key3, key2
-
MapReduce库将Map产生的键值对根据Key进行分组,然后传给Reduce。
key1:1, key2:1, key3:1, key2:1
-
Reduce接受键值对,然后产生一个更小的键值对。
key1:1, key2:2, key3:1
-
-
MapReduce启发自Lisp的map和reduce。在Haskell中的对应示例为:
Prelude> map (+1) [1..10] [2,3,4,5,6,7,8,9,10,11] Prelude> foldl (+) 0 [1..10] 55 Prelude>
-
试图通过MapReduce这个库让没有分布式开发经验的 程序员 也能利用分布式集群的 性能。MapReduce这个库需要提程序员解决的问题包括但不限于:
-
分拆输入数据
-
任务调度和数据分发
-
管理机器间通信
-
容错性
-
负载均衡
-
etc...
-
-
流程概览
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返回,然后开始执行用户的其他代码。
-
容错性
-
worker failure: The master pings every worker periodically. If no response is received from a worker in a certain amount of time, the master marks the worker as failed. Any map task or reduce task in progress on a failed worker is also reset to idle and becomes eligible for rescheduling.
-
master failure: It is easy to make the master write periodic checkpoints of the master data structures described above. If the master task dies, a new copy can be started from the last checkpointed state.(不过此论文发布时 采用了简单的实现,即如果master失败,直接终止执行)
-
Lab
- Part I: 正确实现
doMap
和doReduce
。根据figure1里的描述写代码,基本就不会错。 我在这里遇到的坑是没有仔细读论文,以为所有reduce函数公用一个输出文件。此处核心代码 为:
// 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)
-
Part II:统计单词。只要跟着描述来就行。仔细读一下给出的Hint和 go 的文档。
-
Part III:更改schedule.go。这里我花了点时间,因为大坑在于,我没想到在这一步 就要开始处理错误,还以为是在下一步呢,直到调试的时候看log,总是说没有reduce 的输出文件。然后果断给RPC调用加了个重试机制---死循环。然后就通过测试了。
for { if call(worker, "Worker.DoTask", doTaskArgs, nil) { wg.Done() break } }
- Part IV:处理worker出错。处理方式为如果worker失败,就把任务分配给其他worker执行, 所以也就是在上面的代码小改一下:
for { if call(worker, "Worker.DoTask", doTaskArgs, nil) { wg.Done() break } else { worker = <-registerChan } }
- Part V:统计单词出现的文件名。这个其实应该就是考是不是对MR真正的掌握了吧。 思路就是生成键值对的时候,单词为key,文件名为value然后进行MR。
总结:好玩儿!
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
深入理解计算机系统(原书第3版)
Randal E.Bryant、David O'Hallaron / 龚奕利、贺莲 / 机械工业出版社 / 2016-11 / 139.00元
和第2版相比,本版内容上*大的变化是,从以IA32和x86-64为基础转变为完全以x86-64为基础。主要更新如下: 基于x86-64,大量地重写代码,首次介绍对处理浮点数据的程序的机器级支持。 处理器体系结构修改为支持64位字和操作的设计。 引入更多的功能单元和更复杂的控制逻辑,使基于程序数据流表示的程序性能模型预测更加可靠。 扩充关于用GOT和PLT创建与位置无关代码的......一起来看看 《深入理解计算机系统(原书第3版)》 这本书的介绍吧!