6.824 Lab 1: MapReduce(2016) · Snow Memory

本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循署名-非商业用途-保持一致的创作共用协议.

MapReduce框架简介

应用提供大量输入文件, 一个Map函数, 一个Reduce函数, nReduce个reduce tasks.
RPC服务器启动, 等该worker注册(Register)RPC中. 任务状态为可执行时, 调度器(Schedule)决定如何把task分配给worker和如何容错.
Master把每个输入文件作为一个Map任务, 每个任务至少调用一次doMap. 这些任务或者直接执行或者由DoTask RPC发射, 每个对doMap()的调用读取合适的文件, 对每个文件调用map, 对每个map文件最后产生nReduce个文件.
Master对每个reduce人物至少调用一次doReduce(). doReduce()收集由map产生的nReduce文件(f-*-), 然后对这些文件运行reduce函数. 最终产生nReduce个结果文件.
Master调用mr.merge(), 合并所有的结果文件为一个输出文件.
Master发送Shutdown RPC关闭workers, 然后关闭RPC服务器.

Lab1总共分为五部分

作业: 实现DoMap()(mapreduce/common_map.go)和DoReduce()(mapreduce/common_reduce.go)两个函数

DoMap功能简述:

通过inFile文件名读取文件中的内容, 将内容传入Map函数中, 返回得到Key-value对数组
将Key-value对数组通过Split函数(此处Split函数为ihash), 平均分配到nReduce个中间文件中, nReduce名字可以通过reduceName构造出来. 其中, Key-Value写入文件使用了Json进行序列化(将Key-value数据结构序列化为字符串).

DoReduce功能简述:

Map生成nReduce个中间文件后, DoReduce遍历读取这些中间文件, 通过序列化器拿出所有的Key-Value对, 然后将Key-value放入新的数据结构(该数据结构使key相同的value值合并, 自然想到使用Map数据结构)
对所有的key进行排序, 生成有序的key数组. 然后对key-values(注意此处key对应的值为一个数组)进行Reduce操作, 并将结果写入新的文件(文件名由mergeName获得).

运行mapreduce/test_test.go时需要注意, 只运行TestSequentialMany, TestSequentialSingle两个测试用例, 将其他三个测试用例注释掉.

Part I 完成后, Part II 没什么难度了, 一个简单的Map-Reduce词频统计的任务, 对输入文件内容进行分词, 然后将词发射出去(词频默认为1), Reduce将values进行加和就完成了.

整体流程: 启动一个Master RPC服务器, 服务器调用schedule来调用Map/Reduce任务; 启动多个Worker RPC服务器, 并将Worker的端口信息注册到Master服务器的数据结构(channel)中

注意事项: 应该保证schedule中所有的goroutine全部完成后才能返回. 所以应该使函数阻塞直到所有的goroutine完成.

Go中有两种方法可以保证进行同步程序:
参考文章: Go goroutine同步

Master来处理失败的workers, 当某worker上的Map/Reduce任务失败后, 需要将这个任务转移给其他worker来执行.

在设计调度任务函数schedule()的时候考虑容错性, 判断在Worker上调用RPC是否成功, 若失败则重新分配一个新的worker服务器来处理task. 整个容错逻辑可以放到一个for循环中, 只有当任务成功调用才break跳出循环.

构建一个倒排索引Map/Reduce任务

拿到一个网页url和url对应网页文本, 对网页文本进行分词, 将每个词作为key, 网页url作为value发射出去

拿到一个关键词key, 和关键词对应的url集合, 首先对url进行去重(可能一个url中出现多次关键词), 然后对url进行排序(可以不排序), 最后根据需要的结构对整个url集合作拼接(url集合的长度即为url中出现关键词的url个数), 最后将关键词和拼接字符串发射出去

个人完成Lab1的代码托管在Github上, 仅供参考, 第一次使用Go语言, 有些不太熟悉的地方, 若有更好的方法欢迎指导.