《Kubernetes 分布式系统原理深入解析》5.2 选举限制:日志新旧比较

选举协议只解决「谁能竞选」,选举限制解决「谁配当选」:投票者只投给日志不落后于自己的候选,用 term 优先、index 次之的日志新旧比较,保证当选 leader 必然包含全部已提交条目。本节先推演无限制时旧日志节点覆盖已提交数据的事故链,再给出比较规则、投票决策、多数派交集与领导者完整性的安全证明,最后落到 etcd 节点重启、磁盘落后时如何避免选主后丢数据。lab 用 TestElectionRestriction 复现旧日志候选拿不到多数、新日志候选当选。

5.2 选举限制:日志新旧比较

5.1 节把「谁能竞选、怎么拿到多数票」讲清楚了,但还留着一个悬案:选举协议只要求多数派认可,而多数派认可并不等于它带来的日志是正确的。如果让一个日志残缺的节点当选,它可以用自己的旧日志覆盖集群已经提交的条目——这不是理论上的极端情况,而是 etcd 生产事故里「换主后数据回退」的标准成因。

本节补上选举限制(Election Restriction):投票者只投给日志不落后于自己的候选。它不改变选举流程,只在投票端加一条日志比较规则,却承担了整个状态机安全证明的起点。为了让后面的例子可复算,先固定两套数字:3 节点集群 quorum = 2,5 节点集群 quorum = 3;日志条目统一记作 (term, index)。

为什么需要选举限制

先完整推演一遍「没有选举限制」的事故链。3 节点 etcd 集群:

节点任期最后一条日志状态
A2(2, 5)在多数派,正常
B2(2, 5)在多数派,正常
C1(1, 3)曾离线,重放 wal 后停在旧点

A、B 组成的多数派已经提交了 index ≤ 5 的日志。此时 C 网络恢复并发起竞选,C 的 term 递增到 2。事故链分五步:

  1. C 广播 RequestVote(term=2, lastLog=(1,3))。
  2. A、B 收到请求:C 的 term 2 高于本地。若没有日志检查,A、B 按任期对齐把自己降为 Follower 并把票投给 C。
  3. C 拿到 A、B 的两票,凑齐 quorum=2 当选。
  4. C 作为 leader 广播自己的日志前缀(到 index 3),A、B 用日志匹配规则删除 index 4、5 的冲突条目。
  5. 客户端已确认写入的 index 5 数据消失,状态机安全被破坏。

第 2 步就是唯一的拦截点:A、B 各自持 (2,5),C 持 (1,3),日志比较发现 C 的日志旧于自己,拒绝。C 最多只能拿到自己的 1 票,永远凑不齐 quorum,事故链在第 3 步之前被剪断。

这里有一个值得强调的区分:C 的竞选请求是合法的,A 投它也不违反任何协议条款,但组合结果违背了安全。 Raft 的解法不是禁止落后节点发起竞选(那会让节点永远无法通过选举自愈),而是让投票者用日志新旧把「多数认可」收紧为「多数中日志不落后的认可」。合规但危险的路径在投票端被剪断——这是 Raft 设计里「把安全检查放在节点本地决策」的典型风格,后面 5.3 节的 pre-vote 也是同一个风格。

日志新旧比较规则

比较只看候选日志的最后一条,规则只有两句话:

  1. 先比较最后一条的 term,term 大者新;
  2. 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 有两个属性:

  1. X 持有一致前缀到 i(它在 M 里,包含已提交条目 e 及其之前全部日志);
  2. 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. 第 1 个 term 的 leader 当选时已含全部已提交条目(上面的安全证明二)。
  2. 假设第 T term 的 leader 含所有 term ≤ T 的已提交条目;它在任期内只追加、不删除自己的日志。
  3. 若第 T term 内提交了新条目,第 T+1 term 的 leader 由证明二包含全部已提交条目(含 T 内提交的),归纳成立。

「leader 任期内日志只增不减」来自 Raft 的一个不对称设计:冲突删除只发生在 Follower 侧,leader 的日志从不被回退。 新 leader 对落后节点逐个下发缺失段,Follower 永远向 leader 看齐,绝无反向覆盖 leader 的可能——因为 leader 已经被证明「不可能缺已提交条目」,它是标准答案。

角色日志操作方向
Leader只 append、只广播日志是标准答案
Followerappend + 冲突删除 + 追赶永远向 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 的选举超时先到,发起竞选:

  1. E 广播 RequestVote(term=3, lastLog=(2,100))——term 3 高于集群当前 term 2;
  2. 收到请求的 4 个节点先执行任期对齐:term 更新为 3、降为 Follower、清空投票记录;
  3. 再执行日志检查:其中 3 个节点持 (2,150),比 E 新,拒绝;
  4. E 最多拿到自己 1 票 + 可能的 1 票落后节点,2 < 3,竞选失败;
  5. 集群在最新节点(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 说明仿真行为与理论一致——选举限制不是可选项,而是状态机安全的第一道闸。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图