L09d PBFT 检查点与经典协议对照:旧账什么时候能扔,五个协议怎么分
副本定期广播 CHECKPOINT,收到 2f+1 个序号和摘要都相同的消息,检查点就稳定,旧日志可以丢,掉队副本也从这里追上。最后把 BFT、PBFT、VR、Basic Paxos、Multi-Paxos 按故障模型和有没有 leader 放进一张表。
一句话版
PBFT 每处理一个请求就留下一堆消息,日子久了日志会撑爆。检查点让大家定期对一下账本指纹:2f+1 个副本对得上,这一刻之前的旧消息就能扔掉。讲完 PBFT,再把它和 BFT、VR、Paxos 放在一张表里,看各自防什么故障、要多少台机器。
先认识这几个词
读之前最好先懂第一页的摘要、3f+1,以及上一页的视图切换。
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 检查点 | checkpoint | 某个序号执行完之后,整份状态的快照 |
| 状态摘要 | digest of state | 对整份账本算出来的一串指纹,状态一样指纹就一样 |
| CHECKPOINT 消息 | 读「检查点消息」 | 副本广播的「我执行到第几号了,账本指纹是多少」 |
| 稳定检查点 | stable checkpoint | 收到 2f+1 个序号和摘要都相同的 CHECKPOINT 后,大家公认的那份快照 |
| 证书 C | certificate | 证明检查点稳定的那 2f+1 份签名消息 |
| 崩溃故障 | crash fault | 节点只会宕机不说话,不会撒谎 |
| 拜占庭故障 | Byzantine fault | 节点可能撒谎、发互相矛盾的消息 |
一个类比:月底对账
四家分行每天都在记流水,每笔都附着一大摞电话记录:谁报了价,谁同意了,谁确认了。这些记录是为了防扯皮,可总不能永远留着。
于是约好:每做完一批,各家把自己账本的总指纹报给其他分行。三家报上来的指纹一模一样,就说明到这一笔为止,大家的账是一致的。
这份对上的账就是定稿。定稿之前的电话记录可以销毁,留着定稿就够了。
哪天某家分行停电一周回来,不用从开业第一天重算。它向别家要这份定稿,再把定稿之后的流水补上,就追上了。
类比在哪里失效:
- 真实分行对账是人工核数字;副本比的是摘要,一个字节不同指纹就完全不同,没有「差不多」。
- 第四家报上来的指纹对不上,不需要查清它是作恶还是掉队,三家对上就够。
从零讲起
1. 检查点:凑满 2f+1 个相同指纹
它解决什么问题
每个请求都要经过 pre-prepare、prepare、commit,每个副本都存着成堆的签名消息。这些消息在视图切换时要当证据,所以不能随便删。
可是一直不删,存储会无限增长。检查点给出一个安全的删除时机:大家都确认过的那个状态之前的证据,以后再也用不上了。
从哪来(补充)
原论文里,副本在请求序号能被某个常数整除时(论文举例每 100 个请求)做一次检查点。证明检查点正确的 2f+1 份消息合起来,就让它变成稳定检查点;之后副本丢弃序号 ≤ n 的 pre-prepare、prepare、commit 消息,以及更早的检查点。
论文还给日志设了上下界:下水位 h 等于最近稳定检查点的序号,上水位 H = h + k,k 要足够大,论文举的例子是 200。主节点分配的序号必须落在这个窗口里。
出处:Castro & Liskov 1999, Practical Byzantine Fault Tolerance
直觉
一个副本自己说「我执行到第 20 号了」,可能是谎话。要 2f+1 个副本报上同一个指纹,其中至少 f+1 个诚实,它们都真的到了这个状态。
这和 prepare、commit 是同一个道理:门槛定在 2f+1,两次这样的多数一定有诚实的人重叠。
一步一步看
目标:看副本怎样凑满 2f+1 份相同的 CHECKPOINT,让序号 20 成为稳定检查点,之前的日志为什么就能丢。
课件 Example 2:f = 1,上一个检查点在序号 10,副本已执行到序号 20。
-
四个副本都执行完第 20 号请求,各自对执行后的状态算出摘要。
-
每个副本生成 CHECKPOINT 消息:序号 20、状态摘要、副本 ID,例如 CHECKPOINT(seq 20, digest abc123, R1),广播给其他所有副本。
-
每个副本收集来自不同副本、序号和摘要都相同的 CHECKPOINT。R1、R2、R3 摘要相同,凑够 3 个,序号 20 的检查点标为稳定。
-
稳定之后可以丢弃之前的日志,这是安全的垃圾回收。
-
之后崩溃恢复或分区后重新加入的副本,向别人要这个稳定检查点,从这里往后补日志。
课件还提到周期性做法:每 1000 次共识做一次,图里在 1000、2000、3000 三处各有一轮全员互发。
怎么算
检查点稳定的门槛 = 2f + 1 个序号和摘要都相同的 CHECKPOINT(含自己的)
- f:最多容忍的拜占庭副本数
- 相同:序号一样、摘要一样,缺一样都不算
意思是:在 3f+1 个副本里凑够 2f+1 个相同指纹,剩下最多 f 个对不上的,不管它们是叛徒还是掉队,都拦不住检查点稳定。
| 副本数 n | f | 稳定要几个匹配 |
|---|---|---|
| 4 | 1 | 3 |
| 7 | 2 | 5 |
常见误解
误解:一出事所有副本就回滚到检查点,之后的操作全作废
稳定检查点是恢复的起点。掉队的副本从这里取状态,再向别人补齐后面已提交的操作,那些操作照样有效。
误解:每个副本自己执行到第 20 号就能删日志
一个人说了不算。要等收到 2f+1 个匹配的 CHECKPOINT,检查点稳定了才能删。删早了,视图切换时可能缺证据。
试一下
f = 1、4 个副本。R1、R2 的摘要是 abc123,R3、R4 的摘要是 def456。序号 20 的检查点稳定了吗?
没有。两种摘要各 2 个,都不到 3 个。至少有一边出了问题,要等更多一致的消息。
2. 五个经典协议怎么分
它解决什么问题
这门课到这里已经见过 BFT(OM 算法)、VR、Paxos、PBFT。课件最后用一张表把它们放在一起,问的就是:遇到一个场景,该选哪个?
从哪来(补充)
Paxos 的论文 1989 年首次投稿,1998 年以 The Part-Time Parliament 为题发表在 ACM Transactions on Computer Systems。VR 是 Oki 和 Liskov 在 1988 年的 PODC 上提出的。Google 的 Chubby 锁服务用的是 Paxos。
出处:Wikipedia: Paxos (computer science)
直觉
先问一个问题:节点会不会撒谎?
会撒谎,就要防拜占庭故障,至少 3f+1 台。只会宕机,防崩溃故障就够,2f+1 台。
再问第二个问题:有没有固定的 leader?有 leader 的协议效率高,但要设计 leader 坏了怎么换。
一步一步看
目标:用「会不会撒谎」「有没有固定 leader」两个问题把五个协议分进四格,看各自适合什么场景。
-
按两个问题把五个协议摆进四个格子。
-
把课件的两张对照表合成一张:
协议 故障模型 所需节点 leader 管什么 课件用例 BFT(OM) 拜占庭 3f+1 没有固定 leader 一次共识,消息量 O(n^f) 可能有恶意节点的场景 PBFT 拜占庭 3f+1 有选主协议 操作序列,消息量 O(n²) 可能有恶意节点的场景 VR 崩溃 2f+1 每视图一个 primary 操作序列 云服务的复制数据库(TigerBeetle、Apache Iggy) Basic Paxos 崩溃 2f+1 没有,可多个 proposer 单个值 分布式锁服务(Google Chubby) Multi-Paxos 崩溃 2f+1 通常有稳定 leader 一串值 分布式文件系统元数据(GFS、HDFS) -
看拜占庭这一行。BFT 和 PBFT 都要 3f+1,区别在效率:OM 递归互传,消息量 O(n^f),叛徒越多越爆炸;PBFT 靠主节点排号,每阶段全员互发一次,O(n²)。
-
看崩溃这一行。VR 和 Multi-Paxos 都管一串操作、都有 leader;Basic Paxos 只管一个值。VR 的法定人数是 f+1(含 primary)。
-
最后把 PBFT 和 VR 对上:PBFT 沿用 VR 的「主节点排号 + 视图切换」骨架,把副本数从 2f+1 提到 3f+1,把法定人数从 f+1 提到 2f+1。
怎么判断
拿到一个场景,按顺序问:
- 节点会不会撒谎、发矛盾消息?会 → 拜占庭行,至少 3f+1 台;不会 → 崩溃行,2f+1 台
- 要对一个值还是一串操作达成一致?一个值(谁持有锁)→ Basic Paxos;一串操作(文件创建、删除)→ Multi-Paxos 或 VR
- 拜占庭场景里节点多不多?多就别用 OM,选 PBFT
意思是:故障模型定节点数,「一个值还是一串」定协议形态,节点规模定能不能承受消息量。
常见误解
误解:BFT 是一个具体协议的名字,和 PBFT 是两回事
BFT 本来是「拜占庭容错」这类性质的统称。课件对照表里的「BFT」指的是之前讲过的 OM 算法,O(n^f) 和那时的 O(nᵐ) 是同一个结论,m、f 都表示叛徒数。
误解:Paxos 能防坏节点,所以区块链可以直接用
Paxos 和 VR 只防崩溃,节点撒谎就会出错。课件的总结页写明:VR 和 Paxos 不适用于拜占庭场景,这正是部署到区块链的难点。
试一下
一个内部分布式锁服务,机器都在自己机房,只会宕机不会作恶,要容忍 2 台宕机。选哪个协议,要几台?
只防崩溃、管单个值(谁持有锁),选 Basic Paxos,2f+1 = 5 台。
把它们串起来
PBFT 的三个子协议到这里讲齐了:正常操作负责排序和执行,视图切换负责换掉坏主节点,检查点负责清理旧证据。
检查点的门槛和另外两个一样是 2f+1。它稳定之后有两个用处:丢掉旧日志控制存储;掉队的副本从这里取状态,再补齐之后的日志。
放回经典协议的谱系里看,PBFT 就是 VR 的骨架加上拜占庭级别的门槛。代价是更多的副本和 O(n²) 的消息量,换来的是在有人撒谎的场景下仍然安全。
课件里的坑
- [说得过满] p.18 写「一旦系统崩溃,所有节点回滚到这个检查点」,和 p.9「稳定检查点之前的操作已执行、结果不会回滚」放在一起容易误读。稳定检查点是恢复的起点,掉队副本从这里取状态再补齐后续日志,检查点之后已提交的操作不作废(p.18、p.19)。
- [与原论文差一格] p.19 写丢弃序号 20「之前」的日志。原论文丢弃的是序号 ≤ 20 的消息(含第 20 号本身),因为它的执行结果已经包含在检查点状态里。答题写课件口径,被追问写「≤ 20」(p.19)。
- [读图提醒] p.25 把 PBFT 的用例写成公链。原版 PBFT 要求副本集合固定、身份已知,更常见于许可链和联盟链。答题写「可能有恶意节点的区块链场景」更稳(p.25)。
- [名字混用] p.23 的「BFT」指 OM 算法;「leaderless」指没有固定 leader 和选主协议,OM 每次仍由一位指挥官发起(p.23)。
- [拼写] p.18 的「Lastest」应为 Latest(p.18)。
课后 10 分钟:考点复习
这 10 分钟怎么用:先合上页面,说出检查点稳定的门槛和两个作用;再凭记忆画出五个协议的四格图;然后照完整例题把 Example 2 的六步写一遍,最后做变式题。
必背
- 检查点:收到 2f+1 个序号和摘要都相同的 CHECKPOINT 后稳定
- 稳定检查点两个作用:丢弃旧日志降低存储;崩溃或掉队的副本从这里取状态再补齐后续日志
- BFT、PBFT 防拜占庭故障,要 3f+1 个节点;VR、Paxos、Multi-Paxos 只防崩溃,要 2f+1 个
- BFT(OM 算法)没有固定 leader,消息量 O(n^f);PBFT 有轮转 leader,消息量 O(n²)
- Basic Paxos 对单个值达成一致(如谁持有锁);Multi-Paxos 对一串操作达成一致(如文件系统元数据)
- VR 每个视图一个 primary,2f+1 个副本容忍 f 个崩溃,法定人数 f+1 含 primary
课件例题
例 1(课件 p.18):检查点子协议做什么
说出检查点子协议的两个目的,以及周期性检查点怎么做。
提示
一个和「状态」有关,一个和「存储」有关。
解答
一是记录由 2f+1 个节点认可的最近稳定全局状态;二是丢弃旧日志,降低存储成本。周期性做法例如每 1000 次共识做一次,图里在 1000、2000、3000 三处各有一轮全员互发,每次各需 2f+1 个匹配的 CHECKPOINT。消息格式是 ⟨CHECKPOINT, 100, d, i⟩,d 是执行到该序号后的状态摘要,i 是副本 ID。
例 2(课件 p.19,Example 2):序号 20 的检查点
见下方完整例题。
例 3(课件 p.23):BFT、PBFT、VR、Paxos 有什么区别
提示
从故障模型、节点数、有没有 leader、消息量四个角度比。
解答
BFT 没有固定 leader,防拜占庭故障,3f+1 个节点容忍 f 个,消息量 O(n^f)。PBFT 有设计好的 leader 选择协议,同样 3f+1,消息量 O(n²)。VR 每个视图一个主节点,2f+1 个副本容忍 f 个崩溃,法定人数 f+1 含主节点。Basic Paxos 无 leader、管单个值;Multi-Paxos 通常有稳定 leader、管一串值,都是 2f+1 个 acceptor 容忍 f 个崩溃。
例 4(课件 p.24–25):为什么区块链不能直接用 VR 和 Paxos
提示
看 p.25 表里的「故障模型」一列。
解答
VR、Paxos、Multi-Paxos 的故障模型都是 Crash,只防宕机。区块链里可能有恶意节点,要的是拜占庭容错,所以 p.24 说它们不适用于拜占庭场景,p.25 把 BFT、PBFT 列为可能有恶意节点时的选择,要 3f+1 个节点。
完整例题
题目(课件 p.19,Example 2):f = 1,4 个副本 R1 到 R4。上一个检查点在序号 10,副本已执行到序号 20。写出序号 20 的检查点从生成到稳定的完整步骤,并说明稳定后能做什么。
解:
第 1 步,到达检查点。每个副本执行完第 20 号请求。
第 2 步,生成消息。每个副本生成 CHECKPOINT:序号 20、执行完第 20 号请求后的状态摘要、副本 ID。例如 CHECKPOINT(seq=20, digest=abc123, replica=R1)。
第 3 步,广播。每个副本把 CHECKPOINT 发给其他所有副本。
第 4 步,收集。每个副本等收到 2f+1 = 3 个来自不同副本、序号和摘要都相同的 CHECKPOINT。设 R1、R2、R3 执行完第 20 号后摘要相同,都是 abc123。
第 5 步,标记稳定。收到 3 个匹配消息后,把序号 20 的检查点标为稳定。R1、R2、R3 可以丢弃第 20 号之前的日志,这是安全的垃圾回收。这 3 份消息就是证书 C。
第 6 步,恢复。崩溃后恢复、或分区后重新加入的副本,向其他副本要最新稳定检查点,从序号 20 往后补日志追上。
验算:f = 1 → 2f+1 = 3;四个副本里只要 3 个摘要一致就稳定,第 4 个可能是拜占庭副本或落后副本,不影响结果。
一句话结论:检查点和 prepare、commit 用同一个门槛 2f+1,稳定后旧日志可删,掉队副本从这里归队(p.19)。
变式题(先自己做)
1. 7 个副本跑 PBFT,系统每 1000 个请求做一次检查点。(a) 序号 3000 的检查点要几个匹配的 CHECKPOINT 才稳定?(b) 若 R5 在序号 2500 时宕机,序号 3000 的检查点稳定后它重启,怎样追上?(c) 有人提议「执行到 3000 就立刻删掉之前的日志,不用等别人」,错在哪?(改编自课件 p.18、p.19)
提示
7 = 3f+1 先求 f。(c) 想一想:自己的摘要可能是错的吗?视图切换时要不要这些旧消息?
判分点与答案(非官方评分标准)
7 = 3 × 2 + 1,f = 2。
(a) 2f+1 = 5 个序号和摘要都相同的 CHECKPOINT,含自己的。
(b) R5 向其他副本要序号 3000 的稳定检查点和证书 C(5 份匹配签名),验过后直接装载这份状态,再补 3000 之后已提交的操作。判分点:说出「从稳定检查点追上」,不需要重放 2500 到 3000 的每一笔。
(c) 一个副本自己的执行结果可能和别人不同(它可能是掉队或出错的那个),只有 5 个副本的摘要对上才能证明这个状态是公认的。检查点没稳定前删掉日志,视图切换时就拿不出 prepared 证书和检查点证据。判分点:指出「要等 2f+1 个匹配才稳定」并说出删早了的后果。
2. 一家公司要给内部分布式文件系统做元数据服务,机器都在自己机房,只会宕机。另一家联盟链有 7 个互不信任的机构做节点。各该选什么协议,最多容忍几个坏节点?(改编自课件 p.25)
提示
先判断故障模型,再看是一个值还是一串操作。
判分点与答案(非官方评分标准)
文件系统元数据是一串操作(创建、删除),只防崩溃,选 Multi-Paxos,课件用例正是 GFS、HDFS 的元数据服务;节点数按 2f+1 配。
联盟链节点可能作恶,要拜占庭容错,选 PBFT;7 个节点 f = ⌊(7 − 1)/3⌋ = 2,最多容忍 2 个作恶节点。判分点:两个故障模型各判对,节点数公式用对。
闪卡自测
1. 检查点子协议的两个作用?
记录 2f+1 个节点认可的稳定状态;丢弃旧日志,降低存储成本(p.18)。
2. CHECKPOINT 消息里带什么?
序号、执行到该序号后的状态摘要、副本 ID(p.18、p.19)。
3. Example 2 里检查点在第几号稳定、要几个匹配消息?
第 20 号,3 个,即 2f+1(p.19)。
4. 稳定检查点之后的已提交操作会不会作废?
不会。检查点是恢复起点,之后的操作照样有效,掉队副本从这里往后补(p.18、p.19)。
5. 哪些协议防拜占庭,哪些只防崩溃?
BFT、PBFT 防拜占庭,要 3f+1;VR、Paxos、Multi-Paxos 只防崩溃,要 2f+1(p.23、p.25)。
6. BFT 和 PBFT 的消息量?
BFT(OM)O(n^f),PBFT O(n²)(p.23)。
7. Basic Paxos 和 Multi-Paxos 的区别?
Basic Paxos 无 leader、管单个值;Multi-Paxos 通常有稳定 leader、管一串值(p.23、p.25)。
8. VR 和 PBFT 各要多少节点、法定人数多少?
VR 2f+1 个副本,法定人数 f+1;PBFT 3f+1 个副本,法定人数 2f+1(p.23)。
下一讲
下一讲是 L10a HotStuff:PBFT 每轮全员互发,消息量 O(n²),视图切换还要搬一大堆证书。带着问题读:如果每轮的票都交给 leader 汇总,消息量和换届的代价能降多少?
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。