← COMP5567 全部讲次
L08b · 第 8 周

L08b Paxos 两阶段:谁都能提议,但已选定的值只能被再提一遍

没有固定主节点时怎样让多数选出同一个值:先认识 proposer、acceptor、learner 和提案编号,再一帧一帧跑 prepare/promise 与 accept 两阶段,看后来者为什么必须沿用旧值,以及 acceptor 怎样决定接受还是拒绝。

一句话版

Paxos 没有固定主节点,谁都可以提议,靠编号决定谁有发言权。发言前要先问一圈「之前同意过什么」,问到旧值就只能把旧值再提一遍,所以已经选定的值不会被换掉。

VR 的主备做法和多数集交集见 L08a。这一页讲单个值怎样被选定;多个提议者抢编号卡住、Multi-Paxos 和两种协议的对照,见下一页 L08b-2。

先认识这几个词

词 全称 / 读法 一句人话
Paxos 协议名,取自一个希腊岛名 没有固定主节点,靠编号和投票选定一个值
proposer 提议者 发起提议、想让大家选某个值的人
acceptor 接受者 投票接受或拒绝提议的人,过半接受就算选定
learner 学习者 得知最终选定了哪个值的人
提案编号 n proposal number 全局唯一、越来越大的号,号大的才有发言权
promise 承诺 acceptor 答应以后不再接受比 n 小的编号
选定 chosen 某个值被过半的 acceptor 接受

一个类比:没有值班经理的分行投票

四家分行要定一个数,没有固定的值班经理。谁都可以发起「我提议把这个数定成 42」,但发起前要领一个比自己用过的都大的号。

发起人先问一圈:「你们还认不认更早的号?之前同意过什么?」分行答应「以后不认更小的号」,同时报告自己同意过的提议。

只要有人回答「我已经同意过 99」,发起人就只能把 99 再提一遍,不能换成自己的 42。

等过半的分行都答应了,发起人才正式请大家投票。过半投了同意,这个数就定下了。之后谁再来问,都会问到它。

类比在哪里失效:

  • 真实分行能打电话确认对方倒闭没有。协议里的节点只能靠超时去猜,猜错了也不能出错。
  • 类比里的「问一圈」像开会。协议里每一步都只是发消息、数回应。

从零讲起

1. 角色与提案编号

它解决什么问题

VR 只有一个主节点排号,主节点挂了就要先停下来换届。Paxos 想去掉这个固定的角色,让谁都可以提议。

这样一来,必须先说清楚:谁提议,谁投票,谁听结果;两个人同时提议时,凭什么排先后。

从哪来(补充)

Paxos 由 Leslie Lamport 提出,1989 年首次投稿,1998 年以论文「The Part-Time Parliament」发表在 ACM TOCS 上。名字取自希腊 Paxos 岛上一个虚构的议会表决制度,论文就用这个议会的故事来讲协议。

出处:Wikipedia: Paxos (computer science)

直觉

把编号想成发言的排队号。号越大越新,acceptor 只听号大的。

一台机器可以身兼几个角色。三台服务器里,A 当 proposer 去提议,B、C 当 acceptor 投票,也可以三台都兼任 acceptor。

一步一步看

目标:按顺序走一遍一次提议,看 proposer、acceptor、learner 各管哪一步,谁的票算进过半。

把一次提议里各个角色做的事按顺序排开:

  1. proposer 领一个编号 n,n 全局唯一,并且比它用过的任何编号都大。
  2. proposer 拿着 n 去问 acceptor。
  3. acceptor 按编号大小决定答不答应、接不接受。
  4. 过半的 acceptor 接受了同一个提案,这个值就选定了。
  5. learner 收到通知,得知选定的值。
角色 做什么 算不算进法定人数
proposer 领编号、发起提议 只有兼任 acceptor 时,它的那一票才算
acceptor 承诺、接受或拒绝 算,过半的 acceptor 决定结果
learner 听结果 不算

怎么判断

要容忍 f 个 acceptor 崩溃,就要 2f+1 个 acceptor,每一步等 f+1 个回应。

意思是:和 VR 一样,剩下的 f+1 个还够过半,两组过半必有交集。数票时只数 acceptor,proposer 自己不额外算一票。

课件流程图有 3 个 acceptor,老师在每个「等多数」处都写了 f+1。这里 f 是 1,即等 2 个。

常见误解

proposer 发起提议,自己就算一票

法定人数数的是 acceptor。proposer 只有兼任 acceptor 时,它作为 acceptor 的那一票才计入。

以为编号只要在同一个 proposer 内部递增就行

编号还要全局唯一。两个 proposer 用了同一个编号,acceptor 就分不清该听谁的。

试一下

5 个 acceptor,最多容忍几个崩溃?每一阶段要等几个回应?

5 = 2 × 2 + 1,f = 2,每一阶段等 f+1 = 3 个 acceptor 回应。

2. 两阶段:先要承诺,再请接受

它解决什么问题

谁都能提议,就会有两个人同时提不同的值。Paxos 要保证:同一个实例里只选出一个值,并且一旦选定,以后不会被换掉。

办法是把一次提议拆成两步。第一步先摸底、要承诺,第二步才正式请大家接受。

直觉

第一阶段像在问:「我拿 1 号发言,你们认不认?之前接受过什么?」第二阶段才说:「那就定 42 吧。」

先摸底的好处是,如果之前已经有值被选定,第一阶段一定能问出来。

一步一步看

目标:跟着 A 提 42 走完两个阶段,看一个值在哪一刻算选定。

课件的 Example 2:A 当 proposer,B、C 当 acceptor,A 想提 42,用编号 1。每一帧里近黑的是这一步的消息,灰色的是前面走完的步骤。

  1. 第一阶段。A 给 B、C 发 prepare(1),问编号 1 认不认。

    Paxos 选定 42 第一帧:四条泳道是 proposer A、acceptor B、acceptor C、learner,A 向 B 和 C 各发一条 prepare(1) 箭头

  2. B、C 都没向别人承诺过,回 promise(1),答应不再接受比 1 小的编号。它们没接受过任何提案,所以 promise 里不带旧值。A 拿到两个承诺,是 3 个里的多数。

    Paxos 选定 42 第二帧:B 和 C 向 A 回 promise(1) 箭头,两人身上标着没接受过,前一步的 prepare 退成灰色

  3. 第二阶段。没有旧值,A 就用自己想提的 42,发 accept(1, 42)。B、C 接受,记下 (1, 42),通知 learner。多数接受的那一刻,42 就选定了。

    Paxos 选定 42 第三帧:A 向 B、C 发 accept(1, 42),B、C 记下 (1, 42) 后向 learner 发通知,learner 旁青绿标签写着选定 42

怎么算

proposer 在两个阶段各要凑一次多数:

  • 第一阶段:promise 的个数 ≥ f+1,才能进入第二阶段。
  • 第二阶段:accepted 的个数 ≥ f+1,值才算选定。

意思是:哪一阶段凑不够,就停在哪一阶段,这一轮不选值。proposer 换一个更大的编号重新来过。

常见误解

以为 proposer 发出 accept 就等于值已选定

发出不算,要等过半的 acceptor 真的接受。accept 阶段只有 1 个回 accepted,这一轮什么也没选出来。

以为 learner 也要参与投票

learner 只听结果。它从 acceptor 那里得知哪个值被过半接受,不影响值能不能选定。

试一下

3 个 acceptor,proposer 发 prepare(4),只有 1 个回 promise(4)。下一步该做什么?

1 < 2,第一阶段没凑够多数,不能发 accept。这一轮作废,proposer 稍后换一个更大的编号(比如 5)重新 prepare。

3. 后来者必须沿用旧值

它解决什么问题

上一个概念里没人捣乱。如果 99 已经被选定,另一个 proposer 又想提 42,会不会把 99 冲掉?

Paxos 的回答是不会。规则只有一条:promise 要报告自己接受过的、编号最大的提案;proposer 只要收到旧值,就必须用它。

直觉

99 已经被过半接受。后来者的第一阶段也要问过半的人,两组过半必有交集,交集里那台一定会报告 99。

后来者拿着更大的编号,换来的只是发言权。它说的内容只能是 99。

一步一步看

目标:看 99 已被选定后,A 拿更大的编号再提,为什么最后只能把 99 再提一遍。

课件的 Example 3:X 和 A 两个 proposer,B、C 是 acceptor。

  1. X 已经跑完两阶段:B、C 都接受了 (1, 99)。三个 acceptor 里两个接受,99 已被选定。

    两个 proposer 竞争第一帧:四条泳道是 proposer X、proposer A、acceptor B、acceptor C,X 向 B、C 发过消息,B、C 身上标着记录 (1, 99)

  2. A 本想提 42,选了更大的编号 2 发 prepare(2)。B、C 回 promise(2),各自附上接受过的 (1, 99)。

    两个 proposer 竞争第二帧:A 向 B、C 发 prepare(2),B、C 回 promise(2),A 身上标着带回 (1, 99) 两份,X 的消息退成灰色

  3. A 只能把 99 再提一遍,发 accept(2, 99)。B、C 记下 (2, 99)。编号从 1 变成 2,值还是 99。

    两个 proposer 竞争第三帧:A 向 B、C 发 accept(2, 99),B、C 标着 (2, 99),底部青绿字写编号从 1 变成 2,值还是 99

怎么判断

proposer 拿到过半 promise 后,按这一条选 accept 里的值:

  • promise 里有旧提案:取编号最大的那个提案的值。
  • promise 里都没有旧提案:用自己想提的值。

意思是:只要可能有值被选定过,它一定会出现在某个 promise 里,并且编号最大的那个就是要沿用的值。proposer 没有选择权。

常见误解

编号更大的提案能覆盖旧值

更大的编号只换来发言权,不换来改值权。99 在第一步就被多数接受、已经选定,之后任何提案都必须沿用它。

以为几个 promise 带了不同的旧值时,proposer 可以挑自己喜欢的

只能取编号最大的那个提案的值。编号最大的那个才是最近一次可能被选定的。

试一下

proposer 发 prepare(9),收到三个 promise:一个带 (4, red),一个带 (7, blue),一个什么都没带。accept 里该用哪个值?

取编号最大的旧提案 (7, blue),发 accept(9, blue)。

4. acceptor 的规则:接受还是拒绝

它解决什么问题

前三个概念都站在 proposer 那边。acceptor 收到 prepare 和 accept 时怎么回,也要有一条死规矩,否则承诺就是空话。

直觉

acceptor 心里只记一个数:自己承诺过的最大编号。收到任何消息,都拿消息的编号和这个数比。

一步一步看

目标:看 acceptor 怎样拿消息编号和自己承诺过的最大编号比一比,决定回 promise、接受还是拒绝。

  1. acceptor 收到 prepare(n)。n 比承诺过的都大,就回 promise(n),附上自己接受过的编号最大的提案,并把承诺升到 n。

  2. acceptor 收到 accept(n, v)。n 不小于承诺过的最大编号,就接受,回 accepted(n, v),记下 (n, v)。

  3. n 小于承诺过的最大编号,就拒绝,因为接受它会违反之前的承诺。

    acceptor 处理 accept 消息的判断流程:顶部方框问 n 是否大于等于承诺过的最大编号,是则进入青绿框接受并回 accepted(n, v)、记下 (n, v),否则进入拒绝框,底部说明 prepare 同理

怎么判断

收到 accept(n, v) 时:

n ≥ 已承诺的最大编号 → 接受;n < 已承诺的最大编号 → 拒绝

意思是:只比编号,不管这个提案是谁发的,也不管自己有没有收到过对应的 prepare。

常见误解

以为 acceptor 没收到过 prepare(6),就不能接受 accept(6, v2)

规则只比较编号。6 比承诺过的 5 大,acceptor 没向更大的编号承诺过,就接受。

试一下

acceptor 已回过 promise(3)。依次收到 accept(2, a)、accept(3, b),各怎么回?

accept(2, a):2 < 3,拒绝。accept(3, b):3 = 3,不小于承诺的编号,接受,记下 (3, b)。

把它们串起来

VR 把排序权交给一个主节点。Paxos 拿掉固定主节点,谁都可以提议,于是要回答新问题:两个人同时提不同的值怎么办。

答案是编号加两阶段。编号决定谁有发言权,acceptor 只听号大的。「promise 必须报告旧值」决定发言内容。

多数集交集保证后来者一定问得到旧值。已经被过半接受的值,后来者只能原样再提一遍。

acceptor 一侧只有一条规矩:拿编号和承诺比。所有的安全性都落在这一次比较上。

课件里的坑

  • [读图提醒] p.31 箭头端点画重复:两条 promise(1) 都从 C 出发、两条 accept(1, 99) 都指向 B 等。按文字和方框理解,每对消息一条给 B、一条给 C(p.31)。
  • [页码说明] 课堂批注版比原版多 3 页,分别插在原版 p.19、p.29、p.42 之后。本页写「批注版 p.N」的按批注版计,其余页码按原版。
  • [课件笔误] p.32 表格第 2 行写「another processor」,老师改成 proposer(批注版 p.34)。
  • [读图提醒] 故障情形编号 (1)、(2) 后直接跳到 (4),没有 (3)(p.28–33)。
  • [历史口径] p.4 写 Paxos 1988 首次提出。常见说法是 1989 年首次投稿、1998 年正式发表,答题写 1998 年正式发表不会错(p.4)。

课后 10 分钟:考点复习

这 10 分钟怎么用:先合上页面,默写两阶段的四种消息和 acceptor 的比较规则;再把 Example 3 的三帧自己画一遍;然后把完整例题的表空着填一次,最后做变式题。

必背

  1. Paxos 两阶段:prepare(n)/promise 附上已接受的最大编号提案;accept(n,v) 的 v 必须沿用该值,没有才用自己的
  2. Paxos 用 2f+1 个 acceptor 容忍 f 个崩溃;proposer 只有兼任 acceptor 才计入法定人数
  3. Paxos 角色:proposer 提值、acceptor 投票、learner 得知结果;提案编号全局唯一且递增
  4. acceptor 收到 accept(n,v):没向比 n 更大的编号承诺过就接受,否则拒绝;比较只看编号
  5. acceptor 或 proposer 失效:凑得到多数就继续;凑不到就换更大编号重试,接手者从 promise 里拿回已接受的旧值

课件例题

例 1(课件 p.27,Example 2):选定 42

A 想提 42,用编号 1 给 B、C 发 prepare。写出到选定为止的消息。

提示

B、C 之前没接受过任何提案。

解答

B、C 都没承诺过,回 promise(1),不带旧值。A 收到多数承诺,发 accept(1, 42);B、C 接受,回 accepted(1, 42)。多数接受后 42 被选定,learner 得到通知。

例 2(课件 p.28):acceptor 失效

某个 acceptor 在 prepare、accept 或 learn 阶段崩溃,Paxos 怎么办?

提示

剩下的 acceptor 还够不够多数?

解答

它不回 promise 或 accepted,proposer 和 learner 只要凑到多数就行。accept 阶段凑不到多数,这一提案没选出值,proposer 换更大编号重试。

老师的板书:3 个 acceptor、f 为 1,A3 崩溃后还有 2 个回应,够多数;accept 阶段凑不够时,编号 n=1 的提案失败,换 n=2 重来(批注版 p.29)。

例 3(课件 p.29):proposer 失效

proposer 在 prepare 阶段或 accept 阶段崩溃,各会怎样?

提示

accept 阶段崩溃时,可能已经有 acceptor 接受了它的值。

解答

prepare 阶段崩溃,acceptor 收不到 accept,别的 proposer 用更大编号重新发起。accept 阶段崩溃,别的 proposer 发 prepare 时会从 promise 里得知已接受的旧值,只能用这个旧值发 accept。

老师的板书:P 用 n=1 时在 prepare 阶段崩溃,P2 用 n=2 重新发起;accept 阶段崩溃的情形,旁注指向后面的 Example 3(批注版 p.30)。

例 4(课堂批注版 p.31):一次成功、两种失败

1 个 proposer、3 个 acceptor、2 个 learner,多数是 3 个里的 2 个。比较三种情形:多数 acceptor 都回应;只有 1 个回 promise;promise 够了但只有 1 个回 accepted。各自结果如何,失败后怎么接着走?

Paxos 成功与两种失败情形对照图:3 个 acceptor、多数为 2;成功时 prepare、accept 都收到多数回应,值被选定并通知 learner;prepare 阶段只有 1 个 promise 则不能进入 accept,需用更大编号重试;accept 阶段只有 1 个 accepted 则本轮不选值。红笔写出接手流程:新 proposer 发 prepare(n+1),acceptor 回 promise(n+1) 附上 (n, v),再发 accept(n+1, v)
图片来源:COMP5567 Lecture_8-VR-Paxos-anno.pdf(课堂批注版), p.31,红笔为老师手写批注
提示

两个阶段各要凑一次多数,哪一阶段凑不够就停在哪一阶段。

解答

成功:prepare、accept 两阶段都收到多数回应,值 v 被选定,learner 得到通知。prepare 阶段只有 1 个 promise:不能进入 accept,本轮不选值,稍后重试或由别的 proposer 用更大编号发起;老师在旁边写了 f=1,并在 PREPARE(n′) 后补了 +1。accept 阶段只有 1 个 accepted:本轮也不选值。老师用红笔补了接手流程:P2 发 prepare(n+1),已接受过的 acceptor 回 promise(n+1) 并附上 (n, v),P2 只能发 accept(n+1, v),旁注指向 Example 3。

例 5(课件 p.30–31,Example 3):两个 proposer 竞争

X 已让 B、C 接受 (1, 99)。A 用编号 2 发起,本想提 42。写出 A 收到的 promise 和它最终发出的 accept。

提示

promise 里会附带什么?

解答

B、C 各回 promise(2) 并附上 (1, 99);A 必须发 accept(2, 99),不能发 42。同一个实例只会选出一个值。

例 6(课件 p.32,Exercise 2):填 acceptor 的响应表

见下方完整例题。

完整例题

题面:Proposer P 给 acceptor A、B、C 发 prepare(5),A 回了 promise(5)。之后 A 先收到另一个 proposer 的 accept(3, v),再收到 accept(6, v2)。写出 A 对这两条消息的响应。(课件 p.32,Exercise 2)

约定:A 在 promise(5) 之前没有接受过任何提案;只看 A 一台 acceptor 的反应。

解法:

  1. A 回 promise(5) 后,它承诺不再接受编号小于 5 的提案,记下「已承诺的最大编号 = 5」。
  2. accept(3, v):3 < 5,违反承诺,拒绝。
  3. accept(6, v2):6 > 5,A 没有向更大的编号承诺过,接受,回 accepted(6, v2)。
  4. A 没收到过 prepare(6) 并不影响,规则只比较编号。
  5. 此后 A 记录的已接受提案是 (6, v2),编号不超过 5 的 accept 都会被拒绝。

要点:老师课上的答案与此一致:第 2 步写 Reject(3 < 5),第 3 步打勾并写 accepted(6, v2)(批注版 p.34)。一句话:拿 accept 的编号和已承诺的最大编号比,小于就拒,大于或等于就接受(p.25、p.32)。

答题格式:每条消息写一行「消息 → 比较式 → 接受或拒绝 → 回什么」。

变式题(先自己做)

(1) acceptor A 已回过 promise(7),还没接受任何提案。随后依次收到 accept(6, u)、prepare(8)、accept(7, w)。A 对三条消息各怎么响应?(改编自课件 p.32)

提示

每收到一条,先看 A 当前承诺过的最大编号是几,它会随 prepare 变化。

判分点与答案(非官方评分标准)

accept(6, u):6 小于已承诺的 7,拒绝。prepare(8):8 大于 7,回 promise(8),没有已接受的提案可附带,承诺编号升到 8。accept(7, w):7 小于现在的 8,拒绝。A 最后没有接受任何提案。

(2) 3 个 acceptor 里,B 接受过 (2, apple),C 接受过 (4, pear),D 什么都没接受过。新 proposer 用编号 6 发 prepare,三个都回了 promise。它的 accept 是什么?(改编自课件 p.30–31)

提示

几个旧值里取哪一个?

判分点与答案(非官方评分标准)

取编号最大的旧提案 (4, pear),发 accept(6, pear)。用 apple 或自己的值都错。

(3) 3 个 acceptor,proposer 用编号 1 发 accept(1, 42) 后崩溃,只有 B 接受了。另一个 proposer 用编号 2 发 prepare,只收到 C、D 的 promise。它该提哪个值?会不会和 42 冲突?(自编情境)

提示

42 当时被过半接受了吗?C、D 的 promise 里有没有旧值?

判分点与答案(非官方评分标准)

42 只被 B 一个接受,没过半,没被选定。C、D 都没接受过提案,promise 里不带旧值,新 proposer 可以用自己的值。这不违反安全性,因为 42 从未被选定。

闪卡自测

1. Paxos 三种角色各做什么?

proposer 提值,acceptor 投票接受或拒绝,learner 得知最终的值(p.24)。

2. Paxos 的提案编号有什么要求?

全局唯一,且大于该 proposer 用过的任何编号(p.24)。

3. promise 里要附带什么?

该 acceptor 已接受过的编号最大的提案,没有就不带(p.25)。

4. proposer 收到的 promise 里带了旧值,accept 该用哪个值?

用 promise 里编号最大的那个提案的值,没有旧值才用自己的(p.25)。

5. acceptor 什么时候拒绝 accept(n, v)?

它已经向比 n 更大的编号承诺过(p.25)。

6. accept 阶段只有 1 个 acceptor 回 accepted,新 proposer 怎样接手?

发 prepare(n+1);接受过 (n, v) 的 acceptor 在 promise(n+1) 里附上它,新 proposer 只能发 accept(n+1, v)(批注版 p.31)。

7. 3 个 acceptor 里 1 个崩溃,Paxos 还能选出值吗?

能。剩 2 个,仍是 3 个里的多数(p.28)。

下一讲

下一页是 L08b-2 活锁、Multi-Paxos 与 VR 对照:两个 proposer 轮流抢编号会怎样,怎样选一个 leader 省掉 prepare。带着问题读:卡住的时候,选出两个不同值的风险有没有出现?

下一讲 →
L08b-2 L08b-2 活锁与 Multi-Paxos:抢编号会卡住,选一个 leader 就顺了

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。