1 整体描述

在Raft被提出来之前，Paxos协议是第一个被证明的一致性算法，但是Paxos的论文非常难懂，导致基于Paxos的工程实践和教学都十分头疼，于是Raft在设计的过程中，就从可理解性出发，使用算法分解和减少状态等手段，目前已经应用非常广泛。所以本文通过对https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md这篇论文的梳理， 进行了一些归纳总结。

在Raft中，问题可以分解为：领导选取、日志复制、安全和成员变化。每一个步骤都是一个比较清晰的待解决问题， 便于理解， 接下里我们先来了解一下Raft协议中所涉及的几个基本概念。

2 基本概念

2.1 复制状态机（Replicated State Machine）

1BB4BDB869844A08A5C39DF25B673FAA.png

• 复制状态机通过复制日志来实现：

  • 日志：每台机器保存一份日志，日志来自于客户端的请求，包含一系列的命令

  • 状态机：状态机会按顺序执行这些命令

  • 一致性模型：分布式环境下，保证多机的日志是一致的，这样回放到状态机中的状态是一致的

• 一致性算法作用于一致性模型，一般有以下特性：

  • safety：在非拜占庭问题下（网络延时，网络分区，丢包，重复发包以及包乱序等），结果是正确的

  • availability：在半数以上机器能正常工作时，则系统可用

  • timing-unindependent：不依赖于时钟来保证日志一致性，错误的时钟以及极端的消息时延最多会造成可用性问题

• 注意：真实的实现中，建议状态机的每个命令操作都采用幂等的，这样一致性的保证会更容易。

2.2 服务器状态

每台服务器一定会处于三种状态：

1.  领导者

2.  候选人

3.  追随者

image.png

追随者只响应其他服务器的请求。如果追随者没有收到任何消息，它会成为一个候选人并且开始一次选举。收到大多数服务器投票的候选人会成为新的领导人。领导人在它们宕机之前会一直保持领导人的状态。

2.3 任期(Term)

Raft 算法将时间划分成为任意不同长度的任期（term）。任期用连续的数字进行表示。每一个任期的开始都是一次选举（election），一个或多个候选人会试图成为领导人。如果一个候选人赢得了选举，它就会在该任期的剩余时间担任领导人。在某些情况下，选票会被瓜分，有可能没有选出领导人，那么，将会开始另一个任期，并且立刻开始下一次选举。Raft 算法保证在给定的一个任期最多只有一个领导人。

image.png

2.4 RPC

Raft 算法中服务器节点之间通信使用远程过程调用（RPCs），并且基本的一致性算法只需要两种类型的 RPCs。请求投票（RequestVote） RPCs 由候选人在选举期间发起，然后附加条目（AppendEntries）RPCs 由领导人发起，用来复制日志和提供一种心跳机制。为了在服务器之间传输快照增加了第三种 RPC。当服务器没有及时的收到 RPC 的响应时，会进行重试， 并且他们能够并行的发起 RPCs 来获得最佳的性能。

RPC有三种：

1.  RequestVote RPC：候选人在选举期间发起

2.  AppendEntries RPC：领导人发起的一种心跳机制，复制日志也在该命令中完成

3.  InstallSnapshot RPC: 领导者使用该RPC来发送快照给太落后的追随者。

超时设置：

1.  BroadcastTime : 领导者的心跳超时时间

2.  Election Timeout: 追随者设置的候选超时时间

3.  MTBT :指的是单个服务器发生故障的间隔时间的平均数

Raft协议对物理是时钟一致性没有要求，不需要通过原子钟NTP来校准时间，但是对于超时时间的设置有要求，具体规则如下：

BroadcastTime << ElectionTimeout << MTBF

两个原则：

• 1. BroadcastTime应该比ElectionTimeout小一个数量级，为的是使领导人能够持续发送心跳信息（heartbeat）来阻止追随者们开始选举；
• 2. ElectionTimeout也要比MTBF小几个数量级，为的是使得系统稳定运行。

一般BroadcastTime大约为0.5毫秒到20毫秒，ElectionTimeout一般在10ms到500ms之间。大多数服务器的MTBF都在几个月甚至更长。

3 步骤分解

3.1 领导人选取

触发条件：

1.  一般情况下，追随者接到领导者的心跳时，把ElectionTimeout清零，不会触发；

2.  领导者故障，追随者的ElectionTimeout超时发生时，会变成候选者，触发领导人选取；

触发动作：

1. 转为candidate角色；
2. 为自己投票；
3. 发起RequestVote RPC；

判决：

1.  获得超过半数服务器的投票，赢得选举，成为领导者；

2.  另一台服务器赢得选举，并接收到对应的心跳，成为追随者；

3.  选举超时，没有任何一台服务器赢得选举，自增当前任期，重新发起选举；

选举条件：

• 1. 候选者等待投票时，可能会接收到来自其它声明为领导人的的AppendEntries RPC。如果该领导人的任期（RPC中有）比当前候选人的当前任期要大，则候选人认为该领导人合法，并转换成追随者；如果RPC中的任期小于候选人的当前任期，则候选人拒绝此次RPC，继续保持候选人状态；
• 2. 服务器在一个任期内，最多能给一个候选人投票，采用先到先服务原则；
• 3. 我们来重点说这段话If votedFor is null or candidateId, and candidate’s log is atleast as up-to-date as receiver’s log, grant vote votedFor是server保存的投票对象，一个server在一个term内只能投一次票。如果此时已经投过票了，即votedFor就不为空，那么此时就可以直接拒绝当前的投票（当然还要检查votedFor是不是就是请求的candidate）。如果没有投过票， 则对比candidate的log和当前server的log哪个更新，比较方式为谁的lastLog的term越大谁越新，如果term相同，谁的lastLog的index越大谁越新 。
• 4 candidate统计投票信息，如果过半同意了则认为自己当选了leader，转变成leader状态，如果没有过半，则等待是否有新的leader产生，如果有的话，则转变成follower状态，如果没有然后超时的话，则开启下一次的选举。

选举失败：

• 候选人既没有赢得选举也没有输掉选举：
  如果许多追随者在同一时刻都成为了候选人，选票会被分散，可能没有候选人能获得大多数的选票。当这种情形发生时，每一个候选人都会超时，并且通过自增任期号和发起另一轮 RequestVote RPC 来开始新的选举。然而，如果没有其它手段来分配选票的话，这种情形可能会无限的重复下去。所以Raft使用的随机的选举超时时间（150~300ms之间），来避免这种情况发生。

3.2 日志复制

image.png

日志由有序编号的日志条目组成。每个日志条目包含它被创建时的任期号（每个方块中的数字），并且包含用于状态机执行的命令。如果一个条目能够被状态机安全执行，就被认为可以提交了。每个日志条目也包含一个整数索引来表示它在日志中的位置。

接受命令的过程：

1.  领导者接受客户端请求；

2.  领导者把指令追加到日志；

3.  发送AppendEntries RPC到追随者；

4.  领导者收到大多数追随者的确认后，领导者Commit该日志，把日志在状态机中执行，并返回结果给客户端；

提交过程：

1.  在下一个心跳阶段，领导者再次发送AppendEntries RPC给追随者，日志已经commited；

2.  追随者收到Commited日志后，将日志在状态机中执行。

Raft 能够接受，复制并且应用新的日志条目只要大部分的服务器是正常的。在通常情况下，一条新的日志条目可以在一轮 RPC 内完成在集群的大多数服务器上的复制；并且一个速度很慢的追随者并不会影响整体的性能。

3.3 安全性

到目前为止描述的机制并不能充分的保证每一个状态机会按照相同的顺序执行相同的指令，例如：一个跟随者可能会进入不可用状态同时领导人已经提交了若干的日志条目，然后这个跟随者可能会被选举为领导人并且覆盖这些日志条目；因此，不同的状态机可能会执行不同的指令序列。

3.3.1 日志复制原则（Append-Only)

image.png

当最上边的领导人掌权之后，追随者日志可能有以下情况（a~f）。一个格子表示一个日志条目；格子中的数字是它的任期。一个追随者可能会丢失一些条目（a, b）；可能多出来一些未提交的条目（c, d）；或者两种情况都有（e, f）。例如，场景 f 在如下情况下就会发生：如果一台服务器在任期2时是领导人并且往它的日志中添加了一些条目，然后在将它们提交之前就宕机了，之后它很快重启了，成为了任期3的领导人，又往它的日志中添加了一些条目，然后在任期2和任期3中的条目提交之前它又宕机了并且几个任期内都一直处于宕机状态。

领导人通过强制追随者们复制它的日志来处理日志的不一致。这就意味着，在追随者上的冲突日志会被领导者的日志覆盖。（下面几节会证明为什么这么做是安全的）

为了使得追随者的日志同自己的一致，领导人需要找到追随者同它的日志一致的地方，然后删除追随者在该位置之后的条目，然后将自己在该位置之后的条目发送给追随者。这些操作都在 AppendEntries RPC 进行一致性检查时完成。

领导者永远不会覆盖自己已经存在的日志条目；

日志永远只有一个流向：从领导者到追随者；

3.3.2 选举约束

• master选举最终安全性目标： 被选举出来的leader必须要包含所有已经提交的entries
  如leader针对复制过半的entry提交了，但是某些follower可能还没有这些entry，当leader挂了，该follower如果被选举成leader的时候，就可能会覆盖掉了上述的entry了，造成不一致的问题，所以新选出来的leader必须要满足上述约束。

• raft简单实现：只要当前server的log比半数server的log都新就可以，具体到每一个node的比对就是上述说的“谁的lastLog的term越大谁越新，如果term相同，谁的lastLog的index越大谁越新”

正是这个实现并不能完全实现约束，才会产生下面4.3.3中另外一个问题，一会会详细案例来说明这个问题， 我们先来看看到现在为止整个系统是安全的么？

leader挂掉时机：

a、 尚未打log： 完全无影响

b、 自己写了log， 但还未发requestRPC ：不会对client返回处理成功， 但是会在自己服务器中保留一份log， 未来新选的master会刷掉这份log（也就是3.3.1中设置的条件）

c、 发了requestRPC 尚未commit ： 收到消息的follow都会保留一份log， 但因为还未commit 所以不会对client返回处理成功， 但是此处是存有疑问的。

d、 commit 之后： 已经commit了， 也就是说client认为已经处理成功了， 此时挂了的话剩下的机器中有一多半都已经保存了数据log， 他们竞争master时也会保留已经提交的数据（参见3.3..2）。

最终会剩下一个问题， 也就是c中新接手的master怎么处理之前尚未commit的数据， 再来看之前的选举限制：

“lastLog的term越大谁越新，如果term相同，谁的lastLog的index越大谁越新”

在这种情况下我们选举master其实只是关注了log新旧， 并没有关注commit与否， 在3.3.3 中例子可以发现现在的约束是无法实现master选举的最终安全性目标的

3.3.3 如何处理任期之前的日志条目

在Raft算法中，当一个日志被安全的复制到绝大多数的机器上面，即AppendEntries RPC在绝大多数服务器正确返回了，那么这个日志就是被提交了，然后领导者会更新commit index。

image.png

详细解释如下：

a场景：s1是leader,此时处于term2，并且将index为2的entry复制到s2上

b场景：s1挂了，s5利用s3,s4,s5当选为leader，处于term3,s5在index为2的位置上接收到了新的entry

c场景：s5挂了，s1当选为leader，处于term4，s1将index为2,term为2的entry复制到了s3上，此时已经满足过半数了

重点就在这里：此时处于term4,但是之前处于term2的entry达到过半数了，s1是提交该entry呢还是不提交呢？

• 假如s1提交的话，则index为2，term为2的entry就被应用到状态机中了，是不可改变了，此时s1如果挂了，来到term5，s5是可以被选为leader的，因为按照之前的log比对策略来说，s5的最后一个log的term是3比s2 s3 s4的最后一个log的term都大。一旦s5被选举为leader，即d场景，s5会复制index为2,term为3的entry到上述机器上，这时候就会造成之前s1已经提交的index为2的位置被重新覆盖，因此违背了一致性。

• 假如s1不提交，而是等到term4中有过半的entry了，然后再将之前的term的entry一起提交（这就是所谓的间接提交，即使满足过半，但是必须要等到当前term中有过半的entry才能跟着一起提交），即处于e场景，s1此时挂的话，s5就不能被选为leader了，因为s2 s3的最后一个log的term为4比s5的3大，所以s5获取不到投票，进而s5就不可能去覆盖上述的提交

从这个案例中我们得到的一个新约束就是：

当前term的leader不能“直接”提交之前term的entries 必须要等到当前term有entry过半了，才顺便一起将之前term的entries进行提交

所以raft靠着这2个约束来进一步保证一致性问题。

再来仔细分析这个案例，其问题就是出在：上述leader选举上，s1如果在c场景下将index为2、term为2的entry提交了，此时s5也就不包含所有的commitLog了，但是s5按照log最新的比较方法还是能当选leader。

那就是说log最新的比较方法并不能保证2中的选举约束即
被选举出来的leader必须要包含所有已经提交的entries
所以可以理解为：正是由于上述选举约束实现上的简单实现并不靠谱， 才导致又加了这么一个不能直接提交之前term的entries的约束。

3.3.4 安全性论证讨论

Leader Completeness： 如果一个entry被提交了，那么在之后的leader中，必然存在该entry。

经过上述2个约束，就能得出Leader Completeness结论。正是由于上述“不能直接提交之前term的entries”的约束，所以任何一个entry的提交必然存在当前term下的entry的提交。那么此时所有的server中有过半的server都含有当前term(也是当前最大的term)的entry，假设serverA将来会成为leader，此时serverA的lastlog的term必然是不大于当前term的，它要想成为leader，即和其他server pk 谁的log最新，必然是需要满足log的index比他们大的，所以必然含有已提交的entry。

client端

在client看来如果client发送一个请求，leader返回ok响应，那么client认为这次请求成功执行了，那么这个请求就需要被真实的落地，不能丢。

如果leader没有返回ok，那么client可以认为这次请求没有成功执行，之后可以通过重试方式来继续请求。

leader挂

一旦你给客户端回复OK的话，然后挂了，那么这个请求对应的entry必须要保证被应用到状态机，即需要别的leader来继续完成这个应用到状态机。

一旦leader在给客户端答复之前挂了，那么这个请求对应的entry就不能被应用到状态机了，如果被应用到状态机就造成客户端认为执行失败，但是服务器端缺持久化了这个请求结果，这就有点不一致了。

这个原则同消息队列也是一致的。再来说说什么叫消息队列的消息丢失（很多人还没真正搞明白这个问题）：client向服务器端发送消息，服务器端回复OK了，之后因为服务器端自己的内部机制的原因导致该消息丢失了，这种情况才叫消息队列的消息丢失。如果服务器端没有给你回复OK，那么这种情况就不属于消息队列丢失消息的范畴。

再来看看raft是否能满足这个原则：

• leader在某个entry被过半复制了，认为可以提交了，就应用到状态机了，然后向客户端回复OK，之后leader挂了，是可以保证该entry在之后的leader中是存在的

• leader在某个entry被过半复制了，然后就挂了，即没有向客户端回复OK，raft的机制下，后来的leader是可能会包含该entry并提交的，或可能直接就覆盖掉了该entry。如果是前者，则该entry是被应用到了状态机中，那么此时就出现一个问题：client没有收到OK回复，但是服务器端竟然可以成功保存了， 为了掩盖这种情况，就需要在客户端做一次手脚，即客户端对那么没有回复OK的都要进行重试，客户端的请求都带着一个唯一的请求id，重试的时候也是拿着之前的请求id去重试的服务器端发现该请求id已经存在提交log中了，那么直接回复OK，如果不在的话，那么再执行一次该请求。

follower挂

follower挂了，只要leader还满足过半条件就一切正常。他们挂了又恢复之后，leader是会不断进行重试的，该follower仍然是能恢复正常的

follower在接收AppendEntries RPC的时候是幂等操作

3.3.4 集群成员变更

集群成员的变更和成员的宕机与重启不同，因为前者会修改成员个数进而影响到领导者的选取和决议过程，因为在分布式系统这对于majority这个集群中成员大多数的概念是极为重要的。

简单的做法是，运维人员将系统临时下线，修改配置，重新上线。但是这种做法存在两个缺点：

1.  更改时集群不可用

2.  人为操作失误风险

直接从一种配置转到新的配置是十分不安全的

如下图所示：

image.png

因为各个机器可能在任何的时候进行转换。在这个例子中，集群配额从 3 台机器变成了 5 台。不幸的是，存在这样的一个时间点，两个不同的领导人在同一个任期里都可以被选举成功。一个是通过旧的配置，一个通过新的配置。

两阶段方法保证安全性：

• 在 Raft 中，集群先切换到一个过渡的配置，我们称之为共同一致（joint consensus）；
  一旦共同一致已经被提交了，那么系统就切换到新的配置上。共同一致是老配置和新配置的结合。

• 共同一致允许独立的服务器在不影响安全性的前提下，在不同的时间进行配置转换过程。此外，共同一致可以让集群在配置转换的过程中依然响应服务器请求。

一个领导人接收到一个改变配置从 C-old 到 C-new 的请求，他会为了共同一致存储配置（图中的 C-old,new），以前面描述的日志条目和副本的形式。一旦一个服务器将新的配置日志条目增加到它的日志中，他就会用这个配置来做出未来所有的决定。领导人完全特性保证了只有拥有 C-old,new 日志条目的服务器才有可能被选举为领导人。当C-old,new日志条目被提交以后，领导人在使用相同的策略提交C-new，如下图所示，C-old 和 C-new 没有任何机会同时做出单方面的决定，这就保证了安全性。

image.png

一个配置切换的时间线。虚线表示已经被创建但是还没有被提交的条目，实线表示最后被提交的日志条目。领导人首先创建了 C-old,new 的配置条目在自己的日志中，并提交到 C-old,new 中（C-old,new 的大多数和 C-new 的大多数）。然后他创建 C-new 条目并提交到 C-new 中的大多数。这样就不存在 C-new 和 C-old 可以同时做出决定的时间点。

3.3.5 日志压缩

日志会随着系统的不断运行会无限制的增长，这会给存储带来压力，几乎所有的分布式系统(Chubby、ZooKeeper)都采用快照的方式进行日志压缩，做完快照之后快照会在稳定持久存储中保存，而快照之前的日志和快照就可以丢弃掉。

Raft的具体做法如下图所示：

image.png

与Raft其它操作Leader-Based不同，snapshot是由各个节点独立生成的。除了日志压缩这一个作用之外，snapshot还可以用于同步状态：slow-follower以及new-server，Raft使用InstallSnapshot RPC完成该过程，不再赘述。