原文地址：https://www.thebyte.com.cn/consensus/consensus.html

我是买的纸质书学习的，记录笔记时发现web端的内容其实挺全面的，下方内容大部分摘录自web端页面。

什么是共识

“共识”和“一致”意思相似，但在计算机领域，它们具有截然不同的含义。

• 共识（Consensus）：指所有节点就某项操作（如选主、原子事务提交、日志复制、分布式锁管理等）达成一致的实现过程。

• 一致性（Consistency）：描述多个节点的数据是否保持一致，关注数据最终达到稳定状态的结果。

在分布式系统中，节点故障是不可避免的，但部分节点故障不应该影响系统整体状态。通过增加节点数量，依据“少数服从多数”原则，只要多数节点（至少N/2+1）达成一致，其状态即可代表整个系统。这种依赖多数节点实现容错的机制称为 Quorum 机制。

基于 Quorum 的机制，通过“少数服从多数”协商机制达成一致的决策，从而对外表现为一致的运行结果。这一过程被称为节点间的“协商共识”。一旦解决共识问题，便可提供一套屏蔽内部复杂性的抽象机制，为应用层提供一致性保证，满足多种需求。

• 主节点选举：在主从复制数据库中，所有节点需要就“谁来当主节点”达成一致。如果由于网络问题导致节点间无法通信，很容易引发争议。若争议未解决，可能会出现多个节点同时认为自己是主节点的情况，这就是分布式系统中最棘手的问题之一 —— “脑裂”。

• 原子事务提交：对于支持跨节点或跨分区事务的数据库，可能会发生部分节点事务成功、部分节点事务失败的情况。为维护事务的原子性（即 ACID 特性），所有节点必须就事务的最终结果达成一致。

• 分布式锁管理：当多个请求尝试访问共享资源时，共识机制可确保所有节点一致认定“谁成功获取了锁”。即使发生网络故障或节点异常，也能避免锁争议，从而防止并发冲突或数据不一致。

• 日志复制：日志复制指将主节点的操作日志同步到从节点。在这一过程中，所有节点必须确保日志条目的顺序一致，即日志条目必须以相同顺序写入。

日志与复制状态机

日志是有序且持久化的记录序列。新记录会从末尾追加，而读取时则按“从左到右”的顺序进行扫描。结构如下：

有序的日志记录了“何时发生了什么”，这一点可以通过以下两种数据复制模型来理解。

• 主备模型（Primary-backup）：又称 状态转移 模型，主节点（Master）负责执行如“+1”、“-2”的操作，将 操作结果 （如“1”、“3”、“6”）记录到日志中，备节点（Slave）根据日志直接同步结果。

• 复制状态机模型（State-Machine Replication）：又称 操作转移 模型，日志记录的不是最终结果，而是具体的 操作指令 ，如“+1”、“-2”。指令按照顺序被依次复制到各个节点（Peer）。如果每个节点按顺序执行这些指令，各个节点最终将达到一致的状态。

无论哪一种模型，它们都揭示了：“顺序是节点之间保持一致性的关键因素”。如果打乱了操作的顺序，就会得到不同的运算结果。

复制状态机的基本原理

两个“相同的” (identical)、“确定的” (deterministic) 进程：

• 相同的：进程的代码、逻辑、以及配置完全一致，它们在设计和实现上完全相同；
• 确定的：进程的行为是完全可预测的，不能有任何非确定性的逻辑，比如随机数生成或不受控制的时间依赖。

如果它们以相同的状态启动，按相同的顺序获取相同的输入。那么，它们一定会达到相同的状态。

节点内的进程按 顺序 执行日志序列，操作具有全局顺序。因此，所有节点 最终将达到一致 的状态。多个这样的进程结合有序日志，就构成了 Apache Kafka、Zookeeper、etcd、CockroachDB 等分布式系统中的关键组件。

Paxos算法

算法背景

在 Paxos 算法中，节点分为三种角色。

• 提议者（Proposer）：提议者是启动共识过程的节点，它提出一个值，请求其他节点对这个值进行投票，提出值的行为称为发起“提案"（Proposal），提案包含提案编号 (Proposal ID) 和提议的值 (Value)。注意的是，Paxos 算法是一个典型的为 操作转移 模型设计的算法，为简化表述，本文把提案类比成 变量赋值 操作，但你应该理解它是 操作日志 相似的概念，后面介绍的 Raft 算法中，直接就把“提案”称做“日志”了。

• 决策者（Acceptor）：接受或拒绝提议者发起的提案，如果一个提案被超过半数的决策者接受，意味着提案被“批准”（accepted）。提案一旦被批准，意味着在所有节点中达到共识，便不可改变、永久生效。

• 记录者（Learner）：记录者不发起提案，也不参与决策提案，它们学习、记录被批准的提案。

在 Paxos 算法中，所有节点都是平等的，能够承担一种或多种角色。例如，提议者既可以发起提案，也可以对其他提案进行表决。但为了更明确地计算 Quorum，通常建议表决提案的节点数为奇数。

Paxos 算法描述

简而言之，Paxos 算法本质是一个支持多次重复的 二阶段提交 协议。

Paxos 算法的第一个阶段称 准备阶段（Prepare）。提议者选择一个提案编号 N（通常是单调递增的数字，相当于乐观锁中的 version，更高的编号意味着更高的优先级），向所有的决策者广播许可申请（称为 Prepare(N) 请求），如果决策者：

• 尚未承诺 ≥N 编号的提案：则“承诺”（promise）不再接受任何编号小于 N 的提案，返回一个响应，其中包含承诺的提案编号以及对应的提案值（如果有）；

• 已承诺 ≥N 编号的提案：拒绝 Prepare 请求，不返回任何响应。

提议者从多数决策者获得了“承诺”（Promise），则“准备阶段”达成。接着，决策者选择提案值：如果决策者的响应中返回了提案值，从中选择 编号最高 的提案值；如果没有提案值返回，则使用决策者 初始提案值。

完成以上操作后，进入下一个阶段。Paxos 算法的第二个阶段称 批准阶段 （Accept）。提议者向所有决策者广播批准申请（称为 accept(N,V) 请求），请求批准：“提案编号 N 提案值 V”。如果决策者发现提案编号 N 不小于它已承诺的最大编号，则“批准”（accepted）该提案；否则拒绝该提案。当多数的决策者批准提案时，提议者认为本轮提案成功、共识达成。一旦提案成功，提议者会将最终的决议广播给所有记录者节点，供它们学习、记录最终结果。

证明 Paxos 算法的正确性比重新实现 Paxos 算法还难。我们没必须推导 Paxos 的正确性，通过以下几个例子来验证 Paxos 算法。

下面的示例中，X、Y 代表客户端，S1 ~ S5 是服务端，它们既是提议者又是决策者，图中的 P 代表 “准备阶段”，A 代表“批准阶段”。为了便于理解，提案编号 N 由自增序号和 Server ID 组成。例如，S1 的提案编号为 1.1、2.1、3.1…。

现在，我们来分析 S1 、S5 同时发起提案，会出现什么情况。

情况一：提案已批准。如图所示，S1 收到客户端的请求，于是 S1 作为提议者，向 S1…S3 广播 Prepare(3.1) 消息，决策者 S1…S3 没有接受过任何提案，所以接受该提案。接着，S1 广播 Accept(3.1, X) 消息，提案 X 成功被批准。

在提案 X 被批准后，S5 收到客户端的提案 Y，S5 作为提议者向 S3…S5 广播 Prepare(4.5) 消息。对 S3 来说，4.5 比 3.1 大，且已经接受了 X，它回复提案 (3.1, X)。S5 收到 S3…S5 的回复后，使用 X 替换自己的 Y，接着进入批准阶段，广播 Accept(4.5, X) 消息。S3…S5 批准提案，所有决策者就 X 达成一致。

情况二：事实上，对于情况一，也就是“取值为 X”并不是一定需要多数派批准，S5 发起提案时，准备阶段的应答中是否包含了批准过 X 的决策者也影响决策。如图所示，S3 接受了提案 (3.1, X)，但 S1、S2 还没有收到 Accept(3.1, X) 消息。此时 S3、S4、S5 收到 Prepare(4.5) 消息，S3 回复已经接受的提案 (3.1, X)，S5 将提案值 Y 替换成 X，广播 Accept(4.5, X) 消息给 S3、S4、S5，对 S3 来说，编号 4.5 大于 3.1，所以批准提案 X，最终共识的结果仍然是 X。

情况三：另外一种可能的情况是 S5 发起提案时，准备阶段的应答中未包含批准过 X 的决策节点。S1 接受了提案 (3.1, X)，S3 先收到 Prepare(4.5) 消息，后收到 Accept(3.1, X) 消息，由于 3.1 小于 4.5，会直接拒绝这个提案。提案 X 没有收到多数的回复，X 提案就被阻止了。提案 Y 顺利通过，整个系统最终对“取值为 Y”达成一致。

情况四：从情况三可以推导出另一种极端的情况，多个提议者同时发起提案，在准备阶段互相抢占，反复刷新决策者上的提案编号，导致任何一方都无法达到多数派决议，这个过程理论上可以无限持续下去，形成 活锁 （livelock）。

解决这个问题并不复杂，将 重试时间随机化 ，就能减少这种巧合发生。

以上，就是整个 Paxos 算法的工作原理。

Paxos 算法只能处理单个提案，达成共识至少需要两次网络往返，高并发情况下还可能导致活锁。因此，Paxos 算法主要用于理论研究，很少直接用于工程实践。后来，Lamport 在论文《Paxos Made Simple》中提出了 Paxos 的变体 —— Multi Paxos。Multi Paxos 引入了“选主”机制，通过多轮运行 Paxos 算法来处理多个提案。

Raft算法

前言

不可否认，Paxos 是一个划时代的共识算法。

Raft 算法出现之前，绝大多数共识系统都是基于 Paxos 算法或者受其影响。同时，Paxos 算法也成为教学领域里讲解共识问题时的范例。不幸的是，Paxos 算法理解起来非常晦涩。此外，论文虽然提到了 Multi Paxos，但缺少实现细节。因此，无论是学术界还是工业界普遍对 Paxos 算法感到十分头疼。

那段时期，虽然所有的共识系统都是从 Paxos 算法开始的，但工程师们实现过程中有很多难以逾越的难题，往往不得已开发出与 Paxos 完全不一样的算法，这导致 Lamport 的证明并没有太大价值。所以，很长的一段时间内，实际上并没有一个被大众广泛认同的 Paxos 算法。

2013 年，斯坦福大学的学者 Diego Ongaro 和 John Ousterhout 发表了论文 《In Search of an Understandable Consensus Algorithm》[1]，提出了 Raft 算法。Raft 论文开篇描述了 Raft 的证明和 Paxos 等价，详细阐述了算法如何实现。也就是说，Raft 天生就是 Paxos 算法的工程化。

此后，Raft 算法成为分布式系统领域的首选共识算法。

领导者选举

Paxos 算法中“节点众生平等”，每个节点都可以发起提案。多个提议者并行发起提案，是活锁、以及其他异常问题的源头。那如何不破坏 Paxos 的“节点众生平等”基本原则，又能在提案节点中实现主次之分，约束提案权利？

理解上面的问题，是先搞清楚 Raft 算法中节点的分类。Raft 提出了领导者角色，通过选举机制“分享”提案权利。

• 领导者（Leader）：负责处理所有客户端请求，将请求转换为 日志 复制到其他节点，不断地向所有节点广播心跳消息：“你们的领导还在，不要发起新的选举”。

• 跟随者（Follower）：接收、处理领导者的消息，并向领导者反馈日志的写入情况。当领导者心跳超时时，他会主动站起来，推荐自己成为候选人。

• 候选人（Candidate）：候选人属于过渡角色，他向所有的节点广播投票消息，如果他赢得多数选票，那么他将晋升为领导者。

联想到现实世界中的领导人都有一段不等的任期。自然，Raft 算法中也对应的概念 —— “任期”（term）。Raft 中的任期是一个递增的数字，贯穿于 Raft 的选举、日志复制和一致性维护过程中。

• 选举过程：任期确保了领导者的唯一性。在一次任期内，只有获得多数选票的节点才能成为领导者。

• 日志一致性：任期号会附加到每条日志条目中，帮助集群判断日志的最新程度。

• 冲突检测：通过比较任期号，节点可以快速判断自己是否落后，并切换到跟随者状态。

Raft 集群 Leader 选举过程：

初始状态下，所有的节点处于跟随者状态。如果跟随者在某个时限（通常是 150-300 毫秒的随机超时时间）未收到领导者心跳，则触发触发选举。节点的角色转为候选者，任期号递增，然后向其他节点广播“投票给我”的消息（RequestVote RPC）。

RequestVote RPC 消息示例如下：

1
2
3
4
5
6

{
  "term": 5, // 候选者的当前任期号，用于通知接收方当前选举属于哪个任期。
  "candidateId": 3, // 候选者的节点 ID，标识请求投票的节点。
  "lastLogIndex": 12, // 候选者日志的最后一条日志的索引，用于比较日志的完整性。
  "lastLogTerm": 4//候选者日志的最后一条日志的任期号，用于进一步比较日志的新旧程度。
}

其他节点收到投票消息后，根据下面的条件判断是否投票：

• 候选者的日志至少与投票者的日志一样新（根据最后一条日志的任期号和索引号判断）。

• 当前节点尚未在本任期投票。

RequestVote 响应的示例如下：

1
2
3
4

{
  "term": 5, //接收方的当前任期号，用于告知候选者最新的任期号。如果候选者发现该值比自己大，会转为跟随者。
  "voteGranted": true//是否投票给候选者，true 表示同意，false 表示拒绝。
}

如果候选者获得多数（超过半数）投票，即成为领导者。之后，领导者向其他节点广播心跳消息，维持领导者地位。如果没有获得多数票，进入下一轮选举，任期号递增，重新发起投票。如果选举过程中收到任期号更高的心跳或投票请求，则转为跟随者。

日志复制

一旦选出一个公认的领导者，那领导者顺理成章地承担起“处理系统发生的所有变更，并将变更复制到所有跟随者节点”的职责。

在 Raft 算法中，日志承载着系统所有变更。下图展示了 Raft 集群的日志模型，每个“日志条目”（log entry）包含索引、任期、指令等关键信息：

• 指令: 表示客户端请求的具体操作内容，也就是待“状态机”（State Machine）执行的操作。

• 索引值：日志条目在仓库中的索引值，是单调递增的数字。

• 任期编号：日志条目是在哪个任期中创建的，用于解决“脑裂”或日志不一致问题。

Raft 算法中，领导者通过广播消息（AppendEntries RPC）将日志条目复制到所有跟随者。AppendEntries RPC 的示例如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

{
  "term": 5, // 领导者的任期号
  "leaderId": "leader-123",
  "prevLogIndex": 8, // 前一日志条目的索引
  "prevLogTerm": 4, // 前一日志条目的任期
  "entries": [
    { "index": 9, "term": 5, "command": "set x=4" }, // 要复制的日志条目
  ],
  "leaderCommit": 7// Leader 的“已提交”状态的日志条目索引号
}

当 Raft 集群收到客户端请求（例如 set x=4）时，日志复制的过程如下：

• 若当前节点非领导者，将请求转发至领导者；

• 领导者接收请求后：

  • 将请求转化为日志条目，写入本地存储系统，初始状态为“未提交”（uncommitted）；

  • 生成日志复制消息（AppendEntries RPC），并广播至所有跟随者；

• 跟随者收到日志复制消息后，验证任期（确保本地任期不大于领导者任期）、日志一致性（通过 prevLogIndex 检查日志是否匹配）。若验证通过，跟随者将日志条目追加至本地存储系统，并发送确认响应；

• 领导者确认日志条目已成功复制至多数节点后，将其状态标记为“已提交”（committed），并向客户端返回结果。已提交的日志条目不可回滚，指令永久生效，且可安全地“应用”（apply）至状态机。

领导者向客户端返回结果，并不意味着日志复制过程已完全结束，跟随者尚不清楚日志条目是否已被大多数节点确认。Raft 的设计通过心跳或后续日志复制请求中携带更新的提交索引（leaderCommit），通知跟随者提交日志。此机制将“达成共识的过程”优化为一个阶段，减少了客户端约一半的等待时间。

我们来看日志复制的另一种情况。在上述例子中，只有 follower-1 成功追加日志，follower-2 因为日志不连续，追加失败。日志的连续性至关重要，如果日志条目没有按正确顺序应用到状态机，各个 follower 节点的状态肯定不一致。

日志不连续的问题是这样解决的：follower-2 收到日志复制请求后，它会通过 prevLogIndex 和 prevLogTerm 检查本地日志的连续性。如果日志缺失或存在冲突，follower-2 返回失败响应，指明与领导者日志不一致的部分。

1
2
3
4
5
6

{
  "success": false,
  "term": 4,
  "conflictIndex": 4, // 表示发生缺失的日志索引，Follower 的日志中最大索引为 3，所以缺失的索引是 4。
  "conflictTerm": 3//缺失日志的“上一个有效日志条目”的任期号
}

当领导者收到失败响应，根据 conflictIndex 和 conflictTerm 找到与跟随者日志的最大匹配索引（例如，6）。随后，领导者从该索引开始重新向跟随者（如 follower-2）发送日志条目，逐步修复日志的不一致性，直至同步完成。

成员变更

在前面的内容中，我们假设集群节点数固定，即集群的 Quorum 也保持不变。然而，在生产环境中，集群通常需要进行节点变更，例如因故障移除节点或扩容增加节点等。对于旨在实现容错能力的算法来说，显然不能通过“关闭集群、更新配置并重启系统”的方式来实现。

在讨论如何实现成员动态变更之前，我们需要先搞明白 Raft 集群中“配置”（configuration）的概念。

配置

配置说明集群由哪些节点组成。例如，一个集群有三个节点（Server 1、Server 2、Server 3），该集群的配置就是 [Server1、Server2、Server3]。

如果把“配置”当成 Raft 中的“特殊日志”。这样一来，成员动态变更需求就可以转化为“配置日志”的一致性问题。但需要注意的是，各个节点中的日志“应用”（apply）到状态机是异步的，不可能同时操作。这种情况下，apply “配置日志”很容易导致“脑裂”问题。

举个具体例子，假设有一个由三个节点 [Server1、Server2 和 Server3] 组成的 Raft 集群，当前的配置为 Cold。现在，我们计划增加两个节点 [Server1、Server2、Server3、Server4、Server5]，新的配置为 Cnew。

由于日志提交是异步处理的，假设 Server1 和 Server2 比较迟钝，仍在使用老配置 Cold，而 Server3、Server4、Server5 的状态机已经应用了新配置 Cnew：

• 假设 Server5 触发选举并赢得 Server3、Server4、Server5 的投票（满足 Cnew 配置下的 Quorum 3 要求），成为领导者；

• 同时，假设 Server1 也触发选举并赢得 Server1、Server2 的投票（满足 Cold配置下的 Quorum 2 要求），成为领导者。

一个集群存在两个领导者也就是“脑裂”，同一个日志索引可能会对应不同的日志条目，最终导致集群数据不一致。

上述问题的根本原因在于，成员变更过程中形成了两个没有交集的 Quorum，即 [Server1, Server2] 和 [Server3, Server4, Server5] 各自为营。

Raft 的论文中，对此提出过一种基于两阶段的“联合共识”（Joint Consensus）成员变更方案，但这种方案实现较为复杂，Diego Ongaro 后来又提出一种更为简化的方案 — 单成员变更（Single Server Changes）。该方案思想的核心是，既然同时提交多个成员变更可能引发问题，那么每次只提交一个成员变更，需要添加多个成员，就执行多次单成员变更操作。这样不就没有问题了么！

单成员变更方案很容易穷举所有情况，如下图所示，穷举奇/偶数集群下节点添加/删除情况。如果每次只操作一个节点，Cold 的 Quorum 和 Cnew 的 Quorum 一定存在交集。交集节点只会进行一次投票，要么投票给 Cold，要么投票给 Cnew。因此，不可能出现两个符合条件的 Quorum，也就不会出现两个领导者。

以下图第二种情况为例，Cold 为 [Server1、Server2、Server3]，该配置的 Quorum 为 2，Cnew 为 [Server1、Server2、Server3、Server4]，该配置的 Quorum 为 3。假设 Server1、Server2 比较迟钝，还在用 Cold ，其他节点的状态机已经应用 Cnew：

• 假设 Server1 触发选举，赢得 Server1，Server2 的投票，满足 Cold Quorum 要求，当选领导者；

• 假设 Server3 也触发选举，赢得 Server3，Server4 的投票，但不满足 Cnew 的 Quorum 要求，选举失效。

目前，绝大多数 Raft 算法的实现和系统，如 HashiCorp Raft 和 etcd，均采用单节点变更方案。