System Design

raft基础 一个raft集群一般来说有5个服务器结点，能让系统承受其中任意两台的down掉。每个服务器一共有三个状态，leader,follower,candidate,follower被动的接受来自candidate与leader的消息并作出回应。leader handle了所有了所有的客户端的请求，如果follower接收到了请求，会重定向到leader那去。 raft把时间分成任意长的阶段，从选举开始，每个阶段都是一个连续增长的整数，至少有一个或者多个candidate会尝试成为leader。如果有一个candidate成为了leader，则接下来的term，它将是leader。在一些情况下，选举会出现，平分票数的情况，这种情况，term将会维持没有leader的状态到结束，到下一次的新的选举。 不同的服务器 可能感知不到不同的term之间的转换，或者根本不知道有选举这回事，在这其中，term充当了一个逻辑时钟的作用，能让服务器能检测过时的信息，比如落后的leader。每一个服务器有一个current term number，随着时间增长，当服务器之间通信时，current term 会被 交换，如果有一个服务器的term小于别的，就会更新自己的，如果一个canditate或者leader发现它自己的term过时了，就会马上转变成follower，如果服务器收到了一个过时的请求，则会直接拒绝这个请求。 raft的服务器之间用rpc请行通信，其中RequestVote用于canditate 来进行选举，AppendEntries 用于分发log与当心跳包（事实上是无论收到一个请求，都应该重置time out chekcer）。另外 还有一个转移快照的rpc。之后 再说。 选举 raft使用心跳机制来触发选举。当服务器启动的时候，它们都是follower，follower在收到来自leader或者 candidate合法的rpc请求之前，一直是follower，leader会周期性的发送心跳包来保持leader的权威性，心跳包是一个空的AppendEntries，不带有Log entries。当一个follower一个election timeout后没有收到心跳包，则认为leader没了，将开始一轮选举，选出一个新的leader。 为了开始一次选举，follower会给current term+1然后转变成candidate，然后投自己一票，然后同时发起RequestVote RPC给别的服务器。一个candidate会持续到以下三件情况出现，(a)它成了leader，(b)其它服务器成了leader(c)一段时间过去后，没有server成为leader。这将在之后讨论（应该是过一段时间重新发起） 一个candidate如果收到了整个集群中大多数的投票 (with same term)，就会成为leader。每一个服务器最多只能投出一票。这个大多数 的规则决定了，在一个term里，只能一个candidate成为leader。一旦candidate成为了leader，则会开始发送心跳包给其它所有的服务器，来保证自己的权威与阻止其它服务器发起选举。 在投票的过程中，可能 会收到来其它服务器发来的AppendEntries RPC来声称自己是leader，这种情况，看leader的term与自己的current term的大小，如果比自己大，那别人就是leader，自己将退回到follower的状态，如果比自己小，就是拒绝别人的RPC call，并继续进行选举。 一个选举如果选不出一个leader那就是分裂的选举，即没人得到大多数票，这种情况下，会等待超时直到下一次的选举，但是如果 没有做额外的操作，分裂的选举会不停的进行下去。 raft采用了随机的选举超时来保证split vote是很少见的并且能快速的被解决。即每一个服务器的election timeout不一样，在重新发起选举的之前会等待这个timeout，timeout少的会先发起选举。一般的timeout会选择一个区间比如150-300ms之间。这样会有一个服务器超时完成并在别的服务器节点超时完成前完成选举。 Log replication 一旦一个leader被选举，那它就开始接受client的请求，每一个client的请求都包含一个命令，这个命令会被 replicated state machines执行，leader将会把这个command append到日志中去，作为一个新的entry，然后用AppendEntries 分发到其它的服务器。 leader会永远的尝试去写入follower log entry，直到所有的log entry都被 写入。 leader决定什么时候日志被 commit，当大多数的服务器都复制了一份entry后，就会提交，也会提前之前的entries，论文中设计了两个重要的属性 如果不同日志中的两个Entry有一样的index跟term，那他们存的一个东西 如果不同日志中的两个entry有一样的index跟term，那他们之前的所有entry是相同的。 属性1保证了，在给定的term与index中只会创建一个entry，属性2保证了一致性的简单性。 如果follower发现leader发过来的index跟term在自己的log里没有，那么会拒绝这个新的entry。（因为在消息中包含了这条新的之前的index跟term，所以可以检测之前的一致性，如果之前的都不一致就根本不会append这个新的） 在Raft中，处理leader与follower的不一致性是通过强制把leader的log记录复制给follower来完成的，这意味着follower的log的冲突部分，会被完全覆盖。 为了使follwer的log保持一致，leader必须找到leader与follwer最近的一个一样的entry，然后把这个之后的log都发给follower。 leader对于每一个follower都维护了一个index，这个index是leader将要发给follower的下一个index，当一个leader上台后， 会把这个next index初始化为自己log中的最后一个index，如果有follower的记录与leader不一致，那么在下一次Append Entries RPC的一致性检查中失败。当这个调用失败后，leader将决定下一个next index是多少，最终，next index会在重试中到达leader与follower一致的地方。当RPC调用成功之后，leader会把之后的记录全发给follower，这样就follower就完成了与leader的一致性同步。 ...

前言 MIT 6.824是著名的分布式课程，课程包含了视频，讲义，与作业。而本篇博文将阐述6.824课程的第一个作业的一些思考与解法，记录一些关于Map Reduce系统的思考。 Map Reduce Map Reduce作为“谷三篇”的第一篇，出名不是没有原因的，jeff dean的超前思想构建了谷歌搜索的基石，使得谷歌在超大应用系统的构建上得心应手。而Map Reduce则是一个基石中的基石。 Map Reduce的思想就是分布式的，系统中包含一个Master和许多个Worker，Master负责调度Worker与任务分发，容灾等等，Worker则与Master通信，请求任务。 而Map Reduce则把一个任务拆分成Map与Reduce部分，简单来说，Map部分是把输入通过用户定义的Map Function输出成中间文件，再把中间文件作为输入给Reduce，Reduce把中间文件调用Reduce Function，然后合并并输出。 整个系统如图所示。如论文所说，这些文件可以是在本地机器上，也可以在分布式文件系统中，这并不影响整个系统框架。 具体Map Reduce的思想可以读一下Google的论文。 MIT 6.824 Lab1 现代的6.824比以前的要难许多，我做过之前的lab1，当时就把Map Reduce的框架都搭好了，只要写两个函数就算通过了。而这个2020的6.824要求对Go熟悉且要把MapReduce整个实现一个大概出来，前后花了不少时间去思考要怎么来做这个实验。 思考 当我们拿到Lab的时候需要做什么？需要思考我们要实现哪些东西。MIT的代码里只给了几个RPC的函数，然后在这个基础去实现Map Reduce。 而我们要做的有： 实现Master管理，这其中需要管理任务的状态，Worker请求任务的处理，Worker任务完成报告的处理，Worker失败超时的处理。 实现Worker请求任务，对Map部分任务的处理，对Reduce部分任务的处理，还有任务完成的上报。 还要实现一个文件锁，不能让Goroutine之间产生Race。 实现 我的一些方案是在Master的结构体里管理两个Channel，当Master启动之后，把任务发给MapChannel，然后在另一个Goroutine里面对这个MapChannel进行读取，Channel如果不设置的话，一方没有读，写方会阻塞住，所以只有Worker进行请求任务之后才会继续生产任务。当Map部分完成后，再启动Reduce部分，生产Reduce任务到ReduceChannel。 我们在每个请求任务的RPC返回之前再开启一个Goroutine来等待Worker的任务完成报告，这里我们用到了Go的select语法，并使用一个timer，如果超时就把这个任务再次Push进TaskChannel，即使任务失败了，也能再次把任务分发下去。 对于Worker部分的代码来说，完全就是苦力活，可以看看官方代码里那个非分布式的Worker里代码，可以直接复制过来。Worker如果联系不上Master了，马上退出进程，这样就不用实现一个退出语义了。（其实是我不知道怎么让Master去通知Worker退出） 代码 这里只给出一些结构体的定义： Master: type Master struct { MapTaskList []*MapTask ReduceTaskList []*ReduceTask MapTaskChan chan *MapTask ReduceTaskChan chan *ReduceTask CompleteMapTaskNum int CompleteReduceTaskNum int mu sync.Mutex files []string nReduce int } Task Def type MapTask struct { TaskNum int TaskStatus TASK_STATUS FileName string NReduce int } type ReduceTask struct { TaskNum int TaskStatus TASK_STATUS FileName []string NReduce int } 一些吐槽 这次写了蛮久了，因为不是很熟悉Go，学了一会才知道有select这种语法，然后官方的hint里让人把中间文件命名为mr-x-y.txt，这样其实挺坑的，因为testmr.sh里面没有把这个中间文件删除掉，而在文件读写的时候因为hash的缘故，不会把所有的文件清空，这样导致前一个test的中间文件会影响到后一个test。所以我加一个函数，把所有的中间文件清空的，这样也算是TDD吧。 接下来就是要做Lab2了，完成一个Raft。 ...