分布式算法Raft
,
Source
Edit
History

分布式共识算法Raft

Catalogue
  1. 1. Raft 诞生
  2. 2. 基础概念
    1. 2.1. 共识 & 一致性
    2. 2.2. 拜占庭问题
    3. 2.3. 复制机状态机
  3. 3. Raft 算法基础
    1. 3.1. 领导者选举
      1. 3.1.1. 节点状态
      2. 3.1.2. 任期(Term)
      3. 3.1.3. 选举过程
    2. 3.2. 日志复制
      1. 3.2.1. 正常复制
      2. 3.2.2. 日志冲突处理
  4. 4. 安全性保证
    1. 4.1. 选举限制
    2. 4.2. Leader 只允许提交自己任期内的日志

Raft 诞生

2013 年, 斯坦福大学的 Diego Ongaro 和 John Ousterhout 发表了 Raft 论文《In Search of an Understanding Consensus Algorithm》,但是这篇论文比较短小,只是简单介绍了一下原理,对一些实现细节部分没有提及。更详细的论文是 Diego Ongaro 的博士论文《CONSENSUS: BRIDGING THEORY AND PRACTICE》。Raft的产生就是为了代替 Paxos, 毕竟 Paxos算法自 1990 年诞生以来，就一直被诟病难以理解,这也导致了后面业界很多基于Paxos的实现都是”Paxos-like”实现。

基础概念

共识 & 一致性

共识（Consensus）很多时候会与一致性（Consistency）放在一起讨论。严谨地讲，两者的含义并不完全相同。一致性的含义比共识宽泛，在不同场景（基于事务的数据库、分布式系统等）下意义不同。具体到分布式系统场景下，一致性指的是多个副本对外呈现的状态。如前面提到的顺序一致性、线性一致性，描述了多节点对数据状态的共同维护能力。而共识，则特指在分布式系统中多个节点之间对某个事情（例如多个事务请求，先执行谁？）达成一致观点的过程。因此，达成某种共识并不意味着就保障了一致性。

拜占庭问题

拜占庭问题（Byzantine Problem）又叫拜占庭将军（Byzantine Generals Problem）问题，讨论的是在少数节点有可能作恶（消息可能被伪造）的场景下，如何达成共识问题。 Raft 集群内的节点都对选举出的 Leader 采取信任, 因此, Raft 算法并不是一种拜占庭容错算法。

复制机状态机

复制状态机的结构

上面是复制状态机架构图。共识算法通常出现在复制状态机的环境中, 也就是上图的 Consensus Module, 它管理着来自客户端的状态机指令的复制日志(Log)。 状态机(State Machine)处理来自日志(Log)的相同指令序列，因此它们产生相同的输出。

Raft 算法基础

为了让 Raft 算法更好被人理解, Raft 设计者将一致性问题分解成了三个相对独立的子问题：

  • 领导者选举：启动集群时或现有领导者异常时必须选出新的领导者。
  • 日志复制：领导者接收来自客户端的日志条目，并在整个集群中复制它们，迫使其他节点的日志与自己的一致。
  • 安全性：Raft 的安全属性的关键是状态机安全性属性：如果任一个节点已将特定的日志条目应用于其状态机，则其他节点都不可以对同一日志索引应用不同的指令。Raft 通过选举机制的额外限制以及 Leader 日志提交的任期限制来保证这一特性。

领导者选举

节点状态

集群中的节点主要有以下三者状态:

  • Leader (领导者): 处理与客户端的交互和与 Follower 的日志复制等，正常情况下只有一个 Leader
  • Follower (追随者): 被动从 Leader 同步日志，同时也会在 Leader 超时后转变为 Candidate 参与竞选，正常情况
    下集群中除了 Leader 之外都是 Follower
  • Candidate (候选者): 在竞选期间参与竞选

不同状态的节点之间会发生下图所示的一些变化:

image-20220305152805885

节点的初始状态都是 Follower, 当节点超时(150 ~ 300 ms, 随机), 它会成为 Candidate, 开始竞选 Leader, 当得到大多数选票时, Candidate 会变成 Leader, 否则, 所有节点会再次进入倒计时状态, 重复这个过程, 直到选出 Leader。Leader 选出后, 会周期性地向其他节点发送心跳请求, 避免新的 Leader 产生。

由 Candidate 发往其他节点的请求投票 RPC(RequestVote RPC) 的定义如下:

image-20220305170317787

任期(Term)

Leader 的选举引出了一个新的概念——任期（Term）。

任期

  • 时间被划分成一个个的任期，任期用连续单调递增的整数标记，每个任期开始都是一次选举
  • 在选举成功后，Leader 会管理整个集群直到任期结束 (一个任期最多只会产生一个 Leader)
  • 有时候选举会失败，那么这个任期就会没有 Leader 而结束, 如上图的 t3
  • 当服务器之间通信的时候会交换当前任期号；如果一个服务器的当前任期号比其他的小，那么他会更新自己的编号到较大的编号值。如果 Leader 或者 Candidate 发现自己的任期号过期了，那么他会立即恢复成 Follower。如果一个节点接收到一个包含过期的任期号的请求，那么他会直接拒绝这个请求。
选举过程

要开始一次选举过程, Follower 要先增加自己当前的任期号(Term)并且转换到 Candidate 状态。他会先给自己投一票, 然后并行的向集群中的其他服务器节点发送拉票请求。其他节点在收到 Candidate 发送的拉票请求后, 会根据以下规则(Leader 选举限制)判定是同意还是反对，见下图:

投票限制流程

其他节点在收到 Candidate 的拉票请求后的判定逻辑:

  1. 如果当前节点已经给其他节点(根据 candidateId 判定, 也可以是自己)投过票, 则反对
  2. 如果 Candidate 的任期(Term)比当前节点的任期小, 则反对, 并将 Candidate 的任期设置为当前节点的任期
  3. 如果 Candidate 的 lastLogTerm(上一条日志的任期)比当前节点上一条日志的任期小, 则反对
  4. 如果 Candidate 的 lastLogIndex(上一条日志的索引)比当前节点上一条日志的索引小, 则反对
  5. 否则, 当前节点则投票给 Candidate，当前任期内, 不会再投票给其他的 Candidate

选举的动态图如下，初次选举:

Leader初次选举

Leader 异常后, 重新选举:

Leader再次选举-Leader下线

日志复制

正常复制

流程如下图:

日志复制-正常复制

以 SET 5 为例, 日志复制的流程如下图所示:

image-20220305163810532

在第一次由 Leader 复制到其他节点时, 并不会立即提交。Leader 提交日志条目的条件是该条目在大多数节点上已经存在。

日志冲突处理
日志复制-冲突解决

当一个 Leader 成功当选时:

  • Follower 可能会缺少一些日志条目（a-b）
  • 可能会有一些未被提交的日志条目（c-d）
  • 或者两种情况都存在（e-f）

在 Raft 算法中，Leader 是通过强制 Follower 直接复制它的日志来处理不一致问题的。这意味着在 Follower 中冲突的日志条目会被 Leader 的日志所覆盖。

要使得 Follower 的日志进入和自己一致的状态，Leader 必须找到最后两者达成一致的地方，然后删除从那个点之后的所有日志条目，发送自己的日志给 Follower。所有的这些操作都在进行AppendEntries RPC(附加日志条目的 RPC 请求) 的一致性检查时完成。Leader 针对每一个 Follower 维护了一个 nextIndex，这表示下一个需要发送给 Follower 的日志条目的索引地址。当一个 Leader 刚获得权力的时候，他初始化所有的 nextIndex 值为自己的最后一条日志的 index 加 1（上图中的 11）。如果一个 Follower 的日志和 Leader 不一致，那么在下一次的AppendEntries RPC 时的一致性检查就会失败。在被 Follower 拒绝之后，Leader 就会减小 nextIndex 值并进行重试。最终 nextIndex 会在某个位置使得 Leader 和 Follower 的日志达成一致。当这种情况发生，AppendEntries RPC 就会成功，这时就会把 Follower 冲突的日志条目全部删除并且加上 Leader 的日志。一旦AppendEntries RPC 成功，那么 Follower 的日志就会和 Leader 保持一致，并且在接下来的任期里一直继续保持。

在 Leader 发现它与 Follower 的日志匹配位置之前，Leader 可以发送不带任何条目（例如心跳）的AppendEntries RPC 以节省带宽。 然后，一旦 matchIndex(其他节点和 Leader 日志一致的索引位置) 恰好比 nextIndex 小 1，则 Leader 应开始发送实际的日志条目。

Leader 在复制日志时的AppendEntries RPC 请求定义如下:

image-20220305170726211

安全性保证

选举限制

在任何基于 Leader 的一致性算法中，Leader 都必须存储所有已经提交的日志条目。在某些一致性算法中，某个节点即使是一开始并没有包含所有已经提交的日志条目，它也能被选为 Leader。这些算法都包含一些额外的机制来识别丢失的日志条目并把他们传送给新的 Leader。但这种方式会带来很大的复杂性。Raft 使用了一种更加简单的方法，它可以保证所有之前的任期号中已经提交的日志条目在选举的时候都会出现在新的 Leader 中，不需要传送这些日志条目给 Leader。这意味着日志条目的传送是单向的，只从 Leader 传给 Follower，并且 Leader 从不会覆盖自身本地日志中已经存在的条目。

Raft 使用投票的方式来阻止一个 Candidate 赢得选举除非这个 Candidate 包含了所有已经提交的日志条目。如果 Candidate 的日志至少和大多数的服务器节点一样新 或 比他们更新，那么他一定持有了所有已经提交的日志条目。请求投票 RPC(RequestVote RPC) 实现了这样的限制： RPC 中包含了 Candidate 的日志信息，然后投票人会拒绝掉那些日志没有自己新的投票请求。(根据 term、lastLogTerm、lastLogIndex 来判断, 可参考上文选举过程的流程图)

Leader 只允许提交自己任期内的日志

下图展示了一种情况，一条已经被存储到大多数节点上的老日志条目(2)，也依然有可能会被未来的 Leader 覆盖掉。

Leader只允许提交自己任期内的日志

一开始如 (a) 所示，之后 S1 下线，(b) 中 S5 从 S3 和 S4 处获得了投票成为了 Leader 并收到了一条来自客户端的消息，之后 S5 下线。(c) 中 S1 恢复并成为了 Leader (Term=4)，并且将日志复制到了多数节点，此时， 如果没有 Leader 提交的任期限制，则 S1 在任期 4 下提交了任期 2 的内容(此时, 用户可见), 然后 S1 下线。(d1) 中 S5 恢复，并从 S2、S3、S4 处获得了足够投票，然后覆盖了他们在索引 2 处的日志，再提交日志(此时,对于用户来说就产生了前后不一致的问题)。
另一种遵守 Leader 提交任期限制的情况如(d2)所示, 在任期 4 时提交日志时, 顺带着提交了任期 2，此时, S5 不可能成为 Leader(因为 S1、S2、S3 的任期都比它大), 对于用户来说, 就只会见到一种状态, 保证了一致性。