主题
共识算法：主节点换了，已经答应的事不能反悔
把同一份数据复制到三台机器，能防止一台机器宕机后数据完全不可用。但如果主节点在“已经写给部分副本、还没向所有人确认”时退出，新主该保留哪些记录？客户端收到成功的写入，会不会在换主后消失？这才是共识算法要解决的核心问题。
本文用 Raft 讲清选主、日志复制与安全性，再用 Paxos 和 ZAB 对照它们各自组织问题的方式。要记住的是协议如何把旧决定带进新一轮，而不只是“超过半数就成功”。示例只验证几个有界条件，不是 Raft、Paxos 或 ZAB 的实现。
先认清三层：决定、日志、业务状态
单次共识让参与者对一个值达成一致。复制状态机则需要不断确定命令顺序：先决定日志位置 1 的命令，再决定位置 2，依次应用到同样的初始状态。Raft 直接围绕这条日志组织；Basic Paxos 先描述一个值如何被选定，Multi-Paxos 再把它用于多个日志位置。[1][2]
正在绘制图示…
查看图源代码
flowchart LR
C[客户端命令] --> L[领导节点接收]
L --> R[复制日志与取得协议所需确认]
R --> K[确认某段日志可提交]
K --> A[按索引应用到状态机]
A --> O[返回业务结果]
R -. 未提交尾部可能被替换 .-> U[换主后的日志修复]
| 名称 | 回答的问题 | 常见混淆 |
|---|---|---|
| 已写入日志 | 某个副本是否保存了这条记录？ | 一台机器有记录，不等于集群已决定 |
| 已提交，committed | 协议是否保证以后不能改掉这个决定？ | 不能把任意多数派持有任意旧记录都叫已提交 |
| 已应用，applied | 状态机是否已经执行到该位置？ | 已提交但还未应用的节点，直接读状态仍可能落后 |
| 客户端收到成功 | 响应是否到达调用方？ | 没收到成功不代表没提交；重试可能造成重复业务动作 |
复制状态机要求执行同一命令得到一致效果。当前时间、随机数和外部服务响应若影响状态，通常要把选定结果放进日志，或由应用设计确定性的处理方式。协议负责命令顺序，不能替应用修复不确定的业务代码。[1]
多数派交集有用，但它只是第一块积木
固定 5 个投票节点，任意两个 3 节点集合至少相交 1 个。这个交集让新一轮有机会接触旧一轮的信息。我们的模型枚举全部大小为 3 的集合，检查每一对：
go
p, d := majorityIntersections(5)
fmt.Println("5 voters: quorum pairs =", p, "disjoint =", d)实际输出：
text
5 voters: quorum pairs = 100 disjoint = 0共有 10 种三节点集合，所以有 100 个有序集合对。这只证明这个固定集合的组合性质。要让它支持协议安全性，交集中的节点还得记得自己承诺过什么，并按规则拒绝冲突请求。
典型固定配置的 Raft 用 2f+1 个投票节点，在最多 f 个节点不可用且剩余节点能正常通信等条件下仍可推进；多数派不是容忍任意拜占庭行为的阈值。不要据此推导所有 Paxos 变体都要求每个阶段相同大小的简单多数派，或 ZooKeeper 只能采用一种 quorum 配置。[1][2][3]
Raft 选主：选票带着任期，也带着历史约束
Raft 节点有 follower、candidate、leader 三种角色。任期 term 是逻辑编号，用来区分一轮轮领导权，不是日期或租约到期时间。节点看见更高任期，就更新任期并退回 follower。超时只是怀疑当前领导失联，并不证明旧 leader 已死。[1，§5.1–5.2]
正在绘制图示…
查看图源代码
stateDiagram-v2
[*] --> Follower
Follower --> Candidate: 选举超时，任期加一并自投
Candidate --> Leader: 获得该配置多数票
Candidate --> Candidate: 再次超时，发起新任期
Candidate --> Follower: 收到有效领导消息或更高任期
Leader --> Follower: 发现更高任期
每个节点在一个任期内最多把票给一个候选人。任期和投票记录必须在相应响应之前持久化，否则重启后“忘了投过票”，同一任期可能再次帮助另一个候选人取得多数派。
模型只保留这条投票规则：
go
v := Vote{}
fmt.Println("same term A then B:", v.grant(7, "A"), v.grant(7, "B"))
v = Vote{} // 错误重启：把已持久化状态也丢了
fmt.Println("lost vote after restart, B:", v.grant(7, "B"))实际输出：
text
same term A then B: true false
lost vote after restart, B: true这段故意错误的“重启”没有演出整个双主集群；它展示的是安全论证所需的前提已经被破坏。磁盘持久化不是一个可晚点补上的性能选项。[1，图 2][4]
候选人还必须通过日志新旧检查。Raft 比较最后一条日志的 (term, index)：先比任期，任期相同再比索引。于是 (term=2,index=100) 不比 (term=3,index=10) 新。只数日志条数会选错人。
go
fmt.Println("longer but older tail:", upToDate(Tail{2, 100}, Tail{3, 10}))text
longer but older tail: false这是为什么选主不能简化成“先超时的人获胜”：先发起只是获得机会，最终还要得到满足投票规则的多数支持。随机化选举超时主要减少撞在一起的选举，提高活性；日志限制和投票规则才承担安全性职责。论文里的毫秒示例不是适用于所有机房的默认调参答案。[1，§5.2、§5.4.1]
Raft 复制：先确认共同前缀，再补尾部
leader 发 AppendEntries 时，不只发送新记录，还携带新记录之前的 prevLogIndex 和 prevLogTerm。follower 先检查那里是否一致；不一致就拒绝。leader 据反馈找到共同前缀，再修复冲突的未提交尾部。[1，§5.3]
假设 leader 的日志任期序列是 [1,1,3,3]，follower 是 [1,1,2]。位置 2 一致，位置 3 冲突。修复从冲突位置开始；不是把两份日志按长度拼起来，也不是删除每个暂时多出来的条目就算完成。协议保证同一索引、同一任期的记录所对应的前缀相同，这叫日志匹配性质。
正在绘制图示…
查看图源代码
sequenceDiagram
participant L as Leader
participant F as Follower
L->>F: prev=(3,3)，追加位置 4
F-->>L: 拒绝：本地位置 3 的任期为 2
L->>F: prev=(2,1)，发送位置 3、4
Note over F: 前缀匹配后替换冲突尾部并持久化
F-->>L: 确认复制到位置 4
Note over L: 按提交规则更新 commitIndex
L->>F: 后续消息携带提交位置
Note over F: 按顺序应用已提交日志
图只画一个 follower，实际提交要看该配置需要的 quorum。延迟消息和重复消息必须通过任期、索引及已有状态判断；“收到一次 ACK 就把计数加一”会把重复响应当成多个节点。
为什么旧任期日志在多数节点上，也不能直接按票数提交？
Raft 的 leader 用复制数量直接推进提交位置时，要求该位置上的日志属于当前任期。旧任期的记录可能经历过不同领导的复制过程，单看它当前分布在哪些机器上，不足以排除后续合法选举覆盖它。原论文图 8 给出了这种反例。[1，§5.4.2]
go
fmt.Println("term 2 entry in term 4, 3/5:", directCommit(2, 4, 3, 5))
fmt.Println("term 4 entry in term 4, 3/5:", directCommit(4, 4, 3, 5))实际输出：
text
term 2 entry in term 4, 3/5: false
term 4 entry in term 4, 3/5: true第二行确认当前任期的某条记录可提交后，它之前的日志也随前缀一起提交。第一行并不是说旧记录永远不能提交；限制针对的是“仅凭副本计数直接提交该旧记录”这一步。这个条件属于 Raft，不能把它写成 Paxos、ZAB 的统一规则。
安全性不是一条多数公式
Raft 的证明把几条性质连在一起：同一任期至多选出一个 leader；leader 自己的日志只追加；日志匹配；已提交条目出现在后来任期的 leader 中；各状态机不会在同一位置应用不同命令。选举限制与当前任期提交规则共同支撑后两条。[1，图 3、§5.4]
| 工程问题 | 为什么仅看“写到多数”不够 | 还需要什么 |
|---|---|---|
| leader 与多数派隔离但仍在运行 | 它可能继续相信自己是 leader | 新写无法获得合法确认；读也必须确认领导权或满足安全租约条件 |
| follower 已保存日志但未应用 | 内存状态落后于已提交位置 | 读屏障与 applied index 检查 |
| 重启后投票丢失 | 同一任期可能重新投票 | 正确持久化任期、票和日志，遵守发送时序 |
| 客户端超时重试 | 同一业务命令可能被提交两次 | 客户端 ID/序列号、结果缓存或业务幂等 |
| 集群成员变化 | 旧配置多数与新配置多数可能不相交 | 按协议做配置转换，不能同时随意替换一半节点 |
Raft 论文的 joint consensus 通过重叠配置，要求转换期同时满足旧、新配置的多数条件；具体库可能提供特定的配置变更流程，应遵守该实现的约束。[1，§6][4] “三节点改成另三个节点”不是修改一个配置文件就完成的事。
快照解决日志无限增长的问题，但也必须记住它覆盖到哪个索引和任期、相应的状态及配置。把某个节点的任意数据库文件拷给别人，不等于完成 Raft 的 InstallSnapshot。[1，§7]
线性一致读取也有额外条件。读者至少需要知道自己读的节点没有落在一个失去领导权的旧世界，并且状态机已应用到足够新的位置。新当选的 leader 还必须先确定提交前缀，论文的办法是先提交一条当前任期的记录，通常是初始 no-op；然后通过与多数派交换心跳确认领导权，并等状态机应用到读取屏障要求的位置。Raft 论文讨论这一过程，也讨论依赖时间假设的租约优化；etcd/raft 的 README 则区分 ReadIndex 和 lease-based read，后者明确依赖时钟条件。[1，§8][4] 不能把“发给 leader”当作无条件的线性一致性证明。
Paxos：新提案必须继承可能已经选定的值
Basic Paxos 常用三类角色：proposer 提议值，acceptor 记承诺并接受提案，learner 获知最终选定的值。一台进程可以同时承担多个角色。“提案编号”区分竞争轮次；它不是日志索引，也不等于 Raft 的任期。[2]
| 阶段 | 发起者做什么 | acceptor 必须记住什么 | 为什么需要 |
|---|---|---|---|
| Phase 1：Prepare / Promise | 选择新的、足够大的唯一编号，发 Prepare 并收齐多数 acceptor 的 Promise | 承诺不再接受更小编号；返回自己已经接受的最高编号和值 | 让新提案看到旧决定可能留下的证据 |
| Phase 2：Accept / Accepted | 在收齐多数 Promise 后，若其中有已接受值则选最高编号的值；否则可选新值 | 在没有更高承诺阻止时接受 (编号, 值) | 新轮不能任意改掉已选定的内容 |
| 学习结果 | 获知某个值已被多数 acceptor 接受而选定 | 决定与业务应用状态 | “某节点接受过”与“值已被选定”不同 |
假设 A、B 已接受编号 5 的值 X。假设共有 A、B、C 三个 acceptor，新的 proposer 用编号 6 向 B、C 发 Prepare 并收到这两个节点的 Promise，B 会把 X 带回来。proposer 不能说“我是新领导，所以改成 Y”；它必须按 Phase 1 收到的最高编号已接受提案来选择值。这一继承规则加上 quorum 交集，才阻止两个不同值都被选定。[2，§2.2]
Paxos 的安全性不要求每一轮都能迅速完成，但多个 proposer 不断用更高编号互相打断，可能没有进展。稳定领导者可以减少这种争抢。Multi-Paxos 在稳定领导等条件满足后，让同一领导处理多个日志位置，减少反复进行准备阶段的开销；换领导时仍须正确恢复每个位置的信息，不能把“只做一次 Prepare”理解为永久免检。[2，§3]
Paxos 与 Raft 都能支撑复制服务。Raft把领导选举与日志结构规定得更直接；Paxos 的基本表述更小，组成完整服务时还需决定日志、领导管理、学习与重配置方式。这里没有测它们的性能，不能根据协议图上的箭头数量推导某个实现一定更快。
ZAB：新主先接上旧历史，再广播新的状态变化
ZAB 是 ZooKeeper 为主备复制设计的崩溃恢复原子广播协议。它关注 primary order：同一个 primary 的增量状态变化必须保持顺序；换 primary 后，新变化必须接在协议要求保留的旧历史之后。ZooKeeper 的 primary 可以流水线地产生多个尚未全部确认的更新，因此恢复不能只找到“一个看似最新的主”。[5]
论文把协议组织为 discovery、synchronization、broadcast 三个阶段。选出候选 primary 之后，发现阶段收集历史并建立新的 epoch；同步阶段让参与 quorum 的节点采用合适的历史前缀；达到协议规定的激活条件后，新 primary 才开始广播新变化。选举结束与可安全接收新写入之间，还隔着恢复和同步。
正在绘制图示…
查看图源代码
flowchart LR
E[候选 primary] --> D[发现：收集 epoch 与历史]
D --> S[同步：建立应保留的历史前缀]
S --> Q[达到激活所需确认]
Q --> B[广播：分配 zxid 并复制更新]
B --> C[满足确认条件后提交]
B -. 主故障或失去支持 .-> E
ZooKeeper 的 zxid 将 epoch 和递增计数组合起来标识事务顺序。这能帮助识别历史前缀及缺失更新，但只比较一个最大数字并不能替代完整恢复协议。固定版本的官方内部说明同时解释了 leader activation、原子广播与 quorum 配置。[3]
还要区分协议和对外读接口。ZooKeeper 的写入顺序依赖复制协议，而读取可以由本地服务器提供，可能看到落后的状态；同一客户端的顺序保证不能扩展成“所有客户端每次读都线性一致”。sync、会话顺序和写后读应按 API 文档及实际故障条件分析。[3][6] 不能因为底下用了 ZAB，就把所有上层操作一律标为强一致。
选实现时，审协议之外的那一半
| 需要回答的问题 | 可以要求的证据 |
|---|---|
| 哪些状态先落盘、哪些消息后发送？ | 固定版本的持久化接口说明、崩溃恢复测试 |
| 有哪些故障不会丢已确认数据？ | 明确的磁盘、节点、网络故障模型，而非一句“三副本” |
| 读路径承诺什么？ | 普通读、线性一致读、租约读的不同前提 |
| 客户端重试会怎样？ | 相同请求 ID 重复、不同 payload 同 ID、响应丢失测试 |
| 如何备份、恢复、扩缩容？ | 经演练的快照和成员变更流程 |
| 落后副本如何追赶？ | 日志/快照切换、带宽限制、恢复时间和容量余量 |
自写几十行模型可以帮助理解一条不变量，但生产级共识还要面对磁盘写失败、消息重排、重启、快照、配置变更和应用执行。对于普通 Go 业务，优先使用成熟存储或经过充分验证的库，并把精力放在自己的状态机、幂等及恢复语义上。这个建议假设团队主要交付业务系统；研究协议本身则需要更完整的规范、模型检查和故障测试。
依据与验证范围
- Ongaro、Ousterhout：In Search of an Understandable Consensus Algorithm，扩展版，图 2、图 3、图 8，§5–8：选举、复制、安全性、成员变更、快照、读和客户端重试。
- Lamport：Paxos Made Simple，§2–3：角色、两阶段、值继承与多次共识。
- ZooKeeper 3.9.3 Internals：leader activation、zxid、quorum 与一致性说明。
- etcd/raft v3.6.0 README：实际库的持久化顺序、ReadIndex、租约读和成员变更边界；这里引用固定 tag，不声称它是最新版本。
- Junqueira、Reed、Serafini：Zab: High-performance broadcast for primary-backup systems，§III–V：primary order、discovery/synchronization/broadcast。
- ZooKeeper 原论文，2010，§2：面向客户端的一致性及读取设计。
本次 Go 1.27.2、Linux/amd64 实测：运行、普通测试、race 测试及 vet 均通过。模型枚举 1–9 个投票节点的固定多数集合交集；检查 Raft 的局部投票、日志尾部比较和直接提交条件；错误重启反例直接清空内存投票。模型没有磁盘、网络、完整 Raft 状态机、Paxos/ZAB 执行、成员变更或协议级安全证明。未启动任何真实共识集群，未做吞吐/延迟比较。
完整可复现实验
把以下三个文件放在同一空目录。只依赖标准库，不需要外部服务。
sh
go run .
go test -count=1 -v ./...
go test -race -count=1 ./...
go vet ./...go.mod
mod
module example.com/distributed/consensus
go 1.27.2main.go
代码块 · 71 行 · 点击收起 / 展开
go
package main
import (
"fmt"
"math/bits"
)
func majorityIntersections(n int) (pairs, disjoint int) {
if n < 1 || n > 10 {
panic("bounded model: 1..10 voters")
}
q := n/2 + 1
for a := 1; a < 1<<n; a++ {
if bits.OnesCount(uint(a)) != q {
continue
}
for b := 1; b < 1<<n; b++ {
if bits.OnesCount(uint(b)) != q {
continue
}
pairs++
if a&b == 0 {
disjoint++
}
}
}
return
}
type Tail struct{ Term, Index int }
func upToDate(candidate, voter Tail) bool {
return candidate.Term > voter.Term || candidate.Term == voter.Term && candidate.Index >= voter.Index
}
// Tests only the leader's direct commit predicate, not all Raft safety rules.
func directCommit(entryTerm, currentTerm, replicas, voters int) bool {
return entryTerm == currentTerm && replicas > voters/2
}
type Vote struct {
Term int
Candidate string
}
func (v *Vote) grant(term int, candidate string) bool {
if term < v.Term {
return false
}
if term > v.Term {
v.Term = term
v.Candidate = ""
}
if v.Candidate != "" && v.Candidate != candidate {
return false
}
v.Candidate = candidate
return true
}
func main() {
p, d := majorityIntersections(5)
fmt.Println("5 voters: quorum pairs =", p, "disjoint =", d)
fmt.Println("term 2 entry in term 4, 3/5:", directCommit(2, 4, 3, 5))
fmt.Println("term 4 entry in term 4, 3/5:", directCommit(4, 4, 3, 5))
fmt.Println("longer but older tail:", upToDate(Tail{2, 100}, Tail{3, 10}))
v := Vote{}
fmt.Println("same term A then B:", v.grant(7, "A"), v.grant(7, "B"))
// Incorrect restart: a new zero value models losing the persisted vote.
v = Vote{}
fmt.Println("lost vote after restart, B:", v.grant(7, "B"))
}main_test.go
go
package main
import "testing"
func TestMajorityIntersection(t *testing.T) {
for n := 1; n <= 9; n++ {
_, d := majorityIntersections(n)
if d != 0 {
t.Fatal(n)
}
}
}
func TestRaftPredicates(t *testing.T) {
if directCommit(2, 4, 5, 5) || directCommit(4, 4, 2, 5) || !directCommit(4, 4, 3, 5) {
t.Fatal("commit predicate")
}
if upToDate(Tail{2, 100}, Tail{3, 10}) || !upToDate(Tail{3, 10}, Tail{3, 9}) {
t.Fatal("tail ordering")
}
v := Vote{}
if !v.grant(7, "A") || v.grant(7, "B") || v.grant(6, "A") || !v.grant(8, "B") {
t.Fatal("vote")
}
}