本部分主要是关于不一致的日志是怎么决策和取舍的。同时对于日志的恢复，通过快照的方式提高恢复的效率。
1. 不一致log的处理
在我们分析之前，我们需要明白这个场景是否真的存在，因为有些场景不可能存在我们也就没必要考虑它。即需要思考这种情况可能发生吗？如果可能发生，是怎么发生的？
一个旧Leader在各种奇怪的场景下故障之后，一个新任的Leader如何能整理在不同副本上可能已经不一致的Log？这个话题只在Leader故障之后才有意义，如果Leader正常运行，Raft不太会出现问题。如果Leader正在运行，并且在其运行时，系统中有过半服务器。Leader只需要告诉Followers，Log该是什么样子。Raft要求Followers必须同意并接收Leader的Log。只要Followers还能处理，它们就会全盘接收Leader在AppendEntries中发送给它们的内容，并加到本地的Log中。之后再收到来自Leader的commit消息，在本地执行请求。
在Raft中，当Leader故障了才有可能出错。例如，旧的Leader在发送消息的过程中故障了，或者新Leader在刚刚当选之后，还没来得及做任何操作就故障了。在一系列故障之后，Log会是怎样？假设我们有3个服务器（S1，S2，S3），每一列对齐之后就是Log的一个槽位。我这里写的值是Log条目对应的任期号，所有节点在任期3的时候记录了一个请求在槽位1，S2和S3在任期3的时候记录了一个请求在槽位2。在槽位2，S1没有任何记录。
假设S3是任期3的Leader，S3从客户端收到了第二个请求，它还是需要将这个请求发送给其他服务器。但是这里有三种情况：
- 发送给S1的消息丢了
- S1当时已经关机了
- S3在向S2发送完AppendEntries之后，在向S1发送AppendEntries之前故障了
现在，只有S2和S3有槽位2的Log，这是不同节点之间Log不一样的一种最简单的场景。如果现任Leader S3故障了，首先我们需要新的选举，之后某个节点会被选为新的Leader。接下来会发生两件事情：
- 新的Leader需要认识到，槽位2的请求可能已经commit了，从而不能丢弃。
- 新的Leader需要确保S1在槽位2记录与其他节点完全一样的请求。
这里还有另外一个例子需要考虑。3个服务器，有槽位10、11、12、13。槽位10和槽位11类似于前一个例子。在槽位12，S2有一个任期4的请求，而S3有一个任期5的请求。假设S2在槽位12时，是任期4的新Leader，它收到了来自客户端的请求，将这个请求加到了自己的Log中，然后就故障了。这里S3可能被选上，因为它只需要从过半服务器获得认可投票，而在这个场景下，过半服务器就是S1和S3。S3可能被选为任期5的新Leader，之后收到了来自客户端的请求，将这个请求加到自己的Log中，然后故障了。之后就到了例子中的场景了。
因为可能发生，Raft必须能够处理这种场景。在我们讨论Raft会如何做之前，我们必须了解，怎样才是一种可接受的结果。大概看一眼这个图，我们知道在槽位10的Log，3个副本都有记录，它可能已经commit了，我们不能丢弃它。类似的在槽位11的Log，因为它被过半服务器记录了，它也可能commit了，我们也不能丢弃它。在槽位12记录的两个Log（分别是任期4和任期5），都没有被commit，Raft可以丢弃它们。这里没有要求必须都丢弃它们，但是至少需要丢弃一个Log，因为最终你还是要保持多个副本之间的Log一致。
学生提问：槽位10和11的请求必然执行成功了吗？
Robert教授：对于槽位11，甚至对于槽位10，我们不能从Log中看出来Leader在故障之前到底执行到了哪一步。有一种可能是Leader在发送完AppendEntries之后就立刻故障了，Leader没能收到其他副本的确认，相应的请求也就不会commit，进而也就不会执行这个请求，它也就不会发出增加了的commit值，其他副本也就可能也没有执行这个请求。完全可能槽位10和槽位11的请求没有被执行。如果Raft能知道这些，那么丢弃槽位10和槽位11的Log也是合法的，因为它们没有被commit。从Log上看，没有办法否认这些请求被commit了。换句话说，这些请求可能commit了。Raft必须认为它们已经被commit了，因为完全有可能，Leader是在对这些请求走完完整流程之后再故障。这里，我们不能排除Leader已经返回响应给客户端的可能性，只要这种可能性存在，我们就不能将槽位10和槽位11的Log丢弃，因为客户端可能已经知道了这个请求被执行了。我们必须假设这些请求被commit了。
根本无法从log得知是否已经commit，因为可能应用日志之后，leader还未确认其他副本就挂了，也就没有正确响应客户端，commitID也不会增加
那么对于例子中的 10 ，11 到底是怎么算？
客户端请求，raft发送给副本之后就挂了，客户端没有收到响应；当然也有可能客户端收到成功之后，leader挂了
- 从最简单的角度考虑，10已经全部复制了+leader一定有这条日志+leader不会删除自己的日志，所以10肯定会被commit（执行时间暂不讨论，但一定会commit）
- 这里需要结合客户端进行处理，一是判断是不是同一个消息，二是部分操作客户端重试，但是有些客户端不能重试。
2. 日志恢复（Log Backup）
我们假设下一个任期是6，我们同时假设S3在任期6被选为Leader。在某个时刻，新Leader S3会发送任期6的第一个AppendEntries RPC，来传输任期6的第一个Log，这个Log应该在槽位13。
这里的AppendEntries消息实际上有两条，因为要发给两个Followers。它们包含了客户端发送给Leader的请求。我们现在想将这个请求复制到所有的Followers上。这里的AppendEntries RPC还包含了prevLogIndex字段和prevLogTerm字段。Leader在发送AppendEntries消息时，会附带前一个槽位的信息。在我们的场景中，prevLogIndex是前一个槽位的位置，也就是12；prevLogTerm是S3上前一个槽位的任期号，也就是5。
这样的AppendEntries消息发送给了Followers。而Followers，它们在收到AppendEntries消息时，可以知道它们收到了一个带有若干Log条目的消息，并且是从槽位13开始。Followers在写入Log之前，会检查本地的前一个Log条目，是否与Leader发来的有关前一条Log的信息匹配。
对于S2 它显然是不匹配的。S2 在槽位12已经有一个条目，但是它来自任期4，而不是任期5。S2将拒绝这个AppendEntries，并返回False给Leader。S1在槽位12还没有任何Log，S1也将拒绝Leader的这个AppendEntries。到目前位置，一切都还好。为什么这么说呢？因为我们完全不想看到的是，S2 把这条新的Log添加在槽位13。因为这样会破坏Raft论文中图2所依赖的归纳特性，并且隐藏S2 实际上在槽位12有一条不同的Log的这一事实。
S1和S2都没有接受这条AppendEntries消息，，Leader看到了两个拒绝。
Leader为每个Follower维护了nextIndex。它有一个S2的nextIndex，还有一个S1的nextIndex。之前没有说明的是，如果Leader之前发送的是有关槽位13的Log，这意味着Leader对于其他两个服务器的nextIndex都是13。这种情况发生在Leader刚刚当选，因为Raft论文的图2规定了，nextIndex的初始值是从新任Leader的最后一条日志开始，而在我们的场景中，对应的就是槽位13.
为了响应Followers返回的拒绝，Leader会减小对应的nextIndex。它现在减小了两个Followers的nextIndex。这一次，Leader发送的AppendEntries消息中，prevLogIndex等于11，prevLogTerm等于3。同时，这次Leader发送的AppendEntries消息包含了prevLogIndex之后的所有条目，也就是S3上槽位12和槽位13的Log。
对于S2来说，这次收到的AppendEntries消息中，prevLogIndex等于11，prevLogTerm等于3，与自己本地的Log匹配，，S2会接受这个消息。Raft论文中的图2规定，如果接受一个AppendEntries消息，那么需要首先删除本地相应的Log（如果有的话），再用AppendEntries中的内容替代本地Log。，S2会这么做：它会删除本地槽位12的记录，再添加AppendEntries中的Log条目。这个时候，S2的Log与S3保持了一致。
但是，S1仍然有问题，因为它的槽位11是空的，它不能匹配这次的AppendEntries。它将再次返回False。而Leader会将S1对应的nextIndex变为11，并在AppendEntries消息中带上从槽位11开始之后的Log（也就是槽位11，12，13对应的Log）。并且带上相应的prevLogIndex（10）和prevLogTerm（3）。
这次的请求可以被S1接受，并得到肯定的返回。现在它们都有了一致的Log。
而Leader在收到了Followers对于AppendEntries的肯定的返回之后，它会增加相应的nextIndex到14。
在这里，Leader使用了一种备份机制来探测Followers的Log中，第一个与Leader的Log相同的位置。在获得位置之后，Leader会给Follower发送从这个位置开始的，剩余的全部Log。经过这个过程，所有节点的Log都可以和Leader保持一致。
重复一个我们之前讨论过的话题，或许我们还会再讨论。在刚刚的过程中，我们擦除了一些Log条目，比如我们刚刚删除了S2中的槽位12的Log。这个位置是任期4的Log。
为什么Raft系统可以安全的删除这条记录？
我在上堂课说过这个问题，这里的原理是什么呢？这条Log条目并没有存在于过半服务器中，因此无论之前的Leader是谁，发送了这条Log，它都没有得到过半服务器的认可。因此旧的Leader不可能commit了这条记录，也就不可能将它应用到应用程序的状态中，进而也就不可能回复给客户端说请求成功了。因为它没有存在于过半服务器中，发送这个请求的客户端没有理由认为这个请求被执行了，也不可能得到一个回复。Leader只会在commit之后（响应应用层，应用层处理之后）回复给客户端。
如果客户端发送请求之后一段时间没有收到回复，它应该重新发送请求。我们知道，不论这个被丢弃的请求是什么，我们都没有执行它，没有把它包含在任何状态中，并且客户端之后会重新发送这个请求。
这种情况需要结合客户端+具体业务情况考虑
学生提问：前面的过程中，为什么总是删除Followers的Log的结尾部分？
Robert教授：一个备选的答案是，Leader有完整的Log，当Leader收到有关AppendEntries的False返回时，它可以发送完整的日志给Follower。如果你刚刚启动系统，甚至在一开始就发生了非常反常的事情，某个Follower可能会从第一条Log 条目开始恢复，然后让Leader发送整个Log记录，因为Leader有这些记录。如果有必要的话，Leader拥有填充每个节点的日志所需的所有信息。
3. 快速恢复（Fast Backup）
核心思想，把Leader follower的信息都有效利用起来，而非知识leader一点点探测，从而快速对齐。
在前面介绍的日志恢复机制中，如果Log有冲突，Leader每次会回退一条Log条目。 这在许多场景下都没有问题。但是在某些现实的场景中，至少在Lab2的测试用例中，每次只回退一条Log条目会花费很长很长的时间。现实的场景中，可能一个Follower关机了很长时间，错过了大量的AppendEntries消息。这时，Leader重启了。按照Raft论文中的图2，如果一个Leader重启了，它会将所有Follower的nextIndex设置为Leader本地Log记录的下一个槽位。
如果一个Follower关机并错过了1000条Log条目，Leader重启之后，需要每次通过一条RPC来回退一条Log条目来遍历1000条Follower错过的Log记录。这种情况在现实中并非不可能发生。在一些不正常的场景中，假设我们有5个服务器，有1个Leader，这个Leader和另一个Follower困在一个网络分区。但是这个Leader并不知道它已经不再是Leader了。它还是会向它唯一的Follower发送AppendEntries，因为这里没有过半服务器，没有一条Log会commit。在另一个有多数服务器的网络分区中，系统选出了新的Leader并继续运行。旧的Leader和它的Follower可能会记录无限多的旧的任期的未commit的Log。当旧的Leader和它的Follower重新加入到集群中时，这些Log需要被删除并覆盖。可能在现实中，这不是那么容易发生，但是你会在Lab2的测试用例中发现这个场景。
为了能够更快的恢复日志，Raft论文在论文的5.3结尾处，对一种方法有一些模糊的描述。大致思想是，让Follower返回足够的信息给Leader，这样Leader可以以任期（Term）为单位来回退，而不用每次只回退一条Log条目。现在，在恢复Follower的Log时，如果Leader和Follower的Log不匹配，Leader只需要对每个不同的任期发送一条AppendEntries，而不用对每个不同的Log条目发送一条AppendEntries。这只是一种加速策略，当然，或许你也可以想出许多其他不同的日志恢复加速策略。
我将可能出现的场景分成3类，为了简化，这里只画出一个Leader（S2）和一个Follower（S1），S2将要发送一条任期号为6的AppendEntries消息给Follower。
- 场景1：S1没有任期6的任何Log，因此我们需要回退一整个任期的Log。
- 场景2：S1收到了任期4的旧Leader的多条Log，但是作为新Leader，S2只收到了一条任期4的Log。这里需要覆盖S1中有关旧Leader的一些Log。
- 场景3：S1与S2的Log不冲突，但是S1缺失了部分S2中的Log。
AE Reply
可以让Follower在回复Leader的AppendEntries消息中，携带3个额外的信息，来加速日志的恢复。这里的回复是指，Follower因为Log信息不匹配，拒绝了Leader的AppendEntries之后的回复。这里的三个信息是指：
- XTerm：这个是Follower中与Leader冲突的Log对应的任期号。在之前有介绍Leader会在prevLogTerm中带上本地Log记录中，前一条Log的任期号。如果Follower在对应位置的任期号不匹配，它会拒绝Leader的AppendEntries消息，并将自己的任期号放在XTerm中。如果Follower在对应位置没有Log，那么这里会返回 -1。
- XIndex：这个是Follower中，对应任期号为XTerm的第一条Log条目的槽位号。
- XLen：如果Follower在对应位置没有Log，那么XTerm会返回-1，XLen表示空白的Log槽位数。
我们再来看这些信息是如何在上面3个场景中，帮助Leader快速回退到适当的Log条目位置。
- 场景1。Follower（S1）会返回XTerm=5，XIndex=2。Leader（S2）发现自己没有任期5的日志，它会将自己本地记录的，S1的nextIndex设置到XIndex，也就是S1中，任期5的第一条Log对应的槽位号。如果Leader完全没有XTerm的任何Log，那么它应该回退到XIndex对应的位置（这样，Leader发出的下一条AppendEntries就可以一次覆盖S1中所有XTerm对应的Log）。
- 场景2。Follower（S1）会返回XTerm=4，XIndex=1。Leader（S2）发现自己其实有任期4的日志，它会将自己本地记录的S1的nextIndex设置到本地在XTerm位置的Log条目后面，也就是槽位2。下一次Leader发出下一条AppendEntries时，就可以一次覆盖S1中槽位2和槽位3对应的Log。
- 场景3。Follower（S1）会返回XTerm=-1，XLen=2。这表示S1中日志太短了，以至于在冲突的位置没有Log条目，Leader应该回退到Follower最后一条Log条目的下一条，也就是槽位2，并从这开始发送AppendEntries消息。槽位2可以从XLen中的数值计算得到。
这些信息在Lab中会有用。
对于这里的快速回退机制有什么问题吗？
学生提问：这里是线性查找，可以使用类似二分查找的方法进一步加速吗？
Robert教授：我认为这是对的，或许这里可以用二分查找法。Raft论文中并没有详细说明是怎么做的，我这里加工了一下。或许有更好，更快的方式来完成。如果Follower返回了更多的信息，那是可以用一些更高级的方法，例如二分查找来完成。为了通过Lab2的测试，你肯定需要做一些优化工作。我们提供的Lab2的测试用例中，有一件不幸但是不可避免的事情是，它们需要一些实时特性。这些测试用例不会永远等待你的代码执行完成并生成结果。有可能你的方法技术上是对的，但是花了太多时间导致测试用例退出。这个时候，你是不能通过全部的测试用例的。因此你的确需要关注性能，从而使得你的方案即是正确的，又有足够的性能。不幸的是，性能与Log的复杂度相关，很容易就写出一个正确但是不够快的方法出来。
学生提问：能在解释一下这里的流程吗？
Robert教授：Leader发现冲突的方法在于，Follower会返回它从冲突条目中看到的任期号（XTerm）。在场景1中，Follower会设置XTerm=5，因为这是有冲突的Log条目对应的任期号。Leader会发现，哦，我的Log中没有任期5的条目。因此，在场景1中，Leader会一次性回退到Follower在任期5的起始位置。因为Leader并没有任何任期5的Log，它要删掉Follower中所有任期5的Log，这通过回退到Follower在任期5的第一条Log条目的位置，也就是XIndex达到的。
4. 日志快照（Log Snapshot）
在Raft中，Log压缩和快照（Log compaction and snapshots）解决的问题是：对于一个长期运行的系统，例如运行了几周，几个月甚至几年，如果我们按照Raft论文图2的规则，那么Log会持续增长。最后可能会有数百万条Log，从而需要大量的内存来存储。如果持久化存储在磁盘上，最终会消耗磁盘的大量空间。如果一个服务器重启了，它需要通过重新从头开始执行这数百万条Log来重建自己的状态。当故障重启之后，遍历并执行整个Log的内容可能要花费几个小时来完成。这在某种程度上来说是浪费，因为在重启之前，服务器已经有了一定的应用程序状态。
为了应对这种场景，Raft有了快照（Snapshots）的概念。快照背后的思想是，要求应用程序将其状态的拷贝作为一种特殊的Log条目存储下来。
我们之前几乎都忽略了应用程序，但是事实是，假设我们基于Raft构建一个key-value数据库，Log将会包含一系列的Put/Get或者Read/Write请求。假设一条Log包含了一个Put请求，客户端想要将X设置成1，另一条Log想要将X设置成2，下一条将Y设置成7。如果Raft一直执行没有故障，Raft之上的将会是应用程序，在这里，应用程序将会是key-value数据库。它将会维护一个表单，当Raft一个接一个的上传命令时，应用程序会更新它的表单。第一个命令之后，应用程序会将表单中的X设置为1。第二个命令之后，表单中的X会被设置为2。第三个命令之后，表单中的Y会被设置为7。
对于大多数的应用程序来说，应用程序的状态远小于Log的大小。某种程度上我们知道，在某些时间点，Log和应用程序的状态是可以互换的，它们是用来表示应用程序状态的不同事物。但是Log可能包含大量的重复的记录（例如对于X的重复赋值），这些记录使用了Log中的大量的空间，但是同时却压缩到了key-value表单中的一条记录。这在多副本系统中很常见。在这里，如果存储Log，可能尺寸会非常大，相应的，如果存储key-value表单，这可能比Log尺寸小得多。这就是快照的背后原理。
当Raft认为它的Log将会过于庞大，例如大于1MB，10MB或者任意的限制，Raft会要求应用程序在Log的特定位置，对其状态做一个快照。如果Raft要求应用程序做一个快照，Raft会从Log中选取一个与快照对应的点，然后要求应用程序在那个点的位置做一个快照。这里极其重要，因为我们接下来将会丢弃所有那个点之前的Log记录。如果我们有一个点的快照，那么我们可以安全的将那个点之前的Log丢弃。（在key-value数据库的例子中）快照本质上就是key-value表单。我们还需要为快照标注Log的槽位号。
有了快照，并且Raft将它存放在磁盘中之后，Raft将不会再需要这部分Log。只要Raft持久化存储了快照，快照对应的Log槽位号，以及Log槽位号之后的所有Log，那么快照对应槽位号之前的这部分Log可以被丢弃，我们将不再需要这部分Log。Raft要求应用程序做快照，得到快照之后将其存储在磁盘中，同时持久化存储快照之后的Log，并丢弃快照之前的Log。Raft的持久化存储实际上是持久化应用程序快照，和快照之后的Log。
这里“Raft的持久化存储实际上是持久化应用程序快照，和快照之后的Log”部分很重要，之前一直比较迷惑，到底raft的snapshot和上层应用的snapshot是不是同一个东西，这里明确说明了，实际上就是持久化应用程序的快照。解释说明如下：
raft log -- 通过第一个log一直应用到当前，那就和当前应用程序的状态一致 --> 所以直接整体存储当前状态就不需要这些日志。
这里是应用层结合做的快照，实际上相当于将之前的日志压缩了。
重启的时候会发生什么呢？现在，重启的场景比之前只有Log会更加复杂一点。重启的时候，必须让Raft有方法知道磁盘中最近的快照和Log的组合，并将快照传递给应用程序。因为现在我们不能重演所有的Log（部分被删掉了），必须要有一种方式来初始化应用程序。应用程序不仅需要有能力能生成一个快照，它还需要能够吸纳一个之前创建的快照，并通过它稳定的重建自己的内存。尽管Raft在管理快照，快照的内容实际上是应用程序的属性。Raft并不理解快照中有什么，只有应用程序知道，因为快照里面都是应用程序相关的信息。重启之后，应用程序需要能够吸纳Raft能找到的最近的一次快照。
因为丢弃了快照之前的Log，引入了大量的复杂性。如果有的Follower的Log较短，在Leader的快照之前就结束，那么除非有一种新的机制，否则那个Follower永远也不可能恢复完整的Log。我们可以通过这种方式来避免这个问题：如果Leader发现有任何一个Follower的Log落后于Leader要做快照的点，那么Leader就不丢弃快照之前的Log。Leader原则上是可以知道Follower的Log位置，然后Leader可以不丢弃所有Follower中最短Log之后的本地Log。但是如果一个Follower关机了一周，它也就不能确认Log条目，同时也意味着Leader不能通过快照来减少自己的内存消耗（因为那个Follower的Log长度一直没有更新）。
Raft选择的方法是，Leader可以丢弃Follower需要的Log。我们需要某种机制让AppendEntries能处理某些Follower Log的结尾到Leader Log开始之间丢失的这一段Log。解决方法是（一个新的消息类型）InstallSnapshot RPC，Leader会将自己的快照发给Follower，之后立即通过AppendEntries将后面的Log发给Follower。这里明显的增加了的复杂度。因为这里需要Raft组件之间的协同，这里还有点违反模块性，因为这里需要组件之间有一些特殊的协商。例如，当Follower收到了InstallSnapshot，这个消息是被Raft收到的，但是Raft实际需要应用程序能吸纳这个快照，它们现在需要更多的交互了。
学生提问：快照的创建是否依赖应用程序？
Robert教授：肯定依赖。快照生成函数是应用程序的一部分，如果是一个key-value数据库，那么快照生成就是这个数据库的一部分。Raft会通过某种方式调用到应用程序，通知应用程序生成快照，因为只有应用程序自己才知道自己的状态（进而能生成快照）。而通过快照反向生成应用程序状态的函数，同样也是依赖应用程序的。每个快照又必须与某个Log槽位号对应。
学生提问：如果RPC消息乱序该怎么处理？
Robert教授：是在说Raft论文图13的规则6吗？Follower有可能收到一条很久以前的InstallSnapshot消息。因此，Follower必须要小心应对InstallSnapshot消息。Raft论文图13的规则6有相应的说明。我认为正常的响应是，Follower可以忽略明显旧的快照。其实我（Robert教授）看不懂那条规则6。
