记录一下 6.5840 2025 Spring Lab3 的过程

实验要求

该实验的地址如下：mit 6.824
实验要求的部分为原文翻译并做适当的修改

在本实验中，需要实现 Raft，这是一种复制状态机协议。

复制服务通过在多个副本服务器上存储其状态（即数据）的完整副本来实现容错。即使某些服务器发生故障（崩溃、网络中断或不稳定），复制功能也能让服务继续运行。挑战在于，故障可能会导致不同副本之间持有的数据副本不一致。

Raft 将客户端请求组织成一个序列（称为日志），并确保所有副本服务器看到相同的日志。每个副本按日志顺序执行客户端请求，并将其应用于服务状态的本地副本。由于所有存活的副本都能看到相同的日志内容，它们都会按相同的顺序执行相同的请求，从而保持一致的服务状态。如果某个服务器故障后稍后恢复，Raft 会负责将其日志更新至最新状态。只要至少大多数（majority）服务器存活且能相互通信，Raft 就会继续运行。如果没有达到大多数，Raft 将停止进度，但一旦大多数服务器能够再次通信，它就会从中断的地方继续。

在代码中，需要遵循 Raft 扩展论文中的设计。需要实现论文中的大部分内容，包括保存持久化状态并在节点故障重启后读取它，不需要实现集群成员变更（论文中的第6节）

笔记内容

以下的内容是对论文
In Search of an Understandable Consensus Algorithm (Extended Version) 的翻译
同时删除了适当的内容，只保留了对于 Raft 算法流程的介绍

引言

什么是一致性算法？

一致性算法允许一组机器作为一个协调的整体工作，从而在部分成员故障时仍能正常民运行。因此它们在构建可靠的大规模软件系统中起着关键作用。

Raft的设计初衷：由于Paxos过于难学，因此作者需要找到一种新的一致性算法，同时要有高可理解性，比Paxos显著容易学习。

Raft相比与现有的一致性算法，有几个新颖点：

强领导者：Raft 使用比其他一致性算法更强的领导形式。例如，日志条目仅从领导者流向其他服务器。这简化了复制日志的管理，并使 Raft 更易于理解。
领导者选举：Raft 使用随机定时器来选举领导者。这在任何一致性算法已要求的“心跳”机制基础上仅增加了少量的机制，同时能简单快速地解决冲突。
成员变更：Raft 变更集群服务器集的新机制使用了“联合一致性”（joint consensus）方法，在转换期间两个不同配置的“大多数”会发生重叠。这允许集群在配置更改期间继续正常运行。

复制状态机

一致性算法通常出现在需要重复状态机的背景下。如果一组拥有相同状态机的服务器出现了少部分故障，那么他们依然能继续运行。

而复制状态机通常使用复制日志的方式来实现。从图1中可以看到，每个服务器存储一个包含一系列命令的日志（log），其状态机（State Machine）按顺序执行这些命令。每个日志包含相同顺序的相同命令，因此每个状态机处理相同的命令序列。由于状态机是确定性的，因此每个状态机都会计算出相同的状态与相同的输出序列。

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

实际系统中的一致性算法有以下的属性：

在所有的 non-Byzantine ¹¹ ai 的翻译是: 非拜占庭条件。它的核心是故障-停止模型。节点要么正常工作，要么彻底停止。一旦运行，则严格遵守算法定义的逻辑，不会欺骗其他的服务器，也不会发送伪造的消息条件下是安全的。
只要任何大多数服务器²² 比如5节点的集群可以容忍任意两台服务器故障可以运行并能相互通信及与客户端通信，它们就是完全功能可用的。
不依赖时序来确保日志的一致性：错误的时钟与极端的延迟在最坏的情况下也只会导致可用性的问题。
在通常情况下，一旦集群的大多数节点对一轮RPC做出了响应，命令即可完成；少数慢速的服务器不会影响系统的整体性能。

Raft 算法

Raft 通过首先选举一个领导者，然后赋予该领导者管理复制日志的全权来实现共识。领导者从客户端接收日志条目，将其复制到其他服务器上，并在安全性允许时告知服务器将日志条目应用到其状态机中。拥有领导者简化了复制日志的管理。领导者可能会失效或与其他服务器迷情工连接，在这种情况下会选举产生新的领导者

Raft 将一致性问题分解为3个相对独立的子问题：

领导者选举：当现有的领导者失效时，必须选出一个新的领导者
日志复制：领导者必须从客户端接收日志条目，并将其跨集群复制，强制其他日志与其自身保持一致
安全性：如果任何服务器已将特定的日志条目应用到其状态机中，则其他服务器不得在相同的日志索引处应用不同的命令。

Raft 基础

一个 Raft 集群有若干的服务器。在任何给定时间，每台服务器都处于三种状态之一：领导者（leader），跟随者（follower）或候选人（candidate）。在正常的运行期间，只有一个领导者，而其他的服务器都是跟随者，都是被动的，它们不会主动发生请求，而只是响应来自领导者与候选人的请求。领导者处理所有客户端请求³³ 如果跟随者收到了客户端的请求，则会将其重定向到领导者。候选人用于选举新的领导者。这三种状态通过右图的方式完成转换。

Raft 将时间划分为任意长度的任期（terms），如右图所示。每个任期都以一次选举开始，其中一个或多个候选人尝试按照 “领导者选举” 所述成为领导者。如果一个候选人赢得了选举，它将在该任期的剩余时间内担任领导者。在某些情况下，选举可能会导致选票瓜分⁴⁴ 即：没有任何一个候选人赢得了超过半数的选票，导致该任期内无法选出领导者。在这种情况下，该任期结束时没有领导者；新的任期（以及新的选举）将很快开始。Raft 确保在给定的任期内最多只有一个领导者。

不同的服务器可能会在不同的时间观察到任期之间的转换，并且在某些情况下，服务器无法观察到某次选举甚至整体任期。为了解决这种问题，在 Raft 中，选择了任期充当了逻辑时钟，他们允许服务器检测过时的信息⁵⁵ 比如，过时的领导者。每台服务器都存储一个当前的任期号，该编号随时间单调递增。每当服务器通信时，都会交换当前的任期；如果一个服务器的当前任期小于另一个服务器，则它会将其当前任期更新为较大的值。如果候选人或领导都发现其任期已经过时，它会立即转回跟随者状态。如果服务器收到带有过时任期号的请求⁶⁶ 这里是指过时的领导者的请求（复制日志与发送心跳等）以及过时候选人的请求（在选举期间拉票等），它会拒绝该请求。

Raft 服务器使用远程过程调用（RPC）进行通信，基本的一致性算法只需要两种类型的RPC：

RequestVote RPC：由候选人在选举期间发起
AppendEntires RPC：由领导者发起，用于复制日志条目并提供一种心跳韩式

领导者选举

Raft 使用心跳机制来触发领导者选举。当服务器启动时，它们最初作为跟随者。

只要服务器从领导者或候选人那里接收到了有效的RPC，它就会保持在跟随者的状态。领导者会定期向所有的跟随者发送心跳⁷⁷ 不含日志条目的 AppendEntires RPC，从而使其一直是领导者。如果跟随者在一段时间内⁸⁸ 这段时间称为选举超时（election timeout）没有收到通信，它就会假定没有可用的领导者，并开始选举以选出新的领导者。

开始选举时，跟随者会增加其当前任期并转换为候选人状态。然后它为自己投票，并向集群中的其他每个服务器并行发出RequestVote RPC。候选人会一直保持这种状态，直到以下三种情况之一发生：

赢得了选举
另一个服务器确立了自己作为领导者的地位
一段时间过去后没有获胜者

以下是对上述三种状态的详细的描述：

如果一个候选人在同一任期内获得了集群中大多数服务器的选票，它就赢得了选举。在给定的任期内，每台服务器按照先来先服务的原则最多为一个候选人投票。多数派规则确保了在特定任期内最多只有一个候选人可以赢得选举。一旦候选人赢得了选举，它就成为了领导者。然后，它会向所有其他服务器发送心跳消息，以确立其权威并降频新的选举。

在等待选举期间，候选人可能会收到来自另一个声称是领导者的服务器的的 AppendEntires RPC。如果该领导者的任期至少与候选人的当前任期人一样大，则候选人承认该领导者的合法性并返回到跟随者的状态。如果 RPC 中的任期小于候选人的当前任期，则候选人拒绝该 RPC 并继续保持候选人状态。

第三种可能的结果是候选人既没有赢得也没有输掉选举：如果许多跟随者同时成为候选人，选票可能会被瓜分，导致没有任何候选人获得多数票。当发生这种情况时，每个候选人都会越野，并通过增加任期和发起另一轮 RequestVote RPC 来开始新的选举。为了防止这种情况再次重复，Raft 使用随机选举超时来减小选票瓜分的情况再次出现。

为了从一开始就防止选票瓜分，选举超时时间是从一个固定的区间（比如 150 ~ 300ms中随机选择的）。这分散了服务器的超时时间，使得在大多数情况下只有一个服务器会超时；它会在任何其他服务器超时之前赢得选举并发送心跳。同样的机制也用于处理选票瓜分。每个候选人在选举开始时重启其随机选举超时，并等待该超时过去后再开始下一次选举；这降低了在新选举中再次发生选票瓜分的可能性。

日志复制

当领导者被选出后，它就开始为客户端请求提供服务。每个客户端请求都包含一个要由复制状态机执行的命令。领导者将该命令作为一个新的条目追加到日志中，然后并行地向其他每个服务器发出 AppendEntries RPC，以复制该条目。当该条目被安全地复制后，领导者将该条目应用到其状态机中，并将执行结果返回给客户端。如果跟随者崩溃或运行缓存，或者网络数据包丢失，领导都会无限期地重试 AppendEntires RPC（甚至在它已经响应客户端后），直到所有跟随者最终存储了所有的日志条目。⁹⁹ 我写代码实现这部分的时候，对这个有些误解，如果是RPC错误，也就是网络错误，会让 sendAppendEntries 返回 false, 而对于其他的情况，比如日志不一致这些，它本身的 sendAppendEntires 函数是会返回 true 的，但是 reply 中的语义会返回 false，这里需要区别一下

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

领导者决定何时将日志条目应用到状态机是安全的。应用到状态机后的条目被称为已提交的（committed）。Raft 保证已提交的条目是持久的，并且最终会被所有可用的状态机执行。一旦创建该条目的领导者将其复制到大多数服务器上，则该日志条目就可以被视为是已提交。这同时也提交了领导者日志中所有等效的条目，包括由前任领导者创建的条目。节介绍了领导者变更后应用此规则时的一些注意点，同时 “安全性” 证明了这种提前定义是安全的。领导者会跟踪它所知道的已提交的最高索引，并在未来的 AppendEntries RPC（包含心跳）中包含该索引，以便其他服务器最终能发现。一旦跟随者得知某个日志条目已提交它就会按日志顺序将该条目应用到其本地状态机中。

Raft维护以下的属性，这些属性共同构成了日志匹配属性

如果不同日志中的两个条目具有相同的索引与任期，则它们存储相同的命令
如果不同日志中的两个条目具有相同的索引与任期，则日志中所有先前的条目也完全相同

第一个属性：领导者在给定的任期内最多创建一个具有给定日志索引的条目，且日志条目永远不会改变其在日志中的位置。¹⁰¹⁰ 注意，这句话的理解是：对于(term, index)的这个组合来说，全局只会存在一个，并且之后的所有操作中其位置不会再被修改了。因此，如果两个日志包含具有相同索引与任期的条目，则它们存储相同的命令。不是指领导者在其任期内只会创建一个日志条目第二个属性：通过 AppendEntires 执行的简单一致性检查来保证。发送 AppendEntires RPC 时，领导者会包含其日志中紧接在新条目之前的条目的索引和任期。如果跟随者在其日志中找不到具有相同索引和任务的条目，它就会拒绝新的条目。一致性检查起到了归纳步的作用：日志的初始空状态满足日志匹配属性，且每当日志扩展时，一致性检查都会保持日志匹配属性。因此，每当 AppendEntires 成功返回时，领导者就知道跟随者的日志直到新条目为止都与自身的日志相同。

正常运行时，领导者和跟随者的日志保持一致，因此 AppendEntires的一致性检查永远不会失败。然而，领导者崩溃可能会使日志变得不一致（比如旧领导者可能尚未完全复制其日志中的所有条目）。这些不一致可能会在一系列领导者和跟随者崩溃中累积。

如右图所示，跟随者的日志可能与新领导者的日志不同的几种方式。跟随者可能会丢失领导者上存在的条目，它可能会拥有领导者上不存在的额外条目，或者两者兼而有之。日志中缺失和多余的条目可能会跨越多个任期。

在 Raft 中，领导者通过强制让跟随者复制自己的日志来处理不一致。这意味着跟随者日志中冲突条目将被领导者日志中的条目覆盖。“安全性-选举的限制” 节将介绍这种操作结合另一项限制时，是安全的。

为了让跟随者的日志与自己的日志保持一致，领导者需要找到两个日志达到一致的最新日志条目，删除跟随者日志中该点之后的所有条目，并将该点之后的所有领导者条目发送给跟随者。这些操作都是为了响应 AppendEntries RPC 执行的一致性检查而发生的。领导者为每个跟随者维护一个 nextIndex，即领导者将发送给该跟随者的下一个日志条目的索引。当领导者刚掌权时，它会将所有 nextIndex 值初始化为其日志中最后一个索引之后的索引（即 figure 7 中的 11）。如果跟随者的日志与领导者的不一致，AppendEntires 一致性检查将在下一次 RPC 中失败。在被拒绝后，领导者会减小 nextIndex 并重试 AppendEntires，直到 nextIndex 达到领导者与跟随者日志的匹配的点。在这种情况下，AppendEntires将成功，从而删除跟随者日志中任何冲突条目，并追加领导者日志中的条目（如果存在）。一旦 AppendEntires 成功，跟随者的日志就与领导者的保持了一致，并在该任期的剩余时间下保持这种状态。

论文在这里提到了一种优化的方案¹¹¹¹ 在拒绝 AppendEntries 请求时，跟随者可以包含冲突条目的任期以及它为该任期存储的第一个索引。利用这些信息，领导者可以减小 nextIndex 以避开该任期内的所有冲突条目；这样每个包含冲突条目的任期只需要一个 AppendEntries RPC，而不是每个条目一个 RPC。，从而减少被拒绝的 AppendEntries RPC 的数量。但是论文也指出：在实践中，这种故障发生频率较低，而且不太可能出现许多不一致的条目。

通过这种机制，领导者在掌权时不需要采取任何特殊行动就可以恢复日志一致性。它只需要开始正常运行，日志就会在响应 AppendEntires 一致性检查失败时自动趋于一致。领导者永远不会覆盖或删除自己日志中的条目，这也就是领导者的只增属性（Leader APpend-Only Property）

这种日志复制机制展现了理想的共识属性：只要集群中大多数服务器正常运行，Raft 就可以接收、复制并应用新的日志条目；在正常情况下，新条目可以通过一轮发往集群多数派的 RPC 进行复制；且单个缓慢的跟随者不会影响整体性能。

安全性

前面的章节描述了 Raft 如何选举领导者和复制日志条目。然而，到目前谈恋爱止描述机制还不足以确保每个状态机以相同的顺序执行完全相同的命令¹²¹² 例如，当领导者提交多个日志条目时，某个跟随者可能不可用，随后它可能被选为领导者并用新条目覆盖这些条目；结果，不同的状态机可能会执行不同的命令序列。。

因此，本节需要对想要选举成为领导者的服务器添加一项限制。该限制可以确保任何给定任期的领导者都包含之前任期中所有已提交的条目（领导者完备性属性 Leader Completeness Property）。

安全性-选举的限制

在任何基于领导者的一致性算法中，领导者最终都必须存储所有已提交的日志条目。Raft 使用了一种更简单的方法，来保证新领导者当选的时候，之前所有已提交的条目都存在于该领导者上。因此日志条目只从领导者流向跟随者，且领导者从不覆盖其日志中已有的条目。

Raft 使用投票过程来防止候选人赢得选举，除非其日志包含所有已提交的条目。候选人必须联系集群的多数派才能当选，这意味着每个已提交的条目必须至少存在于这些服务器中的一个。如果候选人的日志至少与该多数派中任何其他日志一样“新”，那么它将持有所有已提交的条目。而RequestVote RPC实现了这一限制：RPC 包含有关候选人日志的信息，如果投票者自己的日志比候选人的日志更“新”，则投票者会拒绝投票。

Raft 通过比较日志中最后一个条目的索引和任期来确定两个日志中哪个更“新”。如果日志的最后条目具有不同的任期，则任期号较大的日志更“新”。如果日志以相同的任期结束，则较长的日志更“新”。

安全性-提交之前任期的条目

领导者一旦发现当前任期的某个条目存储在大多数服务器上，就会认为该条目已提交。如果领导者在提交某个条目之前崩溃，未来的领导者将尝试完成该条目的复制。然而，领导者不能在之前任期的条目存储在大多数服务器上时，就立即得到该条目已提交的结论。因为可能会出现右图的情况。此时旧的日志条目存储在了大多数服务器上，但是依然可能会被未来的领导者覆盖。

为了消除图示问题，Raft 永远不会通过计算副本数来提交之前任期的日志条目。只有领导者当前任期的日志条目通过计算副本数来提交；一旦当前任期的条目以这种方式被提交，那么由于日志匹配属性，所有靠前的条目也会被间接提交。

Raft 通过引入任期号来解决这个问题，但这也增加了额外的复杂性。但是相比于其他的一致性算法，Raft对于日志条目的推理更加容易，因为日志条目在不同服务器间复制时始终保持其原始的任期号，不会被重新编号。

这种机制之所以有效，是因为选举限制确保了：拥有最新提交条目的节点，才能在未来的选举中获得多数票。对于那些没有得到最新的提交的条目的节点，它无法得到多数选票¹³¹³ 什么是提交的？即：大多数节点都接收到的条目，而成为候选人要求得到大多数的选票。而如果跟随者发现候选人的条目不是最新的，则不会同意其成为领导者。

安全性-安全性认证

这里就不详细写了，最后的结论是：

所有任期大于T的领导者必须包含任期T中所有已提交的条目
日志匹配属性保证了未来的领导者也将包含被间接提交的条目

跟随者和候选人崩溃

在此之前，一直讨论的是领导者的故障。而跟随者和候选人的处理比领导者要简单得多，且处理方式相同。如果跟随者或候选人，那么未来发给它的 RequestVote 和 AppendEntires RPC 将失败。Raft 通过无限期重试来处理这些失败；如果崩溃的服务器重启，RPC将成功完成。如果服务器在完成RPC后但在响应前崩溃，它在重启后将再次收到相同的RPC。Raft RPC是幂等的¹⁴¹⁴ 比如如果跟随者收到了一个 AppendEntries 请求，其中包含已存在于其日志中的日志条目，它会忽略新请求中的这些条目，因此这样不会出现问题。

时间与可用性

Raft 的特点是安全性不可以依赖于时间：系统绝不能仅仅因为某些事件发生的比预期快或慢就产生错误的结果。但是可用性¹⁵¹⁵ 系统及时响应客户端的能力必须取决于时间。如果消息交换花费的时间筐服务器崩溃之间的典型间隔时间，候选人将无法保持足够长的在线时间来离得选举；没有稳定的领导者，Raft就无法取得进展。

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

broadcastTime 是服务器并行向集群中每台服务器发送RPC并接收响应所需的平均时间
electionTimeout 是选举超时时间
MTBF 是单台服务器两次故障之间的平均时间

同时，广播时间应该比选举超时小一个数量级，同时选举超时应该比MTBF小几个数量级。广播时间与MTBF是底层系统的属性，而选举超时是我们的必须选择的。一般来说，广播时间在0.5ms到20ms之间，所以选举超时选择10ms到500ms之间就行。典型的服务器MTBF是几个月或更长，这很容易满足时间的要求。

集群成员变更

实验不要求实现该功能，所以这里我也不做实现了

日志压缩

Raft的日志在正常运行期间会随着包含更多客户端请求而增长，但是在实际的系统中，日志不能无限制的增长。

有一种压缩最简单的办法：快照。在快照机制中，整个当前的系统状态被写入到稳定存储上的快照，然后到该点为止的所有日志都会被丢弃。

也可以采用增量压缩的方法，比如日志清理（Log cleaning）与日志结构合并树（LSM tree）。这些方法每次只处理一小部分的数据，因此它们可以随时间更均匀地分散压缩负载。它们首先选择一个积累了许多已删除和已覆盖对象的区域，然后将该区域中活跃对象重写得更紧凑，并释放该区域。与快照相比，这需要大量的额外机制与复杂性，而快照通过始终处理整个数据集来简化问题。虽然日志清理需要对 Raft 进行修改，但状态机可以使用与快照相同的接口来实现 LSM 树。

右图展示了Raft快照的基本思想。每个服务器独立生成快照，仅涵盖其日志中已提交的条目。大部分工作由状态机将其当前状态写入快照组成。Raft 还在快照中包含少量的元数据：最后包含的索引（last included index）是快照所替换的日志中最后一个条目的索引（状态机最后应用的条目），而最后包含的任期（last included term）是该条目的任期。保留这些信息是为了支持快照后第一个日志条目的 AppendEntires 一致性检查，因为该条目需要前一个日志条目的索引与任期。为了支持集群成员变更，快照还包含截至最后包含索引时的最新集群配置。一旦服务器完成快照编写，它就可以删除最后包含索引之前的所有日志条目，以及任何之前的快照。

如右图所示，领导者使用一种名为 InstallSnapshot 的新RPC向落后太多的跟随者发送快照。可以从右图中看到其具体的定义。当跟随者通过该RPC接收到快照时，它必须决定如何处理其现有的日志条目。通常，快照会包含接收者日志中尚未包含的新信息。在这种情况下，跟随者需要丢弃整个日志；这些日志都被快照取代，可能存在与快照冲突的未提交条目。如果跟随者收到的快照描述的是其日志的前缀（由于重传或误发），那么快照涵盖条目会被删除，但快照之后的条目仍然有效，必须保留。

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

作者也考虑过另一种基于领导者的方法：只有领导者创建快照，然后将其发送给每个跟随者。但是这有两个缺点：

向每个跟随者发送快照会浪费网络带宽并减慢快照过程。每个跟随者都已经拥有生成自己快照所需的信息，而且服务器从其本地状态生成快照通常比通过网络发送和接收快照要廉价得多。
领导者的实现会更加复杂。

而且还有两个影响快照性能的问题：

服务器必须决定何时进行快照。如果服务器快照过于频繁，会浪费磁盘带宽和能量；如果快照频率太低，则面临耗尽存储容量的风险，并增加了重启期间回放日志所需的时间。
写入快照可能需要大量时间。其解决方案是写时复制技术，以便在不影响正在写入的快照的情况下接受新的更新。

总体的流程

以上就是Raft算法的所有的内容，以下是论文中的图2，也就是总览性的图

我的实现

任务A

读起来还是很容易的，但是实现起代码来还是会有很多的困难的，可以发现我之前的理解还是不够的深。

比如这个选举超时时间，原来就是心跳的超时时间，这个是随机的。我一开始以为心跳超时时间是固定的，然后选举超时的时间是随机的。所以当时还想到在正式选举前，先使用随机的Sleep来来防止选举瓜分的情况。后来pass测试用例后，问了一下ai，才知道==。

经过我的优化，效果还是蛮明显的（而且还比lab中给出的示例的效果更好😎）：

这个是我一开始的实现的性能：

Test (3A): initial election (reliable network)...
  ... Passed --  time  3.5s #peers 3 #RPCs    60 #Ops    0
Test (3A): election after network failure (reliable network)...
  ... Passed --  time  5.5s #peers 3 #RPCs   138 #Ops    0
Test (3A): multiple elections (reliable network)...
  ... Passed --  time  5.5s #peers 50 #RPCs  3430 #Ops    0
PASS
ok      6.5840/raft1    14.571s

这个是优化后的：

Test (3A): initial election (reliable network)...
  ... Passed --  time  3.1s #peers 3 #RPCs    46 #Ops    0
Test (3A): election after network failure (reliable network)...
  ... Passed --  time  4.5s #peers 3 #RPCs    96 #Ops    0
Test (3A): multiple elections (reliable network)...
  ... Passed --  time  5.3s #peers 50 #RPCs  3038 #Ops    0
PASS
ok      6.5840/raft1    12.939s

不论是时间，还是总的RPC的使用数量都有比较明显的下降。

现在还没写完整个实验，剩下的等我写完实验以后再写

任务B

经过我3天的奋战，终于把任务B写出来了。这个任务看起来很简单，逻辑看起来也很简单，但是花了我蛮长时间的。我感觉一个最大的问题就是有些细节不太能直接想出来，得一直看运行的时序图，找到代码中的小的逻辑bug，还有并发的bug¹⁶¹⁶ 还是rust在并发方面的心智负担比较低，rust在编译期就能杜绝各种数据竞争什么的，心智负担特别低。写这个go又让我想起来之前写cpp时的痛苦经历QAQ。所以我期间也在一直看论文，看笔记，最后实在有些不确定的部分，我就使用ai来分析了一下。

这个任务B主要的内容就是实现日志的复制。日志的复现主要有两个个任务：

实现选举限制，即：简单一致性 “安全性-选举的限制”
根据日志复制中的相关的逻辑，完善两个RPC的发送与处理逻辑
实现Start函数。需要注意这个函数的特性：需要立即返回的，而不是像论文中一样要阻塞等到日志条目被提交才返回结果。我一开始没注意到这个问题，导致卡了很久QAQ

这里还有一个需要注意的：当服务器判断出来可以提交log时，需要通过 applyCh 导出。而这个 applyCh 在Make中传入了，但是默认没有被添加到结构体中！！！这个也导致我卡了很久，我让ai给我思路的时候才发现有这个东西。我说我的思路和代码基础都对的，但是为什么我的测试一个都没通过(╯‵□′)╯︵┻━┻

经过3天的折磨，最后也是把这个Lab3B写出来了，hard果然非常的hard /_\

最后这个是我的运行结果：

ghost-him@lab ~/6/s/raft1 (master) [1]> go test -run 3B -race
Test (3B): basic agreement (reliable network)...
  ... Passed --  time  0.9s #peers 3 #RPCs    14 #Ops    0
Test (3B): RPC byte count (reliable network)...
  ... Passed --  time  2.0s #peers 3 #RPCs    46 #Ops    0
Test (3B): test progressive failure of followers (reliable network)...
  ... Passed --  time  4.9s #peers 3 #RPCs   108 #Ops    0
Test (3B): test failure of leaders (reliable network)...
  ... Passed --  time  6.8s #peers 3 #RPCs   214 #Ops    0
Test (3B): agreement after follower reconnects (reliable network)...
  ... Passed --  time  4.7s #peers 3 #RPCs    93 #Ops    0
Test (3B): no agreement if too many followers disconnect (reliable network)...
  ... Passed --  time  4.1s #peers 5 #RPCs   172 #Ops    0
Test (3B): concurrent Start()s (reliable network)...
  ... Passed --  time  0.5s #peers 3 #RPCs    14 #Ops    0
Test (3B): rejoin of partitioned leader (reliable network)...
  ... Passed --  time  4.9s #peers 3 #RPCs   148 #Ops    0
Test (3B): leader backs up quickly over incorrect follower logs (reliable network)...
  ... Passed --  time 16.1s #peers 5 #RPCs  2952 #Ops    0
Test (3B): RPC counts aren't too high (reliable network)...
  ... Passed --  time  2.0s #peers 3 #RPCs    52 #Ops    0
PASS
ok      6.5840/raft1    47.983s

除了 Test (3B): leader backs up quickly over incorrect follower logs (reliable network) 这个测试花的时间比较长，其他的速度和RPC数都比官方好一些。这里其实是可以用论文中提到的优化方法的，但是本着代码和人有一个能跑就行的原则，这里就先不做优化了😋

任务C

哎，写文档好麻烦－O－
想到什么就写什么了，不管行文节奏了

任务c要求实现持久化的存储。这里是先通过encoder与decoder将变量变成字节流，然后将字节流做一个保存。这里写的代码中，要注意Encode与Decode与顺序必须是一样的，比如Encode的顺序是A, B, C，那么Decode的顺序也必须是A, B, C。而且如果使用了labgob（还有原生的gob），那么它只能导出以大写字母开头的字段。而且这里也有一个需要注意的点：使用Decode获取保存的数据时，要传入指针。我一开始没传入导致数据读取失败了。

继续往下看，没想到任务C要求优化nextIndex了。本来想着摸鱼呢。不过也能发现，如果不实现这个功能，那么测试的时候会比较的长。所以还是开始实现吧。任务中给出了3个变量：XTerm, XIndex, XLen，其含义分别是：冲突条目的任期，该任期中第一个条目的索引，当前接收者的日志的长度。

这3个变量的处理逻辑如下：对于跟随者，只有两个处理的逻辑：

如果发现领导者的PrevLogIndex在自己的日志中没有，那么就说明自己的日志太短了，那么只需要设置XLen，其他的两个值设置成-1就行¹⁷¹⁷ 这里设置啥都行，我习惯设置成-1，因为正数与0都是有含义的，负数还没有含义
如果发现领导者的PrevLogIndex在自己的日志中存在，但是对应位置的日志不匹配¹⁸¹⁸ 什么叫匹配呢？从论文中可以知道，一个日志可以被(任期，索引)唯一的确定。那么如果索引对了，还是不匹配，那么就只有任期不对这一种情况。那么就需要将XTerm与XIndex设置成跟随者的冲突日志的任期与索引。

跟随者的返回值设置好了，那么该消息返回给领导者，领导者则需要根据这3个值来调整nextIndex值

首先先看一下XTerm是不是等于-1¹⁹¹⁹ 为什么是-1？因为我们在上面自己规定了，等于-1时说明跟随者的日志太短了。如果等于-1，则说明跟随者的日志过于短了，那么短到了多少呢？即，短到了XLen，所以直接让nextIndex = XLen就行。下一次领导者在发送日志时，就会直接发送跟随者所拥有的日志之后的所有的日志。
如果不是-1，说明当前的跟随者中存在指定索引的日志，但是这个日志的任期与领导者的不同。这个时候领导者要分情况讨论
1. 如果跟随者中冲突的日志的任期在领导者中可以找到，则说明在领导者的日志中能够找到任期为 XTerm 的日志，这说明领导者和跟随者虽然在该索引处不匹配，但它们在过去可能拥有过一段共同的任期。在这种情况下，领导者不应该直接跳过整个 XTerm，因为领导者手中可能存有该任期内的一段有效日志。因此，领导者应该将 nextIndex 设置为自己日志中 XTerm 最后一次出现的索引之后的那个索引²⁰²⁰ 其实这里我也想了好长时间，为什么选择最后一次出现的索引之后的索引是正确的。首先，这里如果直接选择 XIndex 是可以完全保持正确性的！只不过会有网络带宽的浪费，因为选择了 XIndex 就等于将冲突日志的任期中所有的日志全都重发了一遍，不管之前的日志是不是有匹配上了的，那这肯定正确啊！简单来说：既然领导者和跟随者都有这个任期（XTerm）的日志，那么领导者最合理的做法就是去尝试匹配自己在这个任期内的“最后一个位置”，看看跟随者是不是也拥有完整的这一段历史。如果两个日志在某个索引上的日志条目拥有相同的任期，那么从头开始到这个索引为止的所有日志条目都是完全相同的。而选择了领导者日志中该 XTerm 最后出现的位置 + 1 就是为了贪婪地保留尽可能多的日志，避免误删跟随者手中已经存在且正确的数据。如果这样贪了一下还是没有匹配上，那么就会再次触发回溯机制，不会影响正确性。而后果也只是多一次网络传输。。
2. 如果跟随者中冲突日志的任期 XTerm 在领导者的日志中找不到，这说明跟随者在 XTerm 任期内的所有日志在领导者看来都是过时的或者处于冲突状态。此时，领导者可以直接跳过跟随者在这个任期内的所有日志，即直接将 nextIndex 设置为跟随者传回来的 XIndex。

在 unreliable 网络下，会存在信息过期的情况，在 reliable 的网络下，则该问题很难被测试出来。不论是投票，还是发送日志复制的请求，都应该有这样的保证：

如果收到的RPC的任期更新，则更新自己的任期。
如果收到的RPC的任期比自己的旧，则忽略该RPC。
只有两个任期是一样的时候，才可以做更进一步的处理。

注意，这里领导者向跟随者发送AppendEntires后，当收到该跟随者的回复时，也应该检查该跟随者所回复的任期是多少，如果该任期已经过期了，则不应该再响应逻辑上的操作，即我上述的第2点。我一开始没有注意到这个问题，导致有的时候能跑通测试，有的时候又跑不通测试

以下是测试结果，非常不错，就是不知道为啥我的RPC数会比官方的多那么多：

ghost-him@DESKTOP-PQRV465 ~/6/s/raft1 (master) [1]> go test -run 3C -v -race
=== RUN   TestPersist13C
Test (3C): basic persistence (reliable network)...
  ... Passed --  time  4.5s #peers 3 #RPCs    72 #Ops    0
--- PASS: TestPersist13C (4.47s)
=== RUN   TestPersist23C
Test (3C): more persistence (reliable network)...
  ... Passed --  time 12.7s #peers 5 #RPCs   350 #Ops    0
--- PASS: TestPersist23C (12.74s)
=== RUN   TestPersist33C
Test (3C): partitioned leader and one follower crash, leader restarts (reliable network)...
  ... Passed --  time  1.8s #peers 3 #RPCs    33 #Ops    0
--- PASS: TestPersist33C (1.80s)
=== RUN   TestFigure83C
Test (3C): Figure 8 (reliable network)...
  ... Passed --  time 36.3s #peers 5 #RPCs   881 #Ops    0
--- PASS: TestFigure83C (36.31s)
=== RUN   TestUnreliableAgree3C
Test (3C): unreliable agreement (unreliable network)...
  ... Passed --  time  1.6s #peers 5 #RPCs  1036 #Ops    0
--- PASS: TestUnreliableAgree3C (1.59s)
=== RUN   TestFigure8Unreliable3C
Test (3C): Figure 8 (unreliable) (unreliable network)...
  ... Passed --  time 41.9s #peers 5 #RPCs 11464 #Ops    0
--- PASS: TestFigure8Unreliable3C (41.91s)
=== RUN   TestReliableChurn3C
Test (3C): churn (reliable network)...
  ... Passed --  time 16.3s #peers 5 #RPCs  7228 #Ops    0
--- PASS: TestReliableChurn3C (16.27s)
=== RUN   TestUnreliableChurn3C
Test (3C): unreliable churn (unreliable network)...
  ... Passed --  time 16.5s #peers 5 #RPCs  4734 #Ops    0
--- PASS: TestUnreliableChurn3C (16.49s)
PASS
ok      6.5840/raft1    132.705s

任务D

任务D要求实现日志压缩。