鲁班 - 系统设计大全

21.5 Raft：选主

一句话

Raft 选主是四件套——多数派 + 任期 + 日志至少一样新 + 随机超时：前两个保证一个任期最多一个 leader，第三个保证新 leader 一定包含所有已提交条目，第四个保证它真的能选出来。

三个状态、两个 RPC、一个逻辑时钟

状态 行为 什么时候离开
follower 被动接收心跳与日志；超时未收到心跳 → 变 candidate 收到心跳（重置计时器）/ 超时
candidate term+1、投自己、并发 RequestVote；拿到多数派 → leader 拿到多数派 / 发现更高 term / 超时重选
leader 周期发心跳（空 AppendEntries）、接收写、复制日志 发现更高 term → 退回 follower

任期 term 是逻辑时钟：单调递增、永不回退。它有两个用途——给每次选举编号（一个 term 最多一个 leader），以及让旧 leader 的请求被识别并拒绝（term < currentTerm 一律拒绝）。term 不是时间，不能用来估算超时。

选举流程

follower ──(超时未收到心跳)──▶ candidate: term++，votedFor=self，向所有节点发 RequestVote
   candidate ──(收到多数派赞成)──▶ leader: 立即发心跳，宣誓主权
   candidate ──(收到更高 term)────▶ follower: 退位，更新 term
   candidate ──(选举超时)─────────▶ candidate: term++，重新拉票

        超时                   多数票
follower ─────▶ candidate ─────────▶ leader
    ▲               │                  │
    │   发现更高 term│      发现更高 term│
    └───────────────┴──────────────────┘

RequestVote：四条授予规则，少一条都不安全

投票人检查 规则 少了会怎样
任期 args.term < currentTerm → 拒绝 过期候选人搅乱集群（把旧 term 的票投出去）
本任期是否已投票 votedFor ∈ {null, candidateId}，否则拒绝 同一 term 选出两个 leader（一票投两次）
日志新旧 候选人日志必须"至少一样新"，否则拒绝 日志落后的候选人当选，覆盖已提交条目
term 更大 若 args.term > currentTerm，先更新自己的 term 并转为 follower 拒绝高 term 候选人的同时，自己停留在旧任期，集群无法推进

"至少一样新"的精确比较（先比最后一条的 term，再比长度）：

candidateUpToDate = (candLastTerm > voterLastTerm) ||
                    (candLastTerm == voterLastTerm && candLastIndex >= voterLastIndex)

举例：投票人日志 [1(t1), 2(t2)]，候选人日志 [1(t1), 2(t2), 3(t3)] → 候选人的 lastTerm 3 > 2 → 投赞成。反过来，投票人 [1(t1), 2(t3)]、候选人 [1(t1), 2(t2), 3(t2)] → 候选人 lastTerm 2 < 3 → 拒绝，哪怕它更长。term 优先于长度，这是"日志新旧"最容易被写错的地方。

🔑 这条规则就是选举限制（election restriction）。它把"多数派相交"从"两拨人一定有交集"升级成"交集里的人不会投给落后者"。没有它，Raft 会退化成"谁先超时谁当主"。

随机超时：把"必然分裂"变成"几乎必成"

如果所有 follower 的超时时间相同，它们会同时变成 candidate，各投自己一票 → 没人拿到多数派 → 下一轮重复，理论上可以永远选不出来。随机化就是打破这个对称。

下面这个简化模型模拟 5 节点集群：每轮每个节点有独立超时（固定或随机），在"最早请求到达"之前超时的节点也自称候选，非候选节点把票投给最早到达的拉票请求，拿 3 票者当选；没选出就 term+1 重来（最多 20 轮）。

package main

import (
	"fmt"
	"math/rand"
	"sort"
)

const (
	N    = 5
	T    = 1000.0 // 选举超时基准（ms）
	maxR = 20     // 一轮选不出就重试，最多 20 轮
)

// 一次试验：返回是否选出 leader、用了几轮、耗时（ms）
func trial(rng *rand.Rand, randomized bool, rtt float64) (bool, int, float64) {
	elapsed := 0.0
	for round := 1; round <= maxR; round++ {
		// 1) 各节点的选举定时器
		t := make([]float64, N)
		for i := range t {
			if randomized {
				t[i] = T * (1 + rng.Float64()) // [1000, 2000)
			} else {
				t[i] = T // 所有节点同一时刻超时
			}
		}
		// 2) 最早超时者；在「最早请求能到达」之前超时的节点也自称候选
		tmin := t[0]
		for _, x := range t {
			if x < tmin {
				tmin = x
			}
		}
		dmax := rtt
		cands := []int{}
		for i := range t {
			if t[i] <= tmin+dmax {
				cands = append(cands, i)
			}
		}
		// 3) 候选投自己；其余节点投给最早到达的拉票请求
		votes := make([]int, N)
		for _, c := range cands {
			votes[c]++
		}
		for j := 0; j < N; j++ {
			isCand := false
			for _, c := range cands {
				if c == j {
					isCand = true
				}
			}
			if isCand {
				continue
			}
			best, bestAt := -1, 1e18
			for _, c := range cands {
				at := t[c] + (rtt/2)*(0.5+rng.Float64()) // 单程延迟带抖动
				if at < bestAt {
					best, bestAt = c, at
				}
			}
			if best >= 0 {
				votes[best]++
			}
		}
		// 4) 拿到多数派（3 票）的人当选
		for _, v := range votes {
			if v >= N/2+1 {
				return true, round, elapsed + tmin + rtt
			}
		}
		elapsed += tmin + rtt
	}
	return false, maxR, elapsed
}

func main() {
	scenarios := []struct {
		name       string
		randomized bool
		rtt        float64
	}{
		{"固定超时（都 1000ms）", false, 1},
		{"随机超时 1000–2000ms，RTT=1ms", true, 1},
		{"随机超时 1000–2000ms，RTT=30ms", true, 30},
		{"随机超时 1000–2000ms，RTT=100ms", true, 100},
	}
	const trials = 10000
	fmt.Println("| 场景 | 首轮选出 leader | 平均轮数 | 选举耗时 P50 | 选举耗时 P99 |")
	fmt.Println("|---|---|---|---|---|")
	for _, s := range scenarios {
		rng := rand.New(rand.NewSource(42))
		first, rounds := 0, 0
		var times []float64
		for i := 0; i < trials; i++ {
			ok, r, el := trial(rng, s.randomized, s.rtt)
			if ok && r == 1 {
				first++
			}
			rounds += r
			times = append(times, el)
		}
		sort.Float64s(times)
		fmt.Printf("| %s | %.1f%% | %.2f | %.0fms | %.0fms |\n",
			s.name, float64(first)/trials*100, float64(rounds)/trials,
			times[trials/2], times[int(float64(trials)*0.99)])
	}
}

输出（本机实测）：

| 场景 | 首轮选出 leader | 平均轮数 | 选举耗时 P50 | 选举耗时 P99 |
|---|---|---|---|---|
| 固定超时（都 1000ms） | 0.0% | 20.00 | 20020ms | 20020ms |
| 随机超时 1000–2000ms，RTT=1ms | 100.0% | 1.00 | 1129ms | 1600ms |
| 随机超时 1000–2000ms，RTT=30ms | 99.8% | 1.00 | 1158ms | 1658ms |
| 随机超时 1000–2000ms，RTT=100ms | 97.7% | 1.02 | 1232ms | 2646ms |

四个读法：

  1. 固定超时 = 必然分裂：5 个节点同时成为候选，每人 1 票，20 轮都选不出来。这就是"为什么必须随机"。
  2. 随机化之后首轮成功率接近 100%：超时窗口 [T, 2T] 里最小值唯一，别的节点还没醒。
  3. RTT 相对超时越大，撞车概率越高：RTT=100ms 时 2.3% 的试验要第二轮（P99 从 1.6s 涨到 2.6s）。经验规则：选举超时 ≈ 10 × RTT 以上，且至少比心跳间隔大一个量级（论文建议 150–300ms，etcd 默认心跳 100ms、选举超时 1000ms，具体以版本配置为准）。
  4. P50 约 1.1s 而不是 1.0s：5 个 U[1000,2000] 的最小值中位数是 1000 + 1000×(1−0.5^(1/5)) ≈ 1129ms，实测 P50 正好 1129ms；最小值期望是 1000 + 1000/6 ≈ 1167ms。这解释了"故障切换要 1 秒左右"的量级感。

选举耗时与故障切换时间

组成 量级 说明
检测 leader 失联 ≈ 选举超时 T follower 等不到心跳才动
拉票（RequestVote） 1 RTT 多数派并行返回
宣誓与恢复可用 1 RTT 新 leader 提交一条当前任期条目（no-op）后才能确定 commitIndex，读才能线性一致
合计 T + 2 RTT 同城 1ms RTT ≈ T+2ms；跨城 30ms RTT ≈ T+60ms

⚠️ 常见误解：以为"选出来就能读"。新 leader 的 commitIndex 可能落后（它不知道自己已提交到哪），必须先提交一条当前任期的条目，才能安全地响应读（机制见 21.6 Raft：日志复制，读路径的三种做法见 21.12 共识算法对比）。

任期膨胀：一个被隔离的节点如何打断整个集群

场景：节点 E 因网络分区被隔离，它不断超时、不断 term++ 去竞选。分区恢复后，E 带着 term = 10086 发 RequestVote，健康 leader（term 5）收到后必须退位并更新 term —— 集群白丢一次 leader，重选一次，业务出现一次 1 秒级的写停顿。

两个工业解法：

机制 做什么 代价
PreVote（预投票） 竞选前先问"如果我竞选，你们会投我吗"，不先加 term；拿不到多数派就不加 term、不打扰集群 多 1 RTT；需要全集群支持
CheckQuorum leader 周期性确认自己还能联系到多数派，联系不上就主动退位，避免"僵尸 leader" 网络抖动时可能误退位

两者通常一起开（etcd 的 --pre-vote、--check-quorum）。没有它们，一个反复重启/网络抖动的节点就能让集群持续选主——可用性问题被伪装成"共识不稳"。

反模式

反模式 后果
所有节点用同一个选举超时 必然分裂票，永远选不出 leader
选举超时接近 RTT（如 RTT 30ms、超时 50ms） 心跳与拉票互相打断，反复选举
心跳间隔 ≥ 选举超时 follower 频繁超时，集群持续处于选举中
投票给日志更旧的候选人（比较写错：先比长度） 破坏选举限制，已提交条目可能被覆盖
把 term 当时间用（"term 差 3 就是过了 3 秒"） 逻辑错误：term 只在选举时递增
不持久化 currentTerm / votedFor 重启后在同一 term 投两次票 → 一个任期两个 leader
不区分"收到请求"与"已提交" 客户端以为写成功，实际还没提交
有 PreVote 却不配 CheckQuorum（或反之） 前者防打扰、后者防僵尸，缺一个都留一类故障

自检

Q1 为什么"随机选举超时"是正确性之外的必需品？固定超时到底会怎样？

▸ 答案：固定超时会让所有 follower 同时超时、同时变 candidate、各投自己一票，没有任何人能拿到多数派；下一轮重复同样的对称，理论上可以永远选不出 leader（实测 20 轮全失败）。随机化把"同时"打散成"有唯一最早者"，首轮成功率接近 100%。注意它是活性手段，不改变安全性。

Q2 候选人日志 [1(t1), 2(t2), 3(t2)]，投票人日志 [1(t1), 2(t3)]。投票人该投赞成吗？为什么？

▸ 答案：不该。比较先看最后一条的 term：候选人 2 < 投票人 3，所以候选人"更旧"，即使它更长（3 条 vs 2 条）。规则是"lastTerm 大者更新；lastTerm 相同才比 lastIndex"。写反成"先比长度"会让日志落后但更长的候选人当选，直接破坏选举限制。

Q3 一个被隔离 10 分钟的节点回来后，为什么会触发一次不必要的选举？怎么避免？

▸ 答案：它隔离期间不断超时并 term++，回来时带着远高于集群的 term。其他节点收到 RequestVote 看到更高 term，必须先更新自己的 term 并转为 follower，健康 leader 因此退位，集群重选。避免方式：PreVote（拉票前不加 term，先试探能否拿到多数派）+ CheckQuorum（leader 确认自己仍有多数派支持，否则主动退位）。

Q4 3 节点集群，leader 挂掉后客户端感知的写停顿大约是多少？由哪几段组成？

▸ 答案：约 T + 2 RTT（T 是选举超时）。① 检测：follower 等到超时才发起选举（≈T）；② 拉票：一次 RTT；③ 新 leader 提交当前任期条目（no-op）后才能确定 commitIndex，又一次 RTT。同城（RTT 1ms、T 1s）约 1 秒；跨城（RTT 30ms）约 1.06 秒。把 T 调小能加快切换，但会增加误触发选举的概率（GC/网络抖动就会被当成 leader 挂了）。

Q5 "选出了 leader"就等于"可以安全地读"了吗？

▸ 答案：不等于。新 leader 的 commitIndex 可能落后于已提交位置（它只知道"我有这些日志"，不知道"哪些已被多数派确认"），必须先提交一条当前任期的条目，才能通过多数派反推出旧的提交位置（这条规则的证明见 21.7 Raft：安全性证明）。在此之前，线性一致读需要 ReadIndex（一次多数派往返）或等 no-op 提交完成。

关联