这篇文章实际上并不是我在阅读etcd中跟Raft相关的部分之后得出的，而是我在读了ZooKeeper中Zab的实现以及重新读«IN Search of an Understandable Consensus Algorithm(Extended Version)»这篇论文而得到的．虽然可能跟实际的实现有一点差距，但是应该不大．后面我会读etcd源码中的Raft部分，然后再写一篇文章介绍．
文末的参考资料中，有一个动画版的对Raft算法的解析，各位可以看一下．当然，很多细节方面的内容，它并没有说的很明确．
Raft算法中，各个Server具有的属性
- currentTerm：这个是Server当前的term．如果Server处于Follower状态，则其表示的是Server认为的leader的当前的term．
- votedFor：表示Server为谁投过票，也就是Server认为谁更有资格成为Leader．在一个term中，只能给一个Server投票．
- log[]：log entries．每个Log Entry都包含状态机要执行的命令，以及其term．
- commitIndex：已知的要被提交的Log的最大的index
- lastApplied：已应用Log的index
Leader还有两个特殊的属性：
- nextIndex[]：代表下次要发送给各个Server的log entry．开始时是Leader的最后一个log的index + 1
- matchIndex[]：代表Leader的log和各个Server的log匹配的位置
Raft算法的三个阶段
跟Zab算法一样，可以将Raft算法分成三个阶段，分别是Election，Synchronization，Broadcast．
Election阶段
在这个阶段，顾名思义，就是选择一个Leader．
那么什么时候需要选择一个Leader呢？有这么三种情况：
- 当集群刚开始启动时
- 当一台新的Server想要加入到集群时
- 当一台Server经过分区或者故障后，想要重新加入集群时
下面我们会拿第一种情况，即集群刚开始启动时举例说明：
- Server会先进入到Follower状态，并设置一个超时时间
- 如果过了超时时间，那么Server进入到Candidate状态
- 增加Server的currentTerm
- 为它自己投票
- 设置选举超时时间
- 给集群中的其他机器发送RequestVote RPC
- 如果从半数以上的Servers中收到Ok，则进入到Leader状态
- 如果收到来自Leader的AppendEntries RPC，则进入到Follower状态
- 如果收到其他Server的RequestVote RPC，并且当前Server的voteFor为null或者那台Server，并且那台Server的log比这台Server的log更新，则为那台Server投票
- 如果收到的RequestVote RPC的响应中，term比当前Server的term大，则重置当前Server的term为来自RequestVote RPC的term，并进入到Follower状态
- 如果在过了选举超时时间之后，还未确认自己就是Leader或者来自Leader的Append Entries RPC，则将当前Server的term+1并开始新的一轮选举
- 如果在超时时间内收到了来自Candidate的RequestVote RPC：
- 如果RequestVote RPC中的term比当前Server的更大，那么更新当前Server的term．同时，判断一下voteFor是否为null或者发送RequestVote RPC的Server，以及Candidate的log是否比当前Server的更新，如果是，那么就返回true和当前Server的term．同时，在当前term中，不能再为其他具有相同term的Server投票．
- 如果RequestVote RPC中的term没有当前Server的大，那么返回false以及当前的term
- 如果在超时时间内收到了来自Leader的AppendEntries RPC：
- 如果leader的term比当前Server的term大，那么就重置当前Server的term
- 如果leader的term比当前Server的term小，那么返回false以及当前Server的term
- 如果当前Server的log和Leader的log在prevLogIndex处的日志冲突，删除当前Server对应位置以及往后位置的log，并返回false
- 如果Leader包含当前Server没有的log，那么就将这些Log追加到当前Server的log的末尾
- 如果leaderCommit > commitIndex，则更新commitIndex为min(leaderCommit，当前Server的最后一个log entry的位置)
Synchronization阶段
在一个Server成为Leader之后，它需要将其日志同步给Follower．
Leader会做下面的操作，将其log同步给Follower：
- 向Follower发送AppendEntries RPC，其中prevLogIndex为其最后一条log的index，prevLogTerm为其最后一条log的term
- 如果收到的AppendEntries RPC的响应为true，则更新nextIndex[]和matchIndex
- 如果收到的AppendEntries RPC的响应为false并且其中的term比Leader当前的term大，那么更新Leader的term并进入到Follower状态
- 否则的话，如果只是响应为false，那么就减小nextIndex[]的值并且重试
Broadcast阶段
在这一阶段，Leader将接收客户端请求并应用到状态机.
Leader会这样做：
- 接收来自Client的请求，将其封装成一个log，保存到log[]，并且将其发送给Follower
- Follower在收到AppendEntries RPC之后，会将其添加到本地log[]并应用到状态机，然后给Leader回复Ok．
- Leader在收到半数以上的Follower的OK之后，就将这个log应用到本地状态机，更新commitIndex以及lastApplied，同时给Client回复OK.
AppendEntries RPC和RequestVote RPC
上面我们反复提到这两种RPC，却并没有深入介绍．这里介绍一下这两种RPC的请求数据以及响应数据，关于Leader和Follower以及Candidate对于这两种RPC会作何反应，上面已经介绍过．
AppendEntries RPC
请求数据：
- term：leader的term
- leaderId：有了这个leaderId，follower才能接收到客户端请求时，将其重定向到leader
- prevLogIndex：要发送给follower的log entry的index
- prevLogTerm：要发送给follower的log entry的term
- entries[]：要存储的log entries
响应数据：
- term：Follower或Candidate的当前的term
- success：是否更新成功，当其为true时，表明Follower已经成功的将log entries保存了下来
RequestVote RPC
请求数据：
- term：Candidate的term
- candidateId：Candidate的Id
- lastLogIndex：Candidate的最后一个log entry的index
- lastLogTerm：Candidate的最后一个log entry的term
响应数据：
- term：接受者当前的term
- voteGranted：接受者是否为这个Candidate投票．如果为true，则表明此接受者愿意为这个Candidate投票．
实例
上面说了那么多，都是比较理论的东西，下面我们来讨论几个场景，以及一些难题．
当一个集群刚刚启动时，此时集群中的Server均处于Follower状态．此时它们都接收不到来自Leader的Append Entries RPC，因为此时集群中压根就没有Leader．
Server在初始化时，除了会初始化为Follower状态，还会为其设置一个固定的超时时间．
假设集群中有三台Server，分别是Server A，Server B以及Server C，它们的超时时间均为300ms．
在这300ms过去后，Server A，B和C均进入到Candidate状态，此时Server A，B和C会获得一个随机分配的选举超时时间，假设这三台Server获得的超时时间为50ms,100ms,150ms．
Server A, B和C在第一轮选举中，分别为自己投票．由于在每个term中，一台Server只能投一次票，所以在第一轮选举中，无Server成为Leader．
50ms过去以后，Server A会将它的term+1，并通知其他Server为自己投票，Server B和C收到Server A的RequestVote RPC以后，由于开始时他们的term都相同，此时RequestVote RPC中的term更大，所以Server B和C会更新自己的term为从RequestVote RPC中收到的term，然后比较一下Server A中的log是否比自己的新，如果是，则为Server A投票．
那么Server A的log在满足什么条件下比其他Server的log更新呢？
- ①Server A中的log的term比其他Server的term更大
- ②Server A中log的term跟其他Server的log的term相同，但是Server A中log的index更大，即Server A的log更长
在这两种情况下，我们认为Server A的log比其他Server的log更新．
这两条还可以保证选出的leader一定包含全部已提交的log．
为什么呢？
因为当一台Server收到半数以上的Server的赞同时，才会被选为leader，而leader提交一个log时，也需要半数以上Server的同意．所以它们之间至少有一台Server相交．
注意已提交Log和已应用的Log的区别．
当Leader收到来自客户端的请求时，它会将其添加到本地log[]中，然后发送给全部Followers，当收到半数以上的Followers回复Ok的时候，它会提交这个log entry，这时Log称为已提交Log，然后，它会回复给客户端一个Ok，同时，将这个log entry应用到本地状态机，然后在下次给Follower发送AppendEntries RPC的时候，将其commitIndex发送给Followers，Follower在收到AppendEntries RPC的时候，会将commitIndex位置上及之前位置上的log entry应用到本地状态机．此时log entry被称为已应用Log．
我们可以看到，已应用Log就是已经成功应用到集群的Log，而已提交Log则是Leader收到半数以上Followers的回复但是并没有被应用到集群上的Log．
Leader并不会记录是否多半的Followers已成功应用此Log，实际上，这也完全没有意义，因为已经告诉Client成功了．所以，如果一个log已提交，它就必须应用到Followers．
所以，如果leader崩溃了，新选出的Leader必须将这些已提交log应用到集群中．
那么新的leader要在何时应用上一个leader所在的term的log呢？
最简单也最容易想到的就是，在新的leader选择出来之后，计算上个term留下的log在集群中的数量，如果过半则认为它已经被应用到集群了呗．
但是在Raft论文中，专门强调了这样做是不行的，有数据被覆盖的风险．
在解释这一点之前，我们需要明白，Raft必须满足下面的条件：
- 已经给Client请求成功的响应的log，必须被应用到状态机中．
记住这一点，我们再来解释为何不能通过计算上个term留下的log在集群中的数量来判断它是否已经应用．
这幅图是Raft论文中用来解释这样做不行的原因的例子．
在这幅图中，每个方框代表一个Log Entry，方框中的数字代表Log Entry的term，最上面的数字表示的是Log Entry的index．
在(a)时刻，S1是Leader，它的term是2，此时，它接受了一个客户端请求并成功发送给了S2，S2也保存在logs[]中了．
在(b)时刻，S1崩溃了，S5通过给S3和S4发送RequestVoteRPC并收到了成功的回复，成为了Leader，其term为3．此时S5收到了客户端请求并加到了log中，但是还未来得及向其他Server发送就崩溃了．
在(c)时刻，S5崩溃以后，S3和S4由于选举超时时间还未到，还是Candidate状态(其实处于Follower状态也无妨)，此时S1再次选举成为Leader，在S1的Synchronization阶段，会将index为2以及term为2的Log Entry复制到S2和S3，加上S1正好达到了半数以上的条件，所以这个log就被认为成功应用到了集群．
在(d)时刻，如果S1再次崩溃了，则S5必定会成为leader．那么此时，它会在Synchronization阶段，用index为2而term为3的entry覆盖掉s2,S3,S4上index为2，term为2的entry．
我们可以看到，S1认为已被集群应用的log却被S5覆盖掉了．
那么如何解决这个问题呢？
我们首先考虑一下这个问题产生的原因，就是因为在(d)时刻，S5的log确实比S2，S3，S4的更新，所以才能成为Leader并将Log覆盖掉．
那么，我们如果能够阻止S5在(d)时刻成为leader，即让其他的Server的Log比S5的更新，不就可以防止这种情况了吗？
在Raft论文中，便是通过这种方式解决的．
即，Server在将当前term的entry应用到状态机时，才顺带着应用之前的term的entry，正如前面那幅图中(e)时刻所做的那样．
其实这里数据是否被覆盖，我感觉没有那么重要，因为我们前面介绍过，选举得出的Leader一定是含有全部已提交Log的Server，所以，即使被覆盖，也只是覆盖一些未提交的log，也就是并未给Client回复Ok的log．而且，在实现中，当一台Leader宕机后，它跟客户端之间的连接肯定就会被关闭了，客户端收到的肯定是一个错误．所以，客户端如果需要的话，肯定会再次发起请求．
那么，这样的话，又有一个难点，即对于非幂等性的操作，如果Leader已经成功引用到集群，却对Client响应了一个错误，客户端再次发送一个请求，该怎么办呢？
对于幂等性的操作，这里并不重要，在发送一次就再发送一次呗，无所谓．
而对于非幂等性的操作，再发送一次就可能造成数据错误．
那么如何处理这个问题呢？
Raft论文中并没有给出明确的方案，但我在其他文章中看到过一个方案．
我们可以在客户端动一些手脚，客户端每次发送请求时，都为这个请求生成一个唯一的ID，Leader在收到请求之后，同样在Broadcast阶段将这个ID随着AppendEntries RPC发送给Followers．当客户端重试时，还是发送这个ID，Leader检查一下，如果发现该ID的请求已被处理过，则直接返回给客户端OK.
由于这个ID是随着AppendEntries RPC发送给Followers的，所以Leader上的ID的记录必然能够正确地反映出此集群已经处理的请求．
这样便能解决上面提到的非幂等性操作的问题．
总结
我们可以看到，Raft实现的是强一致性，因为全部的请求，不管是读请求还是写请求，都是先到Leader的．
同时，它也实现了CAP中的CP．
其实这些都是可以打破的．比如说，我们不想要强一致性，而只想要最终一致性，那么我们完全可以让Follower接收客户端的读请求，而不是重定向给Leader．如果我们想要实现AP，那么完全可以让分区的Server继续接受读请求．
