鲁班 - 系统设计大全

20.5 三种算法对比 (消息量 / 公平性 / 可用性)

一句话

三种互斥算法是三个固定的取舍：集中式用中心换消息（2 条），Ricart-Agrawala 用消息换去中心（2(N−1) 条），令牌环用延迟换公平（O(N) 跳）；没有最优，只有 “你的瓶颈是消息、延迟还是容错”。

一张表看完

维度 集中式（协调者 + 租约） Ricart-Agrawala（全票） 令牌环
每次进入消息数 2 + 1（释放） 2(N−1) 1（令牌传递）
进入延迟 1 RTT 1 RTT（等最慢回复） 平均 N/2 跳
公平性 可做 FIFO，取决于实现 天然按时间戳 FIFO 严格轮转
容错 中心挂 = 不可用；有副本需共识 任一节点挂 = 卡住 任一环断 = 停摆
单点 有（可高可用化） 无 无
实现复杂度 低 中 中高（环维护）
规模 大（中心可扩展） 小（N < 10） 中（依赖延迟）
生产可用性 高（租约 + fencing） 低 低

选型判据

你的情况 选择
通用场景、要求可用性 集中式 + 租约 + fencing（生产默认）
节点少、要严格轮流、无中心 令牌环
学术/嵌入式、可接受零容错 Ricart-Agrawala
跨地域、网络分区频繁 集中式（区域中心）+ 分区内自治，不要全票算法

数字直觉

  • N=5：集中式 3 条 vs RA 8 条 vs 环平均 2.5 跳。
  • N=100：集中式 3 条 vs RA 198 条 vs 环平均 50 跳。

消息量是 O(1)、O(N)、O(1) 但延迟 O(N)——三个不同的增长曲线，决定了适用规模。

三种算法的细节分别在 20.2 集中式互斥 (协调者)、20.3 分布式互斥 (Ricart-Agrawala / 全票通过)、20.4 令牌环互斥。

代码：一次互斥的 “预算表”

集中式：  acquire 1 RTT + release 1 RTT   ≈ 2 RTT，消息 3 条
RA：      广播 N-1 + 收 N-1              ≈ 1 RTT（等最慢），消息 2(N-1)
令牌环：  等令牌平均 N/2 跳 + 传递 1 跳     ≈ (N/2+1) 跳，消息 1 条

选型判据（把 N 代进去算）：
  N &lt; 10 且要求严格公平 → 令牌环
  任意 N，要求可用性    → 集中式 + 租约 + fencing
  封闭环境、可接受零容错 → RA

反模式

反模式 后果
不看规模直接选 RA N 大了消息爆炸
用令牌环做高频互斥 延迟 O(N)，吞吐上不去
集中式不做高可用 锁服务挂 = 全站停写
任何方案都不做 fencing 暂停进程的迟到写破坏互斥

| 只比较消息数就选算法 | 忽略延迟与容错，规模上来后返工 | | 忽视 “算法外的工程” | 成员变更/失联处理才是事故来源 |

三条铁律

🔑 消息量与延迟的增长曲线决定适用规模，不是 “哪个更先进”。

🔑 生产默认集中式；它的单点可以用共识与租约解决，其他两者的容错更难补。

🔑 无论哪种算法，资源侧都要有 fencing。

自检

Q1 为什么生产上更偏爱集中式，尽管它有单点？

▸ 答案：因为单点可以被工程手段消解（多副本 + 共识 + 租约 + 客户端重试），而 RA 与令牌环的 “全票/环” 特性在故障时直接失去活性，且成员变更本身需要共识。集中式的复杂度是 “可运维的复杂度”。

Q2 令牌环 “消息最少” 为什么反而不常用？

▸ 答案：因为延迟随 N 线性增长，而且环维护（加入/离开/令牌丢失）的复杂度很高，任何一处故障都可能导致全局停摆。消息少的好处被 “延迟 + 运维” 抵消。

Q3 如果一定要在 N=50 的集群做互斥，选哪个？

▸ 答案：集中式（带租约与 fencing）：RA 要 98 条消息、令牌环平均 25 跳；集中式 1 RTT 且可水平扩展（按锁名分片到多个协调者）。只有在 “完全不能有中心” 的约束下才考虑其他两者。

Q4 三种算法的公平性差异体现在哪？

▸ 答案：RA 按时间戳 FIFO（先请求先进入）；令牌环严格轮转（每节点一次机会）；集中式取决于队列实现（可 FIFO，也可优先级）。公平性影响的是 “最坏等待时间”，在高竞争场景下比平均延迟更重要。

Q5 为什么说 “算法选对了但没配 fencing 依然会错”？

▸ 答案：因为所有算法都假设 “持有者会按时释放”。现实中进程会暂停（GC、缺页、调度），恢复后仍以为自己持有锁。fencing token 让资源侧能拒绝 “过期的持有者”，这是算法层面的互斥无法覆盖的工程漏洞。

Q7 为什么表中 RA 是 “1 RTT” 而令牌环是 “N/2 跳”？

▸ 答案：因为 RA 的请求/回复并行广播，延迟由最慢的一个回复决定（1 RTT）；令牌环的令牌必须串行逐跳传递，等待时间随环上节点数线性增长。两者消息量与延迟的增长曲线完全不同，这就是 “按规模选” 的数学依据。

关联