共识:让多个节点对一个值达成一致

6.1共识问题:要什么、能买到什么

共识：让 N 个节点对同一个值作出且仅作出一次相同的决定，即使部分节点崩溃或消息延迟。

四个性质

正式定义要求共识满足四个性质：

• Agreement（一致）：所有作出决定的进程都决定同一个值。
• Validity（有效）：决定的值必须是某个进程曾提议过的值，不能凭空产生。
• Termination（终止）：每个非崩溃进程最终都会作出决定。
• Integrity（完整）：每个进程最多作出一次决定，不可反悔。

前三条容易直觉接受；Integrity 是防止"改主意"——一旦提交就不可撤销，这正是日志 commit 的语义来源。

等价性：共识是所有分布式协调的公因子

共识的核心洞察在于：解共识 ≡ 线性一致 CAS ≡ 全序广播（total-order broadcast）≡ leader 选举 ≡ 锁/租约服务。这五件事在计算复杂度意义上等价——能解其中一个，就能派生其余四个。

给定一条共识日志，实现一把锁只需：客户端提议"我要持锁"，共识模块对该操作达成共识并写入日志，状态机从日志里顺序执行"持锁/释放"操作——日志保证全序，因此任意两个客户端都看到相同的操作顺序，不会同时自认持锁。这正是 etcd 和 ZooKeeper 能同时提供 CAS、选主、分布式锁的原因：底层只有一条共识日志，所有高层原语都从它派生。第 03 章讲过，线性一致性需要"看起来像单副本原子读写"，而这恰好就是共识给出的保证。

FLP 不可能定理与实务出路

FLP（Fischer-Lynch-Paterson 1985）证明：在纯异步模型下（消息延迟无上界、无随机化），不存在确定性算法能在有一个进程可能崩溃的情况下同时满足 Agreement 和 Termination。这是第 01 章"无法区分慢与死"的数学证明形式。

实务出路是放弃纯异步假设：引入部分同步（超时检测、心跳）和随机化（随机选举超时）。超时让系统在大多数时候能区分"慢"与"死"；随机化让竞争的候选者以不同时间发起选举，避免永久活锁。Raft 同时使用了这两条。

6.2Raft 三子问题

Raft 把共识拆成三个相互独立的子问题：leader 选举、日志复制、安全性——每个子问题有独立的机制和证明。

（一）Leader 选举

每个节点持有一个单调递增的逻辑时钟——term（任期），对应第 02 章的 Lamport 时钟思路：term 本质上是一个全局逻辑纪元，比较两个消息的 term 就能判断先后。节点有三种状态：follower、candidate、leader。

选举流程：follower 在随机超时（150–300 ms）内未收到 leader 心跳，则自增 term、转为 candidate、向所有节点广播 RequestVote。每个节点每个 term 至多投一票（先到先得），且只投给日志不旧于自己的 candidate（见安全性一节）。第一个获得多数派票数的 candidate 成为新 leader，立即发送 AppendEntries 心跳宣告存在。

若两个 candidate 平票，双方各自重新随机等待后再次发起选举。随机超时使平票概率随轮次指数下降——这是绕过 FLP 的随机化手段。

（二）日志复制

leader 收到客户端写请求后，将操作追加为一条 log entry（含 term + index + command），并行发送 AppendEntries RPC 给所有 follower。leader 为每个 follower 维护两个指针：

• nextIndex[]：乐观估计下次应发送的 entry index（初始为 leader 日志末尾 + 1）。
• matchIndex[]：已确认 follower 复制到的最高 index。

一旦某条 entry 被写入多数派节点的日志（不是内存缓冲，是持久化日志），leader 推进 commitIndex，将该 entry 应用到本地状态机，并在后续心跳中携带 commitIndex，通知 follower 也应用到相同位置。

当 follower 的日志与 leader 发来的 entry 前缀不一致时，AppendEntries 的一致性检查失败：leader 回退该 follower 的 nextIndex 直到找到两端日志匹配的分叉点，然后用 leader 的日志覆盖 follower 的冲突后缀。follower 不能拒绝这种覆盖——follower 的日志只有在成为 leader 之前没有被提交的 entry，才会被覆盖。

（三）安全性：已提交 entry 永不丢失

Raft 通过两条性质联合保证安全：

Log Matching Property：若两个节点的日志在某个 index 处有相同 term 的 entry，则该位置的命令相同，且该 index 之前的所有 entry 也完全相同。这是因为 AppendEntries 携带前一条 entry 的 (index, term) 作为一致性检查——前缀匹配则全部匹配，递归地保证了前缀一致性。

选举限制（Election Restriction）：candidate 在 RequestVote 中携带自己的最后一条 entry 的 (lastLogTerm, lastLogIndex)。follower 只投票给"日志不旧于自己"的 candidate——比较规则：先比 lastLogTerm，term 大的更新；term 相同则比 lastLogIndex，更长的更新。不满足条件的投票请求一律拒绝。

成员变更

直接从旧配置切换到新配置会产生两个独立的多数派（旧配置的多数派 + 新配置的多数派），导致同一 term 内两个节点都认为自己是合法 leader。Raft 的解法是 joint consensus（联合配置）：引入过渡配置 C_old,new，在过渡期间日志 entry 必须在新旧两个配置各自取得多数派才算提交。这确保过渡期间也不会出现两个 leader。单节点增减（one-by-one 方案）是更简单的替代，但要求每次只改变一个节点。

6.3Paxos 概览，以及 Raft 为何更易懂

Paxos 是最早被证明正确的共识算法；Raft 是在 Paxos 思路之上、以可理解性为首要设计目标的重新推导。

Basic Paxos：三角色与两阶段

Paxos 有三个角色：proposer（提议者）、acceptor（接受者）、learner（学习者）。一次决议分两阶段：

Phase 1 — Prepare/Promise：proposer 选取唯一的、单调递增的 proposal number n，向多数派 acceptor 发送 Prepare(n)。acceptor 收到后，若 n 大于自己已见过的最大 proposal number，则 promise：承诺不再接受编号低于 n 的提案，并返回自己已接受的最高编号提案的值（若有）。

Phase 2 — Accept/Accepted：proposer 收集多数派回复后，确定要提议的值——若任意 acceptor 返回了已接受值，则必须取编号最高的那个值（不能选自己想要的值）；否则才能自由选值。proposer 发送 Accept(n, v)，多数派接受后，该值被决定，learner 得知并应用。

Phase 2 的"必须取已接受的最高编号值"是 Paxos 安全性的核心：它确保一旦某个值被多数派接受，后续任何 proposer 也只能提议同一个值，不会覆盖。

Paxos 落地的四个难点

Basic Paxos 只能决定单个值。构建分布式日志需要对每个 slot（位置）运行一个独立的 Paxos 实例。没有稳定 leader 时，多个 proposer 互相抢占对方的 proposal number，每个人都在 Phase 1 抢票、破坏对方的 Phase 2——活锁（dueling proposers）。此外，日志空洞（某个 slot 还没被决定、但后面的 slot 已决定）、成员变更语义都被 Lamport 的原始论文留给实现。

Raft 用稳定的强 leader消除了竞争：所有写入只经过 leader，日志没有空洞（顺序追加），成员变更有明确的 joint consensus 协议。代价是 leader 成为瓶颈，但换来的是实现复杂度大幅降低。

6.4多数派为何防脑裂

任意两个多数派在 N 节点集群中必然有公共节点——这个数学事实使同一时刻两个多数派不可能持有矛盾的决定。

证明极简：设 N=5，多数派大小 q=3。假设两个节点集合 Q1 和 Q2 都达到多数派。|Q1|+|Q2| = 3+3 = 6 > 5 = N，由鸽巢原理 Q1∩Q2 ≥ 1。该公共节点在同一 term 内至多投一票——因此 Q1 和 Q2 不可能对相互矛盾的提案都达成多数派。同理，candidate 在同一 term 内不可能有两个都拿到多数派，脑裂被数学排除。

生产中的脑裂通常源于 quorum 大小配置错误，不是算法 bug。常见误配：把 quorum 设为 N/2（偶数时两个 N/2 不重叠）、或允许网络分区后两侧都能达到配置中的 quorum（静态配置未感知节点已离开集群）。

6.5租约、fencing token 与分布式锁

租约是有时限的领导权；fencing token 是让存储侧能拒绝过期持锁者写入的递增令牌。两者结合才能实现正确性意义上的分布式互斥。

租约（Lease）

租约是带有明确过期时间的锁授权。持有者在 TTL 内独占资源，到期自动释放——即使持有者崩溃，系统也不会永久等待其显式释放。etcd 和 ZooKeeper 的 session + ephemeral node 都是租约的实现形式。

租约的代价：持有者依赖本地时钟判断租约是否过期，而第 02 章说过物理时钟有漂移。若持有者时钟走慢、它以为租约还有 2 秒但实际已过期，锁服务已把锁给了新客户端——两个客户端同时持锁。单靠租约不够，需要 fencing token。

Fencing Token

fencing token（接第 04 章）是锁服务每次授予锁时颁发的单调递增整数。客户端在访问共享资源时携带 token；资源侧（数据库、存储服务）记住见过的最大 token，并拒绝 token 值更小的写请求。

这样，即使旧持锁者因 GC 暂停超过 TTL 后恢复，它携带的是旧 token（如 33），而存储已见过新 token（如 34），旧写请求被拒绝——不依赖客户端自知"其租约已过期"，而是由存储侧强制执行顺序。

分布式锁：Redis SETNX 的两个安全漏洞

朴素实现：SET key val NX PX ttl（Redis SETNX + TTL）。两种情况下两个客户端会同时自认持锁：

1. GC 暂停超 TTL：Client 1 持锁期间 JVM GC 暂停，TTL 到期，Redis 释放锁，Client 2 获锁。Client 1 从暂停中恢复，本地认为自己还持锁——两者同时持锁。
2. Redis 主从 failover：Client 1 在主库写入锁，主库在将该写入同步到从库之前崩溃，从库晋升为新主库，此时锁记录不存在，Client 2 也能获锁——两者同时持锁。

Redlock 与争议

Redis 作者 Antirez 提出 Redlock：向 5 个独立 Redis 实例发送 SETNX，若在有效时间内从多数派（≥3）获得锁，则认为加锁成功。Kleppmann 的批评（"How to do distributed locking" 2016）指出：Redlock 仍然没有 fencing token，时钟跳变或客户端 GC 暂停可以破坏其安全性，而它的安全论证依赖精确时钟假设。Antirez 回应：Redlock 的设计目标是效率（避免重复工作），而非正确性——在这个目标下，时钟偏差带来的窗口期是可接受的。

结论：需要正确性互斥时，使用 etcd 或 ZooKeeper（共识支持的锁服务）获取租约，并在资源侧实现 fencing token 检查。