VR 1988 — 用"主备 + 换届"做共识的另一脉

是什么

Viewstamped Replication（VR）是 1988 年 Brian Oki 和 Barbara Liskov 在 PODC 上发表的复制协议。日常类比：一个会议室有一名主持（primary）和几名旁听（backup），主持决定每条议案的顺序，旁听负责抄会议记录；一旦主持失联，剩下的人开换届会议（view change）选新主持，并把上一任没盖章的议案重新核对一遍——核对完成前不接受新议案。

view 就是”第几届”——每届有唯一主持。viewstamp 是 (view-number, op-number) 的二元组，给每条操作打”第 v 届第 n 号”这样的标签，让全局有序。

VR 等价于 Paxos 但用了完全不同的语言：Paxos 讲多数派投票、acceptor/proposer，VR 讲主备 + 换届。今天 raft 的 term + leader + log 几乎是 VR 术语的翻译。

为什么重要

不理解 VR 1988，下面这些事都没法解释：

为什么 raft 自称”易理解共识”，它的 term/leader/log 模型其实从 VR 来
为什么 paxos-1998 在工程上没人直接用——大家用的是 Multi-Paxos，而 Multi-Paxos 的 leader-driven 模式就是 VR 的思路
为什么 PBFT (Castro & Liskov 1999) 处理拜占庭也用 view change——直接搬的 VR
为什么 1988 年和 1989 年同时冒出 VR + Paxos 这两个共识协议（Lamport 在 DEC 同期搞 Paxos）
为什么”共识的难点其实在换届”这句话是过去 30 年分布式课的 punchline

核心要点

VR 把节点分成 两种角色（动态切换）：

Primary（主）：一个 view 内唯一处理客户端请求的节点，决定操作顺序
Backup（备）：复制 primary 的日志，回 ACK，不直接服务客户端

整个协议有 三个子协议：

Normal case（正常路径）：客户端 → primary 分配 op-number 并写日志 → 发 prepare 给 backups → 收齐 f+1 个 prepare-ok 即视为 committed → 回客户端 + 异步通知 backups commit
View change（换届）：任一节点超时怀疑 primary 死了 → 发 start-view-change(v+1) → 收齐 f+1 个 do-view-change 后，新 primary 选最大 view 的日志做基线 → 发 start-view 进入新一届
Recovery（崩溃恢复）：崩溃重启的节点不能直接加入，需先发 recovery 请求 + nonce → 收齐 f+1 个 recovery-response 才能并入新 view

关键不变量：2f+1 节点容忍 f 故障；正常路径需 f+1 个 ACK（含 primary 自己）；换届也需 f+1 节点参与——任意两个 quorum 必交集，保证已 committed 的日志不会在换届中丢失。

实践案例

案例 1：5 节点的正常路径（f=2，quorum=3）

Client → Primary P0 (view=1)
P0: op-number=42 写本地日志 → prepare(view=1, op=42, value="X") 给 P1..P4
P1, P2 回 prepare-ok → P0 已收 3 票（含自己）→ committed
P0 回 client "OK" → 异步广播 commit(op=42)

注意：只要 3 个节点 ACK 就 commit，不必等 P3、P4。这就是 quorum 的好处：少数慢节点不拖快路径。

案例 2：primary 死了，换届救场

P0 失联，P1 超时
P1: 发 start-view-change(view=2) 给所有人
P2 也超时跟进 → P3 跟进 → 收齐 3 个 do-view-change(包含各自 log)
view=2 的新 primary（按 view-number mod n 决定，比如 P1）
   选所有 do-view-change 里 view 最大、op 最大的那条日志做基线
P1: 发 start-view(view=2, log=...) → 大家进入第 2 届

为什么必须收 f+1：万一只收 f 个就换届，可能漏掉已 committed 的日志（committed 需 f+1 ACK，与换届 quorum 相交至少 1 个会带来这条日志）。

案例 3：viewstamp 怎么排序

两条日志条目：A=(view=3, op=10)，B=(view=2, op=99)。

谁更新？A 更新——viewstamp 字典序，view 优先。这一条让换届时选基线很简单：所有 do-view-change 里挑最大 viewstamp 的 log 即可。

具体 view-change 处理流程：

新 primary 收到 3 个 do-view-change：
  P1: log_max_viewstamp = (view=2, op=99)
  P2: log_max_viewstamp = (view=2, op=99)
  P3: log_max_viewstamp = (view=3, op=10)
→ 选 P3 的日志做基线（view=3 优先）
→ 把基线日志当成新 view 的初始状态
→ 广播 start-view，所有人 reset 到这个日志

重点：选基线只看 viewstamp，不看节点身份；这样保证了”最新 committed 的日志一定被保留”，因为 committed 必须有 f+1 节点 ACK，与换届的 f+1 quorum 必交集。

踩过的坑

viewstamp 不是墙钟时间：它是逻辑时钟（lamport-1978 那一脉）；view 才是粗粒度的”届数”，op 是同一届内的细粒度顺序。
backup 不能直接服务读：原版 VR 只让 primary 处理读写，否则可能读到上一届脏数据。后续工作（Read Lease）才补上。新人常误以为 backup 可以承担读流量。
换届必须凑齐 f+1：少了会丢已 committed 数据；多了浪费时间但安全。这个不对称是 quorum intersection 的直接结果。
不要读 1988 原版做工程：原文描述偏寓言、有些状态转移图不严谨。应读 Liskov & Cowling 2012 “VR Revisited”，那一版才是今天教学和实现的标准。
VR 不处理拜占庭：fail-stop only；要拜占庭安全得用 PBFT（Castro & Liskov 1999），它在 VR 之上加了消息认证 + 三阶段。
recovery 必须带 nonce：崩溃节点重启后发 recovery 请求时要带一个新的随机 nonce，要求其他节点把 nonce echo 回来。这是为了防止重启节点用过时的状态”假装”自己已经在某个 view 里——nonce 保证 response 是当前会话的回应而不是历史消息重放。新人实现时常忽略这个细节。

适用 vs 不适用场景

适用：

需要 state machine replication，副本 3-7 台
leader-based 模型可接受（绝大多数线上系统都接受）
跨机房容灾，希望 leader 路径快、follower 可异步追

不适用：

拜占庭故障场景（节点会撒谎、伪造消息）→ 用 PBFT
需要 leaderless / multi-master 写入 → 用 EPaxos 或 Generalized Paxos
网络极不稳定，view change 频繁触发会把吞吐打到地板
单机/双机系统（VR 至少要 2f+1 节点才能容忍 f 故障，f=1 起步就需要 3 节点）
强延迟敏感且无法接受 leader hop 的场景（每次写都得到 primary 然后再到 backup，跨机房一次至少一个 RTT）

历史小故事（可跳过）

1988：Brian Oki 在 MIT 跟 Barbara Liskov 做博士；VR 是他博论核心，PODC 1988 一起发。
1989：Lamport 在 DEC SRC 写完 Paxos，但被审稿人压到 paxos-1998 才发出来。也就是说 VR 比 Paxos 早 1 年公开问世。
1991：Liskov 团队用 VR 做 Harp 分布式文件系统（SOSP 1991），证明它在真系统里能跑。
1999：Castro & Liskov 把 VR 扩到拜占庭，写出 PBFT——PBFT 的 view change 几乎照搬 VR。
2012：Liskov & Cowling 重写 VR Revisited，今天教学引这一版。
2014：Stanford 的 Diego Ongaro 写 raft，承认借鉴 VR 的 leader/term/log 三件套。

学到什么

共识的难点在换届：正常路径每个协议都差不多，区别在 leader 死了之后怎么不丢数据、怎么不脑裂——VR 把这一点摆在最显眼的位置
同一个数学骨架可以有多种工程语言：Paxos 用投票/quorum 讲，VR 用主备/换届讲，Raft 用 term/leader/log 讲——三者数学等价但工程亲和度不同
viewstamp = 逻辑时钟在共识里的应用：lamport-1978 给了基础，VR 把它升级成 (view, op) 二元组让换届时排序变 trivial
多数派交集是几何不变量：只要每个 quorum 都含 f+1 节点，任意两个必交集——这一条决定了所有 leader-based 共识协议的安全性

关联

paxos-1998 —— 同期共识协议，数学等价但语言不同
paxos-simple-2001 —— Lamport 的简化版 Paxos，仍偏数学
raft —— 直接借鉴 VR 的 leader/term/log，自称”易理解版”
lamport-1978 —— viewstamp 用的逻辑时钟思想从这里来
spanner-2012 —— Google 跨大洲强一致系统，底层是 Paxos 系
chubby —— Google 锁服务，Multi-Paxos 实现，思想与 VR 同源

反向链接

chubby —— Chubby — 给凡人用的分布式锁服务
lamport-1978 —— Lamport 1978 — 分布式系统里没有”绝对的同时”
paxos-1998 —— Paxos 1998 — 古希腊议会寓言里藏的共识协议
paxos-simple-2001 —— Paxos Made Simple — Lamport 用平直英语把共识协议推导一遍
raft —— Raft — 易理解的共识算法
spanner-2012 —— Spanner 2012 — 用原子钟和 GPS 给全球数据库发时间戳
vr-revisited-2012 —— VR Revisited 2012 — VR 协议的”工程化重写版”