SMR 1990 — 把"容错服务"还原成"多副本一起跑同一台状态机"

是什么

SMR 1990 全称 State Machine Replication——状态机复制。日常类比：你和 4 个朋友各自抄一本完全相同的账本，每收到一笔账都按同一顺序记下来。只要”大家都收到了同一组账”和”大家按同一顺序记”两件事保住，5 本账永远长得一样；丢一两本（朋友辞职、账本烧了）剩下的还能继续对账，外界看上去像永不出错的一台机器。

Schneider 把这个思路抽象成：把任何确定性服务（KV store、文件系统、订单中心）建模为一台状态机——给定当前状态 + 输入命令，下一状态唯一确定。把这台状态机复制到 n 个副本上，让它们以相同初始状态 + 相同命令序列跑下去，输出必然一致。容错问题就归约为两条要求：agreement（所有正确副本都收到同一组命令）+ order（按相同顺序执行）。

这篇 tutorial 是 1990 年发在 ACM CSUR 上的综述，把零散在 Lamport / Schlichting / Cristian 论文里的”复制状态机”思路第一次系统化。后来 30 年所有共识论文（Paxos / Raft / Zab / VR）的术语和分析框架基本都来自这里。

为什么重要

不理解 SMR，下面这些事都解释不了：

为什么 paxos-1998 / raft / Zab / VR 各自细节不同却能互换：它们都是 SMR 的 ordering layer 实现
为什么 chubby / ZooKeeper / etcd 的”复制日志 + 状态机回放”结构会撞脸：这是 SMR 的标准模板
为什么”确定性”在分布式系统里被反复强调：状态机非确定 = 副本立刻分叉
为什么拜占庭容错要 3t+1 副本而不是 t+1：拜占庭场景下输出投票要走多数派

只要系统里有”多副本 + 强一致”的需求，背后的抽象骨架就是 SMR。

核心要点

状态机抽象：服务 = 一个确定函数 (state, command) → (state’, output)。像一台收银机：当前余额 + “+100” 命令 → 新余额 + 凭条。只要这个函数确定，所有副本喂同样命令就长一样。
agreement + order：所有正确副本收到同一组请求，且按同一顺序执行。这两条合起来叫 atomic broadcast 或 total order broadcast。Paxos / Raft 的核心就是实现这个。
容错门槛：fail-stop（节点要么对要么宕，不撒谎）只要 t+1 个副本能容 t 个故障；拜占庭（节点会撒谎）需要 2t+1 个副本做多数投票；异步 + 拜占庭还要 safety 时门槛升到 3t+1。
客户端投票：拜占庭场景下客户端不能信单个副本回复，要收齐 t+1 条相同回复才采信；fail-stop 场景一条够用。这是 PBFT 之后的工业实现都遵守的规则。

把这 4 条对在一起，就能把任何”我要做容错版的 X 服务”归约为”实现 atomic broadcast + 写一个确定状态机”。

实践案例

案例 1：3 副本 KV store（fail-stop）

客户端 → SET k=v
   ↓ atomic broadcast 到 3 副本
副本 1: log[7] = SET k=v → 执行 → 状态更新
副本 2: log[7] = SET k=v → 执行 → 状态更新
副本 3: log[7] = SET k=v → 执行 → 状态更新
任意副本回 "OK" → 客户端采信

3 副本同步执行，任意 1 个宕机不影响（t=1, 副本数 = t+1 = 2 还够用，3 副本能容 2 故障）。这就是 etcd / chubby / bigtable 元数据服务的运行模型。

案例 2：拜占庭 4 副本（t=1）

客户端 → GET k
副本 1 回 v=apple    ← 真值
副本 2 回 v=apple    ← 真值
副本 3 回 v=banana   ← 撒谎
副本 4 回 v=apple    ← 真值
客户端收到 ≥ t+1=2 条相同 → 采信 v=apple

拜占庭副本可以撒谎、可以不回，但凑不出 t+1=2 条相同假回复。客户端按多数表决采信。PBFT、HotStuff 都基于这条骨架。

案例 3：非确定性陷阱

状态机里写了：
  on SET k=v:
    timestamp = now()         ← 本地时钟，副本各异
    state[k] = (v, timestamp)

副本 1 取到 t=100, 副本 2 取到 t=101, 副本 3 取到 t=99
3 副本状态立刻分叉。

修复方式：所有非确定输入由 leader 在命令中写死。

leader 决定 timestamp=100，写进命令：
  log[7] = SET k=v WITH ts=100
3 副本读命令里的 ts，状态保持一致。

时间、随机数、读本地文件大小都是常见非确定源，必须显式注入。这条规则在 raft 和 spanner 实现里反复出现。

踩过的坑

状态机必须是确定函数——一行 now() 或 random() 就让副本立刻分叉，但 bug 要等到状态分歧外显才被发现，定位极难。生产实现把所有非确定输入显式注入命令流。
agreement 不等于 order——TCP/UDP multicast 只解决了”广播到位”，不保证副本之间的执行顺序一致。必须叠 total order layer，这就是 paxos-1998 / raft / Zab 的核心工作。
客户端不能信任单副本回复——拜占庭场景下副本可以撒谎或选择性回。客户端必须收齐 t+1 条相同回复才采信。fail-stop 场景下任意一条够用，因为副本要么对要么沉默。
状态机大 = 同步代价大——每副本存全量状态。100GB 状态意味着新副本加入要传 100GB。生产系统普遍用 snapshot + log truncation 控制成本，但论文没讨论这个工程问题，全是工业自己补的。

适用 vs 不适用场景

适用：

多副本一致性服务（KV store / 元数据 / 分布式锁）
严格 safety 要求的写路径（金融、订单、配置中心）
5-7 节点同 IDC 或跨 IDC 部署
读多写少 + 状态可控大小（GB 级）

不适用：

状态超大（TB 级）的纯数据存储——快照同步成本压垮系统
高吞吐流式写入——atomic broadcast 多 RTT + fsync 限制吞吐，应该用 Kafka 类协议
跨大洲低延迟读写——光速决定 RTT 下限，70ms+ 不可绕过
服务本身非确定（依赖外部 RPC、时间、随机）——要么改写成确定，要么放弃 SMR

工业最常见的形态：SMR 跑元数据 + 大数据量走最终一致复制。

历史小故事（可跳过）

1978 年：lamport-1978 给出 happens-before 偏序。SMR 的 order 概念直接继承自这里。
1985 年：FLP 不可能定理证明”异步 + 故障 + 共识”三选二。SMR 的 ordering layer 必须在它阴影下生存。
1988 年：MIT 的 Oki-Liskov 写 Viewstamped Replication，第一个真正可跑的 SMR 协议，但被忽略多年。
1989 年：Lamport 写完 paxos-1998 草稿，被审稿人压了 8 年。
1990 年：Schneider 这篇 tutorial 在 ACM CSUR 发表，把”状态机复制”提升为统一抽象，成为后续所有共识论文的术语母版。
2014 年：raft 论文发表，把 SMR + Multi-Paxos 重新包装成易懂版本，工业界广泛采用。

学到什么

抽象的力量——把”容错服务”归约为”两件简单事”（agreement + order）是论文影响力的根源。后 30 年共识工作都在这两条骨架上打补丁。
确定性是分布式的隐形契约——单机程序非确定无所谓（每次跑结果不同就不同），SMR 一旦有非确定立刻分叉。这条强约束在工业实现里被反复踩。
fail-stop / 拜占庭门槛差一倍——t+1 vs 2t+1 vs 3t+1。设计前要先想清楚故障模型；模型选错容错门槛立刻变天。
tutorial 的影响力可以超过原创论文——Schneider 没发明状态机复制，但把它系统化、教学化的这篇综述成了所有共识系统的术语 SoT。写得清楚比想得深更稀缺。

关联

paxos-1998 —— SMR 抽象框架的具体协议实现，回答”怎么做到 agreement+order”
raft —— 易理解版 SMR ordering layer，工业广泛采用
lamport-1978 —— happens-before 偏序，SMR 的 order 概念源头
chubby —— Google 第一个公开的 SMR 工业部署
zab-2011 —— ZooKeeper 的 SMR ordering 协议，FIFO 顺序保证
spanner —— Multi-Paxos × SMR 跨大洲全球部署
tigerbeetle —— 现代记账数据库的 SMR 派生协议产品级实现
bigtable —— Chubby 之上构建的列式存储，证明 SMR 抽象可承载 PB 级
bernstein-1981-cc —— 单机并发控制综述，与 SMR 拼起来构成完整复制事务模型
aries-1992 —— 单机崩溃恢复骨架，叠到 SMR 上才是工业级容错日志体系

反向链接

aries-1992 —— ARIES 1992 — 数据库崩溃后怎么把账目对回来
bernstein-1981-cc —— Bernstein 1981 并发控制综述 — 把分布式数据库的 20+ 算法整成两条主线
brewer-cap-2000 —— Brewer CAP — 网络一断电，一致性和可用性只能留一个
chubby —— Chubby — 给凡人用的分布式锁服务
craq-2009 —— CRAQ — 让链复制每个节点都能读，吞吐线性扩展
lamport-1978 —— Lamport 1978 — 分布式系统里没有”绝对的同时”
linearizability-1990 —— Linearizability 1990 — 让并发对象看起来像一次只执行一个操作
paxos-1998 —— Paxos 1998 — 古希腊议会寓言里藏的共识协议
raft —— Raft — 易理解的共识算法
spanner —— Spanner — 全球分布式 SQL 数据库
tigerbeetle —— TigerBeetle — 只能记账但把记账做到极致的金融数据库
zab-2011 —— Zab — ZooKeeper 怎么把客户端写入按顺序复制到所有副本