Raft是用于管理复制日志的一致性算法，raft 协议也是一个主备模型，有一个唯一的 leader 控制任务的提交。
Raft通过选出一个leader来简化日志副本的管理，例如，日志项(log entry)只允许从leader流向follower。
在Raft中，问题分解为：领导选取、日志复制、安全和日志压缩。
基本概念
服务器状态
一个 Raft 集群包含若干个服务器节点；通常是 5 个，这允许整个系统容忍 2 个节点的失效，每个节点处于以下三种状态之一：
follower（跟随者）：所有结点都以follower的状态开始。如果没收到leader消息则会变成candidate状态。candidate（候选人）：会向其他结点“拉选票”，如果得到大部分的票则成为leader。这个过程就叫做Leader选举(Leader Election)。leader（领导者）：所有对系统的修改都会先经过leader。
任期(Term)
raft 最关键的一个概念是任期，用以解决“时间同步”的问题，每一个 leader 都有自己的任期，必须在任期内发送心跳信息给 follower 来延长自己的任期。
1、每个Term至多存在1个Leader
2、 某些Term由于选举失败，不存在Leader
3、 每个Server本地维护currentTerm
RPC
RPC有三种：
RequestVote RPC：候选人在选举期间发起
AppendEntries RPC：领导人发起的一种心跳机制，复制日志也在该命令中完成
InstallSnapshot RPC: 领导者使用该RPC来发送快照给太落后的追随者。
Leader election (领导选举)
Raft 使用心跳机制来触发领导人选举。当服务器程序启动时，他们都是 follower(跟随者) 身份，如果跟随者在超时时间(每一个节点会自定义一个超时时间)内没有收到 Leader 的请求则转换为 Candidate 进行选举。在一次选举过程，每一个 Candidate 首先term加一，并且投自己一票。
然后他会并行的向集群中的其他服务器节点发送请求投票的 RPCs 来给自己投票。候选人的状态维持直到发生以下任何一个条件发生的时候，
获得超过半数服务器的投票，赢得选举，成为领导者；
另一台服务器赢得选举，并接收到对应的心跳，成为追随者；
选举超时，没有任何一台服务器赢得选举，自增当前任期，重新发起选举；
注意事项：
服务器在一个任期内，最多能给一个候选人投票，采用先到先服务原则；
候选者等待投票时，可能会接收到来自其它声明为领导人的的AppendEntries RPC。如果该领导人的任期（RPC中有）比当前候选人的当前任期要大，则候选人认为该领导人合法，并转换成追随者；如果RPC中的任期小于候选人的当前任期，则候选人拒绝此次RPC，继续保持候选人状态；
候选人既没有赢得选举也没有输掉选举：如果许多追随者在同一时刻都成为了候选人，选票会被分散，可能没有候选人能获得大多数的选票。当这种情形发生时，每一个候选人都会超时，并且通过自增任期号和发起另一轮 RequestVote RPC 来开始新的选举。然而，如果没有其它手段来分配选票的话，这种情形可能会无限的重复下去。所以Raft使用的随机的选举超时时间（150~300ms之间），来避免这种情况发生。
Log replication (日志复制)
接受命令的过程：
领导者接受客户端请求；
领导者把指令追加到日志；
发送AppendEntries RPC到追随者；
领导者收到大多数追随者的确认后，领导者Commit该日志，把日志在状态机中回放，并返回结果给客户端；
提交过程：
在下一个心跳阶段，领导者再次发送AppendEntries RPC给追随者，日志已经commited；
追随者收到Commited日志后，将日志在状态机中回放。
当 follower 宕机或者运行较慢时，leader 会无限地重发AppendEntries给这些follower（尽管已经回复了客户端），直到所有的follower都复制了该log entry。
Raft的log replication保证以下性质(Log Matching Property)：
如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。
其中特性一通过以下保证：
leader在一个特定的term和index下，只会创建一个log entry
log entry不会改变它们在日志中的位置
特性二通过以下保证：
AppendEntries会做log entry的一致性检查，当发送一个AppendEntriesRPC时，leader会带上需要复制的log entry前一个log entry的(index, iterm)
如果follower没有发现与它一样的log entry，那么它会拒绝接受新的log entry。
不一致场景：某服务器在任期 2 的时候是领导人，已附加了一些日志条目到自己的日志中，但在提交之前就崩溃了；很快这个机器就被重启了，在任期 3 重新被选为领导人，并且又增加了一些日志条目到自己的日志中；在任期 2 和任期 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。
在 Raft 算法中，领导人处理不一致是通过强制跟随者直接复制自己的日志来解决了。这意味着在跟随者中的冲突的日志条目会被领导人的日志覆盖。要使得跟随者的日志进入和自己一致的状态，领导人必须找到最后两者达成一致的地方，然后删除从那个点之后的所有日志条目，发送自己的日志给跟随者。
在数据同步阶段，可能出现六种情况：
-
数据到达 Leader节点前，Leader 挂掉。
- 这个阶段
Leader挂掉不影响一致性。
- 这个阶段
-
数据到达 Leader节点，但未复制到 Follower节点，Leader挂掉。
- 这个阶段
Leader挂掉，数据属于未提交状态，Client不会收到Ack会认为超时失败可安全发起重试。Follower节点上没有该数据，重新选主后Client重试重新提交可成功。原来的Leader节点恢复后作为Follower加入集群重新从当前任期的新Leader处同步数据，强制保持和Leader数据一致。
- 这个阶段
-
数据到达 Leader节点，成功复制到 Follower所有节点，但还未向 Leader响应接收，Leader挂掉。
- 这个阶段
Leader挂掉，虽然数据在Follower节点处于未提交状态（Uncommitted）但保持一致，重新选出Leader后可完成数据提交，此时Client由于不知到底提交成功没有，可重试提交。针对这种情况Raft要求RPC请求实现幂等性，也就是要实现内部去重机制。(类似于 zab)
- 这个阶段
-
数据到达 Leader节点，成功复制到Follower部分节点，但还未向 Leader响应接收，Leader挂掉。
- 这个阶段
Leader挂掉，数据在Follower节点处于未提交状态（Uncommitted）且不一致，Raft 协议要求投票只能投给拥有最新数据的节点。所以拥有最新数据的节点会被选为Leader再强制同步数据到Follower，数据不会丢失并最终一致。
- 这个阶段
-
数据到达 Leader节点，成功复制到 Follower所有或多数节点，数据在 Leader处于已提交状态，但在 Followe处于未提交状态，Leader挂掉。
- 这个阶段
Leader挂掉，重新选出新Leader后的处理流程和第三种情况一样。
- 这个阶段
-
网络分区导致的脑裂情况，出现双 Leader
- 原先的
Leader独自在一个区，向它提交数据不可能复制到多数节点所以永远提交不成功。向新的Leader提交数据可以提交成功，网络恢复后旧的Leader发现集群中有更新任期（Term）的新Leader则自动降级为Follower并从新Leader处同步数据达成集群数据一致。
- 原先的
安全性
领导者追加日志（Append-Only)
领导者永远不会覆盖已经存在的日志条目； 日志永远只有一个流向：从领导者到追随者；
选举限制：投票阻止没有全部日志条目的服务器赢得选举
如果投票者的日志比候选人的新，拒绝投票请求； 这意味着要赢得选举，候选者的日志至少和大多数服务器的日志一样新，那么它一定包含全部的已经提交的日志条目。
永远不提交任期之前的日志条目（只提交任期内的日志条目）
在Raft算法中，当一个日志被安全的复制到绝大多数的机器上面，即AppendEntries RPC在绝大多数服务器正确返回了，那么这个日志就是被提交了，然后领导者会更新commit index。
如果允许提交任期之前的日志条目，那么在步骤c中，我们就会把之前任期为2的日志提交到其他服务器中去，并造成了大多数机器存在了日志为2的情况。所以造成了d中S5中任期为3的日志条目会覆盖掉已经提交的日志的情况。
Raft 从来不会通过计算复制的数目来提交之前人气的日志条目。只有领导人当前任期的日志条目才能通过计算数目来进行提交。一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配原则（Log Matching Property），之前的日志条目也都会被间接的提交。
论文中的这段话比较难理解，更加直观的说：由于Raft不会提交任期之前的日志条目，那么就不会从b过渡到c的情况，只能从b发生S5down机的情况下直接过渡到e，这样就产生的更新的任期，这样S5就没有机会被选为领导者了。
跟随者和候选人崩溃
跟随者或者候选人崩溃，会按如下处理：
领导者会不断给它发送选举和追加日志的RPC，直到成功
跟随者会忽略它已经处理过的追加日志的RPC
日志压缩
raft采用快照的方式进行日志压缩，做完快照之后快照会在稳定持久存储中保存，而快照之前的日志和快照就可以丢弃掉
与Raft其它操作Leader-Based不同，snapshot是由各个节点独立生成的。除了日志压缩这一个作用之外，snapshot还可以用于同步状态：slow-follower以及new-server，Raft使用InstallSnapshot RPC完成该过程。
