← COMP5567 全部讲次
L09c · 第 9 周

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

副本等请求超时就怀疑主节点,按 p = v mod n 轮到下一任;新主节点收齐 2f+1 份 VIEW-CHANGE 后发 NEW-VIEW(v+1, V, O),把已 prepared 的操作原样带进来。去掉 Commit、prepared 就执行,换届后会出 safety violation。

一句话版

主节点不干活,副本们等到超时就按轮值表换下一任。新主节点要先收齐 2f+1 份「交接材料」,把已经定下的操作原样接过来。正常操作里多走的那一轮 Commit,就是为了让这份交接材料里一定有那笔账。

先认识这几个词

读之前最好先懂上一页的五个阶段、prepared 和 2f+1 投票交集。

词 全称 / 读法 一句人话
视图 view,编号 v 某一任主节点在任的这段时期,换一次主节点视图号加 1
视图切换 view change 怀疑主节点坏了,大家一起换到下一任
VIEW-CHANGE 读「视图切换消息」 副本交给下一任的交接材料:要进的视图号、检查点、手上的 prepared 证书
NEW-VIEW 读「新视图消息」 新主节点收齐材料后的就职通告,格式 NEW-VIEW(v+1, V, O)
prepared 证书 课件记作 P pre-prepare 加上凑满的匹配 prepare,证明「这个序号上就是这个操作」
计时器 timer 副本收到请求就开始计时,等太久还没执行就怀疑主节点

一个类比:值班经理撂挑子

四家分行轮流当值班经理,轮值表早就排好:一分行、二分行、三分行、四分行,再回到一分行。

这周一分行当班,可它接了 Alice 的单子迟迟不办。其他分行各自掐着表,等太久了,就判定它不干活了。

按轮值表,下一任是二分行。各家把自己的账本情况写成一份交接材料交给二分行:哪几笔已经核对完、写进了预备栏。二分行收齐三份(含自己的),发通告:「我接任了,以下这几笔照旧办。」

还有一个细节决定成败。要是某家分行已经把一笔账正式入账,交接材料里必须能找到这笔账;否则新经理可能在同一个编号上记另一笔,两家账本就对不上了。正常操作里那第二轮电话,就是在保证这一点。

类比在哪里失效:

  • 真实的分行可以打电话问「你是不是病了」;副本分不清主节点是宕机还是故意不干,也不需要分清,超时就换。
  • 交接材料在协议里是带签名的消息,新主节点没法伪造别人的材料。

从零讲起

1. 轮转选主:p = v mod n

它解决什么问题

主节点要换的时候,下一任是谁?如果要现场投票选,选举本身又可能被叛徒搅乱。PBFT 干脆提前定死:按视图号轮流当。

从哪来(补充)

原论文把副本从 0 开始编号,视图 v 的主节点是 p = v mod |R|,|R| 是副本总数。论文提到 VR 和 Paxos 在只有崩溃故障的场景里用过类似办法。轮流当还有一个好处:坏的主节点不可能连续霸占超过 f 个视图。

出处:Castro & Liskov 1999, Practical Byzantine Fault Tolerance

直觉

像值日表。每个人都知道今天轮到谁,明天轮到谁,不用开会商量。

叛徒最多 f 个,轮着轮着总会轮到一个老实人当主节点,系统就能继续往前走。

一步一步看

目标:用 p = v mod n 排出四个副本的轮值顺序,看主节点怎样一圈圈轮转。

  1. 四个副本编号:R1 = 0、R2 = 1、R3 = 2、R4 = 3。

    轮转选主:上排 view 0 到 view 4,下排对应主节点 R1、R2、R3、R4,view 4 因为 4 mod 4 = 0 又回到 R1,这一格用青绿标出表示转满一圈

  2. 按 p = v mod 4 逐个算:

    视图 v v mod 4 主节点
    0 0 R1
    1 1 R2
    2 2 R3
    3 3 R4
    4 0 R1
  3. 课件图里 view 0 的 Branch-I 失效,view 1 由 Branch-II 接任,和表里第二行对上。

  4. 第 5 个视图(v = 4)又轮回 R1,转满一圈。

怎么算

p = v mod n

  • v:视图号,从 0 开始
  • n:副本总数
  • mod:取余数,v 除以 n 剩下的那个数

意思是:视图号除以副本数,余几就轮到几号副本。换一次主节点,视图号加 1,主节点就往后挪一位。

常见误解

误解:第一个视图是 view 1

课件变量表里写过「v = 1:第一个当选的主节点」,可是视图切换那几页的第一个视图是 view 0。按公式 p = v mod n,view 0 对应 0 号副本,第一个视图就该是 view 0。

误解:主节点坏了,新视图号就是坏主节点的编号加 1

新视图号是旧视图号加 1,跟编号无关。算主节点时用新视图号取模。

试一下

n = 7,当前 view 8 的主节点失效。新视图的主节点是几号?

新视图 v = 9,9 mod 7 = 2,2 号副本。

2. 视图切换三步:超时、交材料、就职

它解决什么问题

主节点不响应或者乱来,正常操作就卡住了。视图切换要把大家安全地带到下一任主节点手里,还要保证已经定下的操作不丢。

从哪来(补充)

原论文里视图切换由计时器触发:backup 收到请求就启动计时器,在视图 v 里计时器到期还没执行,就开始切到 v+1。论文说得很直接:视图切换是为了提供活性,让系统在主节点出故障时还能往前走。

出处:Castro & Liskov 1999, Practical Byzantine Fault Tolerance

直觉

换届不能一个人说了算,否则叛徒随便一喊就能把好好的主节点换掉。所以新主节点要收齐 2f+1 份交接材料,证明大多数人都同意换。

交接材料里带着各自手上的 prepared 证书。新主节点看到哪个序号已经有证书,就必须在新视图里把同一个操作放回那个序号。

一步一步看

目标:跟着 R1 不响应的例子,看超时、交材料、就职三步怎样把系统交到 R2 手里。

f = 1,四个副本,view 0 的主节点 R1 不响应。

  1. 超时:R2、R3、R4 收到请求后各自开始计时,等太久 R1 都没推进,计时器先后到期。

    视图切换第 1 步:R1 那条线上打叉表示 view 0 主节点不响应,R2、R3、R4 线上各有一个青绿的计时器到期标签

  2. 交材料:下一任是 1 mod 4 = 1 号,也就是 R2。R2、R3、R4 各发一份 VIEW-CHANGE 给 R2,里面带要进的视图号 1、最近的稳定检查点、自己手上的 prepared 证书。

    视图切换第 2 步:两支青绿箭头从 R3、R4 指向 R2,旁边标 R2 + R3 + R4 = 3,表示下一任 R2 连同自己共收到 3 份 VIEW-CHANGE

  3. 就职:R2 收齐 3 份(自己、R3、R4),3 = 2f+1,构造 NEW-VIEW(v = 1, V, O) 发给所有副本。

    视图切换第 3 步:前一步的箭头转灰,三支青绿箭头从 R2 指向 R1、R3、R4,表示 R2 群发 NEW-VIEW(v = 1, V, O)

  4. 副本接受新视图,处理 O 里的请求:X 已经 prepared 的会被带进来;没 prepared 的,客户端必须重发。协议恢复。

怎么判断

新主节点什么时候可以发 NEW-VIEW:收到的有效 VIEW-CHANGE 达到 2f+1 份(含自己的)。

NEW-VIEW(v+1, V, O) 里三样东西各管一件事:

  • v+1:新视图号
  • V:收齐的 2f+1 份 VIEW-CHANGE,证明换届是大多数同意的
  • O:新视图要接着处理的 pre-prepare,V 里有 prepared 证书的序号,必须原样放回同一个操作

意思是:新主节点能决定的只有「没人有证书的序号放什么」,有证书的序号它改不了。

常见误解

误解:一个副本超时就能发起换届

一个副本超时只能发出自己那份 VIEW-CHANGE。新主节点要凑够 2f+1 份才能就职,叛徒一个人喊换届没用。

误解:没 prepared 的请求,新主节点会替客户端补上

没 prepared 的请求不在任何人的证书里,新主节点不知道它存在。客户端等不到回复,要自己重发。

试一下

f = 2、7 个副本,新主节点手上已经有 4 份 VIEW-CHANGE(含自己)。能发 NEW-VIEW 吗?

不能。2f + 1 = 5,还差 1 份。

3. 为什么还要 Commit:一个反例

它解决什么问题

上一页说 prepared 已经保证了同一视图里同一序号只有一个值。那为什么不 prepared 就执行,还要多走一轮 Commit?课件用一个反例回答:跳过 Commit,换届之后两个诚实副本会在同一序号上执行不同的操作。

直觉

prepared 只是某一个副本自己心里有数。要是只有它一个人 prepared,换届时它的交接材料又恰好没送到,新主节点就看不到这笔账。

Commit 轮让副本确认「足够多的人都 prepared 了」。人数够多,换届时收上来的材料里就必定有人带着证书。

一步一步看

目标:看跳过 Commit 时,换届后两个诚实副本怎样在同一序号执行不同操作。

四个副本 A、B、C、D,f = 1,法定人数 3,A 是拜占庭主节点。假设把规则改成「prepared 就执行,跳过 commit」。

  1. A 在 view 0 发 PRE-PREPARE(view = 0, seq = 10, x),backup 们开始广播 Prepare。

    反例第 1 步:四个方框 A、B、C、D,A 是青绿虚线框标注主节点作恶,B、C、D 的序号 10 还是问号,底部写着这一帧用的是 prepared 就执行的错误规则

  2. A 把足够的匹配 Prepare 送到 C,故意延迟送给 B、D。只有 C 拿到 x 的完整 prepared 证书。

    反例第 2 步:C 用青绿标成 prepared x,B 和 D 写着没 prepared,A 是灰色虚线,说明只有 C 拿到完整证书

  3. 按修改后的规则,C 不等 commit,直接在序号 10 执行 x。B、D 对此毫不知情。

    反例第 3 步:C 用青绿标成执行 x,B 和 D 仍是没 prepared,表示错误规则下 C 抢先执行

  4. A 停止推进,开始换届。新主节点 B 收到 A、B、D 的 VIEW-CHANGE,C 的被延迟。B、D 手上没有完整证书,A 隐瞒信息,所以这 3 份材料里没有 x。

    反例第 4 步:B 用青绿标成新主节点,A 和 D 写着交 VIEW-CHANGE,C 画成灰色虚线写着消息被延迟

  5. 没有证书要求保留 x,新视图把另一个操作 y 分到序号 10,B、D 执行 y。C 在序号 10 是 x,B、D 是 y,诚实副本之间出现分歧,这就是 safety violation。

    反例第 5 步:B、C、D 三个方框都用青绿标出,B 和 D 执行 y,C 执行 x,下方青绿字写同一个序号 10 上 C 是 x、B 和 D 是 y,safety violation

  6. 换回真实规则:要 3 个匹配 COMMIT 才执行。假设 C 真凑齐了 3 个,发 COMMIT 的人和交 VIEW-CHANGE 的人必然碰上。

    加上 commit 后:四个方框下各写有没有发 COMMIT、有没有交 VIEW-CHANGE,发 COMMIT 的是 A、B、C,交 VIEW-CHANGE 的是 A、B、D,两组重叠 A、B,诚实的 B 用青绿标出

怎么算

真实规则下,C 要执行 x,得收到 3 个匹配 COMMIT:

  • 发 COMMIT 的副本:3 个,每个诚实的发送者都已 prepared x
  • 新主节点收的 VIEW-CHANGE:3 份
  • 两组在 4 个副本里至少重叠:3 + 3 − 4 = 2 个
  • 扣掉最多 1 个叛徒:2 − 1 = 1 个诚实副本

意思是:只要有人执行了 x,换届收上来的材料里一定有一个诚实副本带着 x 的证书,新主节点只能把 x 留在序号 10。

回到反例本身:B、D 没 prepared,不会发 COMMIT,C 最多拿到自己和 A 的 2 个,2 < 3,C 根本不会执行 x,也就不会和 B、D 分歧。

常见误解

误解:prepared 已经凑满 2f+1 票了,再多一轮纯属浪费

prepared 的 2f+1 票只保证同一视图里不分歧,是某一个副本自己看到的。Commit 的 2f+1 票保证足够多的副本都 prepared 了,这样换届时证书才藏不住。

误解:反例里出错是因为 A 作恶,换个老实主节点就不需要 Commit

主节点是不是叛徒,副本事先不知道。消息被延迟这种事老实网络也会发生。协议要在最坏情况下都不出错,所以 Commit 必须有。

试一下

f = 2、7 个副本。某副本凑满 5 个 COMMIT 执行了 x,新主节点收齐 5 份 VIEW-CHANGE。两组至少重叠几个?里面至少几个诚实?

至少重叠 5 + 5 − 7 = 3 个,扣掉 2 个叛徒,至少 1 个诚实,它带着 x 的证书。

把它们串起来

主节点坏了,副本靠计时器发现,按 p = v mod n 轮到下一任,不用投票选。

新主节点收齐 2f+1 份 VIEW-CHANGE 才能就职,叛徒一个人喊换届没用。NEW-VIEW 里的 V 证明换届合法,O 把有证书的序号原样带进新视图。

能带进来的前提是证书一定在材料里。prepared 只保证同一视图内不分歧;Commit 轮让足够多的副本都 prepared,换届时收上来的材料必定有人带着证书。

一句话:prepare 管「同一视图内同一序号只有一个值」,commit 管「这个值换视图后还在」。下一页讲第三个子协议:账本越记越长,什么时候能把旧账扔掉。

课件里的坑

  • [前后不一致] p.10 写「v = 1:第一个当选的主节点」,p.15–17 的第一个视图却是 view 0。按 p.15 的公式,第一个视图应是 view 0(p.10、p.15)。
  • [隐含条件] p.17 Exercise 1 说作恶的 R1 漏掉 R4,但 R2、R3 已提交。要凑满 3 个 COMMIT 必须有 R1 的一票,所以题目默认 R1 对 R2、R3 照常发了 COMMIT,只坑 R4(p.17)。
  • [简写] p.16、p.17 写 R4 在 NEW-VIEW 里看到 X 已提交就执行。原论文里 R4 要在新视图对这个序号再走一遍 prepare、commit 才执行(p.16、p.17)。
  • [编号] 课件有 Exercise 1、2、4,没有 Exercise 3;p.16 叫 Example 1,p.19 叫 Example 2(p.16、p.17、p.20、p.28)。

课后 10 分钟:考点复习

这 10 分钟怎么用:先合上页面,默写 p = v mod n 和 NEW-VIEW 的三个字段;再用 A、B、C、D 四个副本复述去掉 commit 会出什么事;然后照完整例题把 Exercise 1 的八步写一遍,最后做变式题。

必背

  1. 视图切换:新主节点 p = v mod n(第一个视图是 view 0,副本从 0 编号)
  2. 副本等请求超时就怀疑主节点,向下一任发 VIEW-CHANGE;新主节点收齐 2f+1 个后发 NEW-VIEW(v+1, V, O)
  3. NEW-VIEW 里 V 是收齐的 2f+1 个 VIEW-CHANGE,O 是新视图要处理的 pre-prepare 集合;已 prepared 的请求被带进新视图,没 prepared 的客户端要重发
  4. Commit 阶段让已执行的操作在视图切换后保留;跳过 commit、prepared 就执行会出 safety violation
  5. prepare 保证同一视图内同一序号只有一个值;commit 保证这个值换视图后还在
  6. 作恶主节点最多拖慢进度、逼出视图切换,没法让诚实副本提交不同结果

课件例题

例 1(课件 p.15):轮转选主

4 个副本 R1 到 R4,按 p = v mod n 轮转。view 0 到 view 4 的主节点分别是谁?

提示

副本编号从 0 起,R1 是 0 号。

解答

view 0 是 R1,view 1 是 R2,view 2 是 R3,view 3 是 R4,view 4 回到 R1。课件图里 view 0 的 Branch-I 失效,view 1 由 Branch-II 接任,正好对上。

例 2(课件 p.16,Example 1):主节点不响应

客户端把操作 X 发给主节点 R1,R1 不响应。写出视图切换的全过程。

提示

按「超时 → VIEW-CHANGE → 收齐几份 → NEW-VIEW 带什么 → X 的下场」的顺序写。

解答

R2、R3、R4 等到超时,各自向下一任主节点 R2 发 VIEW-CHANGE,内容包括本副本 prepared、committed 的请求、检查点,以及要进入的视图号 1。

R2 收齐 3 份(自己、R3、R4),3 = 2f+1,构造 NEW-VIEW 发给所有副本,内含新视图号 1、收集到的 VIEW-CHANGE 集合 V、本视图要处理的请求集合 O。

副本接受新视图。X 若已 prepared,就在 O 里被带进来;若没有 prepared,客户端必须重发。协议恢复。

例 3(课件 p.17,Exercise 1):作恶主节点只和一部分副本说话

见下方完整例题。

例 4(课件 p.21):去掉 commit 会怎样

4 个副本 A、B、C、D,f = 1,A 是拜占庭主节点。规则改成「prepared 就执行」。A 在 view 0 把 x 排在序号 10。说明这条修改后的规则怎样导致错误,再说明真实规则怎样避免。

提示

盯住新主节点 B 收到的 VIEW-CHANGE 里到底有没有 x 的 prepared 证书。

解答

A 只把足够的 PREPARE 送到 C,延迟送给 B、D。只有 C 拿到 x 的完整 prepared 证书,按修改后的规则在序号 10 执行 x。

A 随后停止推进。新主节点 B 收集 A、B、D 的 VIEW-CHANGE,C 的被延迟。A 隐瞒信息,B、D 投过 Prepare 票但没收齐证书,所以证据里没有 x。新视图把 y 分到序号 10,B、D 执行 y。C 执行 x、B 和 D 执行 y,这就是 safety violation。

真实规则要 3 个匹配 COMMIT 才执行。B、D 没 prepared,不会发 COMMIT,C 最多拿到自己和 A 的 2 个,不会执行 x,也就不会和 B、D 分歧。

例 5(课件 p.28,Exercise 4):作恶主节点在每个阶段能干什么

4 个节点,其中主节点作恶。分阶段写出它的作恶行为和协议的应对。

提示

逐个阶段问:诚实的 R2、R3、R4 三票够不够 2f+1?客户端的 f+1 够不够?

解答

以下是推导,不是课件原文。Request:主节点不理请求,客户端超时后广播请求,backup 启动计时器,到时发 VIEW-CHANGE,换到 view 1 由 R2 接任。Pre-prepare:同一序号给不同副本发不同操作,诚实副本对一个序号只 prepare 一个值,冲突的两个值至多一个凑满 3 票,凑不满的副本超时触发视图切换。Prepare、Commit:主节点不投或乱投,R2、R3、R4 三票已够 2f+1,照常执行。Reply:主节点回错结果,客户端等 2 个相同回复,错的被忽略。

结论:作恶主节点最多拖慢进度、逼出视图切换,没法让诚实副本提交不同结果。

完整例题

题目(课件 p.17,Exercise 1):f = 1,4 个副本。主节点 R1 作恶,在 view 0 只和 R2、R3 说话,漏掉 R4。R2、R3 已提交请求,R4 没有。按八步填空:Prepare 和 Commit 阶段各副本做什么;视图切换时 R2、R3、R4 的 VIEW-CHANGE 各带什么;NEW-VIEW 是什么。

解:

第 1、2 步。客户端把 X 发给 R1,R1 把 PRE-PREPARE(v=0, n=5, X) 只发给 R2、R3。

第 3 步,Prepare 和 Commit。R2、R3 各向所有副本(含 R4)多播 PREPARE(v=0, n=5, h(X))。R4 没收到 pre-prepare,不发 X 的 PREPARE,也进不了 prepared。R2 手上匹配票是 R1 的 pre-prepare 加 R2、R3,共 3 = 2f+1,进入 prepared,R3 同理。两者多播 COMMIT;要凑满 3 个,还需要 R1 的一票,所以题目默认 R1 对 R2、R3 照常发了 COMMIT。R2、R3 收齐 R1、R2、R3 三个 COMMIT,执行 X 并回复客户端。

第 4 步。R4 等 X 等到超时,R2、R3 也因 R1 不推进后续请求而超时,三者发起视图切换。只靠 R4 一个人凑不够 3 份。

第 5 步。新主节点 p = 1 mod 4 = 1,是 R2。R2 的 VIEW-CHANGE 带最近稳定检查点和序号 5 上 X 的 prepared 证书;R3 同样带 X 的证书;R4 只有最近稳定检查点,序号 5 没有 prepared 记录(P 为空)。

第 6 步。R2 收齐 R2、R3、R4 三份 VIEW-CHANGE,3 = 2f+1。

第 7 步。R2 发 NEW-VIEW(v=1, V, O)。V 是这 3 份 VIEW-CHANGE;O 里含 PRE-PREPARE(v=1, n=5, X)。V 里有两份 X 的 prepared 证书,新主节点必须把 X 留在序号 5,不能换成别的操作。

第 8 步。R2、R3 已执行过 X,不重复执行;R4 处理序号 5 上的 X,执行后追上进度。

一句话结论:作恶主节点能让 R4 暂时掉队,但 X 的 prepared 证书在 2f+1 份 VIEW-CHANGE 里藏不住,换届后序号 5 仍然是 X(p.17)。

变式题(先自己做)

1. 7 个副本跑 PBFT,编号 0 到 6。当前是 view 8,主节点失效。(a) 新视图的主节点是几号?(b) 它要收齐几份 VIEW-CHANGE 才能发 NEW-VIEW?(c) 若序号 40 上的操作 z 只有 1 个副本 prepared 过,而这个副本的 VIEW-CHANGE 没被收进 V,新视图会怎样处理序号 40?(改编自课件 p.15、p.16、p.21)

提示

先由 7 = 3f+1 求 f;新视图号是 8 + 1。(c) 想想只有 1 个人 prepared 时,真实规则下有没有人能执行 z。

判分点与答案(非官方评分标准)

7 = 3 × 2 + 1,f = 2。

(a) 新视图 v = 9,p = 9 mod 7 = 2,2 号副本。判分点:视图号加 1 再取模,没加 1 算成 8 mod 7 = 1 扣分。

(b) 2f+1 = 5 份,含新主节点自己。

(c) V 里没有 z 的证书,新主节点可以在序号 40 放别的操作,z 的客户端要重发。这不会出错:只有 1 个副本 prepared,没人能凑满 5 个 COMMIT,z 从没被任何诚实副本执行。判分点:说出「可以换」并用 commit 门槛解释为什么安全。

闪卡自测

1. 什么时候触发视图切换?

其他副本怀疑主节点出故障时,典型信号是等请求等到超时(p.15、p.16)。

2. 新主节点怎么定?

p = v mod n,按视图号轮转,第一个视图是 view 0(p.15)。

3. 4 个副本,view 1 的主节点是谁?

1 mod 4 = 1,编号 1 的副本,也就是 R2(p.15)。

4. VIEW-CHANGE 消息里带哪些东西?

新视图号 v+1、最近稳定检查点的序号 n、检查点 s 及其证书 C、本副本的 prepared 证书 P、副本 ID i(p.12)。

5. NEW-VIEW 里的 V 和 O 各是什么?

V 是收齐的 2f+1 个 VIEW-CHANGE;O 是新视图要处理的 pre-prepare 集合(p.11、p.16)。

6. 为什么不能 prepared 就执行?

换届时 prepared 证书可能没被收上来,新视图会把别的操作放到同一序号,出现 safety violation(p.21)。

7. 加上 commit 后,为什么证书一定能被收上来?

3 个 COMMIT 发送者和 3 份 VIEW-CHANGE 在 4 个副本里至少重叠 2 个,其中至少 1 个诚实且已 prepared(p.21)。

8. Exercise 1 里 R4 为什么能追上?

R2、R3 的 VIEW-CHANGE 带着序号 5 上 X 的证书,NEW-VIEW 把 X 留在序号 5,R4 处理后追上(p.17)。

下一讲

下一页是 L09d PBFT 检查点与经典协议对照:日志越记越长,什么时候能把旧消息扔掉;再把 BFT、PBFT、VR、Paxos 放进一张表比一比。

下一讲 →
L09d L09d PBFT 检查点与经典协议对照:旧账什么时候能扔,五个协议怎么分

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