Raft 一致性算法

1. 简介

在本教程中，我们将讨论 Raft 一致性算法的工作原理，并探讨其为分布式系统带来的关键优势。

在分布式系统中，保持多个服务器同步是一个主要挑战。如果一个节点发生故障，系统应该继续运行而不会出现不一致的情况。

2. 共识在现代计算中的重要性

设想一个分布式数据库处理数百万用户帐户。当某人尝试注册一个新用户名，例如“Alice123”时，系统中的每台服务器都必须立即知道该名称是否可用。

如果没有可靠的共识机制，就会陷入混乱；一台服务器可能接受注册，而另一台服务器仍然显示该名称可用。这种不一致性会产生严重的问题，从重复帐户到可能导致整个应用程序崩溃的数据损坏。

共识算法是保持 分布式系统同步的基础。它们充当一个组织框架，协调多个服务器作为一个单一、连贯的单元进行工作。

这些算法不仅可以防止冲突，还能使系统在组件发生故障或网络连接变得不可靠时保持准确性。

3. 共识的三大支柱

现代共识算法提供三个基本保证，以确保分布式系统平稳运行

首先，它们确保所有节点达成一致。每个服务器都会对系统的状态得出相同的结论，无论是在确定用户名是否已被占用还是在处理金融交易。 这消除了对客户端请求产生冲突响应的风险。

其次，它们提供容错能力。当服务器崩溃或网络分区时，系统将继续运行而不会出现故障。 其余健康的节点会自动补偿失败的组件，从而保持服务可用性。 这种弹性将单服务器系统中可能导致灾难性的故障转化为轻微且可恢复的事件。

最后，它们保证一致性。客户端始终与系统的最新版本状态进行交互。 无论用户从东京的手机还是纽约的笔记本电脑查看他们的帐户余额，他们都将看到相同且准确的信息。这种一致性建立对应用程序的信任，并防止让用户远离令人沮丧的差异。

4. Raft 是如何工作的？

Raft 的操作围绕两个基本过程展开，这两个过程协同工作以维护分布式系统的一致性。领导者选举和日志复制。在领导者选举过程中，系统会选择一个节点作为领导者。 一旦节点选出领导者，协议就会进入日志复制阶段，领导者会将新的日志条目发送到跟随者节点。

4.1. 领导者选举

Raft 将操作组织成按单调递增的整数标记的顺序词条，作为逻辑时钟，用于维护事件顺序并防止领导权冲突。

节点在三种角色之间转换： 跟随者（被动等待心跳）、候选者（在超时后发起选举）和领导者（管理集群操作）。当跟随者的随机 150-300ms 选举超时到期且未收到心跳时，它会通过递增其词条、对自己投票并征求同行投票来成为候选者。

通过严格的投票规则来执行选举安全，这些规则要求多数批准和日志最新性验证（比较最后一个条目的词条和日志长度），它们共同保证单领导者选举，同时优先考虑最新的候选者

为了处理分裂票数，Raft 采用随机超时，从而自然地错开后续选举尝试。实际部署应使用奇数大小的集群（3、5 或 7 个节点），并将选举超时配置为网络广播延迟的至少 10 倍。

4.2. 日志复制

Raft 的日志复制遵循严格的领导者协调过程，以确保整个集群的一致性。当领导者收到客户端请求时，它会验证并分配一个唯一的 ID，然后将命令作为未提交状态附加到其日志中。

领导者随后广播 AppendEntries RPC，其中包含其当前任期、先前的日志位置（用于连续性验证）、新条目和提交索引。Follower 在持久化条目之前执行三个关键检查：任期验证、日志连续性确认和稳定存储验证。

提交需要多数复制和顺序处理——条目仅在所有先前的条目都安全后才会提交。领导者通过特定于 Follower 的索引（nextIndex/matchIndex）监控进度，在获得法定人数确认后推进 commitIndex，然后再将更改应用于状态机并响应客户端。这种分阶段的方法保证了线性可扩展性，同时保持可用性。

Raft 的一致性机制强制执行两个关键的不变量：日志匹配属性确保具有相同（索引，任期）条目的条目共享相同的历史记录，而状态机安全通过领导者完整性要求和无重写策略，通过故障来保护已提交的条目。

4.3. 实际示例

为了更好地理解 Raft 共识算法的运作方式，让我们考虑一个由五个服务器组成的分布式系统：A、B、C、D 和 E。

最初，所有服务器都从 Follower 状态开始。如果 Follower 在指定超时时间内没有收到指示活跃领导者的心跳消息，它将转换为候选人状态，并通过递增其任期和向其他服务器请求投票来发起选举。

例如，如果服务器 C 的超时时间首先到期，它将向 A、B、D 和 E 请求投票。如果 C 收到多数投票，它将成为当前任期的领导者。然后，领导者开始向 Follower 发送周期性的心跳消息，以维持其领导地位并防止新的选举。

一旦选出领导者，客户端请求（例如“添加事务 X”）将直接发送到领导者。领导者将请求作为新的日志条目附加到其日志中，然后将 AppendEntries 远程过程调用 (RPC) 发送到所有 Follower。例如，如果客户端将命令发送到服务器 C，现在是领导者，它会将条目 X 添加到其日志中，并转发到 A、B、D 和 E。一旦大多数服务器确认已收到并写入该条目，领导者就会将其提交到其状态机，并通知 Follower 也进行提交。

此过程确保所有服务器都同意相同的已提交日志条目序列，并且即使领导者在提交后发生故障，已提交的条目仍保持持久性。此外，Raft 的机制保证了任何新选出的领导者都将始终拥有最新的日志，从而在整个系统中保持一致性。

如果领导者崩溃，例如，如果服务器 C 意外失败，其余 Follower 服务器将检测到心跳消息的缺失。这将触发新的领导者选举。相同的选举过程重复进行，并在剩余服务器中选出一个新的领导者。这个无缝的恢复过程确保了系统的持续运行，而不会损害复制日志的一致性。

5. 客户端交互和一致性管理

Raft 通过结构化流程处理客户端请求，其中领导者验证命令、分配唯一 ID，并将它们作为未提交的日志条目附加。然后，领导者通过 AppendEntries RPC 复制这些条目，其中包含其当前任期、先前的日志位置、新命令和提交索引。

追随者在持久化条目并确认它们之前，会验证任期有效性和日志连续性。多数节点必须复制每个条目，并且所有先前的条目必须提交后，领导者才会将其更改应用于其状态机并响应客户端，从而确保线性可扩展性。

该协议维护两个关键不变式：日志匹配属性保证相同的条目共享相同的历史记录，通过只追加日志和一致性检查来强制执行。状态机安全性确保已提交的条目能够通过多数提交、领导者完整性要求和不可变已提交日志在故障中幸存。这些属性协同工作，以防止在正常操作和故障场景中数据丢失或不一致。

为了容错，Raft 会通过基于超时的选举和新领导者通过日志协调来自动处理领导者崩溃。网络分区通过防止少数派领导者提交条目并强制它们在遇到更高任期时让步来管理。日志修复协议通过在第一个不匹配处截断并重新发送后续条目来有效地同步不同的日志，从而在最小化不必要的数据传输的同时保持一致性。

6. 共识算法的比较概览

我们可以在分布式系统中看到多种共识算法，每种算法都针对不同的需求进行了优化。有些优先考虑简单性，而另一些则侧重于拜占庭容错或高吞吐量。

让我们检查一下关键参与者。

Raft 旨在实现清晰易懂和易于实现。它将领导者选举与日志复制分开，使其比替代方案更易于上手。与 Raft 的结构化方法不同，Paxos 提供了强大的 consistency，但复杂度更高——我们通常发现它更难正确实现。

对于拜占庭环境，当面临潜在的恶意参与者时，我们使用 PBFT。它为许多需要强安全保证的区块链平台提供支持。Viewstamped Replication (VR) 赋予我们类似于 Paxos 的保证，但具有更清晰的操作分离。

在协调服务中，我们通常部署 ZAB——ZooKeeper 背后的引擎。它专门用于高可用性的原子广播。对于区块链需求，我们通常选择 Tendermint 或 HotStuff，它们将 BFT 与基于领导者的有效共识相结合。

让我们看一下下面的示例表，这是共识算法的摘要比较

7. 结论

在本文中，我们讨论了 Raft 共识算法，这是一种分布式共识协议，旨在既易于理解又适用于现实世界的系统。我们研究了 Raft 如何通过两种关键机制实现共识：领导者选举和日志复制。

领导者选举过程通过基于任期的投票和随机超时，确保集群的稳定性，而日志复制通过在提交之前需要对条目进行多数确认来保证一致性。

该算法对分布式协调的结构化方法使其对需要可靠性和可维护性的系统特别有价值。