MIT 6.824 学习记录：Raft 论文阅读（Section 1 - 5）
最近因为杂事较多，学习进度稍有延误。不过最终还是结合视频和相关资料，完整完成了 Raft 论文 Section 1-5 的学习。
Raft 是一种共识算法。在此前学习的内容中，比如 MapReduce、FT VM，都存在单点故障的问题：MapReduce 中的 coordinator 宕机，FT VM 中的存储系统故障，这些都会导致系统不可用。这些系统之所以这样设计，核心原因是在保持架构简洁的前提下，尽可能避免分布式系统中常见的脑裂（brain split）问题，归根结底，本质还是一致性问题。而共识算法，正是分布式系统中针对一致性问题的标准解法，可以有效保障多节点之间的数据一致性。比如，可以借鉴之前 FT VM 的思路，将 Raft 引入，构建出一个具备故障容错能力的分布式状态机（Fault Tolerant State Machine）系统。
相较于前段时间阅读的 Paxos，Raft 的可理解性更强（实际上论文本身就提到 Raft 的一个设计目标就是提升可理解性），同时在工程实践中也更加易用。这两点正是 Raft 被设计的核心目标——教学友好（Understandability）*和*易于工程落地（Practicality）。
为了提升可理解性，Raft 在设计上重点考虑了以下三个方面：
提供清晰易懂的阅读和理解路径
提供一套在工程环境下可直接落地的系统设计，而无需额外的复杂设计
在必要的地方引入随机性（例如选主过程），以降低系统的不确定性，避免陷入活锁等异常状态
核心概述
Raft 与 Paxos 最大的区别之一在于 Raft 采用了显式的选主机制（Leader Election）。相较于 Paxos 中相对模糊的 leader 概念，Raft 首要解决的问题就是 leader 的选举。后续的所有操作，比如日志提交、日志复制和状态变更，都由 leader 主导。这种设计极大地提升了系统的可理解性。整个系统被明确拆解为三个核心子模块：
Leader Election（选主）：选举 leader
Log Replication（日志复制）：leader 将客户端的命令同步到其他节点
Safety（安全性）：确保所有节点应用的日志是相同的，保障状态一致
基本架构
一个基于 Raft 的集群通常包含多台服务器。对于 2n + 1 个节点的集群，Raft 能容忍 n 个节点故障。
每个 server 有三种状态：
Leader：唯一的主节点，负责处理客户端请求。
Follower：被动节点，仅响应 leader 和 candidate 的请求。
Candidate：在选主过程中由 follower 转变而来，主动发起投票请求。
在正常运行时，集群会有一个 leader 和若干 follower。candidate 状态仅在 leader 宕机、发生重新选举时出现。这种模式非常契合传统的一主多从数据库架构，事实上，很多数据库的主从同步机制的确可以看作是基于 Raft 或类似思想设计的。
Raft 将时间划分为若干个 term，每个 term 拥有一个递增的编号。每个 term 都始于一次选举，若选举成功，则该 term 内由该 leader 主导直到出现崩溃或进入新 term。
论文中示意图如下：
term 的变更与 server 状态密切相关。选举过程中，candidate 试图成为 leader；一旦成功，就在当前 term 内主导整个集群的运作。
Raft 定义了两类核心 RPC：
RequestVote RPC：candidate 在选举阶段发起，用于拉票。
AppendEntries RPC：leader 在日志复制阶段发起，也承担心跳（heartbeat）的功能。
如果 follower 在一定时间内没有接收到来自 leader 的任何 RPC（包括心跳），它就会转变为 candidate，发起新一轮的选举。
term ID 是整个系统一致性的关键。当某个节点接收到低于自己当前 term 的请求时，会直接拒绝。反之，如果发现自己落后（term 比其他节点小），则立即降级为 follower，从而完成状态闭环。
状态转换示意图如下：
这个设计的一个精妙之处在于：每个节点本质上都是一个事件驱动的状态机。节点不需要感知其他节点的完整状态，只需要根据接收到的事件（RPC 请求或超时）来驱动自身状态的转换，并履行相应职责。这种解耦式的设计思路，在分布式系统中尤为重要。过度的全局状态感知不仅增加系统复杂度，也严重影响扩展性和可靠性。Raft 通过事件驱动的状态机模型，优雅地平衡了复杂性与一致性。
Leader 选举
选主机制基于心跳超时（heartbeat timeout）触发：
所有 server 初始都是 follower。
只要持续接收到 leader 或 candidate 发出的 RPC（如 AppendEntries 或 RequestVote），follower 就会保持当前状态。
如果在配置的 election timeout 时间内没有接收到任何 RPC，follower 会将自身状态转为 candidate，并开始发起选举（term +1）。
选举过程是一个事件驱动的状态转换。candidate 会：
向其他 server 发出 RequestVote 请求。
自己给自己投票。
根据以下事件改变状态：
赢得选举（获得多数投票） → 转为 leader
接收到新的 leader 的 AppendEntries RPC → 转为 follower
若对方 term 不小于自己，candidate 接受其为 leader 并转为 follower
若对方 term 过旧，忽略该请求，继续选举
超时未获胜 → 进入新的 term，重新开始选举
在投票过程中，每个节点在一个 term 中最多只能投票一次，且只投给第一个满足条件的 candidate。这一设计与 Paxos 中 acceptor 对 proposal 的响应机制高度一致，目的都是为了保证同一时间只能有一个 leader。
同时，这也解释了为何 Raft 集群需要 2n + 1 个节点来容忍 n 个故障：只要多数节点（n + 1）在线，系统就能够完成选举并继续提供服务。
Split Votes（投票分裂）
在存在多个 candidate 同时竞争时，可能会出现投票分裂（split votes），导致没有任何 candidate 获得多数票。为了缓解这一问题，Raft 引入了随机的 election timeout。每个 follower 在超时转变为 candidate 前，会等待一个随机的超时时间，从而降低多个 candidate 同时出现的概率。绝大多数情况下，这种随机化能够有效避免投票分裂，提高选主的成功率。
日志复制
一旦 leader 被选举出来，它就开始接收客户端请求，并将命令封装成 log entry：
leader 将 log entry 追加到本地日志。
并向所有 follower 发送 AppendEntries RPC 进行同步。
当一条 log entry 被集群中大多数节点成功复制后，该 entry 被视为 committed。此时：
leader 会应用该命令到状态机。
返回结果给客户端。
如果未能完成大多数复制，leader 会持续重试 AppendEntries，直到成功。
这个机制与 FT VM 中的主备同步策略异曲同工，通过 majority commit 保证强一致性。
示意图如下：
图中可以看到，log index 1-7 被至少三个节点持有，因此被认为是 committed。
日志不一致修复
当 leader 崩溃并重新选举后，可能会存在部分节点日志不一致的情况。新的 leader 通过以下机制完成修复：
leader 为每个 follower 维护一个 nextIndex（下一个要发送的日志条目）。
leader 会从 nextIndex 开始向 follower 发送日志。
如果 follower 返回日志不匹配，leader 会递减 nextIndex，直到找到匹配的前缀，然后继续发送缺失的日志。
日志检查是从高 index 往低回退的。这种机制依赖于 Raft 中日志的前缀一致性：一旦在某个 index 上匹配成功，之前的日志必然一致，保障了修复的正确性。
安全性
Raft 的安全性主要依赖于 Leader Completeness Property：
一个新的 leader 必须包含所有已 committed 的日志。
为了实现这一目标，Raft 在投票时采用如下策略：
候选人（candidate）只有在日志不落后于投票人的情况下，才能获得该投票。
判断日志是否更新：
首先比较最后一条日志的 term，term 大的更新。
若 term 相同，则比较日志长度（index）。
这种设计结合 committed 的定义非常巧妙：一旦一条日志被多数节点持有，它就是 committed 的。即使发生故障，只要多数节点中至少一个存有该日志，那么这个节点就有可能成为 leader，从而确保日志不会丢失。
另外，Raft 的所有 RPC 都是幂等的，leader 可以无限次重试，因此 follower 或 candidate 无需专门的机制来保障宕机恢复后的正确性。
Raft 的安全性并不依赖时间，但可用性确实受时间参数影响。论文提出：broadcastTime ≪ electionTimeout ≪ MTBF
其中：
broadcastTime：一次 RPC 广播的时间。
electionTimeout：触发选举的超时时间。
MTBF（Mean Time Between Failures）：平均故障间隔时间。
满足这个时间关系，Raft 系统能够维持高可用和稳定性。
Question
问题描述：
Suppose we have the scenario shown in the Raft paper's Figure 7: a cluster of seven servers, with the log contents shown. The first server crashes (the one at the top of the figure), and cannot be contacted. A leader election ensues. For each of the servers marked (a), (d), and (f), could that server be elected? If yes, which servers would vote for it? If no, what specific Raft mechanism(s) would prevent it from being elected?
对应图示如下：
分析
a、d、f 在无法接收到原 leader 心跳后，都会成为 candidate，但能否当选 leader，取决于能否获得多数投票（即至少4票）。
按照日志更新的投票规则：
节点 b：term 小，投票。
节点 c：term 相同但 index 更大，不投票。
节点 d：term 更大，不投票。
节点 e：term 小，投票。
节点 f：term 小，投票。
→ a 最多能获得 4 票，可能当选
→ 同理得 d 的 term 最大，所有节点都会投给 d，d 最多获得 6 票，可能当选
→ 同理 f 的 term 最小，没有任何节点会投票，无法当选
总结
本次学习顺利完成了 Raft 论文 Section 1-5 的阅读。不得不说，这篇论文确实做到了它所承诺的“understandable”。论文的逻辑严密，层层递进，设计细节充分考虑了分布式系统中的各种异常场景😍
我感觉这次收获最大的，是深刻体会到事件驱动状态机模型在复杂系统建模中的巨大价值。这种设计不仅提升了系统的可维护性，也显著降低了分布式一致性协议的复杂度。
接下来，我将继续推进课程，正式开始 Lab3 的编程实践。非常期待通过亲手实现一个完整的 Raft 系统，进一步加深对这个优秀设计的理解与掌握🫠