MIT 6.824分布式系统课程,是一门著名的讲解分布式系统设计原理的课程。通过课程讲解和实验结合来学习分布式系统设计原理,实验和课程安排见课程表

前言

我为什么要学习这个课程?之所以会接触到这门课程,是之前在表示对分布式系统感兴趣时一位基友介绍的,由于种种原因并没有开始学。直到最近,开始研究分布式缓存系统的设计才重新开始。有读过笔者之前的文章可能知道,笔者对redis的研究内容比较感兴趣,后面对redis如何做分布式缓存比较感兴趣,于是开始查资料,后来发现etcd在这方面也很强,在学习etcd过程中又了解到了到了raft协议,接着就查到了这门课程中有介绍Raft协议的论文以及相关的实验,刚好得知2020年春季的课程有官方版的视频且被热心网友分享到B站了,再加上完成实验需要用go语言来实现,基于学习分布式系统设计原理和实践go语言的目的,于是就开始学习这门课程。

实际上,etcd和redis是完全不一样概念的东西,etcd主要用于分布式锁以及集群核心配置,核心特性是高可用;而Redis是内存型数据库,目的是做分布式缓存,保存数据。

准备资料

学习这门课程,是先阅读了课程主页的介绍,接着根据课程表去学习,课程表里说明了先阅读论文后再去上课(或者看视频),要先看论文后再去看视频,否则看视频时教授在讲什么都不知道。

上课步骤就是:读论文->看视频->做实验。

MapReduce简介

通过学习论文、课程视频以及完成了实验,对MapReduce有了个初步的认识,在这里总结一下我的理解。

MapReduce,本质就是一种编程模型,也是一个处理大规模数据集的相关实现。之所以会有这个模型,目的是为了隐藏“并行计算、容错处理、数据分发、负载均衡”,从而实现大数据计算的一种抽象。

MapReduce的编程模型:

  • map:接收一组输入的key/value键值对,处理后生成一组被称为中间值的key/value键值对集合。

  • reduce:输入是map生成的key/value键值对集合,合并中间值集合中相同key的值。

整个处理过程的抽象过程如下:

在分布式系统中,除了程序以外还有很多需要考虑的问题,比如并发、容错处理等等,对于分布式的MapReduce,执行概览看下面这幅经典的流程图:

从图里可以看到,Map和Reduce程序分布在多台机器,取出分片数据来处理,数据可以被多台机器并行地处理,而如何分发数据及程序的管理由Worker和Master组成。执行的流程大致如下:

  • 系统会启动一个或多个Master,需要执行任务的机器启动Worker来处理任务。Master主要职责是分配任务给Worker,Master可以随机选择空闲的Worker来分配任务,或者Worker主动向Master请求任务;

  • 获得map任务的Worker,读取数据分片,生成一组key/value键值对的中间值集合,并将数据写到本地文件,这里每个map任务数据分为R份(Master创建reduce任务的数量),通过用户定义的分区函数(如hash(key) mod R)决定将key存在哪个文件;

  • 获得reduce任务的Worker,通过远程调用请求数据,数据加载完毕后,对数据进行排序,之后遍历数据,将相同key的数据进行合并,最终输出结果;

  • 当所有的map和reduce任务完成了,整个MapReduce程序就处理完毕了,Worker得到处理后的数据,通常会保存在不同的小文件中,合并这些文件之后就是最重要的结果。

以上就是我对MapReduce论文的理解总结,还有其他的本地化、任务粒度、合并和排序程序、性能等等话题,因为在实验里还没很深的印象,所以这里暂不进行说明。

另外要重点关注的是容错处理,如果Master中断、Worker程序崩溃,这些情况要怎么处理?论文里提到的解决方案是将处理结果保存在临时文件中,等到任务真正处理完才写到待输出文件里。

实验完成之路

无法入手

读完MapReduce论文后,去看课程的前两节视频,听懂了大部分,然后兴致勃勃开始做实验。代码拉下来之后,发现根本没法下手,对着实验题和代码苦恼了一个晚上,只知道实验1就是要实现一个分布式的MapReduce,但是看代码已经有了map和reduce函数,根本不知道要做什么,感觉还没开始就要结束了。

反复学习资料

第一次开始做实验失败之后,花了几个晚上将论文反复看了两遍,再回去看视频,在第二次的学习里,印象更加深刻了,再反复看题目的说明,说明里提到每次修改完程序后,都要执行test-mr.sh,里面包含了很多测试用例,只要通过了所有测试用例,那么实验就算完成了。于是去看测试用例文件,再结合题目描述,终于知道要做什么了。

测试先行,阅读test-mr.sh可以发现,里面主要包含了5个测试用例:单词计数mapreduce、索引mapreduce、并行map、并行reduce、程序崩溃。比如单词计数,检查的步骤是先运行mrsequential.go输出一个文件mr-correct-wc.txt,接着启动mrmaster和mrworker,得到结果后合并为mr-wc-all文件,比较两个文件内容一样就说明通过该用例了。那么要完成实验要,可以先看看mrsequential.go里面做了什么,写一个分布式程序去实现mrsequential.go的功能。

只要完成了以上的5个测试用例,实验就算完成了,而实际上map和reduce程序已经实现好了,那么需要做的是实现论文里提到的master和worker:

1、如何分配任务?map和reduce任务如何分配?(用例1、用例2)

2、如何实现并行处理?(用例3、用例4)

3、怎么判断Worker崩了?Worker失败后,如何恢复,如何处理正在处理中的任务?(用例5)

4、任务处理完成后,结果如何处理?

5、Worker和Master之间的通信通过rpc通信,如何维持两者间的状态?

理清了需求是要做什么以后,接下来就是设计和编码了。

系统设计

只要是程序,设计起来都不外乎数据结构和算法,对于这个实验而言,也是如此。

数据结构

定义Master和Task的数据结构如下:

type Master struct {
	nReduce             int
	nMap                int
	mapTasks            []Task
	reduceTasks         []Task
	state               int // MASTER_INIT;MAP_FINISHED;REDUCE_FINISHED
	mapTaskFinishNum    int
	reduceTaskFinishNum int
}
type Task struct {
	State          int // TASK_INIT;TASK_PROCESSING;TASK_DONE
	InputFileName  string
	Id             int
	OutputFileName string
	TaskType       int // MAP_TASK;REDUCE_TASK
	NReduce        int
	NMap           int
	StartTime      int64
}

实现流程图

根据对论文以及实验题目的理解后,设计Master和Task两个结构体,要实现的功能如下图:

1、启动Master后,Master状态为INIT,并根据启动参数初始化map任务

2、启动Worker,请求Master分配一个任务,然后处理任务(map/reduce)

3、处理完成后通知Master更新任务状态为完成;每次有任务完成时,检查Map/Reduce任务是否全部完成,根据完成进度更新Master状态

4、所有任务完成后,Master状态为REDUCE_FINISHED

崩溃处理

关于处理worker崩溃,实验提示里提到,Master不能明显区分出Worker是处理超时还是崩溃了,所以需要设计一个超时时间(如10秒),如果任务超时了,就认为任务未完成,下一次再重新分配。实现是在Master分配一个任务时,初始化一个开始时间,Master分配任务时,检查进行中任务,如果任务还未完成且超时了,就重新分配该任务给Worker。

ALL PASS

所有测试用例都通过的那一刻,内心有一份小小的激动,仿佛上大学时通过了一道实验题那种感觉。

Q&A

分享几点学习中遇到的问题:

1、学习这个有什么用?

这个问题比较尖锐了,我的理解就是,如果对分布式系统感兴趣,想通过实践来强化对分布式系统的理解,那么学习这个课程会有帮助。如果不感兴趣的话,那么这篇文章对你没有什么用。

2、如何开始学习?

课程主页,根据课程表安排,先看论文,在看视频,理解个大概后开始做实验,然后再看论文和视频加深理解。

3、看完了视频,实验程序怎么跑起来?怎么开始写下第一行代码?

准备一点Go语言的基础,开始做时多看题目的提示,比如提示的第一点说到,让代码跑起来的第一步就是修改mr/worker.go的Worker函数,发一个RPC请求到Master,请求一个任务数据。

4、论文、课程和题目都是英文版的,看不懂怎么办?

硬着头皮看,不懂的就去翻译,当然可以看中文版,网上有很多资源。课程视频有热心网友做了个中文字幕,可以看中文字幕。

另外,多说一句,还是推荐尽量看英文版的,并没有崇洋媚外的意思,只不过对于程序开发而言,英文能力还是一个必备技能,因为平时查问题的时候都是英文资料比较多,而且读一手的资料是最好的,这篇文章也只不过是我消化完的知识分享,有可能论文和课程里还有很多我看不到但是你看得到的东西。

5、有代码链接吗?

程序员名言:talk is cheep, show me the code.但是由于课程强调了尽量不要看别人的实现,也有人放到Github被MIT要求删除过,所以笔者就不共享全部代码了,如果有需要可私下交流。

总结

通过学习前两课,完成MapReduce这个实验,对分布式系统有了一个最表面的认识,还谈不上掌握,这只是一个最简单的实验,更重点的课程和实验还在后面,路漫漫其修远兮。

如果你也在学习,希望这篇文章对你有帮助。欢迎有兴趣的同学来一起学习讨论。

原创文章,文笔有限,才疏学浅,文中若有不正之处,万望告知。

如果本文对你有帮助,请点个赞吧,谢谢^_^

更多精彩内容,请关注个人公众号。