1 多数派原则

多数派原则是指:在分布式系统中多个节点做出决策或达成共识时,必须获得超过半数参与节点的同意。

多数派原则可以带给我们一个重要的推论:即两个多数派集合必然存在交集。这将是后续证明 Raft 许多特性时的重要依据。

而奉行多数派原则的集群节点数量一般是奇数个,主要的原因在于,奇数个节点的容错率更高

对于相同的容错能力(能够容忍 x 个节点故障),使用奇数节点 2x+1 比使用偶数个节点 2x+2 更节省资源。

比如,在 5 个节点存在的集群中,多数派要求至少 3 个节点做出决策,最多可以容忍 2 个节点开小差,而存在 6 个节点的集群中,多数派要求至少 4 个节点才能做出决策,最多也是可以容忍 2 个节点开小差。

既然都最多可以容忍 2 个节点开小差,显然奇数个节点占用的资源要少一些。

在 Raft 算法中,不管是数据同步还是领导人选举,只需要达到多数派的认可,就可以即时采纳结果,同时拒绝或者尚未响应的少数派在随后感知到该决断已经被集群多数派认同后,最终也会执行采纳。

多数派原则是 Raft 算法提高可用性的关键,对于分布式系统而言,做出决策时如果要求所有节点共同响应以实现一致性的保证是过于苛刻的,因为我们无法保证所有节点都能健康运作,但是倘若退而求其次,只要多数派达成共识即可正常决断和响应,这样下限就提高很多了。

2 如何理解复制状态机

一致性算法是在“复制状态机(ReplicatedStateMachine,RSM)”的背景下提出的。

理解复制状态机的核心在于三个部分:状态机、复制以及复制状态机如何工作。

2.1 什么是状态机

我们想象一个抽象的计算模型(状态机)

  • 它有一个内部状态(State),表示状态机在某一时刻的内部数据(比如数据库的内容、变量的值);
  • 同时它接收外部的输入,即命令,要求状态机执行某些操作(比如,“将账户 A 的余额增加 100 元”,“设置变量 x 为 5”);
  • 此外,状态机还存在一个确定性的函数,即状态转移函数,该函数接收当前的状态和命令作为输入,输出新的状态(和可选的输出结果)。

状态机的关键特性在于:确定性,如果给定相同的初始状态和相同的命令序列,那么状态机总是会经历相同的状态序列,并产生相同的输出序列,同时得到一个暂时的终态

2.2 如何理解复制

所谓复制,也就是不只存在一个状态机,而是在多个独立的副本上都运行着完全相同的状态机实例。

2.3 状态机如何工作

接着,复制状态机是如何工作的,或者说复制状态机是如何解决“分布式一致性”问题的。

核心思想在于:在多个节点上维护相同状态机的多个副本,所有的副本都从相同的初始状态开始,然后按相同的顺序执行相同的命令序列。

这样,由于复制状态机的确定性 + 相同的初始状态 + 相同的命令序列,那么所有的节点就都能得到相同的输出序列,从而得到一个暂时的数据终态,这样客户端无论连接到哪个正常的副本,都能得到一致的响应。

2.4 其中的核心挑战

确保多个节点上命令序列的顺序一致性,是复制状态机实现的核心挑战。

分布式环境中,节点故障、网络延迟或分区都可能导致命令丢失或乱序到达。

因此,需要一个可靠的共识机制,使所有正常节点能够就一个全局一致的命令序列及其执行顺序达成共识。这正是共识算法所要解决的核心问题。一旦达成这种顺序共识,复制状态机的特性即可保证所有节点以相同的顺序执行命令,从而实现各节点状态的一致性。

3 Raft 特性

下面是 Raft 在任何时候都能够保证的一些特性,后面逐一说明为什么。

特性 解释
选举安全特性 对于一个给定的任期号,最多只会有一个领导人被选举出来
领导人只附加原则 领导人绝对不会删除或者覆盖自己的日志,只会增加
日志匹配原则 如果两个日志在某一相同索引位置日志条目的任期号相同,那么我们就认为这两个日志从头到该索引位置之间的内容完全一致
领导人完全特性 如果某个日志条目在某个任期号中已经被提交,那么这个条目必然出现在更大任期号的所有领导人中
状态机安全特性 如果某一服务器已将给定索引位置的日志条目应用至其状态机中,则其他任何服务器在该索引位置不会应用不同的日志条目

3.1 选举安全特性

选举安全性证明依赖于 Raft 的三个核心设计。

1)任期单调递增

每个节点会维护一个持久化的当前任期值 currentTerm,当节点发现更高的任期时,必须将自己的 currentTerm 更新为该值并转换为跟随者状态,并且任期值只能增加,这是 Raft 规定的。

2)每任期单票制

每个节点在给定的任期内最多只能投一次票,节点持久化存储 votedFor 字段记录当前任期投给的候选人 ID,这也是 Raft 规定的。

3)多数派原则

在选举时,候选人必须获得多数派的认可。

下面基于反证法进行证明,假设同一个任期内存在两个领导人,即存在两个节点 N1 和 N2 在同一任期 T 都成功当选领导人,集群节点数 N,多数派节点数 Q。

  • N1 当选,则 N1 获得 V1 的选票数,且 V1 ≥ Q,V1 ≤ N
  • N2 当选,则 N2 获得 V2 的选票数,且 V2 ≥ Q,V1 ≤ N
  • 而两个多数派集合必然存在交集,所以一定存在至少一个节点同时投给了 L1 和 L2,这和上述第二点“每任期单制”矛盾。

3.2 领导人只附加原则

这是 Raft 算法的一个设定。

3.3 日志匹配原则

日志匹配原则其实是阐述了两点:

  • 如果在不同的日志中的两个条目拥有相同的索引和任期号,那么他们存储了相同的指令。
  • 如果在不同的日志中的两个条目拥有相同的索引和任期号,那么他们之前的所有日志条目也全部相同。

解释:

1)在 Raft 中,一个任期内最多存在一个有效(排除集群脑裂的情况)的领导人,而由于 Raft 中领导人只附加原则,所以对于同一个任期内的相同索引的日志条目,他们的指令内容一定相同。

2)第二点特性由 AppendEntries RPCs 中的一致性检查保证。

当领导人向跟随者发送 AppendEntries RPC 时,不仅会包含新的日志条目(如果有),还会包含两个关键参数:

  • prevLogIndex:紧接在新条目之前的那条日志的索引。
  • prevLogTerm:紧接在新条目之前的那条日志的任期。

跟随者收到 RPC 后,会检查自己的日志在位置 prevLogIndex 处是否存在一个日志条目,并且该条目的任期号是否等于 prevLogTerm,只有当检查成功,它才会接受领导人发来的新日志条目(如果有),并将其追加到自己的日志之后。这确保了跟随者在追加新条目之前,其日志直到 prevLogIndex 的部分都与领导人一致。

如果一致性检查失败,跟随者就会拒绝该 RPC,此时领导人必须要找到两者(指领导人和拒绝该 RPC 的跟随者)最后达成一致的地方,然后删除跟随者从那个点之后的所有日志条目,并发送自己在那个点之后的日志给跟随者。

在实现层面,领导人针对每一个跟随者维护了一个 nextIndex,表示下一个需要发送给某个跟随者的日志条目的索引地址。当一个领导人刚上任的时候,初始化所有的 nextIndex 值为自己的最后一条日志的 index 加 1。当一致性检查失败,跟随者拒绝 AppendEntries RPC,领导人就会减小 nextIndex 值并进行重试。

最终 nextIndex 会在某个位置使得领导人和跟随者的日志达成一致。当这种情况发生,AppendEntries RPC 就会成功,这时就会把跟随者冲突的日志条目全部删除并且加上领导人的日志,这样一来,跟随者的日志就会和领导人保持一致,并且在接下来的任期里一直继续保持。

3.4 领导人完整特性

要想证明领导人完整特性,还需要理解一个点:“选举限制”

3.4.1 选举限制

一个跟随者在收到一个候选人的 RequestVote RPC 时,只有当下面两个条件都满足时,才会投票给这个候选人:

  • 规则 1:这个跟随者在当前任期内尚未投票给其他候选人。
  • 规则 2:这个候选人的日志至少和该跟随者的日志一样新。

日志“新”的比较:任期号大的更“新”,任期号相同则日志索引更大的更“新”。

3.4.2 证明领导人完整特性

假设领导人完整特性是不存在的。

在任期 T 的领导人(领导人 T)在任期内提交了一条新的日志条目 E,但是这条日志条目没有被存储到未来某个任期的领导人的日志中,假设大于 T 的最小任期 U 的领导人(领导人 U)没有这条日志条目 E。

1)由于日志条目 E 被提交,这意味者 E 已经被多数派节点所复制。

2)由于领导人 U 在任期 U 当选,这意味着它必须获得多数派的认可。

3)两个多数派集合必然存在交集,所以至少有一个节点(假设为 N,日志条目 E 的索引为 I)包含日志条目 E,同时在任期 U 将选票投给了领导人 U。

4)而由于选举的限制,如果 N 将选票投给了领导人 U,那么 U 的日志一定会比 N 更“新”,那么可能满足选举限制的情况如下:

  • 首先,如果投票者和领导人 U 的最后一条日志的任期号相同,那么领导人 U 的日志至少和投票者一样长(否则就不符合选举限制了),由于 Raft 的日志匹配原则(参考第一点阐述),相同的任期号+索引处的日志条目必然相同,推出领导人 U 在索引 I 处的日志条目也必须为 E,这和假设矛盾。
  • 既然任期相同的情况被排除了,并且 N 确实投了票,那么唯一的可能性就是 lastTerm_U > lastTerm_N,而根据我们的假设:领导人 U 是大于 T 的第一个不包含日志条目 E 的领导人,所以创建了领导人 U 最后一条日志的之前的领导人一定已经包含了日志条目 E,再根据日志匹配原则(参考第二点阐述),领导人 U 一定也包含日志条目 E,这和假设矛盾。

4 提交限制

在 Raft 中,日志提交意味着该日志条目已经不可逆转,最终会被所有节点应用到状态机。

但 Raft 强调,一个日志条目的提交只有在 它所在任期的领导人日志 被复制到大多数节点之后,才能认为“提交”,而不能仅仅因为它已经在“物理上”被复制到了大多数机器上,就认为它提交了,这可能会导致不一致。

一个例子:

image-20250815213311816

1)在 (a) 中,S1 是领导人,部分跟随者复制了索引位置 2 的日志条目。

2)在 (b) 中,S1 崩溃了,然后 S5 在任期 3 通过 S3、S4 和自己的选票赢得选举,然后从客户端接收了一条不一样的日志条目放在了索引 2 处。

3)然后到 (c) 中,S5 又崩溃了,S1 重新启动并且选举成功(term 4),它把自己之前(term 2)的日志继续往下复制,此时索引 2 处的日志已经被多数派认可,但是注意,此时仍然不会提交日志。

不能提交的原因在于:如果 S1 产生了新的日志条目,但是在被多数派接收之前,或者说 S1 根本没有产生新的日志条目就又崩溃了,此时 S5 可以再次当选领导人,并且将索引 3 处的日志覆盖到多数派节点,这样索引 2 处 term 2 的日志就彻底丢失了,所以,如果索引 2 term 2 的日志被多数派认可就提交,就会出现不一致问题。

4)但是如果 S1 在 term 4 产生了新的日志,并且被多数派认可,那么一旦这条日志被提交,之前的所有日志(比如索引 2 term 2)的也就一并提交了,就如 (e) 中那样。

为什么此时可以提交索引 2 term 2 的日志,因为此时如果 S5 还想竞选领导人时,会被选举限制所拒绝,S5 不可能当选领导人,那么索引 2 term 3 的日志就会再将来的某个时刻被删除,也就没有不一致的问题了。

5 集群配置切换

Raft 集群配置切换(也称为成员变更)是将集群从旧配置(C-old)迁移到新配置(C-new)的过程。

Raft 通过一种特殊的机制来保证在配置变更期间的安全性:即防止在配置变更的过程中出现脑裂。

在 Raft 中,集群先切换到一个过渡的配置,称为 joint consensus(联合一致/共同一致),一旦联合一致被提交,那么系统就切换到新的配置上。

这个联合配置是 C-old 与 C-new 的结合,需要遵循以下原则

  • 日志条目被复制给集群中 C-old,new 的所有服务器。
  • C-old,new 的所有服务器都可以成为领导人。
  • 达成一致(针对选举和提交)需要分别在两种配置上获得多数派的认可。

整个过程如下:

1)领导人接收配置变更请求:

  • 客户端(或管理员)向当前领导人发送一个配置变更请求,其中包含新的集群配置(C-new),通常是一个节点列表(可能添加、移除节点或修改节点角色/地址)。

2)提交联合配置日志条目(C-old,new):

  • 领导人将包含联合配置 C-old,new 的日志条目复制到 C-old 中的所有节点,并在获得 C-old 中的多数派认可之后,提交该联合配置日志条目(遵循旧配置的多数派规则)。
  • 一旦这个 C-old,new 日志条目被提交(意味着它已经被 C-old 中的多数派认可),联合配置正式生效。领导人现在知道集群已经安全地进入了联合一致状态。
  • 可用性:在联合一致状态下,集群仍然可以处理客户端请求。领导人继续接收客户端请求,生成普通的日志条目,并按照联合共识的规则(需要 C-old 和 C-new 的双重大多数)来复制和提交这些日志条目。

3)提交新配置日志条目(C-new):

  • 在联合配置 C-old,new 提交之后,领导人创建一个新的配置日志条目,这次只包含最终的新配置 C-new。
  • 领导人将这个 C-new 日志条目复制给 C-new 配置中的节点(遵循新配置的多数派规则)。
  • 一旦这个 C-new 条目被提交(意味着它已经被 C-new 中的多数派认可),联合一致状态结束,集群正式切换到新配置 C-new,后续所有决策只需要 C-new 中的多数派认可即可。

4)清理旧配置:

  • 领导人在提交 C-new 后,可以安全地通知不在 C-new 中的节点关闭。

一个可能的配置切换过程如下:

配置切换流程图

5.1 如何保证安全性

联合一致的核心在于确保配置变更期间(C-old,new 提交后到 C-new 提交前),不可能出现两个领导人。

原因是,在配置变更期间要赢得选举,候选人必须获得 C-old 的多数派认可和 C-new 的多数派认可。

显而易见的是,由于每个节点在同一次选举期间最多投一次票的限制,所以存在至少两个候选人同时获得 C-old 的多数派认可和 C-new 的多数派认可,是不可能的。

5.2 新节点的追赶

新加入的 C-new 的节点可能初始化没有存储任何日志条目,所有领导人需要将缺失的日志条目复制给它们,直到它们追上进度。

在这期间,这些新节点将没有投票权,领导人只会复制日志给他们,但是不会将它们视为多数派中的节点。所以,在这些新节点追赶进度之前,集群的可用性可能会受到影响,因为新节点暂时无法帮助形成 C-new 的多数派。

5.3 老节点的扰乱

移出的节点可能会因为选举超时从而发起新的选举,这些节点会发送更高 term 的请求投票 RPC,导致当前领导人被迫退位,一个新的领导最终会被选举出来,但是被移除的节点将会再次超时,然后这个过程会再次重复,导致整体可用性大幅降低。

解决的方式就是当节点在当前最小选举超时时间内收到一个请求投票 RPC,它不会做出动作(更新 term 或者投出选票),这并不会影响正常的选举,因为每个节点在开始一次选举之前,至少都要等待一个最小选举超时时间。

6 客户端交互的一些问题

6.1 不丢失、不重复写

不丢失:当客户端启动的时候,他会随机挑选一个服务器进行通信。如果客户端第一次挑选的服务器不是领导人,那么那个服务器会拒绝客户端的请求并且提供他最近接收到的领导人的信息(附加条目请求包含了领导人的网络地址)。如果领导人已经崩溃了,那么客户端的请求就会超时;客户端之后会再次重试随机挑选服务器的过程。

不重复:Raft 是可能执行同一条命令多次的:例如,如果领导人在提交了这条日志之后,但是在响应客户端之前崩溃了,那么客户端会和新的领导人重试这条指令,导致这条命令就被再次执行了。解决方案就是客户端对于每一条指令都赋予一个唯一的序列号。然后,状态机跟踪每条指令最新的序列号和相应的响应。如果接收到一条指令,它的序列号已经被执行了,那么就立即返回结果,而不是重新执行指令。

6.2 线性化读

Raft 如何处理线性化的只读操作而无需将这些操作写入日志。

在不增加任何限制的情况下,这么做(只读操作不写日志)可能会冒着返回脏数据的风险,因为响应客户端请求的领导人可能在他不知道的时候已经被新的领导人取代了,线性化的读操作必须不能返回脏数据。

Raft 设计了两个机制来实现。

1)确保领导人知晓最新提交信息

领导人需要确切的知道哪些日志条目已经被集群多数派接受并持久化(即已提交),因为已提交的日志最终会应用到状态机,代表最新的、持久化的状态,是可以被线性读获取的结果。

Raft 的选举限制保证了新选举出的领导人一定包含所有之前任期已提交的日志条目,但是一个新领导人刚上任时,它确实拥有所有已提交的日志(因为选举限制),但它不知道在自己任期之前提交的日志中,哪些是已提交的,哪些只是被复制到多数派但未提交的。Raft 提交规则规定,领导人只能通过提交自己任期的日志条目来间接提交之前任期的日志(参考第 4 节)。

所以,当新领导人上任后,立即向自己的日志追加一个空白条目(no-op entry),一旦这个空白条目被复制到多数派节点,根据 Raft 的提交规则,这个空白条目就被提交了。提交这个空白条目有一个非常重要的副作用:它使得所有在该空白条目之前的日志条目(包括之前任期的)都被间接提交了(因为 Raft 的提交规则保证,如果一个条目被提交,那么它之前的所有条目也都被提交)。

此时,领导人状态机中的数据就反映了所有已提交日志应用后的最新状态。

2)确认领导人身份未被废黜

即使第一点保证了领导人知道最新的提交点,但在它处理只读请求的瞬间,它可能已经不再是领导人了(比如在它响应请求前的短暂时间内,发生了新的选举)。

如果领导人 L1 在处理只读请求时已经被 L2 取代(但 L1 还不知道),它用自己状态机的数据响应请求。然而,L2 可能已经提交了更新的日志并更新了状态机。L1 返回的数据就是过时的脏数据。

解决方案就是:“先和集群中的大多数节点交换一次心跳信息”。

在处理每个只读请求之前,领导人必须向集群中的多数派节点发送一次心跳消息(即 AppendEntries RPC,通常不包含日志条目,只作为心跳),只有当领导人收到了来自多数派节点的成功响应后,它才能基于自己的本地状态机处理该只读请求并返回结果。

心跳成功响应表明:在心跳发出并收到多数响应的这个时间窗口内,没有其他节点获得了多数派的支持成为新的领导人,所以可以保证它的状态机的数据是最新的。

为什么写操作不需要这些额外的措施?其实写操作天然通过日志复制过程实现了这些保证。而读操作因为没有写日志,所以需要额外补上这些验证步骤。

但是这样做(只读前先和集群中的大多数节点交换一次心跳信息保证自己的领导人地位)毕竟还是有心跳的开销,所以在 Raft 中提到一个优化机制:租约机制。

租约机制的原理在于:领导人假设,只要它在自己的租约期内(比如上一次**成功心跳后(即多数派都响应了心跳)**的一个固定时间段内),集群中的多数派节点仍然会认可它的领导地位。这样就可以避免为每个只读请求都等待一次心跳往返延迟,只需要检查本地时钟是否在租约期内即可,性能更高。

那么如何确定租约有效期的长度?一个可能的有效期公式是:start + election timeout - clock drift bound。

Raft 要求,一个跟随者只有在超过 election_timeout 时间没有收到来自领导人的心跳(或任何有效的 Raft 消息,如 AppendEntries)时,才会发起选举,这意味着在 start 时刻,这些跟随者刚刚重置了它们的选举计时器,所以这些跟随者在接下来 election timeout 的时间内不会因为超时而重新发起选举。

而考虑到物理时钟存在漂移(Drift),所以公式中减去了 clock drift bound,这是一个安全边界值,它表示在系统的任意两个节点之间的时钟计时的最大误差。