2025 期末真题解析(二)|Q19–Q20:3PC 与 VR 时序图
非官方参考解答:2025 年期末卷 Part C 的 Q19 三阶段提交成功执行与协调者崩溃后的恢复、Q20 VR 在副本崩溃和恢复下的执行,题面中文转述,自绘时序图配逐步说明和讲义页码。
手机上宽表格可左右滑动;自测答案默认收起,点击题目下方按钮查看。
非官方参考解答,不是讲师给的标准答案;今年的考试安排与范围以讲师通知为准。 先自己画一遍,再展开对照。
范围与作答约定
本页收 2025 年期末卷 Part C 的两道画图题,题目按卷面原题中文转述。前三题见真题解析(一),后三题见真题解析(三)。
画时序图时每个节点一条竖线,一条消息一根箭头,箭头上写消息名。解析里的图是按讲义的消息命名自绘的参考画法,不是课件原图;考场上箭头不必画得这么全,但每一轮发给谁、收齐几个才往下走、崩溃发生在哪两条消息之间,这三样要画清楚。
题目与解析
Q19 · 3PC sequence diagrams
系统里有一个 Client、一个协调者 P0 和四个参与者 P1–P4,运行标准的三阶段提交(3PC:CanCommit、PreCommit、DoCommit)。
(1) 画出一次完整成功执行的时序图,从 Client 发请求开始,到所有节点提交为止。
(2) 协调者 P0 把 PreCommit 发给 P1、P2、P3 之后、发给 P4 之前崩溃。画出恢复过程:P1 成为新的协调者,把事务推进到最终状态,并回复 Client。
Q19 · 查看答案与解析
参考解答,非官方答案。
(1) 三轮,每轮 P0 发给四个参与者、再收齐四个回复,前后加上 Client 的请求和结果,共 26 条消息。
| 步 | 消息 | 之后的状态 |
|---|---|---|
| 1 | Client → P0:request | |
| 2 | P0 → P1–P4:CanCommit? | |
| 3 | P1–P4 → P0:Yes | 参与者 Waiting |
| 4 | P0 → P1–P4:PreCommit | 参与者 Prepared |
| 5 | P1–P4 → P0:ACK | |
| 6 | P0 → P1–P4:DoCommit | 参与者提交 |
| 7 | P1–P4 → P0:ack | |
| 8 | P0 → Client:reply(committed) |
(2) 先写清崩溃那一刻每个人在哪:P1、P2、P3 收到了 PreCommit,是 Prepared;P4 投过 Yes 但没收到 PreCommit,是 Waiting;没有人提交,因为 DoCommit 要等 P0 收齐 ACK 才发。
| 步 | 动作 |
|---|---|
| 1 | P1–P4 等 P0 超时,P1 当恢复协调者 |
| 2 | P1 自己已是 Prepared,说明全体都投过 Yes,按 L06 p.33 的情形 ② 推向提交(可先问一圈:P2、P3 报 Prepared,P4 报 Waiting,结论不变) |
| 3 | P1 → P2、P3、P4:PreCommit(补发,P4 由此进入 Prepared) |
| 4 | P2、P3、P4 → P1:ACK |
| 5 | P1 → P2、P3、P4:DoCommit,P1 自己提交 |
| 6 | P2、P3、P4 → P1:ack |
| 7 | P1 → Client:reply(committed) |
为什么能提交:只要有人到了 Prepared,说明 P0 已经收齐全票 Yes,没人投过 No,提交不会违反任何人的否决。反过来,如果恢复协调者手里只有 Waiting 状态(例如只剩 P4 能联系上),就落到情形 ③,中止或重启。本题指定 P1 当协调者,P1 自己就是 Prepared,所以走提交。
这一问默认 P0 不再回来插手、网络没有分区;分区时 3PC 会出问题,见 L06 p.34。
Q20 · VR sequence diagrams
系统里有一个 Client、主节点(primary)P0 和四个副本 P1–P4,运行 Viewstamped Replication(VR)。除题目特别说明的以外,所有节点都正常。
(1) P3 在协议开始前就崩溃,收不到任何消息。画出一次完整成功执行的时序图。
(2) 接着 (1):P3 恢复。紧接着 Client 发出一个新请求,P0 开始新一轮 Prepare;P1 和 P4 收到新的 Prepare 之后、回复之前崩溃。画出恢复过程和之后的执行。
Q20 · 查看答案与解析
参考解答,非官方答案。 先定参数:5 个节点是 2f+1,所以 f 为 2;一次请求要有 f+1,也就是 3 个节点(含主节点)记下这条操作才能提交,即主节点加至少 2 个 PrepareOK(L08 p.7、p.14)。
(1)
| 步 | 消息 |
|---|---|
| 1 | Client → P0:Request |
| 2 | P0 给请求排号、写入日志,向 P1–P4 发 Prepare(发给 P3 的那条没人收) |
| 3 | P1、P2、P4 → P0:PrepareOK |
| 4 | P0 收到 2 个 PrepareOK,加自己共 3 个,提交并执行 |
| 5 | P0 → Client:Reply |
| 6 | P0 在下一条 Prepare 或心跳里带上已提交的编号,副本据此执行 |
(2)
| 步 | 消息 |
|---|---|
| 1 | P3 恢复,向其他节点发 recovery request(讲义里的 dorecoveryrequest) |
| 2 | 其他节点回 recovery response;主节点的回复带着日志和已提交编号 |
| 3 | P3 收到包括主节点在内的 f+1 个回复,同步日志,回到正常状态 |
| 4 | Client → P0:新的 Request |
| 5 | P0 → P1–P4:Prepare(新的编号) |
| 6 | P1、P4 收到后崩溃,不回复 |
| 7 | P2、P3 → P0:PrepareOK |
| 8 | P0 加 P2、P3 共 3 个,提交、执行,回复 Client |
关键在顺序:P3 必须先完成恢复才能回 PrepareOK,恢复中的副本不参与投票。若 P3 没恢复,P0 只能拿到 P2 一个 PrepareOK,加自己 2 个,凑不够 3 个,请求卡住,直到有节点恢复。这时崩溃的是 P1、P4 两个,正好用完 f 为 2 的预算,系统还能推进,再坏一个就停。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。