引言
Raft算法是一种解决分布式系统一致性问题的算法，类似的算法还有大名鼎鼎的Paxos算法。但Paxos太过复杂并且难以实现（虽然Zookeeper就是基于Paxos算法，但它在Paxos的基础上已经做了很多改进和优化），所以斯坦福的Diego Ongaro、John Ousterhout两个人以易懂（Understandability）为目标设计了Raft一致性算法，在2013年发布了论文：《In Search of an Understandable Consensus Algorithm》，Kubernetes系统使用的分布式数据库ETCD就是基于Raft实现。
为了达到易于理解的目标，Raft主要做了两件事情：
- 问题分解
问题分解是将”节点一致性”这个复杂的问题划分为数个可以被独立解释、理解、解决的子问题。这些子问题包括：Leader选举（Leader election）、日志复制（Log replication）、安全性（Safety）、从属关系变化（Membership changes）等。 - 状态简化
状态简化更好理解，就是对算法做出一些限制，减少需要考虑的状态数，使得算法更加清晰，更少的不确定性（比如，保证新选举出来的leader会包含所有commited log entry）
Raft implements consensus by first electing a distinguished leader, then giving the leader complete responsibility for managing the replicated log. The leader accepts log entries from clients, replicates them on other servers, and tells servers when it is safe to apply log entries to their state machines. A leader can fail or become disconnected from the other servers, in which case a new leader is elected.
上面的引文对Raft算法的工作原理进行了高度的概括：集群会先选举出leader，leader完全负责replicated log的管理。leader负责接收所有客户端更新请求，然后复制到follower节点。如果leader故障，集群会重新选举出新的leader。
几个重要概念
节点的三种角色
Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选者（Candidate）：
Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。再选举期间对Candidate进行投票。
Candidate：Leader选举过程中的临时角色。
Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。Raft算法将时间分为一个个的任期（term），每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。
Term
Raft 算法将时间划分成为任意不同长度的任期（term）。任期用连续的数字进行表示。每一个任期的开始都是一次选举（election），一个或多个Candidate会试图成为Leader。如果一个候选人赢得了选举，它就会在该任期的剩余时间担任Leader。在某些情况下，有可能因为没有获得超半数票而没有选出Leader，那么，将会开始另一个任期，并且立刻开始下一次选举。
RPC调用
Raft 算法中服务器节点之间通信使用远程过程调用（RPC），基本的一致性算法只需要用到两种类型的 RPC，为了在服务器之间传输快照需要用到第三种 RPC。
所以总共有如下三种RPC调用：
RequestVote RPC：候选人在选举期间发起。
AppendEntries RPC：Leader发起的一种心跳机制，复制日志也在该命令中完成。
InstallSnapshot RPC: Leader使用该RPC来发送快照给太落后的Follower。
Leader选举（Leader election）
在Raft协议中使用心跳（heartbeat）触发Leader选举，一个节点任一时刻处于以下三个角色之一：
- Leader
- Follower
- Candidate
角色转换如下图所示：
可以看出：
- 所有节点启动时都是Follower角色。
- 在一段时间内如果没有收到来自Leader的心跳请求，则从Follower切换到Candidate，发起选举。
- Candidate如果收到超过半数节点的选票（含自己的一票）则转换为Leader；发现Leader或者收到更高任期的请求则转换为Follower。当这三种情况都没有时，则在超时后又发起下一轮选举。
- Leader在收到更高任期的请求后转换为Follower。
选举过程
正常情况下，Leader向所有Followers周期性发送heartbeat。如下图
每个Follower内部都有时钟，默认是一个150ms~300ms随机的值，表示在这个时钟跑完后没有收到Leader的心跳请求，则发起Leader选举。当Leader节点故障了，Follower在超时时间内未收到heartbeat，则其会当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC。
当然选举可能会出现平票情况，如果平票则开始下一个Term的选举，如下图，第4个和第5个Term的情况下，没有任何节点获得超半数选票（3张选票），所以知道第6个Term才选出Leader。
前面讲到选举是通过 RequestVote RPC 请求来完成的，这里介绍一下 RequestVote RPC 请求的参数和响应逻辑。
请求参数：
| 参数 | 解释 |
|---|---|
| term | Candidate的任期 |
| candidateId | Candidate的ID |
| lastLogIndex | Candidate最后一条日志的索引 |
| lastLogTerm | Candidate最后一条日志的任期 |
响应数据：
| 参数 | 解释 |
|---|---|
| term | 当前任期，用于Candidate更新自己的任期 |
| voteGranted | true表示给Candidate投票 |
voteGranted的逻辑：
- 如果收到的任期term比当前任期小，返回false。
- 如果本地状态中votedFor为null或者CandidateId，且Candidate的日志等于或多余（按照index判断）接收者的日志，则接收者投票给Candidate，即返回true。
日志复制（Log replication）
一旦选举出了一个Leader，它就开始负责接受客户端的请求。每个客户端的请求都包含一个要被复制状态机执行的指令。Leader首先要把这个指令追加到log中形成一个新的entry，然后通过AppendEntries RPC 并行的把该entry发给其他节点，其他节点如果发现没问题，复制成功后会给Leader一个表示成功的ACK，Leader收到大多数ACK后才会告诉客户端请求成功。如果follower节点宕机或出现网络问题，Leader会不断重试AppendEntries RPC。
Log 的示意图如下：
每个log entry都存储着一条用于状态机的指令，同时保存从Leader收到该entry时的term号。该term号可以用来判断一些log之间的不一致状态。每一个entry还有一个index指明自己在log中的位置。
leader需要决定什么时候将日志应用给状态机是安全的，被应用的entry叫committed。Raft保证committed entries持久化，并且最终被其他状态机应用。一个log entry一旦复制给了大多数节点就成为committed。同时要注意一种情况，如果当前待提交entry之前有未提交的entry，即使是以前过时的leader创建的，只要满足已存储在大多数节点上就一次性按顺序都提交。leader要追踪最新的committed的index，并在每次AppendEntries RPCs（包括心跳）都要捎带，以使其他server知道一个log entry是已提交的，从而在它们本地的状态机上也应用。
Raft的日志机制提供两个保证，统称为Log Matching Property：
不同机器的日志中如果有两个entry有相同的偏移和term号，那么它们存储相同的指令。
如果不同机器上的日志中有两个相同偏移和term号的日志，那么日志中这个entry之前的所有entry保持一致。
第一个保证是由于一个leader在指定的偏移和指定的term，只能创建一个entry，log entries不能改变位置。第二个保证通过AppendEntries RPC的一个简单的一致性检查机制完成。当发起一个AppendEntries RPC，leader会包含正好排在新entries之前的那个entry的偏移和term号，如果follower发现在相同偏移处没有相同term号的一个entry，那么它拒绝接受新的entries。这个一致性检查以一种类似归纳法的方式进行：初始状态大家都没有日志，不需要进行Log Matching Property检查，但是无论何时followers只要日志要追加都要进行此项检查。因此，只要AppendEntries返回成功，leader就知道这个follower的日志一定和自己的完全一样。
在正常情形下，leader和follower的日志肯定是一致的，所以AppendEntries一致性检查从不失败。然而，如果leader crash，那么它们的日志很可能出现不一致。这种不一致会随着leader或者followers的crash变得非常复杂。下图展示了所有日志不一致的情形：
如上图(a)(b)followers可能丢失日志，(c)(d)有多余的日志，或者是(e)(f)跨越多个terms的又丢失又多余。在Raft里，leader强制followers和自己的日志严格一致，这意味着followers的日志很可能被leader的新推送日志所覆盖。
leader为了强制它人与自己一致，势必要先找出自己和follower之间存在分歧的点，也就是我的日志与你们的从哪里开始不同。然后令followers删掉那个分歧点之后的日志，再将自己在那个点之后的日志同步给followers。这个实现也是通过AppendEntries RPCs的一致性检查来做的。leader会把发给每一个follower的新日志的偏移nextIndex也告诉followers。当新leader刚开始服务时，它把所有follower的nextIndex都初始化为它最新的log entry的偏移+1（如上图中的11）。如果一个follower的日志和leader的不一致，AppendEntries RPC会失败，leader就减小nextIndex然后重试，直到找到分歧点，剩下的就好办了，移除冲突日志entries，同步自己的。