← COMP5567 全部讲次
L06b-2 · 第 6 周

L06b-2 分区弱点与取舍:网络一断,两边各判各的

3PC 靠超时换来不阻塞,前提是大家能互相问到。网络分区时两边各选恢复协调者,一边提交一边中止。再把没有协议、2PC、3PC 放在同一笔转账上对照一遍。

一句话版

3PC 的恢复规则要求大家能互相问到。网络断成两块时,两边各选一个恢复协调者,各看各的状态,一边提交、一边中止,网络愈合后结局对不上。

3PC 怎么走、怎么恢复,见上一页 L06b。这一页讲它在哪里出错,再把三种做法放在一起对照。

先认识这几个词

词 全称 / 读法 一句人话
网络分区 network partition 网络断成几块,块与块之间互不相通
愈合 heal 断开的网络重新连上
一致性 consistency 所有节点对同一笔事务的结局相同
非阻塞 non-blocking 不用等崩溃的节点恢复就能继续
不可能性结论 impossibility result 证明某种协议在某种假设下做不出来

一个类比:两间教室各自表决

还是全票通过的那种表决。主席多敲了一锤「准备通过」,才喊到一半就晕倒了。偏偏这时走廊的门被锁上,人被分在两间教室里,互相听不见。

左边教室有人听到了「准备通过」,大家一商量:全票同意过,签字。右边教室没人听到,大家一商量:谁都没签过,作废。

两边都按规矩办事。等门打开,一半人签了字,一半人作废了,同一笔预算出了两种结局。

类比在哪里失效:

  • 教室里的人知道门锁了。网络里的节点分不清「对方崩溃了」和「对方还活着,只是连不上」,看到的都是超时。
  • 现实里可以等门开了再商量。3PC 为了不阻塞,选择不等。

从零讲起

1. 网络分区是什么

它解决什么问题

前面讲 2PC 和 3PC 时,一直假设节点之间总能通信。这一条要是不成立,会发生什么?先得弄清楚「不能通信」长什么样。

从哪来(补充)

Wikipedia 把网络分区定义为:计算机网络被分成相对独立的子网。条目举的例子是交换机故障后,A、B 和 C、D 互相连不上。条目还把它和 CAP 定理联系在一起。

出处:Wikipedia: Network partition

直觉

分区和崩溃不同。崩溃的节点停了;分区里的节点都还活着,只是两块之间的消息过不去。

可在每个节点看来,两者长得一样:等不到回复。3PC 把超时当作对方崩溃,分区时这个猜测就错了。

一步一步看

目标:看网络断成两块后,两边节点为什么都以为对方崩溃了。

  1. 四个参与者 P1–P4,网络正常时彼此相通。

  2. 某个时刻,网络断成两块:P1、P2 在一边,P3、P4 在另一边。

  3. 同一块里的节点照常通信,跨块的消息全丢。

  4. 两边都等不到对方,都以为对方崩溃了。

时刻 P1、P2 之间 P3、P4 之间 跨两块
分区前 相通 相通 相通
分区后 相通 相通 消息全丢

怎么判断

一个节点等不到回复,可能是下面三种情况之一:

情况 对方还活着吗 节点自己能分清吗
对方崩溃 否 分不清,只看到超时
网络分区 是 分不清,只看到超时
网络很慢 是 分不清,只看到超时

意思是:超时只能说明「没收到」,说明不了「对方倒了」。

常见误解

以为分区就是有节点崩溃了

分区时所有节点都可能还活着,只是互相连不上。这正是它难处理的地方。

以为分区很少见,可以不管

一台交换机故障就可能造成分区。课件专门用一页讲 3PC 在分区下的问题。

试一下

P1 等 P3 的回复超时了。P1 能断定 P3 崩溃了吗?

不能。P3 可能崩溃了,也可能和 P1 处在不同分区,或者网络只是慢。P1 只知道「没收到」。

2. 3PC 在分区下不一致

它解决什么问题

3PC 的恢复规则看起来很安全:有人 Prepared 就提交,谁都没收到 PreCommit 就中止。分区时,这两条规则会在两边同时被触发。

直觉

恢复协调者只能看到本侧的状态。两边看到的不一样,按同一套规则就会得出相反的决定。

每一边单独看都合法,合在一起就破坏了原子性。

一步一步看

目标:看分区两边按同一套 3PC 恢复规则,怎样对同一笔事务做出相反的决定。

  1. 网络断成两块,协调者也崩溃了。分区 A 的 P1、P2 收到了 Prepare,分区 B 的 P3、P4 没收到。

    第 1 步:网络断成分区 A 和分区 B,协调者崩溃;分区 A 的 P1、P2 收到 Prepare,分区 B 的 P3、P4 没收到

  2. 两边各选一个恢复协调者:A 选 P1,B 选 P3。P1 看到有人收到 Prepare,P3 看到没人收到。

    第 2 步:两边各选一个恢复协调者,P1 看到有人收到 Prepare,P3 看到没人收到 Prepare,青绿标出

  3. P1 按分支 ② 提交,P3 按分支 ③ 中止。两边都按规则做了「合法」的决定。

    第 3 步:分区 A 按分支 ② commit,P1、P2 Committed;分区 B 按分支 ③ abort,P3、P4 Aborted,青绿标出

  4. 网络愈合。同一笔事务一边提交、一边中止。

    第 4 步:网络愈合,P1、P2 Committed,P3、P4 Aborted;结论文字说明两边结局相反,原子性被破坏

怎么判断

判断一个 3PC 场景会不会不一致,看三个条件是否同时成立:

条件 本例
网络分区,两边各自恢复 成立:A、B 各选恢复协调者
一边有人 Prepared 成立:P1、P2 收到 Prepare
另一边无人收到 PreCommit 成立:P3、P4 没收到

意思是:三条都成立时,两边分别走分支 ② 和分支 ③,结局相反。

常见误解

以为是某一边违反了 3PC 的规则

两边都完全按恢复规则办事。出错的是规则的前提:大家能互相问到。

以为分区下 3PC 会像 2PC 一样阻塞

3PC 不阻塞,它会做出决定,只是两边的决定可能相反。2PC 在这里宁可等,所以不会不一致。

试一下

网络断成两块,两边都有人收到了 Prepare。两边恢复后结局一致吗?

一致。两边都看到有人 Prepared,都走分支 ②,都 commit。不一致只在一边有人 Prepared、另一边无人收到时出现。

3. 有没有两全的协议

它解决什么问题

既然 3PC 在分区下会出错,能不能再打个补丁,让它既不阻塞又抗分区?理论上已经有答案。

从哪来(补充)

Fischer、Lynch、Paterson 在 1985 年证明:异步网络里,只要有一个进程可能崩溃,就没有确定性的共识算法总能结束。这条结论叫 FLP,后来获得了 Dijkstra Prize。

出处:Wikipedia: Consensus (computer science)

直觉

异步网络里,节点分不清「对方慢」和「对方倒了」。要不阻塞,就得在某个时刻不再等,自己做决定。可只要不等,就有可能和另一边做出相反的决定。

所以安全和不阻塞,在这种网络里拿不全。3PC 选了不阻塞,2PC 选了安全。

一步一步看

目标:看时限到了之后自己拿主意和继续等各付出什么代价,弄清安全和不阻塞为什么拿不全。

  1. 想要不阻塞:等到某个时限,必须自己拿主意。

  2. 时限到了,节点分不清对方是倒了还是连不上。

  3. 如果对方只是连不上,它可能也在拿主意,结论可能相反。

  4. 想要安全:只能继续等,直到能问到对方。这就是阻塞。

时限到了 好处 风险
自己拿主意 不阻塞 对方只是连不上时,两边结论可能相反
继续等 不会和对方相反 对方一直不回,就一直卡住

怎么判断

协议 分区或崩溃时的选择 得到 失去
2PC 等 安全(不会一半提交一半中止) 可能阻塞
3PC 不等,按本侧状态决定 不阻塞 分区下可能不一致

意思是:再给 3PC 打补丁也绕不开这个取舍。后面的共识协议会换一套假设和目标。

常见误解

以为 FLP 说的是「共识永远做不到」

它说的是在异步网络、可能有进程崩溃时,没有确定性算法能保证总能结束。换假设(比如加上时限、允许随机)就有办法。

以为 3PC 比 2PC 更好,所以现实里都用 3PC

3PC 多一轮往返,又怕分区。它换来的不阻塞在分区面前不成立。

试一下

一个系统宁可让事务卡住,也绝不能出现一半提交一半中止。它该选 2PC 还是 3PC?

选 2PC。它在不确定时会等,不会做出相反的决定。

4. 同一笔转账,三种做法

它解决什么问题

这一讲从银行转账开始。最后把同一笔转账放在三种做法下对照一遍,就能一眼看出每种做法卡在哪里。

直觉

没有协议,消息一丢钱就少了。2PC 多问一轮,钱不会丢,但协调者在两轮之间倒下时,参与者只能干等。3PC 再多一轮,不再干等,但网络分区时两边各判各的。

每多一轮消息,就多一份「别人知道什么」的信息,代价是多一次往返。

一步一步看

目标:把同一笔转账依次放进无协议、2PC、3PC,看每种做法卡在哪里。

  1. 没有协议:Bank A 扣款,再通知 Bank B。通知丢了,钱就少了。

  2. 2PC:协调者先问两行能否提交,两行检查后答 Yes 或 No。全 Yes 发 Commit,任一 No 发 Abort。

  3. 2PC 的问题:协调者在 prepare 之后、commit/abort 之前崩溃,两行可能一直等。

  4. 3PC:CanCommit 问能否提交;全体 Yes 后发 PreCommit,参与者确认就绪;最后发 Commit。

  5. 3PC 的变化:协调者崩溃时,参与者可以按规则互相沟通,决定 commit 或 abort,阻塞减少。

    同一笔转账三种做法:没有协议时扣款后通知,消息一丢钱就少了;2PC 有 CanCommit? 和 commit 两轮,协调者在两轮之间倒下时参与者干等;3PC 有 CanCommit?、PreCommit、DoCommit 三轮,不再干等,但网络分区时两边各判各的

怎么判断

做法 消息轮数 会丢钱吗 会干等吗 分区下会不一致吗
没有协议 1 会 不会 会
2PC 2 不会 会 不会
3PC 3 不会 减少(无分区时) 会

意思是:2PC 和 3PC 都是为了让分布式事务有原子、一致的结局,只是在「等」和「不等」之间选了不同的一边。

常见误解

以为 3PC 完全不会干等

它降低了阻塞,前提是无分区、超时可靠。这些前提不成立时,它的保证也不成立。

以为没有协议只是慢一点

没有协议时,一方扣了款、另一方没加上,钱就丢了,全局不一致。

试一下

用一句话分别说出 2PC 和 3PC 在转账例子里的问题。

2PC:协调者在 prepare 之后、commit/abort 之前崩溃,两行可能一直等。3PC:网络分区时,两边可能一边 commit、一边 abort。

把它们串起来

3PC 的恢复规则靠一个前提:大家能互相问到。分区打破了它,节点又分不清分区和崩溃,看到的都只是超时。

两边各选恢复协调者,各自按本侧状态走分支。一边有人 Prepared 就提交,另一边无人收到 PreCommit 就中止,网络愈合后结局相反。

这个取舍绕不开。异步网络里要么等(安全但可能阻塞),要么不等(不阻塞但可能不一致)。2PC 选了前者,3PC 选了后者。

回到转账:没有协议会丢钱,2PC 会堵,3PC 怕分区。下一讲换一套假设,看共识协议怎么推进。

课件里的坑

  • [口径提醒] p.2、p.13 的「节点总能通信」是强假设;p.34 分区场景专门打它的脸,答 3PC 优点时必须同时写分区弱点(p.2、p.13、p.34)。
  • [读图提醒] p.34 图注写的是 Partition A Received Prepare – commit can proceed,Partition B No nodes received Prepare – must abort,答题时两边的条件都要写(p.34)。
  • [答题边界] p.43 说 3PC「降低阻塞」,没说「消灭阻塞」,答题别写成绝对(p.43)。
  • [对照复习] p.41 复读了 p.9 的银行动机,p.42、p.43 用同一个转账分别写 2PC 和 3PC,适合整段默写(p.9、p.41–43)。

课后 10 分钟

这 10 分钟怎么用:合上页面,画一遍分区四步图:断网、各选恢复协调者、各自决定、愈合后对不上。再默写三种做法的对照表,最后做变式题。

必背

  1. 3PC 弱点:网络分区可使一边 commit、一边 abort,愈合后全局不一致。
  2. 3PC 用超时换非阻塞,牺牲了分区下的安全性;它隐含依赖一定的网络可靠性。
  3. 2PC 保证原子但可能永远等;3PC 降低阻塞但怕分区;没有协议会丢钱。
  4. 2PC 的问题在 prepare 之后、commit/abort 之前协调者崩溃;3PC 协调者崩溃时参与者可按规则协商。
  5. 答 3PC 优点时必须同时写分区弱点:节点总能通信是强假设。

课件例题

例 1(课件 p.34):3PC 的弱点

画图说明 3PC 为何在网络分区下可能不一致。

提示

两边各自看到什么状态?各走哪条恢复分支?

解答

Partition A 有节点收到了 Prepare,新恢复协调者允许 commit。Partition B 没人收到 Prepare,新恢复协调者必须 abort。两个决定在各自分区内都合法,网络愈合后全局不一致。

例 2(课件 p.43):3PC 版的转账

用 3PC 写一遍跨行转账,说明它和 2PC 版的区别。

提示

对比 2PC 版的问题出在哪一段。

解答

CanCommit 问能否提交;全体 Yes 后发「准备提交」,参与者确认就绪;最后发 Commit。协调者崩溃时,参与者可以按协议规则互相沟通决定 commit 或 abort,阻塞减少。2PC 版在 prepare 之后、commit/abort 之前协调者崩溃时,银行可能一直等。

完整例题

题目(改编自课件 p.34、p.42–43):Bank A、Bank B 用 3PC 转账。协调者发出 PreCommit 后崩溃,PreCommit 只送到了 Bank A。同时网络断开,两行互相连不上,各自超时后各自恢复。最终会怎样?如果换成 2PC,同样是协调者崩溃加断网,会怎样?

解:

第一步,列状态。Bank A 收到 PreCommit,处于 Prepared。Bank B 没收到,处于 Waiting。没人收到 DoCommit,没人提交过。

第二步,Bank A 一侧恢复。它只能看到自己,看到 Prepared,走分支 ②,commit。

第三步,Bank B 一侧恢复。它只能看到自己,看到没收到 PreCommit,走分支 ③,abort。

第四步,网络愈合。Bank A 提交,Bank B 中止,原子性被破坏。

第五步,换成 2PC。两行投了 yes 后协调者崩溃,两行都在 prepared,不知道结局,只能握锁等。断网时谁也不会擅自决定,所以不会不一致,但会阻塞,直到协调者恢复。

一句话结论:同一场故障,3PC 给出相反的结局,2PC 给出漫长的等待。

变式题

1. 四个参与者 P1–P4 用 3PC。协调者崩溃,同时网络断成 {P1} 和 {P2, P3, P4} 两块。PreCommit 只送到了 P2。两边恢复后结局是什么?

提示

分别列出两边能看到的状态,再对照分支 ② 和分支 ③。

判分点与答案

判分点:①P1 一侧只看到自己没收到 PreCommit,走分支 ③ abort;②另一侧看到 P2 Prepared,走分支 ② commit;③愈合后不一致。

答案:P1 abort,P2、P3、P4 commit。网络愈合后同一笔事务一边提交、一边中止。

2. 同样是分区,如果 PreCommit 已经送到了全部四个参与者,两边恢复后会不一致吗?如果四个人都没收到呢?

提示

不一致需要两边看到不同的状态。

判分点与答案

判分点:①全都收到 → 两边都走分支 ②,都 commit,一致;②全都没收到 → 两边都走分支 ③,都 abort,一致;③只有一边有人 Prepared、另一边无人收到时才不一致。

答案:两种情况都一致。分区本身不一定出错,出错的是两边看到的状态不同的时候。

闪卡自测

1. 画分区图说明 3PC 为何在网络分区下可能不一致。

Partition A 有人收到 Prepare → commit;Partition B 没人收到 → abort;愈合后不一致(p.34)。

2. True or False: 3PC eliminates all blocking and is safe under network partitions.
中文:3PC 消灭一切阻塞且在分区下仍安全。

False. 3PC reduces blocking under timeout assumptions but can decide inconsistently across partitions. 分区两边可分别 commit / abort(p.34)。

3. 2PC 版转账的问题是什么?

协调者在 prepare 之后、commit/abort 之前崩溃,银行可能一直等(p.42)。

4. 3PC 版转账相比 2PC 版改善了什么?

协调者崩溃时,参与者可以按规则互相沟通决定 commit 或 abort,阻塞减少(p.43)。

5. 课件 p.2 说 2PC 和 3PC「隐含依赖一定的网络可靠性」,在哪一页兑现?

p.26(2PC 阻塞)和 p.34(3PC 分区不一致)(p.2、p.26、p.34)。

6. 银行转账一句话总结三种做法。

没有协议会丢钱;2PC 保证原子但可能永远等;3PC 降低阻塞但怕分区(p.9、p.41–43)。

下一讲

下一讲进入 L07a 两将军与拜占庭将军:信道会丢消息,节点还可能撒谎,故障模型比只会崩溃的节点更难。带着问题听:3PC 用超时换非阻塞却怕分区,共识协议换了哪些假设来推进?

下一讲 →
Lab1 Lab 1 把 2PC 跑起来:一个协调者、三个参与者、四个终端

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