技术
2024 年 3 月 9 日

崩溃容错共识算法

定义

分布式计算和有状态多副本系统中必须要面对的一个基本问题是如何在各种故障的情况下实现系统的整体可靠性。共识算法是一种在分布式系统中达成一致决定的机制，它是使得系统中的所有参与者能够就某个值或状态达成一致的协议。共识算法解决了分布式系统中的一致性问题，即如何确保系统中的所有节点对系统状态有相同的理解。在一个分布式网络中，节点可能由于网络延迟、故障或恶意攻击而无法达成一致。共识算法通过定义一套规则来保证即使在这些不确定性条件下，系统中的节点也能够就某个特定的值达成共识。共识算法的常见应用包括就哪些事务按照哪种顺序提交到数据库、状态机复制和原子性广播。

属性

共识算法通常需要具备以下几大属性：

  1. 安全性（Safety）：确保系统中的节点对数据的一致性达成共识，即便是在有恶意节点存在的情况下，系统也不应该决定出错误的值。
  2. 活跃度（Liveness）：算法应保证系统最终能够对某个值达成一致，即使面临各种合理的网络延迟和节点故障。
  3. 容错性（Fault Tolerance）：系统应该能够在一定比例的节点出现故障的情况下依然正常运行和达成共识，这包括拜占庭容错（Byzantine fault tolerance）和非拜占庭容错（非Byzantine fault tolerance，如崩溃容错）。
  4. 公平性（Fairness）：所有的参与节点应当有平等的机会参与共识进程，避免某些节点对共识过程有不正当的控制权。

崩溃容错共识算法（Crash Fault Tolerance / CFT）

崩溃容错共识算法解决的问题是在分布式系统中，当一部分进程或节点可能会因为故障而完全停止工作（即“崩溃”），但这些进程在崩溃前不会给系统发送错误或者恶意的信息。CFT算法确保即使在一些进程崩溃的情况下，系统仍然能够达成共识，并继续正常运作。换言之，CFT关注的是处理非恶意的故障（非拜占庭场景）。常见于分布式数据库，分布式计算系统中。

Paxos

论文：Paxos Made Simple

协议和算法定义

Basic Paxos（Single-Decree Paxos）

节点类型

Paxos 协议将成员划分为以下三种角色，使用 Paxos 算法的分布式系统里的，所有的节点都是平等的，它们都可以承担以上某一种或者多种的角色，不过为了便于确保有明确的多数派，决策节点的数量应该被设定为奇数个，且在系统初始化时，网络中每个节点都知道整个网络所有决策节点的数量、地址等信息。

  • Proposer 提案节点：提出对某个值进行设置操作的节点，设置值这个行为就被称之为提案（Proposal），值一旦设置成功，就是不会丢失也不可变的。请注意，Paxos 是典型的基于操作转移模型而非状态转移模型来设计的算法，这里的“设置值”不要类比成程序中变量赋值操作，应该类比成日志记录操作，在后面介绍的 Raft 算法中就直接把“提案”叫作“日志”了。同时处理所有客户端请求。
  • Acceptor 决策节点：主要作用是应答提案的节点，决定该提案是否可被投票、是否可被接受。提案一旦得到过半数决策节点的接受，即称该提案被批准（Accept），提案被批准即意味着该值不能再被更改，也不会丢失，且最终所有节点都会接受该它。
  • Learner 记录节点：不参与提案和决策，只是单纯地从提案、决策节点中学习已经达成共识的提案，譬如少数派节点从网络分区中恢复时，将会进入这种状态。
二阶段提交

Paxos 算法包括两个阶段，其中第一阶段“准备”（Prepare），如果某个提案节点准备发起提案，必须先向所有的决策节点广播一个许可申请（称为 Prepare 请求）。提案节点的 Prepare 请求中会附带一个全局唯一的数字 n 作为提案 ID，决策节点收到后，将会给予提案节点两个承诺与一个应答。

两个承诺是指：

  • 承诺不会再接受提案 ID 小于或等于 n 的 Prepare 请求。
  • 承诺不会再接受提案 ID 小于 n 的 Accept 请求。

一个应答是指：

  • 不违背以前作出的承诺的前提下，回复已经批准过的提案中 ID 最大的那个提案所设定的值和提案 ID，如果该值从来没有被任何提案设定过，则返回空值。如果违反此前做出的承诺，即收到的提案 ID 并不是决策节点收到过的最大的，那允许直接对此 Prepare 请求不予理会。

当提案节点收到了多数派决策节点的应答（称为 Promise 应答）后，可以开始第二阶段“批准”（Accept）过程，这时有如下两种可能的结果：

  • 如果提案节点发现所有响应的决策节点此前都没有批准过该值（即为空），那说明它是第一个设置值的节点，可以随意地决定要设定的值，将自己选定的值与提案 ID，构成一个二元组“(id, value)”，再次广播给全部的决策节点（称为 Accept 请求）。
  • 如果提案节点发现响应的决策节点中，已经有至少一个节点的应答中包含有值了，那它就不能够随意取值了，必须无条件地从应答中找出提案 ID 最大的那个值并接受，构成一个二元组“(id, maxAcceptValue)”，再次广播给全部的决策节点（称为 Accept 请求）。

当每一个决策节点收到 Accept 请求时，都会在不违背以前作出的承诺的前提下，接收并持久化对当前提案 ID 和提案附带的值。如果违反此前做出的承诺，即收到的提案 ID 并不是决策节点收到过的最大的，那允许直接对此 Accept 请求不予理会。

工作实例

假设一个分布式系统有五个节点，分别命名为 S(1)、S(2)、S(3)、S(4)、S(5)，这个例子中只讨论正常通信的场景，不涉及网络分区。全部节点都同时扮演着提案节点和决策节点的身份。此时，有两个并发的请求分别希望将同一个值分别设定为 X（由 S(1)作为提案节点提出）和 Y（由 S(5)作为提案节点提出），以 P 代表准备阶段，以 A 代表批准阶段，这时候可能发生以下情况：

  • 情况一：譬如，S(1)选定的提案 ID 是 3.1（全局唯一 ID 加上节点编号），先取得了多数派决策节点的 Promise 和 Accepted 应答，此时 S(5)选定提案 ID 是 4.5，发起 Prepare 请求，收到的多数派应答中至少会包含 1 个此前应答过 S(1)的决策节点，假设是 S(3)，那么 S(3)提供的 Promise 中必将包含 S(1)已设定好的值 X，S(5)就必须无条件地用 X 代替 Y 作为自己提案的值，由此整个系统对“取值为 X”这个事实达成一致。
  • 情况二：事实上，对于情况一，X 被选定为最终值是必然结果，但从图 6-2 中可以看出，X 被选定为最终值并不是必定需要多数派的共同批准，只取决于 S(5)提案时 Promise 应答中是否已包含了批准过 X 的决策节点，S(5)发起提案的 Prepare 请求时，X 并未获得多数派批准，但由于 S(3)已经批准的关系，最终共识的结果仍然是 X。
  • 情况三：当然，另外一种可能的结果是 S(5)提案时 Promise 应答中并未包含批准过 X 的决策节点，譬如应答 S(5)提案时，节点 S(1)已经批准了 X，节点 S(2)、S(3)未批准但返回了 Promise 应答，此时 S(5)以更大的提案 ID 获得了 S(3)、S(4)、S(5)的 Promise，这三个节点均未批准过任何值，那么 S(3)将不会再接收来自 S(1)的 Accept 请求，因为它的提案 ID 已经不是最大的了，这三个节点将批准 Y 的取值，整个系统最终会对“取值为 Y”达成一致。
  • 情况四：从情况三可以推导出另一种极端的情况，如果两个提案节点交替使用更大的提案 ID 使得准备阶段成功，但是批准阶段失败的话，这个过程理论上可以无限持续下去，形成活锁（Live Lock）。
总结

Basic Paxos 的价值在于开拓了分布式共识算法的发展思路，但它因有诸多细节没有进行明确的定义，可能在实现过程中导致如下缺陷，一般不会直接用于实践：

  • Basic Paxos 只能对单个值形成决议，并且决议的形成至少需要两次网络请求和应答（准备和批准阶段各一次），高并发情况下将产生较大的网络开销。
  • 极端情况下两个提案节点互不相让地争相提出自己的提案，抢占同一个值的修改权限，形成活锁。
  • 提案的最终结果只有部分 Acceptor 知道。这就无法保证每个实例的复制状态机都有完全一致的日志。

总之，Basic Paxos 是一种很学术化但对工业化并不友好的算法，现在几乎只用来做理论研究，而实际的应用是基于 Multi Paxos 和 Fast Paxos 算法。

Multi Paxos

Multi Paxos 对 Basic Paxos 的核心改进是增加了选举的过程，提案节点会通过定时轮询（心跳），确定当前网络中的所有节点里是否存在有一个主提案节点。一旦没有发现主节点存在，节点就会在心跳超时后使用 Basic Paxos 中定义的准备、批准的两轮网络交互过程，向所有其他节点广播自己希望竞选 Proposer 的请求，希望整个分布式系统对这件事情协商达成一致共识，如果得到了决策节点中多数派的批准，则选举成功。当选举完成之后，除非主节点故障发起重新竞选，否则从此往后，就只有 Proposer 本身才能够提出提案。此时，无论哪个提案节点接收到客户端的操作请求，都会将请求转发给 Proposer 来完成提案，而 Proposer 提案的时候，也就无需再次经过准备过程，因为可以视作是经过选举时的那一次准备之后，后续的提案都是对相同提案 ID 的一连串的批准过程。也可以通俗理解为选举过后，就不会再有其他节点与它竞争，相当于是处于无并发的环境当中进行的有序操作，所以此时系统中要对某个值达成一致，只需要进行一次批准的交互即可。避免了同时存在多个 Proposer 导致的提案竞争。

同时 Accept 请求中 Proposer 增加一个提案索引，这个编号必须是严格单调递增的，以应付 Proposer 故障或陷入网络分区后重新恢复，例如：网络分区后另外一部分节点仍然有多数派，且已经完成了重新选主的情况，此时必须以任期编号大的主节点为准。此外，Multi-Paxos 为每个服务器添加了一个 firstUnchosenIndex，可以让 Proposer 知道 Acceptor 所缺失的记录，并同步到每个 Acceptor。

Raft

论文：In Search of an Understandable Consensus Algorithm (Extended Version)

可视化：The Secret Lives of Data

研究背景

Raft 对比主流共识算法的创新点（Section 1）

  • 强领导：Raft 使用强领导形式。例如，日志条目仅从 Leader 流向其他服务器。这简化了复制日志的管理，并使 Raft 更容易理解。在 Leader 没有故障的情况下心跳包会避免其他实例发起新一轮的选举。
  • 领导人选举：Raft 使用随机定时器来触发选举。这仅仅在共识算法原有的心跳机制上进行了少量的适配，简单快速地解决了冲突。（避免定时器同时到期导致所有候选成员同时变为 Candidate 分票导致的选举失败）
  • 成员变更：Raft 采用了一种新的联合共识方法解决了集群变更过程中不同配置实例共存的问题，这允许集群在配置变更期间仍然可以正常运行。

Paxos 存在的问题 (Section 3)

在Raft论文中，作者提出Paxos协议的两大缺点主要是：

  1. 难以理解：Paxos 协议被普遍认为难以理解。学术界和工业界都认为 Paxos 的算法细节非常抽象并难以把握，这给想要实现或教学 Paxos 协议的人带来了困难。
  2. 难以实现：论文中还提到 Paxos 协议论文中对其部分细节的省略和隐晦的描述导致它很难正确实现。业界认为 Paxos 算法的描述与实际系统的需求之间存在显著差距。因此想完全实现 Paxos 协议并在其基础之上构建高可用系统变得极具挑战性。

因此，Raft协议的设计目标之一就是降低这种复杂性，让共识算法变得更加直观和易于理解，从而更轻松地被实现和维护。

协议和算法定义

角色变换

Raft 协议将成员划分为以下四种角色，在特定情况下进行转换。

  • Leader：处理所有客户请求（如果 Client 首先握手 Follower，Follower 会将其请求转发给 Leader）。向 Follower 发送心跳维持 Leadership。同步日志给所有 Follower。Raft 保证在给定的任意任期，有且仅有一个 Leader。
  • Follower：被动角色，不处理任何外部请求。响应 Leader 的心跳和日志同步请求，提交 Leader 同步的日志。响应 Cadidate 的投票请求，以便选举出新的 Leader（每个节点仅有一票）。
  • Candidate：当出现 Leader 出现崩溃，或网络分区导致 Leader 无法接收大多数 Follower 的心跳响应时，同时在随机超时计时器的作用下，一般情况下剩余节点中一个或多个 Follower 会首先超时并发起选举（不排除同时过期出现 Split Vote 的情况，该情况下会重新进行选举），角色从 Follower 转换为 Candidate。在收到剩余大多数节点的投票后，竞选成功变为新的 Leader。如果期间收到来自另一个竞选成功节点发来的心跳且任期号大于等于自身的任期号，则转换为 Follower，否则维持 Candidate 身份继续选举。
  • Learner：新加入的成员初始时没有任何数据，因此需要从 Leader 节点拉取大量日志，直至追上 Leader 节点的日志点位。这样一来，Leader 节点的网络更有可能变得过载，导致阻塞或丢弃发往 Follower 节点的心跳包。在这种情况下，Follower 可能因为长时间没收到心跳包而发起新的 Leader 选举。也就是说，拥有新成员的集群更容易受到 Leader 选举机制的影响。Leader 选举以及向新成员传播更新都有可能导致集群不可用。为了解决上述问题，后续论文补充了 Learner 角色。该角色在未更新到 Leader 日志临近点位前，不参与选举机制。完成同步后会通过升级机制，变成 Follower。

任期

Raft 将时间划分为任意长度的任期。任期用连续的整数编号。每个任期以选举开始，在选举中，一个或多个 Cadidate 试图成为 Leader。如果一名 Cadidate 在选举中获胜，那么他将在任期的剩余时间内担任 Leader。Raft 会确保在给定的任期内最多只有一个 Leader。不同的服务器可能会在不同的时间观察到任期之间的转换，在某些情况下，服务器可能不会察觉到选举，甚至察觉不到整个任期更替。在 Raft 中，任期就像一个逻辑时钟，它允许c成员检测过时的信息，如历史任期的 Leader 。每个服务器都会存储一个当前任期的编号，该编号会随着时间的推移单调增加。每当服务器进行通信时，就会交换当前项；如果一个服务器的当前项小于另一个服务器的当前项，那么它就会将自己的当前项更新为较大的值。如果 Cadidate 或 Leader 发现自己的任期落后，就会立即恢复到 Follower 状态。如果一个服务器收到一个来自过时的任期的请求，它就会拒绝该请求。

RPC 类型

AppendEntries RPC
  • 作用：心跳，日志同步，一致性检查
  • 携带参数：
    • term：当前 Leader 的任期号。
    • leaderId：指示当前的 Leader，以便 Follower 重定向客户端请求。
    • prevLogIndex： 新日志条目之前的最后 LogIndex。
    • prevLogTerm：prevLogIndex 条目所在的任期。
    • entries：所需存储的日志（可能为空，用作心跳；可能有多条，减少 RTT 优化效率）。
    • leaderCommit：Leader 提交的点位。
  • 返回结果：
    • term：Follower 所记录的当前任期。
    • success：如果 Follower 存储的日志中包含 prevLogIndex 和 prevLogTerm 对应的条目，则返回成功。
  • 接收者行为：
    • 如果接收到的任期小于所记录的任期，则返回失败
    • 如果 Follower 存储的日志中不包含 prevLogIndex 和 prevLogTerm 对应的条目，返回失败。
    • 如果 Follower 存储的日志中包含对应 prevLogIndex 的日志但日志所记录的任期不同，则删除所持有的冲突日志及其后续日志。
    • 存储所有接收到但未保存的日志条目
    • 如果 leaderCommit 大于所记录的 commitIndex，则将 commitIndex 设置为 min(leaderCommit, lastIndexOfNewEntries)
RequestVote RPC
  • 作用：Cadidate 投票请求
  • 携带参数：
    • term： Candidate 的任期
    • candidateId：请求投票的 candidateId
    • lastLogIndex：Cadidate 所持有的最新日志的序号
    • lastLogTerm：Cadidate 所持有的最新日志的任期
  • 返回结果：
    • term：Follower 所记录的当前任期。
    • voteGranted：是否投出宝贵的一票
  • 接收者行为：
    • 如果接收到的任期小于所记录的任期，则返回失败
    • 如果 Follower 没有为其他 Candidate 投票（即 Follower 自身记录的 votedFor 为空），同时发送请求的 Candidate 的日志与所持有的日志点位持平或更新，则进行投票。
    • 没有发生选举超时前，忽略接收到的 RequestVote RPC
InstallSnapshot RPC
  • 作用：快照同步
  • 携带参数：
    • term：当前 Leader 的任期号。
    • leaderId：指示当前的 Leader，以便 Follower 重定向客户端请求。
    • lastIncludedIndex：快照会替换包括该索引在内的所有条目。
    • lastIncludedTerm：lastIncludedIndex 条目所在的任期。
    • offset：数据块在快照文件中位置的字节偏移量
    • data: 快照块的原始字节，offset 为起始偏移量
    • done：指示是否为最后一个数据块
  • 返回结果：
    • term：Follower 所记录的当前任期。
  • 接收者行为：
    • 如果接收到的任期小于所记录的任期，则立即返回
    • 如果接收到的起始 offset 是 0，则创建一个新的快照文件
    • 将 data 写入到文件中由 offset 指定的偏移量位置之后
    • 如果 done 为 false，则回复并继续等待剩余的数据块
    • 保存快照文件，丢弃所有所记录的日志 index 比新保存的快照文件更小的快照
    • 如果所持有的日志已经包含了快照同步请求中的条目，则保留快照文件并直接返回。否则丢弃所有日志记录，从快照恢复内容和配置。

Leader 选举

选举触发

Raft 使用一种心跳机制来触发 Leader 选举。

  1. 节点启动时是 Follower 状态；只要能持续从 Leader 或 candidate 收到合法的 RPC 请求，就会一直保持在 follower 状态；
  2. Leaders 定期发送心跳给（空的 AppendEntries 消息）所有的 Follower，抑制其他 Follower 发起选举；
  3. 如果一个 Follower 在选举超时时间内都没有收到来自 Leader/Cadidate 的通信，就认为当前已经没有有效 Leader 了，然后发起一次选举。
选举流程
  1. 增大自身记录的任期号，转换为 Candidate 身份
  2. 为自己的 Leader 选举投票（Candidate 自动获得自己一票），并向集群内其他节点发送 RequestVote RPC。
  3. 等待其他节点投票结束
选举结果
  1. Candidate 获得了集群大多数节点针对同一任期（term）的投票，选举成功成为 Leader
  2. 集群内其他 Candidate 获得了集群大多数节点针对同一任期（term）的投票，选举成功成为 Leader。其余 Candidate 收到 Leader 的 AppendEntries RPC 后，且该消息包含的任期大于等于自身所记录的任期是，则承认当前 Leader，退回 Follower 身份。否则保持 Candidate 身份。
  3. 选举超时，多个 Candidate 分票导致没有 Candidate 获得集群大多数节点针对同一任期（term）的投票，选举超时失败。等待下次选举。

日志复制机制

  1. 当 Leader 被选举出来后，它开始处理客户端请求。每个客户端请求都包含一个要由复制状态机执行的命令。Leader 将命令作为新条目附加到其日志中，然后并行向其他服务器发出 AppendEntries RPC 以复制该条目。当条目安全复制后（如下所述），Leader 将该条目应用于其状态机并将执行结果返回给客户端。如果 Follower 崩溃或运行缓慢，或者网络数据包丢失，Leader 将无限期地重试AppendEntries RPC（即使在回应客户端之后），直到所有 Follower 最终存储所有日志条目为止。
  2. Leader 决定何时将日志条目应用于状态机；这样的条目称为已提交。Raft 保证提交的条目是持久的，并且最终将由所有可用的状态机执行。一旦创建条目的 Leader 在大多数服务器上复制了该条目，该条目就被提交了。这也提交了 Leader 日志中的所有先前条目，包括由前任 Leader 创建的条目。Leader 跟踪其已知的最高提交索引，并将该索引包含在未来的AppendEntries RPC中（包括心跳），以便其他服务器最终得知。一旦 Follower 得知日志条目已提交，它就会将该条目按日志顺序应用于其本地状态机。
  3. Raft的日志复制机制旨在保持不同服务器上的日志之间的高度一致性。这不仅简化了系统的行为，使其更可预测，而且是确保安全性的重要组成部分。Raft维护以下属性，这些属性共同构成日志匹配属性：
    1. 如果不同日志中的两个条目具有相同的索引和任期，则它们存储相同的命令。
    2. 如果不同日志中的两个条目具有相同的索引和任期，则这些日志在所有先前的条目中都是相同的。
  4. 在正常操作期间， Leader 和 Follower 的日志保持一致，因此 AppendEntries 一致性检查永远不会失败。然而，Leader 崩溃可能会导致日志不一致（旧 Leader 可能没有完全复制其日志中的所有条目）。这些不一致性可能会在一系列 Leader 和 Follower 崩溃中累积。Follower 可能缺少 Leader 存在的条目，可能有 Leader 不存在的额外条目，或两者兼而有之。日志中缺失和多余的条目可能跨越多个任期。
  5. 为了使 Follower 的日志与自己的日志一致，Leader 必须找到两个日志在最新条目上达成一致的地方，删除 Follower 日志中该点之后的任何条目，并向 Follower 发送该点之后 Leader 的所有条目。所有这些操作都是响应 AppendEntries RPC 执行的一致性检查而发生的。 Leader 为每个 Follower 维护一个 nextIndex，这是 Leader 将发送给该 Follower 的下一个日志条目的索引。当 Leader 首次掌权时，它将所有nextIndex值初始化为其日志中最后一个条目之后的索引。如果 Follower 的日志与 Leader 的日志不一致，那么在下一个 AppendEntries RPC 中，一致性检查将失败。在拒绝后， Leader 递减 nextIndex 并重 AppendEntries RPC。最终，nextIndex 将达到 Leader 和 Follower 日志匹配的点。当这种情况发生时，AppendEntries 将成功，这将删除 Follower 日志中的任何冲突条目，并附加 Leader 日志中的条目（如果有）。一旦 AppendEntries 成功， Follower 的日志就与 Leader 的日志一致，并且在该任期的剩余时间里将保持这种状态。
  6. 有了这种机制， Leader 在选举成功后不需要采取任何特殊行动来恢复日志一致性。它只是开始正常操作，日志会自动响应 AppendEntries 一致性检查的失败而收敛。 Leader 永远不会覆盖或删除其自己日志中的条目（Leader 仅追加属性）。
  7. 综上所述，这种日志复制机制展现了理想共识属性：只要多数服务器正常运行，Raft就 可以接受、复制和应用新的日志条目；在正常情况下，一个新条目可以通过向多数集群成员发送一轮RPC 来复制；一个较慢的 Follower 不会影响性能。

日志一致性保障

  1. 包含所有已提交日志的节点才能被选为 Leader
  2. Leader 只有在当前任期且日志条目复制副本数量过半，日志条目才能提交。
  3. Raft 处理 Follower/Candidate 故障的方式是无限重试，且由于 Raft RPC 是幂等的（如果一个 Follower 收到了一个 AppendEntries 请求，而它所记录的日志中已经包含了对应条目， 会直接忽略该请求），所以不会因为无限重试引发其他问题。
  4. 广播耗时要比选举超时低一个数量级，Leader 能可靠地发送心跳消息给 Follower，抑制新选举频繁发起。选举超时要比单节点平均故障间隔时间低几个数量级，这样系统能稳步前进。 当 leader 挂掉后，系统仅会经历一个选举超时时间不可用。

节点扩容和配置切换

问题的本质就是在于增删节点期间同时出现两个及以上 Leader。不管用什么方式，我们都无法在同一时刻原子地切换所有节点。因此在变更时，集群可能会分裂为两个独立的大多数 。

Raft 通过两阶段提交机制，结合日志复制机制，首先让集群切换到过渡性配置（又称联合共识）。随后联合共识提交后，集群配置将会过渡到新配置。其中联合共识同时包含新老配置，但无论新老配置，日志仍将被复制到所有的节点，任何节点都能成为 Leader，同时选举或提交仍需要大多数节点同意。

配置变更的过程如图所示，Leader 首先在自己的 log 中创建一个联合共识配置项 C(old,new) 并提交；这个配置会被集群大多数节点接受；然后创建一个 C(new) 并提交到大多数节点，新配置提交后，所有节点都会使用新配置进行决策。如果 Leader 发生故障，使用 C(old) 或 C(old,new) 配置的节点们可能会选出一个新 leader， 取决于获胜的那个 Candidate 是否收到并提交了 C(old,new)。 但不管哪种情况下，此时（这个时间段内）C(new) 都无法做出单边决策。C(old,new) 提交之后，除非有其他节点的同意，否则 C(old) 或 C(new) 都无法做出决策， 并且 Leader 完整性属性确保了只有那些有 C(old,new) 日志的节点才能被选为 Leader。以此保证了节点扩容和配置切换过程的安全性。

日志压缩

解决随时间推移导致日志膨胀，日志重放变慢，可用性降低的问题。论文中给出了两种实现方法。

快照

将日志内已提交的条目写入快照，持久化到存储中。一旦服务器完成了快照的写入，它可以删除最后包含的索引中的所有日志条目，以及先前的快照。

Compaction

Compaction 方式也是可行的。 这些只对一部分数据进行操作，因此压缩所占用的负载是随时间分布更加均匀。首先选择一块已经积累了一些已删除和已覆盖对象的数据区域。然后以更紧凑的方式，重写这些区域内仍活跃的对象。这比快照方式要更精细但也更复杂，需要对 Raft 的状态机数据结构进行修改，比如使用 LSM Tree。

客户端交互

寻找 Leader

Raft 中，客户端会将所有请求都发给 Leader。客户端启动时，首先会随机选择一个 raft 节点进行连接，

  • 如果该节点是 Leader，就会直接处理请求；
  • 如果该节点不是 Leader，就会拒绝这个请求，并将 Leader 信息告诉客户端。
  • 如果 Leader 故障，客户端请求会超时，然后重新随机选择一个节点进行连接。
可线性化语义

Raft 的目标之一是实现可线性化语义，让每个操作看起来都是立即执行且精确执行一次。 但前面也提到，Raft 可能会多次执行同一条命令：例如，Leader 在提交了来自客户端的日志条目但还没返回响应时就发生故障，那客户端会向新 Leader 重试这条命令，导致命令重复执行。Raft 通过一下机制解决上述问题

  1. 给客户端的每个命令分配唯一的顺序编号。
  2. 状态机为每个客户端记录最后已执行的命令序号，放到响应中。
  3. 状态机如果发现某个序号的命令已经执行过，就会直接返回，不会再执行一遍。

扩展

ZAB（Zookeeper Atomic Boardcast） 协议

论文：Zab: High-performance broadcast for primary-backup systems

ZAB（ZooKeeper Atomic Boardcast）是 ZooKeeper 中使用的共识协议。ZAB 是 Zookeeper 的专用协议。它与 Zookeeper 紧密绑定，尚未被提取到独立的数据库中。因此，ZAB 并未得到广泛应用，仅局限于 Zookeeper。不过，有关 ZAB 协议的论文充分证明，ZAB 有能力满足强一致性要求。ZAB 的核心逻辑和 Multi-Paxos 类似。

核心概念
  • 节点类型：Leader / Follower
  • ZXID：ZXID 作为 ZooKeeper 最核心的一个概念，唯一标识一个 Transaction，即 Proposal 表示为 <value,ZXID>。为了保证顺序性，ZXID 必须单调递增,因此全局唯一递增的64位正整数,所以 ZXID 又由

<epoch,count> 构造。其中 epoch 是 ZXID 的高32位,指的是每个 Leader 生命周期的一个标识，简单来说就是任期。每次选出新的 Leader，epoch 就加一。count 是低 32 位，标识一个 epoch 期间每个 Transaction ID，每个 epoch 的 count 都会从 0 开始

递增。

算法描述

整个ZAB协议一共定义了三个阶段：

  • 发现：要求 Zookeeper 集群必须选举出一个 Leader 进程，同时 Leader 会维护一个 Follower 可用客户端列表。将来客户端可以和这些 Follower节点进行通信。
  • 同步：Leader 要负责将本身的数据与 Follower 完成同步，做到多副本存储。这样也是体现了CAP 中的高可用和分区容错。Follower 将队列中未处理完的请求消费完成后，写入本地事务日志中
  • 广播：Leader 可以接受客户端新的事务Proposal请求，将新的Proposal请求广播给所有的 Follower。
工作模式
崩溃恢复（选举 - 发现 - 同步）

一旦 Leader 服务器出现崩溃或者由于网络原因导致 Leader 服务器失去了与过半 Follower 的联系，那么就会进入崩溃恢复模式。

前面我们说过，崩溃恢复具有两个阶段：Leader 选举与初始化同步。当完成 Leader 选举后，此时的 Leader 还是一个准 Leader，其要经过初始化同步后才能变为真正的 Leader。

  • 发现过程具体如下：
    • Follower 向准 Leader 发送一个 FOLLOWERINFO 类型消息,将自己的信息上报给准 Leader,该
    • 信息包括自己的epoch内容 F.acceptedEpoch。
    • Leader 等待收到过半的 FOLLOWERINFO 消息后,从这些 Follower 节点的 acceptedEpoch 中取
    • 出最大的 epoch 并加 1，即 newEpoch=max{F.acceptedEptedEpoch}+1，再将新的 epoch 信息
    • NEWEPOCH 发给集群中的节点。
    • Follower 收到 NEWEPOCH 后,将新的 epoch 与自己的 epoch 比较，如新 epoch > acceptedEpoch，即更新自己的 acceptedEpoch 为新 epoch，然后给 Leader 发送一个 ACKEPOCH 信息，该信息包括上个 epoch、history 和 lastZXID；如新 epoch < acceptedEpoch，则回退到阶段 0。
    • Leader 收到所有 Follower 的 ACKEPOCH 后，从中找出 currentEpoch 最大的或者 lastZXID 最大的 Follower，把该 Follower 的 history 作为同步的 history。
  • 同步过程具体如下：
    • Leader 给所有 Follower 发一个 NEWLEADER 类型消息，把最新的 epoch 和 histroy 一起携带。
    • Follower 收到 NEWLEADER 消息后，判断自己的 acceptedEpoch 和新 epoch是否相等。如果相等则表示自己已经跟上了新 epoch，那么更新自己的 currentEpoch 为新 epoch，表示进入新的 epoch。同时按照 ZXID 的大小逐一进行本地 proposed (此时这些 Transaction 还未提交)，然后更新 history，返回一个 ACKNEWLEADER 消息表表示已经同步完数据。如果不相等，那么重新进入新一轮崩溃恢复。
    • Leader 收到集群中节点的 ACKNEWLEADER 后，对 history 中的这些 Proposal 进行提交，即向所有 Follower 发送提交请求。
    • Follower 收到 Leader 对 history 的 COMMIT 消息后,对于已经 Proposed，但还未提交的事务按 ZXID 顺序进行提交。
  • 恢复模式的两个原则：
    • 已被处理过的消息不能丢：当 Leader 收到超过半数 Follower 的 ACKs 后，就向各个 Follower 广播 COMMIT 消息， 批准各个 Server 执行该写操作事务。当各个 Server 在接收到 Leader 的 COMMIT 消息后就会在本地执行该写操作，然后会向客户端响应写操作成功。但是如果在非全部 Follower 收到 COMMIT 消息之前 Leader 就挂了，这将导致一种后 果：部分 Server 已经执行了该事务，而部分 Server 尚未收到 COMMIT 消息，所以其并没有 执行该事务。当新的 Leader 被选举出，集群经过恢复模式后需要保证所有 Server 上都执行 了那些已经被部分 Server 执行过的事务。
    • 被丢弃的消息不能再现：当在 Leader 新事务已经通过，其已经将该事务更新到了本地，但所有 Follower 还都没 有收到 COMMIT 之前，Leader 宕机了（比前面叙述的宕机更早），此时，所有 Follower 根本 就不知道该 Proposal 的存在。当新的 Leader 选举出来，整个集群进入正常服务状态后，之 前挂了的 Leader 主机重新启动并注册成为了 Follower。若那个别人根本不知道的 Proposal 还保留在那个主机，那么其数据就会比其它主机多出了内容，导致整个系统状态的不一致。 所以，该 Proposa 应该被丢弃。类似这样应该被丢弃的事务，是不能再次出现在集群中的， 应该被清除。
原子广播

Leader 处理事务请求的过程如下：

  1. Leader 接收到事务请求后，为事务赋予一个全局唯一的 64 位自增 id，即 ZXID，通过 ZXID 的大小比较即可实现事务的有序性管理，然后将事务封装为一个 Proposal。
  2. Leader 根据 Follower 列表获取到所有 Follower，然后再将 Proposal 通过这些 Follower 的 队列将提案发送给各个 Follower。
  3. 当 Follower 接收到提案后，会先将提案的 ZXID 与本地记录的事务日志中的最大的 ZXID 进行比较。若当前提案的 ZXID 大于最大 ZXID，则将当前提案记录到本地事务日志中，并向 Leader 返回一个 ACK。
  4. 当 Leader 接收到过半的 ACKs 后，Leader 就会向所有 Follower 的队列发送 COMMIT 消息，向所有 Learner 的队列发送 Proposal
  5. 当 Follower 收到 COMMIT 消息后，就会将日志中的事务正式更新到本地。当 Learner 收到 Proposal 后，会直接将事务更新到本地。
  6. 无论是 Follower 还是 Learner，在同步完成后都需要向 Leader 发送成功 ACK。

Gossip 协议

Gossip 协议是一种去中心化的点对点通信技术，用于在庞大的分布式系统中传输消息。Gossip 协议的核心逻辑是，每个节点定期向其他一些随机选定的节点发送消息。最终，整个系统都将有很高的概率接收到特定的消息。用通俗的话来说，Gossip 协议是一种技术，通过有限的局部互动，分布式系统参与者可以构建一个全局视图。也正因如此，Gossip 协议即使在部分参与者出现网络分区的情况下，也能将信息同步到所有参与者。

Gossip 协议被应用在 Apache Cassandra, Consul, Redis Cluster, BlockChain 等主流技术中，因此，Gossip 协议容易和上述的 CFT 算法混淆。

然而 Gossip 协议并不是一种共识算法，而是一种网络通讯协议。尽管 Gossip 协议可以帮助分布式系统中的节点更新和同步信息，但它并不保证所有节点最终能达成一致的决定，这才是共识算法的主要目标。共识算法如 Paxos、Raft 是专门设计来确保分布式系统中的一致性协议。

然而，Gossip 协议有时可以与共识算法结合使用，作为信息传播的一部分，帮助实现共识过程或者达成最终一致性。但它本身并不解决如何在所有节点间达成一致决策的问题。

参考文献

  1. Paxos Made Simple - Leslie Lamport
  2. Paxos Made Practical - David Mazi`eres
  3. Implementing Replicated Logs with Paxos - John Ousterhout and Diego Ongaro
  4. In Search of an Understandable Consensus Algorithm (Extended Version) - John Ousterhout and Diego Ongaro