共识问题的精确定义：Agreement、Validity、Termination

先看一个真实的灾难场景，再谈形式化定义。

一个没有共识的系统会怎样

2016 年某大型支付平台发生了一次事故。五节点的分布式锁服务集群出现网络分区：节点 1、2 被隔离在一侧，节点 3、4、5 在另一侧。两侧各自认为对方已经宕机，各自选出了自己的 Leader。

结果是：同一把分布式锁被同时授予了两个客户端。客户端 A 从节点 1 获得了订单 #88721 的处理锁，客户端 B 从节点 4 获得了同一订单的处理锁。两个客户端同时处理同一笔订单——扣款执行了两次，用户被多扣了 4,800 元。

这不是性能问题，不是延迟问题，不是可用性问题。这是正确性问题。系统的五个节点没有就”锁给谁”达成一致，直接导致了数据损坏。

问题出在哪里？这个锁服务的”共识”实现有一个致命缺陷：它在网络分区时允许少数派（2 个节点）独立做出决定。如果它要求多数派（至少 3 个节点）同意才能授予锁，那么两侧不可能同时凑齐多数派——因为 2 + 3 = 5，任何两个多数派必有交集。

这个例子浓缩了共识问题的本质：多个节点必须对同一件事做出相同的决定，即使部分节点不可达。 “相同的决定”就是 Agreement，“多数派交集”就是保证 Agreement 的几何基础。

但仅仅知道”要达成一致”还不够。达成一致到什么程度？如果所有节点永远返回一个硬编码的常量，也算”一致”——但这毫无意义。如果系统在网络不稳定时选择永远等待而不做决定，也不违反一致性——但业务挂了。

这就是为什么共识需要精确定义。它不是一个模糊的目标，而是三个可以独立分析、独立验证、独立取舍的形式化性质。

假设你在设计一个分布式锁服务。五个节点组成一个集群，客户端请求获取锁。某一时刻，两个客户端几乎同时发起请求，两个请求分别被不同节点接收。问题来了：五个节点必须就”锁给谁”这件事达成一致。如果节点 1 认为锁属于客户端 A，节点 3 认为锁属于客户端 B，系统就坏了——这不是性能问题，是正确性问题。

这就是共识（Consensus）问题。它不是一个抽象的学术概念，而是分布式系统里每天都在发生的事情：etcd 的 key-value 存储、ZooKeeper 的配置管理、TiKV 的事务提交、Chubby 的分布式锁——底层都要解决同一个问题。

但”达成一致”这四个字太模糊了。什么叫一致？一致到什么程度？如果有节点挂了，剩下的节点还需要一致吗？如果永远达不成一致，算不算解决了问题？

这些问题的答案，取决于共识的精确定义。这篇文章要做的事情就是把这个定义拆开讲清楚。

一、共识问题的形式化定义

共识问题的形式化定义最早可以追溯到 Lamport、Pease 和 Shostak 在 1982 年关于拜占庭将军问题（The Byzantine Generals Problem）的开创性工作，后来被 Fischer、Lynch 和 Paterson 在 1985 年的 FLP 论文中进一步精确化。

考虑一个由 \(n\) 个进程（Process）组成的分布式系统。每个进程 \(p_i\) 有一个初始的提议值（Proposed Value）\(v_i\)。共识协议的目标是让所有正确的进程（Correct Process）最终输出一个决定值（Decision Value）。

这里”正确的进程”指在整个执行过程中不会发生故障的进程。故障进程可能崩溃（Crash-stop）、崩溃后恢复（Crash-recovery），或者表现出任意行为（Byzantine）。本文在第四节讨论变体之前，默认讨论的是崩溃停止（Crash-stop）模型下的共识。

共识协议必须满足以下三个性质。

Agreement（一致性）

所有正确进程的决定值必须相同。

形式化表述：如果正确进程 \(p_i\) 决定了值 \(v\)，正确进程 \(p_j\) 决定了值 \(v'\)，那么 \(v = v'\)。

Agreement 是最直觉的性质。回到开头的锁服务例子：如果两个正常运行的节点对”锁给谁”给出了不同的答案，系统就违反了 Agreement。

注意 Agreement 只约束正确进程之间的关系。一个已经崩溃的进程在崩溃之前可能输出了不同的值——这种情况不算违反 Agreement。至于是否需要约束故障进程，这是 Uniform Consensus 要讨论的问题，在第四节展开。

Validity（有效性）

决定值必须是某个进程的提议值。

形式化表述：如果所有正确进程都决定了值 \(v\)，那么 \(v\) 一定是某个进程提议过的值。

Validity 看起来是一个非常弱的性质，但它排除了一种平凡的”解法”：无论输入是什么，协议总是输出一个固定的常量，比如 0。这样的协议确实满足 Agreement（所有人都输出 0），也满足 Termination（所有人都立刻输出），但它没有意义——决定值和提议值毫无关系。

Validity 的存在确保了共识的”内容”来自参与者，而不是凭空捏造。

Validity 有几种不同的强度：

弱有效性（Weak Validity）：决定值是某个进程的提议值。这是上面定义的标准形式。
强有效性（Strong Validity）：如果所有正确进程都提议了同一个值 \(v\)，那么决定值必须是 \(v\)。这个版本更常见于二值共识（Binary Consensus）的讨论中。
非平凡性（Non-triviality）：存在至少两种不同的执行场景，分别导致不同的决定值。这是 FLP 论文中使用的形式。

在大多数工程相关的文献中（包括 Paxos 和 Raft 论文），使用的是弱有效性。

Termination（终止性）

所有正确进程最终都会做出决定。

形式化表述：每个正确进程 \(p_i\) 最终都会输出一个决定值 \(v_i\)。

Termination 保证了共识协议不会永远”卡住”。如果一个协议满足 Agreement 和 Validity，但在某些执行路径上永远不输出结果，它就不是一个完整的共识协议。

一个满足 Agreement 和 Validity 但不满足 Termination 的协议在实际中并非毫无用处——它至少保证了”如果最终做出了决定，那个决定一定是对的”。但它无法保证系统不会挂起。

三个性质合在一起，构成了共识的完整定义：

把一个问题精确地切成三块，分别讨论、分别证明、分别取舍——这是形式化定义的价值。一旦有了这三个性质的精确表述，我们就可以严格地讨论：一个算法到底满足了什么，牺牲了什么，在什么条件下牺牲的。

二、Safety 与 Liveness

Lamport 在 1977 年的工作中首先区分了安全性（Safety）和活性（Liveness）这两类性质，Alpern 和 Schneider 在 1985 年给出了精确的拓扑学定义。这个二分法是分布式系统理论的基石之一。

Safety：坏事永远不会发生

Safety 性质的特征是：一旦被违反，就不可挽回。

更精确地说：如果一个有限执行（Finite Execution）违反了某个 Safety 性质，那么这个执行的任何延伸（Extension）都不可能修复这个违反。

Agreement 是 Safety 性质——如果两个正确进程已经做出了不同的决定，无论后续发生什么，这个不一致都无法挽回。

Validity 也是 Safety 性质——如果决定值不是任何进程的提议值，后续也无法改变已经做出的决定。

Liveness：好事最终一定会发生

Liveness 性质的特征是：对任何有限执行，都存在某个延伸使得该性质被满足。

换句话说：Liveness 不能在有限时间内被”判定为违反”。你只能说”到目前为止还没满足”，但不能说”已经被永久违反了”——因为未来总有可能满足。

Termination 是 Liveness 性质——如果到目前为止某个正确进程还没有做出决定，你不能断定它永远不会做出决定。只要系统继续运行，它仍然有可能做出决定。

为什么这个区分如此重要

Safety 和 Liveness 的区分不是为了分类学上的整洁，而是因为它直接决定了系统设计中的工程取舍。

Alpern 和 Schneider 证明了一个关键定理：任何性质都可以分解为一个 Safety 性质和一个 Liveness 性质的交集。 这个结论意味着我们可以分别分析和验证 Safety 和 Liveness，而不必把所有东西混在一起。

在共识的语境中：

Safety（Agreement + Validity） 可以无条件保证。无论网络多么混乱、多少节点崩溃、消息延迟多高，一个正确的共识算法都不应该违反 Safety。这不是理想化的目标，Paxos 和 Raft 确实做到了这一点。
Liveness（Termination） 则需要对系统模型做出假设。FLP 不可能定理精确地告诉我们，在完全异步的模型中，Termination 无法被确定性地保证。

理解这一点之后，工程师在评估一个共识实现时，应该问两个独立的问题：

这个实现在什么条件下可能违反 Safety？答案应该是”没有任何条件”——Safety 违反意味着实现有 bug。
这个实现在什么条件下可能违反 Liveness？答案应该是一组具体的故障场景，比如”Leader 和所有候选者同时不可达”或”网络分区持续时间超过选举超时的上限”。

这两个问题有完全不同的严重性。Safety 违反是灾难——数据损坏、状态不一致、无法修复。Liveness 违反是服务中断——不好，但可以等待恢复。

一个具体的思维实验

考虑一个简单的共识协议：

进程收到提议后，等待所有其他进程的提议值。
如果收到了所有人的提议，取最小值作为决定值。
如果某个进程崩溃了，永远等下去。

这个协议：

满足 Agreement：所有正确进程看到同一组提议值，取最小值的结果相同。
满足 Validity：最小值一定是某个进程的提议值。
不满足 Termination：只要有一个进程崩溃，其他所有进程永远卡在等待阶段。

这就是为什么只有 Safety 的协议在理论上是不完整的：它宁可不回答，也不回答错。 但不回答本身就是一种故障。

真正的共识算法必须在保证 Safety 的前提下，尽可能保证 Termination。问题在于 FLP 定理说了，完全异步系统中做不到这一点。

三、FLP 不可能定理的工程含义

FLP 说了什么

Fischer、Lynch 和 Paterson 在 1985 年证明了这个定理：

在一个完全异步的系统中，即使只有一个进程可能发生崩溃故障，也不存在一个确定性的共识算法能同时保证 Agreement、Validity 和 Termination。

“完全异步”意味着消息可以被延迟任意长的时间，进程的执行速度没有上界，也没有全局时钟或超时机制。

FLP 的证明思路概要是这样的：

首先证明存在一个初始配置（Initial Configuration），在这个配置中系统处于”不确定”状态——既可能决定 0，也可能决定 1。这叫做二价配置（Bivalent Configuration）。
然后证明对于任何确定性算法，从一个二价配置出发，总是可以通过精心调度消息的投递顺序，让系统停留在二价状态——永远不做出决定。
关键的构造技巧是：当系统即将从二价变为一价（Univalent）时，利用一个进程的崩溃来”打断”这个转变。因为系统是异步的，其他进程无法区分”某个进程崩溃了”和”某个进程的消息延迟很长”，所以它们不能安全地做出决定。

FLP 证明的精彩之处在于，它不需要假设很多故障——只要一个进程可能崩溃就够了。它也不需要拜占庭故障——简单的崩溃停止就足以构成不可能性。

FLP 没说什么

FLP 的结论经常被误读。以下几点需要厘清：

FLP 不是说共识问题无解。 FLP 说的是不存在一个确定性算法在完全异步模型下同时保证三个性质。它没有排除以下几种情况：

随机化算法：Ben-Or 在 1983 年就证明了，允许使用随机硬币翻转（Random Coin Flip）的共识算法可以在异步模型下以概率 1 保证 Termination。代价是终止时间的期望可能是指数级的。
部分同步模型：Dwork、Lynch 和 Stockmeyer 在 1988 年提出的部分同步（Partial Synchrony）模型假设系统在某个未知时间点之后会变得同步（或者消息延迟有一个未知的上界）。在这个模型下，确定性共识是可解的。Paxos 和 Raft 正是在这个模型下工作。
故障检测器：Chandra 和 Toueg 在 1996 年引入了不可靠故障检测器（Unreliable Failure Detector）的抽象。他们证明了一个足够强的故障检测器（Ω 类型，即最终选出一个正确的 Leader）就足以在异步模型中解决共识问题。

FLP 不是说 Paxos/Raft 有 bug。 Paxos 和 Raft 的正确性不依赖于 FLP 是否成立。FLP 影响的是这些算法的 Termination 保证，而不是 Safety。

Paxos/Raft 的工程回答

理解了 FLP 之后，Paxos 和 Raft 的设计策略就很清晰了：

Safety 始终保证，无条件。 无论网络延迟多高、多少节点崩溃、消息乱序到什么程度，Paxos 和 Raft 的 Safety 性质（Agreement + Validity）都成立。这是通过仲裁（Quorum）机制实现的——任何决定都需要多数节点同意，而任何两个多数集必定有交集，这就排除了两个互相矛盾的决定被同时做出的可能性。

Liveness 在部分同步模型下保证。 Paxos 和 Raft 都假设系统最终会达到一个稳定期（Stable Period），在此期间消息能在有界时间内送达。在稳定期，算法能够选出 Leader、完成共识、响应请求。

用更工程化的语言来说：

Paxos 和 Raft 永远不会返回错误的结果。
在网络抖动、Leader 切换等不稳定期，它们可能暂时无法响应请求——这是 Liveness 的损失。
一旦网络稳定下来，它们就能恢复正常工作。

这在实践中意味着什么？考虑一个运行 Raft 的 etcd 集群。当 Leader 宕机时，集群需要选出新 Leader。选举依赖随机化超时来避免活锁（两个候选者反复互相取消投票）。如果网络不稳定，选举可能反复失败。在此期间，集群不可用——这是 Liveness 损失。但集群的数据始终是一致的——Safety 从未受到威胁。

Raft 论文中使用的随机化选举超时，本质上就是用随机性打破 FLP 定理所依赖的确定性假设。这不是一种妥协，而是一种经过理论论证的、正确的工程策略。

超时与故障检测

在实际实现中，部分同步模型通常通过超时（Timeout） 机制来实现。超时本质上就是一个不完美的故障检测器：

如果一段时间内没有收到 Leader 的心跳，Follower 就认为 Leader 已经故障，发起新的选举。
如果超时太短，可能把一个还活着但消息延迟了的 Leader 误判为已故障，导致不必要的选举。
如果超时太长，真正的 Leader 故障后集群需要等很久才能恢复。

Chandra 和 Toueg 的理论工作告诉我们，一个最终准确（Eventually Accurate）的故障检测器就够了——它不需要永远正确，只需要在某个时间点之后变得正确。在实践中，这对应的就是：网络最终稳定后，超时机制能正确区分存活的节点和故障的节点。

这就是 FLP 定理的完整工程含义：它不是一个”做不到”的宣判，而是一张地图，告诉我们哪些路走得通、哪些路走不通、以及实际走通的路需要什么条件。

四、共识的变体

标准共识的定义是一个起点。在不同的系统模型和应用场景下，共识有多种变体。

Uniform Consensus（一致共识）

标准共识的 Agreement 性质只约束正确进程：如果两个正确进程做出了决定，它们的决定值必须相同。故障进程在崩溃之前可能输出了不同的值。

Uniform Consensus 加强了这个约束：

Uniform Agreement：如果任何进程（无论正确还是故障）做出了决定，那么所有做出决定的进程的决定值必须相同。

形式化表述：如果进程 \(p_i\)（无论是否故障）决定了值 \(v\)，进程 \(p_j\)（无论是否故障）决定了值 \(v'\)，那么 \(v = v'\)。

Uniform Consensus 和标准共识的区别，在崩溃停止模型下其实很微妙。因为进程崩溃后就再也不会恢复，所以一个崩溃进程输出的值在实际中很少被外部观察到。但在崩溃恢复（Crash-recovery）模型下，区别变得重要：一个进程可能在做出决定后崩溃，恢复后发现自己的决定值和其他正确进程不一致——这在 Uniform Consensus 中是不允许的。

Paxos 和 Raft 实际上都满足 Uniform Agreement。考虑 Raft：一旦一条日志被 committed，它在所有正确节点的日志中都存在于相同的位置。即使一个节点在 commit 之后崩溃重启，它在持久化存储中保留了已 commit 的日志，恢复后不会和其他节点产生不一致。

Binary Consensus 与 Multi-Valued Consensus

根据提议值的值域范围，共识可以分为：

二值共识（Binary Consensus）：提议值只有两个，通常是 0 和 1。
多值共识（Multi-Valued Consensus）：提议值可以是任意域中的元素。

看起来二值共识是一个更简单的问题，但一个经典的归约（Reduction）结果表明：如果你能解决二值共识，你就能解决多值共识。 具体方法是对多值的每一位分别运行二值共识，或者用二值共识来选举一个 Leader，再由 Leader 的提议值作为最终决定值。

这意味着 FLP 定理对二值共识的不可能性结论自动推广到多值共识。

Repeated Consensus（重复共识）

实际系统需要的不是对”一个值”达成共识，而是对”一系列值”依次达成共识。

考虑一个复制日志：日志的第 1 个位置放什么命令？第 2 个位置放什么命令？第 3 个位置呢？每个位置都是一个独立的共识实例（Consensus Instance）。

Multi-Paxos 就是这样工作的：它运行多个 Paxos 实例，每个实例负责日志中的一个位置。Raft 则把这个思路内化到协议设计中：Leader 通过 AppendEntries 把日志条目复制到所有 Follower，每个日志位置的共识隐含在日志复制和提交的流程中。

Repeated Consensus 也被称为序列共识（Sequential Consensus）或多实例共识（Multi-Instance Consensus）。

五、全序广播与共识的等价性

Total Order Broadcast（全序广播）

全序广播（Total Order Broadcast），也叫原子广播（Atomic Broadcast），是比共识更贴近实际应用的一个抽象。它提供两个操作：

broadcast(m)：广播消息 \(m\)。
deliver(m)：投递消息 \(m\)。

全序广播必须满足以下性质：

Validity：如果一个正确进程广播了消息 \(m\)，那么它最终会投递 \(m\)。
Agreement：如果一个正确进程投递了消息 \(m\)，那么所有正确进程最终都会投递 \(m\)。
Integrity：每条消息最多被每个进程投递一次，且只有在它被广播过的前提下才会被投递。
Total Order：如果正确进程 \(p_i\) 先投递了 \(m_1\) 再投递了 \(m_2\)，那么正确进程 \(p_j\) 也必须先投递 \(m_1\) 再投递 \(m_2\)。

最后一条性质是关键：所有正确进程以完全相同的顺序投递消息。这就是”全序”的含义。

全序广播和可靠广播（Reliable Broadcast）的区别在于最后一条：可靠广播保证所有正确进程最终收到同一组消息，但不要求顺序相同。全序广播额外要求顺序一致。

等价性证明

Chandra 和 Toueg 在 1996 年发表的论文 Unreliable Failure Detectors for Reliable Distributed Systems 中证明了一个核心结论：

共识和全序广播在异步系统中是等价的。

等价性意味着两个方向的归约都成立：

方向一：用共识实现全序广播。

这个方向是直觉上更自然的。算法如下：

每个进程维护一个本地待广播消息队列。
重复执行以下过程：
  1. 将本地队列中的消息集合作为提议值，发起共识实例 k。
  2. 共识实例 k 的决定值是一个消息集合 S_k。
  3. 按确定性顺序（如消息 ID 排序）投递 S_k 中的所有消息。
  4. 从本地队列中移除已投递的消息。
  5. k = k + 1，继续。

为什么这个构造是正确的？

Total Order：每轮共识的决定值相同（Agreement），投递顺序由确定性排序决定，因此所有进程的投递顺序一致。
Agreement：共识的 Agreement 保证所有正确进程在每轮看到同一个决定值。
Validity：如果一个正确进程广播了消息 \(m\)，\(m\) 会进入它的本地队列，并最终被某轮共识的提议包含。共识的 Termination 保证该轮最终有决定值，因此 \(m\) 最终被投递。

方向二：用全序广播实现共识。

这个方向稍微不那么直觉，但构造也很简洁：

每个进程将自己的提议值 v_i 通过全序广播发送。
每个进程等待投递的第一条消息 m。
将 m 中携带的提议值作为自己的决定值。

为什么这个构造是正确的？

Agreement：全序广播的 Total Order 保证所有正确进程投递的第一条消息是同一条，因此决定值相同。
Validity：投递的消息一定是某个进程广播的（Integrity），其中携带的是该进程的提议值，因此决定值是某个进程的提议值。
Termination：全序广播的 Validity 保证正确进程广播的消息最终会被投递，因此每个正确进程最终会收到至少一条消息。

这个等价性结果非常重要，因为它说明了：从理论角度看，共识和全序广播是同一个问题的两种表述。 解决了其中一个，就解决了另一个。

等价性的实际意义

在工程中，共识算法（如 Paxos、Raft）和全序广播的关系非常紧密。

Raft 的日志复制机制本质上就是一个全序广播的实现：Leader 接收客户端请求，把它们按顺序写入日志，复制给所有 Follower。所有节点以相同的顺序 commit 这些日志条目。这就是全序广播——每条日志条目对应一条广播消息，commit 对应投递，日志的顺序就是全序。

ZooKeeper 使用的 ZAB（ZooKeeper Atomic Broadcast）协议更是直接以原子广播命名。ZAB 的设计目标就是提供全序广播服务，ZooKeeper 的所有状态变更都通过 ZAB 以全序广播的方式复制到所有节点。

理解这个等价性之后，一个重要的推论是：全序广播和共识一样，无法在完全异步系统中被确定性地解决。 这直接来自等价性——如果全序广播能在异步系统中解决，我们就能用它构造一个异步系统中的共识算法，违反 FLP。

六、状态机复制

SMR 的核心思想

状态机复制（State Machine Replication，SMR）是共识最重要的应用，也是理解共识为什么在实际系统中如此关键的入口。SMR 的思想由 Lamport 在 1978 年提出，后来被 Schneider 在 1990 年的综述论文 Implementing Fault-Tolerant Services Using the State Machine Approach 中系统化。

核心思想用一句话概括：

如果多个副本以相同的初始状态开始，按相同的顺序执行相同的命令，那么它们的最终状态一定相同。

这个思想依赖两个前提：

确定性状态机（Deterministic State Machine）：给定相同的当前状态和相同的输入，状态机产生相同的输出和相同的下一个状态。没有随机性、没有对外部时间的依赖、没有未定义行为。
全序命令序列（Total Order of Commands）：所有副本按完全相同的顺序执行命令。

第一个前提是应用层的责任。第二个前提是共识算法（或等价地，全序广播）的责任。

SMR 的架构

一个标准的 SMR 系统分为三层：

1. 共识层（Consensus Layer）

负责对命令的顺序达成一致。客户端发送命令，共识层确保所有副本以相同的顺序接收这些命令。在 Raft 中，这对应 Leader 接收请求、复制日志条目、确认 commit 的过程。

2. 日志层（Log Layer）

维护已提交命令的有序序列。每个副本的日志内容和顺序完全相同（由共识层保证）。日志是持久化的——即使节点崩溃重启，已 commit 的日志条目不会丢失。

3. 状态机层（State Machine Layer）

按日志中的顺序，依次将每条命令应用到状态机上。状态机的实现是确定性的：相同的命令序列一定产生相同的状态。

这三层的关系是单向的：

Client Request
    → Consensus（提议、投票、commit）
        → Ordered Log（有序、持久化的命令序列）
            → State Machine（确定性地 apply 每条命令）
                → Response to Client

SMR 对确定性的要求

确定性是 SMR 正确性的基石。如果状态机不是确定性的——即使所有副本按相同顺序执行了相同的命令——最终状态也可能不同。

在实际系统中，以下操作会破坏确定性：

时间戳：如果命令中包含”当前时间”，不同节点在不同时刻执行同一条命令会得到不同的时间戳。解决方法：时间戳由 Leader 在提议时确定，作为命令的一部分被复制。
随机数：如果命令的执行依赖随机数生成器，不同节点的随机数序列可能不同。解决方法：随机种子由 Leader 确定并随命令一起复制，或者使用确定性的伪随机数生成。
浮点运算：不同 CPU 架构、不同编译器优化级别下的浮点运算结果可能有微小差异。在要求严格一致性的系统中，要么使用整数运算，要么确保所有节点使用相同的浮点运算行为。
并发执行：如果状态机内部有多线程执行且线程调度不确定，相同的命令序列可能产生不同的执行交错（Interleaving），进而导致不同的状态。解决方法：状态机的命令执行必须是串行的，或者使用确定性的并发执行框架。

CockroachDB 在这方面有过实际教训。在早期版本中，某些非确定性操作导致副本之间的状态漂移（State Drift），最终通过增加确定性检查和修复非确定性代码路径来解决。

SMR 与全序广播的关系

从形式化的角度看，SMR 可以直接建立在全序广播之上：

客户端将命令通过全序广播发送。
每个副本按全序广播的投递顺序接收命令。
每个副本按接收顺序将命令应用到本地状态机。
因为投递顺序相同、状态机确定性相同，所有副本的状态一致。

这个关系解释了为什么共识、全序广播和 SMR 经常被放在一起讨论——它们是同一个问题在不同抽象层次上的表现：

抽象层次	问题表述	典型实现
共识	对单个值达成一致	Paxos（single-decree）
重复共识	对一系列值依次达成一致	Multi-Paxos、Raft
全序广播	所有节点以相同顺序投递消息	ZAB、Raft log replication
状态机复制	所有副本维护一致的状态	etcd、ZooKeeper、TiKV

每一层都可以归约到相邻的层。它们的等价性意味着在任何一层上的不可能性结论（如 FLP）都会传递到其他层。

读请求的处理

SMR 主要解决的是写操作的一致性问题。读请求的处理则引入了额外的复杂性。

最简单的做法是把读请求也通过共识层处理——把每个读请求也当成一条命令写入日志。这样保证了线性一致性（Linearizability），但代价是每次读都要走共识流程，延迟和吞吐量都受限于共识协议。

Raft 论文提出了一种优化：ReadIndex。Leader 在处理读请求时，记录当前的 commit index，然后向多数节点发送心跳确认自己仍然是 Leader。一旦确认，Leader 等待本地状态机 apply 到该 commit index，然后直接从本地状态机读取。这避免了把读请求写入日志的开销。

更激进的优化是 Lease Read（租约读）：Leader 在获得多数节点的心跳确认后，在一个时间段（租约期）内认为自己的 Leader 身份不会被替换，在此期间直接从本地读取，不需要额外的心跳确认。这依赖于时钟的有界偏差假设——如果时钟漂移超出预期，Lease Read 可能读到过期数据。

这些读优化体现了 Safety 和 Liveness 之外的另一个维度：性能。在 Safety 和 Liveness 的约束下，如何最大化吞吐量和最小化延迟，是 SMR 工程实践中最核心的问题之一。

SMR 的局限性

SMR 不是万能的。它有几个固有的局限：

1. 吞吐量受限于单 Leader。 在 Raft 和 Multi-Paxos 的标准实现中，所有写请求都经过 Leader。Leader 的网络带宽、CPU 和磁盘 IO 是整个集群吞吐量的瓶颈。

2. 串行执行限制了并发。 为了保证确定性，SMR 要求命令串行执行。这意味着即使底层硬件支持并行处理，SMR 也很难利用。一些研究（如 Eve、CISE）探索了在不破坏确定性的前提下允许部分并发执行的可能性。

3. 地理分布的延迟。 如果副本分布在不同的数据中心，每次共识都需要跨数据中心的网络往返。Multi-Paxos 和 Raft 的延迟下界是一个跨数据中心 RTT（从 Leader 到最远的多数派成员）。EPaxos 等 Leaderless 协议试图通过去除固定 Leader 来降低跨数据中心场景下的延迟。

4. 状态机的大小限制。 随着时间推移，状态机的状态不断增长。快照（Snapshot）机制可以截断日志，但状态机的完整快照仍需要存储和传输。当状态机非常大时，快照的生成和传输成为性能瓶颈。

这些局限驱动了共识算法和 SMR 的持续演进。后续文章会讨论 Paxos 如何通过灵活的 Quorum 配置减轻 Leader 瓶颈，EPaxos 如何通过 Leaderless 设计降低延迟，以及 Raft 的工程实现如何通过 Pipeline、Batch 和并行 apply 来提升吞吐。

七、从定义到实现：一条思考的线索

回顾全文的逻辑链条：

分布式系统需要多个节点就某个值达成一致——这是共识问题。
共识的精确定义包含三个性质：Agreement、Validity、Termination。
前两个是 Safety，后一个是 Liveness。这个区分决定了工程上的取舍策略。
FLP 定理证明了在完全异步系统中，三个性质无法被确定性算法同时满足。
Paxos 和 Raft 的工程回答是：Safety 始终保证，Liveness 在部分同步模型下保证。
共识和全序广播是等价的——这是 Chandra-Toueg 1996 的结论。
状态机复制建立在全序广播之上：相同的命令序列 + 确定性的状态机 = 一致的副本。

这条线索从抽象到具体，从定义到实现，从不可能到可行。后续文章将沿着这条线索继续：

Paxos 如何在数学上保证 Safety？它的 Prepare-Accept 两阶段协议的每一步为什么是必要的？
Raft 如何把 Paxos 的思想重新组织成工程师能理解的协议？
更先进的共识协议（EPaxos、HotStuff）如何在保持 Safety 的前提下改善 Liveness 和性能？

这些问题的答案，都建立在本文讨论的三个性质和 Safety/Liveness 区分的基础上。

参考资料：

论文

Fischer, M. J., Lynch, N. A. & Paterson, M. S. (1985). Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM, 32(2), 374–382.
Lamport, L., Shostak, R. & Pease, M. (1982). The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 4(3), 382–401.
Chandra, T. D. & Toueg, S. (1996). Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM, 43(2), 225–267.
Dwork, C., Lynch, N. & Stockmeyer, L. (1988). Consensus in the Presence of Partial Synchrony. Journal of the ACM, 35(2), 288–323.
Alpern, B. & Schneider, F. B. (1985). Defining Liveness. Information Processing Letters, 21(4), 181–185.
Schneider, F. B. (1990). Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Computing Surveys, 22(4), 299–319.
Lamport, L. (1998). The Part-Time Parliament. ACM Transactions on Computer Systems, 16(2), 133–169.
Ongaro, D. & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. USENIX ATC.
Ben-Or, M. (1983). Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols. PODC.

书籍

Cachin, C., Guerraoui, R. & Rodrigues, L. (2011). Introduction to Reliable and Secure Distributed Programming (2nd ed.). Springer. — 第 5 章（Consensus）和第 6 章（Total Order Broadcast）对本文讨论的定义和等价性有完整的形式化处理。

同主题继续阅读

把当前热点继续串成多页阅读，而不是停在单篇消费。

2026-04-13 · distributed-systems

【分布式系统百科】共识问题的精确定义：Agreement、Validity、Termination

文章导航

目录