分布式协调
0. 引言
分布式数据库的副本一致性、故障切换、事务提交，都依赖一组底层协调机制：错误侦测判断节点是否存活、领导选举决定谁来做主、可靠传播让变更到达所有副本、共识让多个节点就同一值达成一致。本文按"问题 → 机制 → 算法"的脉络展开这四层。
1. 核心问题与失败模型
分布式协调要解决的核心问题：
| 问题 | 要回答什么 | 对应机制 |
|---|---|---|
| 故障检测 | 节点还活着吗？ | 心跳、Gossip 探测 |
| 领导选举 | 谁来做主？ | Bully / Raft 选举 |
| 一致性 | 副本读到什么状态？ | 一致性模型（详见《一致性：CAP 与一致性模型》） |
| 共识 | 多个节点就某值达成一致？ | Paxos / Raft / ZAB |
| 数据传播 | 变更如何可靠到达所有副本？ | 原子广播、反熵 |
| 事务 | 跨节点操作如何原子？ | 2PC / 共识化提交（详见《事务与恢复》） |
讨论上述问题前需明确失败模型：
| 模型 | 行为 | 典型假设 |
|---|---|---|
| 崩溃-停止（Crash-Stop） | 节点永久停止，不发送任何消息 | 简单理论模型 |
| 崩溃-恢复（Crash-Recovery） | 节点停止后可重启，丢失内存状态 | 数据库节点的常见假设 |
| 遗漏（Omission） | 消息可能丢失 | 网络不可靠 |
| 拜占庭（Byzantine） | 节点可任意行为，包括发送矛盾消息 | 区块链等对抗场景 |
数据库节点通常假设为崩溃-恢复 + 非拜占庭模型，从而可使用较简单的共识算法。
2. 错误侦测
错误侦测是分布式系统感知节点存活的机制，是领导选举、复制、共识的前提。系统必须区分"节点已崩溃"与"节点只是响应慢"：误判会把健康节点剔除（降低可用性），漏判会向已死节点持续发请求（浪费资源）。
2.1 心跳与准确性权衡
最基础的侦测是心跳：节点周期性发送心跳，接收方在超时窗口内未收到即判定失败。超时应大于网络最大延迟与处理抖动，否则误判率升高。
错误侦测存在根本性权衡：
- 强完整（Complete）：每个真实失败的节点最终都被检测到；
- 强准确（Accurate）：被判定失败的节点确实失败了。
在异步网络中二者无法同时完美保证，实际系统采用概率性侦测：以一定误判率换取及时性。
2.2 Gossip 风格的成员探测
节点间通过 Gossip 交换彼此的存活信息，每个节点维护对其它节点的怀疑度：多次未达的心跳使怀疑度累积，超过阈值才判定失败，降低瞬时抖动导致的误判。
侦测结果与上层协作：侦测到 Leader 失败 → 触发选举；侦测到副本失败 → 移出可用集合，剩余副本仍满足 Quorum；侦测结果是共识中判定"诚实节点"的输入。
3. 领导选举
许多操作只适合由单一节点执行：分配分片、决定事务提交顺序、协调复制。若多个节点同时担任协调者，会产生冲突与脑裂（Split-Brain）。选举机制保证任一时刻至多一个有效 Leader。
3.1 基本要求
- 安全性（Safety）：不会出现两个节点同时自认为 Leader；
- 活跃性（Liveness）：旧 Leader 失效后，系统最终能选出新 Leader；
- 唯一性：集群视角下 Leader 唯一。
3.2 选举算法
| 算法 | 机制 | 优点 | 缺点 |
|---|---|---|---|
| Bully | 节点按 ID 排序，大 ID 发起选举，无更大响应则自任 Leader 并广播 | 实现简单、收敛快 | 高 ID 节点频繁触发选举，消息多 |
| Ring | 节点逻辑成环，选举消息沿环传递，ID 最大者胜出 | 结构简单 | 环断裂需自愈 |
| 基于共识 | 选举融入共识算法（如 Raft 的任期选举），Leader 兼负日志复制 | 选举与复制统一，避免脑裂 | 依赖共识实现 |
3.3 租约（Lease）机制
Leader 通过租约向其他节点证明自己仍然有效：定期刷新租约，超时未刷新则其他节点可发起新选举。租约避免持续心跳的开销，并提供明确的 Leader 权威窗口。侦测延迟决定了故障切换（Failover）的时长，过度敏感的侦测会引发频繁选举（抖动）。
4. 可靠传播与反熵
复制把数据放到多节点，但网络会丢包、乱序、节点会离线——可靠传播保证变更最终到达所有副本，反熵保证副本间状态收敛一致。
4.1 广播与原子广播
广播将一份数据从一个节点同步到多个节点。**原子广播（Atomic Broadcast）**额外保证：
- 全序（Total Order）：所有节点以相同顺序收到消息；
- 可靠性：消息要么被所有节点接收，要么都不接收。
原子广播与共识等价（可相互归约），是 ZAB、Raft 的核心能力。
4.2 Gossip 与反熵
Gossip 让每个节点周期性地随机选若干节点交换状态，信息以"传染病"方式指数级扩散：
- 优点：去中心、可扩展、容错好；
- 缺点：传播有延迟，达到一致需若干轮。
反熵是修复副本分歧的过程：副本间定期比对摘要（如 Merkle 树——将数据集分层哈希，比对根与分支哈希即可定位差异分片，避免全量比对），发现差异后同步缺失或过期的数据。配套机制：
- 读修复（Read Repair）：读取时若发现副本不一致，立即修复落后副本；
- Hinted Handoff：临时不可达的副本，由其他节点暂存其应得更新，恢复后补发。
反熵驱动的系统通常提供最终一致性（详见《一致性：CAP 与一致性模型》），修复速度决定了"最终"的时限。
5. 共识算法
共识是多个节点就某个值（如日志顺序、Leader 身份）达成一致的过程，是复制、选举、事务的底层支柱。
5.1 三属性
- 正确性（Validity）：达成共识的值必须来自某个诚实节点的提议；
- 一致性（Agreement）：所有诚实节点就相同值达成共识；
- 终止性（Termination）：诚实节点最终就某值达成共识。
正确性 + 一致性对应安全性（Safety），终止性对应活跃性（Liveness）。
5.2 主要算法
| 算法 | 特点 | 工程代表 |
|---|---|---|
| Paxos | 理论上最严谨，Prepare/Accept 两阶段 + Quorum；难理解与实现，Multi-Paxos 工程复杂 | Spanner |
| Raft | 以可理解性为目标：Leader 选举 + 日志复制 + 任期（Term）安全；等价于 Multi-Paxos，结构清晰 | etcd、TiKV、Consul |
| ZAB | ZooKeeper 的原子广播协议，偏主备模型：单一 Leader 广播事务，Follower 按序应用 | ZooKeeper |
| VR | 早于 Raft 的共识方案，Leader + 日志复制 + 视图切换 | 学术系统 |
5.3 性能与代价
- 共识通常需多数派往返，跨地域延迟高；
- 写入吞吐受 Leader 单点限制（可批处理缓解）；
- 读若要求线性一致，需经 Leader 或读多数派（Read Index / Lease Read）。
6. 小结
- 协调四层：侦测（活着吗）→ 选举（谁做主）→ 传播（变更到齐）→ 共识（顺序一致）；
- 失败模型决定算法选择：数据库常用崩溃-恢复 + 非拜占庭；
- 心跳是侦测基座，Gossip + 怀疑度降低误判；租约给 Leader 明确的权威窗口；
- 原子广播 ≡ 共识，反熵（Merkle 树/读修复/Hinted Handoff）兜底最终一致；
- 共识主流实现：Paxos（严谨）、Raft（可理解）、ZAB（主备）、VR（先驱）。
下一章讲解系统实践：从案例与传统方案看分布式数据库的落地演进。