Raft 共识协议

Raft 让选举证据与复制证据在多数交点相遇。日志新旧限制使含有更高任期或更长同任期前缀的节点阻止过时候选者获多数，AppendEntries 检查再把 leader 的前缀向 followers 扩散。两条规则结合可推出 leader completeness：一旦条目按 Raft 规则 committed，每个更高任期 leader 都含有它；再结合日志匹配，任何两个节点在同一索引应用的命令相同。

“按 Raft 规则”中的当前任期条件不可省略。旧任期条目即使后来出现在多数日志上，少数节点仍可能持有同索引、更高任期的冲突条目；该节点的日志在下一次选举中反而更新。当前 leader 先提交一个本任期条目后，支持它的多数拥有不低于本任期的日志证据，任何缺少该前缀的候选者都无法再凑齐多数。于是旧前缀随本任期条目间接提交。

五节点集群可容忍两个 crash-stop。旧 leader 网络隔离后可能继续接收请求，却无法获得三个节点的复制确认，因此不能提交；它稍后收到更高任期消息便退位。安全性不依赖超时长短，分区只会让不含多数的一侧失去进展。

Figure 8 式轨迹说明旧任期边界。任期 2 的 leader 只把 $x$ 写到两个节点；任期 3 的另一 leader 在少数节点同一索引写入 $y$。原 leader 在任期 4 重新当选并把旧条目 $x$ 补到三个节点。若仅凭“$x$ 现在位于多数”就宣布提交，随后持有任期 3 条目 $y$ 的候选者仍因最后日志任期更高而可能在任期 5 获选，并覆盖 $x$。若任期 4 leader 先追加并把本任期条目复制到多数，这个本任期证据会阻止上述候选者，且连带提交 $x$。

恢复还有一个与选举无关的窗口：日志 10 已执行并把余额从 100 扣至 90，节点随后在保存应用位置前崩溃。重启若从旧 lastApplied=9 重放同一扣款，会得到 80；Raft 日志只出现一次请求也不能阻止应用层重复效果。应原子地持久化状态变更与应用位置，或从一致快照重新构建两者。

若选举实现只比较日志长度而忽略最后日志任期，较长却过时的候选者可能获胜；若比较顺序颠倒，同样会破坏 leader completeness。快照必须携带 last included index/term，才能继续参与相同的匹配与新旧判断。

Raft 用任期、领导者选举理路选主问题Leader election使所有正确进程最终一致输出同一唯一进程为领导者的分布式任务。、投票限制和 AppendEntries 具体实现复制日志的提交接口，再由复制状态机理路状态机复制State machine replication · SMR让多个副本按同一确定顺序执行命令，从而实现容错服务。应用 committed 前缀。这一接口可写成实现状态到抽象日志状态的精化关系理路系统精化关系Refinement relation · System refinement · Specification refinement以行为包含、模拟或表示映射约束实现，使其允许行为不超出规格。：冲突尾部和重试属于实现行为，已提交前缀必须映到同一抽象历史。模型检查可以发现遗漏当前任期条件或持久化顺序后的短反例，却不能替代抽象映射。

在固定配置中，$2f+1$ 个节点可承受 $f$ 个崩溃并仍凑齐多数。活性还要求多数正确节点可达、消息与处理最终足够稳定，并让随机化选举超时最终产生一个未被竞争者打断的 leader；这通常以部分同步理路部分同步模型Partial synchrony · Partially synchronous system时间界存在但其数值或开始生效时刻不为算法预先掌握的分布式系统模型。表述。完全异步调度仍可不断制造分票或任期更替，而不破坏任何安全性质。

成员变更要用 joint consensus 让过渡期决定同时取得旧、新配置所需的 quorum，不能直接把成员列表瞬间替换。客户端去重、线性一致读、磁盘写入屏障与快照安装仍是完整服务的额外义务，不能从日志匹配性质直接推出。

在 $n$ 个节点、leader 稳定且 followers 已追平的正常情形，一条新日志的复制、确认与提交通知使用 $O(n)$ 条消息，不含重试。若每个副本保留 $L$ 条日志，则日志存储为 $O(L)$ 个条目；leader 另维护 $O(n)$ 个 nextIndex／matchIndex 记录。命令 payload、应用状态、客户端去重表及各记录的 bit 长度分别计费；日志修复、选举、重传与独立的后台心跳会增加开销，不能并入上述单条正常路径界。

复制协议之外的服务接口 ​

读屏障与ReadIndex理路Raft读屏障与ReadIndexRaft read barrier · ReadIndex · Linearizable Raft reads用当前任期提交、新一轮多数确认及应用位置屏障排除旧leader陈旧读，比较日志读与ReadIndex的证据和成本。把上述“线性一致读是额外义务”展开为本任期提交、新读关联的多数确认、应用位置等待三道条件；旧leader本地读与当前leader应用落后分别给出反例。联合配置理路Raft联合配置与成员交接Joint consensus · Raft membership change · Joint configuration用旧新两套多数和有序配置项连接成员变化，计算直接切换的分叉反例、联合提交及新配置生效的时机。则保留本页固定配置证明，另行展开配置项追加即生效、J用双多数提交、N用新多数提交的交接轨迹。

快照与安装理路Raft快照、日志压缩与安装Raft snapshot installation · Log compaction snapshot · InstallSnapshot以同一前缀的业务状态、请求结果、配置和索引任期构造恢复包，明确稳定发布、后缀保留和旧快照拒绝条件。把last included index/term接到状态、应用位置、结果表和配置的同一截点；保留后缀需边界匹配，持久发布必须先于日志回收。会话序号去重理路复制会话、请求序号与结果去重Replicated client session · Request deduplication · Session sequence number用显式注册会话、严格请求序号和同前缀结果表处理重试，复算响应丢失、乱序、结果回收及会话过期边界。负责不同日志槽位内的同一逻辑请求，不能误以为Raft日志匹配已经提供这项承诺。