一、复制状态机

复制状态机（Replicated state machine）的概念就是，相同的初始状态 + 相同的输入 = 相同的结束状态。也就意味在多节点集群中，从相同的初始状态开始，执行相同的一串命令，产生相同的最终状态。

 

在 raft 中，leader将客户端请求封装成一个一个 log entry 中，将这些 log 发送到 follow 节点，然后大多数的节点按照同样的顺序应用 log entry 中的 command，依据复制状态机的理论，大家最后的状态是会一致的。在分布式场景中，各个节点就是依靠共识算法，保证命令序列的一致，从而始终保持它们的状态一致，从而实现高可用性。

论文提及raft算法的特性有以下几点：

• 安全性保证(绝对不会返回一个错误的结果):在非拜占庭错误情况下，包括网络延迟、分区、丢 包、冗余和乱序等错误都可以保证正确。（这里的拜占庭错误指的是节点的本身就不可靠，变成集群中的恶意节点，它为了阻挠真实信息的传递以及有效一致的达成，会向各个节点发送前后不一致的信息）
• 可用性:集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信，就可以保证可用。 因此，一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器被停止就认为是失败。他们当有稳定的存储的时候可以从状态中恢复回来并重新加入集群。
• 不依赖时序来保证一致性:物理时钟错误或者极端的消息延迟只有在最坏情况下才会导致可用性问题。
• 通常情况下，一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分 比较慢的节点不会影响系统整体的性能。

 

二、状态变化

在任意时刻，每个服务器节点都只处于 leader，follower或candidate这三个状态之一。

• leader：领导者，在通常情况下，系统中只有一个领导人并且其他的节点全部都是跟随者。
• follow：跟随者，他们不会发送任何请求，只是简单的响应来自领导者或者候选人的请求。
• candidate：选举者，当集群没有领导者时，跟随者会转变成 candidate

 

starts up：集群启动时

time out, start election：follow 在没有收到 leader 心跳后开始选举变成选举者 candidate；

time out，new election：在当前选举中没有出现 leader，此轮次超时后进行下一轮选举

dicocers current leader or new term：当发现已经选出新的 leader，也就是收到 leader 的心跳信息，或者发现已经开始新的 term 任期，选举者状态 candidate 将会转化成 follow。

dicover serer with higher term：当前的 leader 可能因为网络分区的问题和集群中的其他 follow 失去心跳联系，这时候集群选举出了新的 leader，这时候 leader 就要变成 follow 状态。

receives votes from mahority servers：当 candidate 收到集群中大多数的投票时，会被选举成新的 leader，进入 leader 状态

这图展示了 raft 中几个状态的转化。

 

在论文中解释了 term 任期

 

raft将时间划分成一个一个的任期，每个任期开始都是一个选举， 选举成功后 leader 会管理集群到任期结束，如果任期中没有选举成功，那么这个任期会因为没有领导人而结束，这时候 candidate 因为选举超时（也就是没有选出 leader 的超时时间）而自动开启下一个任期 term。

他们通过 rpc 请求来进行服务器之间的远程调用和通信，并且基本的一致性算法只需要两种类型的 RPCs。请求投票(RequestVote) RPCs 由候选人在选举期间发起，然后附加条目 (AppendEntries)RPCs 由领导人发起，用来复制日志和提供一种心跳机制。除此之外在服务器之间传输快照增加了第三种 RPC。

• RequestVote RPC（请求投票）：由 candidate 在选举期间发起。
• AppendEntries RPC（追加条目）：由 leader 发起，用来复制日志和提供一种心跳机制。

在论文中对于 raft 的 rpc 实现有一个算法浓缩总结：还有一个 rpc 是 state 的状态查询 rpc 就不列举了

 

除此之外所有的节点需要遵循的算法规则为：

英文版本

 

三、领导者选举

raft 内部有一种心跳机制，如果存在 leader，那么它就会周期性的向所有 follower 发送心跳，来维持自己的地位。如果 follower 在一段时间灭有收到心跳，那么它会认为没有 leader，开始进行下一轮选举。

开启下一个选举后，follow 会转先增加自己的当前任期，并且转变成 candidate 状态，然后投票给自己，向其他节点发送 RequestVote RPC。这里因为有超时控制，follower 会根据超时时间陆续进入下一轮选举 term，所以不存在同时都变成 candidate 投票给自己的情况。

对于没有成为 canditate 的 follower 节点，按照先来先得的原则进行投票。

当 s2 宕机后开始投票选举确认后提交后正式进入term=3的任期

这里的状态机演示可以在网页上自行调试：https://raft.github.io/raftscope/index.html

当 candidate 在等待其他节点投票给自己的时候，此时会有三种结果，上图是成功当选的结果：

• 它获得超过半数投票赢得了选举 -> 成为主 leader 后发送心跳
• 其他节点赢得选举（这里就是上面的 S4 节点），收到新 leader 心跳后，如果新 leader 的任期号不小于自己当前的任期号，那么就从 candidate 变成  follower 状态
• 一段时间后如果没有任何获胜者，每个candidate 都在一个自己的随机选举超时时间后增加任期号开始新一轮的投票，论文中给的随机选举超时时间为 150~300ms。

 

四、日志复制

集群中 leader 是肯定有最新的日志的，但是其他节点不清楚，基本都是处于一直追赶 leader 日志进度的情况。

在客户端提供服务中，客户端的每一个请求都包含一条被复制状态机执行的指令。领导人把这条指令作为一条新的日志条目附加到日志中去，然后并行的发起附加条目 RPC 给其他的服务器，让他们复制这条日志条目。当这条日志条目被安全的复制

一条日志中需要三个信息：

• 状态机指令（就是存储的数据比如下图的 x->3）
• leader 的任期号（term）
• 日志号（日志索引）

图中日志由有序序号标记的条目组成。每个条目都包含创建时的任期号(图中框中的数字)，和一个状态机需要执行的指令。

一个条目当可以安全的被应用到状态机中去的时候，就认为是可以提交了。 是的，日志还有两个状态，就是 未提交 和 已提交

未提交指的是，当 leader 发送 AppendEntriesRPC 请求给其他节点后，让他们复制该日志条目，这时候日志的状态就是未提交的。一但超过半数的节点 follower 响应成功，也就意味着这个日志已经成功复制到大多数节点上了，那么此时leader就会把结果返回给客户端，并且在本地也执行复制保存该日志的操作，在leader中此时日志条目是已提交状态。但是注意的是，此时大多数节点中的日志条目还没有提交。是的，raft 是使用的累计确认的机制，通过下一个心跳才让大多数提交当前日志条目的，因为 follower 在下一个心跳来临之前并不知道该日志是否需要改成已提交的。

当收到S5领导者节点发送的append请求后

 

当S5节点收到大多数节点的回复后会把日志条目设置为已提交发送下一个心跳确认会带上最后一个确认的日志条目最后

 

 

下面这里讨论一下当日志复制过程中如果 leader 和 follow 出现崩溃和缓慢超时的情况，raft 算法是怎么保证继续日志复制并且保证每个副本顺序一致

1. 如果有 follower 因为某些原因没有给 leader 响应，那么 leader 会不断的重新发送追加条目请求 appendRPC，哪怕 leader 已经回复了客户端

2. 如果有 follower 崩溃后恢复，此时 raft 追加条目的一致性检查生效，保证 follower 能按照顺序回复崩溃后缺失的进度

raft的一致性检查，leader 在每一个发往 follower 的追加条目 appendRPC 中，会放入前一个日志条目的索引prelogIndex 和 任期号term。 如果 follower 找不到这个前一个日志，那么它就会拒绝日志，leader 收到拒绝后，会发送前一个日志条目，从而逐渐定位到 follower 第一个缺失的日志。这里其实对于不同的 raft 实现算法，会有一定的优化，leader 收到拒绝后可以不是发送前一个日志条目，可以通过二分查找啊，或者下一个发送当前term任期的第一个日志，加快查找的进程。

下图，S3落后 leader 的日志条目非常多，所以在日志复制时：

第一次，S5发送给S3 appendRPC 时，S3 因为 preIndexIndex（等于8） 和它自己当前的 logCurrentindex（等于6） 不符合，所以第一次的时候 S5 并不能将自己的 index=9 的日志条目复制给 s3

第二次，S5发送给S3 appendRPC 时，preIndexIndex=7，还是和S3的 logCurrentindex（等于6） 不符合，所以还是不能将 index=8 的日志条目复制给 s3

第三次，成功复制，将 index=7 的日志条目复制给 s3

3. 如果 leader 崩溃，那么崩溃的 leader 可能已经复制到部分 follower ，但是数据还没有提交 ，而被选出的新leader又可能不具备这些日志，这样就有部分 follow 中的日志和新 leader 的日志不相同。

raft 在这种情况下，leader 会通过强制 follower 复制它的日志来解决不一致的问题，这意味着 follower 中跟 leader 中冲突的日志条目会被新 leader 的日志条目覆盖（注意这里说是未提交的，也就是虚线的数据，意味着这些数据并没有提交，所以不违反外部一致性原则）

例如论文中提出的例子

总结：

ralf 通过这样的日志复制机制，leader 不需要任何特殊的操作来使得日志恢复到一致状态，leader 只需要进行正常的操作，然后日志就能在 appendRPC 回复中通过一致性检查失败的时候自动趋于一致。

leader 从来不会覆盖或者删除自己的条目，只会让 follower 强制和 leader 保持一致，这样可以保证：

1. 只要过半的服务器郑航运行，raft 就能接收，复制并应用新的日志条目
2. 在正常情况下，新的日志条目可以在一个 rpc 来回中杯复制给集群中过半的机器
3. 单个运行慢的follow（如果不是超过集群的大多数）并不会影响整体的性能，也不会影响数据的一致性

 

五、安全性

上面日志复制实际上是解决数据一致性的问题，那么安全性的问题是什么？论文举例说，一个跟随者可能会进入不可用状态同时领导人已经提交了若干的日志条目，然后这个跟随者可能会被选举为领导人并且覆盖这些日志条目;因此， 不同的状态机可能会执行不同的指令序列。 也就是集群中可能选择一个日志条目落后很多的节点当选成为 leader，并且强制覆盖其他节点的数据。以下规则可以保证在各类宕机问题下都不会出错：

1. Leader 宕机：选举限制
2. Leader 宕机：新 leader 是否提交之前任期内的日志条目
3. Follower 和  Candidate 宕机处理
4. 时间和可用性限制

下面进行逐条的解释：

• Leader 宕机：选举限制

如果一个 follower 落后了 leader 若干条日志（但是没有漏一整个任期），那么下次选举时，它依然可能当选为 leader。当它当选为 leader 时，它因为缺失最新的那部分日志，从而导致状态机和其他节点的不一致，并且永远无法达成一致。所以此规则对候选人增加了一个限制，也就是被选出来的 leader 必须保证为一定包含了之前各个任期所有被提交的日志条目。

在 RequestVoteRPC 中，参数有 lastLogIndex（候选者自己最后一个日志号） 和 lastLogTerm（候选者自己最后一个日志任期）

raft 中收到投票选举请求的节点，会对比自己日志中最后一条日志的条目索引值，和自己当前的任期号比较新来判断是否要投票给这个候选者。如果没有自己的新，它就拒绝投票。

当时这里会出现如下图的情况：(c)中原本已经复制到大多数节点的index=2日志，在(d)中由于S5节点当选为 leader ，则被强制覆盖，导致index=2的数据无了

 

• Leader 宕机：新 leader 是否提交之前任期内的日志条目

如果上面所说的这一段规则，那么必然会出现新leader被选择出来后立马就把旧 term 的数据给覆盖提交的情况。如下图

在 (c) 中，当前的 leader 为 s1，此时的 term=4，此时s1宕机了。然后 s5 当选为最新的 leader ，term=5。此时 s5 顺利的把当前的 index=2 term=3 的日志复制给了全部集群，主要看这个日志条目是虚线框，意味着没有提交的。此时如果再请求添加一个 term=5 index=3 的日志条目，这个时候吧这个日志条目复制发送给其他节点后，蓝色的日志部分才会从虚线变成实现，变成提交状态。

这以规则的目的是保证，新选举出来的 leader 不会在当前 term 内的第一条日志条目请求提交前宕机，也就保证了数据肯定是最新的最可靠的，因为宕机的 leader 它们的数据都不可信，也就是 term=2 和 term=4 任期中提交的数据。虽然复制给了大多数，但是并没有在此任期提交 term=4 的日志数据，所以被认为是脏数据。

• Follower 和 Candidate 宕机处理

这里的崩溃宕机比leader宕机要简单，因为宕机后发送给他们的 requestVote 和 appendEntries 请求都会失败。raft 通过无线重试的方法来处理这种失败，如果崩溃的机器重启了，那么这些rpc就会成功的完成。如果一个服务器接收了一个rpc，但是还没有响应的时候宕机了，那么重启之后会再次收到相同的请求。这里重复的请求是 leader 缓存了这个 follower 节点相关的信息，大多数是 stateRPC 中的参数。这里插个题外话，如果 follower 节点过多的话，会不会导致 leader 的负担非常大，因为每个节点都要发送心跳，然后还要记住每个节点的状态信息？

• 时间和可用性限制

raft 只要满足以下的时间要求，整个系统就能选举出并维持一个稳定的 leader。

 

六、集群成员变更

在集群成员变更，或者需要改变集群配置的时候（比如增删节点、替换宕机的机器或者改变复制的程度），raft可以进行配置变更自动化。因为这个时候其实是最容易出现错误的，比如宕机出现，可能会造成集群脑裂的问题。raft 使用的是类似于两阶段提交的方法，来保证转换过程中不会出现同一任期的两个 leader，不会出现集群变成两个独立的大多数的问题。

比如论文中这里，从三台节点增加到五台节点过程中，S4S5是新加入节点，配置变更的时候会出现 two dishoint majorities ，也就是集群可能会出现两个 leader 。

如下图就是发生上面问题的过程：

 

 

阶段a. 集群存在 S1 ~ S3 三个节点，我们将该成员配置表示为 C-old，绿色表示该节点当前视图(成员配置)为 C-old，其中红边的 S3 为 leader。

阶段b. 集群新增了 S4、S5 两个节点，该变更从 leader 例如，我们将 S1 ~ S5 的五节点新成员配置表示为 C-new，蓝色表示该节点当前视图为 C-new。

阶段c. 假设 S3 短暂宕机触发了 S1 与 S5 的超时选主。

阶段d. S1 向 S2、S3 拉票，S5 向其它全部四个节点拉票。由于 S2 的日志并没有比 S1 更新，因此 S2 可能会将选票投给 S1，S1 两票当选(因为 S1 认为集群只有三个节点)。而 S5 肯定会得到 S3、S4 的选票，因为 S1 感知不到 S4，没有向它发送 RequestVote RPC，并且 S1 的日志落后于 S3，S3 也一定不会投给 S1，结果 S5 三票当选。最终集群出现了多个主节点的致命错误，也就是所谓的脑裂。

 

在 raft 中为了避免出现这样的问题，所以用了两阶段的方法。集群在发起变更的时候会切换到一个过渡的配置，也就是（b）中 leader 为 s3 时，收到集群成员新增的命令，此时会变成联合一致的状态（joint consensus）

1.  第一阶段，leader 发起 C(old-new) 让集群进入联合一致状态，这时候所有 rpc 都要在新旧两个配置中都达到大多数才算成功
2.  第二阶段，leader 发起 C(new) 让集群进入新配置状态，这时候 rpc 只要在新配置集群下能达到大多数就算成功。

在联合一致（joint consensus）中，论文说明此阶段 raft 需要遵循一下几点

• 日志条目被复制给集群中新、老配置的所有服务器。
• 新、旧配置的服务器都可以成为领导人。
• 达成一致(针对选举和提交)需要分别在两种配置上获得大多数的支持。特别是这一条，非常重要

来看看在变更阶段的配置切换示意图

 

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

估计大多人看到这里还是会比较懵逼，下面我们分别讨论下如果 leader 在上图不同时段宕机，集群会发生什么变化，就知道 raft 是怎么避免脑裂问题的发生了。

1. leader 在 C(old-new) 联合一致未提交的时候宕机 

 

S1S2S3是旧集群，S4S5是新加入集群，当s3领导者开始提交 C(old-new) 发起联合一致时，注意此时还没提交 C(old-new) 。这个时候 S3 宕机，S1S2选举超时开始下一轮term，然后S1S2会产生一个老配置的 leader，因为可以投票给自己并且获取到对方一票，所以 S1S2 都有可能变成旧集群的 leader，而不需要宕机的 S3。

然后 S3S4S5 集群中的任何一个想要成为 leader 的话，需要在老配置集群 S1S2S3 ，和新集群 S1S2S3S4S5 中都拿到超过半数选票才能当选。S4 和 S5 是不可能成为新 leader 的，因为在旧配置 S1S2 中根本不知道有新集群的节点 S4S5，所以旧集群肯定是不能拿到选票的，也就不可能成为旧集群的 leader。唯一有机会成为 leader 的S3，如果在 S1S2 之中成为 leader 后，也是不可能成为旧集群的 leader 的，所以集群就回退到联合一致的状态之前了，也就是集群变更失败，但是不会出现两个 leader。

如果在 S1S2 超时之前，S3就从宕机恢复，并且成为旧集群的leader，并且在新集群也硬的了大多数，也就是 S4S5 的选票，那么 S3 从宕机中恢复，继续开始集群成员变更。

在S3中将 C(oid-new) 配置都复制到了新旧集群中的大多数的时候，比如下面

 

旧集群：S2S3，新集群：S2S3S4。这时候就可以提交 C(old-new) 了

2. leader 如果在 C(old-new) 已提交但 C-new 未发起的时候宕机

这个时候选举限制安全性规则决定了选出的新 leader 肯定是具有 C(old-new) 配置的，所以也就不存在脑裂的可能。C(old-new) 提交后，leader 就会发起 C-new，这时候 leader 只需要满足新配置的条件就可以提交日志。

3. leader 在 C-new 已发起复制时候宕机

对于这种情况，已经复制了 C-new 的节点会只按新配置选举，没有复制 C-new 的节点会按照新老配置选择，然后新 leader 会再次再次提交 C-new，所以宕机也无所谓了。

 

如果此时 leader S3 宕机了，C-new 会不会覆盖呢？不会的，因为处于联合一致状态的节点，也就是说只复制 C(old-new) 但是没有复制 C-new 的节点，必须要在两个新旧集群中获得大多数选票才能选举成功，而 S2S3 不会投票给 S1S4S5 中的一个，因为它日志是领先的，所以只有 S2 才能当选，已提交的 C-new 是不会覆盖的。

集群成员变更还有三个补充规则需要说明一下：

1.  新增节点时，需要新增的节点一定会先完成日志同步，然后再开始集群成员的变更，这个时候新增的节点不对外提供服务，就只是日志复制追上 leader
2.  缩减节点时，leader 本身可能就是要缩减的节点，这时它会在完成 C-new 提交后自动退位
3. 为了避免下线的节点超时选举影响集群运行，服务器会在它确信集群中有 leader 存在时拒绝 requestVoteRPC。因为 C-new 的新 leader 不会再发送心跳给要退出的节点，如果这些节点没有及时下线，那么它们超时后会发起选举，导致集群进入选举阶段，影响集群正常运行。所以一个节点如果在最小超时时间之内，收到了 requestVoteRPC 请求，那么它会拒绝此 RPC。

 

七、日志压缩

raft 的日志在正常操作中不断的增长，但是在实际的系统中，日志不能无限制的增长。随着日志不断增长，他会占用越来越多的空间，花费越来越多的时间来重置。如果没有一定的机制去清除日志里积累的陈旧的信息，那么会带来可用性问题。
快照是最简单的压缩方法。在快照系统中，整个系统的状态都以快照的形式写入到稳定的持久化存储中，然后到那个时间点之前的日志全部丢弃。快照技术被使用在 Chubby 和 ZooKeeper 中，接下来的会介绍 raft 中的快照技术。

 

图中展示了 raft 中快照的基础思想。每个服务器独立的创建快照，只包括已经被提交的日志。主要的工作包括将状态机的状态写入到快照中。raft 也包含一些少量的元数据到快照中: 最后被包含索引指的是被快照取代的最后的条目在日志中的索引值(状态机最后应用的日志)，最后被包含的任期指的是该条目的任期号。保留这些数据是为了支持快照后紧接着的第一个条目的附加日志请求时的一致性检查， 因为这个条目需要前一日志条目的索引值和任期号。为了支持集群成员更新，快照中也将最后的一次配置作为最后一个条目存下来。一旦服务器完成一次快照，他就可以删除最后索引位置之前的所有日志和快照了。