Lab 3 把 VR 跑起来:五个节点的提交、换届和恢复
按课件步骤在本地跑通课程仓库 5567-VR:六个演示 case、两个练习,外加三个课件没有的变式。逐条标出程序和 L08 理论不一致的地方:备份能投 no、新主节点按视图号轮转、恢复只用第一个回应。
一句话版
这次 Lab 用课程仓库 5567-VR 把 L08 的视图戳复制(VR)跑起来,考试按 L08 答,程序的行为当反例记。
先认识这几个词
读之前最好先懂 VR 的三个子协议:正常操作见 L08a,换届和恢复见 L08a-2,环境搭法见 Lab2。
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| VR | Viewstamped Replication,视图戳复制 | 让几台机器按同样顺序执行同一串操作 |
| 主节点 / 备份 | Primary / Backup | 排序并发号的那台 / 跟着执行的其余几台 |
| 视图 | view | 一段「由某台机器当主节点」的任期,换主节点就换视图 |
| 操作编号 | op number,课件记作 n | 主节点给每个请求排的全局序号 |
| 换届 | view change | 主节点挂了,大家选新主节点进入新视图 |
| 恢复 | replica recovery | 崩溃的机器回来,向别人要日志补课 |
| f+1 | 多数 | 2f+1 台机器里过半的那个数,5 台就是 3 |
和 3PC 那次相比,这次有两点不同。一是节点变成 5 个,阈值从「全体同意」变成「多数同意」。二是主节点能换人,换完之后崩溃的机器还能回来。
题目地图
| 任务 | 在考什么 | 主要失分点 |
|---|---|---|
| VR 回顾 | 三个子协议各自的步骤 | 把备份的回复写成 Yes/No 投票 |
| 代码准备 | 下载、解压、打开仓库 | 没在同一个目录启动五个节点 |
| 程序结构图 | 「3 Yes」里包不包括发起者 | 以为要 3 个备份同意 |
| 启动系统 | 端口和投票命令末尾的编号 | 照抄仓库 README 里写错的 backup 4 启动命令 |
| Case 1–3 | 多数提交、多数反对中止 | 以为投了 no 的备份不执行 |
| Case 4–5 | 换届和新视图下的操作 | 以为发起者一定当选 |
| Case 6 与练习 | 恢复和备份崩溃 | 以为恢复后的 node0 当回主节点 |
最后一页是关闭程序,五个节点都敲 quit,日志文件会被清空。
概念卡
1. 多数为什么是 3
人话定义:VR 要容忍 f 台机器崩溃,所以准备 2f+1 台。剩下的 f+1 台要构成多数,任意两次决定的参与者才一定有交集。5 台机器时 f = 2,多数是 3。
例子:Case 1 里 node2、node4 投 yes,主节点自己算一票,正好 3 票,提交。
常见误解
以为「3 Yes」指 3 个备份同意 → 发起者自己就算一票,主节点只要再拿 2 个备份就够。
回讲义:L08a VR 正常操作:2f+1 台机器,主节点排号,过半确认
2. 备份的回复
人话定义:按 L08,备份收到主节点的 prepare,只回一个 prepareok 表示「记下了」。它不表态同不同意,因为所有副本存的是同一份数据。
例子:程序让备份投 yes 或 no。实测投了 no 的 node1、node3 收到 COMMIT 后照样执行,余额和别人一样。
常见误解
以为 VR 和 3PC 一样要收集同意票 → 3PC 管的是「几个不同的服务要么一起做要么都不做」。VR 管的是「同一份数据的几个副本按同样顺序执行」。
回讲义:L08a VR 正常操作:2f+1 台机器,主节点排号,过半确认
3. 换届
人话定义:主节点崩溃后,副本们各自把日志发给新主节点(doviewchange)。新主节点收齐多数后宣布新视图(startview),再接着处理请求。
例子:Case 4 中 node1 收到 node2、node4 的 yes,加上自己共 3 票,视图从 0 变 1,node1 成为主节点。
常见误解
以为谁发起换届谁就当选 → 程序按「新视图号除以 5 的余数」轮转。实测让 node2 发起,当选的仍是 node1。
回讲义:L08a-2 VR 换届与恢复:主节点没了,从过半的日志里拼回账本
4. 恢复
人话定义:崩溃的机器回来后,先向其他机器要日志,收到多数回应再同步。同步完成后它是普通备份,主节点仍是换届后的那台。
例子:Case 6 中 node0 装回日志后余额为 alice 30、bob 100,is_primary=False。bob 那笔是它崩溃期间发生的。
常见误解
以为问一台机器就够 → 那台可能本身落后。程序实测只用第一个到达的回应,L08 要等多数。
回讲义:L08a-2 VR 换届与恢复:主节点没了,从过半的日志里拼回账本
逐题拆解
准备与启动。 仓库只有 vr_node.py 一个程序,只用 Python 标准库,节点之间走 UDP(一种不保证送达、不建连接的网络传输方式)。五个终端在同一个目录下各启动一个节点:
python vr_node.py --id 0 --port 6000 --peer_ports 6000,6001,6002,6003,6004
python vr_node.py --id 1 --port 6001 --peer_ports 6000,6001,6002,6003,6004
python vr_node.py --id 2 --port 6002 --peer_ports 6000,6001,6002,6003,6004
python vr_node.py --id 3 --port 6003 --peer_ports 6000,6001,6002,6003,6004
python vr_node.py --id 4 --port 6004 --peer_ports 6000,6001,6002,6003,6004
仓库 README 把 backup 4 写成 --id 1,照上面的写法改成 4。提示符里 P 是主节点、B 是备份。投票命令 cancommit vote yes 1 末尾的数字是操作编号,从 1 起连续递增。
Case 1:存 50。 主节点 client alice deposit 50,node1 no、node2 yes、node3 no、node4 yes。收到 node4 的 yes 时凑够 3 票,主节点广播 COMMIT。所有节点余额都是 50,包括投了 no 的两台。
Case 2:取 20。 投票同上,操作编号 2,余额 50 − 20 = 30。
Case 3:取 50。 四个备份全投 no。第 3 张 no 到达时已凑不够 3 个 yes,主节点广播 ABORT。第 4 张 no 到达后又广播一次,备份各打印两次 ABORT op 3 recorded。余额仍是 30。
这笔被中止是因为四个人手动投了 no,程序本身不查余额。另外两个变式(课件没有):
- 在空账户上取 80 并投够 yes,余额变成 −80。
- 1 个 yes、2 个 no、1 人不投,yes 和 no 都不过线,操作一直挂着,程序没有超时。
Case 4:换届。 主节点 crash,node1 start-view-change,提示新视图 1、候选主节点 node1。node2、node4 回 yes,node1 打印 collected_yes=2、collected_yes=3,然后广播 START-VIEW。node3 回的 no 被静默丢弃,没有任何输出,也不会触发中止。node1 按日志重放已提交的操作,status 显示 view=1 | primary=1。
Case 5:新主节点下存 100。 node1 client bob deposit 100,分到的操作编号是 4,接着前面排。node2、node4 yes,node3 no,提交后余额 alice 30、bob 100。
Case 6:node0 恢复。 node0 recover 后向其他四台要日志。第一个到达的是 node1 的回应,它照此重放 op 1、2、4,余额 alice 30、bob 100。后面三个回应只打印收到,不再处理。status 显示它现在是备份,主节点是 node1。
练习 1:备份 node0 再崩溃。 node1 client bob withdraw 20,编号 5,三票通过,bob 余额 80。只崩一台备份,正常操作照常进行。
练习 2:node0 再恢复。 这次第一个到达的是 node2 的回应,重放后 commit_index=5,余额 alice 30、bob 80。两次恢复用的来源不同,谁先到用谁。
变式:换个人发起换届(课件没有)。 另起一组节点,主节点崩溃后让 node2 发起,node3、node4 先投 no。node1 什么都没收到,系统停在视图 0。node2 再发起一次,node3、node4 改投 yes,当选的是 node1,node2 仍是备份。
课件里的坑
- [课件有误] 练习 2 的标题是 Case 2,正文写成 “Case 1: Backup node 0 recovers”(p.27)。
- [术语区别] 回顾页说备份回 Yes 或 No,那是程序;L08 里备份只回 prepareok(p.3)。
- [与程序不符] 回顾页说发起换届的备份「选自己」,程序按新视图号除以 5 的余数选,实测 node2 发起时 node1 当选(p.3)。
- [与程序不符] 换届的「否则中止」在程序里不存在,no 票被静默丢弃(p.3、p.23)。
- [与程序不符] 恢复页写收到 f+1 个回应再同步,程序收到第一个就完成,其余丢弃(p.3、p.25)。
- [课件留白] p.4 指向 L08 第 7 到 16 页,VR 部分实际到 p.20,其中 p.19 的多数交集和 p.20 的 VR 与 3PC 对照最该一起看(p.4)。
- [补充] 仓库 README 和 case_command 把 backup 4 的启动参数写成
--id 1,课件这页写对了(p.17)。 - [补充] 读代码可知,换届时程序取最长的一份日志;L08 按 k(多数副本都已完成的最新编号)确定已提交的操作。本次演示各节点日志一样长,看不出差别(p.23)。
课后 10 分钟:考点复习
这 10 分钟怎么用:先默写三个子协议的消息名和方向,再默写 2f+1 和 f+1 的关系;然后做完整例题,每一行先写「按 L08 应该怎样」,再对照程序实际怎样;最后过一遍闪卡。
必背
- VR 用 2f+1 个副本容忍 f 个崩溃,提交、换届、恢复都要 f+1 个回应,包括发起者自己
- 按 L08,正常操作的消息是 REQUEST → PREPARE → PREPAREOK → REPLY,备份只回 prepareok,不投 No
- 换届的两步是各副本发 doviewchange 给新主节点、新主节点收齐 f+1 个后发 startview
- 崩溃节点恢复后发 recovery request,收到 f+1 个响应、同步日志后成为普通副本,不当回主节点
- 只崩一个备份不需要换届,只有主节点崩溃才触发 view change
- 操作编号跨视图连续,新主节点接着已提交的最大编号往后排
- VR 解决副本一致与操作排序,3PC 解决原子提交,两者不能互换
完整例题
5 个节点的 VR,node0 为主节点。依次发生下面四件事,写出每一步按 L08 的结果和程序的结果。
| 步骤 | 事件 | 按 L08 | 程序实测 |
|---|---|---|---|
| ① | 存 50,2 个备份回应 | 主节点加 2 个 prepareok 共 3 个,提交 | 2 个 yes 加主节点,提交;投 no 的也执行 |
| ② | node0 崩溃,node1 发起换届,2 人响应 | node1 收齐 3 个 doviewchange,发 startview,视图变 1 | 3 票通过,视图 1,node1 为主节点 |
| ③ | 新主节点处理存 100 | 编号接着排为 2 | 编号为 2(本例前面只有一笔) |
| ④ | node0 恢复 | 等 3 个响应,同步后当备份 | 用第一个回应,同步后当备份 |
逐步说明:
- 第 ① 步两种说法结果相同,区别在备份能不能说「不」。L08 里不能,程序里能说但不起作用。
- 第 ② 步要数清 3 票里有 node1 自己。程序的当选者由新视图号决定,这里 1 % 5 = 1,和发起者恰好重合。
- 第 ③ 步的编号不从 1 重来,日志顺序跨视图连续。
- 第 ④ 步结局一样,可靠性不同。L08 等多数,一定能看到所有已提交的操作;程序若第一个回应来自落后的节点,就会漏掉操作。这一情形没有实测。
变式题
(1) 同样 5 个节点,主节点和 node1 同时崩溃,剩下的三台还能完成换届吗?(2) 如果主节点、node1、node2 三台同时崩溃呢?
提示
先算 f。5 台机器 f = 2,再看剩下的机器够不够 f+1 = 3。
参考答案与自检(非官方评分标准)
自检要点:① 能写出 f = 2、f+1 = 3;② 能说出崩 3 台时为什么不能继续;③ 知道第 (1) 问在程序里会卡在轮转上。
(1) 按 L08 可以。剩 3 台正好是 f+1,新主节点加两个 doviewchange 共 3 个,够。程序里做不到:新视图号是 1,候选主节点按轮转是已崩溃的 node1。实测让 node2 发起两次,两次的候选都是 node1,票全发给了它,三台一直停在视图 0。
(2) 不能。崩了 3 台超过 f = 2,剩下 2 台凑不够 3 个,系统停止服务,不能冒险用少数派做决定。
闪卡自测
5 个节点的 VR,主节点要几个备份同意?
2 个。f+1 = 3,主节点自己算一个。
按 L08,备份对 prepare 回什么?
prepareok,带上视图号、操作编号和自己的编号,不表态同不同意。
程序里投了 no 的备份会执行提交吗?
会。它收到 COMMIT 就执行,实测余额和其他节点一致。
程序换届时谁当选新主节点?
新视图号除以 5 的余数对应的节点,与谁发起无关。
恢复后的节点是什么角色?
普通备份。主节点仍是换届后的那台。
为什么恢复要等多数响应?
只问一台可能问到落后的副本;问到多数,必有一台见过所有已提交的操作。
下一步
先照练习 1 和练习 2 自己跑一遍,每一步先在纸上写预期的操作编号和余额,再看屏幕。然后回看 L08a-2 的换届和恢复两页,把 Case 4、Case 6 分别对上 doviewchange / startview 和 recovery 的两条消息。课件没演示的丢包情形(fail 0.3)还没有实测,适合留作自己的练习,跑之前先写下 L08 的预期。
下一次 Lab 换成拜占庭容错:Lab 4:PBFT 程序实测。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。