20.3 分布式互斥 (Ricart-Agrawala / 全票通过)

一句话

Ricart-Agrawala 让每个节点自己判断 “我能不能进临界区”：请求带 Lamport 时间戳，收到请求的节点比较 “谁更早” 决定立即回复还是排队；进入前拿到所有人的回复（N−1 票）——用 2(N−1) 条消息换掉中心节点。

步	动作
①	想进临界区：把 `(时间戳, 我的 ID)` 广播给所有节点
②	收到请求：若我不在临界区、也没有更早的未决请求 → 立即回复；否则排队（等我自己用完再回）
③	收到 N−1 个回复 → 进入临界区
④	退出：回复队列里所有排队的请求

关键：Lamport 时间戳提供全序（时间戳相同比 ID），所以不会死锁；“排队” 保证公平（先到先得）。

N=5 时，一次进入要 8 条消息；N=100 时 198 条——消息量随节点数线性增长，这是它只适合小规模的原因。

方案	需要多少票	容错
全票（RA）	N−1 个回复	0（任一节点不可达即卡住）
多数派	⌈(N+1)/2⌉	f 个故障需 N=2f+1

所以工程上很少直接用 RA，而是 “租约 + 多数派”（如 Raft 选主后由 leader 授权），把 “全票” 降级为 “多数派”，换取容错。

本机按算法定义计算（每次进入 = 广播 N−1 请求 + 收 N−1 回复）：

对比集中式：同样 10 次进入只需 ~30 条消息（请求 + 授权 + 释放），且与 N 无关。所以 RA 的 “无中心” 是拿 O(N) 消息换来的；N=50 时一次进入近 100 条消息，网络与序列化开销已经压过 “省掉一个协调者” 的收益。

消息数 = 2 × (N − 1) × 进入次数
N=50、进入 10 次 → 2 × 49 × 10 = 980

🔑 全序靠逻辑时钟，不靠物理时钟。

🔑 全票 = 零容错；生产要用多数派或租约。

🔑 退出必须回复排队请求；否则活性被破坏。

Q1 为什么 RA 不会有死锁？

▸ 答案：因为所有请求按 Lamport 时间戳全序 排列，每对节点之间的冲突都有明确胜负：要么我回你，要么你回我，不会出现 “互相等对方回复” 的环。这是 “全序 + 排队” 的直接结果。

Q2 一个节点崩溃，RA 会怎样？

▸ 答案：其他节点可能永久等不到它的回复，无法进入临界区（全票要求）。需要额外的故障检测与成员变更（把死节点从集合中剔除），而成员变更本身又需要共识——这就是 “RA 不适合生产直接用” 的原因。

Q3 2(N−1) 条消息在大集群里意味着什么？

▸ 答案：O(N) 的广播开销：N=100 时每次进入 198 条消息，且都要等最慢的一个（尾延迟）。所以它适合小规模（N < 10）或 “互斥很少发生” 的场景；高频互斥要用本地锁或无锁结构。

Q4 “多数派” 为什么能容忍故障？代价是什么？

▸ 答案：因为任意两个多数派必相交（见 21.2 Quorum 与 W + R > N 的证明），所以即使 f 个节点挂，仍能凑出多数派。代价是：需要 N=2f+1、写要等多数派确认（多一个 RTT）、少数派分区期间不可用。

Q5 什么场景还值得用 RA？

▸ 答案：规模小、节点稳定、互斥不频繁、且不想引入中心节点的系统（如嵌入式/边缘集群内的协调）。学术与教学价值更大；工程上更常见的是 “中心化 + 租约 + fencing”。

Q7 既然消息量是 O(N)，为什么还说 RA 有 “公平性” 优势？

▸ 答案：因为它的排队完全由 Lamport 时间戳全序决定：谁先请求谁先进入，不存在 “中心节点偏向某个客户端” 的可能。公平性来自全序，代价是广播。高竞争场景下，O(N) 消息 + 全序排队会让吞吐迅速下降，所以公平性的价值只在 “低竞争、需要严格先到先得” 时体现。

Q6 如果只把 “全票” 改成 “多数派”，算法还叫 RA 吗？

▸ 答案：不再是严格意义上的 RA（它要求所有节点的回复），而是 “基于逻辑时钟的多数派互斥”。改动看似小，但语义变了：多数派可以容忍故障，但需要成员视图与任期，本质已经接近共识算法。工程上更常见的做法是 “leader 选举一次，之后由 leader 授权”，而不是每次互斥都投票。

Q7 为什么 RA 的 “排队” 不会导致饥饿？

▸ 答案：因为 Lamport 时间戳给出全序：每个请求都有确定位置，先到者先被回复。只要请求最终被处理（节点不永久失联），排在前面的一定先进入，不会出现 “后来者不断插队”。饥饿风险来自 “节点永久失联导致永远等不到回复”，那是容错问题，不是公平性问题。