raft (opens new window)

1.1 三个子问题：

1. Leader election领导选举：
2. Log replication日志复制：
3. Safety 安全性：特殊 case，保证 Raft 算法的完备性；

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

• 选出 leader，接收外部的数据更新/删除请求；
• 日志复制到其他 follower 节点
• leader 故障，重新选举新 leader；

2.1 Leader Election

集群中每个节点只能处于 Leader、Follower 和 Candidate 三种状态的一种:

1. follower 从节点：
2. candidate 候选者：
3. leader 主节点：

• 成为 leader 节点后，接受客户端的数据请求，负责日志同步；
• 遇到更高任期 Term 的 candidate 之前任期的 leader 转化为 follower，且投票；
• 遇到更高任期 Term 的 leader ，之前任期的 leader 转化为 follower；

具体的节点状态转换参考下图：

每个任期 Term 都有自TermId，全局唯一、单调递增。

2.2 Log Replication日志复制 (opens new window)

选举 leader 成功后，对外提供服务。Leader 接收客户端请求，转化为 log 复制命令，其他节点完成日志复制请求。每个日志复制请求包括状态机命令 & 任期号，同时还有前一个日志的任期号和日志索引。状态机命令 (opens new window)表示客户端请求的数据操作指令，任期号表示 leader 的当前任期。 follower 日志复制请求的处理流程：

1. follower 会使用前一个日志的任期号和日志索引来对比自己的数据：

• 如果相同，接收复制请求，回复 ok；
• 否则回拒绝复制当前日志，回复 error；

2. leader 收到拒绝复后，继续发送复制请求，带上更前面的日志term和index；
3. 循环，直到找到一个共同的任期号&日志索引。 follower 从这个索引值开始复制，最终和 leader 节点日志保持一致；
4. 超过半数节点复制日志成功， commite ；

2.3 Safety 安全性

2.3.1 Election Safety 选举安全性：避免脑裂 (opens new window)问题

一个Term 内只能有一个 leader，投票原则：

• 一个term，follower 只会投票一次票，先来先得；
• Candidate 存储的日志至少要和 follower 一样新；
• 超过半数投票, 成为 leader；

2.3.2 Leader Append-Only 日志只能 leader 添加修改

所有的数据请求都要交给 leader 节点处理，要求：

1. leader 只能日志追加日志，不能覆盖日志；
2. 只有 leader 的日志项才能被提交，follower 不能接收写请求和提交日志；
3. 只有已经提交的日志项，才能被应用到状态机 (opens new window)中；
4. 选举时限制新 leader 日志包含所有已提交日志项；

2.3.3 Log Matching 日志匹配特性

保证日志的唯一性，要求：

1. 相同索引和任期号，存储的命令是相同的；
2. 着相同索引和任期号，它们之间所有条目完全一样；

2.3.4 Leader Completeness ：leader 必须具备最新提交日志

只有拥有最新提交日志的 follower 节点才有资格成为 leader 节点

candidate 竞选投票时携带最新提交日志，follower 用自己日志和 candidate 做比较。

日志更新 比较日志项的 term (opens new window) 和 index：

• 如果 TermId 不同，选 TermId 最大的；
• 如果 TermId 相同，选 Index 最大的；

2.3.5 State Machine Safety ：确保当前任期日志提交

Raft 日志提交有额外安全机制：leader 只能提交当前任期 Term 的日志，旧任期 Term（以前的数据）只能通过当前任期 Term 的数据提交来间接完成提交。简单的说，日志提交有两个条件需要满足：

1. 当前任期；
2. 复制结点 (opens new window)超过半数；

---

Raft 协议的网络分区与动态成员变更

1. 网络分区与多个 Leader 的产生:

   • 当集群因网络故障分裂成多个无法相互通信的子集群时，如果这些子集群中的某个集群节点数大于（或等于）新的多数派阈值，该子集群可能会选举出一个新的 Leader。
   • 如果有两个子集群，分别遵循旧配置和新配置，并且都满足多数派条件，那么两个子集群可能各自选出一个 Leader。这种情况可能会导致“脑裂”，即短暂的时间内集群中出现两个 Leader。

2. 动态成员变更中的网络分区问题:

   • 在动态成员变更过程中，Raft 会通过日志记录集群的成员变更信息。在这个过程中，如果发生网络分区，可能会导致新旧配置之间的不一致。
   • 比如，如果新配置的 Leader 在某个子集群中，并且节点数超过了新配置中的多数派阈值，同时旧配置的 Leader 在另一个子集群中，并且节点数超过旧配置中的多数派阈值，那么这两个子集群可能会各自选出一个 Leader，导致短暂的“脑裂”。

3. 客户端访问的影响:

   • 当集群出现多个 Leader 时，客户端可能连接到任意一个 Leader，导致数据不一致和潜在的日志回滚问题。
   • 在这种情况下，客户端的请求可能会被不同的 Leader 处理，但这些操作在网络恢复后可能会回滚或冲突。

4. 日志的同步与提交:

   • 日志的追加: Leader 接收到新的日志条目后，立即将该日志条目通过 AppendEntries RPC 发送给 Follower。Follower 会将日志条目追加到自己的日志中，但此时并未标记为已提交。
   • 日志的提交: Leader 会在确认大多数节点已经复制该日志条目后更新 commitIndex，并通过后续的 AppendEntries RPC 或心跳消息将更新的 commitIndex 通知给 Follower。
   • Follower 感知提交: Follower 通过接收 Leader 的 AppendEntries RPC 消息中的 commitIndex 来感知哪些日志条目已被提交，并在本地执行这些提交的操作。

5. Leader 发送 AppendEntries RPC:

   • 立即发送: 当 Leader 接收到新的日志条目时，会立即发送 AppendEntries RPC，将日志条目复制给 Follower。
   • 定期发送: 除了日志复制，Leader 还会定期发送心跳消息（空的 AppendEntries RPC），用于维护领导权、更新 Follower 的 commitIndex，以及检测 Follower 的存活状态。

6. Raft 的异常处理:

   • Raft 通过日志冲突解决、强制日志一致性、重选举机制，确保即便在分区和成员变更的复杂情况下，最终集群可以恢复一致性，选出唯一的合法 Leader。

---

这些笔记总结了 Raft 协议在处理网络分区、动态成员变更和日志同步过程中的关键机制和潜在问题。这些要点有助于理解 Raft 协议在实际分布式系统中的应用和处理异常情况的能力。