分布式一致性算法：Raft算法

type

status

date

slug

summary

1、概述

Paxos 算法是分布式系统领域最重要的一致性算法，同时也是公认的极为艰深难懂的算法。为了解决这个晦涩难懂的问题，Raft 算法应运而生。它的首要设计目的就是易于理解。

Raft 算法实现的功能和 Paxos 基本相同，相对来说更容易实现和理解。和其他分布式一致算法一样，Raft 内部采用如下图所示的复制状态机模型，在这个模型中，会利用多台服务器构成一个集群，工作流程如下图所示：

整个工作流程可以归纳为如下几步：

用户输入设置指令，比如将设置 y 为 1，然后将 y 更改为 9.

集群收到用户指令之后，会将该指令同步到集群中的多台服务器上，这里你可以认为所有的变更操作都会写入到每个服务器的 Log 文件中。

根据 Log 中的指令序列，集群可以计算出每个变量对应的最新状态，比如 y 的值为9.

用户可以通过算法提供的API来获取到最新的变量状态。

Raft 算法具备强一致、高可靠、高可用等优点，具体体现在：

强一致性：虽然所有节点的数据并非实时一致，但 Raft 算法保证 Leader 节点的数据最全，同时所有请求都由 Leader 处理，所以在客户端角度看是强一致性的。

高可靠性：Raft 算法保证了 Committed 的日志不会被修改，State Matchine 只应用 Committed 的日志，所以当客户端收到请求成功即代表数据不再改变。 Committed 日志在大多数节点上冗余存储，少于一半的磁盘故障数据不会丢失。

高可用性：从 Raft 算法原理可以看出，选举和日志同步都只需要大多数的节点正常互联即可，所以少量节点故障或网络异常不会影响系统的可用性。即使 Leader 故障，在选举超时到期后，集群自发选举新 Leader，无需人工干预，不可用时间极小。但 Leader 故障时存在重复数据问题，需要业务去重或幂等性保证。

高性能：与必须将数据写到所有节点才能返回客户端成功的算法相比，Raft 算法只需要大多数节点成功即可，少量节点处理缓慢不会延缓整体系统运行。

2、Raft算法内容

在设计层面，Raft 把算法流程细化三个子问题：

领导选举（Leader election）

日志复制（Log replication）

安全性（Safety）

Raft 算法核心流程可以归纳为：

首先选出 Leader，Leader 节点负责接收外部的数据更新/删除请求。

然后日志复制到其他 Follower 节点，同时通过安全性的准则来保证整个日志复制的一致性。

如果遇到 Leader 故障，Followers 会重新发起选举出新的 Leader。

2.1 Raft算法的角色

Raft 算法分为三种角色：

Leader：主节点，接受客户端请求，并向 Follower 同步请求日志，当日志同步到大多数节点上后告诉 Follower 提交日志。

Follower：从节点，接受并持久化 Leader 同步的日志，在 Leader 告知日志可以提交之后，提交日志。Follower 不能接受客户端请求。

Candidate：候选者，Leader 选举过程中的临时角色。

Raft 要求系统在任意时刻最多只有一个 Leader，正常工作期间只有 Leader 和 Follower。Raft 算法角色状态转换如下：

Follower：

节点默认是 Follower；
如果刚刚开始或和 Leader 通信超时，Follower 会发起选举，变成 Candidate，然后去竞选 Leader；
如果收到其他 Candidate 的竞选投票请求，按照先来先得 & 每个任期只能投票一次的投票原则投票。

Candidate：

Follower 发起选举后就变为 Candidate，会向其他节点拉选票。Candidate 的票会投给自己，所以不会向其他节点投票；
如果获得超过半数的投票，Candidate 变成 Leader，然后马上和其他节点通信，表明自己的 Leader 的地位；
如果选举超时，重新发起选举；
如果遇到更高任期 term 的 Leader 的通信请求，转化为 Follower；如果收到 term 小于等于本身的 Leader 的通信请求，拒绝这次请求，并继续保持 Candidate。

Leader：

成为 Leader 节点后，此时可以接受客户端的数据请求，负责日志同步；
如果遇到更高任期 Term 的 Candidate 的通信请求，这说明 Candidate 正在竞选 Leader，此时之前任期的 Leader 转化为 Follower，且完成投票；
如果遇到更高任期 term 的 Leader 的通信请求，这说明已经选举成功新的 Leader，此时之前任期的 Leader 转化为 Follower。

2.2 Leader选举

2.2.1 term任期

Raft算法将时间分为一个个的任期（term）。以选举（election）开始，选一个 Leader 稳定工作直到开始下一轮选举开始的一段时间称为任期（term）。任期是递增的，这就充当了逻辑时钟的作用。

当一个结点成为 Candidate 并向其他结点请求投票时，会将自己的 term 加 1，表明新一轮的开始以及旧 Leader 的任期结束。所有结点在收到比自己更新的 term 之后就会更新自己的 term 并转成 Follower 状态并重置 election time，而收到过时的消息则拒绝该请求。

在成功选举 Leader 之后，Leader 会在整个 term 内管理整个集群。如果 Leader 选举失败，该 term 就会因为没有 Leader 而结束。

2.2.2 选举过程

选举的触发：

集群中的每个节点都有一个超时时间 election timeout，每个节点的 election timeout 都是 150ms ~ 300ms之间的一个随机数。（随机数的作用是尽量避免新的一次选举出现多个 Candidate 竞争投票的现象。）

Leader 在 term 任期期间向所有 Followers 周期性发送 heartbeat。心跳检测时间很短，要远远小于选举超时时间 election timout。

Follower 节点收到心跳消息后，会返回心跳响应并重置 election timout。

如果 Follower 在 election timeout 时间到了仍没有收到 Leader 的 heartbeat，就会等待一段随机的时间后变为 Candidate 状态，发起一次Leader 选举。

💡

投票者（包括 Candidate 和 Follower）投票的约束如下：

在任一任期 term 内，单个节点最多只能投一票。

Candidate 存储的日志至少要和 Follower 一样新（安全性准则），否则拒绝投票。

first-come-first-served 先来先得。

选举过程如下：

Follower 将其当前 term+1，然后转换为 Candidate。Candidate 的票会投给自己，所以不会向其他节点投票，然后并行给其他节点发送 RequestVote RPCs，等待其他节点的回复。

Follower 收到 Candidate 的竞选投票请求，按照先来先得 & 每个任期只能投票一次的投票原则投票。

Candidate 在等待回复的过程中，根据来自其他节点的消息，可能出现三种结果

收到 majority（超过半数）的投票（含自己的一票），则赢得选举，成为 Leader。赢得了选举之后，新的 Leader 会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举。
遇到更高任期 term 的 Leader 的通信请求，说明已经选出了 Leader，那么自行切换到 Follower
一段时间内没有收到 majority 投票，说明多个 Candidate 竞争投票导致过于分散，或者出现了丢包现象。则保持 Candidate 状态，任期 term+1，重新发出选举。

选出新的 Leader 后，Leader 在任期内会周期性向其他 Follower 节点发送心跳来维持地位。

经典动图可以参考下面链接

https://raft.github.io/

http://thesecretlivesofdata.com/raft/#election

2.3 日志复制

当选举 Leader 成功后，整个集群就可以正常对外提供服务了。

Leader 接收所有客户端请求，Leader 将客户端请求（command）封装到一个个日志（Log entry），然后并行的向其他 Follow 发起 AppendEntries RPC。

Follower 节点复制（replicate）这些 Log entries，然后按相同顺序应用（apply）Log entry 中的 command。

当这条日志被复制到大多数服务器上，Leader 将这条日志应用到它的状态机并向客户端返回执行结果。

这就是复制状态机（Replicated state machines）

2.3.1 日志格式

在 Raft 算法中需要实现分布式一致性的数据被称作日志， Raft 算法中的数据提交记录，会按照时间顺序进行追加，Raft 也是严格按照时间顺序并已一定的格式写入日志文件中。每个服务器上（包括 Leader和 Follower）都有一个日志文件，日志格式如下图所示，

日志文件由多个日志条目（Log Entry）组成。每个日志条目包含以下内容

command：由客户端请求发送的执行指令，有点绕口，我觉得理解成客户端需要存储的日志数据即可。

index：日志条目在日志中的位置，需要注意索引值是一个连续并且单调递增的整数。

term：创建这条日志条目的领导者的任期编号。

2.3.2 日志复制的流程

日志的复制的过程有点类似两阶段提交(2PC)

Leader 把客户端请求作为 Log Entry 追加到日志文件，然后并行地向其他 Follower 发起 AppendEntries RPC，把新增的 Log Entry 发送给其他 Follower。

Follower 接收到 Log Entry 后会检查内容。

检查 term，如果请求的 term 比自己小，说明是来自旧 Leader 的数据，该数据已经过期，直接拒绝请求，回复 error。
对比先前日志的 index 和 term，如果一致，则就可以从此处更新日志，把所有的日志写入自己的日志列表中，回复 ok；否则拒绝请求，回复 error。

Leader 等待 Follower 响应：

如果大多数节点（n/2 + 1）回复 ok，将 Log Entry 应用到状态机上，然后把写入成功的消息响应给客户端，同时通知其他 Follower 应用日志。
如果没收到大多数节点回复ok，说明这个 Log Entry 可能太新了，大部分节点的同步还没有跟上，Leader 会使用更前面一条的 Log Entry 向其他 Follower 发起 AppendEntries RPC。Leader 会重复上面步骤无限重试，直到找到一个可以被大多数节点接受的 Log Entry，此时 Follower 从这个索引值开始复制，最终和 Leader 节点日志保持一致。

在复制的过程中，Raft 会保证如下几点：

Leader 绝不会覆盖或删除自己的日志，只会追加（Leader Append-Only），成为 Leader 的节点里的日志一定拥有所有已被多数节点拥有的日志条目，所以先前的日志条目很可能已经被提交，因此不可以删除之前的日志。

如果两个日志的 index 和 term 相同，那么这两个日志相同（Log Matching），第二点主要是因为一个任期内只可能出现一个 Leader，而 Leader 只会为一个 index 创建一个日志条目，而且一旦写入就不会修改，因此保证了日志的唯一性。

如果两个日志相同，那么他们之前的日志均相同，因为在写入日志时会检查前一个日志是否一致，从而递归的保证了前面的所有日志都一致。从而也保证了当一个日志被提交之后，所有结点在该 index 上提交的内容是一样的（State Machine Safety）。

2.4 安全性（核心）

Raft 算法中引入了如下两条规则，来确保了日志复制的安全性：

已经 commit 的消息，一定会存在于后续的 Leader 节点上，并且绝对不会在后续操作中被删除。

对于并未 commit 的消息，可能会丢失。

2.4.1 多数投票规则

在上面投票环节也有介绍过，一个 Candidate 必须获得集群中的多数投票，才能被选为 Leader；而对于每条 commit 过的消息，它必须是被复制到了集群中的多数节点，也就是说成为 Leader 的节点，至少有 1 个包含了 commit 消息的节点给它投了票。

而在投票的过程中每个节点都会与 Candidate 比较日志的最后 index 以及相应的term，如果要成为 Leader，必须有更大的 index 或者更新的 term，所以 Leader 上肯定有 commit 过的消息。

2.4.2 提交规则

上面说到，只要日志在多数结点上存在，那么 Leader 就可以提交该操作。但是 Raft 额外限制了 Leader 只对自己任期内的日志条目适用该规则，先前任期的条目只能由当前任期的提交而间接被提交。 也就是说，当前任期的 Leader，不会去负责之前 term 的日志提交，之前 term 的日志提交，只会随着当前 term 的日志提交而间接提交。

这样理解起来还是比较抽象，下面举一个例子，该集群中有S1到S5共5个节点，

初始状态如 (a) 所示，之后 S1 下线；

(b) 中 S5 从 S3 和 S4 处获得了投票成为了 Leader 并收到了一条来自客户端的消息，之后 S5 下线。

(c) 中 S1 恢复并成为了 Leader，并且将日志复制给了多数结点，之后进行了一个致命操作，将 index 为 2 的日志提交了，然后 S1 下线。

(d) 中 S5 恢复，并从 S2、S3、S4 处获得了足够投票，然后将已提交的 index 为 2 的日志覆盖了。

这个例子中，在c状态，由于Leader直接根据日志在多数节点存在的这个规则，将之前term的日志提交了，当该Term下线后，后续的Leader S5上线，就将之前已经commit的日志清空了，导致commit过的日志丢失了。

为了避免这种已提交的日志丢失，Raft只允许提交自己任期内的日志，也就是不会允许c中这种操作。（c）中可能出现的情况有如下两类：

（c）中S1有新的客户端消息4，然后S1作为Leader将4同步到S1、S2、S3节点，并成功提交后下线。此时在新一轮的Leader选举中，S5不可能成为新的Leader，保证了commit的消息2和4不会被覆盖。

（c）中S1有新的消息，但是在S1将数据同步到其他节点并且commit之前下线，也就是说2和4都没commit成功，这种情况下如果S5成为了新Leader，则会出现（d）中的这种情况，2和4会被覆盖，这也是符合Raft规则的，因为2和4并未提交。

3、Raft扩展

3.1 日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft 采用对整个系统进行 snapshot 来解决，snapshot 之前的日志都可以丢弃。

每个副本独立的对自己的系统状态进行 snapshot，并且只能对已经提交的日志记录进行 snapshot。

Snapshot 中包含以下内容：

日志元数据。最后一条已提交的 log entry 的 log index和term。这两个值在 snapshot 之后的第一条 log entry 的 AppendEntries RPC 的完整性检查的时候会被用上。

系统当前状态。上面的例子中，x为0，y为9.

当 Leader 要发给某个日志落后太多的 Follower 的 log entry 被丢弃，Leader会将 snapshot 发给Follower。或者当新加进一台机器时，也会发送 snapshot 给它。

做 snapshot 既不要做的太频繁，否则消耗磁盘带宽，也不要做的太不频繁，否则一旦节点重启需要回放大量日志，影响可用性。推荐当日志达到某个固定的大小做一次 snapshot。

3.2 集群成员变更

很多时候，集群需要对节点进行维护，这样就会涉及到节点的添加和删除。为了在不停机的情况下，动态更改集群成员，Raft提供了下面两种动态更改集群成员的方式：

单节点成员变更：One Server ConfChange

多节点联合共识：Joint Consensus

3.2.1 动态成员变更存在的问题

在Raft中有一个很重要的安全性保证就是只有一个 Leader，如果我们在不加任何限制的情况下，动态的向集群中添加成员，那么就可能导致同一个任期下存在多个 Leader 的情况，这是非常危险的。

如下图所示，从 Cold 迁移到 Cnew 的过程中，因为各个节点收到最新配置的实际不一样，那么肯能导致在同一任期下多个 Leader 同时存在。

比如图中此时 Server3 宕机了，然后 Server1 和 Server5 同时超时发起选举：

Server1：此时 Server1 中的配置还是 Cold，只需要 Server1 和 Server2 就能够组成集群的 Majority，因此可以被选举为 Leader

Server5：已经收到 Cnew 的配置，使用 Cnew 的配置，此时只需要 Server3，Server4，Server5 就可以组成集群的 Majority，因为可以被选举为 Leader

也就是说，以 Cold 和 Cnew 作为配置的节点在同一任期下可以分别选出Leader。

基于此，Raft提供了两种集群变更的方式来解决上面可能出现的问题。

3.2.2 单节点成员变更

单节点成员变更，就是保证每次只往集群中添加或者移除一个节点，这种方式可以很好的避免在变更过程中多个 Leader 的问题。

下面我们可以枚举一下所有情况，原有集群奇偶数节点情况下，分别添加和删除一个节点。在下图中可以看出，如果每次只增加和删除一个节点，那么 Cold 的 Majority 和 Cnew 的 Majority 之间一定存在交集，也就说是在同一个 Term 中，Cold 和 Cnew 中交集的那一个节点只会进行一次投票，要么投票给 Cold，要么投票给 Cnew，这样就避免了同一 Term 下出现两个 Leader。

变更的流程如下：

向 Leader 提交一个成员变更请求，请求的内容为服务节点的是添加还是移除，以及服务节点的地址信息

Leader 在收到请求以后，回向日志中追加一条 ConfChange 的日志，其中包含了 Cnew，后续这些日志会随着 AppendEntries RPC 同步所有的 Follower 节点中

当 ConfChange 的日志被添加到日志中是立即生效（注意：不是等到提交以后才生效）

当 ConfChange 的日志被复制到 Cnew 的 Majority 服务器上时，那么就可以对日志进行提交了

以上就是整个单节点的变更流程，在日志被提交以后，那么就可以：

马上响应客户端，变更已经完成

如果变更过程中移除了服务器，那么服务器可以关机了

可以开始下一轮的成员变更了，注意在上一次变更没有结束之前，是不允许开始下一次变更的。

结合下面的图，我们可以走一遍整个集群的变更过程，在多点联合共识的规则之下，每一个任期之中不会出现两个Leader。

Cold,new 的大多数：是指 Cold 中的大多数和 Cnew 中的大多数。

Cold,new：这个配置是指 Cold 和 Cnew 的联合配置，其值为 Cold 和 Cnew 的配置的交集，比如 Cold为[A, B, C]， Cnew 为 [B, C, D]，那么 Cold,new 就为 [A, B, C, D]

这里有几个概念比较拗口，这里解释一下：

一旦 Cnew 的日志复制到大多数节点上时，那么 Cnew 的日志就可以提交了，在 Cnew 日志提交以后，就可以开始下一轮的成员变更了。

在将 Cold,new 日志复制到大多数节点上时，那么Cold,new 的日志就可以提交了，在 Cold,new 的 ConfChange 日志被提交以后，马上创建一个 Cnew 的 ConfChange 的日志，并将该日志通过 AppendEntries 请求复制到 Follower 中，收到该 ConfChange 的节点马上应用该配置作为当前节点的配置。

Leader 收到 Cnew 的成员变更请求，然后生成一个 Cold,new 的 ConfChang 日志，马上应用该日志，然后将日志通过AppendEntries请求复制到Follower中，收到该ConfChange的节点马上应用该配置作为当前节点的配置。

主要步骤分为下面三步：

对于同时变更多个节点的情况， Raft 提供了多节点的联合共识算法，这里采用了两阶段提交的思想。

3.2.3 多节点联合共识

Cold,new 日志在提交之前，在这个阶段，Cold,new中的所有节点有可能处于 Cold 的配置下，也有可能处于 Cold,new 的配置下，如果这个时候原 Leader 宕机了，无论是发起新一轮投票的节点当前的配置是 Cold 还是 Cold,new，都需要 Cold 的节点同意投票，所以不会出现两个 Leader。也就是 old 节点不可能同时 follow 两个 Leader。

Cold,new 提交之后，Cnew 下发之前，此时所有 Cold,new 的配置已经在 Cold 和 Cnew 的大多数节点上，如果集群中的节点超时，那么肯定只有有 Cold,new 配置的节点才能成为 Leader，所以不会出现两个 Leader。

Cnew下发以后，Cnew提交之前，此时集群中的节点可能有三种，Cold的节点（可能一直没有收到请求）， Cold,new的节点，Cnew 的节点，其中 Cold 的节点因为没有最新的日志的，集群中的大多数节点是不会给他投票的，剩下的持有 Cnew 和 Cold,new 的节点，无论是谁发起选举，都需要 Cnew 同意，那么也是不会出现两个 Leader。

Cnew 提交之后，这个时候集群处于 Cnew 配置下运行，只有 Cnew 的节点才可以成为 Leader，这个时候就可以开始下一轮的成员变更了。

参考

https://juejin.cn/post/7218915344130359351