Raft lecture (Raft user study)

Raft讲座（Raft用户研究） John Ousterhout详细阐述了Raft的架构与设计原理。Raft是一种非对称、基于领导者的共识算法，旨在跨集群复制状态机日志。本讲座将共识机制拆解为若干独立且易于管理的子问题：采用随机超时的领导者选举、日志复制、领导者变更期间的安全不变性，以及通过基于任期的逻辑时钟废除过期领导者。讲座还探讨了恰好一次的客户端语义，以及利用两阶段联合共识协议实现安全的动态集群成员变更。Ousterhout自始至终强调，即使仅有勉强过半数的活跃服务器在运行，Raft仍能保证安全性与线性一致性。 Raft围绕非对称且基于领导者的复制状态机模型构建分布式共识，只要勉强过半数的节点保持可达，系统就能持续推进。 (0:00) 协议的复杂性主要集中在领导者更替上，更替过程依赖基于任期的逻辑时钟、随机选举超时以及归纳日志匹配检查来解决日志分歧。 (2:11) 为保证安全性，领导者不得仅凭统计副本数量就提交前任任期的条目；它们必须先将至少一条当前任期的条目复制到大多数节点上。 (32:26) 集群成员变更通过采用两阶段联合共识协议（C_old+new）来避免脑裂状态，该协议需要同时获得新旧两个配置中各自多数派的独立认可。 (48:00)

John Ousterhout presents Raft as an asymmetric, leader-based consensus algorithm designed to build replicated state machines under partial network and machine failures. The protocol decomposes consensus into distinct operational modes, operating on the premise that safety and progress require only a simple majority without needing cluster-wide knowledge. Leader-Based Architecture and Election Dynamics (2:11) Raft operates under a fail-stop model across unreliable networks, deliberately excluding Byzantine fault tolerance. By adopting an asymmetric architecture, normal operations remain straightforward because a single leader manages client proposals and log replication without peer contention. Servers alternate between follower, candidate, and leader states across monotonically increasing terms, with heartbeats dispatched via empty AppendEntries remote procedure calls to maintain authority. To ensure safety, each server grants at most one vote per term on a first-come, first-served basis, mathematically preventing two candidates from securing majorities simultaneously. Progress is preserved by randomizing follower election timeouts between T and 2T (typically 100 to 500 ms). Because this window exceeds cluster broadcast times, a single node reliably times out first, gathers majority ballots, and suppresses split-vote cycles. Log Replication and Inductive Invariants (20:02) Normal replication funnels state machine commands into sequential log entries identified by index, command, and term. Once an entry resides on a majority of disks, it is considered committed, and the leader applies it to its local state machine before responding to the client. Slow or partitioned followers are retried asynchronously without imposing tail latencies on normal request commitments. Raft enforces structural invariants through an inductive check embedded in AppendEntries calls. A leader passes the index and term of the immediately preceding entry (prevLogIndex and prevLogTerm). A follower rejects any write request where its local entry does not match this preceding metadata, ensuring identical historical prefixes across nodes. Leader Transitions and Log Repair (27:49) When transitions occur, Raft does not halt execution for a global cleanup phase; it assumes the active leader's log is authoritative and resolves discrepancies during normal replication. To guarantee the Leader Completeness Property—that committed entries survive across all subsequent terms—voters deny ballots to any candidate whose log is less up-to-date than their own, evaluating the candidate's lastLogTerm and lastLogIndex. Furthermore, leaders cannot commit prior-term entries simply by counting replicas; they must advance their own term's log entry to a majority before earlier entries are considered committed. For misaligned followers, the leader initializes a nextIndex tracker, stepping backward upon each rejection until finding an agreement point. Upon matching, the follower truncates all subsequent conflicting entries and appends the leader's history. Deposed Leaders and Linearizable Semantics (42:14) To prevent split-brain hazards from partitioned nodes, all RPCs transmit the sender's current term. A stale leader attempting to replicate entries receives immediate rejections containing higher terms, forcing it to step down to follower status. Because winning candidates must raise terms across a majority of servers during elections, deposed leaders cannot achieve majority writes on minority partitions. For client interactions, Raft prevents duplicate executions caused by network timeouts and leader failures. Clients attach globally unique identifiers to commands, which leaders record in log entries. If a retried command carries an existing identifier, the leader bypasses re-execution, waits for the original entry to be applied to the state machine if pending, and returns the cached outcome. Membership Adjustments via Joint Consensus (48:00) Direct cluster membership changes from an old configuration to a new configuration risk split-brain states because distributed nodes cannot switch simultaneously. Raft handles reconfigurations through a two-phase joint consensus model using an intermediate configuration entry (Cold+new). While joint consensus is active, decisions such as elections and log commitments require separate, independent majorities from both configurations. Configuration entries take effect immediately upon being logged by each node, without waiting for commitment. Once Cold+new achieves commitment, a final Cnew entry is replicated; subsequent operations then transition entirely to the new membership. If an active leader is excluded from Cnew, it continues orchestrating replication until Cnew is committed, after which it steps down. Ousterhout concludes that the core constraint shaping Raft is that the system must operate reliably with only a bare majority of servers functioning, precluding any reliance on global cluster knowledge or single-phase distributed agreements.

John Ousterhout 在演讲中详细阐述了 Raft 共识算法，指出该算法通过非对称的强领导者模型与离散任期机制，将复杂的状态机复制问题解耦为六个独立子问题，确保系统在仅有多数派存活的不完备信息环境下依然满足线性和安全性。 强领导者架构与状态机复制模型 (0:00) Raft 的核心目标是通过在服务器集群间保持完全一致的日志序列，构建确定性的复制状态机。系统采用非对称的基于领导者架构，将运行分为稳态操作与领导者更替两个阶段。在正常运行期间，客户端所有命令均交由唯一的领导者处理，由领导者追加至本地日志并向追随者广播 AppendEntries RPC。只要集群中有多数派节点确认写入，该条目即视为已提交（committed），并按序应用到各节点状态机以产生一致结果。这种单领导者设计避免了对称无主架构中复杂的并发写冲突，提升了稳态性能。 在容错模型方面，Raft 假设网络可能丢包、延迟、乱序或发生分区，节点遵循故障-停止（fail-stop）模型，明确不处理拜占庭恶意故障。系统保证只要多数派机器存活并能通信即可持续推进：3 节点集群可容忍 1 台故障，5 节点集群可容忍 2 台故障。针对客户端交互，系统通过为每个命令分配全局唯一标识符，使领导者能在日志中拦截重复请求，确保在领导者崩溃重试时仍可提供线性化语义和精确执行一次（exactly-once）的保证。 基于任期与随机超时的领导者选举 (9:47) 集群节点在任何时刻都处于 Follower、Candidate 或 Leader 三种互斥状态之一。时间被划分为单调递增的逻辑任期（term），持久化存储在磁盘上。任期不仅充当逻辑时钟，还是消除陈旧信息的核心凭据：任何携带较小任期的 RPC 都会被直接拒绝，而接收方若发现自身任期落后，则会立即降级为 Follower 并同步任期，从而有效中和因网络分区导致的网络中孤立的旧领导者。 当 Follower 在心跳超时窗口内未收到有效通信，便会递增任期并转为 Candidate 发起 RequestVote RPC。为确保安全性，每个节点在单一任期内仅能依照先来先到原则投出一票并写盘，确保同一任期最多产生一个领导者。为了解决多个节点同时竞选导致选票被瓜分的活性（liveness）问题，Raft 将选举超时随机化设定在 [T, 2T] 区间（通常为 150–300 毫秒）。由于超时时间差远大于网络单程广播延迟，最先苏醒的节点能够迅速收敛多数派选票赢得选举，并在第一时间广播心跳确立统治。 日志匹配原则与领导者完整性安全约束 (21:12) Raft 的日志通过连续索引（index）与生成时的任期（term）唯一标识。在每一次 AppendEntries RPC 中，领导者都会包含前一个条目的索引（prevLogIndex）和任期（prevLogTerm），追随者若无法在对应位置匹配该任期则直接拒绝追加。这一归纳检查保证了强日志匹配特性：一旦两个节点在某条目处任期与索引一致，则该条目之前的所有历史日志必然完全相同，且任何已提交条目的前序日志也必然处于已提交状态。 针对领导者更替可能导致的未提交数据冲突，Raft 确立了“领导者完整性属性”（Leader Completeness），即所有已被提交的条目必须存在于未来任何领导者的日志中。为实现该属性，系统施加了两项关键约束：第一，在选举时执行日志完整性比较，投票节点若发现自身最后一条日志的任期更高，或任期相同但日志更长，则拒绝向该 Candidate 投票；第二，领导者不得仅凭副本数量来提交以前任期的条目，必须至少将当前任期内产生的一个新条目成功复制到多数派，才能将此条目及其前面所有的历史条目一并标记为已提交，彻底阻断旧数据被后续领导者覆盖的安全漏洞。 日志对齐修复与联合共识成员变更 (40:40) 新领导者上任后不会运行耗时且阻塞的全局清理，而是将自身日志视为绝对权威，通过逐步下调针对每个追随者的 nextIndex 变量（初始置为 leaderLogIndex + 1）来探测并修正分歧。当 AppendEntries 触发一致性检查失败后，nextIndex 逐次减 1 回退，直到找到双方日志完全吻合的点。随后，追随者将覆盖该分歧点之后的所有冲突条目并截断后续无效历史，以领导者数据为准完成日志同步。 针对集群服务器增减的配置变更，直接从旧配置（C_old）切换至新配置（C_new）存在发生裂脑的风险，因为不同节点切换的时间差可能导致 C_old 与 C_new 的多数派在同一时刻独立做出冲突决策。Raft 采用两阶段的联合共识（joint consensus）解决这一问题：领导者先写入并复制过渡配置 C_old+new，在此阶段，任何选举与提交决策必须同时获得 C_old 的多数派和 C_new 的多数派双重批准；待 C_old+new 提交生效后，领导者再发起并提交最终的 C_new。Ousterhout 指出，若现任领导者未被包含在 C_new 中，它仍会主持同步直至 C_new 提交，随后主动退位让位于新配置节点。 Ousterhout 总结指出，Raft 算法最底层的设计约束在于：整个系统必须在完全缺乏全局统一视图、仅依赖简单多数派正常运行的局部不完备信息环境下稳定工作。通过将状态转换严格绑定到两阶段联合决策和单向日志同步上，Raft 在大幅降低理解门槛的同时，提供了与 Paxos 同等的形式化正确性。

## Background 该视频由 Diego Ongaro 于 2013 年 8 月 15 日发布在 YouTube 平台上，时长约 58 分钟。内容为斯坦福大学教授 John Ousterhout 为 Raft 用户研究（旨在对比学生学习 Raft 与 Paxos 算法难易度的实验）所录制的讲座，系统讲解了 Raft 共识算法的设计原理与核心机制。 ## TL;DR 本讲座全面拆解了用于构建高可用复制状态机的 Raft 分布式共识算法。John Ousterhout 将协议系统性划分为领导者选举、正常日志复制、领导者更迭与安全性保障、旧领导者防范、客户端交互幂等性以及基于联合共识的动态成员变更六大模块。讲座重点阐释了 Raft 如何利用任期逻辑时钟、强化的选举与提交规则，以及多数派法定人数机制，在节点故障和网络分区等不完整信息的极端环境下，确保系统对外提供严格的线性化安全性与高可用容错能力。 ## Atmosphere & style 整场讲座呈现出典型的顶尖学府系统级计算机课程风格，条理极其分明，兼具学术严谨性与工程直觉。John Ousterhout 的语调沉稳笃定、节奏把控精准，擅长将复杂的分布式状态冲突拆解为直观的归纳推理与推演案例。在讲解两阶段共识的必然性时，他的语言中还自然流露出资深计算机科学家的幽默与锐利，让整个技术论证过程既硬核透彻又极具说服力。 ## Bulletin - [00:00](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=0s) Raft 将复杂的分布式共识问题解耦为常规运行与领导者更迭两大状态，只要集群中保持任意过半数（Majority）节点存活且网络连通，系统便能持续推进业务。 - [13:59](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=839s) 选举安全性通过“每任期每节点仅投一票”保障，而活性死锁则依托随机化选举超时（通常为 100 至 500 毫秒打散）有效化解选票瓜分难题。 - [35:34](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2134s) 提交规则存在关键安全补丁：Leader 不得单凭多数派复制就直接提交早前任期的日志，必须同时将当前任期的一条新日志成功写入多数派才能间接确认历史条目的提交。 - [48:01](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2881s) 集群成员变更采用“联合共识”（Joint Consensus）两阶段协议，强制要求决策同时获得新旧两套配置的独立多数派批准，彻底杜绝单阶段切换引发的双重多数派脑裂。 ## Key takeaways - [00:00](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=0s) Raft 旨在构建高可用复制状态机，只要任意过半数节点在线，即可保证各节点按相同顺序执行一致的日志命令并产生相同输出。 - [02:11](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=131s) 系统基于故障-停止（Fail-stop）模型，不处理拜占庭恶意行为；采用强 Leader 架构消除了常规操作下的并发冲突，协议复杂度主要集中在领导者变更处理上。 - [05:54](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=354s) 全局时间被划分为单调递增的逻辑任期（Terms），任期在协议中作为逻辑时钟，用于快速识别并淘汰集群中的陈旧过期信息。 - [09:47](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=587s) Follower 完全处于被动响应状态，当选举超时（100-500ms）未收到心跳或 RPC 时，会递增任期转为 Candidate 发起选票拉取。 - [13:59](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=839s) 选举安全性依赖多数派重叠与每节点单任期一票的持久化记录；而活性则依赖在特定区间内随机化选举超时，防止多个候选人无限瓜分选票。 - [21:12](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=1272s) Leader 向 Follower 发送 AppendEntries RPC 时内嵌一致性检查（比对前驱条目的索引与任期），以数学归纳法保证日志的前驱一致性与匹配性。 - [27:31](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=1651s) Leader Completeness 属性要求已提交条目必须存在于未来所有 Leader 的日志中；为此 Raft 规定节点必须拒绝投票给日志完整度落后于自己的候选人。 - [35:34](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2134s) Leader 绝不能仅凭多数派复制直接判定历史任期的旧日志已提交，必须等待当前任期的条目也在多数派落盘，以此防止已被覆写风险的极端反例发生。 - [37:29](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2249s) 新 Leader 通过为每个 Follower 维护递减试探的 nextIndex 变量，逐步向前匹配共同前缀，一旦吻合即覆盖截断 Follower 上的多余脏条目并补齐缺失历史。 - [42:14](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2534s) 网络分区恢复后的陈旧 Leader 通过 RPC 中携带的任期号被接收方检测并拒绝，促使其自动降级为 Follower，有效防止脑裂破坏。 - [45:18](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2718s) 客户端通过全局唯一请求 ID 与 Leader 日志去重机制实现幂等处理，保障在 Leader 崩溃重试场景下的 Exactly-Once 线性化执行语义。 - [48:01](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2881s) 单阶段集群配置变更会导致新旧配置各自独立形成有效多数派引发冲突；联合共识通过引入双重多数派过渡阶段在数学上杜绝了脑裂可能。 - [50:46](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=3046s) 配置条目具有写入即生效的特殊机制，甚至不在新配置集合中的旧 Leader 也会履职直至新配置正式提交后才主动退位。 - [56:32](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=3392s) Raft 的核心设计哲学在于系统绝不能假设自身具备全局完整认知，必须仅凭局部存活的过半数法定节点便能做出安全且正确的决断。 ## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=0s) 复制状态机与一致性目标 John Ousterhout 开启了关于 Raft 共识算法的讲解。Raft 的总体目标是将一份日志条目（log of entries）完全一致地复制到多台服务器上，并以此为基础构建所谓的“复制状态机”（replicated state machine）。当需要让一个程序或应用程序变得高可用且可靠时，一个成熟的做法就是让该程序在一组机器上并行运行，并确保所有机器都以完全相同的方式执行。这里的“状态机”泛指任何能够接收输入并产生相应输出的程序或应用。 为了保证不同状态机执行完全相同的命令，日志在其中起到了核心桥梁的作用。当客户端希望执行一条命令时，它会将该命令提交给系统中的一台机器。该机器先将命令（例如称为 $X$）写入本地日志，随后将其同步复制到其他机器的日志中。一旦命令被安全地复制到各个节点的日志中，就可以将其递交给各自的状态机执行；当某台机器的状态机完成执行后，便将执行结果返回给客户端。只要各机器的日志内容完全一致，并且各服务器上的状态机按照相同的顺序依次执行这些日志命令，就能保证产生完全相同的输出结果。 ```mermaid flowchart LR accTitle: Replicated State Machine Architecture accDescr: A client submits a command to a server log, which replicates it to peer logs before applying to state machines. subgraph ClientLayer["客户端"] C["客户端 Client"] end subgraph ServerNodes["共识集群 (Server Cluster)"] direction TB subgraph Node1["Server 1"] L1["本地日志 Log"] --> SM1["状态机 State Machine"] end subgraph Node2["Server 2"] L2["本地日志 Log"] --> SM2["状态机 State Machine"] end end C -->|"1. 提交命令 X"| L1 L1 -->|"2. 复制日志条目"| L2 SM1 -->|"3. 返回执行结果"| C ``` 共识模块的核心职责正是管理这些日志：确保它们被正确复制，并裁决何时可以安全地将命令提交给状态机执行。Ousterhout 指出，这一机制之所以被称为基于“共识”（consensus）的方法，是因为它并不苛求集群中所有服务器在任何时刻都保持在线：“the system has to make progress as long as any majority of the servers are up and can communicate with each other”。这意味着只要集群中任意过半数（majority）的服务器处于存活状态且网络连通，系统就能持续推进业务。 - 容错能力示例：一个由 3 台服务器组成的集群，只要有 2 台存活即可容忍 1 台宕机；由 5 台服务器组成的集群，只要有 3 台存活便可容忍 2 台宕机。 ### [02:11](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=131s) 故障模型假设与 Leader-Based 架构优势 Ousterhout 明确界定了 Raft 系统所预期的故障模型。在服务器节点方面，系统假设节点发生故障时遵循“故障-停止”（fail-stop）模式，即节点只会单纯地停止运行，或者暂时停顿并在稍后恢复，但只要它们处于运行状态，其行为就是完全正确的。Raft 协议不处理恶意篡改或欺骗的拜占庭错误（Byzantine behavior）。在网络环境方面，系统假定网络通信随时可能中断：消息可能丢失、延迟到达、乱序到达，甚至网络可能发生暂时性的网络分区（network partition），并在后续某一时刻自行恢复。 实现共识算法通常有两种主流范式：一种是对称或无主模式（symmetric / leaderless），所有服务器地位平等、角色相同，客户端可以联系任意节点追加日志；另一种则非对称或基于领导者模式（asymmetric / leader-based），节点地位不平等，任何时刻集群中由唯一的 Leader 掌控全局，其余服务器均处于从属地位，仅按 Leader 的意图行事，客户端也仅与 Leader 进行交互。Raft 选择了第二种基于 Leader 的路线。 ```mermaid flowchart TD accTitle: Leader-based Consensus Decomposition accDescr: Raft breaks consensus into normal leader operation and leader changes during failures. Top["Raft 共识问题分解"] Top --> Norm["正常运行状态 (Normal Operation)"] Top --> Change["领导者更迭 (Leader Changes)"] Norm --> NormDesc["单一 Leader 决策，流程极其简洁高效"] Change --> ChangeDesc["涵盖 Leader 崩溃检测、新一轮选举与日志修复"] ``` 这种架构设计将共识问题清晰地分解为两部分：一是拥有正常运行的 Leader 时的常规操作，二是在 Leader 崩溃或需要重新选主时的处理逻辑。这一划分极大地简化了日常操作，因为无需在并发场景下协调多个领导者的潜在冲突，单一负责人可以全权决断。正如 Ousterhout 所总结的那样：“all of the complexity in raft as you'll see comes from leader changes that's particularly true because if a leader crashes it may leave the system in an inconsistent state that the next leader has to clean up”。总体而言，由于消除了常规状态下节点间的冲突处理，基于 Leader 的方案往往比无主方案更为高效。 ### [04:33](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=273s) 课程拆解的六大核心板块 Ousterhout 将整个 Raft 协议系统性地拆分为六个部分进行讲解： 1. **领导者选举（Leader Election）**：探讨如何从所有节点中选出一个作为 Leader，以及当该节点崩溃后，集群如何检测到故障并选出新 Leader 予以替换。 2. **正常运行机制（Normal Operation）**：阐述 Leader 接收客户端请求并将其复制到各个节点的过程，这是 Raft 中最简单直观的部分。 3. **领导者更迭（Leader Changes）**：这是整个协议中最棘手、也是保障系统整体正确性最关键的部分。内容主要包含两点：其一是 Raft 的安全性（Safety）含义及保障机制；其二是新 Leader 如何化解日志不一致，恢复系统一致性。 4. **旧领导者防范（Preventing Stale Leaders）**：解决在 Leader 发生更迭时，如何防止一个并未真正死亡的旧 Leader 重新上线扰乱集群秩序。 5. **客户端交互（Client Interaction）**：探讨客户端如何应对服务器崩溃，重点关注如何实现线性化语义（linearizable semantics），以确保客户端的每个操作“有且仅被执行一次”（once and exactly once）。 6. **配置变更（Configuration Changes）**：介绍如何动态地在负责运行 Raft 系统的集群中安全地添加或移除服务器节点。 ### [05:54](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=354s) 服务器三态与任期（Terms）逻辑时钟 在正式展开具体机制前，Ousterhout 梳理了 Raft 运行的基本全貌。在任意时刻，Raft 集群中的每台服务器都严格处于以下三种状态之一： - **Leader（领导者）**：负责全局控制，协议必须保证任意时刻最多只有一位合法的 Leader。 - **Follower（跟随者）**：常态下绝大多数节点所处的状态。Follower 完全被动，自身绝不主动发起任何 RPC，仅负责响应来自其他节点的 RPC 请求。 - **Candidate（候选人）**：介于 Follower 与 Leader 之间的过渡状态，仅在选举新 Leader 期间临时存在。 ```mermaid flowchart LR accTitle: Server States in Raft accDescr: State transitions between Follower, Candidate, and Leader states. F["Follower 跟随者"] -->|"超时发起选举"| C["Candidate 候选人"] C -->|"赢得多数选票"| L["Leader 领导者"] C -->|"发现新 Leader 或更高任期"| F L -->|"发现更高任期"| F ``` Raft 将时间划分为连续递增的“任期”（Terms）。任期由单调递增的整数编号表示，且任期编号绝不重复使用。每个任期在逻辑上包含两个阶段：首先是以选举开始，用于选出该任期的 Leader；若选举成功，该 Leader 将在该任期的剩余时间内行使领导权。Raft 保证在同一个任期内最多只能有一台服务器当选 Leader。然而，也存在某些任期无法选出 Leader 的情况——当选票被严重分散、没有任何候选人获得多数票时，该任期便宣告流产，系统会立即进入下一个新任期并重新发起选举。 每台服务器都在本地维护一个名为 `currentTerm` 的变量，代表其对当前系统任期的最新认知。该信息必须可靠地持久化在磁盘上，以便服务器在崩溃重启后能够准确恢复。任期在 Raft 中充当着逻辑时钟的关键角色，Ousterhout 特别强调：“the role that terms serve is a really important one it allows raft to identify information that's out of date”。例如，若一台自认为处于 Term 2 的服务器与另一台处于 Term 3 的服务器通信，系统就能立即判定来自前者的所有消息已过期，并果断予以淘汰或更新。 - 节点通信机制：Raft 全协议仅依赖两种远程过程调用（RPC）： - `RequestVote` RPC：仅在选举阶段由 Candidate 发起，用于收集选票以竞选 Leader。 - `AppendEntries` RPC：在正常运行阶段由 Leader 发起，用于向 Follower 复制日志条目并作为心跳信号维持权威。 - 这两种 RPC 均具备幂等性（idempotent），极大地简化了重复消息、乱序到达及丢包等网络异常的处理。随后，Ousterhout 正式切入协议的第一部分——选举机制。 ### [09:47](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=587s) 跟随者状态与心跳机制 在 Raft 集群中，任意时刻通常只有一台机器充当 Leader。当一台服务器刚启动时，它首先处于 Follower（跟随者）状态。在这一状态下，该服务器完全是被动的：它既不会尝试主动与其他机器通信，也不会发起请求，仅仅是响应来自其他节点传入的远程过程调用（RPC）。然而，Follower 要想保持这种被动状态，前提是它必须相信集群中存在一个活跃的 Leader。获知这一信息的唯一途径，就是接收来自 Leader 或 Candidate（候选人）的消息。 因此，Leader 为了维护自身的统治地位与权威，必须定期与集群中的所有其他机器进行通信。如果 Leader 暂时没有其他实际数据需要传输，它就必须周期性地发送心跳（heartbeat）消息。在 Raft 的设计中，心跳并不是一种独立的新协议，而仅仅是不包含任何日志数据的 `AppendEntries`（附加日志条目）RPC。 ```mermaid flowchart TD accTitle: Follower Timeout and Election Trigger accDescr: Follower node waits for heartbeats and triggers election on timeout. A["Follower 启动"] --> B["等待通信"] B --> C{"是否收到 RPC / 心跳？"} C -- "是 (收到 AppendEntries)" --> B C -- "否 (选举超时 100-500ms)" --> D["假定 Leader 失效"] D --> E["发起新一轮选举"] ``` 如果一段时间过去，Follower 没有任何收到来自 Leader 的 RPC 消息，它就会判定集群中已经没有可用的 Leader，进而发起一场选举来争取自己成为 Leader。这段等待的时间被称为“选举超时”（Election Timeout），在典型的生产集群配置中，这一时长通常设置在 100 到 500 毫秒之间。当整个集群最初启动时，所有服务器都以 Follower 身份起步，集群中空无一主，大家都会静待选举超时结束，随后竞相发起选举来选出集群领袖。 - **Follower 行为特征**：完全被动，不主动发送消息，仅对收到的 RPC 做应答。 - **心跳本质**：参数中不携带任何日志数据的 `AppendEntries` RPC。 - **典型选举超时**：通常在 100ms 至 500ms 区间内。 --- ### [11:15](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=675s) 选举流程与三种可能的结果 当一台服务器决定发起选举时，它采取的第一项行动就是递增自己本地保存的任期编号（Current Term）。这一操作会产生一个该节点此前从未见过的、更大的全新任期号。正如 John Ousterhout 所强调的，“记住，在每一个新任期中发生的第一件事，就是举行一场选举。”随即，该节点从 Follower 状态切换为 Candidate 状态。Candidate 的唯一目标就是让自己赢得选举成为 Leader，为此它必须赢得集群中大多数（过半数）服务器的投票。 Candidate 会首先在本地把选票投给自己，随后向集群中所有其他节点并行发送 `RequestVote` RPC 索要选票。如果某个特定节点没有及时响应，Candidate 会不屈不挠地反复重试，直到最终拿到回复。在这一过程中，迟早会出现以下三种局面之一： ```mermaid flowchart TD accTitle: Three Outcomes of an Election accDescr: Candidate initiates vote and reaches one of three outcomes: win, step down, or split vote timeout. subgraph S1["发起选举"] A["递增任期 Term"] --> B["成为 Candidate"] B --> C["给自己投票并广播 RequestVote"] end subgraph S2["三种可能结局"] C --> D["局面 1：获得多数票"] C --> E["局面 2：收到有效 Leader 的 RPC"] C --> F["局面 3：选举超时 (选票瓜分)"] end subgraph S3["状态转移"] D --> G["成为 Leader，立即广播心跳"] E --> H["主动退让 (Step down)，变回 Follower"] F --> I["递增 Term，重启下一轮选举"] end ``` 第一种也是最常见、最理想的局面是：该 Candidate 赢得了集群多数派节点的选票。一旦多数票到手，它会立刻转换为 Leader 状态，并毫不迟延地向所有节点广播心跳消息，以此“宣示领地主权”（marks its territory）并确立自己的领袖地位。 第二种可能则是群雄并起：在它拉票的同时，有另一名 Candidate 抢先一步凑齐了过半数选票并登基为 Leader。这位新 Leader 随即开始向集群发送心跳或日志 RPC。如果当前 Candidate 收到了来自一个合法有效 Leader 的 RPC，它就会立刻放弃争夺。John Ousterhout 解释道：“我们称之为主动退位（stepping down），这会使它退回 Follower 状态，重新变得被动，仅仅去响应合法 Leader 的请求。” 第三种局面是选举无果而终。如果有多个节点在几乎同一瞬间转换成 Candidate，选票极易被瓜分（Split Vote），导致谁都无法凑足多数票。Candidate 发现这一死局的手段正是依赖计时：如果同样的选举超时时间已经耗尽，它既没能拿到多数票称王，也没收到来自任何有效 Leader 的音信，它就会认定发生了选票瓜分。此时它会退回起点，再次递增任期号，重新发起新一轮选举。 --- ### [13:59](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=839s) 选举的安全性与活性保障 一场合格的选举机制必须严密满足两大核心属性：安全性（Safety）与活性（Liveness）。安全性属性规定：在任何给定的任期内，至多只能有一名 Candidate 赢得选举。Raft 实现这一约束的方式极其简洁明了：每个节点在一个任期内只能且仅能投出唯一一张选票。一旦某节点投出了这票，面对其他 Candidate 的拉票请求它一概拒绝。此外，节点并不偏袒特定的参选者，“服务器其实并不在乎把票投给谁，它会把票投给第一个找上门来的候选人。” 为了保证这一原则在节点故障时依然坚挺，服务器必须把自己的投票记录写入磁盘等稳定介质（Stable Storage）。如果缺少这步持久化，节点很可能投完票后崩溃重启，把之前投过票的事忘得一干二净，接着在同一个任期里把票又投给第二台机器，从而引发灾难性的脑裂问题。 从数学逻辑上看，既然每台服务器只投一票，而获胜者又必须斩获过半数选票，那么单个任期内绝对不可能产生两位赢家。举例来说，在一个 5 节点的集群中，如果有 3 台节点把票投给了 Candidate A，那么留给 Candidate B 的选票最多只剩下 2 票，B 显然绝无可能凑齐多数派。尽管随着任期更迭，不同任期内可以产生不同的 Leader，但“在给定的单个任期内，至多只能有一个候选人赢得选举”。 | 核心属性 | 目标 | Raft 达成方式 | 关键实现细节 | |:--- |:--- |:--- |:--- | | **安全性 (Safety)** | 任意任期内至多一人称王（无脑裂） | 多数派交集（鸽巢原理）：赢得选举必须获得过半数投票 | 节点每任期仅投一票；先到先得；投票记录强制落盘以防崩溃重投 | | **活性 (Liveness)** | 系统不能无限期群龙无首，必有胜者 | 随机化选举超时（Randomized Election Timeouts） | 超时在 $[T, 2T]$ 区间离散化随机取值；打散苏醒时机 | 选举的另一大支柱是活性属性：必须确保系统能在合理时间内选出 Leader，而不是永久陷入无主停摆。如果每个节点都在同一时刻超时并发起竞选，就会周期性地爆发选票瓜分：节点在同一任期同时超时、拉票、瓜分选票、再次超时、递增任期重试……在理论上这种恶性循环甚至可能无限延续。 为了彻底化解这一死结，Raft 引入了随机化选举超时机制。每个节点在计算自己的下一次超时时间时，都会在一个区间内随机取值，通常是在时间 $T$ 到 $2T$ 之间（其中 $T$ 是集群配置的基础选举超时基准）。通过将各节点的超时触发点打散，“这使得两台服务器在同一时刻苏醒的可能性微乎其微；谁先醒来，谁就有充足的时间向其他所有人拉票并赢得选举，而此时其他竞争者甚至还没睡醒。”这一机制若想发挥最佳效果，必须保证打散的时间窗口远远大于单台服务器向其他节点通信拉票所需的广播时间（Broadcast Time）。只要超时窗口足够分散，最先苏醒的节点就能抢在其他人察觉之前稳稳当当地统一集群。 --- ### [16:54](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=1014s) 日志结构与正常运行时的复制机制 在确立了 Leader 之后，讲座切入 Raft 协议的第二大部分：Leader 在正常工作期间如何复制日志条目。在 Raft 中，集群内的每个服务器都维护着一份属于自己的独立日志副本。日志在逻辑上被划分为一个个离散的条目（Entry），每个条目都拥有一个指示其在日志中绝对位置的唯一递增索引（Index）。 每个条目内部封装了两项关键信息：第一项是供状态机（State Machine）执行的命令（Command）。这通常是客户端期望执行的操作，比如函数调用名及其参数，共识模块本身对命令的具体格式完全不敏感，仅由客户端和状态机达成一致即可；第二项则是该条目最初被 Leader 创建时所处的任期编号（Term Number）。沿着日志自底向上回溯，这些任期号呈现单调递增的趋势。 ```mermaid flowchart LR accTitle: Normal Log Replication Flow accDescr: Step-by-step path of a command from client to state machine application. A["客户端"] -->|"1. 提交命令"| B["Leader 日志追加"] B -->|"2. 广播 AppendEntries"| C["Follower 日志追加"] C -->|"3. 返回确认 ACK"| D{"获得多数派确认？"} D -- "是 (条目已提交)" --> E["Leader 状态机执行"] E -->|"4. 响应结果"| A E -->|"5. 后续心跳通知"| F["Follower 状态机执行"] ``` 每台机器都必须确保其日志在系统崩溃后依然完好无损，因此日志通常写入磁盘等持久化存储设备。每当服务器修改自己的日志内容时，必须在向集群中其他节点返回任何响应之前，先行完成对磁盘安全副本的刷盘同步。 在日志机制中，一个最为关键的概念是“提交”（Commit）： - 如果某条日志条目已经被安全地持久化存储在集群中的过半数服务器上（例如示例图中的 7 号条目），该条目就被正式认定为已提交（Committed）。 - 一旦条目达成提交状态，将其交付给状态机执行便彻底安全了。Raft 会向外部保证该条目的持久不可逆性，并且该条目迟早会被集群中每一台服务器上的状态机依次执行。 - 在讲座展示的示例中，7 号条目及其此前所有前置条目均已达成提交；而 8 号条目由于仅被 5 台服务器中的 2 台存储，尚处于未提交状态。John Ousterhout 在此处特别提醒，在后续讨论跨服务器更替的日志一致性维护时，这一提交的判定标准还会加入微调。 在正常运行状态下，整个处理链路相当直观流畅：客户端向 Leader 发送一条希望被所有状态机执行的命令；Leader 收到后首先将该命令按序追加到自己本地的日志尾部；紧接着，Leader 向集群中的 Followers 并行广播 `AppendEntries` RPC；随后 Leader 静候对端响应。一旦 Leader 收集到了足够多的成功确认，使得该条目在包括自己在内的过半数节点上成功持久化，条目即宣告提交。此时，Leader 终于可以把命令交付给自己的状态机执行，待执行完毕，将计算结果返回给客户端。 ### [20:02](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=1202s) 日志提交与快速响应机制 当 Leader 确认某个日志条目已经达成提交（Committed）后，并不会通过单独的广播来宣布，而是将这一信息捎带在后续发往其他服务器的 `AppendEntries` RPC 请求中。随着后续通信的进行，集群中的每个 Follower 最终都会知晓该条目已经被提交，并在各自的状态机（State Machine）上执行相应的命令。 在分布式环境下，网络延迟和节点崩溃不可避免。如果某个 Follower 崩溃或响应极度迟缓，Leader 不会放弃，而是会一遍又一遍地重试 `AppendEntries` 调用；一旦崩溃的节点重新上线，它就能立即收到重试请求并追赶进度。然而，在常规执行路径上，Leader 根本不需要等待集群中每一个 Follower 的回复，只要收到来自多数派（Majority/Quorum）节点的响应，足以确保该条目持久化存储在多数派服务器上，Leader 就可以认定提交成功。 ```mermaid flowchart LR accTitle: Normal Case Log Replication accDescr: 客户端发送命令给Leader，Leader只需等待多数派响应即可向状态机执行并返回 Client["客户端 (Client)"] -->|"提交命令"| Leader["Leader 节点"] subgraph Cluster ["多数派判定"] Leader -->|"AppendEntries"| S1["快速 Follower"] Leader -.->|"延迟 / 崩溃"| S2["慢速 Follower"] S1 -->|"成功响应"| Leader end Leader -->|"执行并返回结果"| Client ``` 这种多数派机制赋予了 Raft 在正常工况下的高性能优势。Leader 只要拿到集群中响应最快的那些节点组成的多数派确认，便能立即执行命令并向客户端返回结果。正如讲师所指出的，集群整体不会被单点拖垮： > “So for example one slow server doesn't necessarily slow down the clients because the leader doesn't have to wait for that server.”（因此，举例来说，一台慢速服务器并不一定会拖慢客户端，因为 Leader 根本不必等待那台服务器。） - 日志提交信息通过后续周期性的 `AppendEntries` RPC 顺带传递给 Followers。 - 崩溃节点的重试是持久且无限次的，直至节点恢复或通信恢复。 - 客户端命令完成的充要条件是：写入 Leader 并被集群中多数派（即最快的若干节点）确认持久化。 --- ### [21:12](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=1272s) 日志匹配特性与一致性检查 Raft 致力于在集群中各节点的日志间保持高度的一致性。尽管崩溃的存在使得所有节点始终完全相同成为不可能，但系统通过两项硬性不变式（Invariants）来维护日志结构的一致： 1. **唯一标识规则**：日志索引（Index）与任期号（Term）的组合能够全局唯一地标识一条日志条目。换言之，如果两份日志在相同的索引位置拥有相同的任期号，那么它们在该位置所包含的命令必然完全相同。 2. **前驱一致性传递**：如果两份日志在某一索引处拥有相同的任期号，那么从日志开头直到该位置的所有前驱条目也全部完全相同。 基于上述两条性质，一旦某个特定日志条目被提交，它之前的所有条目也自动被视为已提交。因为提交意味着该条目存在于多数派节点上，由前驱一致性可知，早前所有的条目必然也完好地保存在该多数派节点中。 为了在工程实现中严格维系这种归纳性质，Raft 在每一次 `AppendEntries` RPC 中都设置了一致性检查机制。Leader 在调用 Follower 时，除了携带新增条目外，还会附带紧邻新条目前一个条目的 `prevLogIndex` 与 `prevLogTerm`。Follower 接收到请求后，必须在其本地日志对应的索引处比对任期号；只有本地存在完全吻合的前驱条目时，才会接受并追加新日志；只要不吻合，Follower 就会果断拒绝本次 RPC。 ```mermaid flowchart TD accTitle: AppendEntries Consistency Check accDescr: Leader发送带有prevLogIndex和prevLogTerm的RPC，Follower通过比对决定接受或拒绝 A["Leader 发送 AppendEntries<br>(包含新条目及前驱条目: prevLogIndex, prevLogTerm)"] --> B{"Follower 本地该位置<br>是否包含匹配的前驱条目？"} B -- "完全匹配" --> C["接受追加新日志条目"] B -- "任期不同或缺失" --> D["拒绝 AppendEntries RPC"] ``` 以具体场景为例： - **匹配成功情况**：Leader 收到客户端命令 `jump` 准备追加到索引 5，前驱条目位于索引 4、任期 2。Leader 发送附带 `prevLogIndex = 4, prevLogTerm = 2` 的 RPC。Follower 查看本地索引 4，任期确实为 2，比对无误，遂成功将 `jump` 写入日志。 - **匹配失败情况**：若 Follower 的索引 4 处记录的任期与 2 不符，RPC 直接被拒绝。 这一比对机制犹如数学归纳法中的递推步。新条目的接受以前置条目的一致为前提，而前置条目本身也是经过同样检查写入的，层层递推便确保了链条的绝对可靠： > “This consistency check is really important and you can think of it kind of like an induction step in the proof of the properties on the preceding slide.”（这种一致性检查极其重要，你可以把它看作是上一页幻灯片中那些属性证明过程里的归纳递推步骤。） --- ### [24:43](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=1483s) Leader 变更与混乱日志的收敛 当新 Leader 刚当选上台时，系统中的日志往往处于并不干净的状态。前任 Leader 可能在完全同步某些条目之前就突然崩溃，导致未提交日志悬在半空。面对这种情况，Raft 并没有为新 Leader 设计任何独立的“日志清理阶段”（Cleanup phase），而是让新 Leader 直接投入正常运转，日志清理工作完全是在正常服务流程中自然而然完成的。 之所以不设专门的清理阶段，是因为新 Leader 启动时集群中某些节点可能正处于宕机状态，Leader 根本不可能瞬间整理完所有节点的日志。系统必须保证在部分节点下线的情况下仍能对外服务，而下线的节点可能需要很长时间才会重启。因此，系统只能依靠常态化运行逐步收敛各副本日志。 Raft 解决冲突的核心哲学非常直接：**始终认定 Leader 的日志是绝对正确的，并包含一切关键内容**。Leader 的唯一使命，就是假以时日，强制所有 Follower 的日志无条件向自己的日志对齐。 如果 Leader 还没完全收敛日志就崩溃，随后产生的数任 Leader 也接连发生崩溃和网络分区，集群日志就会堆积出大量杂乱无章的未提交条目。讲师在此引入了一个简化的图示记法：鉴于 `(Index, Term)` 已能全局唯一锁定条目内容，图表中不再绘制具体的命令名称，只标注条目的任期号。 在复杂故障案例中（例如服务器 4 和 5 在任期 2、3、4 期间担任 Leader，但未成功向外复制就遭遇分区与崩溃；随后服务器 1、2、3 在任期 5、6、7 轮流当选却无法与 4、5 通信），各节点的日志会出现严重分歧： | 节点 | 索引 1 (Term) | 索引 2 (Term) | 索引 3 (Term) | 索引 4 (Term) | 索引 5 (Term) | |:--- |:--- |:--- |:--- |:--- |:--- | | **S1-S3 多数派** | 1 | 1 | 1 (已提交) | 5 / 6 / 7 | 未对齐 | | **S4-S5 隔离节点** | 1 | 1 | 1 (已提交) | 2 / 3 / 4 (孤立) | 4 (孤立) | 在这一片狼藉的局面下，索引 1 到 3 已经达成多数派复制并已提交，必须被绝对保全。而其余未提交的条目既未交付给状态机，也没有任何客户端看到过它们的执行结果，因此统统属于“可弃之物”（Expendable）。一旦任期 7 的 Leader 重新恢复与所有节点的通信，它就会以自己的日志为基准覆盖所有冲突条目。 --- ### [27:31](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=1651s) 系统安全性需求与 Leader 完整性属性 在丢弃和覆盖日志以促成一致的过程中，最核心的问题是如何确保系统的绝对安全。所有复制状态机算法都必须遵循一条不可逾越的根本安全性要求： > “Once a particular state machine has received a log entry and applied it as a command we must make sure that no other state machine ever applies a different value for that log entry.”（一旦某个特定状态机接收了一条日志条目并将其作为命令应用，我们必须确保没有任何其他状态机曾对该日志条目应用过不同的值。） 为保证所有状态机严格按照相同的顺序应用完全相同的命令，Raft 提出了一个更为具体且严格的“Leader 完整性”（Leader Completeness）属性：**一旦 Leader 判定某个条目已经提交，Raft 必须保证该条目必然存在于系统未来所有新任 Leader 的日志当中**。 该属性如何自洽地支撑根本安全性？推导逻辑包含三个紧密衔接的环节： 1. **追加专属原则**：Leader 永远不会覆盖或截断自己的日志，它对本地日志只做追加操作（Append-only），因此已存在于 Leader 日志中的条目绝不会被篡改。 2. **唯一提交源头**：一个条目要想被提交，必须先存在于当前 Leader 的日志中；既然未来的 Leader 都会包含此条目，未来就不可能提交与该位置冲突的其他值。 3. **状态机应用依赖于提交**：条目在输入状态机之前必须首先完成提交。 把这三点组合起来，就完全兑现了系统在状态机层面的一致性承诺。 然而，讲师明确指出，此前讲解的基础 Raft 规则（仅凭简单的多数派投票）还无法完全闭环保证“未来 Leader 必然包含所有已提交条目”。为了填补这一安全漏洞，Raft 必须在两个关键机制上打上补丁： - **修改选举流程（Election Restriction）**：在投票阶段加入约束条件，如果候选人的日志没有包含“足够的正确内容”，其他节点将直接拒绝投票，阻止其夺取领导权。 - **微调提交判定定义（Commitment Rule）**：不能仅凭多数派复制就盲目判定条目提交，在某些边界情况下必须推迟提交判定，直至满足能够绝对确保该条目持久存在于未来所有 Leader 日志中的安全条件为止。 ### [30:09](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=1809s) 选举限制：确保新 Leader 拥有所有已提交日志 为了保证系统的安全性，Raft 必须确保选出的新 Leader 包含之前所有已经提交（Committed）的日志条目。但这在实现上面临一个极其棘手的问题：单凭当前在线的节点，系统其实无法确切知道某条日志到底有没有被提交。John Ousterhout 举了一个三节点集群的例子：假设集群正在选举新 Leader，但其中一台服务器离线不可用，此时仅凭剩余两台在线服务器的视角，根本无法断定日志索引 5 究竟是否已经被提交，因为这完全取决于该日志是否已经被写入那台离线的服务器。由于无法实时确知提交状态，Raft 的解决思路并不是去核实日志是否提交，而是通过限制选举规则，“挑选一个拥有最完整日志的候选人，使其最有希望包含全部已提交的条目”。 ```mermaid flowchart TD accTitle: Raft 选票请求日志比较流程 accDescr: 投票节点收到候选人投票请求时比较双方最后一条日志的任期与索引来决定是否投票 subgraph LogCompare["日志比较逻辑 (RequestVote)"] A["候选人发送 RequestVote\n(lastLogIndex, lastLogTerm)"] --> B{"投票人 lastLogTerm\n> 候选人 lastLogTerm?"} B -- "是" --> C["拒绝投票\n(投票人日志更新)"] B -- "否" --> D{"投票人 lastLogTerm\n== 候选人 lastLogTerm?"} D -- "是" --> E{"投票人 lastLogIndex\n> 候选人 lastLogIndex?"} E -- "是" --> C E -- "否" --> F["允许投票\n(候选人日志至少一样新)"] D -- "否" --> F end ``` 这种机制的核心是日志比较。当候选人向其他节点请求投票（`RequestVote` RPC）时，必须附带自己日志的元数据，且只需提供两项关键信息：最后一条日志的索引（`lastLogIndex`）以及该条目所属的任期（`lastLogTerm`）。正如之前讨论过的日志匹配特性，这两个数值就能唯一确定整条日志的前缀。收到请求的投票节点会拿自己的日志与候选人进行比较：如果投票人自身的日志更加完整，它就会直接拒绝投出选票。更具体、精确的判断规则如下： - 如果投票人日志中最后一条条目的任期大于候选人日志最后一条条目的任期，则投票人日志更完整，拒绝投票。 - 如果两者最后一条条目的任期相同，但投票人的日志长度长于候选人（即投票人的 `lastLogIndex` 更大），则投票人日志更完整，同样拒绝投票。 - 只有当候选人的最后一条日志任期更大，或者任期相同但日志至少与投票人一样长时，投票人才可能同意投票。 正如 John Ousterhout 所总结的：“这样做的结果是，无论谁赢得选举，都能保证在给它投票的那些节点（即集群的某个多数派）中拥有最完整的日志。” ### [32:26](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=1946s) 提交当前任期条目与极端反例分析 在明确了选举比较规则后，John Ousterhout 带领大家推演具体的运行场景，核心观察点在于“Leader 刚判定某条日志已提交的时刻”。这里分为两种情况：提交的是当前任期生成的日志，或是来自先前任期的未决日志。第一种情况非常直观且安全：假设在任期 2 中，Leader 刚将条目 4 成功复制到了服务器 S3 上，此时该条目已存在于集群多数派（S1、S2、S3）中，Leader 随即宣布该条目已提交并可以应用到状态机。此时条目 4 是绝对安全的，因为 S5 的任期过于陈旧无法获得多数票，S4 日志虽同属任期 2 但太短也拿不到票，下一任 Leader 必定从拥有该条目的 S1、S2 或 S3 中产生。 真正的危险潜伏在第二种情况中：Leader 试图去提交一条最初是由更早任期创建的日志条目。Ousterhout 详细拆解了一个极为经典的五节点故障场景：任期 2 的 Leader 在其任期结束前，仅仅将条目 3 复制到了两台机器（S1 和 S2）上就下线了；随后任期 3 的 Leader 选出（未包含条目 3），自己写入了若干任期 3 的条目后同样宕机；进入任期 4 后，另一台机器（例如 S1）当选 Leader，开始尝试让其他跟随者的日志与自己同步，于是将那条来自任期 2 的旧条目 3 复制到了 S3 上。 此时，条目 3 已经确确实实保存在了多数派机器（S1、S2、S3）上。然而，如果此时该 Leader 认为条目 3 已经提交，系统就会出现严重错误。因为如果任期 4 的 Leader 在此刻突然宕机，服务器 S5 完全有可能在不包含 S1 的多数派（例如获得 S2、S3、S4 的选票）支持下当选为新任期 Leader——因为 S5 最后的日志任期是 3，而 S2、S3、S4 最后的日志任期仅为 2。一旦 S5 当选，它就会强制将自己任期 3 的日志覆盖到整个集群，导致先前已经分布在多数派上的条目 3 被彻底抹去。Ousterhout 直截了当地指出：“所以在这种情况下，仅凭新的选举规则本身并不足以保证安全性，我们还必须修改提交规则。” ### [35:34](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2134s) 提交规则修正与 Raft 安全性保证 为了堵住上述漏洞，Raft 对提交（Commitment）规则做出了关键修改。在原先的直觉认知中，Leader 只要看到一条日志被保存在集群多数派上就可以认为其已提交；但新的安全约束规定：Leader 不能单凭多数派复制就直接提交来自之前任期的日志条目，Leader 必须能够看到“至少有一条属于自己当前任期的日志条目也成功存储到了多数派服务器上”。 回到刚才的五节点推演中：任期 4 的 Leader 将老旧的条目 3 复制到多数派节点后，不能立即将其提交并交给状态机执行；它必须继续等待，直到属于当前任期（任期 4）的条目 4 也成功复制到多数派节点上。一旦条目 4 达到多数派，条目 4 和此前间接覆盖的条目 3 就同时变为了安全状态。此时集群中已经有多数派节点拥有任期 4 的日志，S5 再也无法获得所需的选票（集群中只有 S4 可能给 S5 投票，但凑不足多数派），因此 S5 绝无可能当选新 Leader，条目 3 和 4 便永久不可逆转。 John Ousterhout 强调：“将比较日志的新选举规则与这条新提交规则相结合，我们就能保证 Raft 的安全性属性（Safety Property）始终成立：一旦 Leader 判定某条日志已提交，该条目必将存在于未来每一任 Leader 的日志中。”虽然在课堂上仅直观推导了该条目必定存在于紧邻的下一任 Leader 中，但数学归纳法可以很容易证明它在未来的所有任期中都不会丢失。 ### [37:29](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2249s) 日志不一致的表现形态与恢复机制（nextIndex） 当 Leader 自身的日志正确性得到保障后，接下来的任务就是强迫所有 Follower 的日志与 Leader 保持严格一致。在真实的分布式网络分区或节点频繁宕机中，Follower 的日志可能呈现出各种混乱的状态： - Follower 可能遗漏了 Leader 拥有的条目（如示例中的跟随者 A、B、E 缺失了最新日志）； - Follower 也可能包含 Leader 根本没有的多余条目（如某些节点遗留了来自任期 7、任期 2 或任期 3 的未提交废弃条目，或者任期 6 的多余条目）。 ```mermaid flowchart LR accTitle: Leader 探测与回退 nextIndex 流程 accDescr: Leader 发送 AppendEntries 触发一致性检查，失败后递减 nextIndex 逐步向前试探 subgraph SyncStep["日志一致性探测流程"] direction LR L1["新 Leader 就职\n设置 nextIndex = 11"] --> RPC1["发送 AppendEntries\n带上 prevLogIndex=10, prevLogTerm=6"] RPC1 --> CHK{"Follower A 一致性检查\n匹配失败？"} CHK -- "拒绝 RPC" --> DEC["Leader 递减 nextIndex\nnextIndex = 10 -> 9... -> 5"] DEC --> RPC2["重试发送 AppendEntries\n带上 prevLogIndex=4, prevLogTerm=..."] RPC2 --> MATCH["Follower A 匹配成功\n覆写多余条目并追加缺失日志"] end ``` 为了消除多余条目并补齐缺失条目，Leader 为集群中的每一个 Follower 都在内存中维护了一个状态变量，命名为 `nextIndex`。它表示 Leader 计划发送给该 Follower 的下一条日志在日志数组中的索引。当一个节点刚当选 Leader 时，它会将所有 Follower 的 `nextIndex` 初始值统一设置为自己日志最后一条条目的下一个位置（例如，Leader 自身最后一条日志的索引是 10，则初始将所有跟随者的 `nextIndex` 都设为 11）。 Leader 会利用 `AppendEntries` RPC 携带的一致性检查机制来逐步修复日志： - Leader 刚就职后发出的第一个 RPC 通常是心跳包（Heartbeat）。心跳与普通日志复制 RPC 机制完全一致，内部同样包含一致性检查参数，只是不携带任何新的日志条目。 - 当针对跟随者 A 发送 RPC 时，Leader 会带上紧邻 `nextIndex` 之前的那条日志的信息（即索引 10 和任期 6）。 - 跟随者 A 检查自己索引 10 的位置，发现根本没有匹配的任期 6 条目，于是果断拒绝（Reject）该 RPC。 - Leader 收到拒绝响应后的处理方式非常简洁直接：“当 Leader 看到拒绝响应时，其应对策略非常简单，只需将 `nextIndex` 减 1 即可。” - Leader 将针对 A 的 `nextIndex` 降至 10，随后带着索引 9 的信息重试；如果依然检查失败，就继续循环递减 `nextIndex`（9、8、7……），一路向前回溯探测。 - 最终，当针对跟随者 A 的 `nextIndex` 降至 5 时，Leader 在请求中带上的前置条目信息（索引 4）终于与跟随者 A 本地的日志完全吻合。从这个匹配点开始，Follower 接受 RPC，Leader 随后便能顺理成章地覆盖掉跟随者后续的多余脏数据，并向后逐步补齐所有缺失的历史日志。 - 关键状态变量：`nextIndex` 是 Leader 维护的易失性状态，选举后初始化为 `leaderLastIndex + 1`。 - 一致性检查失败的处理成本：最基础的实现中，每次被拒仅仅递减 1，虽然可能需要多次网络往返才能找到匹配点，但逻辑极其健壮且安全。 ### [40:40](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2440s) 日志覆盖截断与领导者变更总结 在解决跟随者日志与领导者不一致的过程中，领导者会通过调整 `nextIndex` 来探测匹配点。以 Follower B 为例，当 `nextIndex` 最初设定为 11 时，一致性检查失败；领导者便会逐步递减该值，“一次又一次地往后倒退”，直到 `nextIndex` 降至 4。此时，用于一致性检查的前一条日志索引（`prevLogIndex`）为 3，任期号为 1，恰好与跟随者本地的条目匹配，跟随者的日志由此开始逐步补齐。 在此同步机制中，存在一条关键规则：一旦跟随者收到一条新日志并发现它与本地同一槽位中原有的条目冲突，跟随者将截断（truncate）冲突位置及之后的所有日志。例如，若领导者将第 4 槽位的条目发送给跟随者，而跟随者该位置已有冲突数据，跟随者不仅会覆盖该槽位，还会将该槽位之后的所有日志彻底抹去。其核心依据在于：如果某一条日志是多余或冲突的，那么紧随其后的所有条目必然也是无效的。 John Ousterhout 对整个领导者变更（Leader Changes）板块进行了精炼总结，指出该过程主要包含两大核心任务： 1. **系统安全性（Safety）：** 必须确保领导者选举机制正确，并在严格的判定条件下确认哪些日志条目已被提交（committed）。 2. **日志对齐（Log Consistency）：** 新领导者当选后，唯一需要做的工作就是强制所有跟随者的日志与自身保持一致。而 `AppendEntries` RPC 附带的一致性检查机制，恰好提供了完成这一同步所需的全部信息。 ### [42:14](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2534s) 旧领导者处置：通过任期号检测与降级 领导者变更带来的另一棘手问题是：旧领导者可能并未真正宕机。例如发生网络分区时，旧领导者与集群其余节点断开。剩余节点在等待选举超时后，成功选出新领导者。此时若网络恢复，旧领导者对新的选举和新领导者一无所知，仍会试图继续行使领导职责（如向其他节点复制日志），甚至可能继续接收客户端请求并写入本地。 ```mermaid flowchart TD accTitle: 任期号检测与角色降级机制 accDescr: 展示当发送方与接收方任期号不匹配时，双方如何根据任期大小执行拒绝或降级更新操作。 subgraph SenderOlder["场景 A：发送方任期较旧"] A1["发送方 Leader<br/>（Term 较小，已过时）"] -->|"RPC (Term=旧)"| B1["接收方 Follower<br/>（Term 较大）"] B1 -->|"1. 拒绝 RPC<br/>2. 返回自身较新的 Term"| A1 A1 -->|"3. 发现自身过时，<br/>降级为 Follower 并更新 Term"| A1 end subgraph ReceiverOlder["场景 B：接收方任期较旧"] A2["发送方 Leader<br/>（Term 较大）"] -->|"RPC (Term=新)"| B2["接收方<br/>（Term 较小）"] B2 -->|"1. 降级为 Follower 并更新 Term<br/>2. 正常处理该 RPC"| B2 end ``` Raft 依靠全局递增的“任期号”（Term）彻底解决了这种“脑裂”隐患。具体机制如下： - **RPC 携带任期：** 每一个 RPC 请求都必须包含发送方当前的任期号。接收方收到后将其与自身的任期号比对，若不匹配，任期落后的一方必须立即更新自身状态。 - **发送方过时：** 若发送方的任期小于接收方，说明发送方已处于废弃状态。接收方直接拒绝执行该 RPC，并在响应中附带自己的最新任期号。发送方看到后“意识到自己的任期已经过时，随后主动降级重新变成跟随者，并同步更新其任期”。 - **接收方过时：** 若接收方的任期落后于发送方，接收方若不是跟随者则立即降级为跟随者，将自身任期更新为最新值，但会正常处理该 RPC，无需拒绝。 在选举过程中，候选人向多数派节点发送投票请求（RequestVote），RPC 中携带新任期，导致多数派节点的任期被同步更新。因此，在新领导者产生后，被废黜的旧领导者绝不可能再将其新日志成功写入集群的多数派，因为在尝试写入时必定会撞上至少一个拥有更新任期的节点，触发任期不匹配并迫使其立刻降级。John Ousterhout 总结道：“如果出现过时的情况，任期概念能检测出这一点。” - 每一个 RPC 均附带发送者的 `Term`。 - 接收方任期较新时立即拒绝 RPC，并将新任期回传。 - 选举过程已确保多数派节点拥有最新任期，旧领导者无法再凑齐多数派写入。 ### [45:18](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2718s) 客户端交互与 Exactly-Once 语义 客户端与 Raft 集群的交互模型整体上十分清晰。客户端直接将指令发送给领导者；若客户端不知道谁是领导者，可以向集群中的任意服务器发起请求。若该服务器不是领导者，它会告知客户端当前已知领导者的身份，客户端随后重试即可。领导者接收到指令后，不会立即给客户端返回结果，而是先将指令追加至本地日志，通过复制确保日志提交到多数派服务器的磁盘上，并交给状态机（State Machine）执行完毕后，才把最终执行结果返回给客户端。 然而，若领导者在执行完状态机指令后、向客户端返回响应前意外崩溃，或者网络通信超时，客户端便无法获知该指令究竟是否成功执行。此时，客户端别无选择，只能将同一条指令重试发送给新的领导者。这带来了严重的风险：指令可能被重复执行两次。 为了实现线性化（Linearizability）以及严格的“仅执行一次”（Exactly-Once）语义，Raft 设计了去重机制： 1. **唯一标识符：** 客户端为每个指令生成一个全局唯一的 ID，并随指令一并发送给领导者。 2. **入库记录：** 领导者将此 ID 与指令一同持久化到日志条目中。 3. **查重与幂等处理：** 领导者在接收新指令时，会首先检查日志中是否已包含具有相同 ID 的条目。若发现 ID 已存在，领导者直接忽略这个重复指令，等待旧指令被状态机执行完成后，直接把上次执行的旧响应返回给客户端，绝不重复调用状态机。 ### [48:01](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=2881s) 集群配置变更的安全性危机与联合共识 系统的配置变更涉及集群成员信息（每个服务器的 ID 及其网络通信地址）的变动，这对于判断领导者选举或日志提交所需的多数派至关重要。配置变更往往源于机器硬件故障替换，或是管理员期望调整集群的副本数。 在配置变更过程中，绝对不能直接从旧配置（$C_{old}$）单步切换至新配置（$C_{new}$）。假设集群原先由 3 台服务器构成，现在计划新增 2 台扩容至 5 台。若要求所有节点直接切换配置，由于各节点接收并应用变更指令在时间上无法做到绝对同步，必然出现过渡阶段。在此阶段： - 节点 1 和节点 2 仍处于旧配置（3 节点系统），它们两台联合即可构成旧配置的多数派（2/3），足以选出一个领导者并提交某项决议； - 与此同时，节点 3、4、5 已经切换到了新配置（5 节点系统），它们三台也能构成新配置的多数派（3/5），从而选举出另一个领导者并提交完全冲突的决议。 ```mermaid flowchart TD accTitle: 单阶段配置变更引发双重多数派冲突 accDescr: 展示旧配置与新配置各自独立形成多数派并导致系统脑裂冲突的过程。 subgraph SplitBrain["同时存在的冲突多数派"] subgraph Cold["旧配置 (3 节点系统)"] S1["Server 1"] S2["Server 2"] S1 --- S2 M1["多数派 (2/3) 形成决议 A"] --- S1 end subgraph Cnew["新配置 (5 节点系统)"] S3["Server 3"] S4["Server 4"] S5["Server 5"] S3 --- S4 S4 --- S5 M2["多数派 (3/5) 形成决议 B (与 A 冲突)"] --- S3 end end ``` 针对这种单阶段切换的缺陷，John Ousterhout 幽默且严肃地告诫道：“如果有人告诉你，他们认为自己可以在单阶段内完成分布式决策，你应该非常认真地质疑他们，因为要么他们错了，要么他们发现了全世界其他人还不知道的东西。” 为了确保平滑安全，Raft 引入了两阶段协议（Two-Phase Protocol）。在进入目标配置前，集群首先进入一个被称为“联合共识”（Joint Consensus）的中间过渡阶段。在该过渡阶段中，集群包含新旧两套配置的所有服务器全集（并集），而任何选举或日志提交决策，都必须在旧配置的多数派和新配置的多数派中同时获得通过。 - 配置信息包含服务器 ID 与网络通信地址，直接决定多数派门槛。 - 节点应用配置存在微小时间差，单阶段切换极易导致裂脑与互相冲突的多数派。 - 联合共识（Joint Consensus）将过渡期定义为新旧配置的并集，并强制要求两个独立配置的多数派协同决策。 ### [50:46](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=3046s) 联合共识（Joint Consensus）的过渡机制 在集群配置变更时，系统绝不能出现由新旧配置各自独立做出决定的情况。Raft 采用的方法被称为“联合共识”（Joint Consensus）。变更流程始于客户端向当前 Leader 提交变更请求，就像提交普通的日志操作一样。Leader 收到请求后，会向自身的本地日志写入一条特殊的配置条目，该条目同时包含新旧两个配置集合，即 $C_{\text{old+new}}$。写入后，Leader 通过正常的 `AppendEntries` RPC 将其复制给集群中的其他节点。 配置条目与其他普通日志条目最关键的区别在于：配置条目一经写入日志即立刻生效。节点在将新的配置写入本地日志后，不需要等待该条目被提交（Commit），就立刻以此新配置指导自身的所有运行规则。因此，Leader 在把 $C_{\text{old+new}}$ 记入日志的瞬间，其决策逻辑就切换为了联合共识规则。这意味着后续任何条目的提交，都必须同时获得旧集群的一半以上节点和新集群的一半以上节点分别同意。 在 $C_{\text{old+new}}$ 被完全提交之前，如果 Leader 发生崩溃，集群仍可能由仅运行在 $C_{\text{old}}$ 下的节点接管。但一旦 $C_{\text{old+new}}$ 被正式提交，就绝对不再可能出现只凭 $C_{\text{old}}$ 就做出决定的节点。因为 Raft 的选举规则要求候选人必须包含所有已提交的日志条目，此后当选的任何 Leader 必然包含 $C_{\text{old+new}}$，从而必须在联合共识下做出所有决策。 ```mermaid flowchart LR accTitle: Raft Joint Consensus Transition accDescr: Timeline diagram showing transition from C-old to C-old-plus-new to C-new. subgraph Phase1["阶段 1: 仅旧配置"] Cold["C_old 单独决策"] end subgraph Phase2["阶段 2: 联合共识"] ColdNew["C_old+new 双重多数派决策"] end subgraph Phase3["阶段 3: 仅新配置"] Cnew["C_new 单独决策"] end Phase1 -->|"写入并提交 C_old+new"| Phase2 Phase2 -->|"写入并提交 C_new"| Phase3 ``` - **立即生效原则**：节点一旦将配置条目写入日志，即刻按新规则运行，绝不等待该条目达成 Commit。 - **双重多数派要求**：在 $C_{\text{old+new}}$ 规则下，无论是选举还是日志提交，都必须分别通过 $C_{\text{old}}$ 的多数派和 $C_{\text{new}}$ 的多数派认证。 ### [53:39](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=3219s) 推进至新配置与两阶段共识的必然性 当联合共识条目 $C_{\text{old+new}}$ 成功在双重多数派中提交后，Leader 便可以生成第二条配置变更日志——$C_{\text{new}}$，并同样将其复制到集群节点中。如同前一阶段一样，在 $C_{\text{new}}$ 达成提交前，集群可能会在 $C_{\text{new}}$ 与 $C_{\text{old+new}}$ 两种状态之间切换；但随着 $C_{\text{new}}$ 最终被提交，整个集群以后的所有决策便彻底迁移并锁定在 $C_{\text{new}}$ 之上。 整个过程的核心在于：在任何时间点，$C_{\text{old}}$ 与 $C_{\text{new}}$ 绝不可能在没有互相协商的前提下独自达成决策。系统先经历一段只有 $C_{\text{old}}$ 可独立决策的时期，最后进入只有 $C_{\text{new}}$ 可独立决策的时期，而这两个时期在时间轴上完全没有交集，中间被必须双方同时确认的联合共识阶段严密隔开。这从根本上杜绝了脑裂和分裂共识的发生。 John Ousterhout 强调，这种两阶段特性并非 Raft 的特例，而是分布式一致性的客观规律：“If anybody comes to you with a distributed agreement algorithm and they claim it works in a single phase, you should be very skeptical because either they're mistaken or they've discovered something really important and new that none of the rest of us know.”（如果有人带着一个分布式共识算法来找你，并声称它只需单阶段就能工作，你应该持高度怀疑态度，因为他们要么搞错了，要么就是发现了某种我们所有人都不知道的极其重要的新东西。） ### [55:17](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=3317s) 旧 Leader 下台机制与过渡期边界 在配置变更过程中存在一个特殊的边界情况：如果当前的 Leader 本身并不包含在新的配置集合 $C_{\text{new}}$ 当中，系统该如何运转？既然新集群中已经没有该机器的位置，它最终必然不能一直霸占 Leader 地位。 Raft 的处理策略非常明确：即便当前 Leader 不在新配置中，它也会继续履职，主导将 $C_{\text{new}}$ 写入并复制到集群中，直到 $C_{\text{new}}$ 正式提交的那一刻，旧 Leader 才会主动退位（Step Down）。退位后，新配置中的 Followers 将发生选举超时，并在 $C_{\text{new}}$ 范围内选出新一任 Leader，集群随即完全步入新生命周期。这意味着旧 Leader 会在一段短暂的时间内为自己并不属于其中的集群充当管理者，但正是这种设计确保了变更流程的平滑过渡与安全性。 - **退位触发点**：旧 Leader 只有在 $C_{\text{new}}$ 成功提交后才下台，而不是在将 $C_{\text{new}}$ 写入日志的瞬间下台。 - **新 Leader 来源**：旧 Leader 退位后，只有 $C_{\text{new}}$ 集合中的节点有资格竞选并成为后续的 Leader。 ### [56:32](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=3392s) Raft 算法全貌回顾与核心设计哲学 随着配置变更机制的厘清，John Ousterhout 对整个 Raft 课程讨论的六大核心模块进行了结构化总结： 1. **Leader 选举**：确保在任何给定的任期（Term）内，至多只有一个服务器能担任 Leader。 2. **正常运转（Normal Operation）**：Leader 接收客户端请求并复制到整个集群，其中 `AppendEntries` 内嵌的日志一致性检查是保证日志顺序和后续恢复一致性的关键抓手。 3. **Leader 换届与安全性（Safety）**：确保一旦某条日志被提交，它就会永久留存且不可更改，并强制所有 Follower 的日志最终与 Leader 保持绝对一致。 4. **清理陈旧 Leader**：通过任期号和相关机制，防止被废黜的旧 Leader 在恢复后对系统产生破坏。 5. **客户端交互协议**：处理服务器故障并为客户端提供幂等性保证，使其能在节点崩溃重启中无损恢复。 6. **配置动态变更**：依托联合共识机制，实现全自动、零停机且数学上安全的集群成员拓扑伸缩。 在全课的结语中，John Ousterhout 总结了构建此类分布式容错系统的核心心法：“The key element of this algorithm is that the system has to work perfectly even if just a bare majority of the servers are up, which means it can't ever depend on having complete information or knowledge of what's going on.”（该算法的核心要素在于：即便只有勉强过半数的服务器处于存活状态，系统也必须能够完美运行；这意味着它绝不能依赖对当前局势的完全认知或完整信息。）那些处于失联状态的服务器上可能埋藏着不可预知的历史数据，因此算法在每一个交互分支的设计上，都必须有能力在缺乏全局信息的前提下，仅凭局部与法定人数的共识做出正确无误的决策。 ## Notable quotes > [53:39](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=3219s) If anybody comes to you with a distributed agreement algorithm and they claim it works in a single phase, you should be very skeptical because either they're mistaken or they've discovered something really important and new that none of the rest of us know. — John Ousterhout > [56:32](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=3392s) The key element of this algorithm is that the system has to work perfectly even if just a bare majority of the servers are up, which means it can't ever depend on having complete information or knowledge of what's going on. — John Ousterhout > [27:31](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=1651s) Once a particular state machine has received a log entry and applied it as a command we must make sure that no other state machine ever applies a different value for that log entry. — John Ousterhout > [20:02](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=1202s) So for example one slow server doesn't necessarily slow down the clients because the leader doesn't have to wait for that server. — John Ousterhout > [00:00](https://www.youtube.com/watch?v=YbZ3zDzDnrw&t=0s) the system has to make progress as long as any majority of the servers are up and can communicate with each other — John Ousterhout ## Mentioned John Ousterhout, Diego Ongaro, Raft, Paxos ## Video description This lecture is part of the Raft User Study, an experiment to compare how students learn the Raft and Paxos consensus algorithms. It's a useful introduction for anyone learning Raft. Slides and voice-over by John Ousterhout. Slides, more info, etc: https://raft.github.io/ and https://ramcloud.stanford.edu/~ongaro/userstudy/ Corresponding Paxos video: http://youtu.be/JEpsBg0AO6o [Source](https://www.youtube.com/watch?v=YbZ3zDzDnrw)

[53:39] John Ousterhout: If anybody comes to you with a distributed agreement algorithm and they claim it works in a single phase, you should be very skeptical because either they're mistaken or they've discovered something really important and new that none of the rest of us know. [56:32] John Ousterhout: The key element of this algorithm is that the system has to work perfectly even if just a bare majority of the servers are up, which means it can't ever depend on having complete information or knowledge of what's going on. [27:31] John Ousterhout: Once a particular state machine has received a log entry and applied it as a command we must make sure that no other state machine ever applies a different value for that log entry. [20:02] John Ousterhout: So for example one slow server doesn't necessarily slow down the clients because the leader doesn't have to wait for that server. [0:00] John Ousterhout: the system has to make progress as long as any majority of the servers are up and can communicate with each other

[48:00] John Ousterhout: If anybody ever tells you that they think they can make a distributed decision in a single phase, you should question them pretty seriously because either they're wrong or they've discovered something that everybody else in the world doesn't know yet.

[0:00] hello I'm John osterhout and in this [0:02] video I'm going to introduce the raft [0:04] consensus [0:05] algorithm the overall goal of raft is to [0:08] replicate a log of entries identically [0:11] across a collection of servers and this [0:12] in turn is used to create what we call a [0:14] replicated State [0:16] machine suppose you had a program or an [0:18] application that you wanted to make [0:21] reliable one way to do that is to [0:23] execute that program on a collection of [0:25] machines and ensure that they all [0:27] execute in exactly the same way that's [0:29] the idea have a replicated State machine [0:31] so when I say State machine I just mean [0:33] a program or an application that takes [0:35] inputs and produces [0:36] outputs now a log can help in order to [0:39] make sure that those State machines [0:40] execute exactly the same commands here's [0:43] how it works if a client of the system [0:46] wishes to execute a command it passes [0:48] that to one of those [0:51] machines that command let's call it X [0:54] then gets recorded in the log of the [0:56] local [0:57] machine and then in addition the command [1:00] is passed to the other machines and [1:04] recorded in their logs as well once the [1:07] command has been safely replicated in [1:09] the logs then it can be passed to the [1:12] state machines for execution and when [1:14] one of the state machines has finished [1:16] executing the command the result can be [1:19] returned back to the client program [1:21] again and you can see that as long as [1:23] the logs in the machines are all [1:26] identical and the state machines on the [1:28] on the different servers execute the the [1:30] same commands from the log in the same [1:31] order we know they're all going to [1:33] produce the same [1:34] results so it's the job of the consensus [1:37] module to manage those logs ensure that [1:39] they're properly replicated and then [1:41] determine when it's safe to pass the [1:43] commands to the state machine for [1:45] execution the reason we call this a [1:48] consensus-based approach is that we [1:49] don't require all of the servers to be [1:51] running at any given time in fact the [1:53] system has to make progress as long as [1:55] any majority of the servers are up and [1:58] can communicate with each other so for [2:00] example you might have a cluster of [2:01] three servers this could tolerate one [2:03] server being down as long as two of the [2:05] three are up or in a cluster of five [2:07] servers you could tolerate two servers [2:09] being down as long as three are [2:11] up now let me talk briefly about the [2:14] failures that we expect the system to [2:15] handle we expect that servers can crash [2:18] but we expect them to do that in a fail [2:20] stop way that is they just stop [2:22] operating or they may pause operating [2:24] and then resume later but when they're [2:26] running they're behaving correctly so we [2:28] don't this protocol does not handle a [2:31] situation where a server has so-called [2:33] Byzantine Behavior where it behaves [2:36] maliciously we also assume that the [2:38] network communications can be [2:39] interrupted messages can be lost or [2:42] delayed they may arrive out of order and [2:45] it's possible that the network could be [2:47] partitioned for a while and then the [2:48] partition could go away later [2:51] on there are two general approaches that [2:53] have been used to implement consensus [2:55] algorithms the first approach is called [2:57] symmetric or leaderless in this this [3:00] approach all the servers have the same [3:02] roles they all have equal power behave [3:04] roughly the same at any given time [3:05] they're all they're all very equal a [3:07] client can contact any server to add a [3:09] command to the log and get it replicated [3:12] the second approach is called asymmetric [3:14] or leader-based the servers are not [3:16] equal at any given time at any time one [3:18] of them is the leader it's in charge [3:21] typically manages all of the operation [3:23] of the Clusters and the other servers [3:25] are subservient simply carrying out the [3:27] wishes of the leader in this sort of a [3:29] system the clients always communicate [3:31] with the leader only the leader talks [3:32] with the other servers now raft uses [3:35] that second leader-based approach and [3:38] this decomposes the problem of the [3:40] consensus algorithm into two different [3:42] things one is the normal operation when [3:44] there's a leader that's properly running [3:47] and then the second part is what do you [3:50] do when the leader crashes or you have [3:51] to elect a new [3:53] leader this approach has the advantage [3:55] that it makes the normal operation very [3:57] simple you don't have to worry about [3:58] different leaders conflicting with each [4:00] other uh or trying to do things at the [4:02] same time there's one person in charge [4:04] and they can do exactly what they want [4:06] all of the complexity in raft as you'll [4:08] see comes from leader changes that's [4:10] particularly true because if a leader [4:12] crashes it may leave the system in an [4:14] inconsistent state that the next leader [4:15] has to clean [4:17] up in general the leader-based [4:19] approaches are more efficient than the [4:21] leaderless approaches uh because you [4:23] don't have to worry about these [4:25] conflicts between servers at any given [4:27] time you only have to deal with those [4:29] during leader [4:33] changes I'm going to explain raft in six [4:36] parts first I will talk about leader [4:38] election how do we choose out of all of [4:41] the servers one of them that will be the [4:42] leader and then when that machine [4:45] crashes how do we detect that and pick a [4:47] different leader to replace it second [4:50] I'll talk about the normal operation of [4:51] the system where a leader is receiving [4:53] requests from clients and replicating [4:55] them that's actually the simplest part [4:57] of the raft system [4:59] third I'll talk about leader changes [5:02] this is probably the trickiest part and [5:04] the most crucial in terms of [5:05] guaranteeing the overall behavior of the [5:07] system I'll first talk about what it [5:09] means for rfh to be safe how we ensure [5:11] that and second how leaders resolve [5:14] login consistencies in order to restore [5:16] the system back to a consistent State [5:19] again fourth I'll talk about another [5:21] issue related to leader changes which is [5:24] how do we keep an old leader that isn't [5:25] actually dead from coming back to haunt [5:28] us fifth [5:30] I'll give a little bit more information [5:31] about how clients interact with the [5:32] system and the key issue here is how do [5:35] clients deal with server crashes and how [5:37] do we make sure that we have what are [5:39] called linearizable semantics where each [5:41] client operation is executed once and [5:43] exactly once and then finally I'll talk [5:46] about how we deal with configuration [5:47] changes that is how do we add or remove [5:49] servers to the cluster that is managing [5:51] the raft [5:54] system before going into details of [5:57] those six parts of raft let me first [5:59] provide some overall [6:00] information at any given time a server [6:03] is in one of three states the first [6:05] state I've already described that's the [6:07] leader State we need to make sure [6:08] there's only one of these at a [6:10] time the second state is follower State [6:13] we expect most of the servers to be in [6:15] follower State most of the time these [6:17] servers are completely passive they [6:19] issue no remote procedur calls at all [6:22] all they do is respond to remote [6:24] procedure calls coming from other [6:26] servers the third state is called can [6:29] State this is a state intermediate [6:32] between follower and leader and is used [6:35] temporarily during elections to pick a [6:37] new [6:38] leader in normal operation of the system [6:40] there will be exactly one leader and all [6:42] of the other servers will be followers [6:45] at the bottom of the slide I've shown a [6:46] state diagram of these states and the [6:48] transitions between them I'm not going [6:50] to go over those now but you may find [6:52] those useful to refer to as I go through [6:55] the details of the algorithm in the [6:56] later [6:58] slides time is divided into terms each [7:01] term has a number and these numbers [7:03] increment and are never [7:06] reused each term has two parts first a [7:09] term starts with an election that is [7:11] this is a a process that picks a leader [7:13] for the term and then if the election is [7:16] successful then the chosen leader will [7:19] serve out for the rest of the term as [7:20] the leader as you'll see raft guarantees [7:24] that only one server can be elected [7:26] leader in a term however there can be [7:28] some terms [7:30] where no leader is chosen this happens [7:31] if the votes are split in a way that no [7:33] leader can get a majority of the votes [7:36] when this happens then the system [7:38] immediately moves to a new term to try [7:41] again to pick a [7:42] leader each server in the raft system [7:45] maintains a value called the current [7:47] term which is its best guess about what [7:50] the current term in the system is and by [7:53] the way that information has to be [7:54] stored reliably on that server's disc so [7:57] that it can be recovered when the server [7:59] crashes and [8:01] restarts the role that terms serve is a [8:04] really important one it allows raft to [8:06] identify information that's out of date [8:09] for example if a server that currently [8:12] believes that the term number is two [8:14] communicates with a server that [8:15] currently believes the term number is [8:17] three then we know that the information [8:19] coming from that first server is out of [8:21] date we only want to use this the [8:23] information from the latest term so as [8:25] we go through the talk you'll see [8:27] several situations where terms are used [8:29] to detect and eliminate information [8:32] that's no longer up to [8:35] date this slide contains a complete [8:37] summary of the entire raft protocol I'm [8:40] not going to go over it in detail now [8:42] but I just want to point out a few [8:43] General features you can come back to [8:45] later on so first the slide describes [8:47] what each of the three roles does [8:49] followers candidates and leaders second [8:51] it describes what information has to be [8:53] stored persistently on the diss of the [8:55] servers and then third it describes how [8:58] the servers communicate [8:59] all Communication in raft is done via [9:01] remote procedure calls and there are [9:04] only two of them there's one RPC called [9:07] request vote that's used during [9:09] elections to pick a leader and one RPC [9:12] that's used by the leader during normal [9:14] operations to replicate log entries [9:17] these are the only two rpcs in the [9:19] system and by the way I'll just mention [9:20] briefly each of these is item potent [9:22] which has some nice properties in terms [9:24] of handling replicated and lost messages [9:26] and so on again I'm not going to go over [9:28] the details here but you may want to [9:30] refer back to these as I go through [9:32] details later on in the [9:35] talk okay now let's go through the six [9:38] components of the raft protocol the [9:40] first component of the protocol is [9:42] elections raft has to make sure that at [9:44] any given time there's exactly one [9:47] machine acting as a leader in the [9:49] cluster now when a server starts up it [9:52] begins as a follower and in this state [9:55] it doesn't attempt to communicate with [9:57] anyone else followers are completely [9:58] passive they simply respond to incoming [10:01] remote procedure calls from other [10:03] machines however in order for a follower [10:06] to stay a follower it has to believe [10:08] that there is an active leader in the [10:10] cluster and the only way it can know [10:12] that is if it receives Communications [10:14] from other machines that are either [10:15] leaders or [10:16] candidates so if the leader wants to [10:18] maintain its Authority it must [10:20] communicate with all of the other [10:21] machines in the cluster on a regular [10:23] basis and if it has no other reason for [10:25] communicating with them it must send [10:27] heartbeat messages in raft these are [10:30] simply append entries remote procedure [10:32] calls that contain no data at all so [10:34] those service heartbeat [10:36] messages if a period of time goes by and [10:39] a follower does not receive any remote [10:41] procedure calls then it assumes that [10:44] there's no viable leader in the cluster [10:46] and so it starts an election to see if [10:48] perhaps it should become [10:50] leader this period of time that a [10:52] follower wait is called the election [10:55] timeout in the typical clusters that'll [10:58] be in the range of 100 to 500 [11:01] milliseconds so when the cluster first [11:03] starts up all of the servers will begin [11:05] as followers there'll be no leader and [11:07] so they'll all wait the election timeout [11:09] period and then they'll all start [11:12] elections to elect a [11:15] leader now let's talk about how an [11:17] election works when a server begins an [11:20] election the first thing it does is to [11:22] increment its current term value this [11:24] produces a new value for the term larger [11:27] than anything it has seen before and [11:29] remember the first thing that happens in [11:30] every new term is we hold an [11:33] election the server then converts itself [11:35] from follower state to candidate state [11:38] in this state its goal is to get itself [11:41] elected as leader and in order to do [11:43] that it needs to receive votes from a [11:45] majority of the servers in the cluster [11:48] the first thing the candidate does is [11:50] that it votes for [11:51] itself then it sends out remote [11:54] procedure calls to all of the other [11:56] servers asking them for their votes [11:59] typically it will send these request [12:01] vote rpcs in parallel to all of the [12:04] servers if it doesn't get a response [12:07] from any particular server it will keep [12:08] retrying with that server over and over [12:10] again until it eventually gets a [12:12] response sooner or later one of three [12:14] things will happen first the thing we [12:17] happen most of the hope to happen most [12:19] of the [12:20] time is that the candidate will get [12:22] votes from a majority of the servers in [12:24] the cluster when this happens then it [12:27] converts itself to leader state [12:29] and immediately sends out heartbeat [12:31] messages to all of the other servers [12:33] which effectively marks its territory or [12:36] establishes itself as [12:37] leader the second thing that could [12:39] happen during an election is that there [12:42] could be some other candidate also [12:44] operating at the same time and perhaps [12:45] that candidate receives enough votes to [12:47] become leader at which point it will [12:49] send out rpcs and so if a candidate [12:53] receives a remote procedure call from a [12:55] valid leader then [12:58] immediately gives up its attempt to [13:00] become leader we call that stepping down [13:02] which causes it to return to follower [13:04] state becomes passive and simply [13:06] responds to the request from the valid [13:09] leader then the third state or third [13:12] outcome that can [13:14] happen is that it's possible no one will [13:16] win the election if several servers [13:19] convert to candidate about the same time [13:21] they could split the votes in a way that [13:23] nobody can get a majority of the [13:25] Clusters [13:26] votes the way that a server detects this [13:29] possibility is that a period of time [13:31] goes by and neither of the other two [13:34] options has occurred yet in fact it uses [13:36] the same election timeout period if that [13:39] elapses and this candidate has not [13:41] become leader and has not heard from a [13:43] valid leader then it assumes that [13:46] there's a split vote in the election and [13:48] so at this point it simply goes back to [13:50] the beginning and starts a new election [13:54] by incrementing the term and starting [13:56] the whole process over again it's [13:59] important for an election to have two [14:00] properties safety and liveness the [14:03] safety property says that there must be [14:05] at most one candidate that wins the [14:08] election in a given term the way raft [14:10] guarantees this is that each server only [14:13] gives out its vote once to a single [14:15] candidate once it's given its vote it [14:17] will refuse requests from any other [14:19] candidates for votes and and by the way [14:21] the server doesn't really care which [14:23] server gives its vote to it'll give it [14:24] to the first candidate that comes [14:26] along in order to make this work the [14:29] server needs to make sure that it saves [14:31] information about its vote on some [14:33] durable medium like dis so it can [14:35] recover that after a crash otherwise [14:37] we'd have a problem where a server might [14:39] give out its vote and then crash and [14:41] then restart and give its vote again to [14:43] a different server for the same [14:45] term given that a server is only giving [14:47] out one vote and given that each [14:49] candidate has to get a majority of the [14:51] votes then it's easy to see that you [14:53] can't have two candidates that win an [14:55] election so for example if three servers [14:58] vote for a in a particular term then the [15:01] most that any other server could get say [15:04] B is two and obviously B can't get a [15:06] majority now as we'll see later on it is [15:08] possible of course to have different [15:10] candidates win in different terms but [15:12] within a given term at most one [15:15] candidate can win an [15:16] election now the second property is the [15:19] liveness property we need to make sure [15:21] that somebody wins so the system doesn't [15:23] stay in a state with no leader forever [15:26] and the problem is that we could [15:29] principle have repeated split votes [15:32] where a bunch of candidates all start [15:33] elections for the same term at the same [15:35] time they split the votes they all time [15:38] out again start a new election in a new [15:40] term split the votes again and so on and [15:42] in principle this could go on [15:45] indefinitely the way that raft presents [15:47] this is to spread out the election [15:50] timeouts each server computes its next [15:53] timeout randomly in an interval an [15:56] interval between a particular value T [15:59] and twice that value where T is [16:01] typically what we refer to as that's the [16:04] election timeout so the smaller the [16:06] fastest that a machine could possibly [16:08] time [16:10] out by spreading out these [16:12] timeouts that makes it unlikely that two [16:15] servers will wake up at the same time [16:17] whoever wakes up first will have enough [16:19] time to request votes from everybody [16:20] else and win the election before anybody [16:22] else wakes up to compete with it and [16:24] this works particularly [16:26] well if that time over for which we [16:29] spread the the timeouts is much larger [16:32] than the broadcast time where what I [16:34] mean by broadcast time is the amount of [16:36] time that it takes one server to talk to [16:38] all the other servers that get their [16:39] votes so as long as the timeouts are [16:43] spread out over a much larger interval [16:44] again it's pretty easy to see that [16:46] whichever server wakes up first will be [16:49] able to talk to everybody and get their [16:50] votes before anybody else wakes [16:54] up now let's move on to the second part [16:57] of the raft protocol which which is the [16:59] mechanism that leaders use during normal [17:01] operation to replicate log entries first [17:04] let's talk a little bit about the log [17:06] each server stores its own individual [17:08] copy of a log so leader has a copy and [17:10] each follower has its own private copy [17:13] of the log the log is divided up into [17:15] entries and entries are identified by an [17:18] index which gives their position in the [17:22] log inside an entry there are two things [17:26] first each entry contains a command for [17:29] the state machine the format of this is [17:31] really up to the clients and the state [17:33] machines to agree on the consensus [17:35] module doesn't care but you can imagine [17:36] it might be something like the name of a [17:38] procedure and some arguments to pass to [17:39] that [17:40] procedure then in addition each entry in [17:43] the log contains a term number this is [17:46] the term number when the log when that [17:48] entry was first created by the leader of [17:51] that term and these term numbers [17:53] increase monotonically as you go up the [17:55] log [18:00] each server has to guarantee that its [18:02] log Will Survive crashes so the log is [18:04] typically stored on disk or some other [18:06] form of stable storage and whenever a [18:09] server makes a modification to its log [18:10] it has to update the safe copy on dis [18:13] before it returns any sort of response [18:15] to anybody else in the [18:18] system if a particular log entry happens [18:20] to be stored on a majority of the [18:22] servers in the cluster such as say entry [18:26] 7 here then we say that that entry is [18:29] committed this is a very important [18:31] property of the raft system if an entry [18:34] is committed then it's safe for that [18:37] entry to be passed to State machines for [18:39] execution raft will guarantee that the [18:41] entry is durable and sooner or later [18:43] that entry will be executed by every [18:45] state machine on every server in the [18:49] cluster so in this picture entry seven [18:51] is committed in fact all entries [18:54] preceding entry 7even are committed but [18:56] entry 8 is not yet committed since it's [18:57] only stored on two of the five servers [19:00] now I just want to warn you I'm going to [19:02] modify this definition of commitment [19:04] slightly when we get to the part of the [19:06] talk on managing consistency of logs [19:08] across server [19:11] changes normal operation is pretty [19:14] simple a client sends a command to the [19:17] leader that it would like to have [19:18] executed by all of the state machines [19:20] the leader first adds that command to [19:23] its own log and then it issues append [19:26] entries remote procedure calls to the [19:28] follower is in the cluster typically it [19:31] will execute these rpcs in parallel [19:33] sending the same message to all of them [19:34] at the same time and then it waits for [19:36] the responses to come back once the [19:39] leader has received enough responses to [19:42] consider that entry committed that is [19:44] it's gotten responses from at least half [19:47] of the other servers in the cluster so [19:49] with itself that makes a [19:51] majority then it's okay to execute the [19:53] command so the leader passes the command [19:54] off to its state machine when that [19:56] command finishes then it Returns the [19:58] result back to with the [19:59] client furthermore once the leader knows [20:02] that a particular entry is committed it [20:05] notifies the other servers about that in [20:09] subsequent append entries rpcs So [20:12] eventually each of the followers will [20:14] also find out that that entry has been [20:15] committed and then the followers when [20:18] they find out they will execute that [20:20] command on their state machines [20:22] also now if a follower has crashed or is [20:25] slow to respond to an append entry's [20:27] remote procedure call the leader will [20:30] keep retrying that call over and over [20:31] and over again so if a follower crashes [20:33] and comes back up again the leader will [20:35] will retry it but the leader doesn't [20:38] have to wait for every single follower [20:40] to respond it only needs enough to [20:41] respond to guarantee that the entry is [20:44] stored on a majority of the servers in [20:46] the cluster so this results in very good [20:48] performance in the common case in the [20:50] normal case all that's needed in order [20:52] to finish a client command is to get a [20:54] response back from a majority of the [20:56] servers in fact the fastest machines in [20:58] the in the cluster at which point the [21:00] leader can immediately execute the [21:02] command and return the result to the [21:03] client so for example one slow Server [21:06] doesn't necessarily slow down the [21:08] clients because the leader doesn't have [21:10] to wait for that [21:12] server raft tries to maintain a high [21:14] level of consistency between the various [21:16] logs in a cluster ideally they'd all be [21:18] identical at all times and we can't we [21:21] can't of course do that given there can [21:22] be crashes but as much as possible raap [21:25] tries to keep the logs identical and [21:27] this slide lists some properties that [21:29] are always true at all times the first [21:32] property is that the combination of an [21:35] index and a term uniquely identifies a [21:37] log entry that is if two log entries are [21:41] in the same index log index position and [21:44] they have the same term then it's [21:47] guaranteed that they will also have the [21:49] same command and furthermore it's also [21:53] guaranteed that if two entries have this [21:55] property then all preceding entries in [21:59] those logs will also match each other so [22:02] the combination of a term and an index [22:06] uniquely identifies an entire log from [22:09] its beginning up to that [22:11] point furthermore it turns out that if a [22:13] particular entry is committed then all [22:16] preceding entries are also committed and [22:19] that kind of follows from the previous [22:20] Rule and that you can see if a majority [22:22] of the servers store this one entry here [22:24] at index 5 then because of the the the [22:28] rule above they must also store all the [22:30] same earlier entries and so we know all [22:32] of those entries will also exist on a [22:34] majority of the [22:37] servers this property is enforced by a [22:40] check that's made during the append [22:42] entry's remote procedure call when a [22:45] leader issues an append entries RPC to a [22:49] follower it includes two values in [22:52] addition to the new log entries it [22:54] includes the [22:55] index and the term of the entry just [22:59] before the new [23:01] ones and the follower will only accept [23:04] the RPC if it contains that exact [23:07] matching entry in its log if its log [23:09] doesn't have that entry then it will [23:11] reject the remote procedure [23:14] call so let's go through an [23:16] example suppose a leader has just [23:19] received a new command jump from a [23:21] client and it sends an append entries [23:24] remote procedure call to that follower [23:32] well the leader will include the index [23:34] and term of the preceding entry so it'll [23:36] include index 4 and term two in the RPC [23:40] the follower checks to see that it has a [23:42] matching entry there and since it does [23:44] then it will accept that new entry into [23:47] its log now consider the example on the [23:50] bottom though suppose the follower log [23:52] actually had a [23:53] different entry preceding the new one in [23:56] this case the entry in index 4 four has [23:59] a different term and so because of this [24:01] the append entry's remote procedure call [24:03] will be rejected it will not accept that [24:05] new [24:06] entry this consistency check is really [24:09] important and you can think of it kind [24:10] of like an induction step in the proof [24:13] of the properties on the preceding slide [24:16] it guarantees that a new entry is only [24:19] accepted if the logs match in their [24:20] previous entry but of course the same [24:23] check was applied when those entries [24:24] were created and so that guarantees the [24:26] logs also match in preceding entries and [24:28] so on so this means that if a follower [24:32] accepts a new entry from the leader its [24:35] log exactly matches the leader's log up [24:38] through that entry [24:40] guaranteed that finishes the discussion [24:43] of normal operation now let's talk about [24:45] leader [24:46] changes when a new leader comes to power [24:49] the logs may not be in a very clean [24:50] State because the previous leader could [24:52] have crashed before it finished [24:54] completely replicating some of the log [24:56] entries now the way raft handles this is [24:59] that it doesn't take any special steps [25:01] when a new leader comes online it [25:03] doesn't try and do a cleanup phase it [25:04] just starts normal operation and the [25:06] cleanup has to happen during the normal [25:08] operation now the reason for this is [25:11] that when a new leader comes up some of [25:13] the other machines may be down and so [25:15] there's no way it can clean up their [25:17] logs right away it has to be able to [25:18] resume operation even if some machines [25:20] are down and it could be a long time [25:22] before those machines come back up again [25:24] so we have to design the system so that [25:26] the normal operation eventually [25:28] converges all of the logs the raft [25:31] approach to this is to assume that the [25:33] leader's log is always correct it has [25:35] everything important and so all the [25:37] leader has to do is over time make all [25:40] of the followers logs match its log but [25:44] in the meantime that leader could crash [25:46] before it finishes the job and the next [25:47] leader and the next leader and so [25:49] extraneous log entries could pile up [25:52] over a long period of time to create a [25:55] fairly chaotic looking situation like [25:57] the example in the bottom of the slide [25:59] here uh first I want to mention I'm [26:01] going to change my notation a little bit [26:03] up until now I've shown the commands in [26:05] log entries but I'm not going to do that [26:07] anymore since we know that the [26:08] combination of a log index and the terms [26:11] stored in an entry is a unique [26:12] identifier for that entry so from now on [26:14] I'm just going to show term numbers in [26:16] the log entries without [26:19] commands this particular scenario at the [26:21] bottom could have happened if servers [26:23] four and five were the leaders for terms [26:25] 2 three and four but somehow never [26:27] replic ated any entries outside [26:29] themselves and then they crashed and the [26:31] system partitioned for a while and the [26:34] other servers 1 2 and three took turns [26:36] being leaders for terms five six and [26:38] seven but were not able to communicate [26:40] with servers four and five to clean them [26:41] up so now we're at a situation where the [26:43] logs are really quite a mess the only [26:46] thing that really matters [26:48] here is these entries that I'm drawing [26:51] here entries one through three these are [26:54] committed entries and so we have to make [26:56] sure we preserve them but the other ENT [26:58] entries none of them have been committed [26:59] and so it doesn't really matter whether [27:00] we keep them or throw them away we [27:03] haven't passed any of these to a state [27:04] machine no client machine has seen the [27:06] results of executing any of these [27:07] commands so these are all [27:10] Expendable if for example server 2 is [27:13] the leader for term 7 and it's able to [27:15] communicate with everyone then [27:16] eventually it will make all of the logs [27:19] in the cluster look like its log and any [27:21] conflicting entries will get deleted now [27:24] I'll come back later on to talk about [27:26] how a leader makes the followers logs [27:28] match its logs but first I want to talk [27:31] about correctness and safety you know [27:32] how do we know that the system is [27:34] behaving in a correct way and that we're [27:36] not losing some information that's [27:38] important because you can see clearly [27:39] here we're going to have to throw away [27:41] some log entries in order to bring [27:43] everything back into consistency so how [27:45] do we do that in a safe [27:49] fashion there's a fundamental overall [27:52] safety requirement that any system for [27:54] implementing replicated logs must obey [27:57] and it's written in red here that once a [27:59] particular State machine has received a [28:02] log entry and applied it as a command we [28:05] must make sure that no other state [28:07] machine ever applies a different value [28:09] for that log entry they must all apply [28:12] the same values in the same order for [28:14] this for the log [28:16] entries now in order to achieve this [28:18] overall safety requirement raft [28:21] implements a somewhat narrower what I [28:24] call safety property and this what's [28:26] written on the slide here that once a [28:28] leader has decided that a particular [28:30] entry is [28:32] committed then raft guarantees that that [28:35] entry will be present in the logs of all [28:39] Future Leaders in the system so whenever [28:41] a leader comes to power in the future [28:43] and for its entire lifetime it will [28:44] always have all of the committed log [28:47] entries present if we can make raft uh [28:51] conform to this property then that will [28:53] guarantee the safety requirement at the [28:55] top of the slide and this the rough [28:57] argument is that first a leader never [28:59] overwrites an entry in its log it only [29:01] appends and so we know that those log [29:04] entries will never change then if [29:05] they're always present on the leader [29:07] second in order to be committed an entry [29:10] has to be in the leader's log so no [29:12] other value can be committed and third [29:14] we know that entries have to be [29:15] committed before they're applied to the [29:16] state machine so if you put all of those [29:18] together we've guaranteed the property [29:21] at the top of the [29:23] slide now the raft algorithm as I've [29:26] described it so far does not yet yet [29:28] guarantee this property and I'm going to [29:30] go through the problems and show you how [29:31] we solve them but first I just want to [29:33] go back to what we're trying to do again [29:34] that if an entry is committed that [29:36] implies it will be present in Future [29:38] Leaders logs so in order to do this [29:40] we're going to change the raft [29:41] algorithms in two ways [29:44] first I'm going to modify the election [29:47] process to exclude a machine from [29:49] becoming leader if it doesn't have the [29:51] right stuff in its [29:53] logs and then second that's not going to [29:55] be enough by itself and then second [29:57] we're going to change the definition of [29:58] committed a little bit so at sometimes [30:00] we have to delay committing an entry [30:03] until we know that it'll be safe that is [30:06] that we can guarantee that it will be [30:07] present in Future Leaders logs I'll talk [30:09] about the election stuff [30:12] first so how do we make sure we pick a [30:14] leader that holds all of the committed [30:16] log entries well first of all this is [30:19] kind of tricky because we can't actually [30:20] tell which entries are committed if we [30:23] consider this cluster with three servers [30:25] in it and suppose that we're having to [30:27] pick a new leader but one of the servers [30:30] is not [30:31] available then just looking at the [30:33] servers that are available during the [30:35] transition we can't really tell whether [30:36] entry 5 is committed or not it depends [30:39] whether it's stored on this unavailable [30:40] server in this case it is but in other [30:42] cases it might not [30:44] be know for sure which entries are [30:47] committed so instead what we do is to [30:49] try and pick a candidate to win an [30:51] election such that it has the log that [30:54] is most likely to have all the entries [30:57] that have been committed [30:58] and I'll first describe this intuitively [31:00] and then come back and make it more [31:02] precise to prove that in fact we can [31:04] guarantee that we pick a candidate that [31:06] has all the committed [31:07] entries the way this works is by [31:10] comparing logs so when a candidate [31:12] requests a vote from another server it [31:15] includes information about its log and [31:17] all it needs to include is the index of [31:20] the last log entry and the term from [31:21] that entry and remember from my [31:23] discussion previously this uniquely [31:25] describes the entire log [31:28] then the voting server that receives [31:30] this request for a vote it Compares its [31:33] own log to that of the candidate and if [31:35] the voter's log is more complete think [31:39] of this in an intuitive sense it will [31:40] deny its vote now to make this specific [31:43] we Define this to mean that if the last [31:46] term in the voting server log is greater [31:48] than the last term in the candidates log [31:50] then the voter's log is more complete [31:52] deny the vote or if the terms [31:55] match and the voting log is longer than [32:00] the candidate's log then again the [32:02] voter's log is more complete and so we [32:04] deny the vote so the result of this is [32:06] that whoever wins the election is [32:09] guaranteed to have the most complete log [32:12] among the servers that voted for it [32:14] among some majority of the cluster and [32:16] again by most complete I mean this [32:18] particular definition in terms of the [32:20] the uh index and term of the last entry [32:23] in the [32:26] log let's see how this work Works in [32:28] practice so the interesting time to [32:31] consider is the moment just after a [32:35] leader has decided the log entry is [32:38] committed there are two interesting [32:40] cases to consider the first case is when [32:43] the entry being committed is in the [32:45] current term and the second case if it's [32:46] is if it's in some prior term let me [32:48] deal with those separately first [32:50] consider the case where the leader has [32:52] just decided an entry in its most recent [32:54] current term is committed so we have an [32:56] example here where we're in term two and [32:59] the leader for that term has just [33:02] replicated entry four over onto server [33:04] three the append entries call just [33:06] succeeded and this leader now sees ah [33:08] this entry is on a majority of servers I [33:11] declare that entry committed and it can [33:12] pass it to my safe to my state machine [33:15] now you can see that at this point in [33:17] time this entry is safe that is the [33:20] leader for the next term must contain [33:22] this entry and we can see that by just [33:24] just by considering the rules S5 can't [33:27] become leader for the next term because [33:28] its term is older than the other servers [33:31] there's no way you could get a majority [33:32] of servers with terms that old S4 can't [33:36] become leader because it won't be able [33:38] to get votes from anybody else because [33:40] although the the last terms are the same [33:42] S4's log is too short so we know that [33:45] only one of these first three servers [33:47] can be elected leader in fact if S1 is [33:50] in the mix S1 is guaranteed to win the [33:52] election but S2 or S3 could win by [33:55] getting votes from each other and then [33:57] one of ser four or five but in any case [34:00] you can see that the leader for the next [34:01] term must contain that log [34:05] entry now let's consider the second case [34:08] where a leader is trying to commit an [34:09] entry that was initially started in an [34:11] earlier term in this situation the [34:15] leader for term two replicated an entry [34:18] on only two machines before its term [34:20] ended and then the leader for term three [34:22] for some reason was not aware of those [34:26] entries created a bunch of entries of [34:28] its own and then crashed and now we're [34:31] back another machine has been elected [34:32] leader in term four and finally it's [34:35] trying to make all of the other servers [34:37] logs match its own and so it replicates [34:41] this entry from that Old entry from term [34:44] two over onto server 3 and now at this [34:48] point that entry is known by the leader [34:51] to be stored on a majority of the [34:52] servers but that entry is not safely [34:56] committed and the reason you can see [34:58] this is that if the leader were to crash [35:01] now and a new leader were to be elected [35:03] it's possible that server 5 could be [35:06] elected using any majority that doesn't [35:09] include server one it could get votes [35:10] from server 4 server 3 or server two [35:13] since its last term is greater than any [35:16] of those machines and if it's elected [35:18] then it's going to try and propagate its [35:20] log meaning it'll write those entries [35:22] from term three across all of the other [35:24] servers and all of these entries will go [35:25] away so we cannot consider entry 3 to be [35:29] committed at this point it's simply not [35:34] safe in this situation the new rules for [35:37] elections are not enough by themselves [35:39] to guarantee safety we also have to [35:41] modify the rules for [35:43] commitment remember up until now a [35:46] leader could decide that an entry was [35:47] committed as soon as it saw that the [35:49] entry was stored on a majority of the [35:51] servers but in order to guarantee safety [35:54] we have to add another rule which is [35:55] that in addition the leader must be able [35:58] to see that at least one of the entries [36:00] from its term from the current term is [36:03] also stored on a majority of servers so [36:06] going back to our example if the leader [36:10] finishes replicating entry three to a [36:11] majority it can't yet commit that entry [36:13] and pass it to the state machines [36:15] instead it has to also wait until the [36:18] first entry from its term gets committed [36:22] that is stored on a majority of the [36:23] machines and now at this point both of [36:25] those entries can be passed to state [36:27] machines they're safe and the reason [36:29] that for that is that we can see that [36:31] now there's no way server 5 can get [36:34] elected leader for the next term and the [36:36] reason is that there's too many other [36:38] servers out there with more recent terms [36:41] in their logs the only vote server five [36:43] would be able to get is server four so [36:46] at this point both entries three and [36:48] four are [36:50] safe so with the combination of the new [36:53] election rules where we compare logs and [36:56] this new commitment rule we can [36:58] guarantee that the raft safety property [37:00] always holds that is once the leader [37:02] decide an entry is committed it will be [37:04] present in the log of every leader in [37:06] the future well okay actually I've only [37:08] shown you that the log entry will be [37:10] present in the leader for the very next [37:11] term but it's also fairly [37:13] straightforward to prove that every [37:15] future leader will also have the log [37:17] entry I'm not going to go through that [37:18] proof and then once we know the raft [37:21] safety property holds and as I mentioned [37:22] on the previous slide we know that the [37:24] overall replicated log will also be safe [37:29] now that we've guaranteed safety and we [37:30] know that the leader log is correct how [37:33] do we make all of the followers logs [37:35] match the leader's log well first let me [37:38] show you the different ways in which [37:39] logs can be inconsistent this slide [37:41] illustrates what can happen it's [37:44] possible that followers can be missing [37:46] entries that the leader has such as in [37:48] this case for followers A and B here or [37:51] also for follower e and followers [37:58] and followers can also have extraneous [37:59] entries not present on the leader such [38:02] as these entries for term seven over [38:04] here the entries for terms two and three [38:06] at the bottom an extra entry for terms [38:09] six and so [38:11] on so what we have to do is get rid of [38:14] all the extraneous entries from the [38:16] follower logs and then fill in all of [38:19] the missing entries from the leader [38:24] log to restore log consistency the [38:27] leader maintains a state variable for [38:29] each of the followers in the cluster [38:31] which I will call next index and this is [38:34] the index in the log of the next log [38:36] entry that the server intends to send to [38:38] that follower initially when the server [38:41] becomes leader it sets these next index [38:43] values to the entry just after the last [38:46] one in its log so in this example where [38:48] we have a new leader for term seven and [38:50] the last entry in the log is index 10 it [38:53] will set next index to 11 for all of the [38:55] client uh all of the followers in the [38:57] the [38:59] cluster the leader will find out about [39:01] consistency issues through the append [39:03] entries RPC remember there's this [39:05] consistency check performed by followers [39:07] whenever they receive an append entries [39:09] request and that will find any problems [39:12] so the next time this leader attempts to [39:15] communicate with either of those [39:16] followers it's going to [39:19] include the index and the term 10 and [39:23] six for the entry just before next index [39:26] as part of that request by the way the [39:27] next request is probably going to be a [39:29] heartbeat that it sends out as soon as [39:31] it becomes elected leader but heartbeats [39:33] behave just like all other append [39:35] entries except that they have no new [39:37] values but they still include the [39:38] consistency check so when this message [39:41] arrives at follower a it's going to [39:44] compare this term and index with its own [39:46] log and it has no matching entry there [39:48] so it's going to reject the append [39:50] entries [39:52] request when the server sees this [39:54] rejection sorry when the leader sees [39:56] this rejection its response is very [39:58] simple it just reduces next index by one [40:01] so it we'll drop index back to 10 and [40:04] then we'll try again this time you can [40:06] see the server will include information [40:08] about index 9 and that check is going to [40:10] fail and this will keep failing over and [40:13] over and over and over again until [40:17] eventually next index becomes [40:20] five for follower a at this point now [40:24] the [40:25] leader will include information about [40:29] log entry 4 in the request and that will [40:31] now match and so once that matches then [40:34] the follower can add the entry for four [40:36] and the leader will eventually fill in [40:38] its log a similar thing will happen for [40:40] follower B again when next index is 11 [40:44] the consistency check will fail and in [40:46] this case we'll back up again and again [40:48] and again and again and again and again [40:51] all the way back until eventually next [40:53] index becomes [40:55] four and the consistency information is [40:57] for the preceding entry log index three [40:59] with term one and that will match and [41:01] then eventually this log will also fill [41:07] in one other note about this process of [41:10] making the logs consistent whenever a [41:13] follower receives an entry for its log [41:15] that is replacing another entry that's [41:18] inconsistent then it truncates its log [41:20] removing all of the entries after that [41:22] so for example in this case if the [41:25] leader sends the ENT for Slot 4 to this [41:29] follower and it already had a [41:30] conflicting entry to in there then not [41:33] only will it overwrite the entry for two [41:35] for that uh the old contents of that [41:38] slot but it'll remove all of the [41:39] remaining ones after that we know any [41:41] entry after an extraneous entry is also [41:45] extraneous let me just summarize quickly [41:48] what I've covered in this section of the [41:50] presentation on leader changes there are [41:52] two overall problems we have to deal [41:54] with one is ensuring the safety of the [41:56] system which has to do with how we [41:57] choose leaders and when we decide log [41:59] entries are committed and then second [42:01] once a new leader comes to power all it [42:03] has to do is make the followers logs [42:06] match its own and the append entries [42:08] consistency check provides all the [42:10] information we need in order to do [42:14] that the fourth step of the raft [42:16] protocol is another issue related to [42:19] leader changeovers which is that an old [42:22] leader may not actually be dead for [42:25] example suppose that there's a network [42:28] partition that separates the leader from [42:31] the rest of the cluster well the rest of [42:33] the cluster could then elect a new [42:35] leader they'll wait the election timeout [42:37] and run an election elect a new leader [42:39] now the problem is what if that old [42:41] leader becomes reconnected again it does [42:44] not know about the election does not [42:45] know about the new leader and so it will [42:48] attempt to behave as a leader such as [42:50] trying to replicate log entries and in [42:52] fact there could be clients that are [42:54] talking to that old leader sending it [42:55] requests and the leader will receive re [42:57] them and record them in its own log and [42:59] then attempt to replicate them on other [43:00] machines in the cluster well we have to [43:02] stop that from happening and the way we [43:04] do that is with the use of [43:07] terms what happens is that every [43:10] RPC includes the sender's term and when [43:15] the RPC is received the receiver [43:18] Compares that to its own term and if [43:21] they don't match then whichever one is [43:23] out of date will update so for example [43:25] if the sender's term is older than the [43:26] reer receivers that means the sender is [43:28] stale when this happens the receiver [43:31] immediately rejects the remote procedure [43:33] call does not execute it and sends a [43:36] response back to the sender that [43:38] includes the receiver's term the sender [43:42] sees that realizes that its term is out [43:44] of date and so then it steps down that [43:46] is it becomes a follower again and at [43:48] the same time it updates its term so now [43:50] it's up to date it's consistent with the [43:51] other server conversely if the [43:54] receiver's term is older [43:57] then the receiver also steps down if it [43:59] wasn't already a follower it updates its [44:02] term to match but then the receiver will [44:04] go ahead and still handle the RPC it [44:06] doesn't reject the RPC there's no need [44:08] for that it just becomes a follower and [44:10] does what the RPC [44:12] says now the interesting thing here is [44:14] that the election process causes term [44:17] updates that is when a candidate [44:20] requests [44:21] votes and it has to talk to a majority [44:24] of the servers to do that it will [44:26] include the term for its candidacy in [44:29] those rpcs and so all of those [44:31] recipients will update their terms to [44:33] match that of the candidate and so as a [44:35] result by the time a new leader is [44:37] elected a majority of the servers in the [44:39] cluster reflect that new term that means [44:42] that once an election is complete [44:44] there's no way that that deposed server [44:46] can actually receive a new log entry and [44:48] write it to a majority of the cluster [44:50] because to do that it would have to [44:52] contact at least one of those servers [44:55] that has the new term and when it does [44:57] that the term mismatch will be [45:00] discovered and that old leader will then [45:01] step down so this is the key idea [45:04] there's a few other Corner cases here [45:05] that I'm not going to talk about but the [45:08] term notion allows us to handle all of [45:10] those that if there's something out ofd [45:13] the terms detect [45:18] that now let's move on to the fifth part [45:21] of the raft protocol this is how do [45:22] clients interact with the system this is [45:25] mostly pretty simple [45:27] a client just sends their commands to [45:29] the leader machine and they get [45:31] responses back now if the client doesn't [45:33] know who is the leader that's fine it [45:35] can talk to any server in the cluster [45:37] and if that server is not the leader [45:39] then it will tell the client who the [45:41] leader is and the client can retry with [45:42] the leader so that's easy as I have [45:45] mentioned before the leader does not [45:47] respond to the client until the command [45:50] has been logged and most importantly [45:53] committed so we know it's on a majority [45:55] of the server's discs [45:57] and then executed by the leader State [46:00] machine so at that point the leader [46:02] Returns the result back to the [46:04] client the only tricky thing in here is [46:06] what happens if the leader crashes or if [46:09] the request otherwise times out and the [46:12] answer is that when that happens the [46:13] client simply reissues the command in [46:15] fact you can just pick a random server [46:16] when that happens assume the leader is [46:18] crashed try some other server and [46:21] eventually it will find its way to the [46:23] cluster's new leader and then it'll [46:25] retry that request and the new leader [46:27] will execute it and the command will be [46:29] carried out so this guarantees that a [46:33] command will eventually be [46:35] executed however this leaves open the [46:38] risk that a command might get executed [46:40] twice the problem is that the leader [46:43] might crash after it's executed a [46:45] command but before it has responded to [46:47] the client so the client won't know that [46:50] the command is actually been logged and [46:52] executed if this happens the client will [46:54] then turn around and reassure that [46:56] command to the next leader that it can [46:57] find and we run the risk that the [46:59] command could get executed twice that's [47:01] not acceptable we want each command [47:03] execute once and exactly once the way [47:05] raft achieves that is that the client [47:08] generates a unique identifier for every [47:10] command and it embeds that in the [47:13] command that it sends to the leader when [47:16] the leader logs that command it includes [47:19] this ID in the log entry but before the [47:22] leader accepts a command it first checks [47:25] to see if it already has that identifier [47:29] in some other entry in its log and if so [47:31] then it knows it's receiving a redundant [47:33] command so if it finds the ID in the log [47:36] then it ignores that new command and [47:38] instead it waits for the old command to [47:40] be executed by the state machine if it [47:42] hasn't already been executed and it [47:44] returns that old [47:45] response so as a result we get exactly [47:48] one semantics each command is executed [47:50] exactly once and this is a key element [47:53] of what's called linearizability a [47:54] particular form of strong semantics that [47:56] that we like for systems to [47:59] have this brings us to the last of the [48:02] six parts of the raft [48:04] protocol we need to have some mechanism [48:06] for changing the system configuration [48:08] over time and when I say system [48:10] configuration what I mean is information [48:12] about the servers that are part of the [48:14] cluster so that consists of the ID of [48:16] each server and a network address that [48:18] can be used to communicate with with it [48:21] this information is really crucial [48:23] because it's what determines what we [48:25] need to do in order to get a majority [48:26] vote for things like electing a leader [48:29] or committing a log entry now the reason [48:32] we have to support changes in this is [48:33] because for example machines will fail [48:35] and so they'll need to be replaced with [48:37] new machines or the people managing a [48:39] cluster might want to change the degree [48:41] of replication in the cluster and we'd [48:43] like to be able to do this in an [48:44] automatic and safe fashion without [48:46] bringing the system down in order to [48:48] change the [48:51] configuration now it's important to [48:52] realize that we can't just switch [48:55] directly from an old configuration to a [48:57] configuration and to see that let's look [48:59] at the example the bottom of the slide [49:01] suppose the system is running in a [49:03] configuration where there are three [49:04] servers and then we want to add two more [49:07] servers so that afterwards there will be [49:10] five servers in the cluster if we just [49:12] asked each server to change [49:14] configuration from that Old [49:15] configuration to the new one the problem [49:18] is that they couldn't do it at exactly [49:20] the same time the changes would be [49:21] spaced out at least slightly in time and [49:25] the problem with this is this could [49:26] result in conflicting majorities for [49:29] example there's a point in time where [49:31] servers one and two could get together [49:34] to form a majority of the old [49:37] cluster and they could make decisions [49:40] based on that such as electing a leader [49:41] and committing entries to a particular [49:43] slot in the log but at the same point in [49:46] time the other three servers have [49:48] switched to the new configuration and [49:50] they form a majority of that [49:51] configuration so it's possible they [49:53] could get together with their majority [49:57] and commit an entry for the same log [50:00] entry that conflicts with the one uh [50:02] committed by the first two [50:04] servers what this says is that we have [50:06] to use a two-phase protocol we can't do [50:09] things in one phase and of course that's [50:11] typical of any kind of distributed [50:13] decision- making if anybody ever tells [50:14] you that they think they can make a [50:16] distributed decision in a single phase [50:18] uh you should question them pretty [50:19] seriously because either they're wrong [50:21] or they've discovered something that [50:22] everybody else in the world doesn't know [50:24] yet the solution is to use two phases to [50:28] change the [50:29] configuration raft switches first to an [50:32] intermediate phase called Joint [50:34] consensus during this phase the cluster [50:37] consists of all of the servers in both [50:39] the new and the old configuration so the [50:40] union of those [50:42] configurations but decisions such as [50:44] elections and commitment require a [50:46] separate majority separate agreement [50:48] from both the old configuration and the [50:50] new [50:51] configuration let me show you how this [50:53] works so we start off in an existing [50:57] configuration I'll called C old on the [51:00] slide and the way a configuration change [51:02] is initiated is that a client makes a [51:05] request of the leader just like it would [51:06] for any other state machine [51:08] operation when the server receives that [51:11] request then the leader adds an entry to [51:13] its log describing this joint [51:15] configuration which I'll call C old plus [51:18] new that's just a log entry like any [51:20] other log entry the server puts it in [51:22] its log and then the leader propagates [51:24] it out to the other servers in the [51:26] cluster using the append entries RPC [51:28] just like any other log entry the only [51:31] thing different about configuration [51:33] changes is that they take effect [51:35] immediately so as soon as a server [51:38] places a new configuration into its log [51:40] it begins living by that configuration [51:42] entry it doesn't wait for the [51:44] configuration entry for the log entry to [51:46] become committed before applying it like [51:48] it would for normal log [51:51] entries so back to our timeline here the [51:54] leader places the new configuration ENT [51:56] and its log and then as far as that [51:59] leader is concerned that's the [52:00] configuration in effect so that leader [52:01] makes all of its decisions according to [52:04] the old plus new configuration that [52:06] means that for example for any log entry [52:09] to be committed it must be logged on a [52:11] majority of the machines in the old [52:13] cluster and a majority of machines in [52:14] the new [52:16] configuration now for a while until that [52:19] entry becomes replicated or reaches the [52:21] point of being [52:22] committed it's possible that decisions [52:25] might be made either with C old or C old [52:27] plus new for example if the leader [52:30] crashes shortly after logging the new [52:33] configuration entry it's possible that [52:35] some other machine that is still [52:37] operating under the old configuration [52:39] could be elected and take over the [52:42] cluster but at some point this new [52:45] configuration entry will become [52:47] committed C old plus new once that [52:50] happens now it's not possible for any [52:54] machine to make a decision based purely [52:56] on on SE old now the way to see this is [52:59] to realize that in order for a leader to [53:03] become elected it must hold in its log [53:06] all of the entries that have been [53:07] committed so far so once this C old plus [53:10] new entry has been committed it's [53:12] guaranteed that any leader that's [53:14] elected will have that in its log and [53:16] that means that leader will be living by [53:17] it so for example the decision about [53:19] whether it won the election will be made [53:21] based on C old plus new and any log [53:23] entries that it commits will also be [53:26] committed based on C old plus new so at [53:29] this point it's no longer possible for [53:31] any server in the cluster to make [53:33] decisions based purely on the old [53:37] configuration so this at this point now [53:39] the cluster is operating Under The Joint [53:42] consensus as soon as that joint [53:44] consensus has become committed the [53:47] leader can now begin propagating a [53:50] configuration change entry for c new so [53:52] again it puts that in its log and it [53:54] begins replicating that out to the [53:55] cluster and again for a period of time [53:58] it's possible that the cluster May [54:00] operate under either C new or under that [54:03] joint consensus because once again that [54:05] server could crash and another server [54:07] could take over that's using the joint [54:09] consensus but again eventually that new [54:12] configuration entry will become [54:14] committed and then once that happens all [54:16] future decisions in the cluster will be [54:18] based on c [54:20] new so the key idea here the key thing [54:23] you can see is that there's no point in [54:25] time when both C old and C new can make [54:28] decisions without consulting the other [54:31] there's a period of time where C old can [54:32] make unilateral decisions and a period [54:34] of time where c new can make decisions [54:36] but those do not overlap guaranteed not [54:38] to overlap and in between both [54:41] configurations must be consulted so this [54:44] guarantees that we can't ever have two [54:46] separate consensuses form in the cluster [54:49] at one [54:50] time by the way this two-phase nature is [54:53] fundamental so any consensus algorithm [54:56] will have to use two phases of some sort [54:58] to change configuration in fact any sort [55:01] of distributed agreement requires two [55:03] phases if anybody comes to you with a [55:05] distributed agreement algorithm and they [55:06] claim it works in a single phase you [55:08] should be very skeptical because either [55:10] they're mistaken or they've discovered [55:12] something really important and new that [55:13] none of the rest of us [55:15] know there are a couple of other details [55:17] of this protocol first while we're in [55:20] transition it's possible that a server [55:22] from either configuration can serve as [55:23] the leader for the cluster now there's [55:26] one tricky thing which is what if the [55:28] current leader is not in the new [55:31] configuration then eventually it has to [55:33] step down it can't continue serving as [55:36] leader forever in a cluster where it's [55:37] not the not part of the configuration [55:40] and what we do in raft is that that old [55:44] leader steps down right at this point [55:47] once c new gets committed the old [55:50] leader steps [55:53] down if it's not [55:56] in the new [55:59] configuration so at that point the other [56:02] followers will time out and they will [56:04] elect a new leader and now at this point [56:06] that new leader will have to be elected [56:07] from the new configuration and we're off [56:09] and running but even so this actually [56:11] means that the old leader will continue [56:15] to serve as leader for a little [56:17] while after it is no longer part of the [56:21] configuration it'll be operating under c [56:23] new in which it's not actually a leader [56:25] but it will continue to serve as leader [56:27] until that entry gets fully gets [56:29] replicated enough to be [56:32] committed this brings us to the end of [56:35] the raft presentation let me conclude by [56:37] just reminding you of the six major [56:39] pieces of the algorithm the first piece [56:42] is leader election in which we make sure [56:44] that at most one server can act as [56:46] leader in any given term second I [56:49] described the normal operation of the [56:51] system where leaders accept requests [56:53] from clients and replicate them across [56:54] the cluster and remember the very [56:57] important consistency check performed in [57:00] appended entries which guarantees the [57:02] behavior of the logs and provides a hook [57:04] that we can use to restore consistency [57:06] later on then third I talked about [57:08] leader changeovers and there were two [57:10] major issues the most important one is [57:12] guaranteeing the safety of the system [57:14] and I showed you how we can guarantee [57:16] that once a log entry has been committed [57:18] it will live forever and I also talked [57:20] about how a server can make sure all of [57:22] the followers logs eventually become [57:24] identical to its own [57:26] fourth step is making sure that old [57:28] leaders can't come back to haunt us [57:30] after we've replaced them then I talked [57:33] briefly about how clients behave and in [57:35] particular what they need to do in order [57:37] to survive crashes of some of the [57:39] servers in raft and then finally I [57:41] showed you how the raft system can [57:43] handle configuration changes in a way [57:45] that is automatic and completely safe [57:48] just one overall comment before I [57:50] conclude which is the the key element of [57:52] this algorithm is that the system has to [57:55] work perfectly even if just a bare [57:57] majority of the servers are up which [57:59] means it can't ever depend on having [58:01] complete information or knowledge of [58:02] what's going on there could always be [58:04] information out there in servers that [58:05] are down that's unknown and so the [58:08] algorithm has to be designed at every [58:09] point to be able to handle that all [58:12] right well this concludes the [58:13] presentation on raft