5.2 选举限制:日志新旧比较
5.1 节把「谁能竞选、怎么拿到多数票」讲清楚了,但还留着一个悬案:选举协议只要求多数派认可,而多数派认可并不等于它带来的日志是正确的。如果让一个日志残缺的节点当选,它可以用自己的旧日志覆盖集群已经提交的条目——这不是理论上的极端情况,而是 etcd 生产事故里「换主后数据回退」的标准成因。
本节补上选举限制(Election Restriction):投票者只投给日志不落后于自己的候选。它不改变选举流程,只在投票端加一条日志比较规则,却承担了整个状态机安全证明的起点。为了让后面的例子可复算,先固定两套数字:3 节点集群 quorum = 2,5 节点集群 quorum = 3;日志条目统一记作 (term, index)。
为什么需要选举限制
先完整推演一遍「没有选举限制」的事故链。3 节点 etcd 集群:
| 节点 | 任期 | 最后一条日志 | 状态 |
|---|---|---|---|
| A | 2 | (2, 5) | 在多数派,正常 |
| B | 2 | (2, 5) | 在多数派,正常 |
| C | 1 | (1, 3) | 曾离线,重放 wal 后停在旧点 |
A、B 组成的多数派已经提交了 index ≤ 5 的日志。此时 C 网络恢复并发起竞选,C 的 term 递增到 2。事故链分五步:
- C 广播 RequestVote(term=2, lastLog=(1,3))。
- A、B 收到请求:C 的 term 2 高于本地。若没有日志检查,A、B 按任期对齐把自己降为 Follower 并把票投给 C。
- C 拿到 A、B 的两票,凑齐 quorum=2 当选。
- C 作为 leader 广播自己的日志前缀(到 index 3),A、B 用日志匹配规则删除 index 4、5 的冲突条目。
- 客户端已确认写入的 index 5 数据消失,状态机安全被破坏。
第 2 步就是唯一的拦截点:A、B 各自持 (2,5),C 持 (1,3),日志比较发现 C 的日志旧于自己,拒绝。C 最多只能拿到自己的 1 票,永远凑不齐 quorum,事故链在第 3 步之前被剪断。
这里有一个值得强调的区分:C 的竞选请求是合法的,A 投它也不违反任何协议条款,但组合结果违背了安全。 Raft 的解法不是禁止落后节点发起竞选(那会让节点永远无法通过选举自愈),而是让投票者用日志新旧把「多数认可」收紧为「多数中日志不落后的认可」。合规但危险的路径在投票端被剪断——这是 Raft 设计里「把安全检查放在节点本地决策」的典型风格,后面 5.3 节的 pre-vote 也是同一个风格。
日志新旧比较规则
比较只看候选日志的最后一条,规则只有两句话:
- 先比较最后一条的 term,term 大者新;
- term 相同再比较 index,index 大者新。
设候选携带 (candidateTerm, candidateIndex),投票者自己最后一条是 (myTerm, myIndex),完整判定表:
| 条件 | 判定 | 投票结果 |
|---|---|---|
| candidateTerm > myTerm | 候选日志更新 | 同意 |
| candidateTerm < myTerm | 候选日志更旧 | 拒绝 |
| candidateTerm == myTerm 且 candidateIndex >= myIndex | 一样新 | 同意 |
| candidateTerm == myTerm 且 candidateIndex < myIndex | 候选日志更旧 | 拒绝 |
注意 term 相等时 index 用的是 >=:Raft 允许「一样新」的候选当选,不要求严格更新。两个日志同样新的节点之间不存在覆盖已提交条目的风险——它们最多差几条未提交的尾巴,所以这个放宽是安全的。
可复算的例子:投票者 V 最后一条 (1, 5):
| 候选 | 携带元数据 | 逐条比较 | 结果 |
|---|---|---|---|
| C1 | (1, 5) | term 同、5 ≥ 5 | 同意 |
| C2 | (1, 4) | term 同、4 < 5 | 拒绝 |
| C3 | (2, 2) | 2 > 1 | 同意 |
| C4 | (0, 9) | 0 < 1 | 拒绝 |
C4 最容易看错:index 9 明明很大,但它的 term 0 说明整条日志都属于一个极老的任期,哪怕曾经很长,也是旧日志。term 的优先级高于 index,因为 term 反映节点「最近是否真正参与过共识」,比日志长度更有信息量;一个 term 0 的长日志,很可能只是某个远古 leader 留下的、从未被后续共识覆盖的历史。
为什么只看最后一条就够了?因为 Raft 日志按 term 分段组织,最后一条 term 较大的节点经历过较新的任期,其日志更可能包含已提交条目;term 相同的情况下,index 直接决定谁的前缀更长。论文把这套规则表述为 lastLogTerm 优先、lastLogIndex 次之——这是「决定日志新旧的最小充分信息」,多比较整条日志既不必要也不可靠,因为你根本不知道对方的完整日志。
投票者的完整决策:任期检查与日志检查
投票决策分两步,两步的顺序不能换。k8s-etcd-lab 里 handle 处理 MsgRequestVote 的真实逻辑:
case MsgRequestVote:
to := s.Nodes[m.To]
// 第一步:任期检查。候选 term 更高 → 先降级、清空投票记录(任期对齐)。
if m.Term > to.Term {
to.Term = m.Term
to.Role = Follower
to.VotedFor = -1
}
// 第二步:日志检查。任期不低于、本任期未投他人,且日志不落后 → 投。
granted := false
if m.Term >= to.Term && (to.VotedFor == -1 || to.VotedFor == m.From) {
if to.logUpToDate(m.LastLogTerm, m.LastLogIndex) {
to.VotedFor = m.From
granted = true
}
}
两步的职责不同:
| 步骤 | 检查什么 | 决定什么 | 不通过时的行为 |
|---|---|---|---|
| 任期检查 | 候选 term 是否 >= 本地 term | 这个请求「有没有资格被考虑」 | 更高 term 覆盖本地状态并降级;更低 term 直接忽略 |
| 日志检查 | 候选日志是否不落后于本地 | 考虑之后「投不投赞成票」 | 拒绝,但任期状态已更新(对齐仍然发生) |
一个反直觉的点:即使候选 term 更高,日志旧依然拒绝。 任期对齐(把角色、票权交给更高 term)是「尊重事实」,日志新旧是「安全检查」,两者正交。所以一个重启回来的旧节点即便把 term 抬得再高,也只会让所有节点更新自己的 term,却拿不到任何一张票——这正是 5.3 节 pre-vote 要优化的痛点(无意义地涨 term)。
lab 里这条规则就是 Node.logUpToDate,连同两个辅助函数一共十几行:
func (n *Node) lastLogTerm() int {
if len(n.Log) == 0 {
return 0
}
return n.Log[len(n.Log)-1].Term
}
func (n *Node) lastLogIndex() int { return len(n.Log) - 1 }
func (n *Node) logUpToDate(term, index int) bool {
myTerm, myIndex := n.lastLogTerm(), n.lastLogIndex()
if term != myTerm {
return term > myTerm
}
return index >= myIndex
}
空日志的约定要记住:lastLogTerm 返回 0,lastLogIndex 对空日志是 -1(len(Log)-1)。这保证「空日志的节点只投给同样空或更新的候选」,不会因为 index 取 0 而误以为自己的空日志比别人的日志长。
安全证明一:多数派交集
现在证明「只投给不落后的候选」为什么能保证已提交条目不丢。第一步是多数派交集(quorum intersection):任意两个多数派必有公共节点。
5 节点多数 = 3,两个多数派各 3 人,3 + 3 = 6 > 5,交集至少 1 个;3 节点多数 = 2,2 + 2 = 4 > 3,交集至少 1 个。一般地,多数大小 > n/2,两倍多数 > n,交集非空。这个事实是所有基于 quorum 的安全证明(Raft、Paxos、quorum 读写的线性一致)的公共地基。
用可复算的 5 节点例子:多数派 M1 = {0, 1, 2},多数派 M2 = {2, 3, 4},交集 = {2}。无论分区怎么变,交集节点都「同时参与了两次多数确认」,它是两派共识唯一的共同见证者。
安全证明二:当选 leader 必含所有已提交条目
设某条目 e(index i)已提交,那么它被复制到了某个多数派 M(提交的定义:复制到多数派并确认)。现任 leader L 的选票来自多数派 V(所有投票给 L 的节点)。由多数派交集,M ∩ V 至少有一个节点 X。
X 有两个属性:
- X 持有一致前缀到 i(它在 M 里,包含已提交条目 e 及其之前全部日志);
- X 投给了 L(它在 V 里)。而 X 投票的条件是
logUpToDate通过——L 的日志不落后于 X,即 L 的最后一条不早于 X 的最后一条。
因此 L 的最后一条日志 index ≥ X 的最后一条 ≥ i。再补一个 Raft 的日志匹配性质(复制阶段:Follower 与 leader 冲突的条目被删除、一致前缀被保留,提交时一致前缀已确认),可推出 L 在 i 处的条目与 e 一致,于是 L 包含 e。把 e 推广到所有已提交条目:
当选 leader 必然包含全部已提交条目。 这就是「选举限制 ⇒ 状态机安全(State Machine Safety)」的完整链条。注意这条证明没有依赖「多数派都是诚实的」,只依赖多数派交集与投票条件,所以它对任意不超过 f 个的故障组合都成立。
领导者完整性:任期内只增不减
把上面的结论推广到所有 term,就是 Raft 的领导者完整性(Leader Completeness):每一条已提交的日志,都会存在于之后每一个 term 的 leader 日志中。 归纳证明三句话:
- 第 1 个 term 的 leader 当选时已含全部已提交条目(上面的安全证明二)。
- 假设第 T term 的 leader 含所有 term ≤ T 的已提交条目;它在任期内只追加、不删除自己的日志。
- 若第 T term 内提交了新条目,第 T+1 term 的 leader 由证明二包含全部已提交条目(含 T 内提交的),归纳成立。
「leader 任期内日志只增不减」来自 Raft 的一个不对称设计:冲突删除只发生在 Follower 侧,leader 的日志从不被回退。 新 leader 对落后节点逐个下发缺失段,Follower 永远向 leader 看齐,绝无反向覆盖 leader 的可能——因为 leader 已经被证明「不可能缺已提交条目」,它是标准答案。
| 角色 | 日志操作 | 方向 |
|---|---|---|
| Leader | 只 append、只广播 | 日志是标准答案 |
| Follower | append + 冲突删除 + 追赶 | 永远向 leader 看齐 |
工程含义很清楚:一旦日志被多数派确认(提交),它就在后续所有 leader 的日志里,复制过程可以放心地把「追日志」当成纯单向操作。这就是「多数确认是唯一提交条件」能成立的后盾。
K8s/etcd 场景:旧日志节点重启与磁盘落后
etcd 的持久化靠 wal(write-ahead log):每条日志先写 wal 并 fsync,才会在复制协议中对外确认。一个节点日志落后有几种常见来源:
| 场景 | 落后原因 | 典型落后量 | 选举限制的作用 |
|---|---|---|---|
| 节点重启 | 崩溃前最后几条未 fsync,重启重放 wal 停在旧点 | 数条 | 竞选失败,只能当 Follower 追日志 |
| 慢盘 / IO 抖动 | fsync 耗时过长,复制跟不上、多次心跳超时 | 数十条,甚至触发快照 | 落后节点选不上 leader,避免选主后回退已提交数据 |
| 长时间离线 | 停机维护、跨机房抖动 | 整段日志缺失 | 靠快照(snapshot)追赶,它永远当 Follower |
一个可复算的生产场景:5 节点 etcd,quorum=3。节点 E 因磁盘 fsync 慢,日志停在 (2, 100);其余 4 节点已提交到 (2, 150)。E 的选举超时先到,发起竞选:
- E 广播 RequestVote(term=3, lastLog=(2,100))——term 3 高于集群当前 term 2;
- 收到请求的 4 个节点先执行任期对齐:term 更新为 3、降为 Follower、清空投票记录;
- 再执行日志检查:其中 3 个节点持 (2,150),比 E 新,拒绝;
- E 最多拿到自己 1 票 + 可能的 1 票落后节点,2 < 3,竞选失败;
- 集群在最新节点(term 3)重新收敛出 leader,E 以 Follower 身份接收 AppendEntries,逐条补齐到 150。
注意第 2 步已经发生:E 虽然没当选,但把整个集群的 term 从 2 抬到了 3——这就是 5.3 节 pre-vote 要消除的「无意义抬任」。它不丢数据,但会打断正在进行的复制。
如果去掉选举限制,E 的竞选会走完整条事故链:4 个节点在任期对齐后把票投给 term 更高的 E,E 当选、广播 (2,100) 旧日志,index 101–150 的已提交数据被覆盖。K8s 把全部集群状态(Deployment、Service、Pod 的期望状态)都存在 etcd,这一丢意味着控制面整体回退到旧时间点,并在旧状态上演算新的一致结果——系统性灾难。所以生产实践里,etcd 节点恢复后应先用 etcdctl endpoint status 观察它 behind 的条数,再让它参与竞选;但即便运维出错,选举限制也是永不失效的最后防线。
本节 lab
TestElectionRestriction 用 5 节点仿真直接复现「旧日志候选拿不到多数,新日志候选当选」:
- 节点 0、1、2 的日志置为 [{Term:1, Index:0}],代表「多数派已含较新日志」;
- 节点 3、4 保持空日志,是旧日志节点(lastLogTerm=0、lastLogIndex=-1);
- 旧节点 3 发起竞选(startElection(3)),携带 (term 0, index -1):节点 0/1/2 判定其日志旧、拒绝,3 最终只拿到 2 票(自己 + 空日志的节点 4),测试断言
voteGranted < majority(3 票); - 随后把节点 0 重置为干净 Follower(Term=2、VotedFor=-1、voteGranted=0),节点 0 发起竞选,携带 (term 1, index 0):其余 4 个节点日志都不比它新,5 票全收,测试断言
voteGranted >= majority。
同一套投票逻辑,只因日志新旧不同,一个被多数拒绝、一个全票当选。运行:
cd private/labs/k8s-etcd-lab
go test ./raft -run TestElectionRestriction -v
输出会打印两次竞选的结局:PASS 说明仿真行为与理论一致——选举限制不是可选项,而是状态机安全的第一道闸。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。