Leader election
Raft采用心跳机制来触发Leader选举。Leader周期性的发送心跳（如果有正常的RPC的请求情况下可以不发心跳）包保持自己Leader的角色（避免集群中其他节点认为没有Leader而开始选举）。
Follower在收到Leader或者Candidate的RPC请求的情况下一直保持Follower状态。而当一段时间内（election timeout）没有收到请求则认为没有Leader节点而出发选举流程。
选举流程如下：
Follower递增自己的任期并设置为Candidate角色
投票给自己并且并发的给所有节点发送投票请求
保持Candidate状态直到：
同一个任期内获得大多数选票，成为Leader（一个节点在一个任期内只能给一个Candidate投票，任期相同则选票先到先得）并给其他节点发送心跳来保持自己的角色
收到其他节点的RPC请求，如果请求中的任期大于等于Candidate当前的任期，认为其他节点成为了Leader，自身转换为Follower；如果其他节点的任期小于自身的任期，拒绝RPC请求并保持Candidate角色
一段时间后仍旧没有Leader（可能是出现了平票的情况），则在选举超时后重新发起一轮选举（递增任期、发送投票请求）
为了避免平票的问题，同时在出现平票的情况后能快速解决，Raft的选举超时时间是在一个区间内随机选择的（150~300ms）。这样尽量把服务器选举时间分散到不同的时间，保证大多数情况下只有一个节点会发起选举。在平票的情况下，每个节点也会在一个随机时间后开始新一轮选举，避免可能出现的一直处于平票的情况。
Log replication
一旦Leader被选举出来后，Leader就开始为集群服务：处理所有的客户端请求并将数据复制到所有节点。
一旦日志被“安全”的复制，那么Leader将这个日志应用到自己的状态机并响应客户端。
如果有节点异常或网络异常，Leader会一直重试直到所有日志都会正确复制到所有节点（日志不允许有空洞，所以每个节点上的日志都是连续的，不能有因为失败引起的空洞）。
日志组织形式如上图，每个日志条目中包含可执行的指令、和日志被创建时的任期号，日志条目也包含了自己在日志中的位置，即index。一旦一个日志条目存在于大多数节点，那么该日志条目是committed的。
Raft算法保证所有committed的日志都是持久化的（日志需要在大多数节点上持久化之后再响应给客户端，这意味着每个Follower节点收到AppendEntry请求后需要持久化到日志之后再响应给Leader），且最终会被所有的状态机执行。
Raft算法保证了以下特性：
如果两个日志条目有相同的index和term，那么他们存储了相同的指令（即index和term相同，那么可定是同一条指令，就是同一个日志条目）
如果不同的日志中有两个日志条目，他们的index和term相同，那么这个条目之前的所有日志都相同
两条规则合并起来的含义：两个日志LogA、LogB，如果LogA[i].index=Log[i]B.index且LogA[i].term=Log[i].term，那么LogA[i]=Log[i]B，且对于任何n < i的日志条目，LogA[n]=LogB[n]都成立。（这个结论显而易见的可以从日志复制规则中推导出来）
一个新Leader被选举出来时，Follower可能是上图中的任何一种情况。
(a)(b)可能还没复制到日志
(c)(d)可能曾经是Leader，所有包含了多余的日志（这些日志可能被提交了，也可能没提交）
(e)可能是成为Leader之后增加了一些日志，但是在Commit之前又编程了Follower角色，且还没有更新日志条目
(f)可能是在任期2称为了Leader并追加了日志但是还没提交就Crash了，恢复之后在任期3又成了Leader并且又追加了日志
在Raft中，通过使用Leader的日志覆盖Follower的日志的方式来解决出现像上图的情况（强Leader）。Leader会找到Follower和自己想通的最后一个日志条目，将该条目之后的日志全部删除并复制Leader上的日志。详细过程如下：
Leader维护了每个Follower节点下一次要接收的日志的索引，即nextIndex
Leader选举成功后将所有Follower的nextIndex设置为自己的最后一个日志条目+1
Leader将数据推送给Follower，如果Follower验证失败（nextIndex不匹配），则在下一次推送日志时缩小nextIndex，直到nextIndex验证通过
上面的方式显然可以通过一些方法进行优化来减少重试的次数，但是在Raft论文中对是否有必要进行优化提出了质疑，因为这种异常的情况很少出现。
解读Raft（三 安全性）
前言
之前的两篇文章更多的是在描述Raft算法的正常流程，没有过多的去讨论异常场景。
而实际在分布式系统中，我们更多的都是在应对网络不可用、机器故障等异常场景，所以本篇来讨论一下Raft协议的安全性，即在异常场景下是否会导致数据丢失、数据不一致等情况。
选举限制
在Raft协议中，所有的日志条目都只会从Leader节点往Follower节点写入，且Leader节点上的日志只会增加，绝对不会删除或者覆盖。
这意味着Leader节点必须包含所有已经提交的日志，即能被选举为Leader的节点一定需要包含所有的已经提交的日志。因为日志只会从Leader向Follower传输，所以如果被选举出的Leader缺少已经Commit的日志，那么这些已经提交的日志就会丢失，显然这是不符合要求的。
这就是Leader选举的限制：能被选举成为Leader的节点，一定包含了所有已经提交的日志条目。
回看算法基础中的RequestVote RPC：
参数解释
term
Candidate的任期
candidateId
Candidate的ID
lastLogIndex
Candidate最后一条日志的索引
lastLogTerm
Candidate最后一条日志的任期
参数解释
term
当前任期，用于Candidate更新自己的任期
voteGranted
true表示给Candidate投票
请求中的lastLogIndex和lastLogTerm即用于保证Follower投票选出的Leader一定包含了已经被提交的所有日志条目。
Candidate需要收到超过版本的节点的选票来成为Leader
已经提交的日志条目至少存在于超过半数的节点上
那么这两个集合一定存在交集（至少一个节点），且Follower只会投票给日志条目比自己的“新”的Candidate，那么被选出的节点的日志一定包含了交集中的节点已经Commit的日志
日志比较规则（即上面“新”的含义）：Raft 通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更加新。如果两份日志最后的条目任期号相同，那么日志比较长的那个就更加新。
日志提交限制
上图按时间序列展示了Leader在提交日志时可能会遇到的问题。
在 (a) 中，S1 是领导者，部分的复制了索引位置 2 的日志条目。
在 (b) 中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处。
然后到 (c)，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交。
如果 S1 在 (d) 中又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志。反之，如果在崩溃之前，S1 把自己主导的新任期里产生的日志条目复制到了大多数机器上，就如 (e) 中那样，那么在后面任期里面这些新的日志条目就会被提交（因为S5 就不可能选举成功）。 这样在同一时刻就同时保证了，之前的所有老的日志条目就会被提交。
任期2内产生的日志可能在(d)的情况下被覆盖，所以在出现(c)的状态下，Leader节点是不能commit任期2的日志条目的，即不能更新commitIndex。
在上图最终状态是(e)的情况下，commitIndex的变化应该是1->3，即在(c)的情况下，任期4在索引3的位置commit了一条消息，commitIndex直接被修改成3。
而任期2的那条日志会通过Log Matching Property最终被复制到大多数节点企且被应用。
Raft算法保证了以下特性：
如果两个日志条目有相同的index和term，那么他们存储了相同的指令（即index和term相同，那么可定是同一条指令，就是同一个日志条目）
如果不同的日志中有两个日志条目，他们的index和term相同，那么这个条目之前的所有日志都相同
两条规则合并起来的含义：两个日志LogA、LogB，如果LogA[i].index=Log[i]B.index且LogA[i].term=Log[i].term，那么LogA[i]=Log[i]B，且对于任何n < i的日志条目，LogA[n]=LogB[n]都成立。（这个结论显而易见的可以从日志复制规则中推导出来）
解读Raft（四 成员变更）
将成员变更纳入到算法中是Raft易于应用到实践中的关键，相对于Paxos，它给出了明确的变更过程（实践的基础，任何现实的系统中都会遇到因为硬件故障等原因引起的节点变更的操作）。
显然，我们可以通过shutdown集群，然后变更配置后重启集群的方式达到成员变更的目的。但是这种操作会损失系统的可用性，同时会带来操作失误引起的风险。支持自动化配置，即配置可以在集群运行期间进行动态的变更（不影响可用性）显示是一个非常重要的特性。
Raft成员变更机制
在成员变更时，因为无法做到在同一个时刻使所有的节点从旧配置转换到新配置，那么直接从就配置向新配置切换就可能存在一个节点同时满足新旧配置的“超过半数”原则。
如下图，原集群由Server1、Server2、Server3，现在对集群做变更，增加Server4、Server5。如果采用直接从旧配置到新配置的切换，那么有一段时间存在两个不想交的“超过半数的集群”。
上图，中在中间位置Server1可以通过自身和Server2的选票成为Leader（满足旧配置下收到大多数选票的原则）；Server3可以通过自身和Server4、Server5的选票成为Leader（满足新配置线，即集群有5个节点的情况下的收到大多数选票的原则）；此时整个集群可能在同一任期中出现了两个Leader，这和协议是违背的。
为了保证安全性，Raft采用了一种两阶段的方式。
第一阶段称为joint consensus，当joint consensus被提交后切换到新的配置下。
joint consensus状态下：
日志被提交给新老配置下所有的节点
新旧配置中所有机器都可能称为Leader
达成一致（选举和提交）要在两种配置上获得超过半数的支持
具体的切换过程如下：
Leader收到C-old到C-new的配置变更请求时，创建C-old-new的日志并开始复制给其他节点（和普通日志复制没有区别）
Follower以最新的配置做决定（收到C-old-new后就以C-old-new来决定），Leader需要以已经提交的配置来做决定（即只有C-old-new复制到大多数节点后Leader才以这个配置做决定）；这个时候处于一个共同决定的过程
之后提交C-new到所有节点，一旦C-new被提交，旧的配置就无所谓了
从上图可以看出，不存在一个阶段C-old和C-new可以同时根据自己的配置做出决定，所以不会出现本文开头描述的情况。
Review成员变更
如果当前的Leader不在C-new的配置中会怎么样（即当前的Leader是一个要被下线的节点）？
在C-old-new的状态下，Leader依旧可用；在C-new被commit之后Leader实际已经从集群中脱离，此时可以对Leader节点进行下线操作，而新集群则会在C-new的配置下重新选举出一个Leader。
如果在配置分发过程中Leader Crash了会怎么样？
这个问题要分为多种情况：1. C-new已经分发到超过半数节点、2. C-new还没分发到超过半数的节点
情况1：C-new已经分发到超过半数节点
集群开始重新选举，此时在C-new的规则下，旧节点（不存在新配置中的节点）不会赢得选举（因为他们要在C-old-new的情况下决定，但是拿不到C-new的选票），只有拿到C-new的节点可能成为Leader并继续下发C-new配置，流程恢复。
情况2：C-new还没分发到超过半数的节点
这种情况下，C-old-new和C-new的节点都可以成为Leader，但是无所谓，因为无论谁成为Leader，都能根据当前的配置继续完成后续流程（如果是C-new那么相当与完成了最终的配置，不在C-new的节点会因为没有心跳数据而失效）
旧节点下线造成的问题：旧节点收不到心跳触发选举，发送请求给C-old-new中的节点，是否会影响集群正常运行
Raft的处理方式：当节点确信有Leader存在时，不会进行投票（在Leader超时之前收到新的投票请求时不会提升term和投票）。且开始选举之前等待一个选举超时时间，这样在新Leader正常工作的情况下，不会受到旧节点的影响。
旧节点在发起选举前需要等待一段时间，那么这段时间新Leader可以发送心跳，这样就减少了影响。 对正常流程的影响不大。（Leader失效后要等一段时间，没有及时触发，然而本身这里就有一个判断失效的时间，好像影响不大；比如原先超时时间是10s，那么如果设置成5s，原策略下10s超时就是10s后开始选举，新策略下5s超时就是超时后再等5s再开始选举，影响就是超时时间变短）
新的服务器没有任何数据，加入进来进来怎么保证系统的可用性（这个时候新日志没办法Commit就没办法响应给客户端）？
新加入的节点需要时间复制数据，在这个过程完成之前，Raft采用以下机制来保证可用性： 新加入节点没有投票权（Leader复制日志给他们，但是不将他们考虑在机器数量里面——即在判断是否超过半数时不把这些节点考虑在内），直到这些节点的日志追上其他节点。
发表评论