分布式系统基础-Raft算法
注意:这篇文章是我在阅读Raft算法的论文之后的一些想法，记录下来．其中可能有些地方表述的不准确，也可能我理解有误．所以请各位还是先阅读Raft算法论文<<In Search of an Understandable COnsensus Algorithm>>然后再读这篇文章．防止我误人子弟．
简介
学习分布式系统的朋友应该都知道，分布式一致性问题一直是一个很难的问题．针对这个问题，最早提出的算法是Lamport大神的Paxos算法，但是这个算法由于难于实现，以及不易于理解，而被人诟病．基于此，Standford大学的博士Diego Ongaro和John Ousterhout就发明了Raft算法．
Chubby的作者说，世界上只有一种一致性算法，那就是Paxos算法，其他的算法，不是Paxos算法的简化版，就是错误的．我觉得Raft就是Paxos算法的一个简化版本．事实上它也确实是．
Raft的整体架构，我认为是结合了Primary-Backup 模式以及 State Machine模式，关于State Machine模式，前面我在一篇文章中，专门介绍过，文末我会附上这篇文章的链接，这里也不再介绍了．而Primary-Backup模式，也早已被大家所熟知，它是一种主从结构，平时只使用主节点来响应客户端请求，然后主节点可以有好几个备用节点，一旦主节点挂掉，备用节点就顶上．
关于Primary-Backup模式以及State Machine的介绍，请大家查看文末的链接中，Fault Tolerant Services这一篇文章．
在Raft算法中，就有这么一个专门的Leader节点，这点便是对Paxos算法进行的简化，在Paxos算法中，可以有多个Proposer(Proposer相当于这里的Leader节点).而且Leader有且只能有一个．其他的节点均为Follower节点．在Leader节点以及Follower节点中，均存在一个状态机，Leader节点在接收到客户端的请求之后，会先保存到本地的Log Entry队列中，然后将其发送给Follower节点，一旦收到多数Follower节点的响应，Leader节点便会告知客户端操作成功并返回相应的结果，然后提交Log Entry并通知Follower节点提交Log Entry.写请求是上面的那个流程，而如果是写请求呢，则直接从Leader节点的本地状态机中读取相应的数据并返回给客户端．
我们这么一看，实际上它就是一个结合了Primary-Backup模式以及State Machine模式．
细节我们会在后面的小节中讨论．
Raft算法中的一些概念
在上一小节中，我们大体介绍了Raft的工作流程，但是，这是不够的．我们还需要详细考虑其实现．
那么在此之前，我们先了解一下Raft算法中的一些概念．这些概念我们不会进行翻译，因为我当初在读这篇论文的时候，翻译这些概念的时候，让我有点懵．
我们先说Log Entry．我们把客户端请求执行的命令，放到一个队列中，其中每一条要执行的命令，都把它封装一下，加上一些其他数据，变成了一条Log Entry.
Log Entry中，存储的除了要执行的命令，还有term.terms是Leader的标志，表示是哪个Leader提交的命令．因为在这个Log Entry队列中是还存储之前的Leader提交的命令的，所以需要term.不要误会为可以同时有多个Leader.当时,term还有其他作用，我们后面会介绍．
在Log Entry队列中，还有一个其他的概念，是index.它表明Log Entry在这个队列中的位置．就跟数组中的元素在数组中的位置一样．具体的用处我们也会在后面介绍．
Raft算法中节点的三种状态
在Raft中，存在以下几种类型的节点:
- Leader.Leader负责接收客户端发送的请求，通知Follower节点以及响应客户端．
- Follower.集群中除Leader节点之外的节点，都是Follower节点．Follower节点负责维护一个状态机，接收Leader发送来的Log Entry以及其他命令．
- Candidate.当集群中的Leader不可用时，Follower节点就会转换成Candidate状态直到选举出一个Leader.
Raft算法的具体过程
我们在上面粗略的介绍过Raft算法的处理过程．这里我们详细的介绍一下．
首先，集群启动时，选举出一个Leader节点，然后其他的节点都处于Follower状态．然后，客户端随机选择集群中的一台机器，并访问它，如果这台机器是Follower节点，那么它会拒绝客户端的请求并且告诉它Leader节点的访问地址．当Leader节点收到客户端的请求之后，正如上面我们说的那样，它会生成一个Log Entry并保存在一个队列中，然后将这个Log Entry广播给全部Follower节点，当收到多数Follower节点的响应时，就会给客户端回应并且提交这个Log Entry.提交一个Log Entry的意思是，将其对应的命令应用到状态机．在这里，Leader节点还会同时将这个提交Log Entry的命令广播给其他节点．
当然Leader节点也可能会由于网络延时的问题，而没有收到多数Follower节点的响应．那么Leader节点就会对那些没有收到响应的节点，重复发送请求，直到收到响应．
当Follower节点收到Leader命令的提交Log Entry的命令时，就会将其对应的命令应用到状态机．并且，在其Log Entry队列中的index小于需要提交的Log Entry的index的Log Entry,也会同时被提交．
当Follower节点在一定时间内没有收到来自Leader节点的请求时，便会认为Leader节点出故障了，于是，便会把它自身变为一个Candidate节点，进行选举过程．如果其他的大多数节点同意让它做Leader节点，或者收到了其他新任命的Leader的消息，那么它便会停止选举过程，重新转换为Follower节点．
所以，为了防止Leader其实并没有出现故障，而是由于一段时间内确实没有收到请求，而没有给Follower节点发送请求，Leader节点需要定期发送给Follower一个请求，表明它其实还在正常工作．
同样，在选举过程中，为了让其他的Candidate知晓已经选举出来了Leader,所以Leader需要在上任的时候，给其他的Candidate发送请求，表明它是新选出来的Leader.
各个节点上需要存储的数据
Raft算法中的RPC
从上面的过程中，我们可以看到，至少需要两种RPC操作:
- AppendEntries RPC: Leader在将Log Entry广播给Follower时，便是用的这种RPC.
- RequestVote RPC:当Candidate需要其他的Candidate协助它被选举为Leader节点时，就需要向其他的Candidate节点发送这种RPC.
关于这两种RPC的具体细节，这里我直接就贴出来了，论文中描述的已经很详细了．
还有其他的一些操作，这里也一并列出了:
Raft算法中Leader的产生
每一个节点上，都需要存储一些配置，一些数据，比如，当前是哪个Leader主事，用currentTerm表示．在Candidate节点A进行选举时，它需要提出一个更大的term,并发送给其他的Candidate节点B和C．如果Candidate节点B和C发现Candidate A提出的term比它当前维护的currentTerm大，并且Candidate B和C的voteFor为空或者它自己，并且Candidate B的Log Entry队列中的记录比他的更新，就告诉Candidate B，我选举你为Leader啦．如果上述三个条件中的任意一个不满足，则不选举其为Leader.
那么上面说的记录更新是什么意思呢?
- 如果Log Entry队列中的最后一个Log Entry的term不相同，那么具有更大的term的那个Candidate中的Log Entry队列更新．
- 如果Log Entry队列中的最后一个Log Entry的term相同，那么Log Entry队列更长的那个Candidate更新.
如果集群中仅有三台机器A,B,C，根据上面的过程,Candidate B就可以成为Leader了．因为加上他自己同意他自己成为Leader,已经达成集群中多数机器同意的条件了，那Candidate B现在就成为Leader了．
如果Candidate B在超时的时间范围内，既没有成为Leader,又没有其他的Candidate告诉它，我成为Leader啦，那么Candidate B就保持Candidate的状态，继续进行选举．
上面我们用三台机器举例，那么如果集群中有四台机器，我们假设它们分别为A,B,C,D，那么很可能有这么一种情况产生，就是A和B都同时获得了两票，谁也不能成为Leader.在Raft中，通过每一台Candidate随机选择一个选举超时时间来避免这个问题．这个选举超时时间应该满足下面这个公式:
broadcastTime << electionTimeout << MTBF
在上面的那个公式中，broadcastTime代表的是机器给其他机器发送RPC的平均时间，包括去和回．MTBF代表机器故障的平均时间．这两个变量都是集群中的一些属性，我们能够选择的只能是electionTimeout.取决于所采用的存储技术,broadcastTime可能在0.5ms~20ms,因此，electionTimeout就可能是10ms~500ms.
日志复制
我们知道，刚被选举出来的Leader的Log Entry，一定是最新的，最全的．为了保持全部的节点上的状态机状态一致，我们需要让它们执行相同的命令序列，所以，我们需要将Leader节点上的Log Entry复制到Follower节点上．
既然要将Leader节点的Log Entry复制到Follower节点上，自然存在Follower节点上的Log Entry和Leader节点上的Log Entry冲突的问题．比如，Follower节点上的Log Entry队列为:[{1, a <- 1}, {1, a <- 2}, {2, a <- 1}],而Leader节点上的Log Entry队列为:[{1, a <- 1}, {1, a <- 2}, {2, a <- 3}]．我们在这里用{term, command}来定义一个Log Entry,用[{term, command}, ...]来定义一个Log Entry队列．
我们可以从上面那个例子中看到，Leader节点的Log Entries和Follower节点的Log Entries冲突了．
那么Raft是解决的呢？
我们从前面的部分，也知道了，Leader节点维护着nextIndex[]和matchIndex[]这两个变量．我们也知道, nextIndex[]代表的是下次要从那个index之后的Log Entry发送给Follower, matchIndex[]代表Follower和Leader的匹配的最后一个Log Entry的Index.当选举出来一个Leader时，会将nextIndex[]初始化为它的最后一个Log Entry + 1,将matchIndex[]全部初始化为0.
这样，当选举完Leader之后，Leader会把它的最新的一条Log Entry发送给Follower,如果这条Log Entry不匹配，那么Follower会报告一个错误信息，然后Follower节点就依次减少nextIndex[]的值，并再次进行尝试．直到Follower告诉Leader节点，诶，现在你跟我匹配了．然后Follower节点清除那些不匹配的Log Entry并替换成Leader发送过来的Log Entry.
那会不会出现清除已经提交的Log Entry的情况呢？
我个人认为是没有这个可能的．因为在投票决定Leader的时候，选择的就是具有最新的Log Entry的节点．
集群中增加或者删除新成员
这一部分，在实践中应该是必不可少的一部分．但是，说实话，论文中的这部分我是真没看懂，所以请各位还是读原文来获取这部分信息．
快照
随着时间的增加，Log Entries队列可能会越来越大．会占用大量的磁盘空间，所以，我们还需要对Log Entries队列进行压缩，以快照的形式．
Follower可以自行制作快照，但是必要的时候，Leader还是需要给Follower发送快照．一般发生在Follower处理速度慢，或者新节点加入的情况下．
一旦Follower发现Leader发来的快照中，跟它的发生冲突，那么它会放弃它的快照，而转而使用Leader的．
Raft算法的弊端
各位朋友应该已经注意到了，我们上面的讨论，都是基于Fail-Stop Failure来讨论的，并没有涉及到Byzantine Failure.
实际上，Raft算法的实现，就是假设不会发生Byzantine Failure.当然，其他人也提出了一些基于Raft算法的改进版，能够容忍Byzantine Failure.
