Raft 分布式一致性协议笔记

Raft 是一种用来管理日志复制一致性算法。

基本概念

算法限定每个 Server 只能为以下三种状态之一:Leader、Follower 和 Candidate。

算法通过强化 Leader 地位简化日志副本的管理,比如日志项只允许从 Leader 流向 Follower。

因此 Raft 把算法分解为三个子问题:

  1. 选主(Leader Election)
  2. 日志复制(Log Replication)
  3. 安全性保障(Safety):前两个问题独立解决 OK,但是整合在一起还需要注意一些问题。

算法将时间分为多个 Term,Term 以单调递增连续整数标识,Term 值代表着 Leader 的任期号,Term 值的生命周期由每次 Leader Election 开始。如果有 Server 被选为 Leader,则该 Term 直到该 Server 结束 Leader 状态。

每个 Server 都维护着一个当前的 Term,Server 之间的所有的 RPC 都附带当前 Term 信息。

当 Server 接收到有效的 RPC 消息时,Server 会更新其自身记录中的 Term 值,当 Leader 或 Candidate 发现它们自身记录的 Term 属于旧的值,那么它们将会转成 Follower。

选主算法

Raft 使用一种心跳机制来触发 Leader 选举。当 Server 启动时,他们都是Follower。当 Server 在超时时间内接受到由 Leader 或 Candidate 发出的有效 RPC,比如接收到 Leader 发出的 AppendEntry 报文和 Candidate 发出的 RequstVote 报文,就一直保持 Follower 状态。但如果超时时间内没有接受到任何消息,它就假设系统中没有可用的 Leader,该 Server 状态变成 Candidate 进行选举操作。

要开始一次选举过程,Follower 先增加自己的当前 Term 并转换到 Candidate 状态,然后投票给自己并向集群的其他 Server 调用 RequstVote RPC:如果远程 Server 的 Term < Candidate 的 Term,给它投票。Candidate 会一直保持当前状态直到以下三件事之一发生:

  1. 自己成为 Leader(收到过半数的投票)
  2. 别人成为 Leader(收到比它Term值大的AppendEntry)
  3. 一段时间之后没有任何获胜者,倒计时一定时间后再次重新进行选举(则事件1和事件2都没有发生)

日志复制

正常的日志结构:

Raft通过维护以下特性,构成日志匹配特性:

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

Raft 定义 NextIndex 变量,表示 Follower 想从 Leader 获取的下一条日志项 Index,因此,通过告知 Leader 我这 Follower的 NextIndex 值,实现日志复制。

由于算法限制日志项只能由 Leader 流向 Follower,所以这里只有两种情况:

  1. 复制成功,应用到状态机,Leader 统计回复结果并更新 CommitIndex
  2. 复制失败

由于可能存在网络延迟或分区导致日志复制失败,出现日志不一致,而不一致的内容需要删除或覆盖。

因此,Raft 又定义 PrevLogTerm、PervLogIndex 变量,代表日志内容的前一条Term 及 Index。目的告诉 Follower 如果你前一条日志项和我不一样的话,那你 Follower 告诉我 Leader,我 Leader 把前面的日志也给你,直到所有日志相同。

安全性

选举限制

基本算法存在的问题:选举时候对 Leader 日志没有进行判断,导致选出的 Leader 可能是日志尚未完整复制的少部分 Server。

解决办法:选举时候判对 Candidate 日志有没有比自己新,没有的话拒绝该 Candidate。

// Test if satify election restriction
canUpdateLogs := in.LastLogTerm > s.getLastTerm() ||
    (in.LastLogTerm == s.getLastTerm() && in.LastLogIndex >= s.getLastIndex())

提交之前任期的日志项

基本算法存在的问题:图片里有两个故事

  • 故事1 a-b-c-d:由于图a的身份为 Leader 的 S1 崩溃,导致 Term:2 的日志只复制了两份;然后如图b,S5 被选为 Leader 并添加 Term:3 的日志,但是随后 S5 崩溃;然后如图c,S1 连上并且被选为 Leader,并开始把 Term:2 的日志复制到 S3,可以看出 Term:2 的日志已经存在于大多数的 Server,但此时 Term:2 日志不能认为已被安全提交,因为存在如图d的情况,S1 又崩溃了,S5 又被选为 Leader(投票来自S2、S3、S4和自身S5),这时候 S5 将复制其日志到所有 Server。
  • 故事2 a-b-c-e:由于图a的身份为 Leader 的 S1 崩溃,导致 Term:2 的日志只复制了两份;然后如图b,S5 被选为 Leader 并添加 Term:3 的日志,但是随后 S5 崩溃;然后如图c,S1 连上并且被选为 Leader,并开始把 Term:2 的日志复制到 S3,可以看出 Term:2 的日志已经存在于大多数的 Server,但这次 S1 活的久了一点,把 Term:4 的日志也复制到大多数 Server,如图e,这时候如果 S1 崩溃,S5 将不会被选为 Leader,因为 S5 所持有的最新日志是 Term:3,而当前大多数 Server 所持有的最新日志是 Term:4。

因此问题总结为:当某日志已复制到大多数 Server 中,但却不能保证该日志以后不被覆盖,因此日志不能认为被安全提交。

解决思路:Raft 为了简化算法,并没有杜绝这个现象出现,而是在日志能否被安全提交的判断上下文章。

解决办法:在以前判断能否被安全提交的条件是日志存在大部分 Server 的条件上,添加约束——该日志必须为当前 Term 产生的日志。

安全性论证

目的为了证明 Leader 完全特性:当 Leader 在其 Term 内提交了一条日志项,在往后的其他 Leader 和 Term 都存在这条日志项。

Raft 论文里面进行逆向推理,假设往后的其他 Leader 和 Term 都不存在这条日志项。

首先,要使往后的 Leader 不存在这条日志项,那么,

  1. 选举前不存在。
  2. 选举前存在,在任期内被删除或覆盖。

分别讨论,

  1. 如上图,假设 S1 在 Term T(T<U)时刻把该日志项复制到 S2、S3,随后在 Term U 时刻,S5 成为新的 Leader,但这是不可能的。因为 S5 要获得大多数的选票,势必要从 S1、S2 或 S3 中一个获取选票,但是由于 S1、S2 或 S3 日志比 S5 更为新,它们都不会投票给 S5。所以选举前不存在这条日志项的 S5,永远也无法成为 Leader。
  2. 选举后在任期内被删除或覆盖,显然不可能,因为 Leader 不会删除或覆盖日志。

GO语言描述

纯基本实现:https://github.com/akiasprin/kraft

实现备注:

applyChan 以无缓存 Channel 暴露给状态机,把日志的命令导出到状态机,由此实现分布式 KV 储存系统等,但问题该怎么设计 KV 查询的负载均衡?这是个疑问。
完整的添加日志设计应该是:新建 LogEntry{} 并返回它的 Term 和 Index,轮询 Leader 的 CommitIndex,如果 Index>=CommitIndex,比对 Logs[Index].Term==Term,因此添加日志有三种结果:提交成功、过期提交(Log[Index].Term!=Term)、未提交(结果未知,需要不断提交直至出现前面确定的两种情况)。

参考资料

  1. https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
  2. https://github.com/verg/MIT6.824_Labs
  3. https://github.com/goraft/raft
  4. https://groups.google.com/g/raft-dev/c/t4xj6dJTP6E (成员变更也是原论文的一部分,本文并未记录,但本质其实也是一种日志项,原论文提供两种成员变更处理方法,Single-Server-Change 单步变更和 Joint consensus 多节点联合共识,问题出现在单步变更,原因是文中讲述的提交任期前的日志)
  5. https://www.zhihu.com/question/65667634
  6. https://blog.openacid.com/distributed/raft-bug/

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注