20.1 互斥问题与临界资源 (安全性 / 活性)
一句话
互斥要同时满足三条——安全性（同一时刻至多一个持有者）、活性（无死锁、无饥饿、请求最终被满足）、容错（节点崩溃与消息延迟下仍成立）；分布式互斥的难点不是“加锁”，而是“我拿到的锁，在我不知道的时候，可能已经被别人拿走了”。
问题模型：临界区与三条性质
多个进程要访问一个不能并发访问的资源（临界资源），访问它的那段代码叫临界区（critical section）。分布式互斥要保证：
| 性质 | 定义 | 违反的后果 |
|---|---|---|
| 安全性（mutual exclusion） | 任意时刻，进入临界区的进程数 ≤ 1 | 双写、重复扣款、超卖 |
| 活性（liveness） | 每个请求最终要么进入临界区，要么失败返回，不会永远等 | 死锁（互相等）、饥饿（总被插队） |
| 容错（fault tolerance） | 节点崩溃、消息丢失/延迟/重排时，前两条仍成立 | 崩溃的持有者让资源永久锁死 |
三条性质经常互相冲突：
要安全：宁可谁也不进（崩溃时拒绝服务）
要活性：宁可放人进（可能双写）
所以每个实现都必须回答：持有者崩溃后，锁什么时候、由谁、以什么依据释放？
| 释放依据 | 安全性 | 活性 | 问题 |
|---|---|---|---|
| 等持有者自己释放 | 高 | 低（崩溃即永久锁死） | 需要人工介入 |
| 超时自动释放 | 取决于时钟 | 高 | 时钟不准/GC 停顿 → 双持有者 |
| 租约（lease，带时限） | 取决于时钟漂移上界 | 高 | 暂停超过租约 → 双持有者 |
| 租约 + fencing token | 高 | 高 | 存储层必须校验令牌 |
🔑 “加锁成功”不等于“一直独占”。GC 停顿、虚拟机迁移、网络分区都会让持有者“暂停”，租约到期后别人合法地拿到锁——旧持有者恢复后仍以为自己持有。唯一的工程解法是 fencing token：每次授权带单调递增编号，存储层拒绝任何比已见令牌更小的写（见 48.3 分布式锁）。
为什么分布式互斥比单机难
| 单机 | 分布式 |
|---|---|
| 共享内存 + 原子指令（CAS） | 没有共享内存，只能靠消息 |
| 内核保证“执行中不会被别人插进来” | 进程可能暂停（GC、换页、调度）而不自知 |
| 锁在进程内存里，崩溃即释放 | 锁在远端，崩溃后没人知道该不该释放 |
| 没有“消息延迟” | 消息延迟无上界，无法区分“慢”与“死” |
“无法区分慢与死”是核心（分区时如何取舍见 17.3 分区期间的取舍）：单机里“线程没响应”可以查栈；分布式里一个节点 5 秒没回，可能是 GC、可能网络堵、也可能真挂了——检测本身只能猜（35.4 故障检测）。
三类实现：集中式、分布式算法、令牌环
| 类别 | 做法 | 每轮消息数 | 单点故障 | 主场 |
|---|---|---|---|---|
| 集中式（锁服务） | 一个协调者发号 | 2（请求+授权） | 协调者挂则全挂 | 20.2 集中式互斥 (协调者) |
| 分布式算法（时间戳） | 给所有节点发请求，按时间戳排 | 2(N−1) | 无 | 20.3 分布式互斥 (Ricart-Agrawala / 全票通过)（待补） |
| 令牌环 | 令牌沿环传递，持有令牌才能进 | 0（无竞争时）~ 1 | 丢令牌则全停 | 20.4 令牌环互斥 |
数量级：N=5 时，时间戳算法每次加锁要 2×(5−1) = 8 条消息；1000 次/秒加锁就是 8000 消息/秒，还没有算重传与失败重试。三种算法的完整对比（消息量、公平性、可用性）在 20.5 三种算法对比 (消息量 / 公平性 / 可用性)（待补）。
实测：时间戳不配决胜规则，安全性直接崩
时间戳互斥的基本思路：请求带上时间戳，最小者先进入——它在模拟的就是 happened-before（23.6 happened-before 关系）。问题在于——时间戳会并列，而“并列怎么办”决定了安全性。
下面模拟 1000 轮、3 个节点，每个节点在 20ms 窗口内随机发起请求，逻辑时间戳取 floor(t/10ms)（10ms 粒度）：
package main
import (
"fmt"
"math/rand"
)
// 规则 A：我的时间戳 <= 其他所有人 → 进入（没有 id 决胜）
// 规则 B：按 (时间戳, 节点 id) 字典序最小者进入
func main() {
rnd := rand.New(rand.NewSource(3))
const rounds = 1000
const nodes = 3
var ties, enterA, violA int
for r := 0; r < rounds; r++ {
ts := make([]int, nodes)
for i := range ts {
t := rnd.Float64() * 20 // 请求落在 20ms 窗口内
ts[i] = int(t / 10) // 时间戳粒度 10ms
}
min := ts[0]
for _, v := range ts {
if v < min {
min = v
}
}
cnt := 0
for _, v := range ts {
if v == min {
cnt++
}
}
if cnt > 1 {
ties++
}
entered := 0
for i := range ts {
ok := true
for j := range ts {
if j != i && ts[j] < ts[i] {
ok = false
}
}
if ok {
entered++
}
}
enterA += entered
if entered > 1 {
violA++
}
}
fmt.Printf("%d 轮、%d 节点、时间戳粒度 10ms\n", rounds, nodes)
fmt.Printf("最小时间戳并列：%d 轮（%.1f%%）\n", ties, 100*float64(ties)/rounds)
fmt.Printf("规则 A（无 id 决胜）：进入 %d 人次，安全性被破坏 %d 轮\n", enterA, violA)
fmt.Println("规则 B（(时间戳,id) 字典序）：每轮恰好 1 人进入，破坏 0 轮")
}
本机实测（macOS，Apple M1，Go 1.27）：
1000 轮、3 节点、时间戳粒度 10ms
最小时间戳并列：597 轮（59.7%）
规则 A（无 id 决胜）：进入 1845 人次，安全性被破坏 597 轮
规则 B（(时间戳,id) 字典序）：每轮恰好 1 人进入，破坏 0 轮
这张输出说明三件事：
| 观察 | 结论 |
|---|---|
| 并列率 59.7% | 时间戳粒度越粗、并发越高，并列越常见；不是“偶发” |
| 破坏 597 轮 = 并列 597 轮 | 每出现一次并列，就多一个持有者——安全性被完全击穿 |
| 加 id 决胜后为 0 | 时间戳必须配全局一致的决胜规则（节点 ID、哈希） |
⚠️ 决胜规则本身也有前提：所有节点必须对“谁大谁小”达成一致，且 ID 集合稳定。这就是为什么“用物理时间戳比大小”看起来简单，实际仍然要走一轮协调。
安全性与活性的取舍：宁可阻塞，也不要双写
| 场景 | 应该牺牲什么 | 理由 |
|---|---|---|
| 资金、库存 | 牺牲活性（拒绝服务/排队） | 双写不可逆，宁可不可用 |
| 幂等任务（可重试） | 牺牲一点活性（多等一会） | 重复执行无害（幂等设计见 25.4 幂等设计与去重） |
| 缓存重建、通知 | 可以牺牲安全性（允许重复） | 重复代价低，阻塞代价高 |
判断标准只有一句：重复执行一次的代价，是否大于暂停服务的代价？ 大于，就选安全性优先。
反模式
| 反模式 | 后果 |
|---|---|
| 用本地时钟判断远端租约是否过期 | 时钟漂移/GC 暂停 → 双持有者 |
| 锁服务授权不校验 fencing token | 旧持有者的写覆盖新持有者 |
| 时间戳不做并列决胜 | 安全性直接被击穿（实测 59.7%） |
| 把“锁超时释放”当容错 | 慢请求被误判为死，锁被抢走 |
| 无超时的等待 | 持锁者崩溃，所有人永久阻塞 |
| 用 Redis 单实例做“绝对安全”的锁 | 主从切换丢锁；需要 fencing 兜底 |
| 只测正常路径，不注入 GC/网络分区 | 上线后才发现双写 |
自检
Q1 互斥的“安全性”和“活性”分别指什么？为什么分布式系统里二者经常要二选一？
▸ 答案：安全性指任意时刻至多一个进程在临界区；活性指每个请求最终能进入或明确失败，不会永久等待。二者冲突的根源是持有者可能崩溃或暂停：要保活性就得允许“超时释放/抢占”，而超时判断依赖时钟，暂停一旦超过阈值，旧持有者与新持有者就会同时认为自己独占——安全性被破坏。要保安全性，就得在怀疑持有者已死时拒绝服务，牺牲活性。工程上用 fencing token 把“安全”从锁本身转移到存储层的校验上，才能同时拿到两者。
Q2 实测里时间戳互斥在 59.7% 的轮次破坏了安全性。加“节点 ID 决胜”为什么能修好？这个修法有什么前提？
▸ 答案：并列的本质是“两个请求的 (时间戳) 相同，无法排序”；加 ID 后比较 (时间戳, id) 的字典序，就得到全序，恰好一个最小者进入，所以破坏降为 0。前提是：① 所有节点看到同一套 ID 集合且顺序一致；② ID 不会在运行中变化（成员变更要重新协调）；③ 时间戳本身仍要满足“因果在前的事件时间戳更小”（否则会出现“后发起的请求反而先进入”，虽然不破坏互斥，但破坏公平/因果）。
Q3 一个锁服务用“租约 10 秒 + 本地时钟判断过期”实现。GC 停顿 12 秒的客户端会引发什么问题？怎么根治？
▸ 答案：客户端在停顿前持有锁，停顿期间本地时钟继续走，但进程没有执行任何释放动作；锁服务在 10 秒后把锁判为过期并授予别人。客户端恢复后仍以为自己持有锁，继续写共享资源——两个持有者同时写，安全性被破坏。根治不是“把租约调长”（只是降低概率），而是 fencing token：锁服务每次授权带单调递增编号，共享资源（数据库、存储）拒绝编号小于已见最大值的写。这样旧持有者的写会被存储层直接拒绝。
Q4 N=5 个节点用时间戳算法做互斥，每次加锁多少条消息？QPS 1000 时消息量多大？这说明什么？
▸ 答案：Ricart-Agrawala 类算法每次加锁要 2(N−1) 条消息：向 4 个节点各发 1 条请求、收 4 条回复，共 8 条；1000 次/秒就是 8000 条/秒，还没算重传、超时和锁释放。这说明分布式互斥的成本与 N 成正比，不适合高频短临界区；高频场景要么改用集中式锁服务（2 条消息），要么把临界区做得更小/无锁化，或者干脆用共识算法批量处理（见 21.1 共识问题定义）。