本文为 In Search of an Understandable Consensus Algorithm (Extended Version)12的阅读总结笔记，主要为论文前八章，分别总结了 Raft 算法在分布式共识中的领导者选举、日志复制、安全性、以及工程实践中的相关做法。全文大致按照论文章节来组织。

Introduction

在分布式系统中，一般采用主备结构来保证系统的高可用性。在机器宕机、网络分区导致等错误发生时，需要选择备用副本来接替主节点并提供一致的服务，这个切换过程是对客户端透明的。为达到这个目的，采用共识算法来解决上述问题，Paxos 算法在早期分布式系统中发挥了重要作用，但 Paxos 算法的复杂性导致其在工业界和学术界的运用难度大。

本论文提出了一个易于理解和工程实现的共识算法 Raft，由领导者选举、日志复制和安全保障三个模块组成，并做出了相关限制，减少了状态机的状态数量和非确定性。

Replicated state machines

共识算法中，一般采用复制状态机的方式来保持各个副本之间的一致性共识，如果各个副本以相同的状态开始。并接受相同的输入，且将输入以相同的顺序用运至状态机上，则所有的副本上的结果状态都是相同的。

如下图所示，在 Raft 中完成一次共识的操作如下：

  1. 客户端将操作以日志的形式发送至领导者节点后；
  2. 领导者节点中的一致性模块间日志追加到原有日志上，并将其同步至半数以上节点；
  3. 领导者如果收到了半数以上节点的同步成功消息后，提交日志到状态机上，状态机按照日志顺序执行相应的操作；
  4. 领导者的状态机执行完成后，才返回执行成功的消息至客户端。

image-20220424164209365

为了实现多台服务器节点上都能以相同的顺序执行日志，就必须实现复制日志的相同，共识算法的目标就是为了实现上述目标从而保障各服务器上的状态机的状态一致，从而实现高可用性。

通常来说，工程中所使用的共识算法有以下特点：

  • 安全性保证（从不返回一个错误的结果）：在非拜占庭错误情况下，能在网络延迟、分区、丢包、重复和乱序等错误下保证正确性。
  • 可用性：发生网络分区情况下，在半数以上机器能相互通讯、能和客户端通讯的情况下，能保证可用性。
  • 不依赖于时序保证一致性：依赖物理时钟等时间相关的消息可能会导致可用性（丢包、延迟、重发网络包时物理时钟可能会改变），因此，共识算法不能依赖于时序信息来保证一致性。
  • 集群的整体性能不应收集群中的慢速机器所影响。

The Raft consensus algorithm

本论文有提到两个 Paxos 的缺点，分别如下：

  • single-decree Paxos 算法本身较为晦涩难懂，在此基础上构造 multi-Paxos 算法时需要增加错综复杂的规则。
  • multi-Paxos 在工程化实践上难度较大。

为了设计易于理解的共识算法，Raft 算法将共识问题简化成独立的易于理解的子问题，分别为领导者选举、日志复制、安全性和成员变更这几个部分，同时减少了状态的数量来简化需要考虑的状态空间，使系统更加连贯并且在可能的时候消除不确定性。下文将分节 Raft 算法的三个子问题。

Raft basics

Raft 集群中的服务器分为三个角色，分别为领导者、跟随者、候选者，任何时刻，集群中的服务器都处于上述三个状态之一，其关系如下图所示：

  • 通常情况下，系统中仅有一个领导者且其它节点全部为跟随者，领导者和跟随者之间使用心跳机制。
  • 跟随者不会发送任何请求，其仅仅向应来自领导者和候选者的请求，如果客户端和跟随者联系，跟随者会将来自客户端的请求重定向至领导者。
  • 候选者是在选举新的领导者时的一种角色，领导者选举的过程将在下文阐述。

image-20220424223258364

此外，Raft 将时间分割成任意长度的任期（term），任期用连续的整数标记，如下图所示。其中：

  • 每一任期由一次选举开始，候选者赢得选举后成为领导者，其在当前任期内负责日志复制等工作。
  • 某些情况下，无法选出领导者（例如，两个候选者收到了同样数目的选票），此种情况会以未选出领导者结束，直接开始下一任任期并重新开始选举。Raft 算法保证了在一个给定的任期内，最多只有一个领导人。
  • 在特定情况下某服务器由于宕机可能错过了几个任期， 由于任期号的单调递增，使得任期号在 Raft 算法中能充当逻辑时钟，这使得能够领导者能够知晓该服务器的日志落后并开始日志复制。此外，如果领导者收到比其任期号大的消息，则说明其自身任期号过期了，其会转变为跟随者角色。

image-20220424223352450

所有集群服务器的状态如下：

  1. 所有服务器上的持久性状态

    参数 解释
    currentTerm 服务器已知最新的任期（在服务器首次启动时初始化为0，单调递增）
    votedFor 当前任期内投出选票的 candidateId，如果没有投给任何候选人，则置空
    log[] 日志条目；每个条目包含了用于状态机的命令，以及领导人接收到该条目时的任期（初始索引为1）

  2. 所有服务器上的易失性状态

    参数 解释
    commitIndex 已知已提交的最高的日志条目的索引（初始值为0，单调递增）
    lastApplied 已经被应用到状态机的最高的日志条目的索引（初始值为0，单调递增）

  3. 领导者服务上的易失性状态

    参数 解释
    nextIndex[] 对于每一台服务器，发送到该服务器的下一个日志条目的索引（初始值为领导人最后的日志条目的索引+1）
    matchIndex[] 对于每一台服务器，已知的已经复制到该服务器的最高日志条目的索引（初始值为0，单调递增）

Raft 采用如上简化的角色和状态，使得其可以通过两种 RPC 调用来实现集群节点间的通讯，简化了节点间的通讯：

  • RequestVote RPC ： 请求投票 RPC，由候选者在领导者选举过程中发起，用于实现领导者选举。
  • AppendEntries RPC：日志追加 RPC，由领导者发起，实现日志的复制和心跳机制。

此外，Raft 还规定了如下选择用于限制选举和日志复制，以保证一致性：

特性 解释
选举安全特性 对于一个给定的任期号，最多只会有一个领导人被选举出来
领导人只附加原则 领导人绝对不会删除或者覆盖自己的日志，只会增加
日志匹配原则 如果两个日志在某一相同索引位置日志条目的任期号相同，那么我们就认为这两个日志从头到该索引位置之间的内容完全一致
领导人完全特性 如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中
状态机安全特性 如果某一服务器已将给定索引位置的日志条目应用至其状态机中，则其他任何服务器在该索引位置不会应用不同的日志条目

Leader election

如下图角色切换所示，Raft 的领导者选举流程如下：

  1. 跟随者超过一段时间未收到来自领导者的心跳消息后（选举超时），此时其认为整个系统中没有可用的领导者，便将自己的任期加一，进入候选者状态；

    选举时采取随机超时机制。每个服务器都有 election timer，如果超时后且领导者挂掉了（或者大多数服务器无法感知到 leader 是否存活，可能领导者在少数派网络分区中还存活着），就触发选举（没挂掉亦能触发选举，例如某个服务器未收到心跳包且选举超时了）

  2. 新的候选者首先投票给自己，并且并行的向集群中的其它服务器发送 RequestVote RPC ；

  3. 其它服务器收到 RequestVote RPC 后，会按照先来先服务的原则投出该任期的选票，每个跟随者每个任期中仅能投出一张选票。

  4. 当前候选者收到的选票个数后，最终会出现三种选举结果：

    • 当前候选者收到了超过半数以上的选票，其会成为新的领导者，并相应的发送心跳消息给所有服务器，宣布其已经成为新的领导者，以组织其它服务器发起新的选举。
    • 其它候选者赢得了选举成为了新的领导者，该失败的候选者收到新的领导者的心跳消息后，如果新的领导者的任期号大于等于其当前的任期号，其会变为跟随者状态。
    • 一段时间内如果没有选出新的领导者，这说明可能出现了多个候选者，且其选票被瓜分了，都无法获得半数以上的选票数量。这种情况下，所有的候选者会超时，增加任期号并重新发起一轮新的选举。在这种情况下，为了不重复出现选票瓜分的情况，候选者选举超时时间会被设定为随机数（该随机数要大于心跳消息时间）。

  5. 选举成功后，通过 AppendEntry RPC 的空消息表明其赢得了选举（因为仅仅只有领导者能发送 AppendEntry RPC），此外，AppendEntry RPC 还可以重置跟随者的 election timer，阻止其它人成为 candidater。

image-20220424223258364

MIT 6.824 课堂上有这样一个课堂提问，叙述如下：会存在一些因为访问路径逻辑引发的问题（比如，单向网络通信可以组织系统进行工作），例如，网络分区后领导者在少数派分区中仍然存活，心跳仍然可以对外发送，但是无法收到客户端当前请求。这样 领导者发出的心跳包会组织其它任何服务器发起新的选举。（这种情况下，入口网络发生故障了，leader 无法接受执行 client 的任何命令）

对此问题，Prof Morris 的回答是，raft 算法并不能绝对防范各种可能出现的网络问题，但一种可行的解决方式是：使用双向的心跳机制，如果超过一段时间领导者并未收到心跳包回复，领导者可以自动退化为跟随者。

RequestVote RPC 消息的内容如下：

  1. RequestVote RPC Request

    参数 解释
    term 候选者的任期号
    candidateId 请求选票的候选者的 ID
    lastLogIndex 候选者的最后日志条目的索引值
    lastLogTerm 候选者最后日志条目的任期号

  2. RequestVote RPC Respsonse

    返回值 解释
    term 当前任期号，以便于候选者去更新自己的任期号
    voteGranted 候选者拿到了投票时该字段设置为真

Log replication

日志信息中具有任期号，当前索引等信息，在 raft 算法中作用如下：

  • 日志记录了领导者按照顺序执行的操作，随后提交至状态机上，其它副本也能按照日志顺序提交至其本地状态机上，以达到顺序一致性。
  • 领导者保留日志，用于某些场景下需要重复发送命令至跟随者（例如，某些副本因为宕机错过了一段时间内的日志）。
  • 某些副本宕机后，可以从磁盘日志 replay 来重建状态。

另外，raft 维护了日志匹配特性（Log Matching Property）：

  • 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
  • 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。

领导者被成功选举后，可以开始为客户端提供服务，客户端发请求至集群中，集群的处理过程如下：

  1. 如果发送至跟随者节点，跟随着可返回当前领导者的网络位置至客户端让客户端重新发起请求，也可将客户端发送的请求重定向至领导者节点。
  2. 领导者收到客户端请求后，首先将客户端的请求写入本地日志，然后并行的发送 AppendEntries RPC 至跟随者节点，开始日志复制。
  3. 如果领导者收到一半以上来自跟随者节点的复制成功的相应后，领导者可以开始提交日志至状态机，此时的状态为已提交，成功运用到状态机上后，可以将客户端请求的执行结果发送至客户端。

image-20220510221011403

整个日志复制过程可能会出现以下问题：

  • 如果跟随者崩溃、运行缓慢或者发生了网络丢包，领导者会不断重复发送 AppendEntries RPC ，直至跟随着收到日志为止。
  • 如果跟随者崩溃后恢复，此时 raft 会执行一致性检查以保证跟随者按照顺序恢复崩溃后缺失的日志。一致性检查的过程如下：领导者发送至跟随者的 AppendEntries RPC 中填入了领导者前一条日志条目的任期号和索引号，如果跟随者未能找到相同的任期号和索引号的日志，则跟跟随者拒绝该日志，领导者收到拒绝回应后，会发送更前一个日志条目及其任期号和索引号。通过不断向前回溯，可以补齐该跟随者的缺失的日志。
  • 如果领导者在该过程中崩溃，那么部分跟随者已经收到来自崩溃领导者的日志，该崩溃的领导者也未对这些日志进行提交，但新选举出来的领导者并没有收到这部分日志，此时出现了新领导者和部分跟随者的日志不相同的情况。Raft 在这种情况下，领导者会强制跟随者复制其日志来解决日志冲突的问题（因为那部分日志并未提交至状态机）。

下图中，如果一个新的领导者当选了，其跟随者可能出现 a - e 情况：

  • a 和 b 可能因为运行缓慢或丢包，缺少了部分日志条目；

  • c 和 d 可能会有一些未被提交的日志条目

  • e 和 f 存在上述两种状况

    情况 f 可能是由以下原因造成的，某服务器在任期 2 的时候是领导人，已附加了一些日志条目到自己的日志中，但在提交之前就崩溃了；很快这个机器就被重启了，在任期 3 重新被选为领导人，并且又增加了一些日志条目到自己的日志中；在任期 2 和任期 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。

image-20220510221742713

AppendEntries RPC 消息的内容如下：

  1. AppendEntries RPC Request

    参数 解释
    term 领导者的任期
    leaderId 领导者 ID
    prevLogIndex 紧邻新日志条目之前的那个日志条目的索引
    prevLogTerm 紧邻新日志条目之前的那个日志条目的任期
    entries[] 需要被保存的日志条目（被当做心跳使用时，则日志条目内容为空；为了提高效率可能一次性发送多个）
    leaderCommit 领导者的已知已提交的最高的日志条目的索引

  2. AppendEntries RPC Response

    返回值 解释
    term 当前任期，对于领导者而言它会更新自己的任期
    success 如果跟随者所含有的条目和 prevLogIndex 以及 prevLogTerm 匹配上了，则为 true

Safety

以上的领导者选举和日志复制机制并不能保证集群中所有状态机都能以相同顺序执行指令，例如，领导者宕机后，可能会出现新 leader 出现了异常日志。为保证一致性，Raft 算法在领导者选举的时候增加了一些规则和限制因素。

Election restriction

RequestVote RPC Rqeust 消息中包含了 lastLogIndex 和 lastLogTerm，候选者将这些消息发送至跟随者请求投票时，跟随者会对比本机最后一条日志的信息和候选者的 lastLogIndex 和 lastLogTerm（先比较任期号，后比较日志索引号），如果候选者消息的日志更新，则投票，否则拒绝投票。该限制保证了新选出来的领导者包含了所有已经提交的日志条目。

Committing entries from previous terms

该问题的中文描述为：新 leader 是否可以提交之前任期内的日志条目？

在下图中：

  • a：S1 为领导者，其 [term = 2, log index = 2] 的日志项已被复制到 S2 后，S1 崩溃宕机了；
  • b：在此时，S5 超时，在任期 3 中拿到 S3 和 S4 的选票当选（因为此时 S5 的日志相比于 S3 和 S4 较新）
  • c：S5 崩溃，S1 重启并成功当选为领导者（此时 S1 可以收到来自于 S2，S3 和 S4 的选票），开始复制日志。此时 [term = 2, log index = 2] 的日志项 已被复制到大多数机器上，但并未提交。
  • d：S1 又崩溃了，S5 选举成功重新（S5 中的日志项比 S2，S3，S4 中的新），那么此后领导者在日志复制时会将索引为 2 的日志项全部复制为 [term = 3, log index = 2]。
  • e：如果情况 c 中 S1 崩溃之前将 [term = 4, log index = 3] 及之前日志项复制到大多数机器上，并提交至状态机，那么在这种情况下，如果 S1 再宕机，那么 S5 不可能选举成功（因为此时 S2 和 S3 都拥有更新任期的日志项，会拒绝投票）。

因此，Raft 算法中，新任期当选的领导者不会通过计算副本被复制的数目去提交之前任期内的日志条目；只有领导者在其当选的任期内的日志条目能通过计算副本数目时可以被提交，一旦当前任期的日志条目被提交后，由于日志匹配原则，那么之前的日志条目也会间接的被提交。

在生产系统中，为避免情况 c 到 d 覆盖已经被复制到大多数节点的日志 [term = 2, log index = 2]，会采用如下策略：一个节点当选 leader 后， 会立刻发送一个 no-operation 的 AppendEntries RPC，这使得能把之前任期内的日志都能提交。

该提交规则的依赖于 Raft 会所有日志保留原始的任期号，因此，新当选的领导者可以复制之前任期的日志。比起其它算法，Raft 算法更容易辨认出日志来自哪一任期。

image-20220511173849545

此外，还有另外一个日志提交的问题，如果领导者满足条件，可以将日志提交并应用至状态机上并返回客户端消息，那么领导者在通知跟随者提交前，领导者宕机了，那么此时日志对应的状态并未在大多数集群节点中保存下来。对于该问题， Raft 仅仅是一种底层共识算法，与客户端交互是应用层的任务，该问题可以在应用层以集群提交的方式来解决，参考两阶段提交。

Follower and candidate crashes

跟随者和候选者崩溃后，发送至他们的 RPC 请求都超时失败，Raft 中处理上述问题的方法是通过不断重试，如果崩溃机器重启了，那么 RPC 就能成功完成。由于 Raft 的 RPC 都具备幂等性，因此重试不会造成任何问题。

Timing and availability

Raft 的正确性不受时间影响，当是可用性仍需依赖于时间。Raft 的领导者选举需要满足以下时间要求：

广播时间（broadcastTime） « 选举超时时间（electionTimeout） « 平均故障间隔时间（MTBF）

随机选举超时时间需要大于广播时间，否则心跳广播还没未发送至集群中的其它服务器就会触发超时选举，这样永远也无法选举出新的领导者。

Cluster membership changes

分布式系统中往往需要变更集群配置，停机更新所有集群的配置必然会导致不可用。另外，在集群配置阶段的任一时间点，集群会被划分为两个群体，在同一时间点上，很有可能产生两个不同的领导者在同一任期内选举成功（分别依靠新配置和老配置种的机器的投票）。

image-20220513164722248

为避免集群成员变更时的发生脑裂，Raft 算法提出了联合一致性的集群成员变更方式，联合一致阶段是一个过渡阶段，在该阶段中：

  • 联合一致阶段中集群配置是老配置和新配置的结合；
  • 日志条目会被复制到新、老配置中的所有机器；
  • 新、老配置中的服务器都可以成为竞选为领导者，但其在一致性问题上（领导者选举和日志提交上）需要获得在新、老配置中的大多数的支持。

Raft 的联合一致性的集群成员变更方式如下图所示：

  1. 未变更之前，集群中的配置方式为 $C_{old}$；

  2. 集群变更之后，领导者首先将 $C_{old, new}$ （新、老配置的结合）写入日志中，并将该日志复制到新集群中，该 RPC 需要在新、老两个配置配置中都达到大多数才能算成功；

    此时如果领导者宕机，亦分为两种状况：

    • 如果 $C_{old, new}$ 未提交，领导者宕机。此时重新选举新领导者，此时的领导者选举需要满足新、老两个配置中都达到大多数选票才能当选，避免了分区脑裂。
    • 如果 $C_{old, new}$ 已提交，$C_{new}$ 并未发起，领导者宕机。此时选举出的领导者是一定具有 $C_{old, new}$ 的。

  3. 领导者发起 $C_{new}$ ，使整个集群进入新配置状态，一旦 $C_{new}$ 提交，说明集群成员变更已经完成。

    在 $C_{new}$ 提交之前，如果此时领导者发生宕机，此时的领导者选举规则如下：复制的 $C_{new}$ 节点，按照新集群配置选举，复制了 $C_{old, new}$ 的节点按照新、老两个配置选举。

image-20220513164429652

在 Raft 集群成员变更时，还需要注意以下几点：

  • 新加入的服务器可能并未存储任何日志条目，在发生成员变更前，这些节点需要复制好所有日志条目，在复制日志条目时，这些新加入的服务器时不具备投票权的。一旦完成了日志的复制，即可开始成员变更。
  • 在缩减服务器时，领导者本身可能为缩减的服务器，其提交 $C_{new}$ 后即自动退位。需要注意的时，此时该领导者节点复制日志时的大多数计数不会包括自身节点。
  • 缩减服务器时，这些需要下线的服务器可能会干扰集群的正常运行，其会向集群中发送 RequestVote RPC，导致集群进入投票选举阶段，降低集群的可用性。未避免这个问题，如果一个服务器在其超时时间内收到 RequestVote RPC，其会拒绝该投票请求。

另外，联合一致性的集群成员变更方式无疑增加了 Raft 算法实现的复杂性，在生产实践中，大多数 Raft 算法的实现采用单节点变更的方式。

Log compaction

Raft 算法持续运行时，日志将持续增长，造成内存膨胀，每次写磁盘或者重启后 replay 耗时久。为了处理这种情况，Raft 算法使用 Snapshot 机制来解决这种情况。

当日志长度达到一定时，Raft 会在日志中选择一个点（该点表示所有跟随者都已经提交日志）为程序生成快照，其后抛弃该点前的日志。如下图所示，快照中包含了以下内容：

  • 状态机状态

  • 快照中最后被包含的任期和日志索引（被快照取代的最后的日志条目在日志中的索引值，即状态机最后应用的日志）

    快照中保存 最后被包含的任期和日志索引 是用于其后日志项的一致性检查。

image-20220513172935591

通常情况下，集群中每个服务器都会独立地创建快照。但是，如果某个跟随者落后于领导者的日志项过多，则领导者会直接通过 InstallSnapShot RPC 发送快照给该跟随者，该 RPC 的具体内容如下：

  1. InstallSnapShot RPC Request

    参数 解释
    term 领导者的任期号
    leaderId 领导者的 ID，以便于跟随者重定向请求
    lastIncludedIndex 快照中包含的最后日志条目的索引值
    lastIncludedTerm 快照中包含的最后日志条目的任期号
    offset 分块在快照中的字节偏移量
    data[] 从偏移量开始的快照分块的原始字节
    done 如果这是最后一个分块则为 true

  2. InstallSnapShot RPC Respsonse

    结果 解释
    term 当前任期号（currentTerm），便于领导者更新自己

Reference

  1. In Search of an Understandable Consensus Algorithm (Extended Version) ↩︎

  2. raft-zh_cn ↩︎