1.Some Questions（lec1）

1.1 Leader相关的问题

用Raft集群的方式进行数据分片

当client过多时，显然一个leader是无法同时处理过多请求的，这时我们可以将数据分片，每一个分片都用一个Raft集群存储，这样不同的分片都会各自拥有一个leader，可以做到负载均衡。（这是Lab4要做的内容）
日志的term和log index可以唯一的确定一条日志

因为一个term内只会有一个领导人，因此log的term和log index可以唯一的确定一条日志，一个leader不会分别发送两条term和log index相同但是command不同的命令。
选举是lab2A的内容

这里面要尤其关注选举超时的现象。同时，要严格遵守论文中图2的内容去设计算法，不要忽略任何一条，否则可能会导致实验失败，但是图2的内容并不是完全完整的，还有一些遗漏的细节需要我们在做lab的过程中慢慢地发现。

1.2 Raft中的日志分叉问题

场景：下图是一些服务器，原来的leader突然间崩溃了，接下来会开始一次新的选举：

上图中有可能成为leader的是a、c、d三个服务器。
假设所有的机器都没有崩溃，目前机器d的日志是最新的，当a发起一次选举的时候，它会增加自己的任期号到7，a无法得到c和d的选票，因为c和d的日志都比a要新。
所以论文中提到了，针对以往任期的log，我们不能简单地用Majority Servers标准来判断日志是否已经提交。

如果c和d没有崩溃，a有可能成为leader吗？

可以注意到d曾经成为过term7的leader，所以可以肯定已经有大多数节点的term为7了。如果a没收到请求，那么a会增加任期到7开始选举，但是大多数节点已经在term7内投过票了，不可能存在2次投票，所以a不可能成为任期7的leader。
那么a只能开始term8的选举，在term8中它是有可能成为leader的，当然这是假定别的服务器的term是没有变化的，实际上他们会不停地变化，因此上面的图是不全的，只是给我们一个场景让我们去头脑风暴。

1.3 client的duplicate requests问题

场景：当leader执行完client A的请求后，它崩溃了，此时client A无法接收到回复，那么在一定的时间过后，client会重复发送相同的请求，所以client端必须具备repeat的功能。

方案：而kv 服务器会即时的保存这个response，当新leader收到相同的请求后，他发现之前的leader执行过这个请求，那么就直接将这个response返回即可，而不必重复的执行相同的命令。

kv服务器有一个duplicate detection table，这个DS用来检测client发送来的请求是否已经被执行过了。

1.4 Raft的优化手段

Raft的强领导人特性注定了有很多优化它做不了，但是batch processing是一个十分合适的优化，但是lab中并没有要求我们做这个，这样也不一定会带来性能上的提升，论文中也有专门的文字说明了优化这方面的问题。

2. Some Questions（lec2）

2.1 日志新旧&&任期大小

在Raft协议中，当leader发现有任期比自己更大的server时，他会自动回退到follower状态。这个过程中，只比较的是任期的大小，而不涉及日志的新旧。

然后，在选举过程中，candidate会向其他节点征求选票。在这个过程中，除了比较任期的大小，还会比较日志的新旧。这是为了确保新的leader的日志至少和大多数节点的日志一样新。具体来说，如果candidate的日志比其他节点的日志旧，那么它就不会得到那个节点的选票。

这样做的目的是为了保证系统的一致性。只有当一个节点的日志足够新，它才有可能成为leader。这样可以防止已经被提交的日志被未提交的日志覆盖，从而保证了系统的一致性。这是Raft协议的一个重要特性，也是它能够保证分布式系统一致性的关键所在。

2.2 Log Catch Up机制(lab2内容)

leader会有两个状态变量用来记录followers的日志状态：

NextIndex：乐观变量。代表下一个要发送给follower的日志条目的索引，当leader诞生时，初始化该值为当前leader的最新条目的下一个条目的索引（它乐观的认为别的follower都有和自己一样的条目，都跟上自己了）。

MatchIndex：悲观变量。代表已经复制到follower的最高日志条目索引，当leader诞生时，初始化该值为0。该值会随着收到AppendEntries RPC的回复而不断地更新。

日志的确认可以在平常发送心跳信息时确认，或者在追加日志之前的一致性检查中来确认。

2.3 日志擦除机制

上图是一个可能会发生日志擦除的场景，其中a,b,c三个场景都是连续发生的，而c接下来可能会有d和e两个场景，d是发生日志擦除的场景，e则是S1继续同步自己的日志的场景。

在C中，s1不可能赢得term3的选举，因为term3已经有一个领导人了（虽然该领导人已经崩溃了），所以他会成为term4的领导人，在把日志2复制到S3后，S1接下来的行为决定了会出现场景d还是场景e：

场景d：S1复制完日志2之后又崩溃了，假设S5此时很久没有收到消息了，它仍然在term3，之后它增加任期到term4，开始选举，但是他发现term4已经有了一个领导人（大部分servers已经投过票了），但是它不死心，再次新增到term5，开始选举，这次S5成为了term5的领导人，所以他会擦除S1,S2,S3的日志。

场景e：S1没有崩溃，它接下来也顺利的把term4的日志复制到了大多数，之后不管S1是否崩溃，S5都不可能赢得选举，因为当他碰到比自己任期大的服务器时，他会立即回退到follower，不可能开始下一次选举，因此接下来的leader只能在S1,S2,S3中诞生。

但是注意，无论怎样擦除，对于Raft集群中的任何server而言，都只能擦除未提交的日志，已经提交的日志是不能被擦除的。

2.4 log catch up quickly(日志快速追赶)（lab2c必做内容）

可能会出现一个follower的日志落后某个leader很多的情况：如新加入集群的节点；一个节点的崩溃时间很长，直到过了几个term之后它才回复。

如果按照原来NextIndex--的方案依次递减，直到碰到匹配的，对于这种落后太多的情况实在是太浪费资源了，论文中提到了一种直接回退一个term的方案，这个方案并没有详细描述，但是需要我们在lab中实现它，教授提供了一个思路：

落后很多的follower在拒绝leader的AppendEntry操作时，会包含更多的信息，这些信息将有助于leader更快的后退，而不是逐个后退。
follower的回复包含的信息可能有：follower的日志中与leader冲突的term、 follower中该term的第一个日志条目的索引。

如上图所示，S1落后S2很多，S2在term7当选为leader，S2向S1追加日志(PreviousIndex=5,PreviousTerm=6)，因为leader刚开始总是乐观的认为所有的follower的进度是跟得上自己的。

S1收到后，发现Prev的任期与自己不符合，自己在index=5的时候任期是5，于是将返回信息中的Xterm(冲突任期)设置为5，之后查看自己的日志，确定第一个任期为5的日志的索引是2，之后将Xindex设置为2，返回给leader。

leader收到消息后，将S1的previousTerm设置为4，previousIndex=1，之后会打包发送从index2开始的所有日志[6,6,6,6]给S1，使得S1与自己的日志完全同步。

2.4.1 日志量过大导致网络带宽过载？

一般而言，follower都不会距离leader有太远的日志差距（除了新加入的节点且启动的很慢）；但是针对落后太多的，我们可以用快照的方式让节点进行快速追赶，而不是发送全部日志。

所以结合Snapshot机制和follower一般不会落后太多的情况，可以总结出一般不会出现网络带宽过载的情况。

3. persistence：Reboot

当一个故障节点重启之后，我们不希望他在加入后只通过重放日志来追赶，因为很明显在某些情况下需要重放大量的日志，这毫无效率。因此我们希望可以把某些必要的状态持久化到稳定存储上，当节点重启之后，通过从稳定存储上读取这些state可以实现快速的恢复。

论文中提出：currentTerm、votedFor、log[]，这三种状态是有必要被持久化到磁盘上的，这些可以帮助故障节点快速的融入到Raft集群中。

voteFor确保了Raft每个任期中只会有一个leader被选举出来，因此投过票的server必须记住他；持久化currentTerm确保了任期是单调递增的，还可以识别过期的leader和candidate。重点讨论为什么log需要持久化。

但是写入到稳定磁盘的操作十分的耗时，因此这可能会成为性能的瓶颈。

3.1 why log must be persisted on stable storage

Raft 算法中的日志条目必须持久化到稳定存储中，这是因为日志条目包含了用于复制状态机的命令，而状态机的状态是需要持久化的。如果不把日志条目持久化，那么在节点重启或者崩溃后，这些日志条目可能会丢失，导致状态机无法恢复到正确的状态。

此外，日志条目的持久化也是保证 Raft 算法安全性的关键。Raft 算法要求一个领导者必须保存所有已经提交的日志条目，直到这些日志条目被应用到状态机。如果一个领导者崩溃，那么在它重新选举为领导者之前，它必须有所有已经提交的日志条目。如果这些日志条目没有被持久化，那么在领导者崩溃后，这些已经提交的日志条目可能会丢失，这将违反 Raft 的安全性要求。

因此，如果日志条目没有被持久化到稳定存储，可能会导致状态机状态的丢失和 Raft 算法的安全性问题。

总结来说，如果不持久化日志到稳定存储上，那么在系统中是会丢失已经提交的日志条目的。

3.1.1 Example: if log is not persisted on stable storage.

假设我们有一个分布式数据库，它使用 Raft 算法来保持数据的一致性。在这个数据库中，有三个节点，节点 A、节点 B 和节点 C。我们现在有一个操作，它是将一个银行账户的余额从 1000 美元增加到 1500 美元。

在操作开始时，节点 A 是领导者，它将这个操作作为一个日志条目添加到它的日志中，并复制这个日志条目到其他的跟随者节点 B 和 C。然后，节点 A 和节点 B 都因为一些原因崩溃了，而他们的日志没有持久化到稳定存储。

当节点 A 和节点 B 恢复后，他们的日志都是空的，因为他们没有持久化日志。然后，节点 B 成为新的领导者，它开始接收新的操作。其中有一个操作是将同一个银行账户的余额从 1000 美元减少到 500 美元。这个操作被添加到日志中并被提交。

此时，我们看到一个问题。在节点 C 中，它认为银行账户的余额应该是 1500 美元，因为它有一个未提交的日志条目是将余额从 1000 美元增加到 1500 美元。但在节点 A 和节点 B 中，他们认为银行账户的余额应该是 500 美元，因为他们有一个已经提交的日志条目是将余额从 1000 美元减少到 500 美元。这就导致了数据的不一致。

这就是如果 Raft 不将日志持久化到稳定存储，可能会发生的问题。在一个分布式系统中，数据的一致性是非常重要的，任何导致数据不一致的问题都可能会严重影响系统的可用性和正确性。

3.2 why currentTerm need to be persisted on stable storage?

这确保了currentTerm是单调递增的；此外，识别stale leader或stale candidate，都需要每个follower精确地知道自己的currentTerm。

3.3 when persist these states

每当voteFor、currentTerm、log[]之中有任意一个发生变化时，要即时的将其写入到稳定存储中，但是这样似乎要付出不小的代价。voteFor与currentTerm一般是同时变化的；

论文中的5.3节中有这么一段话：领导人来决定什么时候把日志条目应用到状态机中是安全的；这种日志条目被称为**已提交**。Raft 算法保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行。在领导人将创建的日志条目复制到大多数的服务器上的时候，日志条目就会被提交（例如在图 6 中的条目 7）。同时，领导人的日志中之前的所有日志条目也都会被提交，包括由其他领导人创建的条目。

所以，已经提交的log一定是已经被持久化到稳定存储的。教授的解释是，当follower收到一组日志时，他会首先将log持久化到本地存储中，之后才会回复leader，这样确保了follower不会丢失已经提交的日志。

3.4 Why 3 states must be persisted

在Raft协议中，currentTerm、votedFor和log这三个状态需要持久化，主要是为了保证系统在发生故障重启后，能够从中断的位置恢复服务。具体来说：

currentTerm：这是服务器最近一次知道的任期（term），用于防止过时的信息干扰当前的信息。如果一个服务器的任期落后于其他服务器，那么它的请求就会被拒绝。因此，currentTerm需要持久化，以防止服务器在重启后丢失这个信息。
votedFor：在一个给定的任期内，每个服务器最多只能投票一次。votedFor记录了服务器在当前任期内投票给了哪个候选者。这个信息需要持久化，以防止服务器在重启后忘记它已经投过票，从而违反了“一个任期内最多只能投一票”的规则。
log：这是服务器存储的日志条目集合，其中包含了用于状态机的命令，以及命令被记录时的任期。日志需要持久化，因为它们包含了已经被服务器接受但可能还没有被应用到状态机的命令。

总的来说，这三个状态的持久化是为了保证Raft协议的安全性和一致性。在服务器重启后，这些持久化的状态信息将被用来恢复服务器的状态，使其可以继续正常地参与Raft协议的运行。这是分布式系统中非常重要的一部分，因为在这种环境下，服务器可能会随时出现故障和重启。所以，每次更改这些状态时，它们几乎都必须落盘，因此每次添加 Log 条目或更改 currentTerm、votedFor时，安全的做法肯定是持久化这些信息。这样可以确保即使在面临节点故障或网络问题等分布式系统常见问题时，Raft协议仍能保证系统状态的一致性。

3.5 落盘日志未必是已经提交的

在Raft协议中，持久化到磁盘上的日志包括已经提交的和未提交的日志条目。这是因为Raft的日志复制过程是异步的，Leader节点在接收到客户端的请求后，会先将请求作为新的日志条目添加到自己的日志中，并立即持久化，然后再异步地将这个日志条目复制到其他的Follower节点。

只有当这个日志条目被复制到大多数的节点上时，它才会被视为已经提交。因此，持久化到磁盘上的日志中，可能包含了一些尚未被复制到大多数节点，因此尚未提交的日志条目。

此外，对于已经提交并且应用到状态机的日志条目，其中间状态以及中间操作都不再需要，可以对这一部分日志进行压缩。这就意味着，持久化到磁盘上的日志并不一定都是已经提交的，也可能包含了一些未提交的日志条目。

总的来说，Raft协议通过持久化所有的日志条目（无论是否已经提交），以及在必要时进行日志压缩，来确保在面临节点故障或网络问题等分布式系统常见问题时，仍能保证系统状态的一致性。这是分布式系统中非常重要的一部分，因为在这种环境下，服务器可能会随时出现故障和重启。所以，每次更改这些状态时，它们几乎都必须落盘，因此每次添加 Log 条目或更改 currentTerm、votedFor时，安全的做法肯定是持久化这些信息。这样可以确保即使在面临节点故障或网络问题等分布式系统常见问题时，Raft协议仍能保证系统状态的一致性。

4. Service Recovery(snap shot and log compaction-lab2d)

恢复服务的两种方法，比较直接的方法就是读取所有的log，通过不停地重放来恢复状态；第二种就是我们提到的快照，定期建立快照（由服务层创建），服务层创建完毕后，可以通知Raft层清理不必要的日志和快照。

建立快照的方式需要raft库与上层服务层进行协作，service必须在制作完快照后，告诉对应的server最新快照的log_index，因此raft层可以删除[begin index,log_index]之间的所有日志内容，因为快照已经代表了应用那部分日志之后所得到的一个最终状态。（一般而言begin_index都是0，因为快照是某个时刻的完整状态，因此其实与begin_index的关系不大，主要是与Log_index有很大关系。）

4.1 SnapShot

在Raft协议中，快照是由服务层创建的。这是因为快照需要包含服务状态机的当前状态，这些信息只能由服务层提供。

创建快照后，服务层需要向Raft层发送一些信息。主要的信息是快照对应的日志条目的索引和term。这些信息对Raft层来说是重要的，因为它们可以让Raft层知道哪些日志条目已经被快照包含，从而可以安全地删除这些日志条目。在Raft论文中，这个过程被称为日志压缩。

另外，当服务层创建一个新的快照时，它还可能需要将旧的快照删除，以释放存储空间。这个过程可能也需要通知Raft层，因为Raft层需要知道哪个快照是最新的，以便在需要时使用它。

总的来说，服务层和Raft层在创建和管理快照时需要紧密地协作。服务层负责创建快照并通知Raft层，而Raft层负责根据这些信息来更新和管理它的日志。

4.2 Raft layer and Service Layer

Raft层主要负责日志的稳定存储和复制，以及领导者选举和日志的提交等。它并不知道日志内容的具体含义，也不知道具体服务的逻辑。

在Raft协议中，日志条目通常只包含两部分信息：一个是命令，一个是该命令对应的term。命令是一个由服务层生成的，用于修改服务状态机状态的指令。这个命令的具体内容对Raft层来说是不可见的，它只知道这是一个需要被复制和提交的日志条目。

同样，Raft层也不知道服务层的具体逻辑。它只知道当一个日志条目被提交时，需要调用服务层的接口来应用这个日志条目。至于这个日志条目如何被应用，以及应用后会产生什么样的效果，这些都是由服务层来决定的。

这种分层的设计使得Raft协议具有很高的通用性。通过将复杂的分布式一致性问题抽象为日志复制问题，Raft可以被用于实现各种不同的分布式服务。

4.3 什么情况下Raft层需要与服务层进行通信

在 Raft 协议中，Raft 层需要在以下几种情况下与服务层进行通信：

应用提交的日志条目：当一个日志条目被复制到大多数节点并被领导者提交后，Raft 层需要通知服务层应用这个日志条目。服务层会将日志条目中的命令应用到它的状态机，并可能会根据命令的执行结果更新其状态。
创建快照：当日志变得过大时，Raft 层可能会请求服务层创建一个快照。服务层会创建一个包含当前状态机状态的快照，并将快照对应的日志条目的索引和 term 返回给 Raft 层。
加载快照：当一个节点需要加载一个快照时（例如在启动时或在接收到一个包含快照的 AppendEntries RPC 时），Raft 层会将快照传递给服务层。服务层会加载这个快照，从而将其状态机恢复到快照对应的状态。

以上是 Raft 层与服务层的主要交互。需要注意的是，具体的交互方式可能会根据不同的 Raft 实现而略有不同。

4.4 SnapShot的例子

在Raft协议中，如果有新节点加入，领导者会通过发送AppendEntries RPC来将其日志复制到新节点。如果领导者已经为某个日志范围[i,m]创建了快照，那么新节点就需要首先加载这个快照，然后再从领导者那里获取[m+1,n]范围内的日志条目。（日志的范围是[0,n]，0 < i < m < n）

具体来说，这个过程可能会包括以下几个步骤：

领导者发现新节点的日志落后于自己的快照，于是将快照发送给新节点。这通常是通过特殊的RPC（例如InstallSnapshot RPC）来完成的。
新节点接收到快照后，会将其加载到自己的状态机中，从而将状态机的状态更新到快照对应的状态。
新节点加载完快照后，会将快照对应的日志索引和term发送给领导者，以此告诉领导者自己已经加载完快照并且准备好接收更多的日志条目。
领导者接收到新节点的响应后，会开始发送[m+1,n]范围内的日志条目给新节点。
新节点接收并应用这些日志条目，从而将自己的日志和领导者的日志同步。

这个过程可以确保新节点能够正确地从领导者那里获取并应用所有必要的日志条目，即使领导者已经为一部分日志条目创建了快照。

这个例子中可以看到，快照代表的是某个log_index时的完整状态，因此leader只给新节点发送了快照，当新节点接收完毕后，leader就可以接着发送[m+1,n]范围的日志，而不需要leader发送[0.i-1]范围的日志，因为这对于新节点快速赶上leader的状态而言是没有必要的，快照已经包含了一个状态机应用到log_index=m时的完整状态。

按照论文中的InstallSnapShot的图片示例来看，按照上面的去实现即可。

5. how to use Raft(lab3)

每个service machine（一台物理机器上可能有多个）都会有一个服务层、一个Raft层，Raft层接收从client端发来的操作指令，当大多数节点都复制了这条指令之后，Raft层可以提交这条指令，之后将这条指令放入到apply channel（Service层与Raft层进行通信的一个信道）中，service层读取日志并逐条应用。

5.1 Duplicate detection（重复指令检测-lab3）

在Raft集群中，重复检测主要是通过领导者来完成的。每次客户端发起一个新的请求时，它都会生成一个唯一的请求ID。然后，领导者会为每个客户端和每个请求ID保持一个单独的状态。

当领导者收到一个新的请求时，它会检查这个请求的ID是否已经存在。如果存在，那么领导者就会知道这是一个重复的请求，然后直接返回之前的结果，而不是重新执行这个请求。如果不存在，那么领导者就会执行这个请求，并将结果和请求ID一起保存下来，以便于后续的重复检测。

客户端通常不需要做任何特殊的处理。它只需要确保每个请求的ID都是唯一的，然后将请求发送给领导者就可以了。然后，领导者会负责处理重复请求和非重复请求。

需要注意的是，这种方法只能处理重复的请求，对于重复的响应，Raft协议并没有提供内置的解决方案。这通常需要通过在应用层面实现幂等性来解决，真正的检测由service层实现。

5.2 what client needs to do？

在Raft协议中，客户端通常不需要维护任何特定的状态。客户端的主要职责是生成唯一的请求ID以及将请求发送给集群的领导者。领导者负责处理重复请求，以及执行客户端的命令。

然而，客户端可能需要知道哪个节点是当前的领导者，以便直接将请求发送给它。如果客户端不知道谁是领导者，或者领导者在请求过程中改变，客户端可能需要重新发送请求。在lab中，有一个clerk库，专门负责维护raft集群的当前信息，方便client知道当前集群的配置情况（leader，followers的IP等等这些信息）。

此外，为了高效的失败恢复，客户端可能需要实现重试机制。例如，如果客户端发送的请求没有收到响应，或者响应表明请求失败，客户端可能需要重新发送请求。

总的来说，虽然客户端在Raft协议中的作用相对较小，但是它仍然需要实现一些基本的功能，以便在分布式系统中正确和高效地工作。

5.3 How client interact with Raft Cluster？

在Raft协议中，客户端与集群的交互主要包括以下几个步骤：

客户端生成一个唯一的请求ID并将请求发送给领导者。这个请求可能是一个读操作或者一个写操作。
如果请求是一个写操作，领导者会先检查这个请求的ID是否已经存在。如果存在，领导者会直接返回之前的结果。如果不存在，领导者会将这个请求作为一个新的日志条目添加到自己的日志中。
领导者会将这个新的日志条目发送给其他的跟随者。每个跟随者会将这个日志条目添加到自己的日志中，并向领导者发送确认。
一旦领导者收到了大多数跟随者的确认，它就会提交这个日志条目，之后将这个日志条目放到apply channel中，等待service端去应用这条日志，它就会将这个日志条目应用到自己的状态机中，并将结果和请求ID一起保存下来。然后，领导者会向客户端返回结果。
如果请求是一个读操作，领导者会直接从自己的状态机中读取结果，并向客户端返回结果。

这就是客户端与Raft集群交互的基本流程。需要注意的是，这个流程可能会因为领导者改变、网络延迟、请求失败等因素而有所不同。

6. Correctness：Linearizability

这是线性一致性（Linearizability）要满足的三个特性，之前我们了解过数据库的隔离级别中的Serializablility，二者的唯一区别就是Serial不需要满足第二个match real-time的要求，即不需要满足全局时钟，只需要在进程内满足操作顺序即可。（顺序一致性很像数据库隔离级别中的serializablility）

back.