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

type

status

date

slug

summary

1、概述

Paxos 算法是分布式系统领域最重要的一致性算法，同时也是公认的极为艰深难懂的算法。为了解决这个晦涩难懂的问题，Raft 算法应运而生。Raft 算法实现的功能和 Paxos 基本相同，目的是确保多个节点在不可靠的网络环境中达成数据一致，相对 Paxos 算法来说更容易实现和理解。

Raft 算法的优点：

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

高可靠性：Raft 算法保证了 Committed 的日志不会被修改，即使部分节点故障或网络分区，数据仍不会丢失。

高可用性：只要多数节点（N/2+1）存活，系统即可提供服务。所以少量节点故障或网络异常不会影响系统的可用性。即使 Leader 故障，在选举超时到期后，集群自发选举新 Leader，无需人工干预，不可用时间极小。

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

Raft 算法的适用场景：

Leader 选举：通过选举机制在分布式环境的多个节点中选出一个唯一的 Leader 节点，负责处理所有客户端请求，其他节点作为 Follower 被动同步。

分布式系统的日志复制：客户端请求由 Leader 节点接收，并同步到其他节点（Follower），多数节点确认后才会提交（Commit）。所有节点通过Raft协议维护相同的操作日志（例如数据库写入、配置变更等），确保所有副本最终一致。

Raft 算法适用于要求高可用、强一致性的分布式系统，典型应用：

etcd：Kubernetes 的默认存储引擎，用于服务发现和配置管理。

Consul：服务网格和分布式配置存储。

TiKV：TiDB 的底层存储引擎。

Redis：Redis Cluster 模式的故障转移机制基于 Raft 算法，当主节点不可用时，从节点通过选举过程成为新的主节点。

Raft 不适用的场景：

对性能要求极高（低延迟、高吞吐）：Raft需要多数节点确认，写入延迟较高（通常 10ms~100ms 级），不适合高频交易系统（如股票撮合）。

最终一致性即可（AP系统）：如 Cassandra、DynamoDB 等允许短暂不一致的场景，不需要 Raft 的强一致性开销。

单机或非分布式环境：Raft 的复杂性在单节点系统中无意义。

2、Raft算法

Raft 算法分为三种角色：

Leader：处理所有客户端请求，并向 Follower 同步请求日志。

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

Follower：接受并持久化 Leader 同步的日志。注意 Follower 不能接受客户端请求。

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

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

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

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

Raft 把算法流程细化三个子问题：

Leader 选举（Leader election）

日志复制（Log replication）

安全性（Safety）

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

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

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

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

2.2 Leader选举

2.2.1 任期（term）

Raft算法将时间分为一个个的任期（term）。从本轮 Leader 选举开始到下一轮 Leader 选举开始之前的这段时间称为任期（term）。任期是递增的，充当了逻辑时钟的作用。

term 的作用是区分过期的请求：

当一个结点成为 Candidate 并向其他结点请求投票时，会将自己的 term 加 1，表明新一轮的开始以及旧 Leader 的任期结束。

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

选出新的 Leader 之后，其他节点在收到比自己更大的 term 之后就会更新自己的 term 并转成 Follower 状态并重置 election time，如果收到 term 较小的消息说明是过时的消息则拒绝该请求。

2.2.2 超时时间（election timeout）

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

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

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

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

2.2.3 选举过程

触发条件：Follower 在超时时间（选举超时，通常随机 150-300ms）内未收到 Leader 心跳，转为 Candidate，触发新的一轮选举过程。

选举过程：

Follower 将其当前 term 加一，转换为 Candidate，首先投自己一票，然后向其他节点发起投票请求（RequestVote RPC），等待其他节点的回复。

其他 Follower 收到 Candidate 的竞选投票请求，按照以下投票原则投票：

在一个任期 term 内，单个节点最多只能投一票，按照先来先得原则。

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

Candidate 根据来自其他节点的回复，可能出现三种结果：

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

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

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

https://raft.github.io/

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

2.3 日志复制

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

客户端请求：Leader 接收到客户端请求后，将操作追加到本地日志，然后将客户端请求封装到一个个日志（Log Entry），然后向其他 Follow 发起 AppendEntries RPC。

Follower 同步：Follower 节点收到 AppendEntries RPC 后复制这些日志，然后按相同的顺序应用日志。

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

这就是复制状态机（Replicated State Machines）。

2.3.1 日志格式

在 Raft 算法中需要实现分布式一致性的数据被称作日志（Log）， 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 算法中引入了如下两条规则，来确保了日志复制的安全性：

选举规则：只有包含全部已提交日志的节点才能成为 Leader。换句话说，已经 commit 的消息，一定会存在于后续的 Leader 节点上，并且绝对不会在后续操作中被删除。对于并未 commit 的消息，可能会丢失。

提交规则：Leader 只能提交当前 term 的日志，来间接提交之前 term 的日志。

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 并未提交。