分布式共识算法
共识算法是分布式系统的核心机制，用于在多个节点之间就某个值达成一致。简单来说，共识问题就是要让一组分布式节点在可能发生故障的情况下，对某个提案达成一致意见。
共识问题看似简单，实则深刻。它触及了分布式系统最本质的挑战：在网络不可靠、节点可能故障的环境中，如何实现可靠的协调？这个问题的研究催生了一系列经典算法，深刻影响了现代分布式系统的设计。
共识问题的定义
在讨论具体算法之前，我们需要明确共识问题的定义。一个正确的共识算法必须满足以下三个属性：
安全性（Safety）：
- 只有被提议的值才能被选定
- 最终选定的值只能有一个
- 如果某个节点决定了某个值，那么其他节点最终也会决定相同的值
活性（Liveness）：
- 只要大多数节点存活并可以相互通信，系统最终会选定一个值
- 每个正确的节点最终都会做出决定
容错性（Fault Tolerance）：
- 系统能够容忍一定数量的节点故障
- 故障类型包括崩溃故障（节点停止工作）和拜占庭故障（节点行为任意）
安全性是"不会出错"的保证，活性是"终将完成"的承诺。两者看似简单，但在分布式环境中实现却极具挑战。
FLP 不可能性
定理内容
1985年，Fischer、Lynch 和 Paterson 发表了著名的论文《Impossibility of Distributed Consensus with One Faulty Process》，证明了 FLP 不可能定理。这个定理是分布式系统领域最重要的理论结果之一。
定理内容：在异步分布式系统中，即使只有一个节点可能发生故障，也不存在能够始终正确终止的确定性共识算法。
理解这个定理需要明确几个概念：
异步系统：消息传输延迟没有上限，节点处理速度也没有保证。在这种情况下，无法区分一个节点是"很慢"还是"已经故障"。
确定性算法：算法的行为完全由其输入和当前状态决定，不依赖随机性。
始终正确终止：算法在任何情况下都能在有限时间内达成共识。
为什么不可能
FLP 定理的核心洞察是：在异步系统中，无法区分"节点故障"和"消息延迟"。如果一个节点没有响应，可能是它故障了，也可能是消息还在路上。如果算法选择等待，可能会无限期等待（如果节点真的故障了）。如果算法选择继续，可能会违反安全性（因为那个"不响应"的节点可能在稍后响应，带来不同的决定）。
实际意义
虽然 FLP 证明了完美的共识算法不存在，但在实际系统中我们可以通过以下方式近似解决：
- 使用超时：添加超时机制，假设系统是"部分同步"的，在大部分时间是异步的，但偶尔会有同步的时刻
- 随机化：使用随机化算法降低最坏情况概率，使得无论系统处于什么状态，都有一定的概率能够前进
- 弱化活性：允许短暂的不可用换取一致性，承认在极端情况下系统可能暂时无法达成共识
Paxos 算法
Paxos 是 Leslie Lamport 在 1990 年提出的共识算法，被认为是分布式共识的经典解法。Lamport 在论文《The Part-Time Parliament》中以寓言的形式描述了这个算法，但因其晦涩难懂，后来又发表了《Paxos Made Simple》来解释。Paxos 是第一个被证明正确的容错共识算法，影响了后续众多系统的设计。
算法角色
Paxos 定义了三种角色：
| 角色 | 职责 |
|---|---|
| Proposer（提议者） | 提出提案，提案包含提案编号和提议的值 |
| Acceptor（接受者） | 对提案进行投票，决定是否接受提案 |
| Learner（学习者） | 学习被选定的值 |
在实际系统中，一个进程可能同时扮演多个角色。例如，一个服务器可能既是提议者（发起提案），又是接受者（投票表决），还是学习者（学习结果）。
算法流程
Paxos 实现
// 简化的Paxos实现
class PaxosNode {
private String nodeId;
private int proposalNumber = 0;
private String acceptedValue = null;
private int acceptedProposalNumber = -1;
// 接收准备请求
public Promise prepare(int n) {
if (n > proposalNumber) {
proposalNumber = n;
// 返回之前接受的提案（如果有）
return new Promise(n, acceptedProposalNumber, acceptedValue);
}
// 拒绝（已有更新的提案）
return new Promise(n, -1, null);
}
// 接收接受请求
public Accepted accept(int n, String value) {
if (n >= proposalNumber) {
proposalNumber = n;
acceptedValue = value;
acceptedProposalNumber = n;
return new Accepted(n, true);
}
return new Accepted(n, false);
}
}
// Paxos共识过程
class PaxosConsensus {
private List<PaxosNode> acceptors;
private int quorum; // 多数派数量
public String propose(String value) {
// 1. 生成唯一的提案编号
int proposalNumber = generateProposalNumber();
// 2. 准备阶段：收集多数派承诺
List<Promise> promises = sendPrepare(acceptors, proposalNumber);
// 3. 检查是否有已接受的提案
Promise latest = findLatestPromise(promises);
if (latest.getAcceptedValue() != null) {
// 使用已接受的提案值
value = latest.getAcceptedValue();
}
// 4. 接受阶段：请求多数派接受
List<Accepted> accepted = sendAccept(acceptors, proposalNumber, value);
// 5. 检查是否达成共识
if (countAccepted(accepted) >= quorum) {
return value; // 共识达成
}
// 6. 共识未达成，重试
return propose(value);
}
}
Paxos 安全性不变量
理解 Paxos 的关键在于理解它维护的安全性不变量（Invariants）。Lamport 在论文中通过一系列推导展示了这些不变量是如何保证正确性的。
核心不变量
Paxos 的安全性依赖于以下几个关键不变量：
P1：Acceptor 必须接受它收到的第一个提案
P1. An acceptor must accept the first proposal that it receives.
这个规则确保了在正常情况下（无故障、无消息丢失），即使只有一个提议者提出一个值，这个值也能被选定。
P2：如果某个值的提案被选定，那么所有更高编号的被选定提案必须有相同的值
P2. If a proposal with value v is chosen, then every higher-numbered
proposal that is chosen has value v.
这个不变量是 Paxos 安全性的核心——它保证了不会选定两个不同的值。
从 P2 到 P2a、P2b、P2c 的推导
直接维护 P2 是困难的。Lamport 通过一系列加强条件，最终得到了可实现的 P2c：
P2a：如果一个值为 v 的提案被选定，那么所有更高编号的被接受提案必须有值 v
P2a. If a proposal with value v is chosen, then every higher-numbered
proposal accepted by any acceptor has value v.
P2a 比 P2 更强——它要求每个 Acceptor 接受的提案都满足条件，而不仅仅是被选定的提案。
P2b：如果一个值为 v 的提案被选定，那么所有更高编号的提案（由任何 Proposer 发出）必须有值 v
P2b. If a proposal with value v is chosen, then every higher-numbered
proposal issued by any proposer has value v.
P2b 又比 P2a 更强——它要求 Proposer 在发出提案时就必须遵守条件。
P2c：对于任意 v 和 n，如果编号为 n、值为 v 的提案被发出，则存在一个多数派集合 S 满足以下条件之一：
P2c. For any v and n, if a proposal with value v and number n is issued,
then there is a set S consisting of a majority of acceptors such that
either (a) no acceptor in S has accepted any proposal numbered less than n, or
(b) v is the value of the highest-numbered proposal among all proposals
numbered less than n accepted by the acceptors in S.
P2c 是最终可以实现的条件。它的含义是：
- 条件(a)：要么集合 S 中没有任何 Acceptor 接受过编号小于 n 的提案——这意味着这是一个"全新的"提案，Proposer 可以自由选择任何值
- 条件(b)：要么 v 必须是 S 中所有 Acceptor 接受过的、编号小于 n 的提案中编号最大的那个提案的值——这确保了如果之前已经有提案被接受，新的提案必须沿用那个值
为什么需要两阶段？
P2c 揭示了为什么 Paxos 需要两个阶段：
阶段1（Prepare）的目的：Proposer 需要知道是否存在某个多数派集合 S，以及 S 中是否有 Acceptor 已经接受过提案。这正是为了满足 P2c。
阶段2（Accept）的目的：在了解了历史情况后，Proposer 才能安全地发出提案。
不变量的维护
/**
* Paxos 不变量维护的详细实现
*/
public class PaxosInvariantMaintenance {
/**
* Acceptor 状态（需要持久化）
*/
static class AcceptorState {
int promisedNumber = 0; // 承诺过的最大提案编号
int acceptedNumber = 0; // 接受过的最大提案编号
String acceptedValue = null; // 接受过的提案值
}
/**
* Prepare 阶段：满足 P2c 的条件检查
*/
public PrepareResponse prepare(AcceptorState state, int proposalNumber) {
// 关键规则：只对编号更大的提案做出承诺
// 这确保了 P2c 条件 (a) 的检查
if (proposalNumber > state.promisedNumber) {
state.promisedNumber = proposalNumber;
// 返回已接受的提案（如果有）
// 这让 Proposer 能够满足 P2c 条件 (b)
return new PrepareResponse(
true, // 承诺成功
state.acceptedNumber, // 已接受的提案编号
state.acceptedValue // 已接受的值
);
}
// 编号太小，拒绝
return new PrepareResponse(false, 0, null);
}
/**
* Accept 阶段：确保不会违反之前的承诺
*/
public AcceptResponse accept(AcceptorState state, int proposalNumber, String value) {
// 关键规则：只接受编号不小于已承诺编号的提案
// 这维护了 Prepare 阶段做出的承诺
if (proposalNumber >= state.promisedNumber) {
state.promisedNumber = proposalNumber;
state.acceptedNumber = proposalNumber;
state.acceptedValue = value;
return new AcceptResponse(true);
}
// 违反了承诺，拒绝
return new AcceptResponse(false);
}
/**
* Proposer 如何选择值以满足 P2c
*/
public String chooseValue(List<PrepareResponse> responses) {
String chosenValue = null;
int highestNumber = 0;
// 从多数派的响应中选择编号最大的已接受值
for (PrepareResponse resp : responses) {
if (resp.acceptedValue != null && resp.acceptedNumber > highestNumber) {
highestNumber = resp.acceptedNumber;
chosenValue = resp.acceptedValue;
}
}
// 如果没有已接受的值，可以自由选择
// 如果有，必须使用已接受的值
// 这正是 P2c 的要求
return chosenValue != null ? chosenValue : "my_proposed_value";
}
}
形式化证明的直觉理解
Paxos 的正确性可以通过数学归纳法证明。核心思路是：
-
基础情况：第一个被选定的提案，其值由 Proposer 自由选择（条件 a）
-
归纳假设：假设编号为 m 的提案被选定，其值为 v
-
归纳步骤：证明任何编号为 n > m 的被选定提案，其值也必须是 v
- 由于提案 m 被选定，存在一个多数派集合 C，其中每个 Acceptor 都接受了提案 m
- 提案 n 要被选定，需要另一个多数派集合 S 接受它
- 由于 C 和 S 都是多数派，它们至少有一个共同成员（Quorum 的交集性质）
- 根据 P2c，提案 n 的值必须由 S 中编号小于 n 的最大提案决定
- 而 S 中至少有一个成员同时也接受了提案 m（编号为 m）
- 因此，如果 n 要被选定，其值必须是 v
这个证明展示了 Paxos 安全性的本质：Quorum 的交集性质确保了信息的传递，而两阶段协议确保了 Proposer 能够获知这些信息。
Multi-Paxos
Multi-Paxos是Paxos的优化版本，用于在分布式系统中实现连续的共识：
// Multi-Paxos：连续共识
class MultiPaxosLog {
private int logIndex = 0;
private Map<Integer, String> log = new HashMap<>();
private int committedIndex = -1;
// 客户端请求
public void append(String command) {
// 1. 选择Leader（使用Paxos）
String leader = electLeader();
// 2. Leader直接接受命令（跳过准备阶段）
int index = logIndex++;
accept(leader, index, command);
// 3. 复制到其他节点
replicateToAll(index, command);
// 4. 多数派确认后提交
if (replicatedToMajority(index)) {
committedIndex = index;
}
}
}
Raft 算法
Raft是另一种流行的共识算法，相比Paxos更易于理解和实现。
算法概述
Raft将共识问题分解为三个子问题：
Leader 选举
// Raft节点状态
enum NodeState {
FOLLOWER, // 跟随者
CANDIDATE, // 候选人
LEADER // 领导者
}
// Raft节点
class RaftNode {
private NodeState state = NodeState.FOLLOWER;
private long currentTerm = 0; // 当前任期
private String votedFor = null; // 投票给谁
private String leaderId = null; // 当前Leader ID
// 选举超时计时器
private long electionTimeout;
private long lastHeartbeatTime;
// 处理心跳
public void handleRequestVote(RequestVote request) {
// 1. 如果term更大，更新自己的term
if (request.getTerm() > currentTerm) {
currentTerm = request.getTerm();
state = NodeState.FOLLOWER;
votedFor = null;
}
// 2. 判断是否投票
boolean voteGranted = false;
if (request.getTerm() >= currentTerm) {
// 尚未投票，或投票给请求者
if (votedFor == null || votedFor.equals(request.getCandidateId())) {
// 检查日志是否足够新
if (isLogNewer(request.getLastLogTerm(), request.getLastLogIndex())) {
voteGranted = true;
votedFor = request.getCandidateId();
}
}
}
// 3. 响应
sendResponse(new RequestVoteResponse(currentTerm, voteGranted));
}
// 成为候选人并发起选举
public void startElection() {
state = NodeState.CANDIDATE;
currentTerm++; // 增加term
votedFor = nodeId; // 投票给自己
// 并行发送投票请求
for (RaftNode node : cluster) {
if (!node.equals(this)) {
sendRequestVote(node, new RequestVote(currentTerm, nodeId, lastLogTerm, lastLogIndex));
}
}
// 等待投票结果...
}
}
日志复制
// 日志条目
class LogEntry {
private long term; // 任期号
private long index; // 日志索引
private String command; // 命令
private boolean committed; // 是否已提交
}
// 日志复制流程
class LogReplication {
// Leader处理客户端请求
public void appendEntries(String command) {
// 1. 添加到本地日志
LogEntry entry = new LogEntry(currentTerm, nextIndex.get(nodeId), command);
log.add(entry);
// 2. 并行复制到所有跟随者
Map<RaftNode, Integer> nextIndices = new HashMap<>();
for (RaftNode follower : cluster) {
if (!follower.equals(this)) {
// 从nextIndex开始复制
List<LogEntry> entries = log.subList(nextIndices.get(follower), log.size());
sendAppendEntries(follower, entries);
}
}
// 3. 多数派确认后提交
if (countReplicated() >= majority) {
commit(log.size() - 1);
}
}
// 跟随者处理日志条目
public AppendEntriesResponse handleAppendEntries(AppendEntries request) {
// 1. 检查term
if (request.getTerm() < currentTerm) {
return new AppendEntriesResponse(currentTerm, false);
}
// 2. 检查日志一致性
if (!matchLog(request.getPrevLogIndex(), request.getPrevLogTerm())) {
return new AppendEntriesResponse(currentTerm, false);
}
// 3. 添加新日志条目
for (LogEntry entry : request.getEntries()) {
if (!log.get(entry.getIndex()).equals(entry)) {
// 删除不匹配的条目及其后的条目
log.subList(entry.getIndex(), log.size()).clear();
log.add(entry);
}
}
// 4. 更新commitIndex
if (request.getLeaderCommit() > commitIndex) {
commitIndex = Math.min(request.getLeaderCommit(), log.size() - 1);
}
return new AppendEntriesResponse(currentTerm, true);
}
}
Raft vs Paxos
| 特性 | Paxos | Raft |
|---|---|---|
| 复杂性 | 难以理解 | 更易于理解 |
| 领导人 | 无明确Leader | 有明确的Leader |
| 日志 | 分散 | 集中管理 |
| 可理解性 | 难 | 易 |
| 实现难度 | 困难 | 相对简单 |
成员变更（Membership Change）
在实际生产环境中，集群的节点配置经常需要变更：添加新节点、移除故障节点、或调整副本数量。Raft使用**联合共识（Joint Consensus）**机制来安全地处理这类配置变更。
为什么需要联合共识？
直接切换配置存在双Quorum问题：假设从配置变更为，在切换过程中可能同时存在两个不相交的多数派（如和），导致同时选出两个Leader，破坏共识安全性。
联合共识的两阶段变更
// 联合共识配置变更
class MembershipChange {
// 阶段1：进入联合配置 C_old,new
// 此时需要 OLD配置的大多数和新配置的大多数都同意才能达成共识
public void enterJointConsensus() {
// Leader 将配置 {C_old, C_new} 作为日志条目写入
// 任何选举和提交都需要 OLD 和 NEW 两个配置的大多数分别同意
Configuration jointConfig = new Configuration(oldMembers, newMembers);
log.append(new ConfigChangeEntry(jointConfig));
}
// 阶段2：切换到新配置 C_new
// OLD配置的大多数不再需要，只需要 NEW 配置的大多数
public void transitionToNewConfig() {
Configuration newConfig = new Configuration(newMembers);
log.append(new ConfigChangeEntry(newConfig));
}
}
联合共识的关键特性：
- 日志复制到所有节点：新配置条目会复制到和中的所有服务器
- 任何配置下的节点都可能成为Leader：允许来自或的任何服务器成为Leader
- 分离的大多数：需要和分别的多数派同意才能达成共识
单步成员变更
当成员变更只涉及添加或删除单个节点时，可以使用更简单的单步方法。这要求和的多数派必须有重叠节点：
// 单步成员变更 - 只能添加或删除一个节点
class SingleStepMembershipChange {
// 添加单个节点
public boolean addServer(String newServerId) {
// 检查当前配置和新配置是否有重叠多数派
// 只有当变化是单个节点时才能保证安全性
return checkQuorumOverlap(currentConfig, newConfig) > 0;
}
}
这种方法的限制：
- 每次只能变更一个节点
- Cluster membership change必须是渐进的
- 实现相对更简单，但功能有限
日志压缩与快照
随着系统运行，日志会无限增长。Raft使用**快照（Snapshot）**机制来压缩日志：
// 快照机制
class SnapshotManager {
// 创建快照：保存当前状态机状态
public void createSnapshot() {
// 1. 获取当前状态机的完整状态
byte[] stateMachineState = stateMachine.saveState();
// 2. 记录快照元数据
SnapshotMetadata metadata = new SnapshotMetadata(
lastIncludedIndex, // 快照包含的最后一个日志索引
lastIncludedTerm, // 快照包含的最后一个日志任期
configuration // 当时的配置
);
// 3. 保存到持久化存储
saveToDisk(metadata, stateMachineState);
// 4. 丢弃快照之前的日志
discardOldEntries(upToLastIncludedIndex);
}
// 接收并应用快照
public void receiveSnapshot(SnapshotMetadata metadata, byte[] state) {
// 1. 检查快照是否比当前日志更新
if (metadata.lastIncludedIndex <= commitIndex) {
return; // 忽略过时的快照
}
// 2. 应用到状态机
stateMachine.restoreState(state);
// 3. 更新本地日志
log.truncateAfter(metadata.lastIncludedIndex);
lastIncludedIndex = metadata.lastIncludedIndex;
lastIncludedTerm = metadata.lastIncludedTerm;
}
}
快照的优势：
- 减少磁盘空间：删除已快照的日志条目
- 加速新节点加入：新节点可以直接从Leader获取快照，而不是重放所有日志
- 提高性能：减少日志复制和重放的复杂度
Raft在实际系统中的应用
Raft被广泛用于以下生产系统：
| 系统 | 使用场景 | 特点 |
|---|---|---|
| etcd | 分布式键值存储 | Raft实现的首选参考 |
| Consul | 服务发现与配置 | 支持多数据中心 |
| TiKV | 分布式事务数据库 | 继承自Google Spanner设计 |
| CockroachDB | 分布式SQL数据库 | 支持强一致性事务 |
| Redpanda | 流处理平台 | 高性能Kafka替代品 |
以etcd为例，其Raft实现特点：
- leader lease：Leader使用租约机制，简化逻辑
- pre-vote：使用预投票避免节点重新加入时干扰
- confchange（配置变更）：实现单步成员变更API
- snapshot: 支持定期快照和流式快照传输
[!TIP] 学习Raft实现的最佳方式是阅读etcd/raft的源代码，它是许多其他系统的基础。
ZAB 协议
ZAB是ZooKeeper使用的原子广播协议，与Raft类似但有一些细节差异。
ZAB 工作流程
共识算法的选择
| 场景 | 推荐算法 | 典型系统 |
|---|---|---|
| 配置管理 | Raft | Etcd, Consul |
| 分布式协调 | ZAB | ZooKeeper |
| 分布式存储 | Multi-Paxos | Chubby |
Google Spanner 与 TrueTime
Google Spanner 是分布式数据库领域的里程碑式系统，它首次实现了全球分布数据的强一致性事务。其核心创新在于 TrueTime API，通过硬件时钟同步解决了分布式系统中时间不确定性的根本问题。
分布式系统的时间难题
在分布式系统中，不同机器的时钟不可能完全同步。即使使用 NTP（Network Time Protocol）进行时间同步，时钟之间仍然存在毫秒甚至秒级的误差。这个看似微小的时间差异，却给分布式事务带来了巨大的挑战。
考虑一个跨境转账场景：用户 A 在北京向用户 B 在纽约转账。两地服务器的时钟可能有 100ms 的差异。如果简单地用本地时间戳来排序事务，可能导致事务顺序错乱，破坏数据一致性。
传统分布式事务协议（如 2PC）通过锁机制保证一致性，但代价是性能低下。Spanner 的创新在于：通过精确的时间同步，让全局时间戳成为可能，从而实现无锁的只读事务。
TrueTime API
TrueTime 是 Spanner 的核心创新。它不追求"准确"的时间，而是明确表示时间的"不确定性"。
TrueTime 将时间表示为一个有界的区间 ，而不是一个确定的时间点。区间宽度反映了时间的不确定性，通常在 1-7 毫秒之间。
TrueTime API:
TT.now() 返回 TTinterval{earliest, latest}
表示当前真实时间一定在这个区间内
TT.after(t) 如果 t 已经确定过去，返回 true
等价于: TT.now().earliest > t
TT.before(t) 如果 t 还没有到来，返回 true
等价于: TT.now().latest < t
这个设计蕴含着一个深刻的洞见：与其假装知道准确时间，不如承认时间的不确定性，并在 API 层面显式表达出来。
TrueTime 的硬件实现
TrueTime 的低不确定性依赖于 GPS 时钟和原子钟的组合。
每个数据中心部署一组时间参考服务器（Time Master），其中混合了 GPS 时钟和原子钟。GPS 时钟通过与卫星通信获得精确时间，但容易受天线故障、信号干扰等影响。原子钟自主运行，不受外部干扰，但存在漂移问题。两种时钟具有不同的故障模式，组合使用可以相互校验。
每台服务器运行一个时间守护进程，定期轮询多个时间参考服务器（本地和远程的 GPS 时钟、原子钟）。守护进程使用 Marzullo 算法检测并剔除异常的时间源，然后将本地时钟同步到正常的时间源。
两次同步之间，守护进程会逐步增加时间不确定性。不确定性来源于：
- 本地时钟的最坏情况漂移
- 时间参考服务器的不确定性
- 与时间参考服务器通信的延迟
这种设计导致时间不确定性呈现锯齿状模式：同步后不确定性很低，然后逐渐增加，直到下次同步。
时间不确定性锯齿图：
不确定性 (ms)
│
7 ┤ ╱╲ ╱╲
│ ╱ ╲ ╱ ╲
4 ┤ ╱ ╲ ╱ ╲
│ ╱ ╲ ╱ ╲
1 ┤────╱────────╲╱────────╲────
└─────────────────────────────→ 时间
同步 下次 同步 下次
外部一致性
Spanner 引入了外部一致性（External Consistency）的概念，这是比线性一致性更强的保证。
线性一致性要求系统看起来像是在单一时间点上执行所有操作。外部一致性则更进一步：如果事务 T1 的提交发生在事务 T2 的开始之前（按真实的物理时间），那么 T1 的时间戳必须小于 T2 的时间戳。
外部一致性确保了分布式系统的事件顺序与物理世界的顺序一致。这对于需要严格顺序保证的应用（如财务系统）至关重要。
Spanner 通过两个关键机制实现外部一致性：
时间戳分配规则：事务协调者为事务分配的时间戳 必须大于 TT.now().latest。这保证了时间戳总是"保守"的——不会早于任何可能的真实时间。
提交等待（Commit Wait）：在事务提交后，协调者必须等待 TT.after(s) 为 true，才能向客户端返回成功。这保证了时间戳 确实已经成为"过去"的时间。
// Spanner 事务的时间戳分配（概念性伪代码）
public Timestamp commitTransaction(Transaction txn) {
// 1. 分配时间戳：必须大于 TT.now().latest
Timestamp s = TT.now().latest;
s = max(s, previousTimestamp + 1); // 保证单调递增
// 2. 执行两阶段提交，获取参与者锁
preparePhase(txn);
// 3. 提交等待：确保时间戳 s 已经过去
while (!TT.after(s)) {
// 等待真实时间超过 s
// 这段时间约为 2 * 平均时钟误差
}
// 4. 真正提交
commitPhase(txn, s);
return s;
}
提交等待的时间预期约为 ，其中 是平均时钟误差。在 Google 的数据中心，这通常只有几毫秒。
无锁只读事务
TrueTime 最强大的应用是实现了无锁的只读事务。
在传统分布式数据库中，只读事务需要获取读锁或使用快照隔离，仍然会对写事务产生干扰。Spanner 的只读事务完全不需要锁：
- 系统为只读事务分配一个时间戳
- 在任意足够新的副本上执行读取（时间戳 ）
- 读取结果保证是时间戳 时刻的一致快照
这种设计的关键是 Spanner 可以确定每个副本在哪些时间戳上是"足够新"的。每个副本维护一个 值，表示该副本能够提供服务的最新时间戳。只有当 时，副本才能服务该只读事务。
的计算综合考虑了 Paxos 复制进度和进行中的事务：
- ：副本上最后一条 Paxos 写入的时间戳
- ：考虑未提交事务的时间戳下界
Spanner 架构概览
Spanner 采用分层架构管理全球分布的数据：
Universe：一个 Spanner 部署实例，包含多个数据中心。
Zone：一个管理单元，通常对应一个数据中心。每个 Zone 包含一组 spanserver。
Spanserver：负责存储数据和提供服务。每个 spanserver 管理多个 tablet（数据分片）。
Directory：数据放置的单位。具有共同前缀的 key 存储在同一个 Directory，可以整体迁移。
Paxos Group：每个 Directory 的多个副本组成一个 Paxos 组，通过 Paxos 协议保证副本一致性。
Spanner 分层架构：
Universe
├── Zone 1 (美国东部)
│ ├── Spanserver 1-1
│ │ ├── Tablet 1 (Paxos Group 1 Leader)
│ │ └── Tablet 2 (Paxos Group 2 Follower)
│ └── Spanserver 1-2
│ └── Tablet 1 (Paxos Group 1 Follower)
│
├── Zone 2 (欧洲)
│ └── Spanserver 2-1
│ └── Tablet 1 (Paxos Group 1 Follower)
│
└── Zone 3 (亚洲)
└── ...
Spanner 的 Paxos 实现使用带租约的 Leader 机制。Leader 通过获取多数派的租约投票来维持领导地位。租约默认 10 秒，可以通过写操作自动续期。Leader 租约机制确保同一时刻只有一个 Leader，避免了频繁的选举开销。
Spanner 与传统共识算法的比较
Spanner 的设计与 Raft、ZAB 等共识算法有几个关键区别：
| 特性 | Raft/ZAB | Spanner |
|---|---|---|
| 时间模型 | 逻辑时钟（任期号） | 物理时钟（TrueTime） |
| 一致性保证 | 线性一致性 | 外部一致性 |
| 只读操作 | 需要 Leader 或 Quorum Read | 无锁快照读 |
| 跨分片事务 | 需要额外协调 | 原生支持 |
| 部署范围 | 单一数据中心 | 全球分布 |
Spanner 的 TrueTime 机制使其能够支持跨数据中心的强一致性事务，这是传统共识算法难以实现的。但 TrueTime 的代价是需要专门的硬件设施（GPS 时钟、原子钟），这限制了其在普通环境中的应用。
CockroachDB 和 TiDB 等 NewSQL 数据库借鉴了 Spanner 的设计思想，但使用软件方式模拟 TrueTime（如使用 NTP 时钟和更大的时间不确定性区间），在可用性和一致性之间做了不同的权衡。
小结
本章我们深入学习了分布式共识算法：
-
FLP不可能性
- 异步分布式系统中无法同时满足安全性和活性
- 实际系统中通过超时、随机化等近似解决
-
Paxos算法
- 共识问题的经典解法
- Prepare和Accept两个阶段
- Multi-Paxos用于连续共识
-
Raft算法
- 更易于理解的共识算法
- Leader选举、日志复制、安全性
- 分离的领导人选举和日志复制
-
ZAB协议
- ZooKeeper使用的原子广播协议
- 发现、同步、广播三个阶段
-
Google Spanner 与 TrueTime
- TrueTime API 显式表示时间不确定性
- 硬件时钟同步实现低不确定性的全局时间
- 外部一致性保证物理时间顺序
- 无锁只读事务大幅提升性能
-
算法选择
- 单数据中心：Raft、ZAB
- 全球分布：Spanner 或其开源实现
- 不同场景需要权衡一致性、性能、部署成本