Raft 是一种用来管理日志复制的一致性算法，常用于解决复制状态机架构中的日志一致性问题。相校于另一种流行的算法Paxos，性能和功能是一样的，但学习起来更简单易懂。Raft将一致性算法分为了几个部分，例如领导选取（leader selection），日志复制（log replication）和安全性（safety），同时它使用了更强的一致性来减少了必须需要考虑的状态。Raft 还包括了一种新的机制来使得动态改变集群成员，它使用重叠大多数（overlapping majorities）来保证安全。
复制状态机(Replicated State Machine)
复制状态机是用于解决在分布式环境中的容错问题的一种架构。该架构通过在保证所有集群节点中操作日志顺序一致的前提下，按日志顺序执行命令以达到所有集群节点处于一致状态的目的，如果发生单节点宕机，就可以使用其他节点替代，从而实现容错。而日志复制一致性算法则是为了解决复制状态机中所有集群节点日志顺序一致性问题的方案。下图描述了复制状态机的架构：
Raft算法设计的目标
-
它必须提供一个完整的、实际的基础来进行系统构建，为的是减少开发者的工作；
-
它必须在所有情况下都能保证安全可用；
-
它对于常规操作必须高效；
-
最重要的目标是：易于理解，它必须使得大多数人能够很容易的理解；
-
另外，它必须能让开发者有一个直观的认识，这样才能使系统构建者们去对它进行扩展。
Raft算法基础
一个Raft集群包括若干服务器；对于一个典型的5服务器集群，该集群能够最多容忍2台机器不能正常工作，而整个系统保持正常。在任意的时间，每一个服务器一定会处于以下三种状态中的一个：Leader、Candidate、Follower。在正常情况下，只有一个服务器是Leader，剩下的服务器是Follower。Follower是被动的：他们不会发送任何请求，只是响应来自Leader和Candidate的请求。Leader处理所有来自客户端的请求（如果一个客户端与Follower进行通信，Follower会将信息发送给Leader）。Candidate是用来选取一个新的领导人，更多请看Leader选举部分。
服务器状态转换
下图很简单明了地描述了服务器的状态转换
关于任期号
任期号是在Leader选举过程中，由Candidate在当前任期号上递增生成的，如果Candidate在该任期号上成功晋升为Leader，那么该Candidate就成了该任期号对应的Leader。因此，每个任期的开始必然对应着一次选举的开始。如下图所示
Raft集群中每个服务节点都存在的状态
| 名称 | 描述 |
|---|---|
| currentTerm | 当前任期号 |
| votedFor | 候选人ID，指当前任期内已给哪个Candidate投票的意思（如果没有就为null) |
| log[] | 日志序列,每个日志项包含状态机要执行的命令和从Leader中收到的任期号 |
| commitIndex | 已提交的最大日志项的索引（从0开始递增） |
| lastApplied | 状态机已经执行的日志项的索引（从0开始递增） |
在Leader节点中存在的状态
| 名称 | 描述 |
|---|---|
| nextIndex[] | 记录需要发给其他集群节点的下一个日志项的索引（初始化为Leader上一条日志的索引值+1） |
| matchIndex[] | 记录已经复制到其他集群节点日志的最高索引值（从0开始递增） |
Raft算法的五大原则
下表描述了Raft算法的基本原则，即算法可以提供的保证。Raft一致性算法部分描述了整个Raft算法的实现过程。算法总结部分描述了Raft算法实现是如何为五大原则提供保证的。
| 性质 | 描述 |
|---|---|
| 选举安全原则（Election Safety） | 一个任期（term）内最多允许有一个领导人被选上 |
| 领导人只增加原则（Leader Append-Only） | 领导人永远不会修改或者删除自己的日志，它只会增加日志 |
| 日志匹配原则（Log Matching） | 如果两个节点日志序列在相同的索引位置上的日志项的任期号相同，那么我们就认为这个日志从头到这个索引位置之间的日志完全相同 |
| 领导人完全原则（Leader Completeness) | 如果一个日志项在一个给定任期内被提交，那么这个条目一定会出现在所有任期号更大的领导人中 |
| 状态机安全原则（State Machine Safety） | 如果一个服务器已经将给定索引位置的日志项应用到状态机中，则所有其他服务器不会在该索引位置应用不同的日志项 |
下面通过介绍Raft算法的细则来解析Raft算法是如何保证以上的原则的。
Raft一致性算法
Leader选举
Follower在选举超时（election timeout）时间1内，没有收到Leader的心跳时，则会触发Leader选举。
Leader选举过程:
- Follower状态转换为Candidate
- Candidate的当前任期+1
- Candidate为自己投票
- Candidate重置一个随机的投票超时时间2
- Candidate向集群中的其它节点发送RequestVote RPC
发送RequestVote RPC会有三种结果：
- Candidate在任期内收到大多数3节点的选票。Candidate则晋升为Leader，并发送心跳以维持Leader状态
- Candidate在等待其他节点选票时，可能会收到来自其他节点的AppendEntries RPC请求，如果AppendEntries RPC请求中声明的任期号比Candidate的任期号要大，Candidate则切换回Follower状态，否则拒绝此次RPC请求，保持Candidate状态。
- 多个Candidate瓜分选票，以致没有一个Candidate能获得大多数的选票来晋升为Leader，最终导致投票超时，此时Candidate会重新触发Leader选举过程
投票请求 RPC（RequestVote RPC）过程
RequestVote RPC请求只能由Candidate发起，并由Leader或Follower处理。
RequestVote RPC接口定义：
| 参数 | 描述 |
|---|---|
| term | Candidate的任期号 |
| candidateId | 请求投票的Candidateid |
| lastLogIndex | Candidate最新日志条目的索引 |
| lastLogTerm | Candidate最新日志条目对应的任期号 |
| 返回值 | 描述 |
|---|---|
| term | 投票节点的任期号，用于候选人更新自己 |
| voteGranted | 如果候选人收到选票为 true |
当集群节点收到RequestVote RPC请求之后，需要按以下步骤处理：
- 先比较当前任期号与Candidate的任期号，如果当前任期号较大，则返回false。
- votedFor为null或与Candidate的ID相同，则与Candidate的lastLogIndex和lastLogTerm进行比较，若Candidate的lastLogIndex大于本地的日志索引或log[lastLogIndex].term小于等于Candidate的lastLogTerm，则返回true
日志复制
当选举出Leader之后，Leader就可以接受客户端的请求。
Leader接受客户端请求的过程描述如下：
- 接受请求，并把该请求作为新的日志项加入到它的日志序列中
- 向其他集群节点发起AppendEntries RPC请求
- 当大多数的集群节点成功完成该日志项的AppendEntries RPC请求，该日志项则认为是已经被提交了，同时更新commitIndex。这个commitIndex会在下一次AppendEntries RPC请求中作为leaderCommit参数传递。
- 此时，该日志项处于已提交状态了，由复制状态机执行该日志中的命令并响应客户端
在上面的过程中，有一个在Raft中很重要的一个概念——日志提交！一个日志项何时变为已提交状态呢？在Raft算法中，只有该日志项是由Leader当前任期创建的，并且已经复制到大多数的集群节点，才可以将该日志项视为已提交了，并更新commitIndex。
如下图所示，任期3是Leader所在任期，索引7的日志项已被复制到大多数的集群节点（占了5个节点中的3个，超过50%），则Leader此时可以把commitIndex设置为7了。
AppendEntries RPC请求过程
AppendEntries RPC只能由Leader发起请求，并由Candidate或Follower处理。AppendEntries RPC同时也作为Leader心跳请求，只是entries[]为空。
| 参数 | 描述 |
|---|---|
| term | Leader的任期号 |
| leaderId | Leader的id，为了其他服务器能重定向到客户端 |
| prevLogIndex | 相对于entries[0]的上一条日志索引 |
| prevLogTerm | 相对于entries[0]的上一条日志的任期号 |
| entries[] | 将要存储的日志条目（表示 heartbeat 时为空，有时会为了效率发送超过一条） |
| leaderCommit | Leader提交的日志项索引值 |
| 返回值 | 描述 |
|---|---|
| term | 当前的任期号，用于领导人更新自己的任期号 |
| success | 如果其它服务器包含能够匹配上 prevLogIndex 和 prevLogTerm 的日志时为真 |
需要特别说明的是，在Leader中维持着nextIndex[]的数组，记录了发往各个集群节点的下一条日志的索引。在发起AppendEntries RPC请求的时候，prevLogIndex参数就是从nextIndex[]中取出的索引。但对于一个新上任的Leader，它的nextIndex[]为空，prevLogIndex则取Leader日志的最大日志项索引+1。
当AppendEntries RPC请求返回false，prevLogIndex再往前取值(即prevLogIndex–)重试，直到找到日志匹配的索引位置。
接受AppendEntries RPC请求的服务需要实现：
- 如果 term < currentTerm，返回false
- 如果在prevLogIndex处的日志的任期号与prevLogTerm不匹配时，返回false
- 清空从prevLogIndex+1处开始的日志项，并将entries[]的日志列表从prevLogIndex+1处开始复制
- 如果leaderCommit > commitIndex，将commitIndex设置为leaderCommit和最新日志条目索引中较小的一个
安全性
Raft安全性解决的问题有以下几个：
- 为领导人完全原则（Leader Completeness) 和 状态机安全原则（State Machine Safety）提供保证
- Follower和Candidate崩溃如何处理
- 时序与可用性问题
- 集群成员发生变化之后，如果可以在不重启的情况下，集群如何可以安全地过渡到新的集群配置
下面分段说明Raft是如何解决以上问题的。
领导人完全原则（Leader Completeness) 和 状态机安全原则（State Machine Safety）的保证
Raft算法是通过在Leader选举过程中添加一个限制条件以达到领导人完全原则（Leader Completeness) 和 状态机安全原则（State Machine Safety）。
Raft算法限制了在选举过程中，只有包含有所有已提交日志的集群节点才可以赢得选举。
那么，满足什么样条件的Candidate可以赢得选票呢？
答案是Candidate中的日志比投票节点的日志更新，即 Candidate最新一条日志的索引> 投票节点最新一条日志的索引 或 Candidate最新一条日志任期号 >= 投票节点最新一条日志的任期号。
处理Follower和Candidate崩溃
当Follower和Candidate崩溃了，发送给它们的RequestVote RPC和AppendEntries RPC就会失败。Raft通过无限的重试来处理这些失败；如果崩溃的服务器重启了，RPC就会成功完成。由于Raft的RPC请求都是幂等的，无限重试是允许的。
时序、可用性和安全性4
首先，安全性一定不可以依赖于时序，Raft算法不可能因为某些节点处理得快些或慢些，而影响到算法的一致性。
另外，可用性无可避免要依赖于时序的。因为Candidate不能等太长的时间才能赢得选举；RPC请求延时太长会影响客户端的响应；节点系统不稳定导致Leader任期时间太短等等。
Raft针对可用性的问题，要求时间上要满足下面的条件：
broadcastTime << electionTimeout << MTBF
broadcastTime指的是一台服务器并行的向集群中的其他服务器发送 RPC 并且收到它们的响应的平均时间；electionTimeout指的就是在选举超时时间；MTBF指的是单个服务器发生故障的间隔时间的平均数。
集群成员配置变更
在此之前讨论的Raft算法，都是假设集群成员列表是固定的。但在实际应用中，会有变更集群成员列表的需求。当然，这个问题可以通过重启所有集群节点中的服务器来完成，但这样会导致有一段较长时间集群不可用状态。为了解决这个问题，Raft算法提供了能使集群成员配置变更平稳过渡的方案。
首先，必须认识到只是直接地将$C_{old}$5更改为$C_{new}$是不可行，下图解析了原因。
集群永远不可能同时更新配置，总会存在一定的时间差异。正如上图所示直接更新集群配置，可能会选举出没有包含所有已提交日志的Leader。Server3可以由Server4和Server5选举成为Leader，这就违反了Raft的Leader完全原则。
为了保证安全性，集群配置的调整必须使用两阶段（two-phase）方法。Raft先把集群切换到一个过渡阶段（第一阶段），称其为共同一致（joint consensus）阶段。一旦共同一致已提交，就可切换到$C_{new}$，下图描述了集群变更的时间线。
虚线表示的是已经被创建但是还没提交的配置条目，实线表示的是最新提交的配置条目。当Leader接收到一个集群配置变更请求时，Leader会生成一份由$C_{old}$和$C_{new}$组成的过渡配置$C_{old,new}$6，并保存到本地日志中。这个时候，日志提交所需要的大多数节点就包含了新旧的集群列表配置了。$C_{old,new}$配置提交之后，Leader再对$C_{new}$进行提交就安全了。
注意：配置类日志与其他日志有些区别，服务器节点一旦收到配置类日志，就可以马上使用最新的配置，不需要等到提交。
这个过程会出现三个问题：
-
Leader要响应客户端的请求，需要先在大多数节点复制该日志，提交日志，才能在状态机执行命令并返回给客户端。但在集群配置变更中，一些新的服务器可能没有任何的日志，这就有可能影响到Leader提交日志了($C_{old,new}$的大多数包括了新服务器的情况)。这种情况下，Raft算法把为此种情况使用一种额外的阶段，在此阶段，新服务器没有投票权，也不在日志提交的大多数节点范围内，直到它们的日志追上了Leader，此时再按上面描述的重新配置进行。
-
Leader不是$C_{new}$中的一员。在这种情况下，Leader就会在提交了$C_{new}$日志之后退位（回到跟随者状态）。这意味着有这样的一段时间，Leader管理着集群，但是不包括自己；它复制日志但是不把它自己看作是大多数之一。
-
移除不在$C_{new}$中的服务器可能会扰乱集群。这些服务器将不会再接收到心跳（heartbeat），所以当选举超时时，它们就会进行新的选举过程。它们会发送带有新的任期号的 RequestVote RPC，这样会导致当前的领导人回退成Follower状态。新的领导人最终会被选出来，但是被移除的服务器将会再次超时，然后这个过程会再次重复，导致整体可用性大幅降低。
为了避免这个问题，当服务器确认当前Leader存在时，服务器会忽略 RequestVote RPC。特别的，当服务器在当前最小选举超时时间内收到一个 RequestVote RPC，它不会更新当前的任期号或者投出选票。这不会影响正常的选举，每个服务器在开始一次选举之前，至少等待一个最小选举超时时间。然而，这有利于避免被移除的服务器扰乱：如果Leader能够发送心跳给集群，那么它就不会被更大的任期号废除。
这条分界线之前都是Raft算法的干货，如果需要深入了解Raft算法实现过程是如何满足一致性要求，请看下面的分析过程。
算法总结
只要按照以上Leader选举，日志复制，安全性去实现，即实现了Raft一致性算法了。
现在回过头来看看，算法实现是如何保证Raft的五大原则的呢？
-
选举安全原则（Election Safety）—— 一个任期（term）内最多允许有一个Leader被选上
在一个任期内，每个集群节点只能为一个Candidate投票。每个集群节点内部都维护着一个VoteFor的参数，以保证一个任期内，只能为一个Candidate进行投票，而且只有赢得大多数选票的Candidate才能晋升为Leader
-
领导人只增加原则（Leader Append-Only）—— Leader永远不会修改或者删除自己的日志，它只会增加日志
实现要求就是如此，这个原则没什么好说的。
-
日志匹配原则（Log Matching）—— 如果两个节点日志序列在相同的索引位置上的日志项的任期号相同，那么我们就认为这个日志从头到这个索引位置之间的日志完全相同
日志复制过程要求Follower完全按照Leader的日志序列顺序复制，不符合Leader日志序列的日志项会被覆盖复制或删除。
-
领导人完全原则（Leader Completeness) —— 如果一个日志项在一个给定任期内被提交，那么这个日志项一定会出现在所有任期号更大的领导人中
这是由于一个日志项只有在Leader任期内创建，而且在任期内被大多数集群节点复制之后，才可以认为是被提交的（释疑部分给出了为什么不能提交在非Leader任期内创建并被大多数集群节点复制的日志项），只有被提交的日志项才会被复制状态机执行。而Candidate能晋升为Leader的前提条件有两个：一个是赢得大多数选票，另一个是Candidate的日志要比投票节点的新。正因为大多数集群节点会含有已提交的日志，而能晋升为Leader的节点的日志序列又要比大多数集群节点的日志序列要新，因此已提交的日志项必定在新的领导人中。
-
状态机安全原则（State Machine Safety）—— 如果一个服务器已经将给定索引位置的日志项应用到状态机中，则所有其他服务器不会在该索引位置应用不同的日志项
由于已经满足了日志匹配原则和领导人完全原则，并且，只有已提交的日志才会被复制状态机执行，所以必然满足状态机安全原则。
Raft一致性算法实现的关键点描述如下：
- 每个集群节点需要维护一个VoteFor参数，用于保证一个任期内，只能为一个Candidate进行投票
- 在一个任期内赢得大多数选票的Candidate才能晋升为Leader，投票条件是Candidate的任期号或日志比自己更新
- Leader永远不会修改或者删除自己的日志，它只会增加日志
- 只有在Leader任期内创建的日志，并且被大多数集群节点复制之后，才可以被认为是已提交。
- 只有被提交的日志才能被复制状态机执行
- 当有集群配置变更时，会先把日志同步给$C_{new}$集群，保证所有集群节点（新/旧）日志不会相差太多，再将切换至$C_{old,new}$集群配置，$C_{old,new}$提交后就可以切换为$C_{new}$集群配置了。
- 集群节点只有在最小投票超时时间2内没有收到Leader心跳消息，才会对RequestVote RPC作出响应，这是为了避免集群配置变更后被移除的服务器扰乱。
算法释疑
为什么只能提交由Leader当前任期创建的日志？而不能按复制的数量进行提交呢？
上图描述了在5个时间点（a~e），集群中5个节点（s1~s5）的状态。方框内的数字表示任期号，而最上面的数字则表示日志索引。
在(a)状态中，S1是Leader，但索引2只复制到了两个节点（S1，S2)，因此索引2是未提交状态。
在(b)状态中，S1宕机了，S5通过S3和S4的投票晋升为Leader，而且接收到客户端请求并创建了索引为2，任期号为3的日志。
在(c)状态中，S5宕机了，S1通过S2和S3的投票晋升为Leader，并且继续复制未提交的日志(如图中所示索引2/任期为2的日志)达到大多数的条件，并且接收了来自客户端的请求生成索引为3，任期号为4的日志。
在(d)状态中，S1在未大多数节点复制索引3时就宕机了，S5再次通过S3和S4的投票晋升为Leader，根据日志复制规则，最终所有节点的索引2都被S5中的日志覆盖。
在(e)状态中，S1在大多数节点复制索引3但还未来得及提交时就宕机了，此时能赢得选票晋升为Leader的就只有那些大多数已复制最新日志的节点，因为S4/S5节点的日志都已经比较旧了，无法赢得选票。
(d)状态正好解析了这一个问题，如果在(c)状态中对索引2提交了，再演变成(d)状态，就会出现执行日志不一致的情况了。而(e)状态说明了Leader只要在大多数个节点中成功复制了日志，就可以认为该日志是已经提交了。
日志压缩
Raft的日志是会不断增长的，也会占用越来越多的存储空间，当集群配置变更时，日志同步到新服务器的时间则会越来越长。这就意味着Raft日志的增长是会影响集群的可用性的。
为了解决这个问题，Raft使用了快照（snapshot）的压缩方式进行日志压缩。原理如下图所示:
Raft日志压缩是集群各个节点独立进行的。Raft只会对已提交的日志进行压缩。snapshot只保留要压缩的操作日志中的最终操作结果，省去了中间操作过程从而达到压缩的目的，last included index是指snapshot压缩中最大的日志索引，last included term是last included index对应索引的任期号。一旦服务器完成快照，就可以把last included index之前的日志和快照删除了。
当一个Follower或有新服务器加入到集群时，此时就需要Leader把快照传输给它们了。Raft使用了另一个RPC请求完成快照的安装。
安装快照RPC请求
| 参数 | 描述 |
|---|---|
| term | Leader的任期 |
| leaderId | 为了Follower能重定向到客户端 |
| lastIncludedIndex | 快照中包含的最后日志条目的索引值 |
| lastIncludedTerm | 快照中包含的最后日志条目的任期号 |
| offset | 分块在快照中的偏移量 |
| data[] | 快照块的原始数据 |
| done | 如果是最后一块数据则为真 |
| 返回值 | 描述 |
|---|---|
| term | currentTerm，用于Leader更新自己 |
快照安装的RPC请求会把原快照划分成一个个块进行传输的
客户端交互
客户端要发起请求时，会从集群中选择其中一个节点发送，如果接收请求的节点不是Leader，会拒绝请求，并返回给客户端Leader的网络信息（包括ip/端口)，客户端会重连Leader再次发起请求。
Raft的目标是要实现线性化语义（linearizable semantics）（每一次操作立即执行，在它调用和收到正常回复之间只执行一次）。在客户端请求后和收到响应前，Leader崩溃了，此时客户端会再次发起请求重试，但此时，集群有可能已经提交了该请求，这种情况下会导致命令重复执行。Raft客户端会在每一个请求中带上一个唯一的序列号来避免这个问题。当集群发现序列号所对应的命令已经执行过了，则直接返回该次请求的响应。
只读操作（read-only）是不需要记录操作日志的，但如果不对只读操作添加一些限制的话，可能会导致读操作返回过期的数据。Leader在返回数据给客户端之前，可能已经被其他Leader所取替，但它还未感知到，这种情况下就有可能返回过期数据了。线性化的读操作必须不能返回过期数据！Raft要求Leader在处理只读操作之前，必须先与大多数集群节点交换一次心跳，而且新上任的Leader必须新提交一个空操作的日志项，以确保未提交的日志可以得到提交，以保证新上任的Leader状态是最新的。