Mapreduce

前言 我是一个记忆力不怎么好的人，很多大大小小的经历，过去了之后只会留下一个大概的印象，细节则会随着时间的流逝逐渐淡去。于是从今天开始，我会将一些学习和生活上的心得发在这个博客上，既为了分享也为了记录。虽然我不是一个爱码字的人，我的博客也不会有多少人看——所以非常感激正在看这篇文章的你——但是我也会尽量写得认真一点。 由于读研选择了边缘智能这个方向，而边缘计算又是从云原生的概念中延伸出来的，所以我觉得有必要在第一年对一些分布式系统相关的知识进行补全，MIT6.824是我的第一个计划。MIT6.824这个分布式系统课程有四个广受好评的实验，这里先挖个坑，希望能在一个学期内完成它们并记录下来。当然我的代码写得并不好，大家看看图一乐就好，有什么改进的建议也非常希望能够联系我。 什么是MapReduce MIT6.824第一个实验是实现一个MapReduce，这是谷歌最早的用于处理大规模数据的分布式计算模型，为复杂的计算任务提供了可扩展性和容错性。 对于一个工作，可能是统计单词数量或者统计单词出现位置，MapReduce将它分为Map和Reduce两个任务，Map过程是Map Worker将初始内容按要求处理成一些键值对，并且根据键的不同，将这些键值对分类保存起来，以提供给不同的Reduce Worker，这个分类保存的过程也就是Shuffle；Reduce过程则是将这些键值对进行进一步归并，按照键将所有的值聚集在一起，得到最后的结果。下面的伪代码是MapReduce的一般形式。 map (k1,v1) → list(k2,v2) reduce (k2,list(v2)) → list(v2) 在原论文中，除了阐述了MapReduce的工作过程，还提出了很多实际实现上的优化，如Combiner Function，Backup Task等。这是它的论文链接：https://research.google/pubs/pub62/，在这里就不再细说了。 RPC部分 实验使用Golang作为编程语言，并通过开启不同的进程来模拟不同的节点。而对于模拟节点之间的通信，则使用Unix domain socket的跨进程通信，Golang的RPC库的具体细节就不再本文中赘述了。 接下来分析模拟节点的通信。首先Worker之间并不需要通信，而对于Coordinator和Worker之间的通信，只需要以Coordinator作为RPC服务器，并实现Worker的RPC调用，用于Worker申领工作和Worker完成工作后汇报。接口定义如下，GetTask用于Worker向Coordinator申领工作，MapTaskDone和ReduceTaskDone则是Worker完成工作后向Coordinator汇报。 type GetTaskArgs struct { } type TaskType int var ( TaskTypeOff TaskType = 0 TaskTypeMap TaskType = 1 TaskTypeReduce TaskType = 2 TaskTypeWait TaskType = 3 ) type GetTaskReply struct { JobId string TaskType TaskType TaskId string Content []string NReduce int64 ReduceTaskIndex int64 } type MapTaskDoneArgs struct { MapTaskId string IntermediateFileNames []string } type MapTaskDoneReply struct { } type ReduceTaskDoneArgs struct { ReduceTaskId string OutputFileName string } type ReduceTaskDoneReply struct { } Coordinator 首先关注Coordinator的结构体定义，MapReduce对于每一个新的工作都需要指定Coordinator，所以需要有一个唯一的JobId来标识该工作；同时需要一个状态变量来指示工作现在进行到什么阶段，并保存每个MapTask和ReduceTask的状态；显然这个结构体需要被来自不同的节点修改，所以需要在每次修改时加锁，防止出现Data Race，因此Mutex变量也作为结构体成员保存。...