7.1 选举安全性:日志新旧比较保证候选人完整性
Raft 的安全性不是一条规则单打独斗的结果,而是几条性质互相咬合:选举安全性(Election Safety)、Leader 完整性(Leader Completeness)、日志匹配(Log Matching)、状态机安全(State Machine Safety),再加上作为地基的「Leader 日志只追加(Append-Only)」。第 5.2 节已经从协议层把「选举限制」讲透了:投票者只投给日志不落后于自己的候选。本节换个视角,从安全定理的角度回答一个问题:这条投票规则为什么是安全的?它凭什么让当选的 Leader 必然包含所有已提交日志?
本节聚焦两件事。第一,Election Safety 的准确定义与证明——每个任期至多选出一个 Leader,这是整个安全证明的第一个环节;第二,把 5.2 的日志新旧比较放回安全体系里,说明它如何把「多数派认可」升级为「日志不落后的多数派认可」,从而导出当选 Leader 的日志完整性。证明链条本身不引入任何新机制,它只把已经存在的规则放到定理层面重新组织。
第 7 章「Raft 安全性」共三节,恰好对应安全证明链的三个环节:7.1 选举安全性,给出「当选 Leader 必然包含全部已提交日志」的初始结论;7.2 Leader 完整性,把该结论推广到「任意后续任期」,并解释为什么 Leader 日志只追加是这条性质的地基;7.3 状态机安全,把「Leader 有正确日志」进一步推广到「所有节点应用相同日志」,收拢整条证明链。本节是第 7 章的第一块砖:它只处理「任期 0 之后第一个 Leader」及其之后任意一次换届的当选结论,是 7.2 归纳证明的起点。
Raft 安全性的体系:五条性质如何咬合
先给一张总览表。Raft 论文第 5.4 节把安全性拆成五条性质,后三节(7.1/7.2/7.3)逐一展开其中三条,日志匹配在第 6 章已讲,此处只交代它的位置:
| 性质 | 英文名 | 一句话表述 | 展开位置 |
|---|---|---|---|
| 选举安全性 | Election Safety | 每个任期至多选出一个 Leader | 7.1(本节) |
| Leader 只追加 | Leader Append-Only | Leader 日志从不删除或覆盖,只追加 | 7.2 |
| 日志匹配 | Log Matching | 同 (index, term) 的条目在每条日志中位置与内容相同 | 第 6 章 |
| Leader 完整性 | Leader Completeness | 被提交的日志条目在后续每个任期的 Leader 日志中必然存在 | 7.2 |
| 状态机安全 | State Machine Safety | 所有节点以相同顺序应用相同日志 | 7.3 |
这五条性质不是彼此独立的定理,而是一条互相支撑的证明链:Election Safety 保证「每任期一个 Leader」,加上日志只追加与日志匹配,推出 Leader 完整性;Leader 完整性再配合「只提交当前任期日志」的提交规则,推出状态机安全。7.1 是链条的第一环,也是最容易被低估的一环——很多人以为「选主」只是可用性问题,本节要说明:选主的投票规则同时是一次数据安全闸门。
Election Safety:每个任期至多一个 Leader
Election Safety 的陈述只有一句话:任意一个任期 term 内,至多存在一个 Leader。 它不承诺「一定能选出 Leader」(那是活性,由随机超时与多数派保证),只承诺「不会同时选出两个」(那是安全性)。
为什么不会有两个?反证法。假设同一任期 T 内同时存在 Leader L1 和 Leader L2。要当选,L1 需要获得任期 T 内超过半数的票,L2 也需要超过半数的票。两个多数派必须不相交——因为如果它们共享哪怕一个节点,这个节点在任期 T 只能投出一票,不可能同时投给 L1 和 L2。但两个「超过半数」的集合必然相交:5 节点集群多数是 3,两个多数派各 3 人,3 + 3 = 6 > 5,交集至少 1 人;一般地,多数大小 q > n/2,两倍多数 2q > n,交集非空。矛盾,故假设不成立。
这个证明完全建立在「每个节点在每个任期至多投一票」上。实现上它由两条规则落实:RequestVote 处理时检查 VotedFor——本任期已投票则不能再投;Candidate 收到更高任期会降级成 Follower 并清空投票记录,让新任期重新开始。两条规则共同保证「一节点一任期一票」。多数派的大小用 5.2 的口径:n 节点集群 quorum = n/2 向下取整 + 1,3 节点是 2,5 节点是 3。
为什么「日志新旧比较」是关键
Election Safety 只解决了「最多一个 Leader」,没解决「这个 Leader 带的数据对不对」。想象一个极端场景:一个日志几乎为空的节点,靠抬高 term 骗到多数票当选。Election Safety 依然成立(确实只有一个 Leader),但集群会在它领导下丢掉所有已提交数据。Election Safety 管的是「有没有第二个 Leader」,日志新旧比较管的是「唯一的 Leader 是不是数据的标准答案」。 两者缺一不可。
5.2 已经给出了规则本身:投票者只投给日志不落后于自己的候选,比较只看最后一条日志的 term 与 index。本节不重复规则细节,只强调它在安全体系中的位置——投票时的日志检查是数据安全的唯一闸门:
| 检查 | 防线 | 失效后果 |
|---|---|---|
| 任期检查(m.Term 对齐) | 保证「一节点一任期一票」 | 同一任期出现两个 Leader(违反 Election Safety) |
| 日志检查(logUpToDate) | 保证「当选 Leader 日志不落后于任何投票者」 | 旧日志 Leader 当选,覆盖已提交数据(违反 Leader 完整性) |
把两道检查分开看很重要:任期检查不是安全闸门,它只是让节点尊重更高任期的「事实对齐」;真正的数据安全闸门是日志检查。这就是为什么 5.2 强调「即使候选 term 更高,日志旧依然拒绝」——任期对齐把票权交给更高任期,日志比较再把「不配当选」的候选挡在门外。
logUpToDate 的精确语义与边界情况
k8s-etcd-lab 里 Node.logUpToDate 只有三行:
func (n *Node) logUpToDate(term, index int) bool {
myTerm, myIndex := n.lastLogTerm(), n.lastLogIndex()
if term != myTerm {
return term > myTerm
}
return index >= myIndex
}
完整判定表(投票者 V 的最后一条是 (myTerm, myIndex),候选携带 (term, index)):
| 条件 | 判定 | 结果 |
|---|---|---|
| term > myTerm | 候选更新 | 同意 |
| term < myTerm | 候选更旧 | 拒绝 |
| term == myTerm 且 index >= myIndex | 一样新或更新 | 同意 |
| term == myTerm 且 index < myIndex | 候选更旧 | 拒绝 |
两个边界情况必须记牢。一是空日志:lab 约定 lastLogTerm() 对空日志返回 0,lastLogIndex() 返回 -1(len(Log)-1)。这保证一个空日志节点只投给同样空或更新的候选,不会因为 index=0 的歧义把自己误判为「比别人长」。二是term 优先于 index:候选 (0, 100) 的 index 很大,但 term 0 说明整条日志属于远古任期,仍被拒绝。term 反映节点「最近是否真正参与过共识」,比日志长度更有信息量。
可复算的例子。投票者 V 最后一条是 (2, 7):
| 候选 | 携带元数据 | 逐条比较 | 结果 |
|---|---|---|---|
| C1 | (2, 7) | term 同、7 >= 7 | 同意 |
| C2 | (2, 6) | term 同、6 < 7 | 拒绝 |
| C3 | (3, 1) | 3 > 2 | 同意 |
| C4 | (1, 100) | 1 < 2 | 拒绝 |
C3 是容易看错的一行:index 只有 1,但它的 term 3 说明候选经历过更晚的共识,哪怕日志短也是「更新」,投它不会丢已提交数据。C4 则相反:term 1 的 100 条日志再多,也只代表一个远古 Leader 留下的历史,投它会允许一个更短前缀覆盖当前已提交的尾巴。
为什么只看最后一条就够了?因为 Raft 日志按 term 分段组织,日志匹配性质保证:两条日志在某个下标一致,则此前全部一致。于是「比较最后一条」等价于「比较两段前缀谁更长、谁更新」,最后一条的 term 优先、index 次之就是判断「日志新旧」的最小充分信息——多比较整条日志既不必要,也不可行(你不知道对方的完整日志)。
安全证明:当选 Leader 包含所有已提交日志
现在给出本节的核心定理。定理:若条目 e 已在任期 T 内提交,则任何在任期 T’ > T 当选的 Leader L 的日志都包含 e。
证明分三步,每一步都是 5.2 已给事实的定理化重组:
多数派交集。e 提交时被复制到了某个多数派 M(提交的定义:复制到多数派并确认);L 的选票来自多数派 V。由多数派交集,M ∩ V 至少有一个节点 X。
X 的两重身份。X 在 M 里,所以它包含 e 及之前全部日志(日志匹配:到 i 的前缀与提交时 Leader 一致);X 在 V 里且投给了 L,所以投票瞬间 X 判定了
logUpToDate通过——L 的最后一条日志不落后于 X 的最后一条。L 包含 e。设 e 的下标是 i,由第 2 步:L 的
lastLogIndex >= X.lastLogIndex >= i。再结合日志匹配性质(复制阶段 follower 与 Leader 冲突段被删除、一致前缀保留),L 在下标 i 处的条目与 X 一致,即与 e 一致。e 得证;把 e 推广到所有已提交条目,即得:当选 Leader 必然包含全部已提交日志。
注意第 2 步只用了「X 的日志不新于 L」,而没有假设任何节点诚实或日志正确——它只需要多数派交集这个纯计数事实。因此该定理对任意不超过 f 个的故障组合都成立,这正是 5.2 证明「选举限制 ⇒ 状态机安全」链条的起点:本节把链条的第一环从协议层抬升到了定理层。
可复算的实例:5 节点集群,quorum = 3。条目 e 在 index 7、term 2 提交,意味着多数派 M 至少 3 个节点持 (2, 7) 及以上。L 当选时的投票多数派 V 也至少 3 人,M ∩ V 至少 1 人 X。X 投给 L 前调用 logUpToDate(termL, indexL),因此 termL > 2 或 (termL == 2 且 indexL >= 7),无论哪种情况 L 的最后一条都不早于 (2, 7),L 的日志长度 ≥ 8,包含 index 7 的 e。
这个定理实际上是 Leader 完整性(7.2)的基础情形:它证明了「每个当选 Leader 包含到选举时刻为止的所有已提交日志」。要把它推广为「被提交的日志在后续所有任期的 Leader 中永远存在」,还需要补一条归纳步骤——假定第 T 任期的 Leader 已含 term ≤ T 的全部已提交条目,且它任期内只追加不删除(日志只追加性质),那么第 T 任期内新提交的条目会在第 T+1 任期 Leader 当选时被上面的定理覆盖,归纳成立。因此本节定理每证明一次换届,就为 Leader 完整性续上一个任期。
丢失已提交日志的危险场景
把「没有日志检查」的后果量化一下。3 节点 etcd,quorum = 2,节点 A、B 已提交 index ≤ 5 的日志(term 2),节点 C 离线期间日志停在 (1, 3):
| 节点 | 任期 | 最后一条日志 | 状态 |
|---|---|---|---|
| A | 2 | (2, 5) | 在多数派,正常 |
| B | 2 | (2, 5) | 在多数派,正常 |
| C | 1 | (1, 3) | 曾离线,重放 wal 后停在旧点 |
- C 恢复联网,选举超时先到,广播 RequestVote(term=3, lastLog=(1,3))。
- A、B 收到请求:若无日志检查,任期对齐后把票投给 term 更高的 C,C 以 2 票当选。
- C 广播自己的日志前缀到 index 3,A、B 用日志匹配删除 index 4、5。
- 客户端已确认的写入(例如 K8s 里一个 Deployment 的期望状态)消失,控制面在旧状态上演算新结果。
第 2 步就是唯一拦截点:A、B 持 (2,5),logUpToDate 发现 C 的 (1,3) 旧于自己,拒绝。C 最多拿到自己的 1 票,永远凑不齐 quorum。数据安全不靠「多数节点记住」,靠每个投票节点在投出的那一刻做日志比较。
值得补充一个更隐蔽的变体:危险不只在「日志几乎为空」的节点,也在「日志有已提交前缀但少了未提交尾巴」的节点。比如 C 的日志是 (2, 0..5) 已提交前缀 + 缺 index 6、7,而 A、B 已提交到 index 7。C 的 lastLogTerm 是 2,与 A、B 相同,但 lastLogIndex 是 5 小于 7,logUpToDate 照样拒绝。所以日志比较不是「看有没有已提交数据」,而是精确到每一条:只有最后一条都不落后于投票者的候选,才能保证它不会用更短的前缀覆盖投票者的尾巴。这正是 term 相同必须比较 index 的原因。
etcd 实现对照:raft.go 的投票决策与 storage.go 的日志来源
etcd 的 raft 包把投票决策放在 raft/raft.go 的 Step 里,处理 pb.MsgVote / pb.MsgPreVote 分支(v3.3.27 的真实代码):
if (r.Vote == None || m.Term > r.Term || r.Vote == m.From) &&
r.raftLog.isUpToDate(m.Index, m.LogTerm) {
r.send(pb.Message{To: m.From, Term: m.Term, Type: voteRespMsgType(m.Type)})
if m.Type == pb.MsgVote {
r.electionElapsed = 0
r.Vote = m.From // 记录本任期投给了谁
}
} else {
r.send(pb.Message{To: m.From, Term: r.Term, Type: voteRespMsgType(m.Type), Reject: true})
}
括号里前半段是任期 / 一票一任期检查,后半段 r.raftLog.isUpToDate(m.Index, m.LogTerm) 就是日志比较。isUpToDate 的定义在 raft/log.go,与 lab 的三行版本一一对应:
func (l *raftLog) isUpToDate(lasti, term uint64) bool {
return term > l.lastTerm() || (term == l.lastTerm() && lasti >= l.lastIndex())
}
那 lastTerm() / lastIndex() 的数据从哪来?来自 raft/storage.go 定义的 Storage 接口(LastIndex、Term、Entries 等方法)及其 MemoryStorage 实现:raftLog 先查内存中的 unstable(尚未落盘的尾部日志),查不到再读 storage.LastIndex()。NewMemoryStorage 还会预置一条 index 0 的 term 0 占位条目,保证空日志也有合法下标——这和 lab 里「空日志 lastIndex = -1、term = 0」是同一约定的两种写法。对照结论:etcd 把同一套比较逻辑分成了三处——raft.go 管「投不投」,log.go 管「怎么比」,storage.go 管「比谁」,lab 用单文件 Node 结构把它们合并成了可读的十几行。
还有两个实现细节值得对照。其一,拒绝时的响应带的是 r.Term(本地任期)而不是 m.Term:投票者被更高任期请求重置后,用本地新任期告诉候选「你的任期已过期」,候选据此更新自己的任期。其二,r.Vote 只在真实投票(MsgVote)时被记录,MsgPreVote 不记录——这是 5.3 的 pre-vote 机制:预投票只探测「能不能当选」,不消耗本任期的一票,因此日志比较在预投票与正式投票里被调用两次,语义完全相同。这一来一回正好印证了本节的核心主张:日志比较是无状态的安全闸门,跟任期对齐、票权记录这些「事实状态」正交。
本节 lab
5.2 的 lab 已经用 TestElectionRestriction 演示了旧日志候选被拒、新日志候选当选的协议过程;本节从定理角度再验一遍,重点看这条规则的「安全语义」是否成立。测试构造如下:
- 5 节点集群,quorum = 3;节点 0、1、2 的日志置为
[{Term:1, Index:0}],代表「多数派已含较新日志」; - 旧日志节点 3(空日志)发起竞选:节点 0/1/2 判定其日志旧而拒绝,3 的
voteGranted只有 2 票(自己 + 空日志的节点 4),断言< majority; - 把节点 0 重置为干净 Follower(Term=2、VotedFor=-1、voteGranted=0)后发起竞选:其余节点日志都不比它新,5 票全收,断言
>= majority。
同一个 logUpToDate,只因候选日志新旧不同,一个拿不到多数、一个全票当选——这正是「当选 Leader 包含所有已提交日志」定理在仿真里的直接体现:旧日志候选的选票多数派里,总有节点判定它日志旧而拒绝,候选永远够不到 quorum。运行:
cd private/labs/k8s-etcd-lab
go test ./raft -run TestElectionRestriction -v
输出 PASS 说明:选举安全性依赖的「多数派交集 + 日志不落后于投票者」两个条件在仿真中按定理工作,Election Safety 的第一环验证通过。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。