← COMP5567 全部讲次
Lab4 · 第 10 周

Lab 4 把 PBFT 跑起来:四个节点数票、拜占庭分票、换视图和检查点

按课件步骤在本地跑通课程仓库 5567-PBFT:七个演示 case、两个练习,外加两个课件没测的情形。标出程序计票的固定加 1、拜占庭节点分票后各节点数出不同的票、恢复节点停在旧视图、检查点少一台就卡住,以及课件里写错的命令。

一句话版

这次 Lab 用课程仓库 5567-PBFT 把 L09 的实用拜占庭容错跑起来。考试按 L09 答,程序里和理论对不上的地方当反例记。

先认识这几个词

读之前最好先懂正常操作的三道门槛,见 L09b;环境搭法和 2PC、3PC 那两次一样,见 Lab2。

词 全称 / 读法 一句人话
PBFT Practical Byzantine Fault Tolerance,实用拜占庭容错 有人撒谎也能让诚实的机器达成一致
主节点 / 副本 primary / replica 发起提案的那台 / 跟着投票的其余几台
拜占庭节点 Byzantine node 会乱发消息、对不同人说不同话的那台,程序里固定是 P3
2f+1 门槛 3f+1 台里要凑够的票数,4 台就是 3
视图 view 一段「由某台机器当主节点」的任期
检查点 checkpoint 大家把当前状态记一份存档,旧日志就能扔

和 VR 那次相比,这次多了一个会撒谎的节点 P3。它能单独给某一台发票,所以四台机器数出来的票可能各不一样。

题目地图

任务 在考什么 主要失分点
流程回顾 五个阶段和 2f+1 门槛 把门槛写成过半数,7 台时就差出来
启动系统 5 个终端、端口、拜占庭节点是谁 Mac 上 5000 端口被占,P0 起不来
Case 1–2 门槛刚好够和有余量 以为 P3 投了 no 就一定中止
Case 3–4 分票和两道门槛 以为 Prepare 过了就一定提交
Case 5 崩溃一台照样提交 照抄课件命令,结果交易中止
Case 6 换视图轮一圈 以为恢复的节点自动跟上新视图
Case 7 与练习 检查点和两次分票练习 不会预先算每台数到几票

最后一页是关闭程序,所有节点敲 quit。

概念卡

1. 门槛为什么是 3

人话定义:PBFT 要扛住 f 台撒谎的机器,需要 3f+1 台。每一步凑够 2f+1 票才往下走。这样任意两次决定至少重叠一台诚实机器。4 台机器时 f = 1,门槛 3。

例子:Case 2 里 P3 对 P1、P2 投 no,P0、P1、P2 三台都投 yes,正好 3 票,交易照样提交。

常见误解

以为过半数就够 → 过半数是 VR 那种只防崩溃的协议用的规则。4 台时两者碰巧都是 3。换成 7 台(f = 2):过半数是 4,2f+1 是 5,差别才显出来。

回讲义:L09b PBFT 正常操作:五个阶段、三道门槛,凑不满票就停

2. 程序怎么数票

人话定义:每台机器敲 progress 时自己数 yes。主节点数的是收到的 yes 加自己 1 票。副本数的是收到的 yes、自己那票,再固定加 1 票,代表「主节点肯定同意」。

例子:Case 3 里 P2 只收到 no,自己也投 no,数出来仍是 1,这 1 就是那张固定票。

常见误解

以为四台数出的数一样 → 每台只数自己收到的票。P3 分票时,四台看到的票就不一样。

回讲义:L09b PBFT 正常操作:五个阶段、三道门槛,凑不满票就停

3. 两道门槛

人话定义:Prepare 阶段大家确认「这个提案的序号和内容没有分歧」。Commit 阶段再确认「足够多的人已经确认过」。两道都过了才执行。

例子:Case 4 里 Prepare 全是 yes,进了 Commit。P1、P2 却回 abort,commit 票只有 2 张,交易中止。

常见误解

以为 Commit 是走过场 → L09 里正是 Commit 保证换视图后已执行的操作不会丢。

回讲义:L09c PBFT 视图切换:主节点靠不住就换人,Commit 保证换届不丢账

4. 换视图和恢复

人话定义:主节点崩溃后,副本们发 VIEW-CHANGE 投给下一任。下一任收齐 3 票就广播 NEW-VIEW,开始当主节点。崩溃的机器回来后应该先补状态,再当普通副本。

例子:Case 6 里 P0 崩溃,P1 收到 P2、P3 两票,加上自己正好 3 票,成为 view 1 的主节点。

常见误解

以为恢复的节点会自动同步视图 → 程序实测 P0 恢复后仍停在 view 0,P3 恢复后还以为自己是主节点。

回讲义:L09c PBFT 视图切换:主节点靠不住就换人,Commit 保证换届不丢账

逐题拆解

准备与启动

仓库有三个程序:主节点 primary_node.py、副本 pbft_node.py、客户端 pbft_client.py,只用 Python 标准库。节点之间走 TCP。在项目目录下开 5 个终端,依次启动下面 5 个程序,P3 启动时就被选为拜占庭节点:

python3 primary_node.py           # P0,主节点
python3 pbft_node.py P1 5001
python3 pbft_node.py P2 5002
python3 pbft_node.py P3 5003      # 拜占庭节点
python3 pbft_client.py 7000       # 客户端

全部连上后,在 P0 的窗口里敲 list、status 查看节点。

Mac 上 5000 端口被「隔空播放接收器」占着,P0 起不来。三个文件都把 5000 写死了,有两种办法。一是在系统设置里关掉隔空播放接收器。二是先在项目目录里把三处改成 5050,再按上面的顺序启动:

sed -i '' 's/5000/5050/' primary_node.py pbft_node.py pbft_client.py

这是 macOS 的写法;Linux 上写成 sed -i 's/5000/5050/' primary_node.py pbft_node.py pbft_client.py。本页的输出都是改成 5050 后跑的。

终端截图:P0 打印 started at localhost:5050,依次登记 P1、P2、P3 三台副本,选定 P3 为拜占庭节点,客户端从 7000 端口连上 5050
图片来源:本站在本地运行课程仓库 5567-PBFT 的终端输出(端口改为 5050)

下面按课件顺序在同一组进程上连续跑,中途不重启,alice 初始为 0。

每个 case 的操作都一样:客户端敲 send account=alice,amount=…,operation=…,P0 只打印收到,不会自动发起。P0 要敲 tx,再把同一串数据输一遍。副本投票用 prepare yes|no、ack commit|abort,这两条都是广播。P3 多两条单发命令 prepare to P0 yes、ack to P1 abort。投完票后四台各敲一次 progress 数票。

Case 1:存 100,全 yes

P0、P1、P2 数到 4,P3 数到 3。P3 用单发命令投的票不算「自己那票」,所以少 1。两道门槛都过,提交,alice 100。

终端截图:P0 收到客户端请求,敲 tx 发出三条 PRE-PREPARE,收到三张 VOTE_YES,progress 数到 4/4 进入 COMMIT,收到三张 ACK_COMMIT 后再数到 4/4,广播 REPLY,status 显示 alice 100
图片来源:本站在本地运行课程仓库 5567-PBFT 的终端输出(端口改为 5050)

Case 2:取 20,P3 对 P0 说 yes,对 P1、P2 说 no

Prepare 时 P0 数到 4,其余三台数到 3。Commit 阶段 P3 也是对 P0 说 commit,对 P1、P2 说 abort,计数相同。3 刚好够门槛,提交,alice 80。

Case 3:取 100,P1、P2 投 no,P3 分票

一步一步看

目标:看拜占庭节点分票之后,四台机器各自数出几票、为什么都中止。

  1. P0 敲 tx,向三台副本各发一条 PRE-PREPARE。

    Case 3 第 1 步时序图:P0 向 P1、P2、P3 各发一条 PRE-PREPARE,三条消息青绿标出

  2. P1、P2 敲 prepare no,票广播给其余三台。

    Case 3 第 2 步时序图:P1 和 P2 各向其余三台广播 no,六条消息青绿标出

  3. P3 逐台单发:给 P0、P1 的是 yes,给 P2 的是 no。

    Case 3 第 3 步时序图:P3 给 P0 和 P1 各发 yes、给 P2 发 no,三条消息青绿标出

  4. 四台各敲 progress。P0 是 P3 的 yes 加自己,2 票。P1 是 P3 的 yes 加固定 1 票,2 票。P2、P3 只有固定那 1 票。都不到 3,四台中止,alice 仍是 80。

    Case 3 第 4 步时序图:四台各自数票,P0 和 P1 是 2/4,P2 和 P3 是 1/4,全部中止,四个计数框青绿标出

四个终端的截图拼在一起:P0 收到 P1、P2 的 VOTE_NO 和 P3 的 VOTE_YES,数到 2/4 中止;P1 也是 2/4;P2 收到的三张都是 VOTE_NO,数到 1/4;P3 逐台单发后数到 1/4;四台都打印 Prepare not satisfied
图片来源:本站在本地运行课程仓库 5567-PBFT 的终端输出(端口改为 5050)

Case 4:取 100,Prepare 全 yes,Commit 阶段 P1、P2 反悔

一步一步看

目标:看 Prepare 门槛过了之后,Commit 票不够时交易怎样中止。

  1. P0 发 PRE-PREPARE,P1、P2 广播 yes,P3 对三台都说 yes。

    Case 4 第 1 步时序图:P0 发三条 PRE-PREPARE,P1、P2 广播 yes,P3 逐台发 yes,这一组消息青绿标出

  2. 第一次 progress:P0、P1、P2 数到 4,P3 数到 3,都过门槛,进入 Commit。

    Case 4 第 2 步时序图:四台第一次数票,P0、P1、P2 是 4/4,P3 是 3/4,都通过,四个计数框青绿标出

  3. P1、P2 敲 ack abort 广播,P3 对三台单发 commit。

    Case 4 第 3 步时序图:P1 和 P2 广播 abort,P3 向三台各发 commit,九条消息青绿标出

  4. 第二次 progress:P0 是 P3 的 commit 加自己,2 票。P1、P2 是 P3 的 commit 加固定 1 票,也是 2 票。P3 只有固定那 1 票。全部中止,alice 仍是 80。

    Case 4 第 4 步时序图:四台第二次数票,P0、P1、P2 是 2/4,P3 是 1/4,全部中止,四个计数框青绿标出

Case 5:P3 崩溃,存 100,P3 再恢复

照课件的命令跑会中止,原因见下文「课件里的坑」。把 commit 那两行改成 P1、P2 敲 ack commit 后,P0、P1、P2 都数到 3,提交,alice 180。P3 敲 recover 后从 P0 拿到全部交易,status 里的余额和 P0 一致。

Case 6:主节点轮流崩溃,P0、P1、P2、P3 各当一次

一步一步看

目标:看第一轮换视图怎样凑够 3 票,以及恢复的 P0 为什么跟不上新视图。

  1. P0 敲 crash,之后不处理收到的消息。下一任按编号轮到 P1。

    Case 6 第 1 步时序图:P0 崩溃,崩溃标记青绿,此后 P0 的生命线变成虚线

  2. P1、P2、P3 各敲 view change 广播。发给 P0 的票它不收。

    Case 6 第 2 步时序图:P1、P2、P3 各广播一条 VIEW-CHANGE,发给 P0 的三条标为不收,九条消息青绿标出

  3. P1 收到 P2、P3 两票,加上自己共 3 票,进入 view 1 当主节点,广播 NEW-VIEW。

    Case 6 第 3 步时序图:P1 记录 3 票当选 view 1 主节点,向其余三台广播 NEW-VIEW,这一组青绿标出

  4. P0 敲 recover,只打印 recovered,没有去同步视图。它下一轮敲 view change 时打印的还是 current view=0。

    Case 6 第 4 步时序图:P0 恢复,恢复记录青绿标出,底部状态栏 P0 仍是 view 0,其余三台是 view 1

后三轮照此轮下去,P2、P3、P0 依次当主。第三轮有个细节:P3 收到 P0、P1 两票,加上自己就够 3 票,它还没敲 view change 就当选了。到最后 P0、P1、P2 都是 view 4、主节点 P0。P3 恢复时去问它记得的主节点,也就是它自己,结果没有同步,仍以为自己是 view 3 的主节点。

终端截图:上半是 P0 的 status,View 4,主节点 P0,四台成员中 P0 是 Leader;下半是 P3 恢复后的 status,View 3,Current leader 是 P3,成员列表里 P3 标为 Leader
图片来源:本站在本地运行课程仓库 5567-PBFT 的终端输出(端口改为 5050)

练习 1:取 50,P1、P2 投 no,P3 只对 P2 说 yes

P0、P1 数到 1,P2 数到 2,全部中止。P3 也数到 2,原因是它还以为自己是主节点:自己恒算 1 票,再加固定 1 票。如果在全新启动的程序上跑,P3 这里应是 1,这一点未实测。

Case 7:检查点

P0 敲 checkpoint,等 P1、P2、P3 依次上报,收齐 4 份后写出 checkpoints/final_checkpoint_<日期_时间>.log,每台另有一份自己的快照文件。P3 上报的快照写着 view 3,和其余三台不同,程序照收,不报错。

练习 2:取 20,P1、P2 yes,P3 只对 P1 说 yes,Commit 全员同意

在全新启动的程序上跑,P0、P2、P3 的 Prepare 数到 3,P1 数到 4,都过门槛。Commit 阶段 P0、P1、P2 数到 4,P3 数到 3,提交。账户原来是 0,取完变成 −20:程序取款不检查余额。接在 Case 7 后面跑时,P3 两次都数到 4,原因同练习 1,alice 从 180 变成 160。

课件外加测

两个课件没演示的情形都实测过:

  • 有节点崩溃时做检查点:P2 崩溃后 P0 敲 checkpoint,收到 3 份就停住,不写文件,也没有超时。P2 恢复后再敲一次,收齐 4 份才写出。
  • 换视图后由副本当主节点:全新启动后让 P1 接任,P1 发起一笔 bob 存 10。P1 自己数出 5/4,比节点总数还多。那张固定票本该代表 P0,P1 当主后又把自己算了 1 票,于是多出一张。
终端截图:P1 凑够 3 票广播 NEW_VIEW 成为 view 1 主节点,之后发起的交易里 Prepare 和 Commit 都打印 5/4,交易照样提交
图片来源:本站在本地运行课程仓库 5567-PBFT 的终端输出(端口改为 5050)

未实测的有三项:客户端等 f+1 个相同回复(程序的客户端把回复全打印出来,不做这个判断)、网络分区、P3 以外的节点当拜占庭节点(程序固定选 P3)。

课件里的坑

  • [课件有误] Case 1 标题写 P3「yes to P0, yes to P2, yes to P3」,列表页和下面的命令都是 P0、P1、P2(p.21)。
  • [课件有误] Case 5 客户端那行漏了 send,照抄会被客户端忽略(p.25)。
  • [课件有误] Case 5 的 commit 写成「P2 ack commit、P3 ack commit」。P3 正处于崩溃,它的 ack 带的是上一笔交易号,新交易不认。实测 P0、P1、P2 都只数到 2,交易中止。改成 P1、P2 才能提交(p.25)。
  • [课件有误] 练习 1 页标题是「Practice-Case 1」,正文写 Case 2;练习 2 正文也写 Case 2(p.27、p.29)。
  • [课件有误] Case 7 的文件名带着一次运行的时间戳,每次都不同,反斜杠是 Windows 写法;这页小节编号写「1.」,却排在第 2 部分两个练习中间(p.28)。
  • [术语区别] 回顾页的图把副本叫 Replica 1/2/3,文字写 Replica II、III、IV,是同一组节点(p.3)。
  • [与程序不符] 回顾页说检查点每 1000 次共识做一次、2f+1 个赞成即可。程序要主节点手动敲 checkpoint,等全部 4 台上报,不比对内容(p.5、p.28)。
  • [课件留白] 回顾页没讲恢复节点怎样跟上视图。实测 P0、P3 恢复后都停在旧视图(p.4、p.26)。
  • [补充] 理论部分课件指回 Lecture 9 p.3–18,对应本站 L09a 到 L09d(p.6)。
  • [补充] 仓库 README 写 pip install socket json threading,这三个是标准库,不用装(p.7)。
  • [补充] README 的 Case 4 多一行 P0 ack commit,课件没有。主节点自己恒算 1 票,这行不影响结果(p.24)。

课后 10 分钟:考点复习

这 10 分钟怎么用:先默写五个阶段和两道 2f+1 门槛,再做完整例题,每一格先按程序规则算出票数,再说按 L09 应该怎样;最后过一遍闪卡。

必背

  1. PBFT 用 3f+1 台机器容忍 f 台拜占庭节点,Prepare、Commit 各要 2f+1 票;4 台时 f = 1,门槛 3
  2. 正常操作五步:Request → Pre-prepare → Prepare → Commit → Reply,只有 Pre-prepare 由主节点单独群发
  3. 拜占庭节点可以对不同节点说不同的话,各节点数到的票数因此可能不同
  4. 过了 Prepare 门槛只是进入 Commit,Commit 票凑不够照样中止
  5. 主节点崩溃后副本发 VIEW-CHANGE,新主节点按编号轮到下一台,收齐 2f+1 票后发 NEW-VIEW
  6. 检查点要 2f+1 个序号和摘要都相同的 CHECKPOINT 才稳定,之后可丢旧日志、给掉队节点补状态

完整例题

全新启动的程序,P0 是主节点。练习 2 的 Prepare 阶段:P1、P2 广播 yes,P3 对 P0 说 no、对 P1 说 yes、对 P2 说 no。算出每台 progress 时数到几票。

节点 收到的 yes 自己那票 固定 1 票 合计 过门槛 3?
P0 P1、P2 = 2 1(主节点恒算) 无 3 过
P1 P2、P3 = 2 1 1 4 过
P2 P1 = 1 1 1 3 过
P3 P1、P2 = 2 0(单发不算) 1 3 过

逐步说明:

  1. 先分清每台收到了谁的票。P3 单发的票只到指定的那台,所以 P1 多收一张 yes。
  2. 再加自己。主节点恒算 1;副本广播过 prepare yes 才算 1;P3 用单发命令,不算。
  3. 副本再加固定 1 票。这张票代表主节点,主节点自己不加。
  4. 四台都不低于 3,进入 Commit。实测四台的数正是 3、4、3、3。
  5. 按 L09,副本要收到主节点的 pre-prepare 加 2f 个匹配的 prepare 才算 prepared。程序把这件事简化成数 yes。

变式题

(1) 全新启动的程序,P1、P2 投 yes,P3 对三台都说 no,四台各数到几?交易能进 Commit 吗?(2) 换视图后 P1 当主节点,P0、P2 广播 yes,P3 对三台都说 yes,P1 自己数到几?这说明程序哪里有问题?

提示

按完整例题那张表的四列逐台算。第 (2) 问注意固定 1 票代表的是谁。

参考答案与自检(非官方评分标准)

自检要点:① 能按收到的票、自己那票、固定票三项算;② 知道主节点不加固定票;③ 能说出 5/4 来自重复计算。

(1) P0:P1、P2 两票加自己,3。P1:P2 一票加自己加固定,3。P2 同理是 3。P3:P1、P2 两票加固定,3。四台都过,进 Commit。P3 的 no 只少了它自己那一票,诚实的三台已经够 3 票,这正是 f = 1 能扛住一个撒谎者的意思。第 (1) 问未实测,按程序规则推出。

(2) P1 收到 P0、P2、P3 三票,加自己 1,再加固定 1,共 5,实测打印 5/4。固定票本来代表主节点 P0,P1 当主后自己已经算了 1,再加就重复了,P0 真投的那张也被算了进来。门槛只看是否不低于 3,所以这次结果没错;但票数已经不能反映真实情况。

闪卡自测

4 个节点的 PBFT,最多能扛几个拜占庭节点?门槛是几?

f = 1,门槛 2f+1 = 3。

副本一张 yes 都没收到、自己也投 no,为什么还数出 1?

代码固定加 1 票,代表主节点同意(pbft_node.py 第 160 行的 yes + self_yes + 1)。

拜占庭节点分票有什么效果?

不同节点收到的票不同,数出来的结果也不同,Case 3 里四台是 2、2、1、1。

Prepare 过了门槛,交易一定提交吗?

不一定。Commit 还要再凑够 3 票,Case 4 只有 2 票,中止。

换视图后新主节点是谁?

当前主节点编号的下一台,P0 之后是 P1,P3 之后回到 P0。

程序的检查点少一台上报会怎样?

一直停在 3/4,不写文件,也没有超时。

下一步

先照练习 1 和练习 2 自己跑一遍,每一步先在纸上按完整例题的四列算出每台的票数,再看屏幕。然后回看 L09c 的视图切换,对照 Case 6 里 P0、P3 恢复后停在旧视图的现象,想想 L09 的 NEW-VIEW 和检查点各补上了程序缺的哪一环;检查点的稳定条件见 L09d。

下一讲 →
L10a L10a HotStuff:票交给 leader 攒成一张证书,三轮投票走完一个区块

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