Raft

Tecy 发布于 2025-03-28 106 次阅读

Raft算法是一种为分布式系统设计的一致性算法，旨在简化理解与实现，同时确保强一致性和高可用性。

Raft 设计目标：

  • 可理解性：通过分解问题（领导选举、日志复制、安全性）和强化角色清晰性（领导者、跟随者、候选者），降低学习与实现难度（相比 Paxos）。
  • 强一致性：保证所有节点对日志顺序达成一致，满足线性一致性语义。
  • 容错性：在部分节点故障或网络分区时仍能正常运作，容忍不超过半数节点故障。

节点角色：

  • 领导者（Leader）：唯一处理客户端请求、管理日志复制的节点。
  • 跟随者（Follower）：被动响应领导者/候选者的请求。
  • 候选者（Candidate）：选举过程中发起投票的临时角色。

任期（Term）：

  • 全局递增的整数，标识逻辑时间周期。每个任期内至多存在一个领导者。

角色转换：

节点状态：

Leader election

主要过程

Follower 处有定时器，定时器超时后 Follower 转换为 Candidate 开始选举，获得超过一半选票后成为 Leader，Leader 处理请求、发送心跳重置其他节点的定时器。

选举过程

  1. 候选者 Term 自增，向其他节点发送 RequestVote RPC。
  2. 节点投票：同一任期内仅投一票（votedFor 记录投票），且候选者的日志至少与自身一样新。
  3. 候选者获多数票则成为领导者，立即发送心跳确立权威。

RequestVote RPC

投票规则

  1. 任期检查：
  • 候选者的任期 < 当前节点的任期，拒绝投票。
  • 候选者的任期 > 当前节点的任期，当前节点转为 Follower，更新自己的任期。
  1. 日志比较：
  • 候选者的LastLogTerm > 跟随者的LastLogTerm → 投票。
  • 候选者的LastLogTerm < 跟随者的LastLogTerm → 拒绝。
  • 候选者的LastLogTerm = 跟随者的LastLogTerm ：
    • 候选者的LastLogIndex ≥ 跟随者的LastLogIndex → 投票。
    • 候选者的LastLogIndex < 跟随者的LastLogIndex → 拒绝。

冲突处理

Case Split Vote：
原因：多个 Candidate 同时竞选瓜分选票（split vote）导致无法选出 leader（没有节点的票数超过一半）。
解决方案：

  • 随机选举超时：每个节点的选举超时时间在区间内随机选择，降低冲突概率。
  • 超时后重新选举：若未选出领导者，候选者等待新的随机超时后再次尝试。

Case Split Brain：
原因：网络分区导致旧领导者仍存活，但已被隔离。
解决方案：

  • 任期号强制更新：任何节点收到更高任期的RPC时，立即更新自身任期并退回跟随者。
  • 旧领导者发送心跳时，若发现自身任期已过期，自动退位。

选举优化

  • 随机化选举超时：避免多个节点同时触发选举，减少选举冲突。
  • 心跳压制：候选者在等待投票期间，若收到合法领导者的心跳，立即退位。
  • 预投票机制（扩展）：某些实现（如etcd）引入PreVote阶段，节点在成为候选者前先探测集群状态，避免因网络抖动引发无效选举。

Log replication

主要过程

客户端向 leader 发送请求，leader 封装请求为日志条目，追加到本地日志（未提交），通过 AppenEntries RPC 将新条目并行发送给其他节点。

AppendEntries RPC

日志复制规则

Follower 处：

  1. 验证领导者权威：
  • RPC中的任期 < 自身当前任期，拒绝请求。
  • 否则，跟随者更新任期并重置选举超时。
  1. 日志连续性校验：
  • 检查本地日志在PrevLogIndex处是否存在条目：
    • 不存在 → 拒绝请求。
    • 存在：
      • 该条目的任期 ≠ PrevLogTerm → 拒绝请求，删除从此位置之后的所有日志。
      • 该条目的任期 = PrevLogTerm → 匹配成功，从该位置开始追加不存在的日志。

Leader 处：

成功响应：

  • 更新对应跟随者的nextIndex和matchIndex（记录其日志同步进度）。
  • 若多数节点已复制该条目，领导者提交该条目（更新commitIndex）。

失败响应：

  • 领导者回退nextIndex（递减索引），重发更早的日志条目，直到找到一致点。

容错与异常

领导者崩溃：

  • 新领导者通过日志强制同步机制覆盖可能的未提交日志。
  • 客户端请求因未提交会自动重试。

网络分区：

  • 少数派分区的领导者因无法获得多数确认，停止提交新日志。
  • 多数派分区选举新领导者，旧领导者在恢复后自动退位。

跟随者日志滞后：

  • 领导者持续重试AppendEntries，逐步回退nextIndex，直至找到一致点。

日志复制优化

批处理（Batching）：

  • 将多个客户端请求合并为一个AppendEntries RPC，减少网络通信开销。

流水线化（Pipelining）：

  • 允许领导者在未收到前一批日志的确认时，继续发送后续日志条目。Follower 需要按顺序确认。

优化日志回退（Optimized Rollback）

  • 携带更多日志上下文：在AppendEntries中附加多条日志，加速冲突修复。

Safety

选举限制

候选者必须拥有比集群中多数节点更完整的日志才能赢得选举。
实现方式：

  • 在RequestVote RPC中携带候选者的LastLogTerm和LastLogIndex。
  • 跟随者投票前需验证候选者的日志是否至少与自身一样新（比较 Term 优先，其次 Index ）。

作用：

  • 防止数据丢失：确保新领导者一定包含所有已提交的日志条目，避免已提交日志被覆盖。
  • 规避脑裂风险：旧领导者（日志滞后）无法获得多数投票，无法继续写入。

日志提交规则

  1. 多数派提交：日志条目必须被超过半数节点持久化后才能标记为已提交。
  2. 任期绑定提交：
    • 直接提交：领导者可立即提交当前任期的日志条目。
    • 间接提交：领导者只能通过提交当前任期条目，间接提交之前任期的日志（避免“ Figure 8问题”）。

日志匹配特性

  • 一致性保证：如果两个节点在某个日志索引位置的条目具有相同的 Term，则它们在该索引之前的所有条目完全一致。

任期递增与权威更新

任期（Term）的核心作用：

  • 逻辑时钟：全局单调递增，标识领导权的合法性。
  • 权威验证：任何 RPC 交互均携带 Term，低 Term 的请求自动失效。

关键行为：

  1. 节点收到更高 Term 的 RPC：
    • 立即更新本地 Term，并退回跟随者状态。
    • 若原为领导者，停止所有写入与心跳。
  2. 候选者发现 Term 过期：
    • 终止选举，转为跟随者。

Cluster membership changes

集群变更安全性

两阶段联合共识

raft 论文提出的安全变更方法：

  1. 提交联合配置 （C-old + C-new），日志条目必须在Cold和Cnew中各自获得多数确认（双重多数原则）。提交后，集群进入联合共识模式，Cold和Cnew节点均参与投票和日志复制。
  2. 提交新配置 (C-new)，-新配置日志只需在Cnew中获得多数确认即可提交，旧节点（Cold - Cnew）收到新配置后，自动停止参与Raft流程。

单阶段成员变更

实际系统（如etcd）常用简化方法，通过限制每次只变更一个节点规避脑裂风险。

变更规则：

  • 单节点变更：每次仅增加或删除一个节点（|C-new| = |C-old| ± 1）。
  • 直接提交新配置：无需联合共识，直接复制C-new日志并在新旧集群的交集多数派中提交。

安全性证明：

  • 单节点变更时，新旧配置的多数派必然存在重叠，避免双主：
    • 设旧配置大小N，新配置大小N±1。
    • 新旧多数派分别为⌈(N+1)/2⌉和⌈(N±1+1)/2⌉。
    • 交集至少包含一个节点，确保不会同时存在两个多数派。

Persistency

必须持久化的状态

持久化时机

  • 任何修改时：上述三个状态一旦发生变化（如收到RPC更新任期、投票、追加日志），必须立即持久化，再响应其他操作。
  • 日志追加：领导者将日志写入本地持久化存储后，才能发送给跟随者。

持久化实现

预写日志（Write-Ahead Log， WAL）：

  • 所有状态变更（如任期更新、投票记录、新日志）先写入顺序追加的日志文件，再更新内存状态。

日志条目首先写入内存中的日志缓冲区，而非直接写入磁盘。这是为了减少磁盘 I/O 次数，提升性能。事务提交（commit）时强制刷盘，通过调用 fsync() 或 FlushFileBuffers() 等系统接口强制刷盘。

Snapshot

随着日志越来越长，持久化、宕机恢复与日志同步会变得很慢。

快照生成触发条件

  • 日志大小阈值：当日志条目数量或占用空间超过预设值。
  • 定期生成：按固定时间间隔（如每小时）生成快照。
  • 领导者的主动请求：领导者检测到跟随者日志过于滞后，主动触发快照以减少同步开销。

快照内容

元数据：

  • lastIncludedIndex：快照中包含的最后一条日志的索引。
  • lastIncludedTerm：该日志条目对应的任期号。
  • peers[]：生成快照时的集群成员配置（用于成员变更恢复）。

应用状态：

  • 状态机在lastIncludedIndex时的完整数据（如键值数据库的所有键值对），格式由应用层定义。

快照生成流程

  1. 触发快照生成（通常由状态机主动调用Raft层的Snapshot()接口）。
  2. 冻结状态机，确保状态机在生成快照期间无变更。记录当前的lastApplied索引，作为快照的lastIncludedIndex。
  3. 序列化状态机数据，应用层将状态机数据序列化为紧凑格式（如压缩的二进制流）。
  4. 持久化快照。
  5. 截断日志，删除所有索引 ≤ lastIncludedIndex的日志条目。
  6. 恢复处理，解除状态机写阻塞，继续处理新请求。

Tips：
序列化状态机数据优化：

  • 增量快照：仅保存自上次快照以来的差异数据（需应用层支持）。
  • 压缩算法：使用Snappy、Zstandard等快速压缩算法减小体积。

InstallSnapshot RPC