# 第 34 章 分布式理论：CAP、共识与一致性
> CAP 与一致性模型给出"能承诺什么"，Raft 给出"怎么做到"，分布式事务、ID、锁、限流与分片则是这套理论在工程里的六张落地账单。
## 学习目标
读完本章，你应当能够：
1. 用 C/A/P 的准确定义破除"三选二"误读，说出分区发生时真正的二选一，并用 PACELC 给 `Cassandra`/`HBase`/`MongoDB`/`MySQL` 主从定位；
2. 按强弱排出线性一致、顺序一致、因果一致、最终一致的谱系，并用具体执行历史区分线性一致与顺序一致；
3. 独立推导 Raft 的选举超时随机化、`AppendEntries` 一致性检查、`commitIndex` 推进规则，以及**为什么不能直接提交旧任期的日志**（Figure 8 式反例）；
4. 说出 Paxos 两阶段的活锁成因与 Multi-Paxos 的改进点，并辨析 Raft 与 ZAB 的模型差异；
5. 列出六种分布式事务方案各自的不一致窗口，与六种分布式 ID 方案的失效场景；
6. 说清四种分布式锁各在什么时候不安全，以及 `Redlock` 争议的结论与 fencing token 的位置；
7. 算出一致性哈希下取模扩容的键迁移比例，说明虚拟节点为什么能消除倾斜。
### 前置知识检查
| 你需要知道 | 在哪一节补齐 |
|---|---|
| Redis 的 `SET NX PX`、`Lua` 释放锁、看门狗与主从异步复制 | 见第 27 章 27.11 节；本章只做理论对比与缺陷分析 |
| 主从复制模式、复制延迟与脑裂 | 见第 26 章 26.1、26.2 节 |
| MQ 的可靠投递、重复消费与幂等原语 | 见第 33 章 33.2、33.4 节；接口幂等落地见第 35 章 |
| 事务 ACID、redo/undo、两阶段提交 | 见第 21 章 21.5 节、第 22 章 22.1 节 |
| 哈希函数、环形结构、树与多数派计数 | 数据结构课程内容；本章直接进机制 |
## 34.1 CAP 的准确表述与 PACELC
### 34.1.1 先把三个字母的定义读准
面试里九个候选人里九个会说"CAP 是三选二"，这是本章第一个要拆掉的错误。CAP 出自 Brewer 的猜想与 Gilbert、Lynch 的证明，三个字母的准确含义是：
- **C = 线性一致性（linearizability）**，不是"数据一致"。它要求整个系统对外表现得像**只有一个副本、且每个操作在其调用与返回之间的某一瞬间原子生效**。注意这是一个**强到苛刻**的模型：它同时约束了"所有节点看到同一顺序"和"这个顺序必须与真实时间兼容"。很多系统自称"强一致"，实际只做到顺序一致或读己之写。
- **A = 可用性**，准确定义是"**每一个非故障节点收到的每一个请求，都能在有限时间内返回一个非错误响应**"。关键词是"非故障节点"与"非错误响应"：超时不算可用、返回 `503` 不算可用、返回可能过期的数据**算**可用。所以 A 不等于"高可用"，它是**有界响应性**。
- **P = 分区容忍**，指网络被切成若干互不可达的子集时系统仍能继续运行。这里的"分区"是**网络分区**（network partition），不是数据分区（sharding）。
> [!CAUTION]
> 把 A 理解成"高可用（99.99%）"是本条最危险的答法。可用性是"是否在有界时间内给出非错误响应"，而通常说的"高可用"是年度可用率指标。二者相关但不同：一个每次都在 1 ms 内返回 `500` 的系统可用性定义上不满足 A，但它可能很"少宕机"。面试官听到"高可用"就会追问"那 A 和 SLA 里的可用率是什么关系"，答不上就崩。
### 34.1.2 "三选二"错在哪
"三选二"隐含一个前提：三者权重相同、可以任意舍弃一个。两个错误：
1. **P 不是可选项**。只要系统跨网络部署，交换机故障、GC 长暂停、网线被拔都会产生分区。分区不是"要不要"的问题，而是"什么时候发生"的问题。既然 P 必须保留，"三选二"就退化成**二选一，且只在分区期间**。
2. **CA 系统在分布式语境下不存在**。单机数据库满足 CA（没有分区可言），但一旦跨机，就必须面对分区。
所以正确表述是：**在分布式系统中 P 是前提，真正的选择是"分区发生时，宁可拒绝服务以保证线性一致（CP），还是宁可返回可能陈旧或冲突的数据以保证可用（AP）"**。而且这个选择**只在分区窗口内生效**——没有分区时，CAP 什么都不约束，这正是 PACELC 要补的那一半。
### 34.1.3 PACELC：没有分区时的另一半账
PACELC（读作 "pass-el-see"）由 Abadi 提出，把 CAP 补全为两段：**if Partition then A else L, else C** —— 即"分区时在 A 与 C 之间选；**否则（Else）在延迟 L 与一致性 C 之间选**"。
第二段才是日常态。以三副本为例：`MongoDB` 的多数派写（`w:majority`）要等两个副本确认，比 `w:1` 多出一个跨机房往返；单机房 RTT 约 0.1~0.5 ms，跨可用区往往按毫秒到几十毫秒计，跨大洲约 150 ms。**同步复制用延迟买一致性，这就是 `C` 与 `L` 的交换**。
| 系统 | 分区时的选择 | 无分区时的选择 | 类别 | 原因 |
|---|---|---|---|---|
| `Cassandra` | 多数派可用即可读写 | 默认 `ONE` 级读写，可调 `QUORUM` | PA/EL | 无主多写，副本异步收敛，一致性级别由客户端逐次指定 |
| `HBase` | 分区时 Region 不可用 | 强一致读写，`WAL` + 单 Region 单写者 | PC/EC | 依赖 `HDFS`，RegionServer 故障期间该 Region 阻塞 |
| `MongoDB` | 主节点不可写，等选举 | 默认 `w:1` 时近 EL，`w:majority` 时 EC | PC/EC（可调） | 单主复制，写关注级别决定落在哪一档 |
| `MySQL` 主从（异步） | 主库不可写，需切主 | 主库提交即返回，从库异步追 | PC/EL | 复制是异步的，读从库可能落后，延迟最低 |
| `ZooKeeper`/`etcd` | 少数派侧拒绝服务 | 写走多数派，读可线性化 | PC/EC | 共识协议要求多数派，天然 CP |
> [!NOTE]
> PACELC 把"系统属于哪一类"从静态标签变成了**可调的旋钮**。同一个 `Cassandra` 集群，`ONE` 级读是 EL，`QUORUM` 读就靠近 EC。面试时先说清"这个系统的默认配置落在哪一档"，再谈调参后怎么移动，比背一个标签更有说服力。
### 34.1.4 BASE 与柔性事务
BASE（Basically Available, Soft state, Eventually consistent）是 AP 路线的工程口号，与 ACID 相对。它的准确落点是**放弃"事务边界的原子性由数据库保证"，把原子性移交应用层**：允许中间态被外部观察（软状态）、允许读暂时陈旧（最终一致），用**柔性事务（flexible transaction）**换可用性与吞吐。柔性事务的共同特征是"**没有全局锁或全局锁只持有极短时间**，一致性由**重试、补偿、对账**三条路兜住"，具体六种方案见 34.5 节。判断一个方案是刚是柔，只问一句：**它有没有在一段时间内让某个资源全局不可用？** 有就是刚性（如 `2PC`），没有就是柔性。
## 34.2 一致性模型谱系
一致性模型不是"程度的形容词"，而是一条**从强到弱、可用性和延迟逐级改善**的谱系。判断一个历史是否合法，看它是否满足对应模型的约束。
| 模型 | 约束 | 反例（不满足的情形） | 典型代价 |
|---|---|---|---|
| 线性一致（linearizable） | 存在一个全序，且该全序与真实时间兼容；读读到的是"最近一次已完成写" | 写返回后立刻读仍读到旧值 | 每次写要多数派确认，跨机房 RTT 进入关键路径 |
| 顺序一致（sequential） | 所有节点看到**同一个**操作全序，且保持每个进程内部的程序顺序；**但不要求与真实时间一致** | 两个节点对同一批操作的顺序不一致 | 需要一个全局定序者或共识，但读可以走本地 |
| 因果一致（causal） | 只对有因果关系的操作保序（写后读、读后写、传递闭包）；并发操作可任意排序 | 同一进程先写后读，读却看不到自己的写 | 需要跟踪因果依赖（版本向量、依赖时钟） |
| 最终一致（eventual） | 停止写入后，经过有限时间所有副本收敛到同一值 | 一直有写入时任意陈旧 | 几乎零协调成本，冲突需应用层解决 |
**线性一致与顺序一致的真实差别在"时间"上。** 例子：`P1` 写 `x=1` 并在 `t=10` 返回；`P2` 在 `t=20` 发出读，`t=21` 返回 `x=0`；同时 `P3` 也读 `x`。顺序一致是**可以允许**这个历史的——只要所有节点一致地认为"`P2`、`P3` 的读排在 `P1` 的写之前"这个全序成立，就满足顺序一致（程序顺序没被违反，因为 `P2` 的读和 `P1` 的写来自不同进程）。但线性一致**不允许**：写在 `t=10` 已完成，读在 `t=20` 才开始，两者在真实时间上不重叠，读必须看到 `x=1`。
> [!IMPORTANT]
> 一句话记牢：**线性一致 = 顺序一致 + 真实时间约束**。只满足"大家看到同一顺序"的寄存器（如某些顺序一致但非实时的共享内存）可以出现"写已完成，之后开始的读却读不到"的现象，这在顺序一致下合法、在线性一致下非法。这也是 `ZooKeeper` 默认读（可走 Follower 本地）只能给顺序一致、要线性化读必须显式 `sync` 的原因。
因果一致是工程上性价比最高的一档：它恰好挡住"评论先于原帖可见"这类反直觉现象，同时不要求全局协调。**CAP 里的 A 与 C 之争，实际是"要不要线性一致"之争**；如果只要求因果一致或最终一致，很多 AP 系统就能同时给出可用性与可接受的一致性。
> [!TIP]
> 面试话术：被问"最终一致是不是就是很弱"，答"它的强项是**收敛性有界**——停止写入后有界时间收敛，冲突用 LWW/版本向量/CRDT 解决；它不是'不保证',而是'保证的东西更少但可用性更高'"，然后主动给一个"同一商品在两个机房看到不同库存"的业务例子。
## 34.3 Raft：从选举到提交的完整推导
### 34.3.1 三种角色、任期与状态
Raft 把节点分为 `Leader`、`Follower`、`Candidate` 三种角色，并把时间切成递增的**任期（term）**（连续整数）。每个节点持久化 `currentTerm` 和 `votedFor`，`term` 的作用是给所有消息与日志条目打上**单调的逻辑时间戳**，让节点能一眼判断"这条消息是否过期"。
```
选举超时（150~300 ms 随机）
▼
┌──────────┐ 超时 ┌───────────┐ 拿到多数票 ┌────────┐
│ Follower │────────▶│ Candidate │──────────────▶│ Leader │
└──────────┘ └───────────┘ └────────┘
▲ │ 发现更大 term / │
│ │ 同 term 已有 Leader │ 发现更大 term
└─────────────────────┴────────────────────────┘
全部角色：收到更大 term 的消息 → 立刻退回 Follower 并更新 currentTerm
```
每个节点还维护两个**易失**索引，这是 34.3.3 全部推导的基础：`commitIndex`（已知被多数派持久化的最高日志下标，**可安全应用到状态机**）与 `lastApplied`（已应用到状态机的最高下标）；`Leader` 额外维护每个 `Follower` 的 `nextIndex`（下一条要发的下标）与 `matchIndex`（已确认复制到的最高下标）。
> [!NOTE]
> `commitIndex` 与 `lastApplied` 分离是必须的：提交是"复制到位"的事实，应用是"执行到状态机"的动作，两者之间隔着一次批量应用。这也是 Raft 状态机可以做到"日志先落盘、状态机稍后追"的原因。
### 34.3.2 选举：随机化超时为什么是必需品
`Follower` 在选举超时内没收到任何 `AppendEntries` 或投票请求，就自增 `currentTerm`、投自己一票、转为 `Candidate`，向所有节点并发发 `RequestVote`。
`RequestVote` 的关键参数与投票规则：
- 参数：`term`（候选人任期）、`candidateId`、`lastLogIndex`、`lastLogTerm`。
- 投票条件（两条都必须满足）：**`term` 不小于自己的 `currentTerm`**，且**候选人的日志"至少和我一样新"**。日志新旧的比较是：先比最后一条日志的 `term`，大者更新；`term` 相同再比 `lastLogIndex`，大者更新。
- 拿到**多数派（N/2 + 1）**选票才当选；每个任期每个节点只投一票（`votedFor` 持久化，防止重启后重复投票）。
为什么要随机化超时？假设所有节点固定在同一个超时时间。它们会几乎同时超时、同时进入 `Candidate`、同时把票投给自己。`N` 个节点分成 `N` 份选票，**没有任何人拿到多数派**（这是"选票瓜分",split vote），然后所有人同时等待下一个同样的超时，再次同时开选——系统可以**无限期无法选出 Leader**。
```
固定超时（全部 150 ms） 随机超时（150~300 ms）
t=0 所有节点同时超时 最先超时的节点（如 173 ms）率先发 RequestVote
t=0+ 各投自己 → 票数 1,1,1,1,1 其余节点还在等待，未投票 → 票全部给它
t=150 同时重来 → 再瓜分 当选，发心跳，其余节点重置计时器
⇒ 可能永远选不出来 ⇒ 冲突概率被压到很低，且每轮重试都独立
```
随机区间通常取 `150~300 ms`（Raft 论文口径）；网络 RTT 越大、节点越多，区间要相应放宽，但要保证**随机上限明显小于"业务可容忍的选举中断时间"**，否则每次换主都要停顿几百毫秒。
> [!WARNING]
> 心跳间隔必须**远小于**选举超时下限（论文建议心跳约 100 ms 量级、超时下限 150 ms 量级）。如果心跳间隔接近超时下限，网络抖动就会让 Follower 频繁误判 Leader 已死并发动无谓选举，`term` 疯涨、集群反复换主。这是"集群莫名反复选主"最常见的配置根因。
### 34.3.3 日志复制：两条索引与一次一致性检查
`Leader` 收到客户端请求后，先追加到本地日志，再向所有 `Follower` 并发发 `AppendEntries`，携带新条目以及两个"锚点"：**`prevLogIndex`（紧邻新条目之前的日志下标）与 `prevLogTerm`（该条目的任期）**。
```
Leader (term=5) 日志：[1:1][2:1][3:2][4:3][5:5] Follower A 日志：[1:1][2:1][3:2][4:3]
▲ ▲
nextIndex[A]=5 matchIndex[A]=4
AppendEntries(term=5, prevLogIndex=4, prevLogTerm=3, entries=[idx5,term5])
Follower 检查：自己 idx4 的 term 是 3 == prevLogTerm 3 → 接受，追加 idx5
→ Leader 收到成功：matchIndex[A]=5，nextIndex[A]=6
```
Follower 的两条规则：**`prevLogIndex` 处的条目必须存在且 `term` 等于 `prevLogTerm`，否则拒绝**（并可直接带上自己冲突位置的提示以加速回退）；接受后若新条目与已有条目冲突，**删除从冲突点开始的全部后续条目**再追加。
拒绝时 Leader 的处理是**回退重试**：把该 Follower 的 `nextIndex` 减一，重新发上一轮的 `AppendEntries`，直到找到双方一致的那个点。这是一次"二分式的逐条回退"，最坏要退到 `nextIndex=1`。优化手段是让 Follower 在拒绝响应里直接回报冲突条目的 `term` 与该 `term` 的首个下标，Leader 一次跳过整个冲突任期，把 O(日志长度) 次往返降到 O(冲突任期数) 次。
> [!TIP]
> 面试加分句：`nextIndex` 是**乐观的 Leader 侧猜测**（初值 `lastLogIndex+1`），`matchIndex` 是**已被证实的复制进度**（初值 0）。一条日志"在多数节点的 `matchIndex` 之上"才是可提交的候选；`nextIndex` 只用来决定下一次发什么。
### 34.3.4 commitIndex 的推进规则与"不能提交旧任期日志"
Leader 的提交规则有两条，缺一不可：
1. **只有当前任期的日志条目才能通过"计数多数派"直接提交**；
2. 一旦当前任期的某条目被提交，**它之前的所有条目（含旧任期的）也被连带提交**——因为被提交的条目在所有日志中都位于更早的位置，Followers 的日志按 Raft 日志匹配性质与 Leader 一致。
为什么不能直接提交旧任期日志？用 Figure 8 式反例逐步推。设 5 个节点 `S1`~`S5`，多数派 = 3。
```
时刻① 任期2，Leader=S1。追加了 idx2=term2 的条目，只复制到 S1、S2（未过半数）→ 不可提交
S1:[1:1][2:2] S2:[1:1][2:2] S3:[1:1] S4:[1:1] S5:[1:1]
时刻② S1 宕机。S5 在任期3 当选（S3、S4、S5 投票），追加 idx2=term3 的条目，未提交
S1:--宕机-- S2:[1:1][2:2] S3:[1:1][2:3] S4:[1:1][2:3] S5:[1:1][2:3]
时刻③ S5 与 S3、S4 相继宕机；S1 重启并在任期4 当选（S1、S2 投票，S3/S4/S5 不在）
S1 把 idx2=term2 复制给 S3、S4、S5，此时 idx2=term2 已在 {S1,S2,S3,S4,S5} 多数派上
```
此刻如果 Raft 允许"**只要某条旧任期日志落在多数派上就提交它**"，则 `idx2=term2` 被提交，进而 `idx2=term3`（S5 那条）也被连带提交。但时刻③ 之后 S5 若再次当选并能复制日志，它会把 `idx2=term2` **覆盖**掉——**一条已提交的条目被覆盖，状态机安全性直接破裂**。
根因是：旧任期条目"看起来在多数派上"这件事**不代表它现在还安全**，因为那条目所在位置的多数派可能已被后来的任期内选举换掉。反过来，**只要当前任期的条目提交了，旧任期条目就必然安全**：当前任期条目能过多数派，说明多数派的日志已经包含了它之前的所有条目（`prevLogIndex`/`prevLogTerm` 检查保证了这一点），而任何未来 Leader 都必须从这个多数派里产生，必然带有这些条目。所以规则 1 是**安全性的充分条件**，规则 2 是它的副产品。
> [!CAUTION]
> 答"Leader 的日志只要复制到多数派就能提交"会被判错。正确答法是"**当前任期**的条目复制到多数派即可提交；旧任期条目不能靠计数提交，只能等当前任期条目提交后被连带提交"。这个点几乎必然被追问，也是区分"背过 Raft"和"想过 Raft"的分界线。
若集群长期没有新写入，`commitIndex` 就停住，旧条目迟迟不提交，读操作会受到什么影响，是下一层的追问（解：新 Leader 可在任期开始提交一条 no-op 条目来立刻推进 `commitIndex`）。
### 34.3.5 网络分区下的两个 Leader
5 节点被切成 `{S1,S2}` 与 `{S3,S4,S5}`：
- **多数派侧 `{S3,S4,S5}`**：能选出 Leader、能提交日志、正常对外服务。
- **少数派侧 `{S1,S2}`**：原 Leader 若在其中，它**仍然认为自己是 Leader**（它没有全局视野），但任何 `AppendEntries` 都拿不到多数派确认，所以 `commitIndex` 无法推进，**一条日志都提交不了**，客户端写入全部超时。
- **分区恢复**：少数派侧 Leader 收到更大 `term` 的心跳就退回 `Follower`，其本地**未提交的日志被多数派侧的日志覆盖回滚**；`lastApplied` 之后的条目要回退到提交点重新应用。
这个"双主"是良性的，前提正是 34.3.4 的规则：**少数派侧的"主"没有提交能力**。如果它也能提交，就会出现两个状态机各自前进并永久分叉。
### 34.3.6 成员变更：为什么不能一次换掉一半
集群配置（membership）本身也是一份需要共识的数据。如果直接把 `{A,B,C}` 改成 `{A,B,C,D,E}` 并让两边各自独立选主，可能出现 `{A,B,C}` 选出 `L1`、`{A,B,C,D,E}` 选出 `L2` 的局面，两个多数派**互不重叠**，安全性破裂。
- **单节点变更（one server at a time）**：一次只增删一个节点。任意两步配置的多数派必然相交，因此不会出现两个不相交的多数派。实现简单，但是**串行**的，扩容 10 个节点要 10 轮。
- **联合共识（joint consensus）**：先切到 `C_old,new`（提交需要**两个配置各自的多数派**都同意），再切到 `C_new`。任意时刻最多只有一个配置的多数派能独立工作。代价是实现复杂、需要额外的中间态处理。
> [!NOTE]
> 面试官会追问"加节点是扩容还是缩容更危险"。答案：**加节点本身不提升写吞吐**（写仍要多数派确认，节点越多单次写越慢），它提升的是读容量与容错度；节点数从 3 加到 5，容错从 1 台变 2 台，但每次写要多等一个副本。偶数节点没有收益（4 节点容错仍是 1 台，因为多数派是 3），所以共识集群通常是 3、5、7。
## 34.4 Paxos、ZAB 与 Raft 的关系
`Paxos` 解决的最小问题是"**一组进程对单个值达成共识**"（`Basic Paxos`），两阶段：
```
Phase 1 Prepare(n) → Proposal 编号 n（全局唯一、单调递增）
Promise(n, v') → 承诺不再接受编号 < n 的 Proposal，并回报已接受的最高编号值 v'
Phase 2 Accept(n, v) → v 取"回报值中编号最大的那个"，没有回报值才用自己提议的值
Accepted(n, v) → 多数派接受即选定
```
两个必须点破的地方：**其一，提案编号必须全局唯一且单调**（用 `<序号, proposerId>` 保证）；**其二，Phase 2 的值不是提议人自由选的**——若多数派中有节点已接受过某值，提议人必须采用"最高编号对应的那个值"，这正是"已选定的值不会被推翻"的原因。
`Basic Paxos` 的**活锁**：`P1` 发 `Prepare(1)`，`P2` 发 `Prepare(2)`，各自在对方 `Accept` 前用更大编号抢占，然后互相不断加号——**没有人能完成 Phase 2**，谁也不违反安全性，但永远达不成决议。`Multi-Paxos` 的改进是：**选出一个稳定的 Leader（distinguished proposer）由它串行提出后续所有 Proposal**，并把 Phase 1 一次性对所有日志槽位做完（后续只跑 Phase 2），把每轮 2 个 RTT 降到稳态约 1 个 RTT。
Raft 的定位是**为可理解性而设计的 Multi-Paxos 变体**：它做了三件 Paxos 没规定的事——**强 Leader**（日志只能从 Leader 单向流向 Follower，Paxos 允许任何提议人）、**连续的日志槽位与 `prevLogIndex`/`prevLogTerm` 检查**（Paxos 的 slot 是独立的）、**把成员变更写进协议**。两者共享的核心约束完全相同：**多数派交集保证任意两个已选定的决议不会冲突**，**编号/任期单调保证旧消息被识别并丢弃**。
| 维度 | Paxos（Basic/Multi） | Raft | ZAB |
|---|---|---|---|
| 抽象目标 | 对单个值/单个槽位达成共识 | 复制日志（值序列） | 主备模型下复制状态变更（zab 事务） |
| Leader | Basic 无；Multi 有弱 Leader（distinguished proposer） | **强 Leader**，日志单向 | **强 Leader**，但语义是"主备"而非"领导选举" |
| 日志空洞 | 允许未选定的槽位存在 | 不允许，日志连续 | 不允许，`zxid` 连续 |
| 顺序标识 | Proposal 编号 `n` | `term` + `logIndex` | `zxid`（64 位：高 32 位 epoch + 低 32 位计数器） |
| 成员变更 | 未规定 | 单节点变更 / 联合共识 | 由 Leader 以特殊事务广播 |
| 设计目标 | 正确性优先，抽象度高 | 可理解性与可实现性 | 为 `ZooKeeper` 的主备高可用服务 |
**一句话区分：`ZAB` 是"主备（primary-backup）复制协议"，Raft 是"领导者选举协议"。** `ZAB` 假设有一个主并围绕它做状态复制与恢复（`ZooKeeper` 重启后要靠 `zxid` 做差异同步）；Raft 把"谁来当主"当成一等公民，用 `term` 与选举超时这套机制统一处理换主与日志复制。答题时不要把两者说成"同一个东西的两种实现"。
## 34.5 分布式事务六种方案对比
| 方案 | 一致性模型 | 不一致窗口 | 阻塞/可用性 | 业务侵入 | 适用场景 |
|---|---|---|---|---|---|
| `2PC` | 强（准线性） | 无脏数据，但有**长时间锁定** | Coordinator 单点，`prepare` 后事务处于"不确定态"，参与者持锁阻塞 | 低（数据库/中间件实现） | 单体内跨多个库、或对强一致要求高的短事务 |
| `3PC` | 强 | 仍无法消除脑裂，但**大幅缩短阻塞窗口** | 加 `CanCommit` 预询与超时自动 `commit`，参与者不再是"永久不确定" | 低 | 教科书方案，实践中因网络分区仍不安全而少用 |
| `TCC` | 最终一致 | `Try` 成功到 `Confirm` 之间的**业务中间态** | 无长事务锁，靠 `Try` 预留资源 | **高**（每个操作写三段） | 资金、库存等需要预留与释放的场景 |
| `Saga` | 最终一致 | 每个本地事务提交后即对外可见，**中间态暴露** | 无全局锁，失败靠反向补偿 | 中（每步写补偿） | 长流程（订单→支付→发货→积分），步骤多、耗时长 |
| 本地消息表 | 最终一致 | 本地事务提交到消息被消费之间的窗口 | 与业务**同库同事务**，不引入新单点 | 中（多一张表与一个投递任务） | 已有单库、想用最小代价换取最终一致 |
| 最大努力通知 | 最终一致（弱） | 消息可能**永久丢失**（重试次数耗尽即放弃） | 不保证送达 | 低 | 对账、通知类等容忍丢失的场景 |
**`2PC` 的真实问题不是"慢"，而是"不确定态"。** 协调者发出 `prepare` 后、发出 `commit`/`rollback` 前崩溃，参与者已锁定资源但不知道该怎么办；此时若协调者日志单点丢失，参与者只能阻塞等待人工介入。此外 `prepare` 后**数据对同库其他事务是否可见取决于隔离与锁的粒度**——InnoDB 里 `prepare` 只是把事务状态推进到 `PREPARED` 并持锁，其他事务读该行会被锁阻塞，所以"数据可见性"真正的坑在**锁的持有期跨越了一次跨机往返**（详见第 21 章 21.5 节）。`3PC` 增加 `CanCommit` 并把 `preCommit` 后参与者可超时自行 `commit`，缓解了阻塞，但**超时自行 commit 在分区下会导致部分节点提交、部分回滚**，所以它牺牲的是安全性，实测并没有真正解决问题。
**`TCC` 的三个坑必须在设计时写进注释。** `Try` 阶段做资源预留（冻结金额、锁定库存），`Confirm` 提交、`Cancel` 释放。
```java
// Try：只做资源预留，绝不产生"最终账"——否则 Cancel 无法真正撤销
boolean tryFreeze(String orderId, long amount) {
// 唯一索引 + 幂等表：Try 可能被重复执行（网络超时后重试），必须靠 orderId 去重
return accountMapper.freeze(orderId, amount); // 影响行数 0 表示已被冻结过
}
// Cancel：必须幂等，且必须处理"Try 从未执行"的空回滚
boolean cancelFreeze(String orderId) {
// 空回滚 = Cancel 先于 Try 到达（Try 请求超时但实际未写入），此时没有冻结记录
// 只返回 true 会让悬挂风险成立，所以要先插一条"防悬挂"标记记录
if (freezeMapper.exists(orderId)) return accountMapper.unfreeze(orderId);
return hangGuardMapper.insert(orderId); // 写下防悬挂标记，拒绝其后到达的 Try
}
```
`TCC` 三大坑：**空回滚**（`Try` 未到、`Cancel` 先到，不能报错也不能什么都不做，要落防悬挂标记）、**幂等**（`Try`/`Confirm`/`Cancel` 都可能重试）、**悬挂**（`Cancel` 先到并释放了资源，`Try` 随后才到并真的冻结，资源被永久占用——防悬挂标记就是为它存在的）。这三个坑在面试里几乎是 `TCC` 的必问项。
> [!WARNING]
> 答 `Saga` 时必须主动说"**它不提供隔离性**"。`Saga` 的每个本地事务提交后立刻对外可见，所以别的请求可能读到"订单已创建但尚未支付"的中间态；补偿事务也不一定能真正撤销已发生的副作用（已发出的短信无法撤回）。缓解手段只有"语义锁"（业务上把中间态标记为不可消费）或按业务键串行化，而不是靠数据库锁。
**`Seata` 的三种模式定位**：`AT`（Automatic Transaction）对业务**零侵入**，靠拦截 `SQL` 解析出前后镜像（before/after image）写入 `undo_log`，一阶段提交本地事务并**立即释放本地锁，但持有全局锁（`global lock`）直到全局事务结束**，二阶段若需要回滚就用 `undo_log` 反向补偿；`TCC` 模式把三段留给业务实现，性能与可控性最好；`Saga` 模式面向长流程、状态机编排。`AT` 的关键机制是**全局锁**：它保证同一行记录不会被两个全局事务同时修改（否则两个事务的 `undo_log` 会互相覆盖），代价是**同一行的跨服务并发被串行化**，热点行会成为瓶颈。此外 `AT` 要求**本地事务提交前有可用的 `undo_log`**，且能被二阶段读到——这是 `AT` 与"仅在本地库回滚"的本质差别。
> [!NOTE]
> 面试官常追问"`AT` 的全局锁和数据库行锁有什么区别"。答：数据库行锁在一阶段结束就被释放（所以本地事务的隔离性只覆盖一阶段），全局锁跨两个阶段持有，是**跨服务的逻辑锁**，通常存在 `Seata` 服务端或数据库表中；它的作用不是保证隔离级别，而是保证**二阶段补偿时数据没有被别人改过**。
## 34.6 分布式 ID 的六种方案与取舍
| 方案 | 有序性 | 单机性能量级 | 可用性依赖 | 失效场景 |
|---|---|---|---|---|
| `UUID`（v4） | 无序（`v7` 可时间有序） | 本地生成，10⁶/s 以上量级 | 无依赖 | 无序导致 B+ 树索引页分裂（见第 23 章 23.4 节）；36 字符存储与可读性差 |
| 数据库自增 | 严格递增 | 受单库写入上限约束（千级/s 量级） | **数据库单点** | 单点故障即全站阻塞；多实例步长方案在扩容时要改步长 |
| 号段模式 | 趋势递增 | 一次取一批（如 1000 个），QPS 提升 10³ 倍量级 | 依赖中心存储（DB/Redis） | 中心存储宕机时只能靠本地缓存号段撑住；号段取完瞬间有 DB 尖峰 |
| `Snowflake` | 趋势递增（同毫秒内有序） | 单机 4096 个/ms，`4096 × 1000 = 409.6 万/s` 上限 | 无依赖（靠机器位） | **时钟回拨**导致 ID 重复；机器位分配冲突 |
| `Redis` `INCR` | 严格递增 | 10⁵/s 量级（单实例） | 依赖 `Redis` 可用性 | `Redis` 不可用即发不出号；持久化策略不当重启会重号 |
| `Leaf`/`UidGenerator` | 各自可选 | `Leaf-segment` 走号段，`Leaf-snowflake` 走雪花 | 号段依赖 DB，雪花依赖 `ZK` 校验 | 见下 |
`Snowflake` 的 64 位结构（Java `long`，最高位留给符号）：
```
0 | 41 bit 毫秒时间戳 | 10 bit 机器 ID | 12 bit 序列号
▲ ▲ ▲ ▲
符号位 可用 2⁴¹ ms ≈ 69.7 年 最多 1024 台 同毫秒内最多 4096 个
（恒为 0） 起点为自定义纪元(epoch)，因此 41 位约 69 年才耗尽
```
`10 bit` 常拆成 `5 bit 数据中心 + 5 bit 机器`（各 32）。`4096 × 1000 = 4,096,000/s`，这是单机理论上限。
**时钟回拨是 `Snowflake` 唯一的致命伤**，因为算法假设"时间戳单调不减"，回拨后同一毫秒会重复生成 ID。四种处理方式与各自代价：
| 处理方式 | 做法 | 代价 |
|---|---|---|
| 等待 | 回拨幅度小时自旋等到追上上次时间戳 | 阻塞调用线程，回拨大时不可接受 |
| 抛异常 | 超过阈值（如 5 ms）直接失败 | 发号服务短暂不可用，由上游重试 |
| 备用位 | 预留位记录"回拨次数"，用额外位区分同一毫秒 | 消耗位宽，且回拨多次仍会耗尽 |
| `Leaf-snowflake` 校验 | 启动时用 `ZooKeeper` 顺序节点写入 workerId 并校验时间戳，回拨时**报警 + 拒绝发号**（并等 `ZK` 时间对齐） | 引入 `ZK` 依赖；只解决启动期冲突，运行期回拨仍要策略 |
按四个维度给结论：**要严格有序**（如数据库主键、分页游标）→ 数据库自增或号段；**要高性能且趋势有序**（如订单号）→ `Snowflake` 系；**不想有任何中心依赖** → `Snowflake`；**已有 `Redis` 且量不大** → `INCR`。工程上最常见的是 **`Leaf-segment` 打底 + `Snowflake` 兜高并发**：号段双 `buffer`（当前号段用到 10% 就异步预取下一段）避免取号时的请求尖峰，并支持动态调整步长（按最近一段的消耗速度线性外推，流量涨就调大步长）。
> [!TIP]
> 面试官会追问"`Leaf-segment` 的双 `buffer` 到底解决什么"。答：**它把"取号"这个 DB 往返从关键路径上摘掉**——单 `buffer` 时每个号段耗尽的瞬间都要同步查一次 DB，那一瞬间的 QPS 尖峰与 DB 抖动会直接传导成接口毛刺；双 `buffer` 让预取发生在号段还有余量时，DB 慢一点也有缓冲。这正是"用一点内存换掉尾延迟"的典型例子。
## 34.7 分布式锁：四种实现与各自不安全的时刻
> 本节只做理论对比与缺陷判定；`Redis` 锁的命令写法、看门狗与主从切换细节见第 27 章 27.11 节。
| 实现 | 互斥来源 | 自动释放 | 性能量级 | 什么时候不安全 |
|---|---|---|---|---|
| 数据库唯一索引 | 唯一约束 `INSERT` 冲突 | 无（必须显式 `DELETE`，进程崩溃即死锁） | 一次写入约 1~10 ms 量级 | 进程崩溃后锁永久残留；`DELETE` 语句本身可能超时；无超时机制时依赖人工清理 |
| `Redis` | `SET NX PX` 的原子写入 | 有（`PX` 过期） | 一次往返约 0.1~0.5 ms（同机房） | **主从异步复制**：主库写入成功未同步即宕机，从库升主后另一客户端也能加锁成功，互斥破裂 |
| `ZooKeeper` | 临时顺序节点 + `Watch` | 有（会话超时即删临时节点） | 一次操作约 1~5 ms 量级 | 会话超时抖动导致误判持锁方已死；**羊群效应**（若都用 `Watch` 同一节点，释放时惊群）——用顺序节点各自 `Watch` 前一个解决 |
| `etcd` | 租约 `Lease` + 事务 `Txn` | 有（租约到期） | 与 `ZK` 同量级 | 本质同 `ZK`：租约到期与"旧持有者仍在写"之间的窗口依然存在（`GC` 长暂停会放大它） |
`Redis` 与 `ZK`/`etcd` 的根本差别是**一致性模型的差别**：`Redis` 主从异步复制走的是 AP 路线，"加锁成功"这个事实在故障切换时可能丢失；`ZK`/`etcd` 基于共识协议走 CP，"加锁成功"必然是多数派已持久化的事实，所以它在切换后不会丢。这就是同一把锁在两种底座上"安全性不同"的根源，而不是命令写得对不对。
`Redlock` 想用"向 N 个（通常 5 个）**相互独立**的 `Redis` 实例依次加锁，多数派成功且在总耗时小于锁有效期内才算成功"来绕开单主从的复制丢失问题。Kleppmann 提出两条质疑：**其一，它依赖时钟假设**——锁的有效性靠各实例的过期时间推算，而这些进程的时钟可能发生跳变（`NTP` 校时、虚拟机迁移、`GC` 暂停都可能导致本地时间"快进"），续期与过期判断因此在理论上不可靠；**其二，它没有 fencing token**——一个进程在 `GC` 长暂停后恢复，它不知道自己已经不再持锁，仍会向共享资源发起写操作，而资源侧无法识别这是过期持有者。Antirez 的回应是：不依赖时钟的严格方案需要额外机制，而 `Redlock` 的时钟误差假设（各实例时钟漂移远小于锁有效期）在其设计边界内是可以接受的工程近似。
**结论（本节的加分点）**：`Redlock` 争议的真正价值不在于判谁赢，而在于它揭示了一条工程准则——**锁的正确性不应被用来保护数据一致性，除非配合 `fencing token`**。若锁只是"减少重复计算"（如避免缓存击穿时的重复回填），出错的代价只是多做一次；若锁保护的是**数据一致性**（如"同一订单只能被处理一次"），必须让下游资源能拒绝过期锁的写入：持锁方从锁服务拿到**单调递增的版本号**，写请求带上它；资源侧（数据库、存储）记录已见到的最大版本号，**拒绝任何版本号更小的写入**。
```
客户端 锁服务 资源（DB/存储）
│ acquire ──────────▶│
│ ◀──── token = 33 ──│ （每个锁请求返回比上次更大的 token）
│ │
│ ── 此处发生 GC 长暂停 / 网络分区 ── │
│ │
│ 锁过期，客户端 B 拿到 token = 34 ────────▶│ write(token=34) ✔ 记录 max_token=34
│ │
│ 客户端 A 恢复，仍以为持锁 ───────────────▶│ write(token=33) ✘ 33 < max_token → 拒绝
⇒ 即使锁语义被破坏，数据也不会被旧持有者污染
```
> [!IMPORTANT]
> 这就是"分布式锁"一节的最终答案：**锁本身不可能保证绝对互斥（时钟、暂停、网络都会破坏它），能保证的只有"资源侧的单调版本号校验"**。面试里主动说出这一层，比多背十种锁实现更有区分度。
## 34.8 限流算法与一致性哈希
### 34.8.1 四种限流算法
| 算法 | 通过速率 | 突发容忍 | 实现成本 | 主要缺陷 |
|---|---|---|---|---|
| 固定窗口计数 | 窗口内均值 | 无（窗口边界处可 2×） | 极低（一个计数器） | **临界点双倍**：窗口 1 s、阈值 100，则 0.99 s 来 100 个 + 1.01 s 来 100 个，在 0.02 s 内通过 200 个 |
| 滑动窗口 | 窗口内均值 | 无 | 中（`Redis ZSet` 或环形数组） | `ZSet` 方案内存随请求数增长（每请求一个成员），需按时间清理；环形数组方案精度取决于格子数 |
| 漏桶（leaky bucket） | **恒定**流出 | 不容忍（缓冲后匀速放行） | 低 | 突发被缓存在桶里，桶满即丢；恒定速率无法利用空闲容量 |
| 令牌桶（token bucket） | 平均速率 | **允许，上限为桶容量** | 低 | 需要维护令牌生成速率与桶深两个参数，桶深即"允许多大的瞬时突发" |
固定窗口的**临界点双倍**必须给数字：阈值 100 QPS，窗口按自然秒对齐。客户端在 `t=0.95 s` 打 100 个（第 1 个窗口），在 `t=1.05 s` 再打 100 个（第 2 个窗口），两个窗口各自都没超 100，但**在 0.1 s 内实际通过了 200 个请求，瞬时速率达到 2000 QPS**——这是固定窗口唯一但致命的漏洞。滑动窗口把它按时间切成 `N` 个格子（如 1 s 切 10 格、每格 100 ms），统计"当前时间往前一整窗"的计数总和，把边界效应压到 `1/N` 的粒度。
令牌桶的容量公式值得记牢：桶深 `B`、令牌生成速率 `r`，则在无流量期间最多攒 `B` 个令牌，因此**允许的最大瞬时突发是 `B` 个**；长期平均速率被钳在 `r`。`Guava RateLimiter` 的单机实现用的是"惰性计算"——不真的起定时器加令牌，而是记录 `nextFreeTicketMicros`，每次请求时按经过时间算应生成多少令牌，把开销降到 `O(1)` 且无后台线程。分布式实现则必须把"令牌数与上次填充时间"存到 `Redis` 并**用 `Lua` 脚本原子地读-算-写**，否则并发下会把同一批令牌发两次。
**分布式限流的两种思路**：**集中式**（所有实例共用 `Redis` 计数器，一致性好，但每次限流判定多一次 `Redis` 往返，且 `Redis` 成为限流热 key 与单点——单 key 每秒几万次 `INCR` 就要考虑分片或本地预取）；**配额分配**（中心按实例数把配额切开，每实例本地限流，如 1000 QPS ÷ 10 实例 = 各 100，代价是**流量不均时部分实例饿死、部分实例超发**，靠定期上报与动态调整缓解；也可以让实例按需向中心"借"配额）。
**限流的维度**：接口（`/api/order/create`）、用户（UID/租户）、`IP`、以及它们的组合（"每用户每接口"）。维度选择决定键的设计，键太细会让计数爆炸、太粗会让单用户拖垮全局。**限流后的行为**不止"拒绝"一种：排队（把请求放进有界队列稍后处理，适合同步调用转异步）、降级（返回缓存或默认值）、以及返回 `429` 并带 `Retry-After` 让客户端退避。
> [!NOTE]
> 面试官会追问"网关限流和业务限流为什么要两层"。答：网关限流是**粗粒度的保护**（挡住明显异常流量、保护整个集群），业务限流是**细粒度的公平性**（保护下游依赖、按用户/租户分配配额）。只做网关限流会让单个大客户占满全网配额，只做业务限流会让异常流量打到业务层才被拒。
### 34.8.2 一致性哈希、虚拟节点与 Redis Cluster 的分片
**普通取模扩容的代价可以精确量化。** 用 `hash(key) mod N` 分片，从 `N` 个节点扩到 `N+1` 个节点时，某个键仍落在同一节点，当且仅当 `hash(key) mod N == hash(key) mod (N+1)`。在哈希均匀的近似下，这个比例约为 `1/(N+1)`，因此**需要迁移的键的比例约为 `N/(N+1)`**：
- `N=3 → 4`：迁移 `3/4 = 75%`；
- `N=9 → 10`：迁移 `9/10 = 90%`；
- `N=99 → 100`：迁移 `99/100 = 99%`。
也就是说，节点越多，扩一个节点**几乎要搬全量数据**（`N` 取 100 时是 99%），这是"取模分片不能平滑扩容"的量化结论。
**一致性哈希（consistent hashing）** 把哈希空间组织成一个 `0 ~ 2³² − 1` 的环，节点与键都哈希到环上，**键归属顺时针方向第一个节点**。增删一个节点时，只有该节点逆时针到前一个节点之间的那一段键需要迁移，**期望迁移比例是 `1/(N+1)`**（加一个节点时约分走 `1/(N+1)` 的键）。
```
hash ring: 0 ──────────────────────▶ 2³²−1
┌──────── N1 ────────┐
K3 │ │ N3
┌──────────┤ ├────────┐
│ │ K1 K2 │ │
│ N2 └────────────────────┘ │
└───────────────────────────────────────┘
顺时针：K1 → N3（顺时针第一个节点）；K2 → N3；K3 → N1
加节点 N4 落在 K1 与 N3 之间 ⇒ 只有原本归 N3 且位于 N4 逆时针区间内的键改归 N4
```
一致性哈希的**问题是数据倾斜**：节点数少时，节点在环上分布不均，可能出现一个节点承担 50% 以上的键（"一个节点管半个环"）。极端情况下两个节点哈希得很近，其中一个几乎分不到数据。
**虚拟节点（virtual node）** 解决它：每个物理节点映射为 `V` 个虚拟节点（`V` 通常取 100~1000，工程上常用 150 或 160），虚拟节点散布在环上，键先落到虚拟节点再映射回物理节点。`V` 越大，各物理节点承载的键比例越接近 `1/N`——这是"用更多哈希点逼近均匀分布"的做法。代价是**每个物理节点的信息要存 `V` 份**（`N` 个节点 `V=160` 时是 `160N` 个环上条目），路由表内存与查找成本随之上升；`Ketama` 算法就是在这一层做优化的经典实现（它把每个物理节点的虚拟节点数固定为 `160`，并用一个有序结构做二分查找来定位顺时针第一个节点）。
> [!WARNING]
> **`Redis Cluster` 的 `16384` 个槽（slot）不是一致性哈希环**，别把两者混为一谈。它是**固定分片（fixed sharding）**：槽号由 `CRC16(key) mod 16384` 得到，槽再静态分配给主节点，扩容时是**按槽迁移**（`MIGRATE`）而不是按哈希环区间迁移。为什么是 `16384` 而不是 `65536`：集群用位图（bitmap）表示"每个节点负责哪些槽"，`16384` 个槽只需 `16384/8 = 2 KB`，`65536` 则需要 `8 KB`，心跳包每次都要带这份位图，节点数多时开销明显；同时 `Redis Cluster` 设计上支持的节点数在千级量级，`16384` 个槽在"每节点分到足够多的槽"与"位图开销"之间是折中。答题时把"一致性哈希环"和"槽分片"分成两套机制来答，是这一节的分界线。
## 本章小结
| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| CAP 的准确含义 | C 是线性一致，A 是有界非错误响应，P 是网络分区容忍；分区时在 C 与 A 间二选一 | 答"三选二"、把 A 答成"高可用" |
| PACELC | 分区时选 A 或 C；无分区时选延迟 L 或一致性 C | 只谈 CAP，忽略日常态的 L/C 权衡 |
| 一致性谱系 | 线性一致 = 顺序一致 + 真实时间约束 | 说不清线性一致与顺序一致的区别 |
| Raft 提交规则 | 只有当前任期的日志可凭多数派直接提交，旧任期只能被连带提交 | 答"复制到多数派即可提交" |
| Raft 选举 | 随机化超时打散同时超时，避免选票瓜分；投票要求日志不落后 | 答"超时越短越快"，说不出为什么要随机 |
| 分区下的双主 | 少数派侧无法提交、恢复后回滚未提交日志 | 认为两个 Leader 都会推进状态机 |
| `Paxos` 与 Raft | 同一约束（多数派 + 单调编号）的不同表达；`ZAB` 是主备复制协议 | 把 `ZAB` 与 Raft 说成一回事 |
| 分布式事务选择 | 短事务要强一致用 `2PC`/`TCC`，长流程用 `Saga`，最简是本地消息表 | 认为 `Saga` 提供隔离性；忘记 `TCC` 的空回滚与悬挂 |
| 分布式 ID | 严格有序选自增/号段，高性能无序依赖选 `Snowflake` | 忘记 `Snowflake` 的时钟回拨，答不出 4096/ms 的来源 |
| 分布式锁 | 锁不可能绝对互斥，要一致性必须配 `fencing token` | 只答"`Redis` 快用 `Redis`"，不知主从切换会双持有 |
| 限流 | 固定窗口有临界点双倍；令牌桶用桶深控制突发 | 认为固定窗口就够用，或说不清桶深与速率的关系 |
| 分片 | 取模扩容迁移 `N/(N+1)`；一致性哈希迁移 `1/(N+1)`，靠虚拟节点治倾斜 | 把 `Redis Cluster` 的 `16384` 槽说成一致性哈希环 |
## 自测题
**Q1**（辨析）有人说"我们的系统选择了 AP，所以不需要线性一致，只要最终一致"。这句话在 CAP 的语境下错在哪？
答案与解析
错在两处。**第一，CAP 的选择只在分区期间生效**，无分区时说的是 PACELC 的第二段（L 与 C 的权衡），不能拿"我们选 AP"来为日常态的数据陈旧开脱——日常态的陈旧是 L/C 权衡的结果，需要单独解释（例如异步复制换低延迟）。**第二，"选 AP"只承诺了分区时的可用性偏好，并不蕴含"只能做到最终一致"**。因果一致通常可以在 AP 系统里实现（例如用版本向量或依赖跟踪），而且业务上"最终一致"必须给出**收敛时间上界**与**冲突解决策略**（LWW、版本向量、CRDT），否则不是模型而是一句口号。面试官会紧接着追问"你们的最终一致窗口是多大、冲突怎么解"，答不出上界就是背概念。
答案与解析
不能。`idx2=term2` 虽然物理上位于多数派上，但**它所在位置的多数派可能已被后续任期替换**：`S5` 那条 `idx2=term3` 曾经在 `{S3,S4,S5}` 这个多数派上存在过，若允许"旧任期条目凭计数提交"，则 `idx2=term2` 被提交后会连带提交 `idx2=term3`；而 `S5` 一旦再次当选并复制日志，会用自己的版本**覆盖 `idx2=term2`**，于是"已提交的条目被覆盖"，状态机安全性破裂。Raft 的规则是**只允许提交当前任期的条目**：当前任期条目能过多数派，就意味着多数派已包含它之前的全部条目（`prevLogIndex`/`prevLogTerm` 检查保证），而未来任何 Leader 都必须从这个多数派中产生，必然带有这些条目，安全性由此得到保证。追问层次：面试官下一步会问"那旧任期日志怎么才算提交"（答：当前任期条目提交后被连带提交），再问"如果一直没有新写入，`commitIndex` 停住怎么办"（答：新 Leader 提交一条 no-op 条目推进）。
答案与解析
(1) `N=8 → 9`，迁移比例约 `N/(N+1) = 8/9 ≈ 88.9%`——几乎全量搬迁。推导：某键不迁移要求 `hash(k) mod 8 == hash(k) mod 9`，在均匀哈希下这一比例约为 `1/9`，故迁移 `8/9`。**这是"取模分片不能平滑扩容"的量化依据**，也是面试官要的"迁移比例"数字。(2) 一致性哈希下新增节点只接管它逆时针到前驱之间的区间，期望迁移比例约 `1/9 ≈ 11.1%`，比取模低约 8 倍。(3) 虚拟节点不改变期望迁移比例（仍约 `1/(N+1)`），它改变的是**分布的均匀性**：不加虚拟节点时单个物理节点可能承担 40% 以上的键，这会让新节点接管区间的方差极大（有的节点几乎不动、有的搬走大半）；加上 `V=150` 量级的虚拟节点后，各节点承载比例的标准差约下降 `√V` 倍量级，迁移量从"取决于运气"变成"接近期望值"。追问点：`Redis Cluster` 的 `16384` 槽是按槽迁移的固定分片，不是哈希环，扩容的迁移量取决于你迁移了多少个槽。
答案与解析
方案不充分，因为它把**数据正确性押在锁的可靠性上**，而 `Redis` 锁在至少两种场景下会失效：**主从异步复制丢失锁**（主库加锁成功后未同步即宕机，从库升主后另一客户端也能加锁成功，两方同时扣减），以及**`GC` 长暂停或网络分区导致的锁过期**（旧持有者恢复后仍以为持锁并继续写）。补齐方式有四层：**其一**，把真正的幂等保证下沉到存储层——用唯一索引或 `UPDATE ... WHERE status = 'INIT'` 这类条件更新，让"重复扣减"在数据库层面直接失败（接口幂等的完整落地见第 35 章）；**其二**，若锁只用于减少竞争，就承认它是优化而非正确性保证；**其三**，若锁确实要保正确性，必须引入 **fencing token**：每次加锁返回单调递增的版本号，写请求带上它，存储侧记录已见的最大版本号并拒绝更小的版本号；**其四**，锁的失效要可观测（续期失败、租约到期要告警），并配业务侧的对账补偿兜底。追问链条：`Redlock` 能不能解决？答：它缓解了单主从切换的丢锁问题，但依赖各实例时钟漂移远小于锁有效期的假设，且**依然没有解决"旧持有者不知情仍在写"**，所以不能替代 fencing token。
答案与解析
三点。**其一，`Basic Paxos` 只对"一个值"达成共识**，复制日志需要对每个日志槽位反复跑两阶段，而多个提议人并发提交时会出现**活锁**——`P1` 与 `P2` 互相用更大编号抢占，谁都无法完成 Phase 2，虽然安全性不破但**永远达不成决议**。**其二，`Basic Paxos` 没规定 Leader**，任何节点都能提案，因此没有"日志只能从主单向流向从"的性质，实现者必须自己补上日志空洞的处理、提案顺序、成员变更等大量细节；`Multi-Paxos` 通过选出 `distinguished proposer` 并把 Phase 1 一次做完来降为稳态 1 RTT，而 Raft 直接把这个优化**写进了协议**（强 Leader + 连续日志 + `prevLogIndex` 检查）。**其三，可理解性与可实现性是设计目标**：Raft 把 Leader 选举、日志复制、成员变更、快照拆成相互独立、可分别实现与测试的模块，并提供明确的正确性论证路径，这显著降低了实现出 bug 的概率——分布式共识的实现细节极多，一个不留神的状态判断就会破坏安全性。面试官可能追问"`ZAB` 与 Raft 的差别"，答：`ZAB` 是主备模型的状态复制协议（`zxid` 连续、差异同步），Raft 是领导者选举模型，二者共享多数派与单调编号的核心约束。