Lecture 16: Leader Election — 领导者选举算法
Lecture 16: Leader Election — 领导者选举算法
讲义对应：CS 425 FA2026 Lecture 16「Leader Election」。⚠️ 请注意章号与课程讲次的错位：本笔记第 16 章对应课程日程中的 Lecture 18（10/22，Leader Election），原始讲义为
L17.FA25.pdf（54 页，Fall 2025 的讲次编号）。本章的机制图解部分引用了L18.FA25.pdf（Mutual Exclusion：集中式互斥与令牌环）作为”为什么需要 leader”的动机，理论部分引用了L15.A.FA25.pdf（Impossibility of Consensus：选举 ≡ 共识）与L15.B.FA25.pdf（Paxos）。 教材对应：Coulouris 5th Ed. Sec 15.3（Election Algorithms：Ring-based Election、Bully Algorithm）；Sec 15.2（互斥的集中式解决方案：协调者 + 令牌 + 队列）；Sec 15.1（Failure Detectors）；Sec 15.5.2（Consensus）；Sec 18.4（Gossip）；补充：Sec 17.3.1 与 Sec 21.5.2（Paxos、Raft、复制状态机）。 阅读材料：M. Burrows, Chubby（OSDI 2006）、P. Hunt et al., ZooKeeper/Zab（USENIX ATC 2010）、D. Ongaro & J. Ousterhout, Raft（USENIX ATC 2014）、M. Fischer, N. Lynch, M. Paterson, FLP（JACM 1985）；经典算法原文：G. LeLann（1977）、E. Chang & R. Roberts（1979，单向环）、D. Hirschberg & J. Sinclair（1980，$O(N\log N)$ 双向环）、H. Garcia-Molina（1982，Bully）。
16.1 概述
本讲回答一个看起来极其简单、实际上与共识问题等价困难的问题：在一组随时可能崩溃、可能被网络分区的进程中，选出一个唯一的协调者（coordinator / leader），并让组内每个存活进程都知道它是谁。 课程给出的两个目标是：(1) 在所有非故障（non-faulty）进程中只选出一个 leader；(2) 所有非故障进程对”谁是 leader”达成一致。这两个目标分别对应分布式算法里最经典的一对性质：安全性（Safety）与活性（Liveness）。
为什么分布式系统非要一个 leader？因为大量分布式机制在”有一个中心决策者”时会变得异常简单：集中式互斥（central server / token 方案里，协调者持有一个令牌并维护一个请求队列，收到请求就把令牌交出去）；全序多播（total-order multicast）需要一个序列器（sequencer）给消息编号；复制状态机（Replicated State Machine, RSM）需要一个 leader 决定操作顺序；Paxos 有一个”杰出提议者（distinguished proposer）”，Raft 有一个”强 leader”，共识协议在选举出 leader 之后才真正开始工作。讲义给出的三个动机场景非常具体：银行账户的多个副本中只有一个负责接收读写（如果出现了两个 leader，或者服务器之间对”谁是 leader”意见不一致，或者 leader 崩溃没人接管，结果都是不一致）；序列器方案里的序列器本身就是 leader；一组 NTP 服务器里谁是根服务器（root server）？此外，Apache ZooKeeper 与 Google Chubby 这两个工业界最重要的协调服务，其核心职责之一就是”在任何时刻都维持一个 leader 被选出”。把这条线索落到具体系统上，GFS 的 master、HDFS 的 NameNode、YARN 的 ResourceManager、Kafka 每个 partition 的 leader、数据库的主库（primary）——这些角色全都要求”任意时刻恰好一个实例在服务”，因此它们都需要领导者选举，或者需要一个能提供同等保证的分布式锁服务（这正是 Chubby/ZooKeeper 存在的理由）。
本讲的技术主线是两条：(1) 两个经典选举算法——环形选举（Ring-based Election，Chang-Roberts）与霸道算法（Bully Algorithm），它们简单、好理解，但都建立在超时机制之上，因而都建立在同步假设之上，而且都没有 quorum，因此在网络分区下都会脑裂；(2) 工业界的做法——Chubby 与 ZooKeeper 都用 Paxos 风格的 quorum 选举：候选人向其他服务器拉票，每个服务器在一个任期内最多投一票，拿到多数派（majority / quorum）选票的人当选。讲义明确点出了为什么选举如此困难：如果选举可解，那么共识也可解（选出一个进程，用它 id 的最后一位作为共识决定），而共识在异步系统中不可能（FLP），所以选举在异步系统中也不可能”既保证唯一、又保证终止”。
本章在整门课中的位置：向前，它依赖 Lecture 5–6 的故障检测器（Failure Detector, FD）（选举的第一步永远是”有人发现 leader 崩了”）与 Lecture 15 的共识/FLP（选举的理论上限）；向后，它是 Lecture 17（Paxos 与 Raft）的直接铺垫——Raft 的 leader election 就是本章所有思想的集大成者：随机化超时做故障检测、term 做逻辑时钟、quorum 做安全性、日志新旧比较把”选举”与”状态机安全”缝合在一起。本章的黄金法则是：
“最高 ID 胜出”看起来非常自然，但它在网络分区时会产生两个 leader（脑裂）；真正安全的选举必须依赖 quorum 交集——这正是现代强一致系统放弃 Bully/环形选举、改用 Raft/Paxos 风格 quorum 选举的根本原因。
16.2 核心概念与分布式机制图解
16.2.1 领导者选举问题（Leader Election Problem）
- 定义与目的：给定 $N$ 个进程，每个进程有一个唯一标识符（unique id）（以及某些可以比较的属性），要求设计一个协议，使得在一轮选举结束后：
- 只选出唯一一个 leader——并且这个 leader 必须是在所有非故障进程中属性值最佳（best attribute value）的那个（通常是 id 最大，也可以是 IP 最大、CPU 最快、磁盘最多、文件数最多等）；
- 所有非故障进程都知道它是谁——即每个进程的本地变量
elected都指向同一个进程。
直观解释（”它是什么？”）：把 Bully 算法想象成公司里的一次”谁来当经理”的推举。规则只有两条：职位（id）最高的人当经理；不服的人不要吵架，直接去找比自己职位高的人”请示”，如果所有比你高的人都答复你”我还在”，那么自然由更高的人去争，你只需要等公告；只有当所有比你高的人都联系不上时，你才对外宣布”我是经理”。 这个规则的设计精妙之处在于：最高的那个人永远不会收到任何”我还在”以外的答复（因为没人比他高），所以他必然是最终宣布自己当经理的人；而其他人只要收到过任何一个答复，就知道”上面还有人”，于是自动退让。
形式化要求（安全性 Safety 与活性 Liveness）：讲义把选举问题的正确性写成如下两条，这是本章所有证明的判决标准：
性质 讲义中的形式化表述 通俗解读 安全性（Safety） 对每个非故障进程 $p$：$p$ 的 elected要么等于某个特定的非故障进程 $q$（具有最佳属性值的那个），要么为Null绝不允许两个进程认为自己是 leader；允许”暂时还不知道（Null）” 活性（Liveness） 每一轮选举都会终止，并且结束时每个非故障进程的 elected不为Null选举必须结束，且结束时所有人都知道 leader 这里有一个极其关键、也最容易被误读的细节：安全性为什么允许
Null？ 因为在异步系统里”所有进程在同一瞬间都认为 X 是 leader”是不可能做到的（你无法区分”消息还在路上”和”对方崩溃了”）。因此安全性的真正含义是：任意时刻自认为 leader 的进程至多一个（或者换一种更强的说法：所有进程的elected值最终收敛到同一个进程，中途允许是Null）。Raft 把这个思想做成了”每个任期（term）至多一个 leader“，实际系统把它做成”任意时刻至多一个进程被授权写共享状态“。本章后面所有的脑裂反例，破坏的都是这条”至多一个”。- 机制图解：选举要维护的其实是一个”组视图（group view）”，它由两部分组成——谁是 leader，以及哪些进程还活着（这就是故障检测器与成员管理，详见 Lecture 5–6）。
选举协议的输入与输出
┌──────────────────────────────────────────────────────────────────────────────┐
│ 进程组 {P1, P2, P3, P4, P5} │
│ │
│ 输入 1：唯一 id（可比较） 输入 2：故障检测器（心跳 + 超时，可能误判） │
│ 输入 3：消息通道（可靠 / FIFO？延迟有界？） 输入 4：谁可以发起选举？ │
└──────────────────────────────────────────────────────────────────────────────┘
│ 选举协议（Election Protocol）
▼
┌─────────────────────────────────────────────────────────────────────────────┐
│ 输出 1（安全性）：任意时刻，满足 elected == 自己 的进程数 <= 1 │
│ 输出 2（活性）：选举终止后，所有非故障进程的 elected != Null 且指向同一进程 │
│ 输出 3（属性）：被选中者是"非故障进程中属性值最佳"的那一个 │
└─────────────────────────────────────────────────────────────────────────────┘
选举的”调用规则”（讲义明确规定，直接决定了算法设计）：任何进程都可以发起（call for）一次选举；一个进程同一时刻最多只参与一轮选举；允许多个进程同时发起选举；但这些并发选举合起来必须只产生一个 leader；并且选举结果不能取决于”是谁发起的”。最后这条”结果与发起者无关”是 Bully 与环形选举共同的正确性基石：它们都通过”属性值最佳者胜出”来保证这一点。
关键假设与系统模型：$N$ 个进程；每个进程有唯一 id；消息最终会被送达（messages are eventually delivered）；选举协议执行期间可能发生故障。讲义没有假设”进程不会崩溃”，恰恰相反，“选举期间有人崩溃”才是这个问题的灵魂。
16.2.2 系统模型：同步、异步与故障假设
定义与目的：同一个算法在不同系统模型下的结论完全不同（Lecture 15 的教训：共识在同步模型可解、在异步模型不可能）。选举算法必须先”报出自己的假设”。
维度 同步系统模型（Synchronous） 异步系统模型（Asynchronous） 消息延迟 有已知上界 $ub_{msg}$ 无上界（可以任意长，但有限） 进程步长 每一步耗时有界 $lb < t < ub$ 无界 时钟漂移 有已知漂移率上界 任意漂移 超时能否可靠判定故障 能（超时即崩溃，假设 FD 完美） 不能（”崩溃”与”很慢”不可区分） 典型实例 多核/总线互连的机器、实时系统 互联网、数据中心（本质上偏异步） 正确的直觉：同步模型是异步模型的特例——为异步系统设计的协议一定也能在同步系统中工作，反过来则不一定。Bully 与环形选举恰恰是反向的：它们为同步模型设计，因此在真实（异步）网络中只能”通常正确”。
- 故障模型（Failure Model）：
- crash-stop（崩溃即停止）：进程崩溃后永远不再恢复。多数学术分析用它。
- crash-recovery（崩溃-恢复）：进程崩溃后可能重启（重启后内存中的易失状态丢失，但唯一 id 与稳定存储中的内容保留）。Bully 算法明确按这个模型设计：讲义特别规定”一个恢复的进程会发起选举，因为它不知道谁是当前 leader”。
- 遗漏故障 / 拜占庭故障：本章与课程均不涉及（选举在拜占庭模型下需要 $3f+1$ 个节点，属于另一套理论）。
通道假设：讲义对环形选举假设可靠的单向通道（消息最终送达、不丢失）；对 Bully 假设可靠通道 + 消息延迟有界。真实系统里这两条都要靠 TCP 重传 + 应用层超时近似。
- 机制图解：三种典型假设组合，决定了”选举能不能保证唯一”。
假设强度 典型算法 唯一性（无脑裂）？ 终止（活性）？
─────────────────────────────────────────────────────────────────────────────────
异步 + 无 FD 不存在（FLP 不可能性） 不可能同时保证两者 不可能同时保证两者
部分同步 + 超时 Bully / 环形选举 分区时会脑裂（无 quorum） 会终止（超时兜底）
部分同步 + quorum Raft / Paxos / Zab / Chubby 不会脑裂（quorum 必有交集） 最终终止（随机化超时）
16.2.3 为什么选举这么难：崩溃 vs 很慢，以及脑裂
- 核心困难（来自 Lecture 5–6 的故障检测器）：在异步系统中，一个进程无法区分”对方崩溃了”和”对方只是很慢 / 消息被延迟了”。 因此所有实用的故障检测器都靠超时（timeout）：超过阈值没收到心跳就”怀疑”对方失效。超时必然带来两类错误：
- 不完整（incompleteness）：真正的崩溃被漏检（超时设得太长）⇒ 该换 leader 却没人发起选举 ⇒ 活性被破坏；
- 不准确（inaccuracy）：把没崩溃但很慢的进程误判为崩溃（超时设得太短）⇒ 多余地发起一轮选举 ⇒ 如果此时旧 leader 还活着并且仍然自认为 leader，就同时存在两个 leader——这就是脑裂（Split-Brain）。
脑裂（Split-Brain）的定义与危害：脑裂指系统中同时存在两个（或更多）自认为合法的 leader。它的典型成因不是”算法写错了”，而是网络分区（network partition）：网络被切成两组，两组之间消息全部丢失，每一组都通过超时判定”对面那组（包括旧 leader）已经死了”，于是各自选举出自己的 leader。危害非常具体：两个 leader 都接受客户端写请求并写入同一份共享存储（同一份数据副本、同一个块设备、同一份日志），后写的覆盖先写的，或者交错写入破坏数据结构——这就是数据损坏（data corruption），而银行账户例子里的”两笔各 10000 美元的存款只剩下一笔”就是它的日常版本。
关键结论（本章的第一个”反直觉”）：只靠”选出 ID 最大的进程”是无法避免脑裂的，因为每个分区内部都会认为”自己是完整的系统，对面的更高 ID 进程已经崩溃”。要避免脑裂，必须让”合法性”依赖跨分区的信息——最经典的机制就是 quorum（多数派）：任意两个多数派必有交集，而交集中的节点在一轮内只能投一票，因此不可能产生两个都拿到多数票的 leader。
- 机制图解：同一套超时机制，在两种网络状态下的行为完全不同。
(a) 没有分区：只有一个 leader，超时检测正常工作
┌──────────────────────────────────────────────────────┐
│ P1 ──heartbeat──► ┌──────────────┐ ◄──heartbeat── P3 │
│ P2 ──heartbeat──► │ P5 (leader) │ ◄──heartbeat── P4 │
│ └──────────────┘ │
│ 所有进程的 elected 都是 P5 │
└──────────────────────────────────────────────────────┘
(b) 网络分区 + 超时误判：脑裂！
┌─────────────────────────────┐ ┌───────────────────────────────┐
│ 分区 A：{P1, P2} │ │ 分区 B：{P3, P4, P5} │
│ │ ✂ 消息全丢 │ │
│ P1: P5 超时 => 判定 P5 死了 │ │ P5: 我一直活着，继续当 leader │
│ P2: 我 id 最高 => 称王 │ │ P3/P4: 心跳正常 │
│ elected = P2 │ │ elected = P5 │
└─────────────────────────────┘ └───────────────────────────────┘
===> 两个 leader 同时存在：P2 与 P5 <===
16.2.4 Bully 算法：直觉与机制图解
定义与目的：霸道算法（Bully Algorithm，Garcia-Molina 1982）是最经典的选举算法。核心思想：所有非故障进程中 id 最大的那个成为 leader——”霸凌”这个名字就来自”大的压小的”：任何收到更高 id 者
ELECTION的进程都必须乖乖回一句OK并退让。直观解释：它很像”公司里职位最高的人当经理”。你发现经理失联了，于是给所有职位比你高的人发一封”我想当经理”的信（
ELECTION）；只要任何一个人回你一句”我还活着”（OK），你就立刻闭嘴、退到一边等公告；只有当所有比你高的人都没有任何回应时，你才对外宣布”我是经理”（COORDINATOR）。而每一个收到你信的人，也会顺便去问比他更高的人——像多米诺骨牌一样，最终只有职位真正最高的那个人会走到”没人能回复我”这一步。- 系统模型假设（必须明确）：
- 同步系统（有可靠的超时机制，消息延迟有界）——这是 Bully 能给出活性保证的前提；
- 进程可能崩溃，崩溃的进程之后可能恢复（crash-recovery）；
- 通道可靠，消息延迟有上界；
- 每个进程知道所有其他进程的 id（全连接、已知成员集合）。
三个消息类型：
ELECTION（”我要竞选，比我高的请回答”）、OK（”还有比我更高的人活着”）、COORDINATOR（”新的 leader 是谁”）。- 机制图解（完整消息交互时序图）：下图是一次真实运行的复现（见 16.4.1 的代码输出），组内有 6 个进程
{N3, N5, N6, N12, N32, N80}，原 leader N80 崩溃，由 N3 最先通过心跳超时发现：
N3 N5 N6 N12 N32 N80(崩溃)
│ │ │ │ │ ╳
t0 │ │ │ │ │ ╳ P3 心跳超时，判定 N80 故障
│ │ │ │ │ ╳
│ELECTION►│ │ │ │ │ 只发给 id 更高的进程
│─────ELECTION─────►│ │ │ │
│──────────ELECTION──────────►│ │ │
│────────────────────ELECTION────────────────────►│ 发给 N80 的石沉大海
│ │ │ │ │ ╳
│◄───OK───│ │ │ │ │
│◄────────OK────────│ │ │ │ 每个更高 id 者回 OK
│◄─────────────OK─────────────│ │ │
│◄───────────────────────OK───────────────────────│
│ │ │ │ │ ╳
│ │ELECTION►│ │ │ │ 收 ELECTION 者自己也发起一轮
│ │─────ELECTION─────►│ │ │
│ │───────────────ELECTION───────────────►│
│ │ │ │ │ ╳
│ │ │ELECTION►│ │ │
│ │ │──────────ELECTION──────────►│
│ │ │ │ │ ╳
│ │ │ │─────ELECTION─────►│
│ │ │ │ │ ╳
│ │ │ │ │ELECTION►│
★ N32 等 N80 应答，超时（未收到任何 OK）
│ │ │ │ │ ╳
│ │ │ │ │ ╳ N32 自称 leader
│ │ │ │ │ ╳
│◄───────────COORDINATOR: N32───────────│ │ 向所有更低 id 广播公告
│ │◄─────────COORD: N32─────────│ │
│ │ │◄────COORD: N32────│ │
│ │ │ │◄─COORD──│ │
│ │ │ │ │ ╳
t5 所有人的 elected 都变成 N32（公告完成）
这张图里有三个必须记住的细节：
ELECTION只发给 id 比自己高的进程（把”低 id 的人”排除在外），因此收到ELECTION的进程永远比发送者高——这保证了”回OK“永远是合法的压制动作；- 收到
ELECTION的进程在回完OK之后，自己也发起一轮选举（讲义原文：replies with OK message, and starts its own leader election protocol (unless it has already done so)）——正是这条规则造成了”级联”，也是 $O(N^2)$ 消息复杂度的来源； - 自称 leader 的唯一条件是”向所有更高 id 发出
ELECTION后，在超时内没收到任何OK“（或者”我本来就知道自己是全局最高 id”）。N32 之所以能称王，只是因为它上面唯一活着的候选者 N80 已经崩溃——超时在这里承担了”确认没有更高者”的全部职责。
- 崩溃恢复（crash-recovery）的处理：一个崩溃后重启的进程内存里的
elected变量已经丢失，它不知道当前 leader 是谁，因此讲义规定：恢复的进程会发起一轮选举。它向所有更高 id 发ELECTION：如果当前 leader 的 id 更高，它会收到OK（以及对方的COORDINATOR公告），于是立刻被压制、重新认识 leader；如果它恰好是最高的存活进程，那么它成为新 leader 也是正确的——因为原来更高的进程确实都死着。这就是”恢复不会破坏安全性”的全部理由。
16.2.5 Bully 最坏情形：$O(N^2)$ 的消息爆炸
- 最坏情形是什么：讲义明确指出，当系统中 id 最低的进程最先发现 leader 故障时，选举最慢、消息最多。原因是”收到
ELECTION就自己也发起一轮”这条规则的逐级放大：
最坏情形：id 最低的 P1 最先发现 leader（PN）崩溃，级联向上
每一行是"一位发起者"发出的 ELECTION；● = 发给一个比自己 id 更高的进程
发件人 \ 收件人 P2 P3 P4 P5 P6 P7 PN(崩溃) 条数
-----------------------------------------------------------------------
P1 ● ● ● ● ● ● ✗ 第 1 级：N-1 条
P2 ● ● ● ● ● ✗ 第 2 级：N-2 条
P3 ● ● ● ● ✗ 第 3 级：N-3 条
...
P(N-2) ● ✗ 倒数第 2 级：2 条
P(N-1) ✗ 最后一级：1 条
三角形内 ● 的总数 = (N-1) + (N-2) + ... + 1 = N(N-1)/2 = O(N^2) 条 ELECTION 消息
每条 ELECTION 还会被回一条 OK（发给已崩溃 PN 的那条收不到），再加 N-1 条 COORDINATOR
完整的账目（本章代码实测，与讲义口径一致）：设最高 id 的旧 leader 已崩溃、其余 $N-1$ 个进程同时发现故障并各自发起选举（这正是讲义描述的最坏情形）：
消息类型 数量 说明 ELECTION$\frac{N(N-1)}{2}$ 第 $i$ 高者发 $i-1$ 条（含发给已崩溃进程的那条） OK$\frac{(N-1)(N-2)}{2}$ 每条发给存活高 id 进程的 ELECTION都被回一句OKCOORDINATOR$N-2$ 新 leader（次高 id）向所有更低 id 广播 合计 $N^2-N-1$ 例如 $N=3,5,8,12$ 时分别为 $5, 19, 55, 131$ 条 最好情形：讲义给出的最好情形是”次高 id 的进程检测到 leader 故障“：它只需向 $N-2$ 个更低 id 广播
COORDINATOR（$O(N)$ 条消息），完成时间 1 个消息传输时间。更极端的特例是全局最高 id 的进程自己发现故障（或干脆由它发起），它连一条ELECTION都不用发，直接广播COORDINATOR。时间/轮次复杂度：讲义给出的最坏完成时间是 5 个消息传输时间（在选举期间没有新故障的前提下），这 5 步是：① 最低 id 的服务器发出
ELECTION；② 次高 id 的服务器向它回OK；③ 次高 id 的服务器向最高 id 发出ELECTION；④ 次高 id 的服务器等待应答超时；⑤ 次高 id 的服务器发出COORDINATOR。注意第 ④ 步：超时本身被算作”选举时间”的一部分——这是 Bully 的实际延迟通常由超时值（而非消息数）主导的原因，也是为什么”超时设多长”是 Bully 工程实现中最难的部分：超时值必须覆盖一个最坏往返（ELECTION去 +OK回 + 处理时间，即讲义所说”最坏单程延迟 + 最坏处理时间”的往返版本；讲义用 5 个消息传输时间来标定它），否则会误判；但设得太大，每次 leader 故障后的不可用窗口（election window）就会很长。
16.2.6 环形选举（Ring-based Election）：机制图解
定义与目的：把 $N$ 个进程组织成一个逻辑环（logical ring）（类似 Chord 的环，但不是 DHT），第 $i$ 个进程 $p_i$ 只有一条到 $p_{(i+1) \bmod N}$ 的通信通道，所有消息单向（顺时针）传递。环拓扑的代价是消息必须绕圈，好处是不需要全连接、不需要知道所有成员，而且”绕环一周回到自己”天然提供了一个终止判据。
直观解释：想象一圈人传纸条。任何人发现”原来的组长不在了”，就把写有自己名字的纸条传给下一个人。规则是：看到纸条上名字比自己小，就把名字划掉改成自己的（只改一次）；看到比自己大，就原样传下去；如果纸条转了一圈回到自己手上，那就说明”全圈没有人比我更大”——你当组长，并沿着环宣布结果。纸条上的名字只会越改越大，最终只有最大的那个名字能绕满一圈。
机制图解（讲义环上的 ID 传递与替换）：环的顺时针顺序为
N3 → N12 → N6 → N5 → N32 → N80 → N3（讲义中的六边形环），由N3最先发现 leader 故障并发起选举：
N80 ★原 leader（已崩溃）
⑤ 携 32 ╱ ╲ ① 携 3
N32 N3
④ 携 12 │ │ ② 携 3→12
N5 N12
⑥ 携 80 ╲ ╱ ③ 携 12
N6
顺时针方向：N80 → N3 → N12 → N6 → N5 → N32 → N80
① N12：3 < 12 ⇒ 替换为 12 ② N6：12 > 6 ⇒ 原样转发 ③ N5：12 > 5 ⇒ 原样转发
④ N32：12 < 32 ⇒ 替换为 32 ⑤ N80：32 < 80 ⇒ 替换为 80（环上最大值）
⑥ N80 的 80 绕环一周回到 N80 自己 ⇒ 判定"我是最大者" ⇒ 发 ELECTED:80
上图对应的逐跳演化（每一跳都标注纸条上 id 的取值与动作）：
| 跳 | 持有者 | 收到的 id | 与他自己的 id 比较 | 动作 | 传出的 id |
|---|---|---|---|---|---|
| 0 | N3 | — | — | 发现 leader 故障并发起选举 | ELECTION:3 |
| 1 | N12 | 3 | $3 < 12$ | 首次转发 ⇒ 替换 | ELECTION:12 |
| 2 | N6 | 12 | $12 > 6$ | 原样转发 | ELECTION:12 |
| 3 | N5 | 12 | $12 > 5$ | 原样转发 | ELECTION:12 |
| 4 | N32 | 12 | $12 < 32$ | 首次转发 ⇒ 替换 | ELECTION:32 |
| 5 | N80 | 32 | $32 < 80$ | 首次转发 ⇒ 替换 | ELECTION:80（已是环上最大值） |
| 6 | N3 | 80 | $80 > 3$ | 原样转发 | ELECTION:80 |
| 7 | N12 | 80 | $80 > 12$ | 原样转发 | ELECTION:80 |
| 8 | N6 | 80 | $80 > 6$ | 原样转发 | ELECTION:80 |
| 9 | N5 | 80 | $80 > 5$ | 原样转发 | ELECTION:80 |
| 10 | N32 | 80 | $80 > 32$ | 原样转发 | ELECTION:80 |
| 11 | N80 | 80 | $80 = 80$ | 匹配自己的 id ⇒ 我是最大者 | 宣布 ELECTED:80 |
| 12 | N3 → N12 → N6 → N5 → N32 | 80 | — | 各自设 elected = 80 并继续转发 | ELECTED:80（回到 N80 后停止） |
这次运行恰好落在讲义的最坏情形上：发起者 N3 正是 would-be leader N80 的环后继（N80 → N3 本身就是一条边），因此 ELECTION 必须走满 $N-1=5$ 跳才碰到 N80，而 N80 的 id 又要再走 $N=6$ 跳绕回自己。其账目是：
| 组成 | 消息数 | 说明 |
|---|---|---|
ELECTION 从发起者走到 would-be leader | $N-1$ | 每跳一条 |
| leader 的 id 不变地绕回自己（判定胜利） | $N$ | 绕环一周 |
ELECTED 公告绕环一周 | $N$ | 让所有人更新 elected |
| 最坏合计 | $\mathbf{3N-1}$ | 完成时间同样是 $3N-1$ 个消息传输时间 |
| 最好情形（发起者自己就是最大者） | $2N$ | 自己的 id 绕一圈回来 + 公告绕一圈 |
多个同时发起者怎么办：允许多个进程同时发起（讲义明确允许），做法是把发起者的 id 也放进消息里，每个进程缓存它见过的
Election/Elected消息的发起者 id，并且永远压制（suppress）来自更低 id 发起者的消息；一旦见到更高 id 发起者的消息就更新缓存。结果是：只有最高 id 发起者的那一轮选举能跑完，其余轮次会在某处被”吃掉”，从而仍然只产生一个 leader。故障的致命影响：如果 would-be leader 在它的
ELECTION消息正在绕环时崩溃，那么这条消息会永远在环上打转——因为没有进程能匹配它、也没有进程能替换它，活性被破坏。讲义给出的两种修法是：(1) 让 would-be leader 的前驱/后继检测到它的失败并重新发起一轮（但如果前驱也崩了、前驱的前驱也崩了……）；(2) 让任意进程在收到ELECTION:80后用自己的局部故障检测器判断 N80 是否失败，是则重开一轮。但讲义随即指出这条路的根本困难：故障检测器不可能既完整又准确——不完整（漏检 N80 的崩溃）会违反对安全性的期望（消息永远转圈，或者更糟：另一个进程被误认为 leader），不准确（误判 N80 崩溃）会让选举永远重开，破坏活性。这正是本章反复出现的主题：用超时做故障检测，就要在两个方向上同时付出代价。令牌环（token ring）中的 leader 选举：如果环上已经维护着一个令牌（token）（Lecture 18 的环形互斥就是”环上恰好一个令牌，持有者才能进临界区”），那么”谁是 leader”可以直接由令牌定义：令牌持有者就是当前唯一的授权者，它天然承担 leader 的角色（也可以反过来规定”只有持令牌者有权发起选举并宣布结果”）。好处是唯一性来自”环上恰有一个令牌”这条不变式，而不是来自 id 大小。代价是令牌自己会出事：丢失（持有者崩溃、消息丢失）或被复制（分区让”传令牌”在两侧各自生效，重传也可能制造出第二个令牌）。因此必须有令牌再生（token regeneration）协议：① 检测丢失——某个进程长时间没见到令牌就怀疑它已丢失；② 再生与去重——由指定的一方（例如 id 最小的进程）重新生成令牌，并配合”确认旧令牌已被销毁”的握手消除重复。如果允许多个令牌共存，就等于同一把锁被两个进程同时持有——又是脑裂。 这就把令牌环与本章主线连了起来：“唯一令牌”与”多数派 quorum”是同一个思想——都用一个不可能被两人同时合法持有的对象来定义合法性；区别在于令牌的唯一性依赖环的连通性（断环即失效），而 quorum 的唯一性依赖多数派交集（分区时依然成立）。
16.2.7 基于 quorum 的选举：Raft 的状态机与时序
定义与目的：quorum 选举（也叫基于共识的选举、多数派选举）把”谁当 leader”变成一个投票问题：候选人向组内所有成员拉票，每个成员在一个任期内最多投一票，拿到严格多数派 $\lfloor N/2 \rfloor + 1$ 票的候选人当选。Chubby、ZooKeeper（Zab）、etcd/Raft、MongoDB、Kafka KRaft 都走这条路。
直观解释：它像董事会投票而不是”职位最高者独裁”。任何决议必须得到超过一半的董事同意；因为任意两拨超过半数的董事必然有重叠，所以不可能出现”两拨人各自通过了相反的决议”。这就是 quorum 的全部魔力：它不依赖任何超时是否准确，只依赖”多数派必然相交”这一条组合事实。
机制图解（Raft 的状态转换图）：
随机化选举超时（150~300ms）到点，且没有收到 leader 心跳
┌────────────────┐ ┌────────────────────────┐
│ Follower │ ────────────────►│ Candidate │
│ │ ◄────────────────│ │
│ 只响应投票请求 │ 发现更高 term │ term += 1 │
│ 与 leader 心跳 │ 或已有 leader │ 投票给自己 │
└────────────────┘ │ 向所有人发 RequestVote │
└────────────────────────┘
│ 收到多数派选票
▼
┌────────────────────────────┐
│ Leader │
│ │ 拿不到多数派确认
│ 定期发心跳 AppendEntries │ => 自动退位（step down）
│ 拿到多数派确认 => 维持权威 │
│ └────────────────────────────┘
┌◄─────────────────────────────────────
│
└──► (Follower 收到更高 term 时同样降级)
- 机制图解（Raft 选举时序：随机化超时如何避免”选举风暴”）：
时间 →
P1(follower) │─timer 155ms─╳ 超时
P2(follower) │────timer 210ms────╳ 超时
P3(follower) │──────timer 168ms──────╳ term=2，成为 Candidate
│
P3 ──RequestVote(term=2, lastLogIdx=7)──► P1, P2, P4, P5
P1 ──VoteGrant(term=2)──► P3 （P1 在 term 2 还没投过票：可投）
P2 ──VoteGrant(term=2)──► P3 （P2 在 term 2 还没投过票：可投）
P4 ──VoteGrant(term=2)──► P3
P5 ──✗ 拒绝：候选人的日志不如我新（lastLogIdx 更小）
│
P3 收到 3 票（含自己）= floor(5/2)+1 = 3 票 ==> 当选 term 2 的 leader
│
P3 ──AppendEntries(term=2, 空心跳)──► 所有节点（每 50~100ms 一次）
follower 收到后重置自己的随机化 timer（于是不会再有人超时竞选）
- 与 Bully 的本质区别（必须刻在脑子里）：
- Bully 用”id 最大”决定合法性，不需要任何沟通共识；quorum 选举用”多数派投票”决定合法性，合法性来自跨节点的一致同意。
- Bully 的候选人在”没收到
OK“时即可称王——这个判断完全基于局部信息（我自己的超时）；Raft 的候选人必须收到多数派的票才能称王——这是全局信息。 - 因此在网络分区下：Bully 会在每个分区里都选出 leader（脑裂）；Raft 只在含多数派的分区里选出 leader，少数派永远选不出来（它的票数上限就是少数派的人数）。这一条差异就是本章的黄金法则，也是 16.4.3 那个实验要跑出来的东西。
- 选举限制（election restriction）：Raft 还要求候选人日志至少与投票者一样新（先比最后一条日志的 term，再比 index），否则投票者拒票。这条规则把”选举”和”安全性”缝合在一起：它保证被选出的 leader 一定包含所有已提交的日志条目，从而避免”选出一个落后于已提交状态的 leader，然后覆盖掉已提交的数据”。Bully 与环形选举完全没有这个维度——它们只关心 id，不关心数据新鲜度。这是”选谁”从”选 ID 最大的”进化到”选最合适领导复制状态机的”的关键一步。
- 租约（lease）：Chubby 的做法是，选举完成后，其他服务器承诺在”一段时间内”不再发起选举，这段时间叫 master lease（主租约），通常是几秒；master 只要还能每次赢得多数派就可以续租。租约机制让”master 崩溃后自动重新选举”变得自动而高效，代价是它依赖时钟同步（租约到期是按本地时钟判断的，时钟漂移会让两任 master 的租约重叠 ⇒ 又回到脑裂风险，详见 Lecture 11–12 的时钟同步）。这说明 lease 只是把 quorum 的安全性”摊销”掉，并不能替代 quorum。
16.2.8 脑裂（Split-Brain）与 fencing
脑裂的完整因果链：网络分区（或长时间 GC/机器假死）⇒ 故障检测器超时 ⇒ 一侧认为 leader 已死 ⇒ 该侧选举出新 leader（Bully 这种”局部决定”的算法一定会成功）⇒ 两个 leader 同时接受写 ⇒ 共享存储上的数据被交替覆盖 ⇒ 数据损坏。
四种防护手段（必须分清它们的层次）：
手段 原理 能否阻止第二个 leader 产生 典型系统 quorum / 多数派投票 任意两个多数派必相交，且一个节点一轮只投一票 能（根本手段） Chubby、ZooKeeper、Raft、Paxos fencing token / epoch / sequencer 每次当选都从单调递增的序列器取一个更大的号；存储层只接受比它见过的最大号更大的写，旧 leader 的写被拒绝 不能（仍然有两个 leader），但能阻止旧 leader 生效 Chubby 的 sequencer、HDFS NameNode HA、Raft 的 term、ZooKeeper 的 epoch STONITH（Shoot The Other Node In The Head） 用带外电源控制（PDU/IPMI）真的把对方断电，物理上保证只有一个节点活着 能（物理层面） Pacemaker/Corosync 集群、数据库 HA lease + 时钟同步 leader 只在租约期内合法；租约到期即失效，需要续租（续租依赖 quorum） 部分（依赖时钟漂移上界） Chubby master lease 机制图解（fencing token 如何拦住旧 leader 的写）：
旧 leader P5（少数派分区） 新 leader P2（多数派分区）
│ │
│ ① 取 epoch：序列器返回 1 │ ① 取 epoch：序列器返回 2（单调递增）
│ ② write(余额=100, epoch=1) │ ② write(余额=999, epoch=2)
▼ ▼
┌─────────────────────────────────────────────────────────────────────┐
│ 存储层（Fenced Store） │
│ │
│ 规则：只有当 收到的 epoch >= 我见过的最大 epoch 时才接受这次写 │
│ │
│ ① epoch=1，max_epoch 从 0 变 1 => 接受 P5 的写，max_epoch := 1 │
│ ② epoch=2，2 >= 1 => 接受 P2 的写，max_epoch := 2 │
│ ③ epoch=1，1 < 2 => ✗ 拒绝 P5 的写（epoch 已过期） │
└─────────────────────────────────────────────────────────────────────┘
│ │
│ ③ P5 再用 epoch=1 写 => 被拒绝 │ 最终值 = P2 写入的 999
▼ ▼
旧 leader 虽然还以为自己是 leader，但它的写再也无法破坏数据
- 工业案例：HDFS 的 NameNode HA 用 fencing（通过
sshfence/shell脚本杀掉旧 NameNode 的进程，或依赖 QJM 中 JournalNode 的多数派）确保两个 NameNode 不会同时写 editlog；Pacemaker 用 STONITH 设备；Chubby 给每个锁的获得者发一个 sequencer（内部含锁的世代号 generation number），客户端必须把 sequencer 传给被访问的存储服务，存储服务据此拒绝过期持有者的写——这正是 fencing token 这个名词的来源。
16.2.9 选举与共识：为什么异步系统中的选举不可能
讲义给出的归约：“如果选举可解，那么共识也可解！” —— 先选举出一个进程 $P_i$，然后用 $P_i$ 的 id 的最后一位作为共识决定。更常见的表述是：有了一个唯一的、所有存活进程都认可的 leader，就把它当作共识的”杰出提议者”：每个进程把自己的提案发给 leader，leader 选一个值（例如多数值）沿可靠广播发回，所有人采纳——Agreement、Validity、Termination 全部满足。因此 选举至少和共识一样难。
结论（FLP 的直接推论）：在纯异步系统模型中，只要有一个进程可能崩溃，就不存在一个协议能同时保证 (1) 永远只选出一个 leader、(2) 所有存活进程都认可它、(3) 一定终止。这就是讲义所说的：“既然共识在异步系统中不可能，那么选举也不可能”。课堂上的另一个等价表述是：“完美故障检测（Perfect Failure Detection）、领导者选举、共识”这三者难度相当（都在异步系统中不可解）。
- 那工程上怎么办？三条出路：
- 只要求”最终（eventually）”选出一个 leader：允许临时的
Null、允许临时的分歧、允许在任意长的有限时间内不选出——这恰好就是讲义给安全性的”或Null“留的口子。纯异步系统可以做到”最终选举”，只要有最终准确的故障检测器（weakest failure detector $\diamond W$，Chandra–Toueg，详见 Lecture 5–6 的故障检测器分类）。 - 引入部分同步假设（partial synchrony）：假设”系统大部分时候是同步的，只是偶尔异步”（GST，全局稳定时间之后延迟有界）。Raft/Paxos 的超时机制正是为这个模型设计的，它们的活性是”最终”的、概率性的，而安全性是绝对的。
- 随机化（randomization）：用随机退避/随机超时打破对称性，让”两个候选人永远平票”的概率为零——Raft 的随机化选举超时就是这一路的工程化身。
- 只要求”最终（eventually）”选出一个 leader：允许临时的
- 一句话总结本节：安全性可以做到绝对（靠 quorum 交集），活性只能在”最终”的意义上做到（靠超时 + 随机化）。任何声称”我保证在任何网络条件下都立刻选出唯一 leader”的说法，一定在偷换假设。
16.3 算法伪代码与正确性分析
算法 16.3.1：Bully 算法（霸道算法）
假设与系统模型
- 同步系统模型：消息延迟有上界 $d_{max}$，单个进程步长（处理时间）有上界 $t_{max}$。
- 超时阈值必须覆盖一个最坏往返：$T_{out} > 2d_{max} + t_{max}$（
ELECTION去 +OK回 + 处理）。这是 Bully 全部安全性论证的唯一硬假设——它把”超时未收到OK“变成了”对方确实已崩溃”。讲义给出的 $5$ 个消息传输时间正是这个界的一个具体取值。 - 故障模型：crash-recovery（崩溃后可能恢复；恢复后易失状态丢失）。
- 通道：可靠、不丢失、最终送达；每个进程知道全体成员的 id。
- 故障检测器：心跳 + 超时。
T_leader是”多久收不到 leader 心跳就认定 leader 失效”的阈值。
伪代码
process P_i: # 每个进程都运行同一份代码
elected : 认定的 coordinator（初值 = 配置中的已知 leader，可为 Null）
leader_hb : 最近一次收到 leader 心跳的时刻（初值 = 启动时刻）
in_elect : 布尔，我是否正处于一轮选举中
stage : "WAIT_OK" | "WAIT_COORD" | None
deadline : 当前阶段的截止时刻
higher() = { P_j | id_j > id_i } lower() = { P_j | id_j < id_i }
# ---------- 事件 1：故障检测器报告 leader 失效 ----------
upon (elected != Null) and (elected != self) and (now - leader_hb > T_leader):
elected <- Null
start_election()
# ---------- 事件 2：崩溃恢复 / 启动时不知道 leader ----------
upon (elected == Null) and (not in_elect):
start_election()
# ---------- 事件 7：超时（先处理，因为它可能改变状态）----------
upon (in_elect == True) and (now > deadline):
if stage == "WAIT_OK": # 没有任何更高者应答 => 我是最高存活者
become_leader()
else: # 收到过 OK 却没人公告 => 重开一轮选举
start_election()
# ---------- 事件 3：收到 ELECTION ----------
upon receive ELECTION from P_j:
if id_i > id_j: # 我更高 => 无条件压制对方
send OK to P_j
if elected == self: # 我已是 coordinator：顺手公告
send COORDINATOR(self) to P_j
else if (not in_elect):
start_election() # 讲义口径：自己也发起一轮（级联的根源）
else:
discard # 按协议不会发生（ELECTION 只发给更高 id）
# ---------- 事件 4：收到 OK ----------
upon receive OK from P_j:
if (in_elect == True) and (stage == "WAIT_OK"):
stage <- "WAIT_COORD" # 上面还有人，退让并等公告
deadline <- now + T_coord
# ---------- 事件 5：收到 COORDINATOR ----------
upon receive COORDINATOR(id_k) from P_j:
if id_k >= id_i or elected == Null: # 只接受"不低于自己"的公告（见 16.7 陷阱 4）
elected <- id_k
in_elect <- False; stage <- None
leader_hb <- now
# ---------- 事件 6：心跳 ----------
upon receive HEARTBEAT from P_j where id_j == elected:
leader_hb <- now
# leader 自己：每 T_hb 向所有进程广播一次 HEARTBEAT
# ---------- 选举入口 ----------
procedure start_election():
if elected == self: return # 我已经是 leader，不必再选
in_elect <- True; stage <- "WAIT_OK"; elected <- Null
deadline <- now + T_out
if higher() == {}: # 我知道自己是全局最高 id
become_leader(); return
for each P_j in higher():
send ELECTION to P_j
procedure become_leader():
in_elect <- False; stage <- None; elected <- self
leader_hb <- now
for each P_j in lower(): # 向所有更低 id 广播公告
send COORDINATOR(self) to P_j
算法逻辑解说（走一遍讲义的例子）
组成员 {N3, N5, N6, N12, N32, N80}，当前 leader N80 崩溃，N3 的心跳超时最先触发（对应 16.2.4 的时序图）：
N3事件 1：elected == N80，now - leader_hb > T_leader⇒elected <- Null，进入start_election。higher() = {N5, N6, N12, N32, N80}，于是发 5 条ELECTION（发给 N80 的那条石沉大海）。N5/N6/N12/N32事件 3：各自的 id 都大于N3⇒ 各回一条OK；同时它们都没有在选举中，于是各自调用start_election——级联开始：N5向{N6,N12,N32,N80}发 4 条，N6向{N12,N32,N80}发 3 条，N12向{N32,N80}发 2 条，N32向{N80}发 1 条。于是全组发出的ELECTION条数恰好是 $5+4+3+2+1=15=\frac{N(N-1)}{2}$——最坏情形的”三角形”被完整填满（$\sum_{i=1}^{N-1} i$），这就是 $O(N^2)$ 的来源。N3事件 4：收到第一个OK后进入WAIT_COORD，把主动权让给更高的进程。N32的最后一跳：N32只向N80发了ELECTION，而 N80 已崩溃；T_out之后N32的WAIT_OK超时 ⇒become_leader，向{N3,N5,N6,N12}广播COORDINATOR(N32)。- 所有人事件 5：收到公告后
elected <- N32，in_elect <- False；N32开始发心跳，选举结束。
正确性论证
引理 1（
OK的压制性）：若进程 $Q$ 在时刻 $t$ 之前一直存活，且 $id_Q > id_P$，那么 $P$ 在 $t$ 之前发出的每一条ELECTION都会在 $2d_{max}+t_{max}$ 内收到 $Q$ 的一条OK。 证明：$Q$ 收到ELECTION时id_Q > id_P成立，按事件 3 的第一分支，$Q$ 无条件回OK——这条规则不依赖于 $Q$ 是 follower、候选人还是已经是 leader，也不依赖于 $Q$ 是否正在选举中。$Q$ 存活且通道可靠 ⇒ 消息在 $t_{max}+d_{max}$ 内被处理并发回，OK再过 $d_{max}$ 到达 $P$。由假设 $T_{out} > 2d_{max}+t_{max}$ 可知它严格早于 $P$ 的deadline到达。∎
引理 2（称王的两个必要条件）：进程 $P$ 调用
become_leader时，以下两条至少成立一条： (a)higher() == {}（$P$ 是全局最高 id）； (b) $P$ 向higher()中每一个进程都发出过ELECTION，且在 $T_{out}$ 内一条OK都没收到。 证明：become_leader只在两个地方被调用——start_election中higher()=={}的分支（即 (a)），以及事件 7 的WAIT_OK超时分支。后者的前置条件是in_elect == True且stage == "WAIT_OK"，而stage只有在”higher()=={}“或”已向所有更高者发过ELECTION并进入WAIT_OK“两种情况下才为WAIT_OK；既然此时higher() != {}，就是”发全了并且超时未收到任何OK“，即 (b)。∎
定理 1（安全性）：在 $T_{out} > 2d_{max}+t_{max}$ 的同步模型下，不存在一个时刻同时有两个进程自认为 leader。 证明：反设存在时刻 $\tau$，进程 $P$ 与 $Q$ 都满足
elected == self，不妨设 $id_P < id_Q$。 每个进程只在become_leader中把elected设为自身，且start_election在elected == self时直接返回（不会重开选举），因此 $P$ 与 $Q$ 各自在一个时刻 $t_P, t_Q \le \tau$ 称王并维持到 $\tau$；特别地，$Q$ 在 $[t_P - T_{out} - d_{max},\ \tau]$ 这段区间内一直存活（否则它不可能在 $\tau$ 仍是 leader）。 对 $P$ 应用引理 2：$P$ 不满足 (a)（因为 $id_Q > id_P$ 说明存在更高的 id），故满足 (b)：在某个时刻 $t_s \in [t_P - T_{out}, t_P]$ 它向higher()中的每个进程发过ELECTION，且此后 $T_{out}$ 内没有收到OK。由于 $id_Q > id_P$，$Q \in$higher()，所以 $Q$ 也收到了这条ELECTION；由引理 1（$Q$ 在该区间存活），$P$ 必然在 $t_s + 2d_{max} + t_{max} < t_s + T_{out}$ 之前收到 $Q$ 的OK，与 (b) 矛盾。∎
推论（崩溃恢复不破坏安全性）：设崩溃的进程 $Q$ 在 $P$ 当上 leader 之后恢复，且 $id_Q > id_P$（$Q$ 是更高的 id，所以当初 $P$ 能当上 leader，只是因为 $Q$ 当时是死的）。$Q$ 恢复后发起选举：它向
higher()发ELECTION，T_out内收不到OK（更高者都死了），于是Q宣布自己是 leader 并向所有更低 id（包括 $P$）发COORDINATOR；$P$ 收到后按事件 5 更新elected <- Q、撤销自己的 leader 身份。结论：最终仍然只有一个 leader，但它不是”瞬时”的——从 $Q$ 宣布到 $P$ 处理完公告之间存在一个极短的”双 leader 窗口”（一个 RTT 的量级）。要彻底消除这个窗口，就必须引入 quorum 或 fencing（见 16.3.5、16.3.6 与 16.7 的陷阱 6）——这是”$T_{out}$ 再大也没用”的那一类问题。
定理 2（活性）：若在某个时刻之后不再有新的崩溃，且同步模型的延迟假设成立，则选举在最坏 $O(N)$ 轮、$5$ 个消息传输时间内终止，且所有非故障进程的
elected都指向同一个进程。 证明（分三步）： ① 一定有人发起选举。 对每个非故障进程，若elected == Null，事件 2 会在下一个轮询周期触发start_election；若elected != Null，则该 leader 要么存活（那就已经有一个 leader 了，对存活进程而言”选举”实际上已经完成），要么已崩溃 ⇒ 它的心跳停止 ⇒ 最多 $T_{leader}$ 之后，所有以它为 leader 的非故障进程触发事件 1。因此有限时间内必然有进程进入选举，或者系统中已经存在一个存活 leader。 ② 最高 id 的存活进程 $P_{max}$ 必然当选。 若 $P_{max}$ 已经在之前当选并存活，则步骤 ③ 已经完成。否则 $P_{max}$ 发起（或参加）一轮选举；由”$P_{max}$ 是存活者中 id 最高的”可知higher()中全部是崩溃进程，它们不会发送任何消息，因此 $P_{max}$ 在WAIT_OK阶段必然等到deadline超时（注意：这里依赖”不再有新崩溃”的反面——即”崩溃者不会复活并发消息”，而崩溃恢复者一旦复活就会走它自己的一轮选举，被 $P_{max}$ 的OK/COORDINATOR压制），从而调用become_leader。从发起到称王的延迟 $\le T_{out} + t_{max}$。 ③ 所有人最终接受它。become_leader向所有更低 id 广播COORDINATOR；所有存活进程的 id 都不高于 $P_{max}$（因为 $P_{max}$ 是存活者中最高），因此每一条公告都能送达，接收者在 $d_{max}$ 内更新elected。任何在WAIT_COORD阶段超时的进程会重开一轮选举，但它重开后的ELECTION会再次被 $P_{max}$（以及其它更高者）用OK压制，最终在有限轮内收敛（因为每轮之后”知道 leader 的进程集合”单调增大，且 $P_{max}$ 的公告是确定会到达的）。∎
复杂度
| 指标 | 结果 | 说明 |
|---|---|---|
| 消息复杂度（最坏） | $N^2-N-1 = O(N^2)$ | $N(N-1)/2$ 条 ELECTION + $N(N-1)/2$ 条 OK + $N-1$ 条 COORDINATOR；$N=3,5,8,12$ 时为 $5,19,55,131$ |
| 消息复杂度（最好） | $O(N)$ | 次高 id 检测到故障 ⇒ 只广播 $N-2$ 条 COORDINATOR；最高 id 发起 ⇒ 0 条 ELECTION |
| 稳态开销 | 每 $T_{hb}$ 一轮 $O(N)$ 条心跳 | leader 必须持续广播心跳，否则被误判 |
| 时间/轮次复杂度 | $O(N)$ 轮，最坏 5 个消息传输时间 | 级联深度最多 $N$ 层；实际延迟通常由 $T_{out}$ 主导 |
| 空间复杂度 | 每进程 $O(N)$ | 需要保存全体 id（全连接假设） |
| 容错 | 任意 $f \le N-1$ 个崩溃（同步模型下） | 但网络分区时会脑裂（见 16.4.3 的实验） |
算法 16.3.2：Chang-Roberts 环形选举（单向环）
假设与系统模型
- $N$ 个进程组成单向逻辑环 $p_0 \to p_1 \to \dots \to p_{N-1} \to p_0$，每个进程只与后继通信，消息只向一个方向传递。
- 通道可靠且 FIFO（同一对邻居之间不乱序）；选举过程本身不依赖超时（超时只用于”发现 leader 故障”）。
- 故障模型：crash-stop（环上任何节点崩溃都会断环，需要环修复/成员管理配合）。
- 每个进程知道自己的后继与自己的 id。
伪代码
process P_i: # succ(i) = 环上的下一个进程
elected : 认定的 leader（初值 = 旧 coordinator，可为 Null）
forwarded : 是否已经发出过"以自己 id 替换后"的 ELECTION
am_coord : 是否已成为 coordinator
seen_init : 见过的最高发起者 id 缓存（多发起者抑制用）
# ---------- 发起（任何发现 leader 故障的进程，或恢复后不知道 leader 的进程）----------
procedure start_election():
send ELECTION(value = my_id, init = my_id) to succ(i)
forwarded <- True
# ---------- 收到 ELECTION ----------
upon receive ELECTION(value = v, init = k) from pred(i):
if seen_init != Null and k < seen_init: # 压制更低 id 发起者的选举轮次
discard; return
seen_init <- max(seen_init, k)
if v == my_id: # 绕环一周回到我 => 我是环上最大
if not am_coord:
am_coord <- True; elected <- my_id
send ELECTED(my_id) to succ(i) # 宣布胜利，沿环公告
elif v > my_id: # 别人比我大 => 原样转发
send ELECTION(v, k) to succ(i)
elif not forwarded: # 我更大且还没转发过 => 替换成自己的 id
send ELECTION(my_id, k) to succ(i); forwarded <- True
else: # 已转发过更大的 id：这条不可能获胜
discard
# ---------- 收到 ELECTED ----------
upon receive ELECTED(k) from pred(i):
elected <- k
if k != my_id: # 协调者自己不必再转发
send ELECTED(k) to succ(i)
算法逻辑解说
以 16.2.6 的逐跳表为例：N3 发起后，纸条上的 id 依次是 3 → 12 → 12 → 12 → 32 → 80（被更大的进程”接手”后就变大），然后 80 原样绕行 6 跳回到 N80 自己手里，N80 立刻判定”我是最大者”，发出 ELECTED(80) 并沿环传播，每个进程把 elected 设为 80。整个过程只有 N80 的一条消息完成了整圈。这就是”只有最大者的消息能绕环一周”的含义。
正确性论证
引理 3（出边值的单调下界）：任何进程 $J$ 转发出去的
ELECTION消息所携带的值 $v_{out}$ 都满足 $v_{out} \ge id_J$。 证明：分三种情形——(i) 是 $J$ 自己发起的，$v_{out} = id_J$；(ii) 原样转发，此时要求 $v_{in} > id_J$，于是 $v_{out} = v_{in} > id_J$；(iii) 替换后转发，$v_{out} = id_J$。∎
引理 4（值的单调不减）：沿环的每一跳，消息携带的值不会变小（$v_{out} \ge v_{in}$），因为”原样转发”与”替换”都只可能保持或增大它。∎
定理 3（安全性：至多一个 coordinator，且必为最大 id）：若进程 $P_k$ 收到一条 $v = id_k$ 的
ELECTION消息（即它判定自己胜出），则 $P_k$ 是环上 id 最大的进程。 证明：消息从 $P_k$ 出发又回到 $P_k$，说明它走过了环上的每一个节点——注意：一条消息若在任何节点被discard（情形：$v < id_J$ 且 $J$ 已转发过），它就会消失，不可能再回到 $P_k$。因此环上每个节点 $J$ 都转发过这条消息。由引理 3，在该跳上 $v_J \ge id_J$；由引理 4，值沿路径单调不减，而最终到达 $P_k$ 的值恰好是 $id_k$，因此在每一跳上都有 $id_J \le v_J \le id_k$，即所有节点（包括 $P_k$）的 id 都不超过 $id_k$。∎ 推论：（1）不可能有两个进程都收到自己的 id（否则两者互为最大，矛盾）⇒ 至多一个 coordinator；（2）无论谁发起选举，胜出者都是同一个进程（最大 id 者）⇒ 选举结果与发起者无关（满足讲义的调用规则）；（3）多个进程同时发起时，每一轮都可能有某个进程”胜出”，但它们只可能全是同一个 $P_{max}$，而且am_coord标志保证它只公告一次 ⇒ 仍然只有一个 leader。
定理 4（活性：无故障环中在 $O(N)$ 轮内终止）：在无故障的单向环中，任意一次选举最多经过 $3N-1$ 个消息传输时间完成。 证明：设 $P_{max}$ 是环上最大 id。(1) 任何一条
ELECTION消息在每一跳上要么被替换（值变大，一次性事件，最多发生 $N-1$ 次）、要么被丢弃（消息消失）、要么继续前进；因此每条消息最多走 $N$ 跳就会终止。(2) $P_{max}$ 自己的那条ELECTION必然能走满一圈：丢弃只发生在 $v < id_J$ 且 $J$ 已转发过时，而 $v = id_{max}$ 不小于任何 $id_J$，所以沿途每个节点都只能原样转发；$P_{max}$ 发起时已把forwarded置真，因此环上始终有它的这条消息。(3) 由定理 3，唯一能完成整圈的就是 $id_{max}$，于是 $P_{max}$ 在消息走完一圈时（$\le N$ 跳）成为 coordinator，随后ELECTED再走 $\le N$ 跳。最坏情况下（发起者恰是 $P_{max}$ 的环后继）的消息数上界是 $(N-1) + N + N = 3N-1$，即完成时间 $3N-1$ 个消息传输时间。∎
复杂度
| 场景 | 消息数 | 说明 |
|---|---|---|
| 单个发起者，最好 | $2N$ | 发起者自己就是最大 id：ELECTION 绕一圈 + ELECTED 绕一圈 |
| 单个发起者，最坏 | $3N-1$ | 发起者是最大 id 的环后继：$(N-1)+N+N$ |
| 多发起者（无抑制） | $O(N^2)$；实测在 id 降序排列时恰为 $\frac{N^2+3N}{2}$ | $N$ 个发起者 × 每条消息最多 $N$ 跳 |
| 多发起者（含发起者抑制） | 只有最高 id 发起者的那一轮跑完，$O(N)$ | 需要缓存发起者 id |
| 期望复杂度（id 随机排列） | $O(N\log N)$ | 经典结论：只有”记录最大值”的进程需要走远 |
| 时间 | $O(N)$ 轮 / 最多 $3N-1$ 个消息传输时间 | 环上无法并行于多个方向（除非双向环） |
| 空间 | 每进程 $O(1)$（多发起者抑制时为 $O(1)$ 缓存 + $O(1)$ 标志） | 不需要知道全体成员！只需后继 |
算法 16.3.3：Hirschberg–Sinclair 双向环选举（$O(N\log N)$）
假设与系统模型：环是双向的（每个进程有左右两个邻居）；可靠 FIFO 通道；异步但按阶段（phase）组织（阶段边界由”探测消息返回”隐式界定）；crash-stop。
伪代码（框架）
process P_i:
candidate : 布尔，我是否还在竞选（初值 True）
winner : 已选出的最大 id（初值 Null）
for k = 0, 1, 2, ... while candidate: # 阶段 k，探测半径 R = 2^k
send PROBE(id = my_id, k, dir = left) to left neighbor
send PROBE(id = my_id, k, dir = right) to right neighbor
upon receive PROBE(v, k, dir) from 方向 d 的邻居:
if v > my_id:
# 探测者比我小 => 我不回应（它在这一阶段"失败"）
if candidate and 我尚未在本阶段向外发过 id:
send PROBE(my_id, k, 相反方向 d') 给另一侧 # 借道把更大的 id 送回去
discard
else:
if 已走满 R 跳: send PROBE(v, k, 反向) 回去（沿原路返回）
else: send PROBE(v, k, 同向) 继续前进（跳数 +1）
upon receive 自己发出的 PROBE 回到自己（走满 R 跳且没有被更大的 id 拦下）:
if R >= N: # 已经覆盖整个环
winner <- my_id; candidate <- False # 我是全局最大
send LEADER(my_id) 沿环广播（双向）
else:
继续下一阶段 k+1 # 我赢得了这一阶段
# 若我的 PROBE 没有返回（被更大者拦下且未回送）=> candidate <- False，退出竞选
算法逻辑解说与正确性
- 不变式（候选者收缩）：一个进程在第 $k$ 阶段仍然是候选者，当且仅当在它左右各 $2^k$ 跳的范围内没有比它 id 更大的进程。因为探测消息只有”沿途所有节点的 id 都不大于 $v$”时才能走满 $2^k$ 跳并返回；任何更大的节点都会把它拦下。
- 正确性（安全性）：全局最大 id 的进程 $P_{max}$ 在任何阶段都不会被拦下（没有比它更大的 id），因此它会一路赢得所有阶段，在 $R \ge N$ 时确认自己是最大者并广播。相反，任何非最大者 $P_j$ 迟早会在某个半径内遇到 $P_{max}$（半径加倍后 $R \ge$ 两者间的环上距离）而被拦下、退出竞选。所以唯一幸存者必是 $P_{max}$。
- 活性：阶段 $k$ 的候选者数量每轮至少减半（两个候选者若在半径 $2^k$ 内相遇，只有较大的那个能留下），因此经过 $O(\log N)$ 个阶段就只剩一个候选者，然后它广播 LEADER ⇒ 终止。
- 复杂度：第 $k$ 阶段，每个幸存候选者向两个方向各发一条探测、每条至多走 $2^k$ 跳并返回，即每条探测 $O(2^k)$ 条消息；由于幸存者数 $\le N/2^k$（每轮至少减半），第 $k$ 阶段的总消息数 $O(2^k \cdot N/2^k) = O(N)$。总阶段数 $O(\log N)$ ⇒ 总消息复杂度 $O(N \log N)$。
- 代价：需要双向环与”跳数计数”；实现比 Chang-Roberts 复杂；对动态成员变更的容忍度更低。
算法 16.3.4：异步系统中的”最终”选举（eventual leader election）
假设与系统模型：纯异步（无时钟上界、无延迟上界）；crash-recovery；通道可靠但延迟无界；不要求任何同步假设。代价是放弃”绝对唯一”：只保证最终收敛（eventual convergence），不保证在收敛之前不会出现多个 leader。
伪代码（基于 gossip 的候选者传播 + 超时提升 epoch）
每个进程 P_i 维护：
cand = (epoch, id) # 我支持的候选者；比较用字典序 (epoch, id)
hb = 最近一次收到"比我的 cand 更大的通告"的时刻
T_gossip, T_leader # 两个超时（纯异步下它们只是启发式常量）
upon 每 T_gossip 到期: # 反熵：随机挑 k 个成员传播
for each P_j in random_sample(k):
send GOSSIP(cand) to P_j
upon receive GOSSIP(c) from P_j: # 只接受更大的候选者
if c > cand: # 单调上升：不会"回退"
cand <- c; hb <- now
for each P_l in random_sample(k): # 好消息定向扩散
send GOSSIP(cand) to P_l
upon 每 T_leader 到期 且 (now - hb > T_leader): # 我怀疑 leader 死了
cand <- (cand.epoch + 1, my_id) # epoch 加一：宣布"我竞选"
for each P_j in random_sample(k):
send GOSSIP(cand) to P_j
# 每个进程把"cand 的拥有者"当作自己认定的 leader；不额外做任何全局协调
算法逻辑解说
- 每个进程的候选值是单调不减的（只接受更大的 $(epoch, id)$），且候选值取自一个有限的全序集合（epoch 有限增长、id 有限个），因此不可能无限上升——这就是收敛性的基础。
- 好消息的扩散是反熵（anti-entropy）：每个周期向 $k$ 个随机成员推送，属于流行病传播（epidemic），$O(\log N)$ 个周期即可覆盖全网（详见 Lecture 4 的 gossip）。
- 为什么”最终”能收敛：假设系统在某个时刻之后网络重新连通且不再有进程超时（即没有新的 epoch 提升），那么此刻全网存在的最大候选值 $c^$ 会通过 gossip 在每个周期击败所有更小的候选值；$O(\log N)$ 个周期后所有存活进程的
cand都变成 $c^$，即所有人认同同一个 leader。 - 为什么没有安全性：在收敛之前、或者在分区期间，每个分区都可以独立提升 epoch 并产生自己的候选者。分区期间”两个 leader 同时存在”是允许的，只要上层应用不依赖”唯一写者”。这正是这套机制只适合”软 leader”（后台修复任务、监控汇总、缓存预热）的原因。
正确性论证（形式化）
- Agreement（最终）：定义势函数 $\Phi = \max_i \text{cand}_i$（按全序）。每次
GOSSIP只会把接收者的cand提升到更大值，因此 $\Phi$ 单调不减且有上界；一旦”超时提升 epoch”停止，$\Phi$ 固定为 $c^$。由 gossip 的流行病性质，在无故障、全连通的系统中，$c^$ 经过 $O(\log N)$ 轮覆盖所有进程（每轮一个进程以常数概率被”感染”，标准证明用 Chernoff 界）。因此最终所有存活进程的 leader 视图一致。 - 没有 Safety：构造反例——两个分区各自超时提升 epoch，各自产生候选者 $c_1, c_2$，两侧各自认为自己的候选者是 leader。这就是”异步系统只能做最终选举”的代价。
- 活性：只要网络最终连通、故障最终停止，收敛是概率 1发生的；但如果故障永不停止（每一轮都有节点超时提升 epoch），则可能永远没有稳定的 leader——这与讲义”只有当故障停止时才会最终选出 leader”完全一致。
复杂度：每周期 $O(kN)$ 条消息（$N$ 个进程各发 $k$ 条）；收敛时间 $O(\log N)$ 个周期；空间 $O(1)$/进程（只保存一个候选值）。它是本章所有算法中唯一不需要同步假设的，代价是没有强安全性。
算法 16.3.5：Raft 风格基于 quorum 的选举
假设与系统模型
- 部分同步（partially synchronous）：系统大部分时间同步，但允许任意长的异步期（GST 之后延迟有界）。
- crash-recovery：
currentTerm、votedFor、日志必须持久化（否则重启后会重复投票，破坏安全性）。 - 通道可靠（TCP）且不重复投递；$N$ 个节点，quorum $= \lfloor N/2\rfloor + 1$。
- 每个节点维护一份日志（
lastLogIndex、lastLogTerm），用于选举限制。
伪代码
persistent: currentTerm = 0; votedFor = None; log = []
volatile: state = "follower"; leaderId = None
electionDeadline = now + random(T, 2T) # 随机化，避免同时竞选
# ---------- 任期是逻辑时钟：见到更高任期立即降级 ----------
upon 收到任何 RPC(term) 且 term > currentTerm:
currentTerm <- term; votedFor <- None; state <- "follower"
# ---------- 选举超时 => 竞选 ----------
upon (now > electionDeadline) and (state != "leader"):
state <- "candidate"
currentTerm <- currentTerm + 1
votedFor <- self # 先投自己
votes <- {self}
electionDeadline <- now + random(T, 2T) # 重新随机化
for each P_j != self:
send RequestVote(term = currentTerm,
lastLogIndex = log.lastIndex,
lastLogTerm = log.lastTerm) to P_j
# ---------- 投票方（RequestVote 处理）----------
upon receive RequestVote(term, cid, lli, llt) from P_j:
if term < currentTerm:
reply(term = currentTerm, granted = False); return
up_to_date = (llt > log.lastTerm) or (llt == log.lastTerm and lli >= log.lastIndex)
if (votedFor in {None, P_j}) and up_to_date: # 一个任期最多一票 + 日志至少一样新
votedFor <- P_j
electionDeadline <- now + random(T, 2T) # 授票相当于"承认有人在竞选"
reply(term = currentTerm, granted = True)
else:
reply(term = currentTerm, granted = False)
# ---------- 候选人（VoteGrant 处理）----------
upon receive VoteGrant(term) from P_j:
if state == "candidate" and term == currentTerm:
votes <- votes ∪ {P_j}
if |votes| >= floor(N/2) + 1: # 拿到多数派 => 当选
state <- "leader"; leaderId <- self
for each P_k != self:
send AppendEntries(term = currentTerm, entries = []) to P_k # 立即宣告
heartbeatDeadline <- now + T_hb
# ---------- leader 循环 ----------
upon 每 T_hb 到期: # 心跳维持权威
acks <- {self}
for each P_k != self:
send AppendEntries(term = currentTerm, entries = []) to P_k
if now > ackDeadline: # 结算上一轮心跳的确认
if |acks| < floor(N/2) + 1:
state <- "follower" # 拿不到多数派 => 退位
electionDeadline <- now + random(T, 2T)
else:
ackDeadline <- now + T_hb * 3
# ---------- follower 收到心跳 ----------
upon receive AppendEntries(term) from P_lead:
if term < currentTerm: reply(success = False); return
state <- "follower"; leaderId <- P_lead
electionDeadline <- now + random(T, 2T) # 心跳续期：我不会超时竞选
reply(success = True) # 这个 ACK 计入 leader 的多数派确认
算法逻辑解说（五节点一次成功的选举）
P1..P5，初始 leader P5（term 1）。P1 的随机超时最短，在 155 ms 触发竞选：term <- 2，自投一票，向 P2..P5 发 RequestVote(term=2, lastLogIndex=7, lastLogTerm=1)。P2、P3、P4 在 term 2 都还没投过票、且日志不长于 P1 ⇒ 全部投赞成票；P5 的日志更长（或它先看到更高的 term 而退位）⇒ 视具体情形拒绝或降级。P1 收齐 3 票 $= \lfloor 5/2\rfloor+1$ 后成为 term 2 的 leader，立即向所有人发 AppendEntries 心跳；follower 收到心跳后重置自己的随机超时，于是 P2（原本 210 ms 后要竞选）不会再发起一轮。随机化超时 + 心跳续期这两件事合起来，让”选举风暴”的概率极低。
正确性论证
定理 5（同一任期至多一个 leader —— quorum 交集）：在任期 $t$ 中不可能有两个候选人都收齐多数派选票。 证明：设 $C_1 \ne C_2$ 都以任期 $t$ 当选，$Q_1, Q_2$ 分别是给它们投票的节点集合，$\vert Q_1\vert \ge \lfloor N/2\rfloor+1$，$\vert Q_2\vert \ge \lfloor N/2\rfloor+1$。则 $\vert Q_1\vert + \vert Q_2\vert \ge N+1 > N$，由抽屉原理 $Q_1 \cap Q_2 \ne \emptyset$，取 $P \in Q_1 \cap Q_2$。$P$ 在任期 $t$ 内投了两票，但规则要求”任期 $t$ 内
votedFor一旦被设置就不再改变，且该变量持久化到稳定存储”，因此 $P$ 不可能既投给 $C_1$ 又投给 $C_2$ ⇒ 矛盾。∎ 注：两个多数派必然相交这一点与网络是否分区无关——这正是 quorum 比”最高 id 胜出”强的地方：“最高 id”是一个局部事实（只看 id 表），”多数派交集”是一个全局事实（不依赖任何超时判断）。
定理 6（分区少数派永远选不出 leader ⇒ 不会脑裂）：设网络被划分为 $G_1, G_2$，且 $\vert G_1\vert < \lfloor N/2\rfloor+1$。则 $G_1$ 中的候选人所获票数至多 $\vert G_1\vert <$ quorum，永远无法当选。 证明：候选人的选票只可能来自能把
VoteGrant送达它的节点；分区之间消息全部丢失，所以 $G_1$ 中候选人的票数上界是 $\vert G_1\vert $。由 $\vert G_1\vert < \lfloor N/2\rfloor+1$ 即得。∎ 推论：任一时刻，最多只有一个分区能够产生 leader；结合定理 5，全局至多一个”当前任期的合法 leader”。
定理 7（选举限制保证已提交的条目不会丢失）：设条目 $e$ 在任期 $t$ 被提交（即被复制到某个多数派 $Q$ 上）。则任何在 $t$ 之后当选的 leader $L$ 的日志都包含 $e$。 证明（直观版）：$L$ 当选必须获得多数派 $Q^{\prime}$ 的选票，$\vert Q\vert + \vert Q^{\prime}\vert > N$ ⇒ $Q \cap Q^{\prime} \ne \emptyset$，取 $P \in Q \cap Q^{\prime}$。$P$ 拥有 $e$，且 $P$ 只在”候选人的日志至少和自己一样新”时才投票，因此 $L$ 的日志 $\ge P$ 的日志，即 $L$ 拥有 $P$ 的全部条目（日志匹配性质），从而 $L$ 拥有 $e$。∎ 这条定理是”选举”与”复制安全”的接口：Bully 与环形选举只保证”选出一个 leader”，而 Raft 额外保证”选出的 leader 一定不会让已提交的数据回退”——这就是为什么强一致系统的选举必须带上日志约束。
定理 8（最终活性）：在部分同步模型下，若多数派节点最终存活且网络最终在 GST 后同步，则随机化超时会在有限时间内（概率 1）产生一个当选的 leader。 证明要点：(1) 每个 follower 的选举超时是 $[T, 2T]$ 上的独立随机量，因此”所有节点同时超时并瓜分选票、永远平票”的概率为 0——总存在一个超时最短的节点先成为候选人；(2) 由部分同步假设，GST 之后该候选人与多数派之间的请求/应答在一个有界的 $\delta$ 内完成；只要 $T$（最小选举超时）$\gg \delta$，它就能在收齐多数票之前不被别人的竞选打断；(3) 若选票被瓜分（无人过半），所有节点会在下一个随机超时后重新竞选，重复多次后必然有人成功（每次成功的概率有常数下界，重复独立试验 ⇒ 概率 1 最终成功）。∎
复杂度
| 指标 | 结果 | 说明 |
|---|---|---|
| 一次成功选举的消息数 | $O(N)$ | $N-1$ 条 RequestVote + 至多 $N-1$ 条 VoteGrant + $N-1$ 条心跳宣告（远优于 Bully 的 $O(N^2)$） |
| 失败/平票的选举 | 每轮再 $O(N)$ | 靠随机化超时把概率压到极低 |
| 稳态开销 | 每 $T_{hb}$ 一轮 $O(N)$ 条心跳 | $T_{hb}\approx 50\text{–}100$ ms |
| 选举延迟 | 超时 $(T \sim 2T)$ + 1 个 RTT | 通常几十到几百毫秒（$T\approx150\text{–}300$ ms）；Chubby 讲义口径：实践几秒、最坏 30 s |
| 容错 | 容忍 $\lfloor (N-1)/2 \rfloor$ 个崩溃 | $N=5$ 容忍 2 个；$N=3$ 容忍 1 个；不脑裂 |
| 空间 | $O(\text{log size})$ 持久化 + $O(N)$ 选举状态 | 关键在于 currentTerm、votedFor、日志必须落盘 |
算法 16.3.6：Fencing token / epoch 防护（存储层如何拒绝旧 leader 的写）
假设与系统模型：存在一个单调递增的 token 发放者（序列器 / 锁服务，其自身通过 quorum 或 Paxos 保证唯一性）；存储层可被改造，能在应用写之前检查 token；网络可能分区；允许同时存在两个自认为合法的 leader 客户端。
伪代码
# ---------- 序列器（由 quorum 选出的 leader 或 ZooKeeper/Chubby 提供）----------
sequence_number = 0 # 持久化、单调递增
procedure acquire_epoch(client_id):
sequence_number <- sequence_number + 1
persist(sequence_number) # 必须先落盘再返回
return sequence_number
# ---------- 存储层：带 fencing 的写 ----------
max_epoch_seen = 0 # 持久化
procedure write(value, epoch, client_id):
if epoch < max_epoch_seen:
return REJECT("stale epoch") # 旧 leader 的写被拒绝
max_epoch_seen <- epoch
apply(value) # 只有通过检查才落盘
return OK
# ---------- leader 的写路径 ----------
procedure leader_write(value):
if now > lease_expiry: # 租约到期 => 我已不再是 leader
step_down(); return "not leader"
reply <- send write(value, my_epoch, self) to storage
if reply == REJECT:
step_down() # 被 fencing 拒绝 => 我一定是过期的
# ---------- 执行轨迹（与 16.4.3 的代码输出一致）----------
# P5 取号 => epoch = 1；P5 写(余额=100, epoch=1) => 接受，max_epoch_seen = 1
# P2 取号 => epoch = 2；P2 写(余额=999, epoch=2) => 接受，max_epoch_seen = 2
# P5 再写(余额=50, epoch=1) => 1 < 2 => 拒绝（旧 leader 的写被拦下）
算法逻辑解说
- token 从哪来：Chubby 给每个锁的持有者一个 sequencer（内部含锁的世代号），客户端必须把 sequencer 随每个请求传给存储服务；ZooKeeper 用 zxid（事务 id）与 epoch；Raft 用 term；HDFS 的 NameNode HA 用 JournalNode 的 epoch/txid。它们都是”单调递增、能唯一标识一次任期“的整数或字节串。
- 为什么要单调：只有当”后来的 leader 的 token 一定大于先前的 leader”时，存储层才能用”拒绝比已知最大值小的 token”这一个简单规则把旧 leader 的写挡在门外。
正确性论证
不变式 1（序列器单调）：
sequence_number严格递增，且每次递增都先持久化后返回 ⇒ 即使序列器崩溃重启，也不会发出重复或更小的号。 不变式 2（存储层单调）：max_epoch_seen单调不减，且任何被接受的写都带有 $\ge$ 此前所有被接受的写的 token（因为接受的条件就是epoch >= max_epoch_seen）。 定理 9（旧 leader 无法破坏数据）：设 $L_{new}$ 在任期 $e_{new}$ 上成功写过至少一次。此后任何以 $e_{old} < e_{new}$ 发出的写都会在存储层被拒绝。 证明：$L_{new}$ 的写被接受后，max_epoch_seen >= e_new；由不变式 2，max_epoch_seen之后不会下降。因此任何 $e_{old} < e_{new} \le max\_epoch\_seen$ 的写都满足epoch < max_epoch_seen，被REJECT。∎ 限制（为什么 fencing 不能单独解决脑裂）：
- 它不阻止第二个 leader 的产生，只阻止它”生效”；
- 它只能保护经过存储层过滤的写——绕过存储层直写裸设备（或存储层不支持 token 检查）就完全失效；
- token 的可比性依赖单一序列器：如果脑裂的两侧各有一个锁服务，各自发的号不可比，fencing 立刻失效（所以要回到”锁服务本身必须用 quorum 选主”）；
- 它不解决读：两个 leader 同时提供读仍然可能返回不一致的数据；要一致读仍需 quorum 读或租约。
16.4 代码示例与分布式实现
下面三个程序都只用 Python 标准库（threading + queue.Queue 模拟进程与消息通道），自包含、可直接 python3 运行，随机种子固定为 random.seed(425)。
16.4.1 示例 1：Bully 算法完整实现（含审计断言与四个测试场景）
"""Bully 算法完整实现：threading + queue.Queue 模拟 N 个进程与消息通道。
含 (i) 正常选举 (ii) leader 崩溃重选 (iii) 低 id 抢跑被压制 (iv) 崩溃恢复，
全程用审计器断言"自称 leader 的进程集合"大小 <= 1，并统计消息数与 O(N^2) 对比。"""
import queue
import random
import threading
import time
random.seed(425)
HB_INTERVAL, HB_TIMEOUT = 0.02, 0.20 # leader 心跳间隔 / 判故障超时
OK_TIMEOUT, COORD_TIMEOUT = 0.20, 0.30 # 等 OK / 等 COORDINATOR 的超时
POLL, T0 = 0.02, time.time()
class Audit:
"""安全审计器：任何时刻至多一个进程自认为 leader。"""
def __init__(self):
self.lock = threading.Lock()
self.claims = set()
self.violations = []
def claim(self, pid):
with self.lock:
self.claims.add(pid)
if len(self.claims) > 1:
self.violations.append((round(time.time() - T0, 3), sorted(self.claims)))
def resign(self, pid):
with self.lock:
self.claims.discard(pid)
def check(self):
with self.lock:
assert len(self.claims) <= 1, "SAFETY VIOLATION: %s" % sorted(self.claims)
return sorted(self.claims)
class Network:
"""消息通道：每个进程一个 inbox 队列；向已崩溃进程发送的消息被丢弃。"""
def __init__(self, ids):
self.ids = list(ids)
self.boxes = dict((i, queue.Queue()) for i in self.ids)
self.alive = dict((i, True) for i in self.ids)
self.lock = threading.Lock()
self.sent = {"ELECTION": 0, "OK": 0, "COORDINATOR": 0, "HEARTBEAT": 0}
def send(self, src, dst, kind, **payload):
with self.lock:
self.sent[kind] = self.sent.get(kind, 0) + 1
if not self.alive[src] or not self.alive[dst]:
return False
msg = {"src": src, "kind": kind}
msg.update(payload)
self.boxes[dst].put(msg)
return True
def crash(self, pid):
with self.lock:
self.alive[pid] = False
while not self.boxes[pid].empty():
self.boxes[pid].get_nowait()
def restart(self, pid):
with self.lock:
self.alive[pid] = True
class Process(threading.Thread):
def __init__(self, pid, net, audit, initial_leader):
threading.Thread.__init__(self, daemon=True)
self.pid, self.net, self.audit = pid, net, audit
self.leader = initial_leader
self.last_hb = {}
self.in_election, self.stage, self.deadline = False, None, 0.0
self.running = True
self.count = {"ELECTION": 0, "OK": 0, "COORDINATOR": 0, "HEARTBEAT": 0}
self.recv = {"OK": 0}
if initial_leader is not None:
self.last_hb[initial_leader] = time.time()
def send(self, dst, kind, **payload):
self.count[kind] += 1
return self.net.send(self.pid, dst, kind, **payload)
def run(self):
while self.running:
if not self.net.alive[self.pid]:
time.sleep(POLL)
continue
try:
self.handle(self.net.boxes[self.pid].get(timeout=POLL))
except queue.Empty:
pass
if self.running and self.net.alive[self.pid]:
self.tick()
def stop(self):
self.running = False
def tick(self):
now = time.time()
if self.leader == self.pid and now - self.last_hb.get(self.pid, 0.0) > HB_INTERVAL:
self.last_hb[self.pid] = now
for p in self.net.ids:
self.send(p, "HEARTBEAT", leader=self.pid)
if self.leader is None and not self.in_election: # 启动引导 / 崩溃恢复后
self.start_election()
elif self.in_election and now > self.deadline:
if self.stage == "OK": # 无人比我高 => 我当 leader
self.become_leader()
else: # 等到 OK 却没等到 COORDINATOR
self.start_election()
elif self.leader != self.pid and not self.in_election:
if now - self.last_hb.get(self.leader, 0.0) > HB_TIMEOUT:
self.leader = None # 故障检测器报告 leader 失效
self.start_election()
def start_election(self):
if self.leader == self.pid:
return
self.in_election, self.stage = True, "OK"
self.leader = None
self.deadline = time.time() + OK_TIMEOUT
higher = [p for p in self.net.ids if p > self.pid]
if not higher: # 我知道自己是最高 id
self.become_leader()
return
for p in higher:
self.send(p, "ELECTION")
def become_leader(self):
self.in_election, self.stage, self.leader = False, None, self.pid
self.last_hb[self.pid] = time.time()
self.audit.claim(self.pid) # 审计：登记 leader 声明
for p in self.net.ids:
if p < self.pid:
self.send(p, "COORDINATOR", leader=self.pid)
def handle(self, msg):
kind, src = msg["kind"], msg["src"]
if kind == "OK":
self.recv["OK"] += 1
if kind == "ELECTION":
if self.pid > src: # 我更高 => 压制对方
self.send(src, "OK")
if self.leader == self.pid: # 我已是 coordinator，直接公告
self.send(src, "COORDINATOR", leader=self.pid)
elif not self.in_election:
self.start_election() # 讲义口径：自己也发起一轮
elif kind == "OK":
if self.in_election and self.stage == "OK":
self.stage, self.deadline = "COORD", time.time() + COORD_TIMEOUT
elif kind == "COORDINATOR":
self.leader = msg["leader"]
self.in_election, self.stage = False, None
self.last_hb[self.leader] = time.time()
self.audit.resign(self.pid)
elif kind == "HEARTBEAT":
self.last_hb[src] = time.time()
if self.leader is None or (self.leader != src and self.in_election):
self.leader, self.in_election = src, False
def build(ids, initial_leader):
audit, net = Audit(), Network(ids)
if initial_leader is not None:
audit.claim(initial_leader) # 配置写死的初始 leader 也是一次声明
procs = dict((i, Process(i, net, audit, initial_leader)) for i in ids)
for p in procs.values():
p.start()
return net, procs, audit
def view(net, procs):
return dict((i, procs[i].leader) for i in net.ids if net.alive[i])
def emsgs(net):
return sum(net.sent[k] for k in ("ELECTION", "OK", "COORDINATOR"))
def worst_case(n):
"""最坏情形：旧 leader（最高 id）崩溃，其余 N-1 个进程同时发起选举。"""
ids = list(range(1, n + 1))
net, procs, audit = build(ids, n)
time.sleep(0.25)
net.crash(n)
audit.resign(n)
for i in ids[:-1]:
procs[i].start_election()
time.sleep(1.2)
assert set(view(net, procs).values()) == {n - 1}
audit.check()
for p in procs.values():
p.stop()
return net.sent
if __name__ == "__main__":
print("=== (i) 从零启动：最高 id 的 P5 应成为 leader ===")
net, procs, audit = build([1, 2, 3, 4, 5], None)
time.sleep(0.7)
print(" leader 视图:", view(net, procs), " 审计:", audit.check())
assert set(view(net, procs).values()) == {5}
print(" ELECTION=%d OK=%d COORDINATOR=%d" % (net.sent["ELECTION"], net.sent["OK"],
net.sent["COORDINATOR"]))
print("=== (ii) 杀掉 leader P5：应选出存活者中最高 id 的 P4 ===")
base = emsgs(net)
net.crash(5)
audit.resign(5) # 崩溃进程无法再发消息，撤销其 leader 声明
time.sleep(0.9)
print(" leader 视图:", view(net, procs), " 审计:", audit.check())
assert set(view(net, procs).values()) == {4}
print(" 重选新增选举消息 = %d（最坏情形预测 N^2-N-1 = %d）" % (emsgs(net) - base, 5 * 5 - 5 - 1))
for p in procs.values():
p.stop()
print("=== (iii) 低 id 的 P1 抢先发起选举：应被更高的进程压制 ===")
net, procs, audit = build([1, 2, 3, 4, 5], 5)
time.sleep(0.3)
net.crash(5)
audit.resign(5)
procs[1].start_election() # P1 抢在别人前面发起
time.sleep(1.1)
print(" P1 发出 ELECTION=%d 收到 OK=%d 最终 leader=%s"
% (procs[1].count["ELECTION"], procs[1].recv["OK"], procs[1].leader))
print(" leader 视图:", view(net, procs), " 审计:", audit.check())
assert procs[1].leader == 4 and 1 not in audit.claims
print(" 选举消息总数 = %d" % emsgs(net))
for p in procs.values():
p.stop()
print("=== (iv) P3 崩溃后恢复：恢复者发起选举但被压制 ===")
net, procs, audit = build([1, 2, 3, 4, 5], 5)
time.sleep(0.3)
net.crash(3)
audit.resign(3)
time.sleep(0.4)
before = procs[3].count["ELECTION"]
net.restart(3)
procs[3].leader, procs[3].in_election = None, False # 易失状态丢失
procs[3].start_election()
time.sleep(0.6)
print(" P3 恢复后发出 ELECTION=%d 收到 OK=%d 最终 leader=%s"
% (procs[3].count["ELECTION"] - before, procs[3].recv["OK"], procs[3].leader))
print(" leader 视图:", view(net, procs), " 审计:", audit.check())
assert procs[3].leader == 5 and 3 not in audit.claims
for p in procs.values():
p.stop()
print("=== 消息复杂度实验：N-1 个进程同时发起选举 ===")
print(" N | ELECTION | N(N-1)/2 | OK | COORD | 合计 | N^2-N-1")
for n in (3, 5, 8, 12):
s = worst_case(n)
e, o, c = s["ELECTION"], s["OK"], s["COORDINATOR"]
print(" %2d | %5d | %5d | %3d | %5d | %4d | %6d"
% (n, e, n * (n - 1) // 2, o, c, e + o + c, n * n - n - 1))
print("所有场景通过：全程 |自称 leader 的集合| <= 1。")
【代码做什么？】
- 搭一个可崩溃的网络：
Network为每个进程准备一个queue.Queue作为 inbox；send()在投递前检查”发送者/接收者是否存活”，向已崩溃进程发送的消息被计为丢失——这模拟了”崩溃进程不再响应”这一事实。 - 实现 Bully 状态机：
Process线程的主循环是”取消息（最多阻塞POLL=20 ms）→ 处理 →tick()“。tick()负责三类超时：leader 心跳超时（触发选举）、WAIT_OK超时（这就是”没有更高者应答 ⇒ 我称王”那一行）、WAIT_COORD超时（重开一轮）。 - 审计断言：
Audit维护一个”当前自认为 leader 的进程集合”，become_leader时登记、收到COORDINATOR时撤销，check()在任何时刻断言集合大小 $\le 1$。这个断言就是 16.3.1 定理 1（安全性）的可执行版本。 - 跑四个场景：(i) 从零启动（无已知 leader，全部进程触发引导选举）；(ii) 杀掉 leader P5，验证选出存活者中最高 id 的 P4；(iii) 让最低 id 的 P1 抢先发起，验证它被更高的进程压制；（iv）让 P3 崩溃后恢复，验证恢复者发起选举但被当前 leader P5 压制。
- 统计消息数：
worst_case(n)让”旧 leader 崩溃 + 其余 $N-1$ 个进程同时发起选举”（讲义描述的最坏情形），在 $N=3,5,8,12$ 下统计ELECTION/OK/COORDINATOR的条数，并与 $N(N-1)/2$、$N^2-N-1$ 两个公式对照。
实际运行输出（一次真实运行）：
=== (i) 从零启动：最高 id 的 P5 应成为 leader ===
leader 视图: {1: 5, 2: 5, 3: 5, 4: 5, 5: 5} 审计: [5]
ELECTION=14 OK=14 COORDINATOR=10
=== (ii) 杀掉 leader P5：应选出存活者中最高 id 的 P4 ===
leader 视图: {1: 4, 2: 4, 3: 4, 4: 4} 审计: [4]
重选新增选举消息 = 19（最坏情形预测 N^2-N-1 = 19）
=== (iii) 低 id 的 P1 抢先发起选举：应被更高的进程压制 ===
P1 发出 ELECTION=4 收到 OK=3 最终 leader=4
leader 视图: {1: 4, 2: 4, 3: 4, 4: 4} 审计: [4]
选举消息总数 = 19
=== (iv) P3 崩溃后恢复：恢复者发起选举但被压制 ===
P3 恢复后发出 ELECTION=2 收到 OK=2 最终 leader=5
leader 视图: {1: 5, 2: 5, 3: 5, 4: 5, 5: 5} 审计: [5]
=== 消息复杂度实验：N-1 个进程同时发起选举 ===
N | ELECTION | N(N-1)/2 | OK | COORD | 合计 | N^2-N-1
3 | 3 | 3 | 1 | 1 | 5 | 5
5 | 10 | 10 | 6 | 3 | 19 | 19
8 | 28 | 28 | 21 | 6 | 55 | 55
12 | 66 | 66 | 55 | 10 | 131 | 131
所有场景通过：全程 |自称 leader 的集合| <= 1。
场景 (i) 的确切消息数会随线程调度在 10–14 条之间小幅波动（因为”谁先 tick”不确定，有的进程会在已经被公告压制之前多发起一轮）；但 leader 视图 与 审计: 两行在任何一次运行中都完全相同——这正是”安全性是确定的，消息数是随机的“这一分布式系统普遍规律的缩影。而 (ii)/(iii) 与复杂度实验是确定性的：$N=5$ 时重选恰好 19 条消息，与 $N^2-N-1$ 分毫不差。
【分布式机制透视】
- 进程 = 线程，通道 = 队列：真实系统中”进程 $P_i$ 到 $P_j$ 的消息”变成
boxes[j].put(msg)；线程之间不共享任何可变状态（除了带锁的审计器与网络计数器），这与真实进程”只能通过消息通信”的约束一致。 - 超时 =
time.time()的差值：tick()里的now - self.last_hb[...] > HB_TIMEOUT就是故障检测器，now > self.deadline就是”等待应答超时”。把HB_TIMEOUT调小就能制造误判（脑裂），调大就能制造长时间无 leader——你可以直接改这两个常量观察现象。 - 崩溃 =
alive[pid] = False+ 清空 inbox：这模拟了”崩溃进程不再处理任何消息、也不再发送心跳”。注意Network.send里先计数再判存活：这样”发给已崩溃进程的ELECTION“也会被计入 $N(N-1)/2$，与讲义口径一致。 - 恢复 =
alive[pid] = True+elected = None：这一步把”易失状态丢失”这一崩溃恢复模型的核心事实显式化了——恢复的进程不知道当前 leader，所以它会（也应该）发起一轮选举。 - 真实的对应物：
Heartbeat/COORDINATOR对应真实系统里的 leader 心跳；ELECTION/OK对应 Bully 的两个控制消息；Audit对应真实系统里”集群同一时刻只能有一个 active master”的运维断言（HDFS 用 ZK 的互斥锁、Chubby 用 sequencer 来实现同样的保证）。
【与理论的对应】
| 代码位置 | 对应 16.3.1 的伪代码 | 对应哪条论证 |
|---|---|---|
Process.tick() 的第一个 if | 事件 1（故障检测器） | 定理 2 步骤 ① |
Process.start_election() 中 if not higher | higher()=={} 分支 | 引理 2 条件 (a) |
tick() 中 stage == "OK" 的超时分支 | 事件 7 → become_leader | 引理 2 条件 (b) |
handle() 中 kind == "ELECTION" 无条件回 OK | 事件 3 | 引理 1（OK 的压制性）——整条安全性证明的心脏 |
handle() 中 ELECTION → elif not self.in_election: start_election() | 事件 3 的级联 | 引理 2 (b) + $O(N^2)$ 复杂度来源 |
Audit.claim/check | 无对应伪代码（工程增强） | 定理 1（安全性）的可执行断言 |
worst_case() 的统计打印 | — | 复杂度的实测验证：$N(N-1)/2$ 与 $N^2-N-1$ |
16.4.2 示例 2：Chang-Roberts 环形选举
"""Chang-Roberts 环形选举（单向环，无令牌）：threading + Queue 模拟。
验证：不论谁发起、多少人同时发起，最终只有最高 id 的进程胜出；
统计最好情形（最高 id 发起）与最坏情形（发起者是 leader 的环后继）的消息数。"""
import queue
import random
import threading
import time
random.seed(425)
POLL = 0.02
class Ring:
def __init__(self, order, counters):
self.order = list(order) # 顺时针顺序，后继 = 下一个
self.succ = dict((order[i], order[(i + 1) % len(order)]) for i in range(len(order)))
self.boxes = dict((i, queue.Queue()) for i in order)
self.counters = counters
self.lock = threading.Lock()
def send(self, src, kind, **payload):
dst = self.succ[src]
with self.lock:
self.counters[kind] = self.counters.get(kind, 0) + 1
msg = {"src": src, "kind": kind}
msg.update(payload)
self.boxes[dst].put(msg)
return dst
def quiescent(self):
with self.lock:
return all(b.empty() for b in self.boxes.values())
class Node(threading.Thread):
def __init__(self, pid, ring):
threading.Thread.__init__(self, daemon=True)
self.pid, self.ring = pid, ring
self.forwarded = False # 是否已经发出过"以自己 id 替换后"的 ELECTION
self.elected = None # 自己认定的 leader
self.is_coordinator = False
self.running = True
self.inbox = ring.boxes[pid]
def run(self):
while self.running:
try:
self.handle(self.inbox.get(timeout=POLL))
except queue.Empty:
continue
def stop(self):
self.running = False
def start_election(self):
"""任何发现 leader 故障的进程都可以发起：把自己的 id 放进 ELECTION 交给后继。"""
self.send_election(self.pid)
def send_election(self, value):
dst = self.ring.send(self.pid, "ELECTION", value=value)
if value == self.pid:
self.forwarded = True
def handle(self, msg):
kind, src, value = msg["kind"], msg["src"], msg.get("value")
if kind == "ELECTION":
if value == self.pid: # 绕环一周回到自己 => 我是最高 id
if not self.is_coordinator:
self.is_coordinator = True
self.elected = self.pid
self.ring.send(self.pid, "ELECTED", value=self.pid)
elif value > self.pid: # 别人比我大 => 原样转发
self.send_election(value)
elif not self.forwarded: # 我更大且还没发过 => 替换成自己的 id
self.send_election(self.pid)
# 否则丢弃：我已经转发过更大的 id，这条消息不可能获胜
elif kind == "ELECTED":
self.elected = value
if value != self.pid: # 除协调者外都继续转发
self.ring.send(self.pid, "ELECTED", value=value)
def run(order, initiators, settle=1.5):
counters = {"ELECTION": 0, "ELECTED": 0}
ring = Ring(order, counters)
nodes = dict((i, Node(i, ring)) for i in order)
for n in nodes.values():
n.start()
time.sleep(0.1)
for i in initiators:
nodes[i].start_election()
t0 = time.time()
while time.time() - t0 < settle:
time.sleep(0.05)
if ring.quiescent():
break
time.sleep(0.3)
for n in nodes.values():
n.stop()
return nodes, counters
def experiment(order, initiators, settle=1.5):
"""跑一轮选举，断言"只有最高 id 胜出且所有节点认同它"，返回各类消息数。"""
nodes, c = run(order, initiators, settle)
elected = set(nodes[i].elected for i in order)
assert elected == {max(order)}, "胜出者必须唯一且为最高 id，实测 %s" % elected
return c, c["ELECTION"] + c["ELECTED"]
if __name__ == "__main__":
RING6 = [80, 6, 12, 5, 32, 3] # 顺时针：80->6->12->5->32->3->80
N = len(RING6)
print("环 = %s （后继为下一个，末元素的后继回到首元素）" % RING6)
for name, init in (("(a) 最好情形：N80 自己发起 ", [80]),
("(b) 最坏情形：N6 是 N80 的环后继", [6]),
("(c) 多发起者：N3、N12 同时发起 ", [3, 12])):
c, total = experiment(RING6, init)
print("%s -> 胜出者=%d ELECTION=%d ELECTED=%d 合计=%d"
% (name, max(RING6), c["ELECTION"], c["ELECTED"], total))
print(" 讲义公式：最好 2N=%d 条，最坏 3N-1=%d 条" % (2 * N, 3 * N - 1))
print("(d) 全部 N 个进程同时发起（顺时针按 id 降序 = 最难抑制的排列）")
print(" N | 合计消息 | N^2/2+1.5N（拟合） | 单发起者最好情形 2N")
for n in (4, 8, 16, 32, 64):
order = list(range(n, 0, -1))
c, total = experiment(order, order)
print(" %2d | %5d | %7.1f | %3d" % (n, total, n * n / 2 + 1.5 * n, 2 * n))
【代码做什么？】
- 建环：
Ring保存顺时针顺序order，并预计算succ[i]；send()只把消息放进后继的 inbox——这是”单向环”的物理约束。 - 实现 ID 传递与替换：
Node.handle()对ELECTION分三种情形处理：value == my_id（绕环一周回到我 ⇒ 我是最大者，发ELECTED）；value > my_id（原样转发）；value < my_id且forwarded == False（替换为自己的 id 后转发）；否则丢弃。 - 跑三组对照：(a) 最好情形（
N80自己发起）应为 $2N=12$ 条；(b) 最坏情形（N6是N80的环后继）应为 $3N-1=17$ 条；(c) 多个发起者（N3、N12同时发起）仍只有N80胜出。 - 规模实验：让 $N=4,8,16,32,64$ 个进程全部同时发起（环按 id 降序排列，最难抑制），统计总消息数随 $N$ 的增长。
实际运行输出：
环 = [80, 6, 12, 5, 32, 3] （后继为下一个，末元素的后继回到首元素）
(a) 最好情形：N80 自己发起 -> 胜出者=80 ELECTION=6 ELECTED=6 合计=12
(b) 最坏情形：N6 是 N80 的环后继 -> 胜出者=80 ELECTION=11 ELECTED=6 合计=17
(c) 多发起者：N3、N12 同时发起 -> 胜出者=80 ELECTION=11 ELECTED=6 合计=17
讲义公式：最好 2N=12 条，最坏 3N-1=17 条
(d) 全部 N 个进程同时发起（顺时针按 id 降序 = 最难抑制的排列）
N | 合计消息 | N^2/2+1.5N（拟合） | 单发起者最好情形 2N
4 | 14 | 14.0 | 8
8 | 44 | 44.0 | 16
16 | 152 | 152.0 | 32
32 | 560 | 560.0 | 64
64 | 2144 | 2144.0 | 128
(a)(b) 与讲义公式完全吻合（$2N$ 与 $3N-1$），这是对 16.3.2 定理 4 的直接验证。(d) 的结果更值得玩味：所有 $N$ 个进程同时发起时，总消息数恰好等于 $\frac{N^2+3N}{2}$（$14, 44, 152, 560, 2144$），即 $\Theta(N^2)$ —— 多发起者把环形选举从 $O(N)$ 拉到了 $O(N^2)$，与 Bully 的最坏情形同阶。这说明环形选举的”$O(N)$”只在”单发起者”这个乐观前提下成立。
【分布式机制透视】
- 环是”逻辑环”而不是物理环：代码里用
succ[i]把任意 $N$ 个进程串成环，就像 Chord 用一致性哈希把节点排成环一样——真实的环拓扑（比如令牌环网、Kafka 的 partition replica 环、Cassandra 的 token ring）都是逻辑的。 - 消息只带数据、不带路由信息：
ELECTION只需携带value与init（发起者），这体现了环形算法极低的空间开销（每进程 $O(1)$ 状态），代价是延迟线性于环长。 forwarded标志是”抑制重复竞选”的关键：没有它，一个进程每次收到更小的值都会替换并发起，消息数会爆炸；有了它，每个进程最多用自己的 id 发起一次。quiescent()是终止检测：真实分布式系统里没有”全局静默”这个观察，这里用”所有 inbox 为空”来判定选举结束——这正是分布式系统里最容易出错的地方之一（你无法在本地判断全局事件已经发生，除非有额外的机制，如 Chandy-Lamport 快照里的标记消息）。
【与理论的对应】
| 代码位置 | 对应 16.3.2 的伪代码 | 对应哪条论证 |
|---|---|---|
value == self.pid 分支 | v == my_id ⇒ 发 ELECTED | 定理 3（安全性：只有最大者能收到自己的 id） |
value > self.pid 分支 | 原样转发 | 引理 3 情形 (ii)（$v_{out} = v_{in} > id_J$） |
elif not self.forwarded 分支 | 替换后转发 | 引理 3 情形 (iii)；forwarded 保证替换最多发生一次 |
末尾的 discard（无动作） | discard | 定理 3 证明中的关键：被丢弃的消息不可能回到发起者 |
(a)/(b) 的消息计数 | — | 定理 4 的 $2N$ / $3N-1$ 界 |
(d) 的规模曲线 | — | 多发起者情形下 $\Theta(N^2)$ 的实测证据 |
16.4.3 示例 3：脑裂演示——同一分区场景下 Bully vs Raft 风格 quorum 选举
"""脑裂演示：同一个 5 节点网络被分区成 {1,2} | {3,4,5}，
Bully 会选出 2 个 leader（脑裂），Raft 风格 quorum 选举只会选出 1 个；
最后演示 fencing token 让存储层拒绝旧 leader 的写。"""
import queue
import random
import threading
import time
random.seed(425)
N, QUORUM = 5, 3 # 多数派 = floor(5/2)+1 = 3
HB_INTERVAL, HB_TIMEOUT, OK_TIMEOUT, COORD_TIMEOUT = 0.03, 0.22, 0.22, 0.32
ELECTION_MIN, ELECTION_MAX, ACK_TIMEOUT, POLL = 0.35, 0.60, 0.30, 0.02
class Net:
"""可分区网络：跨分区消息被静默丢弃。"""
def __init__(self, ids):
self.ids = list(ids)
self.boxes = dict((i, queue.Queue()) for i in ids)
self.groups, self.lock, self.sent, self.dropped = None, threading.Lock(), 0, 0
def partition(self, groups):
self.groups = [set(g) for g in groups]
def send(self, src, dst, kind, **payload):
with self.lock:
self.sent += 1
if self.groups is not None and not any(src in g and dst in g for g in self.groups):
self.dropped += 1
return False
msg = {"src": src, "kind": kind}
msg.update(payload)
self.boxes[dst].put(msg)
return True
class Audit:
"""全局审计：记录当前所有自认为 leader 的进程（用于判定脑裂）。"""
def __init__(self):
self.lock, self.claims = threading.Lock(), {}
def claim(self, pid, tag):
with self.lock:
self.claims.setdefault(pid, tag)
def resign(self, pid):
with self.lock:
self.claims.pop(pid, None)
def snapshot(self):
with self.lock:
return sorted(self.claims)
class BullyNode(threading.Thread):
"""经典 Bully：靠心跳判故障，id 最高者胜出，不需要任何 quorum。"""
def __init__(self, pid, net, audit, leader):
threading.Thread.__init__(self, daemon=True)
self.pid, self.net, self.audit, self.leader = pid, net, audit, leader
self.last_hb = {leader: time.time()}
self.in_election, self.stage, self.deadline = False, None, 0.0
self.running, self.log = True, []
def send(self, dst, kind, **p):
return self.net.send(self.pid, dst, kind, **p)
def run(self):
while self.running:
try:
self.handle(self.net.boxes[self.pid].get(timeout=POLL))
except queue.Empty:
pass
self.tick()
def tick(self):
now = time.time()
if self.leader == self.pid and now - self.last_hb.get(self.pid, 0) > HB_INTERVAL:
self.last_hb[self.pid] = now
for p in self.net.ids:
self.send(p, "HEARTBEAT")
if self.leader is None and not self.in_election:
self.start_election()
elif self.in_election and now > self.deadline:
self.become_leader() if self.stage == "OK" else self.start_election()
elif self.leader != self.pid and not self.in_election:
if now - self.last_hb.get(self.leader, 0.0) > HB_TIMEOUT:
self.log.append("P%d: 心跳超时，判定 leader P%d 故障" % (self.pid, self.leader))
self.leader = None
def start_election(self):
self.in_election, self.stage, self.leader = True, "OK", None
self.deadline = time.time() + OK_TIMEOUT
higher = [p for p in self.net.ids if p > self.pid]
if not higher:
self.become_leader()
return
self.log.append("P%d: 向 %s 发 ELECTION" % (self.pid, higher))
for p in higher:
self.send(p, "ELECTION")
def become_leader(self):
self.in_election, self.stage, self.leader = False, None, self.pid
self.last_hb[self.pid] = time.time()
self.audit.claim(self.pid, "Bully")
self.log.append("P%d: >>> 自称 leader <<<" % self.pid)
for p in self.net.ids:
if p < self.pid:
self.send(p, "COORDINATOR", leader=self.pid)
def handle(self, msg):
kind, src = msg["kind"], msg["src"]
if kind == "ELECTION" and self.pid > src:
self.send(src, "OK")
if self.leader == self.pid:
self.send(src, "COORDINATOR", leader=self.pid)
elif not self.in_election:
self.start_election()
elif kind == "OK":
if self.in_election and self.stage == "OK":
self.stage, self.deadline = "COORD", time.time() + COORD_TIMEOUT
elif kind == "COORDINATOR":
self.leader = msg["leader"]
self.in_election, self.stage = False, None
self.last_hb[self.leader] = time.time()
elif kind == "HEARTBEAT":
self.last_hb[src] = time.time()
if self.leader is None and not self.in_election:
self.leader = src
class RaftNode(threading.Thread):
"""Raft 风格选举：随机化超时 + 任期 term + RequestVote + 多数派 quorum。"""
def __init__(self, pid, net, audit, log_index):
threading.Thread.__init__(self, daemon=True)
self.pid, self.net, self.audit = pid, net, audit
self.term, self.voted_for, self.leader, self.state = 0, None, 5, "follower"
self.last_log_index, self.last_log_term = log_index, 1
self.deadline = time.time() + random.uniform(ELECTION_MIN, ELECTION_MAX)
self.votes, self.acks, self.acks_time, self.ack_deadline = set(), set(), 0.0, 0.0
self.running, self.log, self.max_votes = True, [], 0
def send(self, dst, kind, **p):
return self.net.send(self.pid, dst, kind, **p)
def reset_timer(self):
self.deadline = time.time() + random.uniform(ELECTION_MIN, ELECTION_MAX)
def run(self):
while self.running:
try:
self.handle(self.net.boxes[self.pid].get(timeout=POLL))
except queue.Empty:
pass
now = time.time()
if self.state == "leader":
if now > self.ack_deadline: # 结算上一轮心跳的确认
self.max_votes = max(self.max_votes, len(self.acks))
if len(self.acks) < QUORUM: # 无多数派确认 => 退位
self.log.append("P%d: 任期 %d 只收到 %d 个确认 < %d，退位"
% (self.pid, self.term, len(self.acks), QUORUM))
self.state, self.leader = "follower", None
self.audit.resign(self.pid)
self.reset_timer()
else:
self.ack_deadline = now + ACK_TIMEOUT
if now - self.acks_time > HB_INTERVAL: # 再发下一轮心跳
self.acks, self.acks_time = set([self.pid]), now
for p in self.net.ids:
if p != self.pid:
self.send(p, "APPEND", term=self.term)
elif now > self.deadline: # 选举超时 => 竞选
self.start_election()
def start_election(self):
self.state, self.term, self.voted_for = "candidate", self.term + 1, self.pid
self.votes = set([self.pid])
self.reset_timer()
self.log.append("P%d: 任期 %d 成为候选人，请求投票" % (self.pid, self.term))
for p in self.net.ids:
if p != self.pid:
self.send(p, "VOTE", term=self.term,
last_log_index=self.last_log_index, last_log_term=self.last_log_term)
def become_leader(self):
self.state, self.leader = "leader", self.pid
self.audit.claim(self.pid, "Raft(term=%d)" % self.term)
self.acks, self.acks_time = set([self.pid]), time.time()
self.ack_deadline = time.time() + ACK_TIMEOUT
self.log.append("P%d: >>> 任期 %d 当选 leader（得票 %d）<<<"
% (self.pid, self.term, len(self.votes)))
for p in self.net.ids:
if p != self.pid:
self.send(p, "APPEND", term=self.term)
def handle(self, msg):
kind, src, term = msg["kind"], msg["src"], msg["term"]
if term > self.term: # 见到更高任期 => 降级
if self.state == "leader":
self.audit.resign(self.pid)
self.term, self.voted_for, self.state = term, None, "follower"
if kind == "VOTE": # 日志至少一样新才投票
up_to_date = (msg["last_log_term"], msg["last_log_index"]) >= \
(self.last_log_term, self.last_log_index)
if term >= self.term and up_to_date and self.voted_for in (None, src):
self.voted_for = src
self.reset_timer()
self.send(src, "VOTE_GRANT", term=self.term)
elif kind == "VOTE_GRANT":
if self.state == "candidate" and term == self.term:
self.votes.add(src)
self.max_votes = max(self.max_votes, len(self.votes))
if len(self.votes) >= QUORUM: # 集齐多数票才能当选
self.become_leader()
elif kind == "APPEND":
if self.state == "leader":
self.audit.resign(self.pid)
self.state, self.leader = "follower", src
self.reset_timer()
self.send(src, "ACK", term=self.term)
elif kind == "ACK":
if self.state == "leader" and term == self.term:
self.acks.add(src)
class FencedStore:
"""带 fencing token 的存储：拒绝 token 小于已见最大 token 的写。"""
def __init__(self):
self.lock, self.max_token, self.value, self.history = threading.Lock(), 0, None, []
def issue(self):
with self.lock:
self.max_token += 1
return self.max_token
def write(self, writer, epoch, value):
with self.lock:
ok = epoch >= self.max_token
if ok:
self.max_token, self.value = epoch, value
self.history.append((writer, epoch, "接受" if ok else "拒绝(旧 epoch)"))
return ok
def self_leaders(nodes, group):
"""该分区中"leader 视图指向自己"的节点，即该分区实际认可的 leader。"""
return [i for i in group if nodes[i].leader == i]
def run_bully(groups):
net, audit = Net(range(1, N + 1)), Audit()
audit.claim(5, "Bully(初始 leader)") # 配置给定的初始 leader
nodes = dict((i, BullyNode(i, net, audit, 5)) for i in net.ids)
for n in nodes.values():
n.start()
time.sleep(0.35)
net.partition(groups)
time.sleep(1.6)
for i in sorted(nodes):
for line in nodes[i].log:
print(" " + line)
views = [self_leaders(nodes, g) for g in groups]
for n in nodes.values():
n.running = False
return audit.snapshot(), views
def run_raft(groups):
net, audit = Net(range(1, N + 1)), Audit()
nodes = dict((i, RaftNode(i, net, audit, log_index=7)) for i in net.ids)
nodes[5].state, nodes[5].term, nodes[5].leader = "leader", 1, 5
nodes[5].acks, nodes[5].acks_time = set([5]), time.time()
nodes[5].ack_deadline = time.time() + ACK_TIMEOUT
audit.claim(5, "Raft(term=1)")
for n in nodes.values():
n.start()
time.sleep(0.35)
net.partition(groups)
time.sleep(1.8)
for i in sorted(nodes):
for line in nodes[i].log:
print(" " + line)
votes = dict((i, nodes[i].max_votes) for i in sorted(nodes))
views = [self_leaders(nodes, g) for g in groups]
for n in nodes.values():
n.running = False
return audit.snapshot(), votes, views
if __name__ == "__main__":
GROUPS = [[1, 2], [3, 4, 5]] # 少数派 | 多数派
print("场景：5 个节点，网络分区为 %s，旧 leader P5 仍在多数派分区中存活" % GROUPS)
print("[A] Bully 选举（没有 quorum，只看 id 大小）")
bl, bviews = run_bully(GROUPS)
print(" 分区 leader = %s | %s ==> 全局自称 leader = %s（%d 个 => %s）"
% (bviews[0], bviews[1], bl, len(bl),
"脑裂 / SPLIT-BRAIN!" if len(bl) > 1 else "无脑裂"))
print("[B] Raft 风格 quorum 选举（需要 %d 票 = floor(5/2)+1）" % QUORUM)
rl, votes, rviews = run_raft(GROUPS)
print(" 各节点见过的最大得票数 = %s（少数派最多 2 票 < 3）" % votes)
print(" 分区 leader = %s | %s ==> 全局自称 leader = %s（%d 个 => %s）"
% (rviews[0], rviews[1], rl, len(rl),
"脑裂 / SPLIT-BRAIN!" if len(rl) > 1 else "无脑裂"))
print("[C] 对比表")
print(" 算法 | 分区 {1,2} leader | 分区 {3,4,5} leader | 全局 leader 数")
print(" Bully | %-4s | %-4s | %d（脑裂）"
% (bviews[0] or "-", bviews[1] or "-", len(bl)))
print(" Raft | %-4s | %-4s | %d（安全）"
% (rviews[0] or "-", rviews[1] or "-", len(rl)))
assert len(bl) > 1 and len(rl) <= 1, (bl, rl)
print("[D] fencing token：即使存在两个 leader，存储层也能拒绝旧 leader 的写")
store = FencedStore()
e5 = store.issue() # 老 leader P5 从序列器申请到 epoch 1
print(" P5 申请 epoch=%d，写<余额=100> => %s"
% (e5, "接受" if store.write(5, e5, 100) else "拒绝"))
e2 = store.issue() # 少数派 leader P2 随后申请到 epoch 2
print(" P2 申请 epoch=%d，写<余额=999> => %s"
% (e2, "接受" if store.write(2, e2, 999) else "拒绝"))
print(" P5 用旧 epoch=%d 再写<余额=50> => %s（epoch 1 < 2，被 fencing 拦下）"
% (e5, "接受" if store.write(5, e5, 50) else "拒绝"))
print(" 存储层历史 = %s，最终值 = %s" % (store.history, store.value))
【代码做什么？】
- 搭一个可分区的网络：
Net.partition([[1,2],[3,4,5]])之后，跨分区的消息被静默丢弃（dropped计数）。两个算法跑的是完全相同的分区场景，只有选举机制不同——这是控制变量的关键。 - Bully 版本：
BullyNode是 16.4.1 的简化版；$P5$ 是配置给定的初始 leader。分区后{1,2}侧听不到 $P5$ 的心跳 ⇒P1超时、发起选举 ⇒P2压制P1后自己也发起 ⇒P2上面再没有人（P3/P4/P5的消息被丢弃）⇒P2自称 leader；而{3,4,5}侧 $P5$ 依然活着并继续当 leader ⇒ 同时存在两个 leader。 - Raft 版本：
RaftNode实现随机化选举超时、term、RequestVote/VoteGrant、日志新旧比较、leader 心跳与”拿不到多数派确认就退位”。分区后多数派{3,4,5}仍然能给出 3 票（$P5$ 保持领导权），少数派{1,2}无论怎么提升term、怎么反复竞选，得票上限只有 2 < 3，永远选不出 leader。 - 审计与对比表：全局
Audit记录”当前自认为 leader 的进程”，直接给出”全局 leader 数”；最后打印两个版本的分区 leader 对照表。 - fencing 演示：
FencedStore实现”拒绝低于max_token的写”，用老 leaderP5（epoch 1）与新 leaderP2（epoch 2）演示旧 leader 的写被拒绝。
实际运行输出：
场景：5 个节点，网络分区为 [[1, 2], [3, 4, 5]]，旧 leader P5 仍在多数派分区中存活
[A] Bully 选举（没有 quorum，只看 id 大小）
P1: 心跳超时，判定 leader P5 故障
P1: 向 [2, 3, 4, 5] 发 ELECTION
P2: 心跳超时，判定 leader P5 故障
P2: 向 [3, 4, 5] 发 ELECTION
P2: >>> 自称 leader <<<
分区 leader = [2] | [5] ==> 全局自称 leader = [2, 5]（2 个 => 脑裂 / SPLIT-BRAIN!）
[B] Raft 风格 quorum 选举（需要 3 票 = floor(5/2)+1）
P1: 任期 4 成为候选人，请求投票
P1: 任期 5 成为候选人，请求投票
P2: 任期 2 成为候选人，请求投票
P2: 任期 3 成为候选人，请求投票
各节点见过的最大得票数 = {1: 2, 2: 2, 3: 0, 4: 0, 5: 5}（少数派最多 2 票 < 3）
分区 leader = [] | [5] ==> 全局自称 leader = [5]（1 个 => 无脑裂）
[C] 对比表
算法 | 分区 {1,2} leader | 分区 {3,4,5} leader | 全局 leader 数
Bully | [2] | [5] | 2（脑裂）
Raft | - | [5] | 1（安全）
[D] fencing token：即使存在两个 leader，存储层也能拒绝旧 leader 的写
P5 申请 epoch=1，写<余额=100> => 接受
P2 申请 epoch=2，写<余额=999> => 接受
P5 用旧 epoch=1 再写<余额=50> => 拒绝（epoch 1 < 2，被 fencing 拦下）
存储层历史 = [(5, 1, '接受'), (2, 2, '接受'), (5, 1, '拒绝(旧 epoch)')]，最终值 = 999
这段输出就是本章黄金法则的实验证据：同一场景、同一网络故障、同一批节点，仅仅因为”合法性”的定义不同（”我自己没听到更高的应答” vs “我拿到了多数派的票”），Bully 产生了 2 个 leader，而 Raft 只产生 1 个。 注意 Raft 一侧 {1,2} 分区的两个节点在 1.8 秒内反复竞选、term 一路涨到 5，但因为票数上限只有 2，它们永远无法当选——这正是定理 6 的现场演示。
【分布式机制透视】
- 分区是通过”消息丢弃”实现的：
Net.send()里的一句if not reachable(src, dst): dropped += 1; return False就把网络切成了两半。真实系统里这对应交换机 ACL 错误、跨机房专线中断、防火墙规则误配、Kubernetes NetworkPolicy 阻断——分区是数据中心里最常见、也最容易导致脑裂的故障（比节点崩溃更常见）。 - 两个算法的”合法性判据”不同，这正是全部差异的来源：
- Bully：合法性 $=$ “我向所有更高 id 发过
ELECTION且没人回答”——纯局部判断，分区时必然为真； - Raft：合法性 $=$ “我拿到了 $\lfloor N/2\rfloor+1$ 票”——全局判断，分区时少数派必然为假。
- Bully：合法性 $=$ “我向所有更高 id 发过
term是逻辑时钟的工程化身：P1的term涨到 5 而P5还在term=1，说明两侧的”时间”已经分叉；一旦分区恢复，P5看到term=5的请求就会立刻降级（if term > self.term: state <- follower）——用单调计数器解决”谁的信息更新”这个问题，正是 Lecture 12 逻辑时钟思想的应用。- leader 心跳的双重身份：它既告诉 follower”我还活着”（抑制新选举），又携带
term并充当”提交多数派确认”的载体（acks）。在真实 Raft 里，AppendEntries 是唯一的 leader→follower 通道，它的失败既要触发选举、又要阻止提交。 - fencing 的角色：
FencedStore是真实世界里的 HDFS JournalNode、ZooKeeper 的 sequencer 校验、或数据库的”只接受最新主库写入”的网关。它不阻止脑裂，但让脑裂不再造成数据损坏——这是绝大多数生产系统的”第二道防线”。
【与理论的对应】
| 代码位置 | 对应 16.3 的哪一节 | 对应哪条论证 |
|---|---|---|
BullyNode.become_leader（不检查任何票数） | 算法 16.3.1 | 引理 2 (b)：局部信息即可称王 ⇒ 分区下必然产生”每分区一个 leader” |
RaftNode.start_election + len(votes) >= QUORUM | 算法 16.3.5 | 定理 5（同一任期至多一个 leader）+ 定理 6（少数派永远选不出） |
RaftNode.handle 中 if term > self.term 降级 | 算法 16.3.5 | Raft 的任期逻辑时钟；旧 leader 会被新 term 逐出 |
up_to_date 判断 | 算法 16.3.5 | 定理 7（选举限制）：日志不够新的候选人拿不到票 |
FencedStore.write 的 epoch >= max_token | 算法 16.3.6 | 定理 9（旧 leader 无法破坏数据） |
Audit + [C] 对比表 | — | 定理 1 与定理 6 的对照实验 |
16.5 性能与可扩展性分析
16.5.1 消息复杂度总表
| 算法 | 最好情形 | 最坏情形 | 常数项（实测/推导） | 复杂度来源 |
|---|---|---|---|---|
| Bully | $O(N)$ | $O(N^2)$ | $N^2-N-1$ 条（$N=5$ 时 19 条） | 收到 ELECTION 者自己也发起一轮 ⇒ 级联 |
| Ring（Chang-Roberts，单发起者） | $2N$ | $3N-1$ | $N=6$ 时 12 / 17 条 | 消息要绕环，最多一整圈 $\times 3$ |
| Ring（多发起者） | $O(N)$ | $O(N^2)$ | $\frac{N^2+3N}{2}$（$N=8$ 时 44 条） | $N$ 个发起者 $\times$ 每条消息最多 $N$ 跳 |
| Hirschberg–Sinclair | $O(N\log N)$ | $O(N\log N)$ | 每阶段 $\le 4N$ 条 $\times O(\log N)$ 阶段 | 双向探测，候选者每阶段至少减半 |
| Raft/Paxos 风格 quorum | $O(N)$ | $O(N)$（每次选举） | $3N-2$ 条量级（$N=5$ 时约 13 条） | 一次请求投票 + 一次回复 + 一次心跳 |
| Gossip 最终选举 | — | 每周期 $O(kN)$ | 收敛需 $O(\log N)$ 周期 | 反熵传播 |
要点：Bully 的 $O(N^2)$ 与 Raft 的 $O(N)$ 差了两个数量级的常数——$N=1000$ 时 Bully 最坏要发约 $10^6$ 条选举消息，而 Raft 一次选举只要约 3000 条。但请注意：Raft 胜出的真正理由不是消息数，而是”不脑裂”。即使 Bully 的消息数是 $O(N)$，它在分区下依然不安全。
16.5.2 选举延迟（从 leader 故障到新 leader 就绪）
| 算法 | 延迟构成 | 典型量级 | 说明 |
|---|---|---|---|
| Bully | 心跳超时 $T_{leader}$ + WAIT_OK 超时 $T_{out}$ + 广播 | 由超时值主导，通常秒级（把超时设小会误判，设大会导致长时间无 leader） | 讲义的”最坏 5 个消息传输时间”不含前置的故障检测时间 |
| Ring | 故障检测超时 + $O(N)$ 跳 | $O(N)$ 个消息传输时间 | 环越长越慢；断环时需要修复 |
| Raft | 随机化选举超时 $T\sim 2T$ + 1 个 RTT | $T\approx150\text{–}300$ ms，心跳 50–100 ms ⇒ 通常在几百毫秒内 | 随机化让平均选出时间接近 $1.5T$ |
| Chubby（讲义口径） | Paxos 一轮 + lease | 实践几秒，Google 观察到的最坏 30 秒 | 与”选举期间系统不可用”直接挂钩 |
| Gossip 最终选举 | $O(\log N)$ 个 gossip 周期 | 周期通常也是秒级 | 只用于软 leader |
16.5.3 容错性、脑裂风险与”选举窗口”
| 维度 | Bully | Ring-based | Raft / Paxos 风格 |
|---|---|---|---|
| 能容忍多少个崩溃 | 同步模型下最多 $N-1$（但会脑裂） | 环上任何一个节点崩溃都会断环，必须配合环修复/成员管理 | $\lfloor (N-1)/2\rfloor$（$N=5$ 容忍 2 个） |
| 网络分区下的行为 | 每个分区各自选出一个 leader（脑裂） | 同左（环被切成段，每段自成体系） | 只有多数派分区能选出 leader；少数派永远选不出 |
| 是否需要 quorum | 不需要 | 不需要 | 需要（这是它的全部安全性来源） |
| 是否需要时钟/超时 | 强依赖（安全性与活性都建立在超时准确上） | 仅”发现故障”依赖超时 | 活性依赖超时；安全性完全不依赖超时 |
| 选举窗口的不可用时间 | $T_{leader}+T_{out}$，可能很长 | $O(N)$ 个 RTT + 环修复时间 | 几十到几百毫秒（随机化超时） |
| 是否需要日志新旧比较 | 无 | 无 | 有（保证不覆盖已提交数据） |
| 单点写入的瓶颈 | leader 是瓶颈与单点（集中式互斥里体现得最明显：带宽 2 条/enter、1 条/exit，但 leader 是 SPoF） | 令牌持有者是瓶颈 | leader 仍是写瓶颈，但可快速重选 + 通过日志复制保证不丢 |
- 选举窗口（election window）：从 leader 失效到新 leader 就绪的这段时间里，系统无法提供服务（不能提交写、可能连读都不一致）。这就是为什么”选举延迟”是一个独立性指标：Bully 用超时值换消息数，Raft 用随机化超时把窗口压到百毫秒级。生产系统还会用租约 + 优雅下线（graceful handoff）进一步缩短窗口。
- 选举风暴（election storm）：大量节点同时超时、同时竞选，互相瓜分选票，导致长时间选不出 leader（Raft 的经典故障模式；等价地，Bully 的最坏情形就是一场选举风暴）。Raft 的解法是随机化选举超时（让超时时间不同，从而几乎总有一个节点先超时并获胜）；分布式系统里”随机化退避”是打破对称性的通用武器（以太网 CSMA/CD、gossip 周期、Kafka 的 rebalance 延迟都用了它）。
- leader 的双重代价：leader 既是瓶颈（所有写都经过它）又是单点（虽然有 quorum 容错，但 leader 崩溃必然触发一次选举窗口）。缓解手段：quorum + 快速重选（Raft）、多 leader/分片（Kafka 每个 partition 一个 leader）、读分担（follower 提供只读或 lease read）。
16.5.4 全面对比表与评价准则
| 对比项 | Bully | Ring-based（Chang-Roberts） | Raft/Paxos 风格 quorum 选举 |
|---|---|---|---|
| 系统模型假设 | 同步（超时可靠） | 同步（仅故障检测用）；单向环 + 可靠 FIFO | 部分同步（最终同步即可） |
| 拓扑假设 | 全连接，知道所有 id | 只需知道后继（$O(1)$ 状态） | 全连接（$N-1$ 条通道），知道集群成员 |
| 消息复杂度 | 最坏 $O(N^2)$ / 最好 $O(N)$ | 单发起者 $O(N)$（$3N-1$）/ 多发起者 $O(N^2)$ | 每次选举 $O(N)$ |
| 脑裂风险 | 有 | 有 | 无（quorum 交集） |
| 容错能力 | $N-1$ 个崩溃（同步模型） | 断环即失效，需恢复机制 | $\lfloor (N-1)/2\rfloor$ 个崩溃 |
| 选举延迟 | 由超时主导，可能很长 | $O(N)$ 个消息传输时间 | 几十–几百毫秒（随机化超时） |
| 是否需要 quorum | 否 | 否 | 是 |
| 是否考虑日志/数据新旧 | 否 | 否 | 是（选举限制） |
| 安全性是否依赖超时 | 是（核心缺陷） | 是 | 否（只依赖 quorum 交集） |
| 代表系统/场景 | 教学、早期集群软件、简单的主备切换脚本 | 令牌环网、逻辑环拓扑的成员协调 | Chubby、ZooKeeper(Zab)、etcd/Raft、Kafka KRaft、MongoDB、HDFS NameNode HA |
| 本项目中的定位 | “理解选举”的入门模型 | “理解环与消息复杂度”的模型 | 生产系统的实际选择 |
评价一个选举算法的六个准则：
- 正确性（唯一性）：在任何允许的故障下都不会出现两个 leader；这是没有商量余地的第一准则。
- 消息复杂度：稳态开销（心跳）与故障时的突发开销（选举消息）；$O(N^2)$ 的突发在 $N$ 很大时会造成网络拥塞与二级故障。
- 检测延迟（detection latency）：从故障发生到有人开始选举的时间，由心跳间隔与超时阈值决定。
- 选举延迟（election latency）：从开始选举到新 leader 就绪；直接决定系统的不可用窗口。
- 容错性：能容忍多少个崩溃/分区；在分区下是否降级为”少数派不可用”（这是正确的降级）还是”少数派自以为是”（这是脑裂）。
- 是否需要 quorum：需要 quorum 意味着少数派牺牲可用性换取正确性——这正是 CAP 在选举问题上的投影。
16.5.5 现代系统在实践中怎么选
讲义给出的结论非常干脆：经典选举协议（Ring-based、Bully）都 “failure-prone”，而工业界用的是 Paxos-like 协议（Google Chubby、Apache ZooKeeper）。原因可以精确地总结为三条：
- 正确性优先于消息数：Bully 省下的 $O(N^2)\to O(N)$ 消息，换来的是”分区时必然脑裂”这个不可接受的后果。而脑裂的代价（数据损坏、双写、脑裂后的手工修复）远远高于多发的几条消息。在分布式系统里，”省消息”永远排在”不损坏数据”之后。
- 超时是活性假设，不能当安全性假设用：所有把安全性建立在”我的超时是准的”之上的算法，都把系统的正确性押在了网络性能上——而网络性能恰恰是数据中心里最不可控的变量（GC 停顿、跨机房抖动、交换机故障）。quorum 把安全性搬到”组合数学”上，与网络状况彻底解耦。
- 选举必须与数据安全绑定：真实系统的 leader 要领导一个复制状态机，必须保证”新 leader 掌握所有已提交的数据”——这需要日志新旧比较（Raft 的选举限制），而 Bully/环形选举只比较 id。“选谁”这个问题的答案，从”选 id 最大的”变成了”选日志最新的且大多数人都认可的”。
因此，今天几乎所有强一致系统（Chubby、ZooKeeper、etcd、Consul、TiKV、Kafka KRaft、CockroachDB、MongoDB replica set）都使用 Raft/Paxos 风格的 quorum 选举；Bully 与环形选举则主要出现在：教学、资源受限的嵌入式/传感器网络（无法承担 quorum 通信开销）、以及不要求强一致的辅助角色选举（例如”谁来跑这个后台修复任务”）。
16.6 关键要点
- 选举的两个目标：唯一性（任意时刻至多一个 leader，或”所有存活进程最终认同同一个 leader”）与终止性（选举必然结束、所有人最终知道 leader）。前者是安全性、后者是活性，任何算法都必须分别论证。
- “崩溃”与”很慢”不可区分 ⇒ 选举必须依赖超时 ⇒ 超时必然误判 ⇒ 误判 + 无 quorum = 脑裂。 这条因果链是本章所有难点的总根源。
- 黄金法则：“最高 ID 胜出”看起来很自然，但在分区时会产生两个 leader；真正安全的选举必须依赖 quorum —— 这也是为什么现代系统放弃 Bully 而选择 Raft/Paxos 风格的选举。 Bully 的合法性是局部信息（”我没听到更高的应答”），quorum 的合法性是全局信息（”我拿到了多数派的票”）；只有后者能在分区下保持正确。
- 安全性与活性对超时的依赖是分离的：Raft 的安全性完全不依赖超时（只依赖”任意两个多数派必相交”+”一个任期只投一票”），超时只影响活性（多久能选出 leader）。这是 Paxos/Raft 相对 Bully 在工程上最本质的进步。设计任何选举算法时都该问一句：”把超时设成任意值，我的安全性还成立吗？”
- 选举与共识等价困难：能选 leader 就能做共识（用 leader 做杰出提议者），所以在纯异步系统中”既保证唯一又保证终止”的选举不存在（FLP）。工程上的三条出路是：只要求最终一致 + 最终准确故障检测器（$\diamond W$）、部分同步假设（GST）、随机化。
- fencing 是最后一道防线而不是第一道：当脑裂真的发生时，单调递增的 epoch/token 能让存储层拒绝旧 leader 的写，但它不能替代 quorum；顺序永远是”先用 quorum 保证唯一性，再用 fencing/STONITH/租约做纵深防御”。
16.7 常见陷阱与注意事项
陷阱：把”超时没收到消息”直接当成”进程已崩溃”（把活性假设当安全性假设）。 为什么错：这是异步系统的根本限制（Lecture 5–6）：超时只给出”怀疑（suspect）”，不给出”事实（fact）”。正确做法：把超时只用于触发选举（活性），把”谁是合法 leader”交给 quorum 投票（安全性）；或者使用带准确性证明的故障检测器（完美 FD 在异步系统中不可实现，只能用 $\diamond P$/$\diamond W$ 这类最终准确的 FD）。
陷阱：认为”Bully 选出最高 ID，所以一定是安全的”。 为什么错：”最高 ID”是一个局部事实——每个进程只知道自己的 id 表和自己的超时，它无法知道”那个更高 id 的进程是崩溃了还是被网络隔开了”。正确做法：在可能分区的环境里，永远不要用”本地观察 + 全局静态优先级”来决定唯一的写者；把决定权交给多数派。
陷阱：认为”把超时调大就能避免脑裂”。 为什么错：分区可以持续任意长的时间（数小时到数天），任何有限超时都会被超过；调大超时只是降低误判频率，同时延长无 leader 的不可用窗口，是”用可用性买正确性”的错误交易。正确做法：超时只用来决定”何时开始怀疑”；正确性用 quorum 保证。一个自检问题：如果有人把网络延迟变成无穷大，你的算法还会不会产生两个 leader？
陷阱：收到
COORDINATOR不加校验就无条件接受（或相反，有条件地忽略正确公告）。 为什么错：如果无条件接受任何COORDINATOR，一条过期的、来自低 id 旧 leader 的公告（延迟很久才到达，或者从某个缓存/重传中冒出来）会覆盖当前更高 id 的 leader 视图。正确做法：接受”公告者 id $\ge$ 当前认定 leader 的 id”的公告（代码里写成if id_k >= id_i or elected is None）；在 Raft 中则是”只有任期更高或相等的 AppendEntries 才被接受”——“任期/世代号单调”是这类校验的通用形式。陷阱：崩溃恢复的进程”忘记”自己不知道 leader，于是永远不参与选举；或者反过来，恢复后继续用旧的
elected值当 leader。 为什么错：前者导致恢复的进程一直把请求发给一个已经死掉的 leader（活性问题：它自己永远不知道新 leader）；后者更糟——如果它恢复前是 leader，它会继续以 leader 身份对外服务，形成”僵尸 leader”（脑裂的另一种形态）。正确做法：易失状态（elected、stage、租约到期时间）在重启后必须置空，恢复后主动发起一轮选举（Bully 的口径），并被当前更高的 leader 压制；更强壮的做法是把”我是不是 leader”绑定到租约/quorum 确认上——拿不到确认就必须退位。陷阱：认为 Bully 的安全性完全没有窗口。 为什么错：在崩溃恢复场景下存在一个极短（一个 RTT 量级）的”双 leader 窗口”：一个更高 id 的进程恢复并宣布自己是 leader 的瞬间，旧 leader 还没处理完它的
COORDINATOR公告（见 16.3.1 的推论）。正确做法：承认 Bully 的安全性依赖”选举期间不发生恢复”这一假设；真实系统里用 fencing token（存储层拒绝旧 epoch 的写）或 STONITH（物理断电）把这个窗口的后果消除掉。陷阱：在偶数个节点上用 quorum 选举，或把 quorum 算成 $N/2$。 为什么错：$N=4$ 时 quorum $=3$，容错仍是 $1$——与 $N=3$ 完全相同，却多养一个节点（可用性没提高、成本提高）。把 quorum 误算成 $N/2$（2 票即可）会让两个分区都能凑够 2 票 ⇒ 脑裂。正确做法：quorum $= \lfloor N/2\rfloor + 1$，并且部署奇数个投票成员（$3,5,7$）。Kafka/ZooKeeper/Raft 的集群规模几乎总是奇数，就是这个道理。
陷阱：环形选举里忽略”环断了”这件事，或者用
quiescent()（本地观察 all queues empty）来判断全局选举结束。 为什么错：环上任何一个节点崩溃都会让ELECTION消息”卡住”（消息永远绕不回来），选举没有终止（活性被破坏）；而”本地队列为空”不等于“全局选举已结束”——你无法在本地判断一个全局谓词（这正是 Chandy-Lamport 快照要解决的问题）。正确做法：环必须配合成员管理/环修复（让后继指向下一个存活节点）；选举终止应当由协议本身的可判定条件给出（例如”我收到了自己的 id”或”我收到了ELECTED“），而不是靠观察静默。
16.8 思考题（带答案）
Q1（计算/推演题）：某系统有 $N=1000$ 个进程，使用 Bully 算法。若某次 leader 崩溃后，最坏情形发生（最低 id 的进程最先发现故障），请计算 ELECTION、OK、COORDINATOR 三类消息各多少条，总计多少条；若改用 Raft 风格 quorum 选举（同样是 1000 个节点的一次成功选举），消息数大约是多少？两者相差多少倍？并解释这个差距是否意味着”Bully 更差”。
答：
- Bully 最坏情形：
ELECTION$= \frac{N(N-1)}{2} = \frac{1000\times999}{2} = 499{,}500$ 条；每条发给存活高 id 进程的ELECTION都会被回一条OK，其中发给已崩溃 leader 的 $N-1=999$ 条不会，因此OK$= 499{,}500 - 999 = 498{,}501$ 条；COORDINATOR由次高 id 向所有更低 id 广播，共 $N-2 = 998$ 条。总计 $= 499500+498501+998 = 998{,}999$ 条，约 $10^6$ 条（与公式 $N^2-N-1$ 一致）。 - Raft 一次成功选举：候选人向其余 $N-1=999$ 个节点发
RequestVote（999 条），收到约 500 条VoteGrant即已过半（500 条），当选后向所有人发AppendEntries心跳（999 条），节点各回一个 ACK（999 条）。总计约 3500 条，量级 $O(N)$。 - 相差约 285 倍。但这个差距并不构成”Bully 更差”的理由，因为：①$N=1000$ 的全连接 Bully 在实际中根本不会这样部署（组成员表就有 $10^6$ 项）；②更关键的是——即使把 Bully 的消息数优化到 $O(N)$，它在网络分区下依然会脑裂。Raft 胜出的根本原因是安全性，而不是消息数。 这也解释了为什么工程上更在意”选举期间的消息突发”（$10^6$ 条消息可能压垮网络，引发二级故障），而不仅仅是大 O 记号。
Q2（反例构造题）：请构造一个具体的执行序列，使得 Bully 算法在 5 个进程 $\{P1..P5\}$ 上同时存在两个 leader；然后说明把同一场景换成 Raft 风格 quorum 选举后，为什么不可能出现同样的情况。
答：
- 构造：初始 leader 为
P5（id 最高）。时刻 $t_0$，网络发生分区 $\{P1,P2\}\ \vert \ \{P3,P4,P5\}$，所有跨分区消息丢失。P1、P2在 $t_0 + T_{leader}$ 时心跳超时，判定P5故障；P1向{P2,P3,P4,P5}发ELECTION（其中发给P3/P4/P5的消息被丢弃），P2回OK并自己发起一轮（同样被丢弃）⇒P2在T_out后自称 leader 并向P1发COORDINATOR。与此同时，P5在分区另一侧一直是 leader（它的心跳能到达P3/P4，P5没有任何理由退位）。于是从这一刻起到分区恢复为止，P2与P5同时自认为 leader，P1认为 leader 是P2，P3/P4认为 leader 是P5——系统中存在两个合法 leader 和两套互相矛盾的 leader 视图。这就是 16.4.3 代码跑出来的结果（全局自称 leader = [2, 5]）。 - 换成 Raft 为什么不会：设 quorum $=\lfloor 5/2\rfloor+1 = 3$。
P2所在分区只有 $\{P1,P2\}$ 两个节点，它发出RequestVote后能收到的赞成票至多 2 票（含自己）$< 3$，永远无法当选（定理 6）。含多数派的分区 $\{P3,P4,P5\}$ 里，P5仍是 term 1 的 leader 并持续收到 3 个节点（含自己）的确认，因此保持合法。即便P1/P2无限提升term（如代码里涨到 5），它们也选不出 leader —— “选不出来”正是正确的降级行为，因为少数派本来就不应该提供服务。分区恢复后，P5看到更高的term会降级，集群重新收敛到单一 leader。
Q3（”直观但错误”题）：一位同学说：”Bully 之所以会脑裂，是因为超时设得太短了。我把 T_leader 从 200 ms 调到 10 秒，让几乎不可能出现误判，这样 Bully 就安全了。”请指出这个想法错在哪里，并说明在什么条件下 Bully 确实能保证安全。
答：
- 错在把”概率”当成了”保证”，并且搞错了超时能改变什么。 超时长度只影响误判发生的频率，不改变”误判一旦发生就会脑裂”这一结构性缺陷。网络分区可以持续任意长的时间（专线故障几小时、机房断电几天、ACL 误配置到下周才发现），因此只要
T_leader是有限值，总存在一段超过它的分区时间让少数派误判P5已死。把超时调到 10 秒，只是把”分区多久之后出现脑裂”推迟到 10 秒——它没有消除脑裂，只是延后了它；同时它把每一次正常的 leader 故障的不可用窗口从 200 ms 拉长到 10 秒（活性大幅下降），这是用可用性买了一个并不存在的安全性。 - 正确的方向：把”合法性”从局部判断（超时）搬到全局判断（quorum 投票）。在 Raft 中，即使
P1/P2在 100 ms 内就误判P5已死并开始竞选，它们也拿不到 3 票——超时准确与否完全不影响安全性，只影响”多久能选出新 leader”。 - 什么条件下 Bully 确实安全：需要一个同步系统模型，即存在已知的延迟上界 $d_{max}$ 与处理时间上界 $t_{max}$，且 $T_{out} > 2d_{max}+t_{max}$，并且网络不会发生分区（或分区会被系统当作进程崩溃处理且恢复被禁止）。这正是 16.3.1 定理 1 的假设——“网络不会分区”这条假设在真实数据中心里恰恰是最不成立的一条（总线/机箱内的多处理器系统、实时工业控制总线是少见的例外）。
Q4（概念辨析题）：讲义说”如果能解决选举，就能解决共识”。请说明这个归约是怎么做的；再说明为什么 Chubby 与 ZooKeeper 采用 Paxos 风格的选举，而不是直接用 Bully——这两件事矛盾吗？
答：
- 归约（选举 ⇒ 共识）：假设有一个选举 oracle 能在异步系统中保证唯一且终止的 leader 选举。用它跑共识：① 每个进程把自己的提案 $v_i$ 直接发给被选出的 leader $L$；② $L$ 收集足够多的提案后选出一个值（例如出现次数最多的那个值，或最先收到的值），用可靠广播发回；③ 所有进程决定为该值。Agreement 成立：所有人采用 $L$ 的值；Validity 成立：$L$ 选出的值来自某个进程的提案（多数值必然是被提议过的值）；Termination 由选举 oracle 的终止性保证。因此”选举可解 ⇒ 共识可解”。反过来，由 FLP，异步系统中共识不可解，所以选举也不可解（严格地说：不存在同时保证”唯一性”与”必然终止”的异步选举协议）。讲义的说法”用 $P_i$ 的 id 最后一位作为共识决定”是这个归约的最简形式。
- 不矛盾：这个归约说明的是”选举至少和共识一样难“，而不是”Bully 能完成那件事”。Bully 与环形选举根本没有解决讲义定义的那个选举问题——它们依赖超时（即同步假设），因此在异步系统中既可能不终止（活性不保证），也可能产生两个 leader（安全性在分区下不保证）。Paxos 风格的选举正是”在异步/部分同步系统中尽可能逼近那个不可解问题”的工程答案：用 quorum 把它能做到的部分（安全性）做到绝对，把做不到的部分（有界时间内的终止）降级为”最终活性”，并靠随机化让它”几乎总是”很快发生。
- 补充：Chubby 在 Paxos 选举之上又加了 master lease（其他服务器承诺”一段时间内不再选举”），这是用时间去摊销 quorum 的开销；ZooKeeper 用 Zab（一种类 Paxos 的原子广播）选出 leader，并用 zxid（事务 id）保证”只有数据最新的节点能当选”——这与 Raft 的选举限制是同一思想。这就是”选举”从”选 id 最大者”演化为”选能领导复制状态机的、被多数派认可的人”的完整故事。