MIT-6824lab3：raft

Posted on In , Views:
记录一下raft这个lab的学习过程

论文

正文忠于原文翻译，快速了解可以看每一段的总结

引言

共识算法允许一组机器作为一个整体协同工作，即使其中一些成员出现故障也能存续。

Raft 在许多方面与现有的共识算法相似，但它具有几个新颖的特点：

  • 强领导者 (Strong leader)： Raft 使用比其他共识算法更强的领导形式。例如，日志条目只从领导者流向其他服务器。这简化了复制日志的管理，并使 Raft 更易于理解。
  • 领导者选举 (Leader election)： Raft 使用随机定时器来选举领导者。这在任何共识算法心跳机制的基础上仅增加了少量的机制，同时能简单快速地解决冲突。
  • 成员变更 (Membership changes)： Raft 用于更改集群中服务器集的机制使用了一种新的联合共识 (joint consensus) 方法，在这种方法中，两种不同配置的多数派在过渡期间会发生重叠。这使得集群在配置更改期间能够继续正常运行。

它比其他算法更简单、更易理解；它的描述足够完整，可以满足实际系统的需求；它有多个开源实现并被多家公司使用；其安全性属性已得到正式规范和证明；且其效率与现有算法相当。

状态复制机

共识算法通常出现在复制状态机的背景下。在这种方法中，一组服务器上的状态机计算相同状态的副本，并且即使在某些服务器宕机时也能继续运行。复制状态机被用于解决分布式系统中的各种容错问题。

复制状态机通常使用复制日志来实现，如图 1 所示。每台服务器存储一个包含一系列命令的日志，其状态机按顺序执行这些命令。每个日志都包含相同顺序的相同命令，因此每个状态机都会处理相同的命令序列。由于状态机是确定性的（deterministic），因此每个状态机都会计算出相同的状态和相同的输出序列。

保持复制日志的一致性是共识模块的任务。 服务器上的共识模块接收来自客户端的命令并将其添加到自己的日志中。它与其他服务器上的共识模块进行通信，以确保即使某些服务器发生故障，每个日志最终也包含相同顺序的相同请求。一旦命令被正确复制，每台服务器的状态机都会按日志顺序处理它们，并将输出返回给客户端。结果，这些服务器看起来就像形成了一个单一的、高度可靠的状态机。

用于实际系统的共识算法通常具有以下属性：

  • 安全性 (Safety)： 在所有非拜占庭条件（包括网络延迟、分区、数据包丢失、重复和重排序）下，绝不返回错误结果。
  • 可用性 (Availability)： 只要过半数（majority）的服务器处于运行状态且能相互通信并与客户端通信，系统就是完全可用的。因此，一个典型的由五台服务器组成的集群可以容忍两台服务器的故障。服务器被假定为通过停机（stopping）而故障；它们稍后可能会从稳定存储的状态中恢复并重新加入集群。
  • 不依赖时序： 它们不依赖时序来保证日志的一致性：错误的時钟和极端的网络消息延迟在最坏的情况下也只会导致可用性问题（而非安全性问题）。
  • 快速响应： 在通常情况下，一旦集群的大多数成员对单轮远程过程调用（RPC）做出了响应，命令即可完成；少数慢服务器不会影响整体系统性能。

总结：

1. 复制状态机（Replicated State Machine）

  • 定义：一组服务器上的状态机，计算相同状态的相同副本
  • 核心能力：即使部分服务器宕机，整体仍能继续运行
  • 典型应用：领导者选举、配置信息管理（如GFS、HDFS、Chubby、ZooKeeper）

2. 实现方式：复制日志（Replicated Log）

  • 每个服务器存储相同的命令序列（日志）
  • 状态机按顺序执行这些命令
  • 由于状态机是确定性的 → 输出结果必然相同

3. 共识算法的职责

功能 说明
接收命令 从客户端接收请求
复制日志 确保所有服务器日志一致（相同命令、相同顺序）
容错处理 即使有服务器故障，也能保证一致性
状态机执行 命令提交后，各服务器状态机执行并返回结果

4. 实际系统对共识算法的四大要求

特性 含义
安全性（Safety） 绝不返回错误结果（即使网络延迟、丢包、乱序等）
可用性（Availability） 多数服务器存活且互通时，系统可用（如5台容忍2台故障）
不依赖时序 时钟故障或消息延迟只影响可用性，不影响正确性
高效性 多数响应即可提交，少数慢节点不拖累整体性能

Raft共识算法

Raft通过首先选举一个杰出的领导者（distinguished leader），然后赋予该领导者管理复制日志的完全责任来实现共识。领导者接受来自客户端的日志条目，在其他服务器上复制它们，并告诉服务器何时可以安全地将日志条目应用到它们的状态机。拥有领导者简化了复制日志的管理。

Raft将共识问题分解为三个相对独立的子问题：

  • 领导者选举：当现有领导者失败时，必须选择一个新的领导者

  • 日志复制：领导者必须接受来自客户端的日志条目，并在集群中复制它们，强制其他日志与其自身一致

  • 安全性：如果任何服务器已将特定日志条目应用到其状态机，则没有其他服务器可以对同一日志索引应用不同的命令。

1
2
3
4
5
6
7
Raft保证下面这些特性在任何时候都为真，这些特性会在具体算法中体现出来

- 选举安全性（Election Safety）：在给定任期中最多只能选举一个领导者。
- 领导者只追加（Leader Append-Only）：领导者从不覆盖或删除其日志中的条目；它只追加新条目。
- 日志匹配（Log Matching）：如果两个日志包含具有相同索引和任期的条目，则日志在给定索引之前的所有条目中都相同。
- 领导者完整性（Leader Completeness）：如果日志条目在给定任期中提交，则该条目将存在于所有更高编号任期的领导者日志中。
- 状态机安全性（State Machine Safety）：如果服务器已将给定索引的日志条目应用到其状态机，则没有其他服务器将对同一索引应用不同的日志条目。

Raft基础

Raft集群包含若干服务器。在任何给定时间，每个服务器处于三种状态之一：领导者（leader）、跟随者（follower）或候选人（candidate）。在正常操作中，恰好有一个领导者，所有其他服务器都是跟随者。

  • 跟随者是被动的：它们自己不发出请求，只是响应来自领导者和候选者的请求。

  • 领导者处理所有客户端请求（如果客户端联系跟随者，跟随者将其重定向到领导者）。

  • 候选人是用于选举新领导者的临时状态，竞选成功成为领导者，失败回到跟随者。

Raft将时间划分为任意长度的任期（terms）。任期用连续整数编号。每个任期以一次选举开始，其中一个或多个候选人试图成为领导者。如果候选人赢得选举，则它在该任期的剩余时间内担任领导者。在某些情况下，选举可能导致分裂投票（split vote）。在这种情况下，任期将以没有领导者结束；很快将开始一个新的任期（带有新的选举）。Raft确保在给定任期中最多只有一个领导者。

不同服务器可能在不同时间观察到任期之间的转换，在某些情况下，服务器可能无法观察到选举甚至整个任期。任期在Raft中充当逻辑时钟，它们允许服务器检测过时信息，如陈旧的领导者。每个服务器存储一个当前任期号（current term number），该编号随时间单调递增。当前任期在服务器通信时交换；如果一个服务器的当前任期小于另一个服务器的，则它将自己的当前任期更新为较大的值。如果候选人或领导者发现其任期已过时，它立即恢复为跟随者状态。如果服务器收到带有陈旧任期号的请求，它拒绝该请求。

Raft服务器使用远程过程调用（RPCs）进行通信，基本共识算法只需要两种类型的RPC。RequestVote RPCs由候选人在选举期间发起（第5.2节），AppendEntries RPCs由领导者发起以复制日志条目并提供心跳形式（第5.3节）。第7节添加了第三种RPC用于在服务器之间传输快照。如果服务器没有及时收到响应，它们会重试RPC，并且它们并行发出RPC以获得最佳性能。

总结：

1. 集群规模
Raft集群通常包含5台服务器，这样的设计允许系统容忍任意2台服务器的故障，只要多数服务器（3台）正常运行，系统就能继续工作。

2. 节点状态
论文提出每个服务器在任意时刻都处于三种状态之一：

  • 跟随者（Follower）：完全被动的状态，只响应来自领导者和候选人的请求，自己不主动发起任何通信
  • 领导者（Leader）：处理所有客户端请求，负责日志管理和复制，是集群中唯一的活跃决策者
  • 候选人（Candidate）：用于选举新领导者的临时状态，当跟随者超时未收到心跳时转换而来

正常运作时，集群中恰好有一个领导者和多个跟随者。如果客户端误连到跟随者，跟随者会将其重定向到领导者。

3. 任期（Term）
论文将时间划分为任期的概念。任期具有任意长度，用连续整数编号。每个任期都以一次选举开始，候选人试图成为领导者。选举成功则该候选人担任领导者直至任期结束；若选举失败（如分裂投票），则该任期无领导者，很快开始新任期。

4. 任期的作用
任期在Raft中充当逻辑时钟，核心作用包括：

  • 检测过时信息：通过比较任期号识别陈旧的领导者或过期请求
  • 保证单调性：每个服务器存储当前任期号，通信时总是更新为更大的值
  • 强制状态转换：当领导者或候选人发现自身任期过时，立即退化为跟随者
  • 拒绝非法请求：收到任期号小于自身的请求直接拒绝

5. 节点间通信
Raft服务器通过远程过程调用（RPC）通信，基础共识算法仅需两种RPC：

  • RequestVote RPC：由候选人在选举期间发起，用于收集投票
  • AppendEntries RPC：由领导者发起，既用于复制日志条目，也作为心跳维持权威

论文还提到两种机制保证通信可靠性：一是超时重试，未收到响应则持续重试；二是并行发送，同时向所有服务器发请求以获得最佳性能。

领导者选举

Raft使用心跳机制来触发领导者选举。服务器启动时，它们以跟随者状态开始。只要服务器从领导者或候选人接收到有效的RPC，它就保持跟随者状态。领导者向所有跟随者发送周期性心跳（携带空日志条目的AppendEntries RPC）以维持其权威。如果跟随者在一段称为选举超时（election timeout）的时间内没有收到通信，则它假设没有可用的领导者，并开始选举以选择新的领导者。

为了开始选举，跟随者递增其当前任期并转换为候选人状态。然后它为自己投票，并向集群中的每个其他服务器并行发出RequestVote RPC。候选人保持此状态，直到发生以下三种情况之一：
(a ) 它赢得选举
(b ) 另一台服务器确立自己为领导者
(c ) 一段时间过去没有获胜者。这些结果将在以下段落中分别讨论。

如果候选人收到集群中多数服务器在同一任期的投票，则它赢得选举。每个服务器在给定任期中最多投票给一个候选人，以先到先得的方式。多数规则确保对于特定任期，最多只有一个候选人能赢得选举。一旦候选人赢得选举，它就成为领导者。然后它向所有其他服务器发送心跳消息以确立其权威并防止新的选举。

在等待投票时，候选人可能收到来自另一台声称是领导者的服务器的AppendEntries RPC。如果领导者的任期（包含在其RPC中）至少与候选人的当前任期一样大，则候选人承认该领导者为合法领导者并返回跟随者状态。如果RPC中的任期小于候选人的当前任期，则候选人拒绝该RPC并继续保持在候选人状态。

第三种可能的结果是候选人既未赢也未输选举：如果许多跟随者同时成为候选人，投票可能分裂，导致没有候选人获得多数。当这种情况发生时，每个候选人将超时并通过递增其任期和发起另一轮RequestVote RPC来开始新的选举。然而，如果没有额外措施，分裂投票可能重复发生。

Raft使用随机化的选举超时来确保分裂投票很少发生且能快速解决。首先，为了防止分裂投票，选举超时从固定区间（例如150-300ms）中随机选择。这分散了服务器，使得在大多数情况下只有单个服务器超时；它赢得选举并在其他服务器超时之前发送心跳。相同的机制用于处理分裂投票。每个候选人在选举开始时重新启动其随机化选举超时，并等待该超时过去后才开始下一次选举；这降低了新选举中再次发生分裂投票的可能性。

总结：

1. 选举的触发条件

Raft通过心跳机制来触发选举。服务器启动时初始状态为跟随者。只要持续收到来自领导者或候选人的有效RPC，就保持跟随者状态。领导者通过周期性发送心跳（空的AppendEntries RPC）来维持权威。当跟随者在选举超时时间内未收到任何通信，则假设集群中无可用领导者，主动发起选举。

2. 选举的发起流程

一旦触发选举，跟随者执行以下步骤转换为候选人：

  • 递增自身当前任期号（term + 1）
  • 将自身状态转换为候选人
  • 投票给自己
  • 并行向集群中所有其他服务器发送RequestVote RPC请求投票

3. 选举的三种可能结果

候选人保持候选人状态，直到以下三种情况之一发生：
（a）赢得选举

  • 条件：获得集群多数服务器的投票（同一任期内）
  • 投票规则：每个服务器在给定任期中最多投一票，先到先得
  • 安全性保证：多数规则确保同一任期最多只有一个获胜者（选举安全性）
  • 获胜后动作：立即成为领导者，向所有服务器发送心跳确立权威

（b）发现已有领导者

  • 场景：等待投票期间收到AppendEntries RPC
  • 判断规则：比较RPC中的任期与自身当前任期
    • 若对方任期 ≥ 自身任期：承认对方为合法领导者，立即退化为跟随者
    • 若对方任期 < 自身任期：拒绝该RPC，继续保持候选人状态

（c）选举超时（分裂投票）

  • 原因：多个跟随者同时超时成为候选人，导致选票分散，无人获得多数
  • 处理：候选人等待自身选举超时后，递增任期，重新发起新一轮选举

4. 随机化选举超时

为解决分裂投票问题，Raft引入随机化选举超时机制：
设计目的

  • 防止多个服务器同时触发选举
  • 确保分裂投票能快速解决

工作机制

  • 预防分裂：随机化使各服务器超时时间分散，大概率只有单个服务器先超时，它赢得选举并在其他服务器超时前发送心跳
  • 解决分裂：若发生分裂投票，各候选人等待各自的随机超时后重试，降低再次冲突概率

日志复制

每个客户端请求包含一个要由复制状态机执行的命令。领导者将该命令作为新条目追加到其日志中，然后并行向其他每个服务器发出AppendEntries RPC以复制该条目。当该条目被安全复制后，领导者将该条目应用到其状态机，并将执行结果返回给客户端。如果跟随者崩溃或运行缓慢，或者网络数据包丢失，领导者会无限期重试AppendEntries RPC（即使在响应客户端之后），直到所有跟随者最终存储所有日志条目。

每个日志条目存储一个状态机命令以及该条目被领导者接收时的任期号。日志条目中的任期号用于检测日志之间的不一致性。每个日志条目还有一个整数索引，标识其在日志中的位置。

领导者决定何时将日志条目应用到状态机是安全的；这样的条目称为已提交（committed）。Raft保证已提交的条目是持久的，并将最终由所有可用的状态机执行。一旦创建该条目的领导者已将其复制到多数服务器上，该日志条目就被视为已提交。这也提交了领导者日志中所有先前的条目，包括由先前领导者创建的条目。领导者跟踪其已知已提交的最高索引，并将其包含在未来的AppendEntries RPC（包括心跳）中，以便其他服务器最终得知。一旦跟随者得知某日志条目已提交，它就将该条目应用到其本地状态机（按日志顺序）。

Raft维护以下特性，它们共同构成图3中的日志匹配特性（Log Matching Property）：

  • 如果两个日志中的条目具有相同的索引和任期，则它们存储相同的命令。

  • 如果两个日志中的条目具有相同的索引和任期，则日志在该条目之前的所有条目中都相同。

第一个特性源于以下事实：领导者在给定任期内最多创建一个具有给定日志索引的条目，且日志条目永远不会改变其在日志中的位置。

第二个特性由AppendEntries执行的简单一致性检查保证。发送AppendEntries RPC时，领导者包含其日志中紧接新条目之前的条目的索引和任期。如果跟随者在其日志中没有找到具有相同索引和任期的条目，则它拒绝新条目。

一致性检查充当归纳步骤：日志的初始空状态满足日志匹配特性，且一致性检查在扩展日志时保持日志匹配特性。因此，每当AppendEntries成功返回时，领导者就知道跟随者的日志与其自己的日志在新条目之前完全相同。

在正常操作期间，领导者和跟随者的日志保持一致，因此AppendEntries一致性检查从不失败。然而，领导者崩溃可能使日志不一致（旧领导者可能未完全复制其日志中的所有条目）。这些不一致可能在一系列领导者和跟随者崩溃中累积。跟随者可能缺少领导者上存在的条目，可能有领导者上不存在的额外条目，或两者兼有。日志中的缺失和多余条目可能跨越多个任期。

在Raft中，领导者通过强制跟随者的日志复制其自身日志来处理不一致。这意味着跟随者日志中的冲突条目将被领导者日志中的条目覆盖。

为使跟随者日志与其自身一致，领导者必须找到两个日志一致的最新日志条目，删除跟随者日志中该点之后的任何条目，并发送跟随者该点之后的所有领导者条目。所有这些动作都是对AppendEntries RPC执行的一致性检查的响应。领导者为每个跟随者维护一个nextIndex，这是领导者将发送给该跟随者的下一个日志条目的索引。当领导者首次掌权时，它将所有nextIndex值初始化为其日志中最后一个之后的索引。如果跟随者的日志与领导者不一致，AppendEntries一致性检查将在下一次AppendEntries RPC中失败。拒绝后，领导者递减nextIndex并重试AppendEntries RPC。最终nextIndex将达到领导者和跟随者日志匹配的点。当这种情况发生时，AppendEntries将成功，这将删除跟随者日志中的任何冲突条目并追加来自领导者日志的条目（如果有）。一旦AppendEntries成功，跟随者的日志就与领导者一致，并在该任期的剩余时间内保持如此。

如果需要，可以优化协议以减少被拒绝的AppendEntries RPC数量。例如，拒绝AppendEntries请求时，跟随者可以包含冲突条目的任期以及它存储的该任期的第一个索引。有了这些信息，领导者可以将nextIndex递减以绕过该任期中的所有冲突条目；每个有冲突条目的任期需要一个AppendEntries RPC，而不是每个条目一个。在实践中，我们怀疑这种优化是不必要的，因为故障很少发生，且不太可能有太多不一致的条目。

总结：

1. 日志复制的基本流程

当领导者收到客户端请求时，它会将命令作为新条目追加到本地日志，然后并行向所有跟随者发起AppendEntries RPC进行复制。一旦该条目被成功复制到多数服务器上，领导者就将其标记为已提交，应用到状态机并把结果返回给客户端。对于那些崩溃、运行缓慢或网络不通的跟随者，领导者会持续重试AppendEntries RPC，即使在已经响应客户端之后也不会停止，直到所有跟随者最终都存储了该条目。

每个日志条目包含三个关键信息：命令、任期号、索引。

2. 提交机制与日志匹配特性

提交规则

Raft规定：一旦创建该条目的领导者将其复制到多数服务器上，该条目即被视为已提交（可以理解为已同步、已安全）。值得注意的是，提交具有传递性——提交某个条目会自动提交其之前的所有条目，无论这些条目是由当前领导者还是前任领导者创建的。

为了传播提交信息，领导者会在所有AppendEntries RPC（包括心跳）中携带已知的最高提交索引。跟随者收到后，就会将相应条目按顺序应用到本地状态机。

日志匹配

Raft的设计确保了两个核心特性共同构成日志匹配特性：
第一，如果两个日志中的条目具有相同的索引和任期，那么它们存储的命令必然相同；
第二，如果两个条目索引和任期相同，那么它们之前的所有条目也都相同。第一个特性源于领导者在给定任期内只会创建一次给定索引的条目，且条目位置永不改变；
第二个特性则通过AppendEntries的一致性检查来保证。

3. 一致性检查与自动收敛

一致性检查是维护日志匹配特性的关键机制。每当领导者发送AppendEntries RPC时，都会携带紧接新条目之前那个条目的索引和任期信息。跟随者会检查自己的日志中是否存在匹配的条目：如果存在就接受新条目，如果不存在则拒绝。

在正常运作时，领导者和跟随者的日志保持一致，一致性检查不会失败。但领导者崩溃可能造成日志不一致，且这种不一致会在多次领导者变更中累积。Raft的处理方式非常直接：领导者强制跟随者的日志复制自己的日志，用领导者的条目覆盖跟随者中的冲突条目。

实现上，领导者为每个跟随者维护一个nextIndex值，表示下一个要发送给该跟随者的条目索引。新上任时，nextIndex被初始化为领导者最后条目之后的位置（乐观指针）。如果跟随者日志不一致，一致性检查就会失败，此时领导者递减nextIndex并重试，直到找到两个日志匹配的点。随后AppendEntries成功执行，用正确的日志覆盖跟随者错误的那部分。

论文也提到一种可能的优化：跟随者拒绝时可以返回冲突条目的任期和该任期的首个索引，让领导者一次性跳过整个冲突任期。但作者认为这种优化通常没有必要，因为实际故障很少发生，不一致的条目数量通常也不多。

4. 关键设计原则与特性保证

Raft的日志机制遵循几项核心设计原则。

  • 领导者只追加原则规定领导者从不覆盖或删除自身日志中的条目，只向末尾追加新内容，这是保证安全性的重要基础。

  • 强领导者原则则确保所有数据单向流动，从领导者到跟随者，领导者全权决定日志内容和提交时机，这大大简化了系统设计的复杂度。

安全性

上述的机制还不足以“确保每个状态机以相同顺序执行完全相同的命令”，所以还要再附加一些规则

选举限制

Raft使用一种简单的方法，保证从选举时刻起，每个新领导者就包含来自先前任期的所有已提交条目，无需将这些条目传输给领导者。

Raft使用投票过程来防止候选人赢得选举，除非其日志包含所有已提交条目。候选人必须联系集群的多数才能被选举，这意味着每个已提交条目必须存在于这些服务器中的至少一个。如果候选人的日志至少与该多数中的任何其他日志一样新（"最新"的精确定义如下），那么它将持有所有已提交条目。

具体在RequestVote RPC实现了这一限制：RPC包含有关候选人日志的信息，如果投票人自己的日志比候选人的更新，则拒绝投票。

提交先前任期的条目

如领导者知道一旦当前任期的条目存储在多数服务器上，该条目就被提交。如果领导者在提交条目之前崩溃，未来的领导者将尝试完成复制该条目。然而，领导者不能立即得出结论：一旦先前任期的条目存储在多数服务器上，它就被提交。图8展示了一个旧日志条目存储在多数服务器上，但仍可能被未来领导者覆盖的情况。

为了消除图8中的问题，Raft从不通过计算副本数来提交先前任期的日志条目。只有领导者当前任期的日志条目才通过计算副本数来提交；一旦当前任期的条目以这种方式提交，则所有先前条目都因日志匹配特性而间接提交。在某些情况下，领导者可以安全地得出旧日志条目已提交的结论（例如，如果该条目存储在每个服务器上），但Raft采取更保守的方法以保证安全。

Raft在提交规则中承担这种额外复杂性，因为日志条目在领导者复制先前任期条目时保留其原始任期号。在其他共识算法中，如果新领导者重新复制来自先前"任期"的条目，它必须用新的"任期号"这样做。Raft的方法使其更容易推理日志条目，因为它们随时间和跨日志保持相同的任期号。此外，Raft中的新领导者比其他算法发送更少的先前任期日志条目（其他算法必须发送冗余日志条目以在提交前重新编号）。

总结：

前几节描述的领导者选举和日志复制机制还存在安全漏洞。具体来说，如果一个跟随者在领导者提交多个条目期间不可用，之后它可能被选为新领导者，并用新条目覆盖那些已提交的条目，导致不同状态机执行不同命令。（实际可能性非常非常小，只要记住是什么限制就行了）

为解决这一问题，Raft引入了两项关键机制：选举限制和当前任期提交规则。

1. 选举限制机制

核心目标

确保新当选的领导者从选举时刻起就包含所有先前任期中已提交的条目，无需后续传输缺失条目。这保证了日志条目单向流动（从领导者到跟随者），且领导者永不覆盖自身日志。

具体实现

Raft通过投票过程中的日志比较来实现这一限制。RequestVote RPC包含候选人的日志信息，投票人执行以下检查：如果自己的日志比候选人的更新，则拒绝投票。日志新旧比较规则为：先比较最后条目的任期，任期大者更新；若任期相同，则日志更长者更新。

2. 当前任期提交规则

问题根源

直接通过副本数判定先前任期条目提交存在风险。如图8所示，一个旧条目即使复制到多数服务器，仍可能被未来领导者覆盖，因为新领导者可能未包含该条目，且其日志更新。

解决方案

Raft采取保守策略：仅通过计算副本数提交当前任期的条目。一旦当前任期的某个条目被提交，根据日志匹配特性，其之前所有条目都间接被视为已提交。这种设计避免了先前任期条目的直接提交判定，消除了被未来领导者覆盖的风险。

跟随者和候选人崩溃

到目前为止，我们专注于领导者故障。跟随者和候选人崩溃的处理比领导者崩溃简单得多，且两者的处理方式相同。如果跟随者或候选人崩溃，那么发送给它的未来RequestVote和AppendEntries RPC将失败。Raft通过无限重试来处理这些故障；如果崩溃的服务器重新启动，RPC将成功完成。如果服务器在完成RPC后但在响应之前崩溃，那么它将在重新启动后收到相同的RPC。Raft RPC是幂等的，因此这不会造成损害。例如，如果跟随者收到包含其日志中已存在的日志条目的AppendEntries请求，它会忽略新请求中的这些条目。

时序与可用性

Raft的要求之一是安全性不能依赖于时序：系统不能仅仅因为某些事件发生得比预期快或慢就产生错误结果。然而，可用性（系统及时响应客户端的能力）必然依赖于时序。例如，如果消息交换时间超过服务器崩溃的典型间隔时间，候选人将没有足够长的时间来赢得选举；没有稳定的领导者，Raft无法取得进展。

领导者选举是Raft中时序最关键的方面。只要系统满足以下时序要求，Raft就能够选举并维持稳定的领导者：

广播时间 ≪ 选举超时 ≪ 平均故障间隔时间

在这个不等式中，广播时间是服务器向集群中每个服务器并行发送RPC并接收其响应的平均时间；选举超时是第5.2节描述的选举超时；MTBF是单个服务器的平均故障间隔时间。广播时间应该比选举超时小一个数量级，以便领导者能够可靠地发送防止跟随者开始选举所需的心跳消息；鉴于选举超时使用的随机化方法，这个不等式也使分裂投票不太可能。选举超时应该比MTBF小几个数量级，以便系统稳定前进。当领导者崩溃时，系统将不可用大约选举超时的时间；我们希望这只占整体时间的一小部分。

广播时间和MTBF是底层系统的属性，而选举超时是我们必须选择的。Raft的RPC通常需要接收者将信息持久化到稳定存储，因此广播时间可能从0.5ms到20ms不等，取决于存储技术。因此，选举超时可能在10ms到500ms之间。典型的服务器MTBF是几个月或更长，这很容易满足时序要求。

成员变更

实验不涉及

日志压缩

Raft的日志在正常操作中不断增长以纳入更多客户端请求，但在实际系统中，它不能无限制增长。随着日志变长，它占用更多空间，重放时间也更长。如果没有某种机制来丢弃日志中积累的过时信息，这最终会导致可用性问题。

快照（Snapshotting）是最简单的压缩方法。在快照中，整个当前系统状态被写入稳定存储的快照，然后丢弃该点之前的整个日志。快照用于Chubby和ZooKeeper，本节其余部分描述Raft中的快照。

图12展示了Raft中快照的基本思想。每个服务器独立拍摄快照，仅覆盖其日志中已提交的条目。大部分工作包括状态机将其当前状态写入快照。

Raft还在快照中包含少量元数据：**最后包含索引（last included index）**是快照替换的日志中最后条目的索引（状态机应用的最后一个条目），**最后包含任期（last included term）**是该条目的任期。

这些被保留以支持快照后第一个日志条目的AppendEntries一致性检查，因为该条目需要先前的日志索引和任期。一旦服务器完成写入快照，它可以删除到最后包含索引为止的所有日志条目，以及任何先前的快照。

虽然服务器通常独立拍摄快照，但领导者偶尔必须向落后的跟随者发送快照。这发生在领导者已经丢弃了需要发送给跟随者的下一个日志条目时。幸运的是，这种情况在正常操作中不太可能发生：跟上领导者的跟随者已经拥有该条目。然而，异常慢的跟随者或加入集群的新服务器不会有。使这种跟随者最新的方法是领导者通过网络向其发送快照。

领导者使用称为InstallSnapshot的新RPC向落后太多的跟随者发送快照；见图13。当跟随者通过此RPC收到快照时，它必须决定如何处理其现有日志条目。通常快照将包含接收者日志中尚未存在的新信息。在这种情况下，跟随者丢弃其整个日志；它全部被快照取代，可能包含与快照冲突的未提交条目。如果相反，跟随者收到描述其日志前缀的快照（由于重传或错误），则快照覆盖的日志条目被删除，但快照后的条目仍然有效且必须保留。

这种快照方法偏离了Raft的强领导者原则，因为跟随者可以在领导者不知情的情况下拍摄快照。然而，我们认为这种偏离是合理的。虽然有领导者有助于避免达成共识时的冲突决策，但在快照时共识已经达成，因此没有决策冲突。数据仍然只从领导者流向跟随者，只是跟随者现在可以重新组织其数据。

我们考虑了一种替代性的基于领导者的方法，其中只有领导者会创建快照，然后将其发送给每个跟随者。然而，这有两个缺点。首先，向每个跟随者发送快照会浪费网络带宽并减慢快照过程。每个跟随者已经拥有从其本地状态生成自己快照所需的信息，服务器从本地状态生成快照通常比通过网络发送和接收快照便宜得多。其次，领导者的实现会更复杂。例如，领导者需要并行向跟随者发送快照和复制新日志条目，以免阻塞新客户端请求。

还有两个影响快照性能的问题。首先，服务器必须决定何时拍摄快照。如果服务器拍摄快照太频繁，它会浪费磁盘带宽和能源；如果拍摄太少，它可能耗尽存储容量，并增加重启期间重放日志所需的时间。一个简单的策略是在日志达到固定字节大小时拍摄快照。如果此大小设置为明显大于预期快照大小，则快照的磁盘带宽开销将很小。

第二个性能问题是写入快照可能需要大量时间，我们不希望这延迟正常操作。解决方案是使用写时复制（copy-on-write）技术，以便可以在不影响正在写入的快照的情况下接受新更新。例如，用函数式数据结构构建的状态机自然支持这一点。或者，可以使用操作系统的写时复制支持（例如Linux上的fork）来创建整个状态机的内存快照（我们的实现使用这种方法）。

总结：

这里真没看懂，单独问了一下ai：

实验

中言：一开始没好好看论文，了解了一下算法就直接做实验，阻力实在是太大。所以回过头来好好读一下raft的论文，再继续做Part-C的实验

Part-A: 选主

核心内容

这一章要解决的核心问题是：在一个去中心化的系统里，当老大（Leader）挂了，群众（Followers）如何自动选出一个新老大，并且保证只选出一个？

节点角色

  1. Follower（跟随者/群众）：

  • 特点：被动。它只响应来自 Leader 和 Candidate 的请求。

  • 行为：所有节点启动时都是 Follower。如果听不到 Leader 的消息（心跳超时），它就会变成 Candidate。

  1. Candidate（候选人/竞选者）：

  • 特点：主动拉票。

  • 行为：它会给自己投票，并发消息给其他人求票。如果赢得大多数选票，晋升为 Leader。

  1. Leader（领导者）：

  • 特点：绝对权威。处理所有客户端请求。

  • 行为：不断给 Follower 发送心跳（Heartbeat），告诉大家“我还活着，不要造反”。

选举机制

1. 心跳与超时

Raft 的选举完全依靠时间来驱动。这里有两个至关重要的时间概念，请务必区分清楚：

  1. 心跳间隔 (Heartbeat Interval)：
  • 谁发？ Leader。
  • 频率：很高（例如每 50ms - 100ms）。
  • 作用：Leader 不断给所有 Follower/Candidate 发空消息(AppendRpc)，收到的节点需要保持或切换为“Follower”。
  1. 选举超时 (Election Timeout)：
  • 谁用？ Follower。
  • 时长：随机的（例如 150ms - 300ms 之间）。
  • 作用：Follower 进程中持有一个倒计时器，每次收到 Leader 的心跳，倒计时器就清零重置。
  • 触发：如果倒计时归零了，Follower 就会认为 Leader 挂了，立马造反，切换为Candidate触发选举。

选举流程

  1. 正常状态。老leader不断发送心跳（空AppendRpc），Follower和已经变成Candidate的Follower收到立即保持Follower（即使已经有节点投给他票了，也要立即作为普通节点）；
  2. 领导下线。老leader宕机，停止心跳。
  3. 触发超时。Follower切换到Candidate，增加自己任期，给自己头上一票先。
  4. 发起选举。Candidate广播发送RequestVoteRpc，其中说明自己自己的任期和其他一些信息（按下不表先）。
  5. 群众投票。其他节点（包括Candidate），在投票有两个原则“唯任期论”和“先到先得”，都是顾名思义。
  6. 统计结果。Candidate在处理Rpc结果的同时统计得票数，超过半数立即自封Leader，不足则继续尝试，直到成功或收到心跳（已经有其他人上位成功了，变回跟随着）。

实现思路

一些关键的代码实现细节总结

首先考虑这个机制下Raft节点需要维护的属性

1
2
3
4
5
currentTerm int  // 当前任期，任期是raft算法中最重要的属性
votedFor    int  // 投票情况，-1表示还没投
state       State// 当前角色

lastElectionReset time.Time // 上一次重制计时器的时间，用于计算超时发起选举

然后从流程出发，先看看正常运行下需要实现的东西，显然是“心跳机制”
在Raft算法中，一共只有两种Rpc：
Raft 节点之间只通过两种主要的消息（RPC - 远程过程调用）进行沟通：

  1. RequestVote RPC：用于选举。
  • Candidate：“请投我一票！”
  1. AppendEntries RPC：用于日志复制和心跳。
  • Leader：“这是新数据，记下来。” 或者 “我还活着（不带数据）。”

所以我们先实现AppendEntries RPC：

不要忘记RPC属性大写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 根据论文Fig2提示，选择目前需要的参数
type AppendEntriesArgs struct {
	Term    int  // 任期代表发送方的“实力”->任期比别人小，别人是不会理你的
	Leader  int  // 当前的领导
	Entries []any//日志，先不用管

	// prevLogIndex int
	// prevLogTerm  int
	// leaderCommit int
}

type AppendEntriesReply struct {
	Term    int  // 回复自己的最新任期
	Success bool // 接不接受（复制or心跳）
}

func (rf *Raft) AppendEntries(args *AppendEntriesArgs, reply *AppendEntriesReply) {
	rf.mu.Lock()
	defer rf.mu.Unlock()

	// 先判断是否认可，看看实力（任期）
	if args.Term < rf.currentTerm {
		reply.Term = rf.currentTerm
		reply.Success = false
		return
	}

	// 同步任期
	rf.currentTerm = args.Term

	// 重制倒计时
	rf.lastElectionReset = time.Now()

    // 听到圣旨了，老老实实做跟随者
	rf.state = StateFollower

	reply.Term = rf.currentTerm
	reply.Success = true

}

// 调用
func (rf *Raft) sendAppendEntries(server int, args *AppendEntriesArgs, reply *AppendEntriesReply) bool {
	ok := rf.peers[server].Call("Raft.AppendEntries", args, reply)
	return ok
}

然后我们想到什么时候发送心跳Rpc呢？显然是leader的日常工作（循环），找到节点的ticker：
为了看起来清晰一点，就去掉一些并发锁之类的，这当然是非常重要的，这里先不讨论（我自己感觉写的也不咋地）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func (rf *Raft) ticker() {
    // 主循环
	for rf.killed() == false {

		if rf.state == StateLeader {
            // 是领导
			rf.broadcastHeartbeat()
		}else if time.Since(rf.lastElectionReset) > timeout {
            // 不是领导，检查有没有超时（这个timeout是一个合理的随机值，保证快速选出减少平票）
			rf.startElection()
		}

        // 心跳间隔
		time.Sleep(50 * time.Millisecond)
	}
}

然后我们考虑一下怎么广播心跳信号，1.构造一个“当前状态”的AppendRpc，2.目标是除自己外的所有节点，3.并发发送，4.处理回收（看看有没有真领导，即任期更大的节点，有的话直接降级为Follower跟着真领导混）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func (rf *Raft) broadcastHeartbeat() {

    // 在并发环境中，状态瞬息万变，再次确认自己的状态
	if rf.state != StateLeader {
		return
	}

	for peer := range rf.peers {
		if peer == rf.me {
			continue
		}
		go func(server int) {
            // 构造Rpc
			args := &AppendEntriesArgs{
				Term:    rf.currentTerm,
				Leader:  rf.me,
				Entries: nil,
			}
			reply := &AppendEntriesReply{}
			if rf.sendAppendEntries(peer, args, reply) {
                // 处理回复

                // 同理，说不定办完事自己已经是普通节点
                if rf.state != StateLeader {
                    return
                }

                // 退位操作（回到普通Follower）
                // 更新任期、更新状态、更新投票状态、更新计时器
				if reply.Term > rf.currentTerm {
					rf.currentTerm = reply.Term
					rf.state = StateFollower
					rf.votedFor = -1
					rf.lastElectionReset = time.Now()
				}
			}
		}(peer)
	}
}

那么显然这个功能只剩下最重要的“选举”环节了，上文我们已经定义了触发时机（超时），现在我们定义一下这个Rpc：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
type RequestVoteArgs struct {
	Term        int
	CandidateId int
}

type RequestVoteReply struct {
	Term        int
	VoteGranted bool
}

func (rf *Raft) RequestVote(args *RequestVoteArgs, reply *RequestVoteReply) {

    // 1. 检查任期
	if args.Term > rf.currentTerm {
		rf.currentTerm = args.Term
		rf.state = StateFollower
		rf.votedFor = -1
	}

    // 2. 赋值回复的 Term (确保是新的)
    reply.Term = rf.currentTerm

    // 3. 拒绝旧任期
	if args.Term < rf.currentTerm {
		return
	}

    // 4. 投票逻辑：“我还没投过” or “已经给你投过一次了”
	if rf.votedFor == -1 || rf.votedFor == args.CandidateId {
		reply.VoteGranted = true
		rf.votedFor = args.CandidateId
        // 投票也算活跃，重置计时器（这里我不太理解）
		rf.lastElectionReset = time.Now()
	}
}

有了Rpc就可以发起选举了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 发起选举
func (rf *Raft) startElection() {
	// 选举后要做的事：
	// 1. 成为候选人，开一个新任期
	// 2. 给自己投票 + 拉票
	// 3. 统计选票

    // 依旧并发环境检查状态
	if rf.state == StateLeader || time.Since(rf.lastElectionReset) < 10*time.Millisecond {
		return
	}

	// 1. 转换为 Candidate 状态，开启新任期
	rf.state = StateCandidate
	rf.currentTerm++

    // 2. 给自己先来一票
	rf.votedFor = rf.me
	votes := 1

	rf.lastElectionReset = time.Now() // 重置选举计时器

	for peer := range rf.peers {
		if peer == rf.me {
			continue
		}
	    // 2. 并发拉票
		go func(serverID int) {
			args := &RequestVoteArgs{
				Term:        rf.currentTerm,
				CandidateId: rf.me,
			}
			reply := &RequestVoteReply{}
			if rf.sendRequestVote(peer, args, reply) {

                //3. 处理一下选票
				// 依旧响应结束检查当前（任期、状态），这个很重要

                // 任期不足，退化
				if reply.Term > rf.currentTerm {
					rf.state = StateFollower
					rf.currentTerm = reply.Term
					rf.votedFor = -1
					return
				}

				// 可能我发请求时是 Candidate，收到回复时已经是 Follower 了
				if rf.state != StateCandidate || rf.currentTerm != args.Term {
					return
				}

				// 检查投票
				if reply.VoteGranted {
					votes++
					if votes > len(rf.peers)/2 {
                        // 登基！
						rf.state = StateLeader
					}
				}
			}
		}(peer)
	}
}

以上就是Lab3-A的核心内容了，其中的并发加锁解锁处理没有讨论，读者自己折腾吧

Part-B：日志复制

接上一部分，一旦选出了 Leader，它就开始干活了。它的唯一工作就是：接收客户端的指令，把它们记在日志里，然后强迫所有 Follower 也一模一样地记下来。

核心内容

日志

首先引入“日志”这个东西，每一条日志不仅仅是指令，它包含三个字段：

  1. Index (索引)：整数，连续递增（1, 2, 3…）。用来标识日志的位置。

  2. Term (任期)：创建这条日志时，Leader 处于哪个任期。这个字段非常关键，用来检测不一致。

  3. Command (指令)：实际要做的事（如 x=3）。

所以节点所维护的日志表应该长这样：

Text
1
2
3
索引(Index):   1        2        3
任期(Term):    1        1        2
指令(Cmd):   x=1      y=2      x=5

指令的生命周期

指令最初是由客户端发出，由 Leader 接收，再广播与分布式系统中的其他节点同步，最后提交应用。具体来说可以分为以下几个过程：

假设你是 Leader，客户端发来一个请求 set x = 5。

  1. Append (本地追加)：
    Leader 先把这条指令加到自己的 Log 数组末尾。此时，这条日志还是未提交 (Uncommitted) 状态。（还没告诉客户端成功，状态机也没生效）。

  2. Broadcast (广播)：
    Leader 并行给所有 Follower 发送 AppendEntries RPC。（Leader 说：“在位置 3，任期 2，写下 x=5。”）

  3. Replicate (复制)：
    Follower 收到请求，写入自己的 Log，并返回成功（ACK）。（其中需要做一系列的确认，最重要的是日志的一致性验证）

  4. Commit (提交)：
    Leader 收到超过半数 (Quorum) 节点的成功回复。
    Leader 此时将这条日志标记为 Committed。

🎓 Committed (已提交)概念：: 一旦日志被标记为 Committed，Raft 保证它永远不会丢失，即使 Leader 挂了，新 Leader 也一定会有这条日志。简单来说就是这一部分已经实现了同步，新选出来的Leader一定正确持有。

  1. Apply (应用)：
    Leader 把指令交给状态机执行（比如在数据库里把 x 改成 5）。然后返回结果给客户端：“操作成功”。
    Leader 发现“大多数人”都收到了。
    Leader 告诉上层应用：“这条指令生效了！”（通过 applyCh）。
    Leader 告诉 Follower：“刚才那条生效了，你们也可以执行了。”

一致性检查（Consistency Check）

Raft 如何保证成千上万条日志在所有节点上顺序完全一致？
它利用了一个类似拉链的原理：如果你想扣上第 10 颗扣子，第 9 颗必须先扣好。

规则：
如果两个节点的日志在某个索引位置（比如 Index 5）上的任期 (Term) 相同，那么：

  1. 该位置的指令 (Command) 一定相同。

  2. 在这个位置之前的所有日志（1-4）也都完全相同。

为了实现这个，Leader 在发 AppendEntries RPC 时，会携带前一条日志的信息用于一致性检查：

  • prevLogIndex: 我这次要发 Index=5 的日志，那么这个参数就是 4。
  • prevLogTerm: 我 Index=4 那条日志的任期是 2。

处理冲突：回退覆盖机制

如果 Follower 返回 False（拒绝），Leader 怎么办？

  1. Leader 维护每个 Follower 的 nextIndex（下一个要发的日志位置）。
  2. 如果 Follower 拒绝，Leader 将该 Follower 的 nextIndex 减 1。
  3. Leader 重新发送 RPC（带着更旧的一条日志做检查）。
  4. 一直回退，直到找到两者最后一条相同的日志（甚至可能回退到起点）。
  5. 一旦匹配成功，Leader 从那个位置开始，把后面所有的正确日志发过去，覆盖 Follower 的错误数据。

总之就是：一直回退到出错前的位置，一口气覆盖后面所有的错误

实现思路