21.1 共识问题定义
一句话
共识是让 N 个可能崩溃的进程对“一个值”达成不可反悔的一致：一致性（不会有两个决定）、有效性（决定的值有人提过）、终止性（非故障进程最终都决定）——三条缺一不可，而 FLP 说明异步网络里终止性无法保证。
三个性质：少一条都不叫共识
| 性质 | 形式化说法 | 违反会怎样 |
|---|---|---|
| 一致性（Agreement） | 任意两个正确的进程不会决定不同的值 | 双主、脑裂、两个客户端看到不同的“成功” |
| 有效性（Validity） | 被决定的值必须是某个进程提议过的，不能凭空产生 | 返回一个没人提过的值（如默认 0），业务语义错乱 |
| 终止性（Termination） | 每个正确的进程最终都会决定一个值 | 系统卡住、无限等待，等于不可用 |
有时还会加一条完整性/稳定性：一旦决定就不能反悔（不可撤销）。这条实际上是“决定”一词的定义，工程上对应“已提交的日志不能改”。
🔑 三条性质里，终止性是最难的一条：一致性与有效性可以在“永远不决定”时平凡地满足。共识的全部工程难度，都花在“如何在故障下仍然终止”上。
从“决定一个值”到“复制一条日志”
单值共识看起来没用（决定一次就结束了），但它是所有复制系统的内核：
单值共识：决定哪个提案成为 v（Paxos 的经典形式）
↓ 每个日志位置做一次
多值共识（Multi-Paxos / Raft）：决定位置 1、2、3… 上分别是什么
↓ 按顺序执行
状态机复制（SMR）：所有副本执行相同的日志 → 状态一致
这就是为什么“共识算法”等于“复制日志算法”：日志里的每个位置，都是一次单值共识。
| 用途 | 共识在决定什么 |
|---|---|
| 选主 | 哪个节点是 leader（任期号 + 候选人；工程实现见 48.4 Leader 选举） |
| 配置管理 | 集群成员、分片归属 |
| 分布式锁（强安全） | 谁是当前持有者（互斥问题本身见 20.1 互斥问题与临界资源 (安全性 / 活性)） |
| 数据库复制 | 每条事务在日志中的位置与顺序 |
| 分布式事务协调 | 提交还是回滚 |
为什么难：三个绕不过去的约束
| 约束 | 含义 | 后果 |
|---|---|---|
| 没有共享内存 | 只能靠消息 | 无法用一条 CAS 指令定序 |
| 消息延迟无上界 | 异步模型里消息可以任意晚 | 无法区分“对方慢”还是“对方死”（35.4 故障检测） |
| 进程可能崩溃 | 决定前就没了 | 必须靠多数派，而不是“问所有人” |
FLP 不可能性（22.2 FLP 不可能性）把第三条推到极致：在完全异步、且允许一个进程崩溃的模型里，不存在既保证一致性又保证终止性的确定性共识算法。工程上的解法不是“违反 FLP”，而是加假设：
- 部分同步：假设网络最终会恢复“足够快”，用超时触发选举（Raft/Paxos 的工程实现都这么干）；
- 随机化：用随机退避打破对称，终止性变成“以概率 1 终止”；
- 故障检测器：用 φ accrual 之类给出“可疑度”，而不是二值判断。
💡 所以“Raft 保证了共识”这句话要补全：在部分同步假设 + 多数派存活的前提下，Raft 保证一致性与最终终止。网络一直抖，它就会一直选主、一直不提交——这不违反 FLP，因为 FLP 说的是异步模型。
需要多少副本：2f+1 与 3f+1
| 故障类型 | 最少副本 | quorum | 直觉 |
|---|---|---|---|
| 崩溃故障（crash） | 2f + 1 | f + 1 | 任意两个多数派必相交（推导见 21.2 Quorum 与 W + R > N 的证明） |
| 拜占庭故障（byzantine） | 3f + 1 | 2f + 1 | 恶意节点可能“两边都说谎”，交集里不能有它（见 22.1 故障类型） |
| f（能容忍几个坏） | 崩溃模型副本数 | 拜占庭模型副本数 |
|---|---|---|
| 1 | 3 | 4 |
| 2 | 5 | 7 |
| 3 | 7 | 10 |
成本：消息复杂度通常是 O(N²)（每个节点要和所有节点通信），N 从 3 涨到 7，消息量涨 5 倍多；跨城部署时还要乘以 RTT。这就是为什么共识集群通常只有 3 或 5 个节点，而不是 21 个。
共识不是万能的：它不解决什么
| 共识能解决 | 共识不解决 |
|---|---|
| 多个副本对“顺序”达成一致 | 值本身对不对（有效性只要求“有人提过”） |
| 故障时仍只有一个真相 | 吞吐与延迟（单 leader 串行提交，见 21.12） |
| 选主、配置、日志复制 | 业务冲突（两个都合法的写，仍需合并规则） |
| 强一致的元数据 | 跨地域低延迟（跨城一次决策至少 1 个 RTT） |
常见误解
| 误解 | 现实 |
|---|---|
| “共识 = 选主” | 选主只是共识的一个应用；日志复制、配置变更都要共识 |
| “Paxos 决定一个值，所以没用” | 多值共识 = 每个日志位置跑一次单值共识，Raft 是它的工程化 |
| “多数派写入就线性一致了” | 多数派只保证“不会有两个决定”；读还要 ReadIndex/租约（见 21.12） |
| “共识能解决分区” | 分区时少数派只能不可用（17.1），如何取舍见 17.3 分区期间的取舍；共识只是让多数派继续工作 |
| “加节点更可靠” | 崩溃模型 3→5 节点能多容忍 1 个故障，但延迟与消息量都上升；跨城还受 RTT 限制 |
| “FLP 说明共识不可实现” | FLP 说的是异步 + 确定性 + 终止性三者不可兼得；加部分同步/随机化即可工程实现 |
反模式
| 反模式 | 后果 |
|---|---|
| 用“两阶段提交 + 超时”代替共识 | 协调者挂掉后悬挂，参与者长期锁资源 |
| 3 节点集群跨 3 个城市 | 每次提交 30ms 起，吞吐掉一个数量级；且任两地网络抖动就选不出主 |
| 用 gossip 最终一致冒充共识 | 分区时会出现两个“真相” |
| 忽略有效性，返回默认值 | 客户端把“没人提过的值”当真相 |
| 只测正常路径，不测分区/崩溃 | 真故障时才发现选主逻辑有 bug |
| 把共识用于高频数据 | 单 key 串行提交上限 = 1/RTT（见 21.12） |
自检
Q1 共识的三条性质里，哪一条最难？为什么另外两条可以在“什么都不做”的情况下被平凡满足？
▸ 答案：终止性最难。一致性和有效性都是“如果有决定，则……”形式的条件：一个永远不做决定的算法，不会产生两个不同的决定（一致性成立），也不会决定没人提过的值（有效性成立）。所以只满足这两条毫无价值——“永远不决定”在业务上等于不可用。终止性要求“在故障下仍然做出决定”，这才是共识的全部难度，也正是 FLP 打击的那一条。
Q2 3 个节点、容忍 1 个崩溃，为什么是 3 而不是 2？用 quorum 相交解释。
▸ 答案：选主/提交需要多数派 f+1 = 2 票。2 个节点时多数派是 2，任意一个挂掉就凑不齐 2 票，系统不可用；3 个节点时多数派是 2，挂 1 个还剩 2 票，仍能工作。更本质的理由是任意两个多数派必须相交：2q > N，q=2、N=3 满足 4 > 3，所以新主一定能看到旧主已提交的日志。N=2、q=2 时 4 > 2 也相交，但容错为 0（任一节点挂即不可用），等于没有容错。
Q3 为什么说“多数派写入 = 线性一致”是错的？
▸ 答案：多数派写入只保证写不会丢失、不会出现两个互相矛盾的提交（Agreement），不保证读能看到最新值：从库/跟随者可能还没应用该日志；即使从 leader 读，如果读不加 ReadIndex/租约，也可能读到旧状态（比如刚选出的新 leader 还没提交 no-op）。线性一致的读需要额外机制：ReadIndex（一次多数派往返确认自己仍是 leader）、租约读（依赖时钟假设）或把读也走一遍日志。
Q4 FLP 说异步网络里共识不可能，为什么 Raft/etcd 还能用？它们“违反”了 FLP 吗？
▸ 答案：没有违反，它们改变了假设。FLP 的前提是“完全异步 + 确定性算法 + 必须终止”；工程实现加了两条：① 部分同步（假设网络最终会稳定一段时间），用选举超时触发选主；② 随机化（随机选举超时），把“保证终止”换成“以概率 1 终止”。在假设不成立时（网络长期抖动），系统会退化为“不提交”，这与 FLP 的结论一致——实际系统用“不可用”换取了一致性。