共识算法
介绍
Raft是常用的一致性算法，在分布式系统中，能够很好的解决非拜占庭共识问题。在一个大小为2N+1的非拜占庭分布式网络中，即所有节点都诚实的进行通信，Raft算法能够容忍N个节点故障。以下链接有Raft介绍的动画，应该能帮助更好的了解 (http://www.kailing.pub/raft/index.html)
流程
上面的动图是一个正常运行的Raft网络的工作流程和状态，绿色节点是外部请求服务的客户。Raft网络是常规的Master-Slave/Leader-Followers架构，图中的Node B便是Raft网络中的Leader节点，外部节点与Raft网络的交互主要通过与Leader节点通信来完成。Raft的工作本质是对节点日志的维护，为了使网络中大部分节点都达到统一的日志状态，即拥有一模一样的日志记录，Leader需要通过两段式提交的方式与Followers进行日志条目的确认。如上图所示，Node B接收到’ SET 5’请求后，会将此条目记录进入prepare状态，而后将’SET 5’发送给Node A和C，两个节点收到条目后会判断是否接受此条目，如果接受则也将此条目记录并进入prepare状态，然后回复Node B。Node B在接收到大部分节点回复的确认后，将会把记录的条目commit，而后回复绿色的用户，同时也将发送commit信息给所有的Followers，Followers接收到后，也会相应将‘SET 5’条目commit。如此网络中的节点的日志状态都达到了一致。
定时器与初次选举
在Raft网路构建初期，网络中没有Leader节点，所有的节点都是Followers，那么为了对外提供服务以及统领网络中的节点，Raft需要有一个自发的选举机制来从Raft网络中选举出一个Leader节点。于是这里就需要提到Raft网络中，除了Leader和Follower以外的第三个角色，也就是Candidate(候选者)。成为候选者的节点将会发起选举。那么节点如何从Follower成为Candidate呢？这里就又需要提到Raft节点的计时器机制。每一个Follower节点都带有一个计时器，你可以当作一个倒计时沙漏，如果在时间结束前，节点收到了Leader发来的信息，那么Follower节点便会将计时器回归初始状态，从头开始计时。可如果计时器触底后也没有收到Leader发来的消息，当前Follower便会转变成Candidate并发起选举投票，其他的Follower在接收到选举请求后会判断是否接受，并返回结果，如果当前Candidate是收到了超过半数的同意便会转变成Leader节点，并通知其他节点。
再次选举
发生条件
网络中的节点可能会产生故障，如果Followers在一定时间内没有收到Leader节点 的消息，那么当前节点就会判断Leader节点出现了故障，那么为了保障系统的可用性，当前节点的角色会从Follower变更为Candidate。这种有以下两种情况会发生再次选举：
- Leader节点失联。
- 产生网路隔离，即节点间的交流通道被关闭了。
计时器细节
已知当一个节点的计时器触底时会发起选举，那么如果多个节点拥有时长一致的计时器，则会发生多个节点同时变成Candidate发起选举的情况，那么网络中的节点可能会被划分为多个派系。如果其中一个派系拥有了大部分的节点，那么这种情况不会对选举产生影响，因为只有被大部分节点选中的Candidate才会变成Leader并通知所有其他节点。但是如果节点分散导致没有一个Candidate获取到半数以上的同意票，那么当前选举便无法选出新的Leader，只能等选举时间过后重新发起选举。为了解决这种情况，每个节点的计时器一般被设定为150ms~300ms间的一个随机时间，这样可以大概率保证所有节点的计时器时限都不同，从而一定程度上避免同时选举的情况发生。而Leader为了维护领导地位则必须每150ms内给所有的节点发送心跳包来重置他们的计时器，以免有节点变成了Candidate。
选举请求接受准则
1. 最新的任期
任期是一个不断累加的整数值，所有的正常的节点都应当在相同的任期下运行，新的任期的产生是在一次新的选举发起的时候。
2. 最新的log
Raft网络的工作流程就是一个日志复制的过程，所以每一个将要成为Leader的节点都必须具备被大多数节点认可的最新的log，以保证leader中拥有所有已经被commit的log (因为被commit的log都接收到了大多数的节点的记录与认可)。这就是要保证Leader completeness。
3. 投票限制
每个节点在每个任期只能头一次票，防止有多个Candidate都受到了大多数的同意票，保证了一个任期只能产生一位Leader (Election Safety)。
多Leader的情况
在上面提到的网络隔离这种情况发生时，Raft网络中可能诞生多个Leader，如下图所示
图中的Node B和Node E都是Leader，Term 1即任期1，Node B是Term 1时期的Leader，可是发生了网络隔离，导致Node C，E，D构成了一个网络，Node A，B构成了一个网络。在这种情况下，Node E因为计时器触底发起了新一轮的选举并将任期推到了Term 2，Node C，B接收到高于自身任期的投票请求后，回复同意，于是Node E接收到了大部分的节点的同意成为了新的Leader并开始对外提供服务。这种情况下两个网络的日志会发生什么变化呢？我们可以看到Node C，D，E网络中包含了大部分的节点，所以他们的日志commit流程能够顺利进行下去，而Node B，A网络中由于无法满足超过1/2的投票的规则，所以所有的新的操作都无法commit，他的最新状态将一直保持在网络断开的时候。因此一旦网络隔离解除，Node A，B重新加入的时候，他们能够很快检测到Leader B的Term大于了自身的Term，于是Node A也会退出Leader身份，成为Node E的Follower并以新的Leader为准更新自身日志。
Raft五大原则
- 选举安全特性：对于一个给定的任期号，最多只会有一个领导人被选举出来
因为每一个新的任期都代表着一次新的选举，而每一个任期的选举中每个节点都只能投一票，而只有获得绝大多数投票的节点才能成为新的领导人，所以每一个任期的选举最多只有一个Leader被选出来，当然也有可能选不出Leader。(PS. 上面提到网络隔离可能会导致网络中存在多个Leader，可是这些Leader都处在不同的任期，所以和这个原则不冲突)
- 领导人只附加原则：领导人绝对不会删除或者覆盖自己的日志，只会增加
领导人的只附加原则是指所有的信息流都是从领导者流入到跟随者中，这样可以保证领导者自身的数据的一致性，保证了不会出现领导者已经应用的日志被出现更改的情况。
- 日志匹配原则：如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间全部完全相同
这个原则有两个部分组成：
- 如果不同节点的日志中的两个条目拥有相同的索引号和任期号，那么他们存储的指令也一定是相同的
- 如果不同节点的日志中的两个条目拥有相同的索引号和任期号，那么他们之前的条目也都完全相同
为了保证这个特性，每次领导者在将新的日志条目发送给跟随者的时候，都会带上这个条目的前一个条目的任期号和索引号。跟随者会去检查，前一个条目的任期号和索引号与自身最新的条目是否匹配，如果不匹配则向领导者请求前一个条目，知道匹配为止。这样其实保证了领导者和跟随者之间的日志能够对齐，也就是高度一致。防止有些跟随着漏掉了某些条目。(这个特性也可以让在断联后重新加入的节点更新自身的日志以追上其他节点的进度)。
- 领导人完全特性：如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中
所有的信息流都是从领导者流向跟随者的，所以必须要保证只有和上一任领导者数据保持一致的候选者才能成为新一任的领导者。只要保证了每一任的领导者在交替的时候是数据一致的就能够保证所有跟随者在之后的流程中也能跟领导者保持一致。所以每一届的选举，能成为领导者的候选人一定是包含了最新被提交的日志的节点，也就是包含了旧领导人的所有日志信息。
- 状态机安全特性：如果一个领导人已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志
也就是说领导人commit了一个条目后，所有的跟随者也都是相应的commit到这个日志为止。
