目录

拜占庭将军问题

Raft算法是干什么的？

一、领导选举（选老板）

二、日志复制（发通知）

三、安全性（防篡改）

🌰 举个真实例子

✔️ Raft的优势

基础

状态机

节点类型

任期

日志

领导人选举

日志复制

安全性

选举安全性

日志匹配性

状态机安全性

集群成员变更安全性

---

拜占庭将军问题

我们可以先通过拜占庭将军的例子来帮助理解算法>共识算法。
 

假如现在有多位将军，每个将军营中没有叛军，信使的信息是可靠的但有可能会被暗杀，将军和将军们之间如何达成是否要进攻的一致性决定？

解决的方法大致可以理解成：在所有的将军中选择出一个大将军，用来做出所有的决定。

举例如下：假如说我们现在一共是有3个将军A，B，C，每个将军都有一个随机时间的倒计时器，倒计时一结束，这个将军就会把自己当做是大将军的候选人，然后会派信使传递投票的信息给将军B和C，如果说，此时将军B和C还没有把自己当做是大将军的候选人（即自己的倒计时器还没有结束），并且没有把选举票
投给别人，那么他们就会把投票投给将军A。信使回到将军A时，将军A知道自己收到了足够的票数，就会成为大将军。

有了大将军之后，是否需要进攻就会由大将军A来决定，然后再派信使去通知另外的两个将军。如果说一段时间以后还没有收到将军B和C的回复（信使可能被暗杀了），那大将军A就会在重派一个信使，直到收到回复信息。

Raft算法是干什么的？

想象有个银行要把你的存款同时保存在北京、上海、广州三台服务器上，但网络可能出故障。Raft的作用就是让这三台服务器始终保持账本完全一致，即使其中一台坏了也不会出错。

三个核心机制

机制	比喻	作用
领导选举	选董事长	保证只有一个决策中心
日志复制	文件传阅	确保所有节点数据同步
安全性	审计制度	防止数据篡改或丢失

一、领导选举（选老板）

想象三个员工要选组长：

1. 心跳机制：组长必须每5秒发消息（类似"我还活着"）
2. 选举流程：
   • 员工A发现10秒没收到消息 → 自荐当候选人
   • 员工A请求投票："选我当组长吧！"
   • 获得超过半数投票（3人中至少2票）即当选
3. 随机超时：每个员工等待的时间随机（比如员工B等7秒，员工C等12秒），避免同时竞选

二、日志复制（发通知）

假设组长要修改账本：

1. 收到客户存款请求 → 记录到自己的笔记本（日志）
2. 发送给组员："把这条记录抄到你们本子上"
3. 收到大多数确认后宣布："现在正式生效！"

三、安全性（防篡改）

两个铁律保证数据安全：

1. 选举限制：只有拥有最新日志的节点才能当选组长
   • 比如组长的账本记录到第10页，其他节点必须至少有第10页才能竞选
2. 提交规则：只有被大多数确认的日志才能最终生效

🌰 举个真实例子

假设我们要存100元：

1. 客户端发给组长（上海节点）
2. 上海节点记录："2024-02-26 存100元"
3. 北京和广州节点确认记录
4. 上海收到2个确认（超过半数3/2=2）→ 执行操作
5. 通知所有节点正式更新余额

此时即使上海节点宕机，北京或广州也能选出新组长，且数据一致。

---

✔️ Raft的优势

• 比Paxos简单10倍：Paxos的论文需要一周理解，Raft只需要一天
• 明确分工：任何时候只有1个Leader，避免混乱
• 自动故障恢复：节点故障后能快速重组
• 实际应用：Etcd、Consul等知名系统都在用

基础

状态机

从数学模型角度理解

• 状态机本质上是一个数学模型，它由状态集合、输入集合、状态转移函数和输出函数组成。在 Raft 算法中，服务器的各种状态，如 Follower、Candidate、Leader 就是状态集合中的元素。客户端的请求、心跳信号等可以看作是输入集合。状态转移函数根据当前状态和输入来决定下一个状态，比如 Follower 在没有收到心跳超时后变为 Candidate。输出函数则决定了在某个状态下接收到输入后会产生什么结果，例如 Leader 接收到客户端写请求后，会向 Follower 发送日志复制请求。

从程序运行角度理解

• 把状态机想象成一个程序内部的运行框架。在 Raft 算法运行的服务器程序中，状态机控制着程序的执行流程和数据处理方式。当服务器处于 Follower 状态时，程序主要执行接收并记录来自 Leader 的日志等操作；当变为 Leader 状态后，程序就会执行如处理客户端请求、向 Follower 发送心跳和日志等不同的操作。状态机就像是一个无形的指挥棒，让程序根据不同的状态来执行相应的逻辑，保证整个分布式系统的有序运行。

从数据一致性角度理解

• Raft 算法的核心目标是保证分布式系统中数据的一致性，状态机在其中起着关键作用。所有服务器的状态机都以相同的初始状态开始，然后通过日志来接收和处理相同的操作序列。比如，有一个分布式键值对存储系统采用 Raft 算法，客户端向 Leader 发送一个设置键值对的请求，Leader 把这个操作记录到日志并复制给 Follower，所有服务器的状态机按照日志中的操作顺序执行，最终都能保证存储的键值对数据是一致的。即使出现服务器故障等情况，通过状态机和日志的配合，也能在故障恢复后让系统重新达到一致状态。

从实际应用场景角度理解

• 以分布式数据库系统为例，假设有多个数据库节点组成的集群采用 Raft 算法。当客户端要插入一条数据时，请求会先到达 Leader 节点，Leader 节点的状态机接收到这个请求后，将插入操作记录到日志，并向 Follower 节点的状态机发送日志复制请求。Follower 节点的状态机收到日志后，按照顺序执行插入操作，这样所有节点的数据库中都插入了相同的数据，保证了数据的一致性和完整性。

节点类型

一个 Raft 集群包括若干服务器，以典型的 5 服务器集群举例。在任意的时间，每个服务器一定会处于以下三个状态中的一个：

• Leader：负责发起心跳，响应客户端，创建日志，同步日志。
• Candidate：Leader 选举过程中的临时角色，由 Follower 转化而来，发起投票参与竞选。
• Follower：接受 Leader 的心跳和日志同步数据，投票给 Candidate。

在正常的情况下，只有一个服务器是 Leader，剩下的服务器是 Follower。Follower 是被动的，它们不会发送任何请求，只是响应来自 Leader 和 Candidate 的请求。

图中有三个主要的节点角色：

 

• Follower（跟随者）：节点启动时处于此状态。如果在一段时间内没有收到来自 Leader（领导者）的心跳消息（即超时，times out），则会转变为 Candidate（候选人） 状态，开始发起选举。
• Candidate（候选人）：当 Follower 超时后成为 Candidate，发起选举，向其他节点请求投票。如果收到多数节点的投票（receives votes from majority of servers），则转变为 Leader 状态；如果在选举过程中发现有更新任期（term）的 Leader ，则会变回 Follower 状态；如果选举超时（times out），则重新发起选举。
• Leader（领导者）：负责管理日志复制，向 Follower 发送心跳消息以维持领导地位。如果发现有其他节点的任期更高，会转变为 Follower 状态。

任期

1. 任期的基本定义与选举机制：Raft 算法把时间划分成任期，每个任期都从选举开始。选举时，一个或多个 Candidate 竞争成为 Leader。成功赢得选举的 Candidate 在该任期内担任 Leader，若未选出 Leader，则开启新任期并马上进行下一次选举，确保每个任期至少有一个 Leader。这一机制保证了集群中始终有节点负责协调工作，比如在一个分布式数据库集群中，只有选举出 Leader 才能统一管理数据的读写操作。
2. 节点对任期号的存储与更新：每个节点都会保存当前的 term 号，节点间通信时会交换该信息。若某节点发现自身 term 号小于其他节点，会将自己的 term 号更新为较大值。这种机制使得所有节点能及时同步最新的任期信息，保证整个集群在相同的时间基准下运行。
3. 任期号对节点状态的影响：当 Candidate 或 Leader 发现自己的 term 过期（即小于其他节点的 term 号）时，会立即退回为 Follower。这一规则保证了在新的选举产生更 “新” 的 Leader 时，旧的 Candidate 或 Leader 能及时调整自身状态，避免与新的集群状态产生冲突。
4. 任期号对请求处理的影响：如果服务器收到的请求 term 号过期，会拒绝该请求。这确保了节点只处理符合当前集群状态的请求，防止因处理过期请求导致数据不一致或其他问题。比如在集群进行选举切换 Leader 期间，过期的写请求会被拒绝，避免数据错误写入旧的 Leader 节点。

日志

1. 日志条目（entry）
   • 定义与创建：每个事件被称为一个 entry，并且只有 Leader 能够创建 entry。这保证了整个分布式系统中日志记录的一致性，因为所有新的日志记录都由唯一的 Leader 来生成。
   • 内容结构：entry 的内容格式为 <term, index, cmd>。其中，term 表示该 entry 创建时所在的任期号，用于标识该日志条目的时间范围和版本；index 是该 entry 在日志数组中的索引位置，用于唯一确定其在日志中的顺序；cmd 是可以应用到状态机的操作，状态机可以理解为分布式系统中实际执行具体业务逻辑的部分，例如数据库系统中对数据的增删改查操作指令。
2. 日志数组（log）
   • 构成与管理：log 是由多个 entry 构成的数组，每个 entry 在 log 中都有一个对应的 index，用于标识其在数组中的位置。并且只有 Leader 才有权改变其他节点的 log，这确保了所有节点的日志最终能保持一致。
   • 日志添加与提交流程：entry 首先会被 Leader 添加到自己的 log 数组中，然后 Leader 发起共识请求，在获得大多数节点同意后，Leader 才会将该 entry 提交给状态机执行。这一过程通过共识机制保证了只有经过多数节点认可的操作指令，才会被真正应用到状态机上，从而保证了数据的一致性和可靠性。
   • Follower 的日志同步：Follower 自身不能主动创建新日志，只能从 Leader 获取新日志以及当前的 commitIndex（已提交日志条目的索引）。Follower 根据这些信息，将对应的 entry 应用到自己的状态机中，这样就使得 Follower 节点的状态机与 Leader 节点的状态机保持同步。

领导人选举

Raft 算法的领导人选举是 Raft 协议中非常关键的部分，用于在分布式系统中确定一个节点作为 Leader 来协调和管理整个系统的操作，以下从触发条件、选举流程、选举规则等方面详细解释：

• 选举触发条件
  • 初始启动：当分布式系统中的节点刚开始启动时，由于还没有确定的 Leader，所以会触发领导人选举，每个节点都有机会成为 Leader。
  • Leader 故障：在系统运行过程中，如果 Follower 节点在一定时间内没有收到来自 Leader 的心跳信号，就会认为 Leader 可能出现了故障或网络分区等问题，此时也会触发新一轮的领导人选举。
• 选举流程
  • 成为 Candidate：当节点判定需要进行选举时，它会将自己的状态转换为 Candidate，然后给自己投票，并向其他节点发送请求投票的消息。这个消息包含了该 Candidate 的任期号、自身 ID 等信息。
  • 投票阶段：其他节点收到请求投票消息后，会根据一定的规则来决定是否给该 Candidate 投票。如果一个节点在同一个任期内还没有投过票，并且认为 Candidate 的日志至少和自己的一样新，就会给这个 Candidate 投票，并将自己的状态保持为 Follower。每个节点在一个任期内只能投出一票。
  • 赢得选举：Candidate 需要收集到超过半数节点的投票才能赢得选举，成为 Leader。一旦一个 Candidate 获得了多数票，它就会转变为 Leader 状态，并开始向其他节点发送心跳消息，以表明自己的领导地位，同时也用于维持与 Follower 之间的连接和同步。
• 选举规则
  • 任期号比较：任期号是选举中的一个重要概念，它类似于一个时间戳，用于标识选举的轮次。节点在进行选举或处理选举相关消息时，会首先比较任期号。如果接收到的消息中的任期号大于自己当前的任期号，节点会更新自己的任期号，并将自己的状态转换为 Follower；如果任期号小于自己的，则会拒绝该消息。
  • 日志新旧比较：在判断是否给 Candidate 投票时，节点会比较 Candidate 的日志和自己的日志。日志的新旧程度通过日志条目的索引和任期号来判断。如果 Candidate 的日志最后一条的索引值更大，或者索引值相同但任期号更大，就认为 Candidate 的日志更 “新”，符合投票条件。

日志复制

Raft 算法的日志复制是保证分布式系统数据一致性的关键机制，以下从日志结构、复制过程、一致性保证等方面来理解：

日志结构基础

• Raft 算法中的日志由一系列的日志条目（entry）组成。每个日志条目包含 <term, index, cmd> 等信息，其中 term 是任期号，用于标识该条目是在哪个任期内产生的；index 是该条目在日志中的索引位置，用于唯一确定每个条目；cmd 是可以应用到状态机的操作，比如在分布式键值存储系统中，可能是插入、删除或更新某个键值对的操作指令。

日志复制过程

1. Leader 接收客户端请求：当客户端向分布式系统发送写请求时，请求会先到达 Leader 节点。例如在一个分布式文件系统中，客户端要创建一个新文件，这个创建文件的请求会被 Leader 接收。
2. Leader 记录日志条目：Leader 会将该操作记录为一个新的日志条目，添加到自己的日志数组中。假设当前任期为 5，日志中已有的最后一个条目的索引为 10，那么新的日志条目索引为 11，Leader 就会创建一个形如 <5, 11, 创建文件操作> 的日志条目并加入自己的日志。
3. Leader 发送复制请求：Leader 会将新的日志条目封装在 AppendEntries RPC（远程过程调用）消息中，发送给所有的 Follower 节点。这个消息包含了日志条目的任期号、索引以及操作内容等信息。
4. Follower 接收并处理：Follower 节点接收到 AppendEntries RPC 消息后，会首先检查消息中的任期号是否与自己的一致。如果任期号一致，并且该日志条目的索引位置是紧跟在自己已有日志的最后一条之后，Follower 就会将这个日志条目添加到自己的日志中，并向 Leader 发送一个确认消息，表示日志已成功接收。
5. Leader 提交日志：当 Leader 收到大多数 Follower 节点（超过半数）对某个日志条目的确认消息后，就认为该日志条目可以提交了。Leader 会将该日志条目应用到自己的状态机上，执行相应的操作，比如在上述分布式文件系统中创建文件。同时，Leader 会更新一个名为 commitIndex 的变量，记录下已提交的日志条目的最大索引值。
6. Follower 提交日志：Follower 节点会定期检查自己的日志，当发现有日志条目的索引值小于等于 Leader 的 commitIndex 时，就会将这些日志条目应用到自己的状态机上，执行相应操作，从而保证与 Leader 的状态一致。

一致性保证机制

• 日志匹配原则：Raft 算法保证，如果两个日志条目的索引和任期号相同，那么它们所包含的操作内容一定是相同的。这是通过在日志复制过程中严格按照索引顺序和任期号来实现的。例如，在任何节点上，索引为 15 且任期号为 3 的日志条目所代表的操作都是一样的。
• 冲突解决：如果 Follower 的日志与 Leader 的日志出现冲突，即 Follower 在某个索引位置上的日志条目与 Leader 不同，或者 Follower 缺少 Leader 有的某些日志条目。此时，Follower 会根据 Leader 发送的 AppendEntries RPC 消息中的日志信息，删除自己冲突的日志条目，并从冲突点开始，按照 Leader 的日志进行复制，以保证最终与 Leader 的日志一致。
• 强制日志匹配：Leader 在发送 AppendEntries RPC 消息时，会附带前一个日志条目的索引和任期号。Follower 收到消息后，会检查自己的日志中是否存在与该索引和任期号匹配的日志条目。如果不存在或者不匹配，Follower 就会拒绝这个消息，Leader 会不断重试发送，直到 Follower 的日志与 Leader 匹配为止。通过这种方式，确保了所有节点的日志最终能够达成一致

安全性

Raft 算法的安全性是确保分布式系统数据一致性和正确性的关键，主要体现在选举安全、日志匹配、状态机安全等几个方面，以下是具体分析：

选举安全性

• 定义：在任何一个任期内，最多只能有一个 Leader 被选举出来，这确保了系统中不会出现多个 Leader 同时进行操作而导致数据混乱的情况。
• 实现原理
  • 唯一任期号：Raft 算法通过任期号来区分不同的选举轮次。每个节点都维护着一个当前任期号，在选举过程中，节点只会接受任期号大于自己当前任期号的请求。这就保证了在同一时刻，所有节点对于当前选举所处的轮次有一致的认知，避免了不同节点在不同任期下进行选举的混乱情况。
  • 多数投票原则：一个 Candidate 要成为 Leader，必须获得超过半数节点的投票。由于分布式系统中的节点数量通常是奇数个，所以不可能有两个 Candidate 同时获得多数票，从而保证了每个任期内只会有一个 Leader 被选举出来。

日志匹配性

• 定义：如果两个节点的日志中具有相同索引和任期号的日志条目，那么这些条目所包含的命令和状态应该是完全相同的，这是保证所有节点状态机最终一致的基础。
• 实现原理
  • 日志复制机制：Leader 在接收到客户端的写请求后，会将操作记录为新的日志条目，并通过 AppendEntries RPC 将日志条目复制给 Follower。Follower 在接收日志条目时，会检查条目索引和任期号是否连续、匹配，只有在匹配的情况下才会接受并保存日志条目，确保了日志在复制过程中的准确性和一致性。
  • 冲突解决策略：当 Follower 的日志与 Leader 的日志出现冲突时，Follower 会根据 Leader 发送的日志信息，删除自己冲突的日志条目，并从冲突点开始按照 Leader 的日志进行复制。这一策略保证了即使在出现网络故障或节点故障导致日志不一致的情况下，最终所有节点的日志也能恢复到一致状态。

状态机安全性

• 定义：所有节点的状态机在处理相同的日志条目序列后，应该达到相同的状态，从而保证分布式系统中数据的一致性和正确性。
• 实现原理
  • 相同的初始状态：在系统启动时，所有节点的状态机都被初始化为相同的状态，这为后续的状态一致性奠定了基础。
  • 有序执行日志条目：节点按照日志条目的索引顺序依次执行操作，并且只有在日志条目被提交后才会应用到状态机上。由于日志匹配原则保证了所有节点具有相同的日志条目序列，所以按照相同顺序执行这些条目会使所有节点的状态机达到相同的状态。

集群成员变更安全性

• 定义：在集群成员发生变化，如添加或删除节点时，确保系统能够在过渡期间保持数据的一致性和可用性，不会出现数据丢失或不一致的情况。
• 实现原理
  • 两阶段成员变更：Raft 算法采用两阶段的方式进行集群成员变更。首先，Leader 会向所有节点发送包含新成员配置的日志条目，但在大多数节点确认收到该条目后，并不立即应用新配置，而是进入一个过渡阶段。在过渡阶段，Leader 同时使用新旧两种成员配置进行日志复制和选举等操作，确保系统在成员变更过程中仍然能够正常运行且数据一致。当新成员配置的日志条目被大多数节点提交后，再完全切换到新的成员配置，完成集群成员的变更。

为了更好地理解 Raft 算法中集群成员变更安全性的两阶段实现原理，我们通过一个具体例子来详细说明。假设一个分布式集群初始有 3 个节点，分别为 A、B、C，当前 A 是 Leader。现在要添加一个新节点 D 到集群中。

第一阶段：发送新成员配置日志条目

1. Leader 生成并发送日志条目：Leader（节点 A）生成一个包含新成员配置（即 A、B、C、D）的日志条目。这个日志条目就像其他普通日志条目一样，包含任期号、索引和配置内容等信息。然后，A 通过 AppendEntries RPC 消息将这个日志条目发送给所有节点（B、C 和新加入的 D）。
2. 节点接收并确认：节点 B、C 和 D 收到该日志条目后，会检查任期号等信息，确认无误后将其添加到自己的日志中，并向 Leader（A）发送确认消息。
3. 不立即应用新配置：即使 Leader（A）收到了大多数节点（这里至少 2 个节点，即 B 和 C）的确认消息，它也不会马上应用新的成员配置。此时系统进入过渡阶段。

第二阶段：过渡阶段与完全切换

 

1. 过渡阶段操作：在过渡阶段，Leader（A）同时使用新旧两种成员配置进行操作。
   • 日志复制：当有新的客户端请求（比如写入数据）时，Leader（A）会将新的日志条目同时发送给旧配置中的节点（B 和 C）以及新配置中的所有节点（B、C、D）。只要收到大多数节点（旧配置中是 B 和 C，新配置中是 B、C、D 中任意两个）的确认，就认为日志可以提交。这样做保证了无论是旧配置的节点还是新配置的节点，都能接收到并确认新的日志条目，维持数据一致性。
   • 选举操作：如果在这个阶段发生领导人选举（例如 Leader A 出现故障），参与选举的节点会同时参考新旧两种配置来确定多数节点。例如，在旧配置中，B 和 C 构成多数；在新配置中，B、C、D 中任意两个节点构成多数。这样确保了在选举过程中，无论是旧配置的节点还是新配置的节点都能参与到选举中，保证系统的可用性。
2. 完全切换：当包含新成员配置的日志条目被大多数节点（旧配置或新配置中的多数）提交后，意味着所有节点的日志都已经包含了新成员配置。此时，所有节点完全切换到新的成员配置（A、B、C、D）。从这个时刻起，系统只使用新的成员配置进行日志复制、选举等操作，完成了集群成员的安全变更。

 

这种两阶段的成员变更方式，通过在过渡阶段同时使用新旧配置，避免了在成员变更过程中因部分节点使用旧配置，部分节点使用新配置而导致的数据不一致或选举混乱问题，确保了系统在整个成员变更过程中的数据一致性和可用性。