← COMP5567 全部讲次
L08a-2 · 第 8 周

L08a-2 VR 换届与恢复:主节点没了,从过半的日志里拼回账本

VR 的另外两个子协议:先弄懂 k 是「多数副本都已完成的最新操作号」,再一帧一帧跑一遍 view change,最后看崩溃的机器怎样补课、以副本身份回来。

一句话版

VR 的主节点崩溃后,剩下的副本换一个视图、选一台新主节点。新主节点从过半的副本那里收日志,拼出所有已经提交的操作,再接着往下排号。崩溃的机器修好后,先找过半的人把日志补齐,然后只当普通副本。

正常操作的四条消息、2f+1 和多数集交集,见上一页 L08a。这一页讲 VR 剩下的两个子协议:view change 和副本恢复。

先认识这几个词

词 全称 / 读法 一句人话
视图 / 视图号 v view 一任主节点的任期,换主节点时 v 加一
视图切换 view change 主节点失联后选新主节点、开新视图的子协议
日志 l log 一台副本按顺序记下的全部操作
k 课件记法 多数副本都已完成的最新操作号
副本恢复 recovery 崩溃的机器修好后补齐日志、重新加入
超时 timeout 等了太久没回音,就当对方出事了

一个类比:值班经理断线以后

四家分行轮值,本周一分行当值班经理。某天一分行突然断线,客户的转账请求石沉大海,其他分行也联系不上它。

剩下的分行按事先排好的顺序,请二分行接任。三、四分行把各自的账本交给二分行。二分行凑齐过半的账本后,挑出那些「过半分行都已经记下」的流水,作为确定无误的旧账,然后宣布:从现在起我是值班经理,新流水号接着旧账往下编。

一分行修好回来,发现值班经理已经换了。它先找过半的分行把这段时间的账抄回来,然后老老实实当一个普通分行。

类比在哪里失效:

  • 分行能打电话问一分行是不是真倒了。协议里的副本只能靠超时去猜,主节点也许只是网慢,协议得保证猜错了也不出错。
  • 类比里「事先排好顺序」一笔带过。课件没有展开新主节点具体怎样确定,只说换到下一个视图、由新主节点接手。

从零讲起

1. k:多数副本都已完成的最新操作号

它解决什么问题

换届时,各副本的日志长短不一。有的记到了 op 10,有的只到 op 8。新主节点要知道:哪些操作是一定已经定下、必须保留的?

k 就是这条分界线。k 以内的操作,已经在过半的副本上落了地,按上一页的交集论证,它们可能已经回复过客户端,必须保留。

直觉

一条操作算「已提交」,前提是过半的机器记下了它。那么从各家日志里找一个号码,使得「过半的副本都至少做到这里」。这个号码越往后越好,但不能超过过半的那条线。

一步一步看

目标:看三家副本日志长短不一时,怎样找出过半都做到的那个操作号 k。

课件的例子:主节点 Branch-I 崩溃后,三家副本的日志如下。

  1. Branch-II 做到 op 9。

  2. Branch-III 做到 op 10。

  3. Branch-IV 做到 op 8。

  4. 从后往前试。至少做到 op 10 的只有 Branch-III 一家,不够过半。

  5. 至少做到 op 9 的有 Branch-II、Branch-III 两家,3 家里的 2 家,构成多数。所以 k = op 9。

    三家副本日志长短对照:Branch-II、Branch-III、Branch-IV 分别做到 op 9、op 10、op 8,一条青绿竖线画在 op 9 右侧,标注 k = op 9,底部说明到 op 9 的有两家构成多数

怎么算

把各副本做到的操作号从大到小排好,取第「过半人数」个。

这里三个号是 10、9、8,过半是 2,从大到小数到第 2 个,是 9。

意思是:排在第「过半人数」位的那个号,正好是「有过半的副本至少做到这里」的最大值。比它大的号,做到的人数不够过半。

常见误解

以为 k 取最长那份日志的号

最长的日志里,最后几条可能只有它一家记了,还没过半,不能算已提交。k 要的是过半都做到的那一条。

以为 k 取最短那份日志的号

取最短的太保守,会把已经过半的操作丢掉。op 9 已经在两家落地,取 op 8 就漏了它。

试一下

5 台副本分别做到 op 6、op 9、op 7、op 9、op 5。过半是几?k 是多少?

5 台的过半是 3。从大到小排:9、9、7、6、5,第 3 个是 7,所以 k = op 7。做到 op 7 的有三家(9、9、7),够过半;做到 op 9 的只有两家,不够。

2. 视图切换(view change)

它解决什么问题

主节点崩溃了,没人排号,系统停住。view change 要做两件事:选出新主节点,并且保证旧主节点已经回复过客户端的操作一条都不丢。

直觉

旧主节点每条回复过的操作,都已经落在过半的副本上。新主节点只要也凑齐过半的日志,两组过半必有交集,那条操作至少出现在一份交上来的日志里。

所以 view change 的核心动作就是「收过半的日志」。

一步一步看

目标:看新主节点怎样靠收齐过半的日志上任,让旧主节点回复过的操作一条不丢。

四家分行,Branch-I 是旧主节点,Branch-II 接任。每一帧里近黑的是这一步的消息,灰色的是前面走完的步骤。

  1. Branch-I 崩溃。客户端长时间收不到回复,或副本联系不上主节点,换届开始。

    视图切换第一帧:四条泳道是 Branch-I 旧主节点、Branch-II 新主节点、Branch-III、Branch-IV,Branch-I 的线打叉后变成虚线,Branch-III 和 Branch-IV 上标着等不到主节点

  2. 副本把 ⟨doviewchange v, l, k, i⟩ 发给新主节点 Branch-II。v 是新视图号,l 是自己的日志,k 是自己知道的已提交位置,i 是自己的编号。

    视图切换第二帧:Branch-III 和 Branch-IV 把 doviewchange 箭头发给 Branch-II,Branch-II 旁青绿标签写着收齐 3 份等于过半,底部说明视图号从 1 改成 2

  3. Branch-II 连自己在内收齐过半的 doviewchange,把视图号从 1 改成 2,从这些日志里拼出完整的已提交操作,发 ⟨startview v, l, k⟩ 给所有副本。

    视图切换第三帧:Branch-II 把 startview 箭头发给 Branch-III 和 Branch-IV,Branch-II 旁标着 v 等于 2,前一步的 doviewchange 退成灰色

  4. 各副本执行还没执行的已提交操作。新主节点回复客户端,开始接受新请求,操作号接着旧日志往下排。

    视图切换第四帧:Branch-II 上标着接受新请求,前面的 doviewchange 和 startview 都退成灰色,Branch-I 仍是虚线

怎么判断

新主节点在第 3 步问自己:收到的 doviewchange,连自己在内,够不够过半?

意思是:够了才能宣布新视图,因为只有过半的日志才一定和旧主节点的每一组确认重叠;不够就继续等,宁可停着也不带着残缺的日志上任。

2f+1 台时,过半就是 f+1。坏的是主节点,剩下 2f 台,还够凑 f+1 份。

常见误解

原主节点修好后会重新当主节点

它崩溃期间系统已经换了视图,新主节点在岗,它回来只能当副本。

以为换届时旧主节点手里没确认完的操作也会被保留

不一定。只有过半记下、已经提交的操作才保证保留。没凑够过半的操作,旧主节点也没回复过客户端成功,丢了不违反任何承诺,客户端会重试。

试一下

3 台机器跑 VR,主节点崩溃。剩下 2 台能完成 view change 吗?再坏一台呢?

3 = 2 × 1 + 1,f = 1,过半是 2。剩下 2 台正好够,能完成。再坏一台只剩 1 台,凑不到 2 份 doviewchange,换届完成不了,系统停住但不会出错。

3. 副本恢复(recovery)

它解决什么问题

一台机器崩溃后修好了,它的日志停在崩溃那一刻,这期间别人可能已经提交了新操作,甚至换了主节点。它要先补齐,才能重新参与投票。

直觉

它自己的记忆已经不可信,那就去问别人。问过半的人,过半里一定包含所有已提交操作的见证者。

一步一步看

目标:看崩溃后修好的 Branch-I 怎样向别人补齐日志,以普通副本身份回归。

  1. Branch-I 修好,向所有节点发 dorecoveryrequest(v, i),i 是自己的编号。

  2. 各节点回 dorecoveryresponse(v, l, k),带上视图号、日志和 k。

  3. Branch-I 收到 f+1 个响应,按其中的日志同步自己的状态。

  4. 这时系统已经是 Branch-II 当主节点的新视图,Branch-I 以普通副本身份回归。

    VR 副本恢复:恢复中的 Branch-I 向 Branch-II、Branch-III、Branch-IV 发 dorecoveryrequest,三家各回 dorecoveryresponse,最后一列 Branch-I 上青绿标签写着当普通副本

怎么判断

恢复中的节点问自己:响应够 f+1 个了吗?

意思是:够了,这些响应里一定有人见证过每条已提交操作,按它们同步就不会漏;不够,就继续等,在补齐之前不参与投票。

常见误解

以为恢复的节点用自己硬盘上的旧日志直接回来就行

旧日志缺了它崩溃期间提交的操作,直接回来会让它按过时的状态回应,可能把别人带偏。必须先从过半的节点那里补齐。

试一下

5 台机器跑 VR,一台副本崩溃后修好。它最少要收到几个 dorecoveryresponse?

5 = 2 × 2 + 1,f = 2,要 f+1 = 3 个。

把它们串起来

正常操作靠「过半确认才回复」把每条已提交操作放到了过半的机器上。这一页的两个子协议,都是在用这个事实。

view change 让新主节点收过半的日志,两组过半必有交集,已提交的操作一条都漏不掉。k 标出了「过半都做到」的那条线,线以内的必须保留。

副本恢复反过来,让回来的机器去问过半的人。三个子协议用的是同一个门槛。

代价也一样:凑不够过半,系统就停住。停住不会出错,只是暂时不可用。

课件里的坑

  • [读图提醒] p.13 旁注写「Branch-III lacks op 10」,同页列表写 Branch-III 到了 op 10,两处矛盾;k = op 9 的结论不受影响(p.13)。
  • [页码说明] 课堂批注版比原版多 3 页,分别插在原版 p.19、p.29、p.42 之后。本页写「批注版 p.N」的按批注版计,其余页码按原版。
  • [读图提醒] p.15 的换届图画了四家分行,对话框写「After f+1 responses」。四个节点凑不成 2f+1,课件没交代这里 f 取几。图里两个副本都发了 doviewchange,连新主节点自己是 3 个节点,已超过半数。以下是推断:如果按 f = 1 数成 f+1 = 2 份并把新主节点自己算进去,四个节点里的 2 个不是多数;节点数不是 2f+1 时,按「超过半数」去数更稳妥。同一问题在 p.17 Exercise 1 的四节点图里也出现(p.15、p.17、p.19)。

课后 10 分钟:考点复习

这 10 分钟怎么用:先合上页面,默写 doviewchange、startview、dorecoveryrequest、dorecoveryresponse 四条消息的字段;再把 k 的算法用自己的话讲一遍;然后按时间线画完整例题,最后做变式题。

必背

  1. VR view change:doviewchange(v,l,k,i) 收 f+1 后换视图,startview(v,l,k);恢复节点收 f+1 个响应后以副本身份回归
  2. k 是多数副本都已完成的最新操作号:三家分别到 op 9、op 10、op 8 时 k = op 9
  3. 触发 view change:客户端长时间收不到回复,或副本联系不上主节点
  4. 换届后操作号接着旧日志往下排;新主节点从 f+1 份日志里拼回所有已提交操作
  5. 备份 PREPAREOK 少于 f 个时操作不提交,主节点不能回复成功;客户端在换届后重试

课件例题

例 1(课件 p.13):新主节点的 k

Branch-II 到 op 9,Branch-III 到 op 10,Branch-IV 到 op 8。新主节点的 k 取几?

提示

数一数至少做到每个号的有几家。

解答

k 是多数副本都完成的最新操作号。至少到 op 9 的有两家,构成多数,所以 k = op 9。

例 2(课件 p.18,Example 1):主节点崩溃前后的两次写入

见下方完整例题。

例 3(课堂批注版 p.20):只有一个备份回应时,主节点能不能回复成功

5 个副本(f 为 2,法定人数 3),主节点 P 在视图 v 收到请求,给 B1–B4 发 PREPARE。只有 B1 回 PREPAREOK,B2 没回、B3 崩溃、B4 不可达。P 该怎么做?之后系统怎样继续?

VR 故障与恢复八步图:5 个副本、法定人数 3;主节点 P 发 PREPARE 后只有 B1 回 PREPAREOK,记录了该操作的只有 P 和 B1 两份,少于 3,不提交、不回复成功;超时后换届,B2 成为视图 v+1 的新主节点,从多数副本收集日志,只保留已提交操作,未提交的请求由客户端重试
图片来源:COMP5567 Lecture_8-VR-Paxos-anno.pdf(课堂批注版), p.20,红笔为老师手写批注
提示

先数有几份副本记下了这个操作,再和法定人数比。

解答

记下操作的只有 P 和 B1 两份,少于法定人数 3。主节点拿到的备份 PREPAREOK 少于 f 个,操作不算提交,P 不能回复客户端成功。副本等不到进展就超时,发起 view change,选出新主节点(图中是 B2,视图 v+1)。B2 从多数副本收集日志,只保留已提交的操作;这条未提交的请求不在日志里,客户端换届后重试。整条链是:凑不够法定人数 → 不提交 → 不回复成功 → 换届 → 新主节点接着服务。

例 4(课件 p.39–40):三台服务器用 VR 写入 set x=1

A、B、C 三台服务器,A 是主节点。写出 set x=1 的正常流程,以及 A 失效后系统怎样继续。

提示

前半段是正常操作四步,后半段是 view change。

解答

主节点 A 收到请求,给 B、C 发 prepare(set x=1, view=1);B、C 回 ack(view=1);A 拿到过半确认后提交,并通知 B、C 提交。A 失效时,B、C 发现后发起 view change,选出新主节点(比如 B),B 接着处理请求。

完整例题

题面:三个副本 R1、R2、R3,R1 是主节点。客户端先发「Set X = 5」,再发「Set X = 6」,但第二条请求到达前 R1 崩溃。按时间线写出四步:正常操作、主节点失效、视图切换、新操作。(课件 p.18,Example 1)

约定:3 台机器,f = 1,过半是 2;课件这页把 prepareok 简写成 ack,把通知副本执行写成 commit。

解法:

  1. 正常操作。R1 收到请求,分配序号 1,向 R2、R3 发 prepare(1, X=5);R2、R3 回 ack(1);R1 拿到过半确认后发 commit(1) 并回复客户端。
  2. 主节点失效。R1 崩溃,客户端把「Set X = 6」发给 R1,收不到回应。
  3. R2、R3 超时后开始视图切换,新视图是 View 2,主节点是 R2。
  4. 视图切换。R2 从 R3(和自己)收集状态,2 份 = 过半,确认所有已提交的操作都在,然后以主节点身份恢复处理请求。
  5. 新操作。R2 收到「Set X = 6」,分配序号 2,向 R3 发 prepare(2, X=6);R3 回 ack(2)。
  6. R2 加 R3 已是 3 个里的 2 个,构成多数,R2 发 commit(2) 并回复客户端。

要点:换届之后序号接着往下排,新主节点靠过半的状态保证 X = 5 没丢(p.15、p.18)。

答题格式:按四个阶段分段写,每段写清谁发什么消息、凑了几份、为什么够。

变式题(先自己做)

(1) 5 个节点跑 VR,主节点是 R1,R4、R5 都已崩溃。如果 R1 此时也崩溃,剩下的节点能完成 view change 吗?(改编自课件 p.17)

提示

先算 5 个节点的过半是几,再数崩溃后还剩几台。

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

5 = 2 × 2 + 1,f = 2,过半是 3。R1 再崩溃就只剩 R2、R3 两台,凑不到 3 份 doviewchange,view change 完成不了,系统停住。停住不会出错,只是不可用。

(2) 3 台副本换届时,新主节点收到的两份日志分别做到 op 4 和 op 6。k 是多少?op 5、op 6 一定会被保留吗?(自编情境)

提示

3 台的过半是 2,看两份日志都做到哪里。

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

两份都做到的最新号是 op 4,k = op 4。op 5、op 6 只在一份日志上,不保证已提交,旧主节点也不会因为它们回复过客户端成功,不保证保留。

(3) 5 台机器跑 VR,主节点发出 prepare 后只收到 1 个 prepareok 就崩溃了。客户端会看到什么?这条操作一定会出现在新视图里吗?(改编自课堂批注版 p.20)

提示

f = 2 时要几份记录才算提交?

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

主节点加 1 个副本是 2 份,5 台的过半是 3,不够,操作没提交,主节点也没回复成功。客户端收不到回应,换届后重试。新主节点只保证保留已提交的操作,这条不在保证范围内。

闪卡自测

1. 什么情况会触发 VR 的 view change?

客户端长时间收不到回复,或副本联系不上主节点(p.15)。

2. doviewchange 带了哪些字段?

v、l、k、i:新视图号、自己的日志、已提交位置、自己的编号(p.15)。

3. 三家副本分别到 op 9、op 10、op 8,k 取几?

op 9:至少到 op 9 的有两家,构成多数(p.13)。

4. 新主节点收齐 doviewchange 后发什么?

startview(v, l, k),所有副本执行还没执行的已提交操作(p.15)。

5. 崩溃的副本修好后怎样重新加入?

发 dorecoveryrequest,等 f+1 个 dorecoveryresponse,同步日志后以普通副本身份回归(p.16)。

6. 5 个副本里只有 1 个备份回了 PREPAREOK,主节点能回复客户端成功吗?

不能。连主节点在内只有 2 份记录,少于法定人数 3,操作不提交;超时后换届,客户端要重试(批注版 p.20)。

7. 换届后新操作的序号从几开始?

接着旧日志往下排,Example 1 里 X = 5 是序号 1,换届后 X = 6 是序号 2(p.18)。

下一讲

下一页是 L08b Paxos 两阶段:同样靠过半交集,但没有固定主节点,谁都可以提议。带着问题读:没有主节点排号,怎样保证已经选定的值不会被后来的提议换掉?

下一讲 →
L08b L08b Paxos 两阶段:谁都能提议,但已选定的值只能被再提一遍

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