L08b-2 活锁与 Multi-Paxos:抢编号会卡住,选一个 leader 就顺了
两个 proposer 轮流用更大编号互相挡掉 accept,Paxos 会卡在活锁里;单一 leader 或指数退避能化解,Multi-Paxos 选一次 leader 后只跑 accept。最后把 Basic Paxos、Multi-Paxos、VR 放在一张表里对照。
一句话版
两个 proposer 轮流拿更大的编号去 prepare,每次都把对方刚要落地的 accept 挡掉,谁也选不出值,这叫活锁。解法是只让一个 leader 提议,或者让抢号的人越等越久。Multi-Paxos 选一次 leader,后面每个值只跑 accept,又快又不打架。
两阶段的规则见上一页 L08b。这一页先看 Paxos 怎样卡住,再看怎样提速,最后和 VR 对照。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 活锁 | livelock | 大家都在动,却谁也选不出值 |
| 指数退避 | exponential backoff | 每失败一次,下次多等一倍再试 |
| leader | 领导者 | 唯一负责提议的那个 proposer |
| 实例 | instance | 一次 Paxos 只选一个值;要选一串命令就跑一串实例 |
| Multi-Paxos | 多实例 Paxos | 选一次 leader,连定多个值 |
| 安全性 / 可用性 | safety / availability | 不会选错 / 总能选出来 |
一个类比:两个人抢话筒
会议上两个人都想发言。规矩是:谁的号大,听谁的。
张三领了 5 号,刚要开口,李四领了 6 号,主持人请张三坐下。李四刚要开口,张三又领了 7 号,主持人又请李四坐下。两人轮流抢号,会开了一下午,一个决议也没通过。
没有人说错话,只是什么都没说成。
解法有两种。一种是会前定好只有一个人能发言。另一种是谁被打断了,就先等 1 分钟再抢,再被打断就等 2 分钟,等得越来越久,总有一次能把话说完。
类比在哪里失效:
- 会议里大家看得见彼此在等。协议里的 proposer 只能靠超时猜对方在干什么。
- 主持人在类比里像一个人。协议里每个 acceptor 各自判断,没有中央主持。
从零讲起
1. 活锁:两个 proposer 抢编号
它解决什么问题
上一页的规则保证了「不会选出两个值」。这个概念要回答反面的问题:Paxos 能不能保证一定选出一个值?
答案是不能。两个 proposer 互相挡,可以一直挡下去。
从哪来(补充)
这和一个著名的理论结果有关。FLP 结论说:在异步网络里,没有任何确定性的容错共识协议能保证一定推进。Paxos 的取舍是保证安全性,不保证一定终止。
出处:Wikipedia: Paxos (computer science)
直觉
acceptor 只听号大的。P1 刚拿到承诺准备 accept,P2 用更大的号把承诺抢走,P1 的 accept 就被拒。P1 不甘心,用更大的号抢回来,P2 的 accept 又被拒。
一步一步看
目标:看两个 proposer 轮流用更大编号挡掉对方,为什么永远选不出值。
课件活锁图的场景:P1、P2 两个 proposer,A1、A2、A3 三个 acceptor,多数是 2。
-
P1 发 prepare(n),拿到 A1、A2 的承诺,下一步本该发 accept(n)。
-
P1 还没发 accept,P2 用 n+1 发 prepare,拿到 A2、A3 的承诺。P1 的 accept(n) 到了 A1,被接受;到了 A2,A2 已承诺 n+1,拒绝。P1 只有 A1 一票,不够多数。
-
P1 换 n+2 重新 prepare,又把 A2 抢回来。P2 的 accept(n+1) 到 A2 被拒,也不够多数。两人轮流用更大的编号挡掉对方,永远选不出值。
怎么判断
判断一段 Paxos 过程是不是活锁,看两点:
- 每一轮都有 proposer 发出 accept,但没有一个 accept 凑到多数。
- 失败的原因每次都是「acceptor 已向更大的编号承诺」。
意思是:两条都成立,就是编号竞争导致的活锁。这时没有值被选定,也就不存在选错的问题。
两种解法的道理:
- 单一 leader:只有一个人发 prepare,没人来抢号。
- 指数退避:被拒后等一段时间再试,每次等的时间翻倍,让上一轮的 prepare 和 accept 有机会走完。
常见误解
活锁说明 Paxos 可能选出两个不同的值
活锁时一个值都没选出来,安全性没有被破坏,损失的只是可用性。这正是课件说「Paxos 不总能保证可用性」的原因。
以为活锁和死锁是一回事
死锁是大家都停着互相等。活锁里大家都在发消息、换编号,一直在动,只是没有进展。
试一下
用指数退避,第一次被拒后等 1 个单位时间,之后每次翻倍。连续被拒 4 次,每次各等多久?一共等了多久?
依次等 1、2、4、8 个单位,一共 1 + 2 + 4 + 8 = 15 个单位。
2. Multi-Paxos:选一次 leader,连定多个值
它解决什么问题
一次 Paxos 只选一个值。真实系统要对一长串命令排好顺序,每条命令都跑一遍完整的两阶段,消息多、延迟大,还容易抢编号。
Multi-Paxos 的想法是:先选出一个稳定的 leader,后面的值都由它来提,不用每次都 prepare。
从哪来(补充)
leader 稳定时,后续实例可以跳过 prepare/promise 这一阶段。没有故障时,从客户端请求到选定的延迟,从 4 次消息延迟降到 2 次。Google 的 Chubby 锁服务就用 Paxos 保持各副本一致。
出处:Wikipedia: Paxos (computer science)
直觉
prepare 的作用是要承诺、摸旧值。leader 第一次 prepare 拿到承诺后,没人跟它抢号,这份承诺一直有效。后面的实例就可以直接 accept。
这样做也顺带解决了活锁:只有 leader 提议,没人抢号。
一步一步看
目标:比较定三条命令时,Single-Paxos 和 Multi-Paxos 各要跑几次 prepare。
课件的 Example 4:要定三条命令 set x=1、set y=2、set z=3。
-
Single-Paxos:实例 1 跑 prepare、accept 定下 set x=1。
-
实例 2 再跑一遍 prepare、accept 定下 set y=2;实例 3 再跑一遍定下 set z=3。一共 3 次 prepare、3 次 accept。
-
Multi-Paxos:实例 1 跑 prepare,确立 leader,再 accept 定下 set x=1。
-
实例 2、3 leader 已在,只跑 accept。一共 1 次 prepare、3 次 accept。
怎么算
定 m 条命令时,两种做法的阶段数:
Single-Paxos:m 次 prepare + m 次 accept Multi-Paxos:1 次 prepare + m 次 accept
意思是:命令越多,省下的 prepare 越多,省下的是 m − 1 轮。leader 失效时才需要新的 proposer 重新 prepare,这时又回到普通 Paxos 的规则,旧值照样要沿用。
常见误解
以为 Multi-Paxos 跳过 prepare 就不安全了
leader 的第一次 prepare 已经拿到过半承诺,只要没人用更大编号来抢,这份承诺就一直有效。有新 proposer 用更大编号来 prepare 时,规则和普通 Paxos 一样,安全性不变。
试一下
用 Multi-Paxos 定 5 条命令,leader 一直没失效。一共跑几次 prepare、几次 accept?Single-Paxos 呢?
Multi-Paxos:1 次 prepare + 5 次 accept。Single-Paxos:5 次 prepare + 5 次 accept。
3. VR 与 Paxos 对照
它解决什么问题
VR 和 Paxos 都靠 2f+1 和多数集交集,考试常问「两者差在哪」。这张对照帮你把差别落在领导者这一处。
直觉
VR 一开始就有主节点,主节点挂了才换。Paxos 一开始谁都能提,后来为了不打架、为了快,又选出 leader。Multi-Paxos 因此长得很像 VR。
一步一步看
目标:逐项对照 Basic Paxos、Multi-Paxos 和 VR,看差别落在领导者这一处。
按课件的三方对照逐项看:
- 节点数:三者都是 2f+1。
- 法定人数:三者都是 f+1,过半。
- 容错:三者都最多容忍 f 个崩溃,不处理会撒谎的节点。
- 领导者:Basic Paxos 没有固定领导者,可能多个 proposer 竞争;Multi-Paxos 选出稳定 leader,分摊 prepare;VR 每个视图一个主节点。
- 领导者失效:VR 走 view change 选新主节点;Paxos 由任何 proposer 用更大编号重新发起。
| 项目 | Basic Paxos | Multi-Paxos | VR |
|---|---|---|---|
| 节点数 | 2f+1 | 2f+1 | 2f+1 |
| 法定人数 | f+1 | f+1 | f+1 |
| 领导者 | 无固定,可能竞争 | 稳定 leader | 每个视图一个主节点 |
| 领导者失效 | 换更大编号重来 | 新 proposer 重新 prepare | view change |
| 类型 | 法定人数式 | 法定人数式 | 主备式 |
怎么判断
遇到一个协议描述,问一句:提值的权利是固定给某一台,还是谁都能拿编号去争?
意思是:固定给一台、失效后整体换届的,是 VR 这类主备式;谁都能争、靠编号排先后的,是 Paxos 这类法定人数式。
常见误解
Paxos 比 VR 更新,所以 VR 已经没用
VR 1988 年就有,只是长期不出名;Paxos 更通用但更难懂难实现,VR 和它的后代 Raft 更容易推理和实现。
试一下
三台服务器写 set x=1,A 失效。VR 和 Paxos 各由谁接着推进?
VR:B、C 发起 view change,选出新主节点(比如 B),由它接着处理。Paxos:B 或 C 都可以用更大编号发 prepare,从 promise 里拿回已接受的值后再 accept。
把它们串起来
上一页的两阶段保证了安全:不会选出两个值。它没保证进展。
两个 proposer 抢编号就是反例。每个 accept 都被更大的编号挡住,一个值都选不出来。这不违反安全,只损失可用性。
解法都指向同一件事:别让人抢。单一 leader 干脆只让一个人提;指数退避让抢的人越等越久。
Multi-Paxos 把单一 leader 用到底,选一次 leader,后面只跑 accept,于是又长得像 VR。三者的地基都是 2f+1 和 f+1,差别只在领导者怎么产生、失效后怎么换。
课件里的坑
- [课件有误] p.33 活锁图第二段标注「A1 reject due to promise(n+1)」。这一段 P2 的 prepare(n+1) 只发给了 A2、A3,被拒的虚线也是从 A2 发出,应为 A2 reject。第三段「A2 reject due to promise(n+2)」是对的(p.33)。
- [页码说明] 课堂批注版比原版多 3 页,分别插在原版 p.19、p.29、p.42 之后。本页写「批注版 p.N」的按批注版计,其余页码按原版。
- [读图提醒] p.46 课后题说「page 36 的问题」,内容对应的是 p.39 的三服务器「set x=1」问题(p.46)。
课后 10 分钟:考点复习
这 10 分钟怎么用:先合上页面,把活锁的三帧画出来;再用两句话说清活锁为什么不破坏安全;然后默写三方对照表,最后做完整例题和变式题。
必背
- Paxos 保证一致但不保证可用:活锁靠单一 leader 或指数退避解决;Multi-Paxos 选一次 leader,后续实例只跑 accept
- VR 是主备式(主节点提值、换主走 view change);Paxos 是法定人数式(任何 proposer 可提值、失效后换更大编号)
- 活锁时一个值都没选出来,安全性没有被破坏,损失的只是可用性
- Multi-Paxos 定三条命令:只有实例 1 跑 prepare 并确立 leader,实例 2、3 只跑 accept
- Basic Paxos、Multi-Paxos、VR 都是 2f+1 个节点、f+1 的多数法定人数、最多容忍 f 个崩溃,差别在领导者
课件例题
例 1(课件 p.33):活锁
P1 发 prepare(n),P2 发 prepare(n+1),P1 的 accept(n) 被拒;P1 再发 prepare(n+2),P2 的 accept(n+1) 又被拒。怎么破?
提示
问题出在两个人都能发 prepare。
解答
大编号的 prepare 一直挡住小编号的 accept,谁也选不出值。解法:选单一 proposer 当 leader;或给连续发 prepare 的 proposer 加指数增长的等待,让上一轮提案先走完。
老师在这页写了 f=1、f+1=2,退避的板书是 1m、2m、4m、8m 逐次翻倍,目的是让上一轮的 prepare 和 accept 走完(批注版 p.35)。
例 2(课件 p.36,Example 4):Multi-Paxos 定三条命令
要定 set x=1、set y=2、set z=3,哪些实例跑 prepare?
提示
leader 什么时候确立?
解答
只有实例 1 跑 prepare 并选出 leader;实例 2、3 leader 已在,只跑 accept。选一次 leader,连定多个值。
例 3(课件 p.38,Exercise 3):A2 崩溃的 Multi-Paxos
见下方完整例题。
例 4(课件 p.39、p.41):三台服务器用 Paxos 写入 set x=1
A、B、C 三台服务器,A 当 proposer。写出 set x=1 的两阶段,以及 A 失效后怎样继续。
提示
失效后的接手者要先 prepare 摸旧值。
解答
A 给 B、C 发 prepare(n),B、C 回 promise(n);A 发 accept(n, “set x=1”),B、C 回 accepted;多数接受后选定。A 失效时,B 或 C 用更大编号重新发起,协议保证只选出一个值。
例 5(课件 p.46,Take-home):画 VR 和 Paxos 的流程,含换人
按三服务器写 set x=1 的场景,分别画出 VR 和 Paxos 的流程,并画出领导者失效后的接手过程。
提示
题面写的页码对不上,先找到真正对应的那一页。
解答
题面写「page 36 的问题」,按 p.39 的三服务器写 set x=1 来画。VR 部分:正常操作四步,再画 A 失效后 B、C 发起 view change、B 当选。Paxos 部分:两阶段,再画 B 用更大编号 prepare,从 promise 里拿回已接受的值后发 accept。
完整例题
题面:Multi-Paxos,1 个 proposer、3 个 acceptor A1、A2、A3,A2 已崩溃。accept 阶段 proposer 要等几个 acceptor 回应?learner 要等几个?(课件 p.38,Exercise 3)
约定:3 个 acceptor,f = 1,多数是 2;崩溃的 acceptor 不回任何消息。
解法:
- proposer 发一次 prepare,A1、A3 回 promise。2 个 = 多数,leader 确立。
- 之后每个实例只跑 accept。proposer 发 accept,A1、A3 回 accepted。
- proposer 要等 2 个(A1、A3)回应,才算这个值被多数接受。
- learner 收到 3 个中 2 个 acceptor 的通知即确认,也是 2 个。
- 再崩一个就只剩 1 个,凑不够过半,协议停住但不会出错。
要点:两个问号都填 2。老师课上在两个问号处都填了 2,箭头只画到 A1 和 A3(批注版 p.40)。
答题格式:先写多数的算式(3 个里的过半是 2),再分 prepare 一次、accept 每实例一次两段写消息,最后答两个问号。
变式题(先自己做)
(1) 5 个 acceptor 跑 Multi-Paxos,有 2 个崩溃。leader 每个实例的 accept 要等几个回应?再坏一个呢?(改编自课件 p.38)
提示
5 个的过半是几?
判分点与答案(非官方评分标准)
5 = 2 × 2 + 1,f = 2,过半是 3。坏 2 个剩 3 个,正好够,等 3 个。再坏一个只剩 2 个,凑不够,协议停住但不会选错。
(2) 三个 proposer 同时用 Basic Paxos 提值,彼此不断用更大编号 prepare。系统会选出两个不同的值吗?会怎样?(改编自课件 p.33)
提示
活锁影响的是安全性还是可用性?
判分点与答案(非官方评分标准)
不会选出两个值,两阶段的规则保证安全。可能陷入活锁,谁的 accept 都凑不到多数,一个值都选不出来。用单一 leader 或指数退避化解。
(3) 某协议规定:每个任期只有一个节点能提值,它失联后其余节点先停下、选出下一任再继续。它更像 VR 还是 Basic Paxos?(自编情境)
提示
提值的权利是固定的还是竞争的?
判分点与答案(非官方评分标准)
更像 VR:提值权固定给一台,失效后整体换届,属于主备式。Basic Paxos 里谁都能拿编号去争。
闪卡自测
1. 活锁的两种解法?
只选一个 proposer 当 leader;连续 prepare 之间加指数增长的等待(p.33)。
2. True or False: Paxos always guarantees availability.
中文:Paxos 总能保证可用。
False. 活锁时选不出值;Paxos 保证的是一致(p.22、p.33)。
3. Multi-Paxos 比 Single-Paxos 省在哪?
leader 选一次,后续实例省掉 prepare,只跑 accept(p.34–36)。
4. VR 和 Paxos 在领导者失效时的处理有什么不同?
VR 走 view change 选新主节点;Paxos 由任何 proposer 用更大编号重新发起(p.42)。
5. 3 个 acceptor 里 A2 崩溃,Multi-Paxos 的 learner 要等几个通知?
2 个,A1 和 A3(批注版 p.40)。
6. Basic Paxos、Multi-Paxos、VR 的共同点是什么?
都是 2f+1 个节点、f+1 的多数法定人数、最多容忍 f 个崩溃(p.42)。
下一讲
下一讲是 L09a PBFT。PBFT 回到会撒谎的节点,想一想为什么交集里只有一个节点不再够用。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。