← COMP5567 全部讲次
Q05

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)

Q19 第一问参考时序图:Client、P0、P1 到 P4 六条竖线,Client 先发 request 给 P0,P0 依次向 P1 到 P4 发 CanCommit?、收四个 Yes,发 PreCommit、收四个 ACK,发 DoCommit、收四个 ack,最后回复 Client

(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)

Q19 第二问参考时序图:P0 发完 CanCommit?、收齐四个 Yes、向 P1 到 P3 发出 PreCommit 后崩溃,P1 超时后当恢复协调者,向 P2 到 P4 补发 PreCommit、收 ACK、发 DoCommit、收 ack,最后回复 Client

为什么能提交:只要有人到了 Prepared,说明 P0 已经收齐全票 Yes,没人投过 No,提交不会违反任何人的否决。反过来,如果恢复协调者手里只有 Waiting 状态(例如只剩 P4 能联系上),就落到情形 ③,中止或重启。本题指定 P1 当协调者,P1 自己就是 Prepared,所以走提交。

这一问默认 P0 不再回来插手、网络没有分区;分区时 3PC 会出问题,见 L06 p.34。

回讲义:L06b 3PC 与恢复、Lab2 3PC 程序

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 或心跳里带上已提交的编号,副本据此执行

Q20 第一问参考时序图:P3 一开始就崩溃,Client 向 P0 发 Request,P0 向四个副本发 Prepare,发往 P3 的那条打叉,P1、P2、P4 回 PrepareOK,P0 凑够 3 个后提交并回复 Client

(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

Q20 第二问参考时序图:P3 先向其他四个节点发恢复请求并收到回复,回到正常状态,之后 Client 发新请求,P0 发 Prepare,P1、P4 收到后崩溃,P2、P3 回 PrepareOK,P0 凑够 3 个后提交并回复 Client

关键在顺序:P3 必须先完成恢复才能回 PrepareOK,恢复中的副本不参与投票。若 P3 没恢复,P0 只能拿到 P2 一个 PrepareOK,加自己 2 个,凑不够 3 个,请求卡住,直到有节点恢复。这时崩溃的是 P1、P4 两个,正好用完 f 为 2 的预算,系统还能推进,再坏一个就停。

回讲义:L08a VR 正常操作、L08a-2 VR 换届与恢复

下一页 →
Q06 2025 期末真题解析(三)|Q21–Q23:OM 与 SM、PBFT 计票、PoW 与 PoS

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