00 · 设计推演：从零造一个共识算法

“Raft 的每一条规则，都是被某个具体失败逼出来的。这一节我们把那些失败重演一遍。“

---

开场：我要你自己把 Raft 推出来

老陈：需求：三台机器存同一份数据。客户端写入 x=1，要保证三台最终一致，且机器挂了数据不能错。

现在不许说”用 Raft”。你来设计。

小林：写三遍？

老陈：好。v0 就这么写。然后我问你：如果其中一台网络不通呢？

---

v0：写三遍

func (c *Cluster) Set(k, v string) error {
	// 依次写三台
	for _, node := range c.nodes {
		if err := node.Set(k, v); err != nil {
			return err   // ★ 一台失败就返回错误
		}
	}
	return nil
}

能工作（三台都活着的时候）。

失败：

#	问题	后果
1	一台挂了，整个集群不可写	可用性 = 三台全活的概率
2	部分写入	第一台写成功、第二台失败 → 数据不一致
3	顺序不保证	并发写入时，三台可能以不同顺序应用

老陈：问题 1 是关键。三台机器，任何一台挂就不可用——那你用三台图什么？

小林：……为了可靠？

老陈：但现在更不可靠了。三台机器，故障率是单机的三倍。

小林：那……不等所有机器，等一部分就行？

老陈：好想法。等几台？

---

v1：多数派（Quorum）

改动：不等所有节点，等多数派确认就返回。

func (c *Cluster) Set(k, v string) error {
	acks := 1   // 自己
	errCh := make(chan error, len(c.nodes)-1)
 
	for _, node := range c.others {
		go func(n *Node) {
			errCh <- n.Set(k, v)
		}(node)
	}
 
	needed := len(c.nodes)/2 + 1   // 3 台需要 2 台，5 台需要 3 台
	for i := 0; i < len(c.nodes)-1; i++ {
		if err := <-errCh; err == nil {
			acks++
			if acks >= needed {
				return nil   // ★ 多数派达成，返回成功
			}
		}
	}
	return errors.New("多数派未达成")
}

改进：

• 3 台集群可以容忍 1 台故障
• 5 台可以容忍 2 台

★ 为什么是”多数派”而不是”一半”？

关键性质：任意两个多数派，必然有交集

  3 台集群，多数派 = 2
  {1,2} ∩ {2,3} = {2}   ✓ 有交集
  {1,2} ∩ {3,?} = 不可能（{3} 只有一个，不是多数派）

★ 这个交集是后续所有正确性的基础
  （抽屉原理：两个大小都 > n/2 的集合，必然相交）

但仍然有致命问题：

#	问题	场景
1	顺序还是乱的	A 写 x=1，B 写 x=2，不同节点可能以不同顺序应用
2	部分成功的状态	只有 2 台写成功，第 3 台是旧值。读的时候读到哪台？
3	重试导致重复	客户端超时重试，写两次

老陈：问题 1 是核心。并发写入没有全局顺序，就根本谈不上”一致”。

小林：那就加个顺序？给每个写操作编号？

老陈：谁来编号？

小林：……某个固定的节点？

老陈：好。这就是 leader 的由来。继续想：这个节点挂了怎么办？

---

v2：引入 Leader + 日志

改动：

1. 选出一个 leader，所有写请求都走它
2. Leader 给每个操作分配单调递增的序号
3. 用日志（有序的操作序列）而不是直接改数据

type LogEntry struct {
	Index   int      // 单调递增
	Command Command
}
 
type Node struct {
	log       []LogEntry   // ★ 日志，而不是直接的状态
	commitIdx int          // 已提交的日志位置
	state     map[string]string  // 状态机（日志应用后的结果）
}
 
// Leader 处理写请求
func (n *Node) handleSet(cmd Command) error {
	// 1. 追加到本地日志
	n.log = append(n.log, LogEntry{Index: len(n.log), Command: cmd})
 
	// 2. 复制给所有 follower
	// 3. 多数派确认后，commitIdx++
	// 4. 应用到状态机
	return nil
}

★ 为什么用日志而不是直接改数据？这是关键设计。

直接改数据:
  副本 A: x=1 → x=2 → x=3
  副本 B: x=1 → x=3          （漏了 x=2）
  怎么发现 B 漏了？怎么补？很难

用日志:
  副本 A: [set x=1][set x=2][set x=3]
  副本 B: [set x=1][set x=3]           ← 一眼看出 index 1 不一致！
  ★ 日志让"不一致"变得可检测、可修复

老陈：记住这个洞察：日志把”状态一致”这个难题，转化成了”序列一致”这个简单问题。

而”序列一致”是可以靠”前缀比较 + 覆盖”解决的。

同样的思路出现在：

• 数据库的 WAL（redo log）
• 分布式系统的复制日志
• Kafka 的分区日志
• 区块链的链

“用有序日志代替无序状态”是分布式系统最重要的一个技巧。

新问题：

#	问题	场景
1	Leader 挂了怎么办？	没有 leader 就不能写
2	可能有两个 leader	网络分区 → 两边各选一个 → 脑裂
3	怎么知道谁的数据更新？	新 leader 可能缺日志

---

v3：Leader 选举 + Term

改动：

1. Follower 超时收不到心跳 → 发起选举
2. 引入 Term（任期） 作为逻辑时钟

type Node struct {
	currentTerm int    // ★ 逻辑时钟
	votedFor    int    // 本 term 投给了谁
	role        Role
	lastHeartbeat time.Time
}
 
func (n *Node) electionLoop() {
	for {
		if n.role != Leader && time.Since(n.lastHeartbeat) > n.electionTimeout {
			n.startElection()
		}
		time.Sleep(10 * time.Millisecond)
	}
}
 
func (n *Node) startElection() {
	n.currentTerm++        // ★ term 递增
	n.role = Candidate
	n.votedFor = n.id      // 投给自己
 
	// 向所有节点请求投票
	votes := 1
	for _, peer := range n.peers {
		if peer.RequestVote(n.currentTerm, n.id) {
			votes++
		}
	}
 
	if votes > len(n.peers)/2 {
		n.role = Leader
	}
}

★ Term 解决了”过期 leader”问题：

场景:
  Leader A (term 2) 被网络隔离
  剩下的节点选出 Leader B (term 3)
  A 恢复，还以为自己是 leader

  A 发送 AppendEntries(term=2)
  其他节点: 你的 term 比我小 → 拒绝！顺便告诉你现在是 term 3
  A: 收到更大 term → 立即变成 follower  ★

★ Term 就是"谁的话更可信"的判据
  它不需要真实时钟（分布式系统里时钟不可靠）

新问题：

#	问题	场景
1	分裂投票（Split Vote）	多个 candidate 同时选举，没人拿到多数
2	新 leader 可能缺日志	上例中的 B 可能没收到 A 的某些日志

问题 1 的解法：随机超时

如果所有节点超时时间一样:
  同时变成 candidate → 同时投票 → 可能每人一票 → 选举失败
  再同时超时 → 再失败 → 活锁

★ 随机化 (150-300ms):
  某个节点先超时 → 有先发优势 → 大概率拿到多数票

老陈：这是分布式系统里最简单的”打破对称性”技巧。

同类的还有：

• 以太网 CSMA/CD 的二进制指数退避
• Redis 集群的随机重试
• ZooKeeper 的随机选举超时

当多个节点行为完全相同时，引入随机性是打破僵局最便宜的办法。

---

v4：投票限制——只给”日志够新”的候选人投票

问题 2（新 leader 可能缺日志）是安全性问题，最严重。

先看一个具体失败：

3 个节点: A(leader), B, C

1. A 收到 set x=1，追加日志 [x=1]
2. A 复制给 B，B 写入
   A: [x=1]  B: [x=1]  C: []      ← 多数派已达成，A 提交
3. A 崩溃
4. ★ C 发起选举（term 2），C 的日志是空的！
   如果 B 和 C 都投票给 C，C 成为 leader
5. C 的日志里没有 x=1
   → ★ 已提交的 x=1 丢失了！

这就是”已提交的日志被覆盖”——共识算法最严重的安全违规。

解法：投票时检查候选人的日志新旧。

func (n *Node) RequestVote(candidateTerm int, candidateID int,
		candLastLogIdx, candLastLogTerm int) bool {
 
	// ... term 检查 ...
 
	// ★ 关键：日志新旧比较
	myLastIdx := len(n.log) - 1
	myLastTerm := n.log[myLastIdx].Term
 
	if candLastLogTerm < myLastTerm {
		return false   // 候选人的最后一条日志 term 更小 → 更旧
	}
	if candLastLogTerm == myLastTerm && candLastLogIdx < myLastIdx {
		return false   // term 相同但更短 → 更旧
	}
	return true
}

★ 为什么这样就能保证安全？（这是本节最重要的证明）

要证明：选出的 leader 一定包含所有已提交的日志

证明：
  ① 一条日志"已提交" = 它被多数派复制了
  ② 候选人要当选 = 必须获得多数派的投票
  ③ ★ 这两个"多数派"必然有交集（抽屉原理）
  ④ 交集里至少有一个节点，它的日志"至少跟候选人一样新"
     （否则它不会投票）
  ⑤ 那个节点有这条已提交的日志（因为它在第一个多数派里）
  ⑥ 所以候选人也有（因为"至少一样新"意味着要么有，要么更新的日志里包含了它）

  ∎ 证毕

老陈：这个证明的核心是”两个多数派必然相交”。

整个 Raft 的安全性都建立在这一个数学事实上。

记住：当你在分布式系统里看到”多数派”，第一个该想到的就是”两个多数派相交”。

---

v5：日志复制的一致性检查

现在 leader 是安全的了。但 follower 的日志可能跟 leader 不一致（崩溃、丢消息）。

怎么修复？

第一想法：leader 把自己的日志整个发过去。

问题: 日志可能很大（GB 级），每次都发不现实

第二想法：只发缺的部分。但 leader 怎么知道缺哪部分？

Raft 的解法：一致性检查（Consistency Check）

type AppendEntriesArgs struct {
	Term         int
	PrevLogIndex int     // ★ 新日志的前一条的索引
	PrevLogTerm  int     // ★ 新日志的前一条的 term
	Entries      []LogEntry
	LeaderCommit int
}
 
func (n *Node) AppendEntries(args *AppendEntriesArgs) bool {
	// ★ 检查：我的日志在 PrevLogIndex 处的 term，是不是 PrevLogTerm？
	if args.PrevLogIndex >= len(n.log) ||
		n.log[args.PrevLogIndex].Term != args.PrevLogTerm {
		return false   // 不匹配，拒绝
	}
	// 匹配 → 追加新日志（覆盖冲突的）
	// ...
	return true
}
 
// Leader 侧：被拒绝就回退，重试
func (n *Leader) replicateTo(peer int) {
	for {
		prevIdx := n.nextIndex[peer] - 1
		args := buildArgs(prevIdx, ...)
 
		if peer.AppendEntries(args) {
			break   // 成功
		}
		n.nextIndex[peer]--   // ★ 回退一格，再试
	}
}

★ 为什么这样能保证一致？（日志匹配特性）

归纳证明：
  初始: 所有日志为空 → 满足
  
  归纳: 假设 AppendEntries 成功时，
        follower 在 PrevLogIndex 及之前与 leader 完全一致
        
        成功意味着：follower 的 log[PrevLogIndex].Term == 领导者的
        → 两边在这一点"对齐"了
        → 追加的新日志也相同
        → 删除冲突的旧日志后，仍然相同
        
  ★ 结论（日志匹配特性）：
    如果两个日志在相同 index 处的 term 相同，那么：
      ① 内容相同
      ② 之前的所有日志也都相同

老陈：注意这个设计的巧妙之处：

它用”前一个日志的 (index, term)“做锚点，而不是用”日志内容的哈希”或”完整比对”。

好处：

• 通信量 O(1)（只发两个数字）
• 能定位不一致的位置（逐步回退）
• 顺便保证了”term 相同 → 内容相同”

这是一个”用最少的校验信息达到最强保证”的设计。

---

v6：提交条件——最容易写错的地方

现在到了最微妙的一步。

朴素想法：日志被多数派复制 → 提交。

// ❌ 这是错的
func (n *Leader) updateCommitIndex() {
	for i := n.commitIndex + 1; i < len(n.log); i++ {
		if n.countReplicas(i) > len(n.peers)/2 {
			n.commitIndex = i     // 被多数派复制了 → 提交
		}
	}
}

★ 这个”看起来对”的代码，会导致已提交的日志被覆盖。

让我把失败场景走一遍（5 个节点）：

── 阶段 1: term 2, S1 是 leader ──
S1 复制 [idx=2, term=2] 给 S2
  S1: [1(t1), 2(t2)]
  S2: [1(t1), 2(t2)]
  S3: [1(t1)]   S4: [1(t1)]   S5: [1(t1)]
★ 只有 2 个节点有，未达多数派（需要 3 个），所以未提交
S1 崩溃

── 阶段 2: term 3, S5 成为 leader ──
（S5 的日志 [1(t1)]，S3/S4 也一样，S5 能拿到票）
S5 写入 [idx=2, term=3]  ← ★ 注意：S5 在 idx=2 的位置写了自己的东西
S5 崩溃

── 阶段 3: term 4, S1 重启成为 leader ──
S1 继续复制 [idx=2, term=2] 给 S3、S4
  S1: [1, 2(t2)]
  S2: [1, 2(t2)]
  S3: [1, 2(t2)]   ← ★ 现在 idx=2 有 3 个节点了！达到多数派
  S4: [1]
  S5: [1, 2(t3)]

★★ 关键问题：S1 现在能提交 idx=2 吗？

如果按"朴素做法"：能（3 个节点有）。提交，应用，返回客户端。

── 阶段 4: term 5 ──
S1 崩溃
S5 成为 leader（它的日志 [1, 2(t3)]，term 3 > term 2，比 S2/S3/S4 新！）
S5 复制自己的 idx=2 给所有节点
→ ★★ idx=2 (term=2) 被覆盖了！
   但它已经被 S1 提交并告诉客户端"成功了"！

★★ 这是灾难：已提交的数据丢失。

正确的做法：只能提交当前 term 的日志。

// ✅ 正确
func (n *Leader) updateCommitIndex() {
	for i := len(n.log) - 1; i > n.commitIndex; i-- {
		// ★ 只统计当前 term 的日志
		if n.log[i].Term != n.currentTerm {
			continue
		}
		if n.countReplicas(i) > len(n.peers)/2 {
			n.commitIndex = i
			break   // 提交 i 的同时，i 之前的所有日志被间接提交
		}
	}
}

★ 为什么这样就安全？

回到阶段 3:
  S1 (term 4) 复制 idx=2 (term=2) 给 S3
  ★ S1 不能提交 idx=2，因为 term=2 ≠ 当前 term=4

  S1 必须写入一条新的、term=4 的日志
  等它被多数派复制后提交 → 这时才间接提交 idx=2

如果 S1 在写完 term=4 的日志前就崩溃:
  → idx=2 从未提交
  → 后续 leader 覆盖它是安全的（它没提交过）
  ★ 安全！

老陈：这个反例的精髓，一句话：

“被多数派复制过” ≠ “已提交”。

一条日志可能被多数派复制，但在它”锁定”之前，仍可能被覆盖。 只有当你提交了当前 term 的一条日志，它之前的所有日志才被锁定。

这是 Raft 实现里最常见的 bug。 我见过太多人写错这里，而且测试还过不了——因为这个 bug 只在特定的崩溃时序下才暴露。

---

v7：完整的 Raft

把上面所有改动合起来：

① 状态机:     Follower / Candidate / Leader
② 逻辑时钟:   Term（解决过期 leader）
③ 选举:       随机超时 + 多数派投票 + 日志新旧检查
④ 日志:       有序序列（把"状态一致"转成"序列一致"）
⑤ 复制:       一致性检查（prevLogIndex/prevLogTerm）+ 回退重试
⑥ 提交:       ★ 只能提交当前 term 的日志（间接提交之前的）
⑦ 持久化:     currentTerm / votedFor / log 必须落盘

每一条都对应前面的一次失败：

机制	解决了哪个失败
多数派	v0: 一台挂就不可用
日志	v1: 顺序乱、不一致难检测
Leader	v1: 谁来定顺序
Term	v2: 脑裂、过期 leader
随机超时	v3: 分裂投票
投票日志检查	★ v3: 新 leader 缺日志 → 已提交数据丢失
一致性检查	v5: follower 日志不一致怎么修复
只提交当前 term	★ v6: 已提交日志被覆盖

---

★ 这一节真正的收获

不是”Raft 有这些规则”，而是这条推导链：

需求: 多副本数据一致，且故障时不能错
  │
  ├─ v0 写三遍
  │    失败: 一台挂就不可用；部分写入；顺序乱
  ↓
  ├─ v1 多数派                    ← 关键: 两个多数派必相交
  │    失败: 顺序仍乱；部分成功状态
  ↓
  ├─ v2 Leader + 日志             ← 关键: 日志把"状态一致"转成"序列一致"
  │    失败: Leader 挂了怎么办；脑裂
  ↓
  ├─ v3 Term + 随机超时选举
  │    失败: ★ 新 leader 可能缺日志 → 已提交数据丢失
  ↓
  ├─ v4 投票时检查日志新旧         ← 用"多数派相交"证明安全
  │    剩下: follower 日志不一致怎么修
  ↓
  ├─ v5 一致性检查（prevLog 锚点）
  │    剩下: 提交条件是什么
  ↓
  └─ v6 只能提交当前 term 的日志    ← 最微妙的一步
       完成

四个可以迁移的思维模式

① 把”状态一致”转化为”序列一致”

这是 v2 的核心洞察。同样出现在：WAL、Kafka 分区、区块链、事件溯源（Event Sourcing）。

② 多数派的价值在于”两个多数派必相交”

所有 quorum 系统的正确性都源于这个数学事实。看到”多数派”，先想”相交”。

③ 打破对称性用随机

多个节点行为相同时，随机化是最便宜的破局手段（v3）。

④ “看起来对”和”真的对”之间有条鸿沟

v6 的朴素提交逻辑，在绝大多数情况下都能正常工作，只在一个特定的崩溃时序下出错。

这是分布式系统最难的地方： 你的代码可能跑了一百万次都对，第一百万零一次错。

所以分布式算法必须靠证明，不能靠测试。 当你设计一个分布式协议时，问自己：“我能证明它是对的吗？” 如果只能说”我测过没问题”，那还不够。

---

现在，轮到你了

练习：我们上面的推导，都假设”节点会崩溃但不会撒谎”（崩溃容错，CFT）。

如果节点可能撒谎呢？（拜占庭容错，BFT）

v0: 上面的 Raft
     失败: ???

v1: ???

提示（不要用，先自己想）：

• Leader 发送矛盾的日志给不同的 follower，怎么发现？
• 投票时，一个节点给两个候选人都投票，怎么办？
• 需要几个节点才能容忍 1 个叛徒？3 个够吗？
• 为什么比特币需要”工作量证明”？它在解决什么问题？

老陈：答案是：容忍 f 个拜占庭节点，至少需要 3f+1 个节点。

为什么是 3f+1 而不是 2f+1？ 这是另一个推导链，留给你。

提示：在拜占庭场景下，“多数派相交”不够了——因为相交的那个节点可能在撒谎。

---

下一节

01 · 网络编程：从 Socket 到 epoll

然后：02 · 分布式共识：Raft 完整实现——这一节我们讲了”为什么”，那一节讲”怎么做”，并给出完整可运行的 Go 实现。

带着这个问题去读实现：对照本节 v0-v6 的每一次失败，找到代码里对应的那几行。 找不到对应关系，说明你还没真正理解。