6.824 Raft阶段性总结(一)
raft 是一种强leader形式的共识算法，日志只从leader流向其他服务器。
Lecture 06-Raft1
根据：https://mit-public-courses-cn-translatio.gitbook.io/mit6-824/lecture-06-raft1 对这节课的剖析进行划分
6.1 脑裂 (split brain)
前5节课介绍的，具有fault-tolerant的系统：
MapReduce复制了计算，但是复制这个动作，或者说整个MapReduce被一个单主节点（master）控制，分配 map 和 reduce 任务给worker。
GFS以主备（primary-backup）的方式复制数据。它会实际的复制文件内容。但是它也依赖一个单主节点，来确定每一份数据的主拷贝的位置。
VMware FT，它在一个Primary虚机和一个Backup虚机之间复制计算相关的指令。但是，当其中一个虚机出现故障时，为了能够正确的恢复。需要一个Test-and-Set服务来确认，Primary虚机和Backup虚机只有一个能接管计算任务。
这三个系统都是多副本系统，但都有一个主节点。这种单节点有好有坏，好在它的决策就是整体决策，坏在本身就是一个单点故障（Single Point of Failure）。
使用单点的原因就是我们要避免split brain。
很久前有两种方法可以避免脑裂：很长一段时间内，人们都使用以下两种方式中的一种来构建多副本系统。这虽然不太完美，因为人工响应不能很及时，而不出现故障的网络又很贵，但是这些方法至少是可行的。
第一种是构建一个不可能出现故障的网络。
第二种是人工恢复。
6.2 过半票决(Majority Vote)
当网络出现故障，将网络分割成两半，网络的两边独自运行，且不能访问对方，这通常被称为网络分区。
在构建能自动恢复，同时又避免脑裂的多副本系统时，人们发现，关键点在于过半票决（Majority Vote）。这也是raft的一个基本概念。
过半票决的第一步在于系统是奇数（很简单，出现分区的时候不会出现对称现象，必定有一个是多数派）
然后为了完成任何操作，例如Raft的Leader选举，例如Raft的leader提交一个Log条目，在任何时候为了完成任何操作，你必须凑够过半的服务器来批准相应的操作。过半指的是集群总数的半数，即使分区也不会影响过半的数量。
过半票决有一个更微妙的点：每一个操作都需要过半的服务器来批准，例如raft选举leader，那么每一个操作对应的过半服务器，至少包含有一个服务器存在上一个操作的过半服务器中。也就是说，任意两组过半服务器，至少有一个服务器是重叠的。
Raft更依赖这个特性来避免脑裂。例如，当一个Raft Leader竞选成功，那么这个Leader必然凑够了过半服务器的选票，而这组过半服务器中，必然与旧Leader的过半服务器有重叠。所以**，新的Leader必然知道旧Leader使用的任期号**（term number），因为新Leader的过半服务器必然与旧Leader的过半服务器有重叠（一个或者多个），而旧Leader的过半服务器中的每一个必然都知道旧Leader的任期号。类似的，任何旧Leader提交的操作，必然存在于过半的Raft服务器中，而任何新Leader的过半服务器中，必然有至少一个服务器包含了旧Leader的所有操作。这是Raft能正确运行的一个重要因素。
6.3 Raft 初探
Raft会以库（Library）的形式存在于服务中。如果你有一个基于Raft的多副本服务，那么每个服务的副本将会由两部分组成：应用程序代码和Raft库。应用程序代码接收RPC或者其他客户端请求；不同节点的Raft库之间相互合作，来维护多副本之间的操作同步。
从软件的角度来看一个Raft节点，我们可以认为在该节点的上层，是应用程序代码。例如对于Lab 3来说，这部分应用程序代码就是一个Key-Value数据库。应用程序通常都有状态，Raft层会帮助应用程序将其状态拷贝到其他副本节点。对于一个Key-Value数据库而言，对应的状态就是Key-Value Table。应用程序往下，就是Raft层。所以，Key-Value数据库需要对Raft层进行函数调用，来传递自己的状态和Raft反馈的信息。
同时，如Raft论文中的图2所示，Raft本身也会保持状态。对我们而言，Raft的状态中，最重要的就是Raft会记录操作的日志。
对客户端来说，不管我们是几副本服务，在他们眼里都应该是单点服务。
raft库和应用程序的运行流程：
假设kv要完成一个put操作，应用程序只会将来自客户端的请求对应的操作向下发给raft库，告知raft把它应用到日志中，并在完成时通知我。raft就进行rpc交互，直到过半节点将这个新的操作加入到他们的log中，这个时候leader就可以提交这个日志了，然后每个副本节点的Raft层会将相同的操作提交到本地的应用程序层。在本地的应用程序层，会将这个操作更新到自己的状态。
理想情况是，所有的副本都将看到相同的操作序列，这些操作序列以相同的顺序出现在Raft到应用程序的upcall中，之后它们以相同的顺序被本地应用程序应用到本地的状态中。
假设操作是确定的，如不是生成随机数这种，最后所有副本节点的状态会是一样的。
6.4 Log同步时序
客户端发来请求后，Leader服务器的Raft层会发送一个添加日志（AppendEntries）的RPC到其他副本，一旦过半节点响应，Leader就会执行（来自客户端的）请求，得到结果，并将结果返回给客户端。
并且，一旦Leader发现请求被commit之后，它需要将这个消息通知给其他的副本。
过半服务器之外的服务器可能也会响应给Leader，但是我们不需要等它，一旦过半，leader就提交。
committed消息被夹带在下一个AppendEntries消息中，由Leader下一次的AppendEntries对应的RPC发出。任何情况下，当有了committed消息时，这条消息会填在AppendEntries的RPC中。下一次Leader需要发送心跳，或者是收到了一个新的客户端请求，要将这个请求同步给其他副本时，Leader会将新的更大的commit号随着AppendEntries消息发出，当其他副本收到了这个消息，就知道之前的commit号已经被Leader提交，其他副本接下来也会执行相应的请求，更新本地的状态。
commit信息是随着普通的AppendEntries消息发出的，因此其他副本的状态更新就不是很及时了。但是教授认为这个无关紧要，因为没有人在等这个步骤，不会影响客户端感受。
6.5 Raft Log（日志）
为什么Raft系统这么关注Log，Log究竟起了什么作用？
Raft系统之所以对Log关注这么多的**一个原因是，Log是Leader用来对操作排序的一种手段。**这对于复制状态机而言至关重要，对于这些复制状态机来说，所有副本不仅要执行相同的操作，还需要用相同的顺序执行这些操作。而Log与其他很多事物，共同构成了Leader对接收到的客户端操作分配顺序的机制。
实际上，Log是一些按照数字编号的槽位（类似一个数组），槽位的数字表示了Leader选择的顺序。
Log的另一个用途是，在一个（非Leader，也就是Follower）副本收到了操作，但是还没有执行操作时。该副本需要将这个操作存放在某处，直到收到了Leader发送的新的commit号才执行。所以，**对于Raft的Follower来说，Log是用来存放临时操作的地方。**Follower收到了这些临时的操作，但是还不确定这些操作是否被commit了。我们将会看到，这些操作可能会被丢弃。
Log的另一个用途是用在Leader节点，我（Robert教授）很喜欢这个特性。Leader需要在它的Log中记录操作，因为这些操作可能需要重传给Follower。如果一些Follower由于网络原因或者其他原因短时间离线了或者丢了一些消息，Leader需要能够向Follower重传丢失的Log消息。**所以，Leader也需要一个地方来存放客户端请求的拷贝。**即使对那些已经commit的请求，为了能够向丢失了相应操作的副本重传，也需要存储在Leader的Log中。
所有节点都需要保存Log还有一个原因，就是它可以帮助重启的服务器恢复状态。你可能的确需要一个故障了的服务器在修复后，能重新加入到Raft集群，要不然你就永远少了一个服务器。
对于一个重启的服务器来说，会使用存储在磁盘中的Log。每个Raft节点都需要将Log写入到它的磁盘中，这样它故障重启之后，Log还能保留。而这个Log会被Raft节点用来从头执行其中的操作进而重建故障前的状态，并继续以这个状态运行。所以，Log也会被用来持久化存储操作，服务器可以依赖这些操作来恢复状态。
6.6 应用层接口
假设我们的应用程序是一个key-value数据库，下面一层是Raft层。
在Raft集群中，每一个副本上，这两层之间主要有两个接口。
第一个接口是key-value层用来转发客户端请求的接口。如果客户端发送一个请求给key-value层，key-value层会将这个请求转发给Raft层，并说：请将这个请求存放在Log中的某处。
这个接口实际上是个函数调用，称之为Start函数。这个函数只接收一个参数，就是客户端请求(command)。key-value层说：我接到了这个请求，请把它存在Log中，并在committed之后告诉我。
另一个接口是，随着时间的推移，Raft层会通知key-value层：哈，你刚刚在Start函数中传给我的请求已经commit了。Raft层通知的，不一定是最近一次Start函数传入的请求。例如在任何请求commit之前，可能会再有超过100个请求通过Start函数传给Raft层。
这个向上的接口以go channel中的一条消息的形式存在。Raft层会发出这个消息，key-value层要读取这个消息。所以这里有个叫做applyCh的channel，通过它你可以发送ApplyMsg消息。
key-value层需要知道从applyCh中读取的消息，对应之前调用的哪个Start函数，所以Start函数的返回需要有足够的信息给key-value层，这样才能完成对应。Start函数的返回值包括，这个请求将会存放在Log中的位置（index）。这个请求不一定能commit成功，但是如果commit成功的话，会存放在这个Log位置。同时，它还会返回当前的任期号（term number）和一些其它我们现在还不太关心的内容。
在ApplyMsg中，将会包含请求（command）和对应的Log位置（index）。
所有的副本都会收到这个ApplyMsg消息，它们都知道自己应该执行这个请求，弄清楚这个请求的具体含义，并将它应用在本地的状态中。所有的副本节点还会拿到Log的位置信息（index），但是这个位置信息只在Leader有用，因为Leader需要知道ApplyMsg中的请求究竟对应哪个客户端请求（进而响应客户端请求）。
6.7 Leader选举（Leader Election）
其实不用leader也可以构建一个一致系统。例如paxos
有很多原因导致了Raft系统有一个Leader，其中一个最主要的是：通常情况下，如果服务器不出现故障，有一个Leader的存在，会使得整个系统更加高效。因为有了一个大家都知道的指定的Leader，对于一个请求，你可以只通过一轮消息就获得过半服务器的认可。对于一个无Leader的系统，通常需要一轮消息来确认一个临时的Leader，之后第二轮消息才能确认请求。所以，使用一个Leader可以提升系统性能至2倍。同时，有一个Leader可以更好的理解Raft系统是如何工作的。
Raft生命周期中可能会有不同的Leader，它使用任期号（term number）来区分不同的Leader。
Followers（非Leader副本节点）不需要知道Leader的ID，它们只需要知道当前的任期号。每一个任期最多有一个Leader，这是一个很关键的特性。对于每个任期来说，或许没有Leader（出现冲突选票，每个candidate都没有获得多数票），或许有一个Leader，但是不可能有两个Leader出现在同一个任期中。每个任期必然最多只有一个Leader。
每个Raft节点都有一个选举定时器（Election Timer），如果在这个定时器时间耗尽之前，当前节点没有收到任何当前Leader的消息，这个节点会认为Leader已经下线，并开始一次选举。
开始一次选举的意思是，当前服务器会增加任期号（term number），然后发出请求投票（RequestVote）的rpc，发给除了自己的所有服务器（自己会给自己投一票）。
果Leader没有故障，我们仍然有可能会有一次新的选举。比如，如果网络很慢，丢了几个心跳，或者其他原因，这时，尽管Leader还在健康运行，我们可能会有某个选举定时器超时了，进而开启一次新的选举。所以这意味着，如果有一场新的选举，有可能之前的Leader仍然在运行，并认为自己还是Leader。（所以需要在AppendEntries里面纠正它）
让其他服务器知道leader已经选出来了的方式就是发送心跳（AppendEntries）。
6.8 选举定时器（Election Timer）
任何一条AppendEntries消息都会重置所有Raft节点的选举定时器。这样，只要Leader还在线，并且它还在以合理的速率（不能太慢）发出心跳或者其他的AppendEntries消息，Followers收到了AppendEntries消息，会重置自己的选举定时器，这样Leader就可以阻止任何其他节点成为一个候选人。所以只要所有环节都在正常工作，不断重复的心跳会阻止任何新的选举发生。当然，如果网络故障或者发生了丢包，不可避免的还是会有新的选举。但是如果一切都正常，我们不太可能会有一次新的选举。
也会出现选举失败的情况，例如每个服务器同时开始选举，就都把票给了自己，但是他们在转换为candidate的时候会重置定时器，再超时后开始新一轮选举。
这里对于选举定时器的超时时间的设置，需要注意一些细节。一个明显的要求是，选举定时器的超时时间需要至少大于Leader的心跳间隔。这里非常明显，假设Leader每100毫秒发出一个心跳，你最好确认所有节点的选举定时器的超时时间不要小于100毫秒，否则该节点会在收到正常的心跳之前触发选举。所以，选举定时器的超时时间下限是一个心跳的间隔。实际上由于网络可能丢包，这里你或许希望将下限设置为多个心跳间隔。所以如果心跳间隔是100毫秒，你或许想要将选举定时器的最短超时时间设置为300毫秒，也就是3次心跳的间隔。
选举间隔最好是心跳间隔的多倍。但是选举间隔越大，系统恢复的时间越长。
6.9 可能的异常情况
这个话题只在Leader故障之后才有意义，如果Leader正常运行，Raft不太会出现问题。
如果Leader正在运行，并且在其运行时，系统中有过半服务器。Leader只需要告诉Followers，Log该是什么样子。Raft要求Followers必须同意并接收Leader的Log，这在Raft论文的图2中有说明。只要Followers还能处理，它们就会全盘接收Leader在AppendEntries中发送给它们的内容，并加到本地的Log中。之后再收到来自Leader的commit消息，在本地执行请求。这里很难出错。
Lecture 07-Raft2
7.1 日志恢复(Log Backup)
假设s3是leader，任期是6。在某个时刻，新Leader S3会发送任期6的第一个AppendEntries RPC，来传输任期6的第一个Log，这个Log应该在槽位13。
这里的AppendEntries消息实际上有两条，因为要发给两个Followers。它们包含了客户端发送给Leader的请求。我们现在想将这个请求复制到所有的Followers上。这里的AppendEntries RPC还包含了prevLogIndex字段和prevLogTerm字段。所以Leader在发送AppendEntries消息时，会附带前一个槽位的信息。在我们的场景中，prevLogIndex是前一个槽位的位置，也就是12；prevLogTerm是S3上前一个槽位的任期号，也就是5。
Followers，它们在收到AppendEntries消息时，可以知道它们收到了一个带有若干Log条目的消息，并且是从槽位13开始。Followers在写入Log之前，会检查本地的前一个Log条目，是否与Leader发来的有关前一条Log的信息匹配。
Follower:
所以对于S2 它显然是不匹配的。S2 在槽位12已经有一个条目，但是它来自任期4，而不是任期5。所以S2将拒绝这个AppendEntries，并返回False给Leader。
S1在槽位12还没有任何Log，所以S1也将拒绝Leader的这个AppendEntries。
所以S1和S2都没有接受这条AppendEntries消息，所以，Leader看到了两个拒绝。
Leader在下次心跳会根据nextIndex再次发送AppendEntries消息：
对于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为什么能直接删除s2槽位2的任期4呢？
原理是什么呢？是的，这条Log条目并没有存在于过半服务器中，因此无论之前的Leader是谁，发送了这条Log，它都没有得到过半服务器的认可。因此旧的Leader不可能commit了这条记录，也就不可能将它应用到应用程序的状态中，进而也就不可能回复给客户端说请求成功了。因为它没有存在于过半服务器中，发送这个请求的客户端没有理由认为这个请求被执行了，也不可能得到一个回复。因为这里有一条规则就是，Leader只会在commit之后回复给客户端。客户端甚至都没有理由相信这个请求被任意服务器收到了。并且，Raft论文中的图2说明，如果客户端发送请求之后一段时间没有收到回复，它应该重新发送请求。所以我们知道，不论这个被丢弃的请求是什么，我们都没有执行它，没有把它包含在任何状态中，并且客户端之后会重新发送这个请求。
7.2 选举约束(Election Restriction)
现在有个问题是，哪些节点允许成为Leader？
如果你读了Raft论文，那么你就知道答案：为了保证系统的正确性，并非任意节点都可以成为Leader。不是说第一个选举定时器超时了并触发选举的节点，就一定是Leader。Raft对于谁可以成为Leader，谁不能成为Leader是有一些限制的。
在Raft论文的5.4.1，Raft有一个稍微复杂的选举限制（Election Restriction）。这个限制要求，在处理别节点发来的RequestVote RPC时，需要做一些检查才能投出赞成票。这里的限制是，节点只能向满足下面条件之一的候选人投出赞成票:
1.候选人最后一条Log条目的任期号大于本地最后一条Log条目的任期号；
2.或者，候选人最后一条Log条目的任期号等于本地最后一条Log条目的任期号，且候选人的Log记录长度大于等于本地Log记录的长度
Raft更喜欢拥有更高任期号记录的候选人，或者说更喜欢拥有任期号更高的旧Leader记录的候选人。限制2说明，如果候选人都拥有任期号最高的旧Leader记录，那么Raft更喜欢拥有更多记录的候选人。
7.3 快速恢复（Fast Backup）
在前面（7.1）介绍的日志恢复机制中，如果Log有冲突，Leader每次会回退一条Log条目。 这在许多场景下都没有问题。但是在某些现实的场景中，至少在Lab2的测试用例中，每次只回退一条Log条目会花费很长很长的时间。所以，现实的场景中，可能一个Follower关机了很长时间，错过了大量的AppendEntries消息。这时，Leader重启了。按照Raft论文中的图2，如果一个Leader重启了，它会将所有Follower的nextIndex设置为Leader本地Log记录的下一个槽位（7.1有说明）。
所以，如果一个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的测试用例中发现这个场景。
所以需要一个快速恢复日志的方法：
让Follower返回足够的信息给Leader，这样Leader可以以任期（Term）为单位来回退，而不用每次只回退一条Log条目。所以现在，在恢复Follower的Log时，如果Leader和Follower的Log不匹配，Leader只需要对每个不同的任期发送一条AppendEntries，而不用对每个不同的Log条目发送一条AppendEntries。这是其中一种加速策略。
意思就是，如果prevLogIndex和PreLogTerm和我的上一个槽位不匹配，那就找到我上一个槽位所有的任期，一直找到跟我上一个槽位任期不同那里的索引，然后设置nextIndex，这样就只给每一个任期同步一条AppendEntries。
7.4 持久化（persistence）
你可以从Raft论文的图2的左上角看到，有些数据被标记为持久化的（Persistent），有些信息被标记为非持久化的（Volatile）。
持久化和非持久化的区别只在服务器重启时重要。当你更改了被标记为持久化的某个数据，服务器应该将更新写入到磁盘，或者其它的持久化存储中，例如一个电池供电的RAM。持久化的存储可以确保当服务器重启时，服务器可以找到相应的数据，并将其加载到内存中。这样可以使得服务器在故障并重启后，继续重启之前的状态。
实际上，一个常见的故障是断电。断电的时候，整个集群都同时停止运行，这种场景下，我们不能通过从Dell买一些新的服务器来替换现有服务器进而解决问题。这种场景下，如果我们希望我们的服务是容错的， 我们需要能够得到之前状态的拷贝，这样我们才能保持程序继续运行。因此，至少为了处理同时断电的场景，我们不得不让服务器能够将它们的状态存储在某处，这样当供电恢复了之后，还能再次获取这个状态。这里的状态是指，为了让服务器在断电或者整个集群断电后，能够继续运行所必不可少的内容。这是理解持久化存储的一种方式。
在Raft论文的图2中，有且仅有三个数据是需要持久化存储的。它们分别是Log、currentTerm、votedFor。Log是所有的Log条目。当某个服务器刚刚重启，在它加入到Raft集群之前，它必须要检查并确保这些数据有效的存储在它的磁盘上。服务器必须要有某种方式来发现，自己的确有一些持久化存储的状态，而不是一些无意义的数据。
Log需要被持久化存储的原因是，这是唯一记录了应用程序状态的地方。Raft论文图2并没有要求我们持久化存储应用程序状态。假如我们运行了一个数据库或者为VMware FT运行了一个Test-and-Set服务，根据Raft论文图2，实际的数据库或者实际的test-set值，并不会被持久化存储，只有Raft的Log被存储了。所以当服务器重启时，唯一能用来重建应用程序状态的信息就是存储在Log中的一系列操作，所以Log必须要被持久化存储。
那currentTerm呢？为什么currentTerm需要被持久化存储？是的，currentTerm和votedFor都是用来确保每个任期只有最多一个Leader。在一个故障的场景中，如果一个服务器收到了一个RequestVote请求，并且为服务器1投票了，之后它故障。如果它没有存储它为哪个服务器投过票，当它故障重启之后，收到了来自服务器2的同一个任期的另一个RequestVote请求，那么它还是会投票给服务器2，因为它发现自己的votedFor是空的，因此它认为自己还没投过票。现在这个服务器，在同一个任期内同时为服务器1和服务器2投了票。因为服务器1和服务器2都会为自己投票，它们都会认为自己有过半选票（3票中的2票），那它们都会成为Leader。现在同一个任期里面有了两个Leader。这就是为什么votedFor必须被持久化存储。
currentTerm的情况要更微妙一些，但是实际上还是为了实现一个任期内最多只有一个Leader，我们之前实际上介绍过这里的内容。如果（重启之后）我们不知道任期号是什么，很难确保一个任期内只有一个Leader。
这些数据需要在每次你修改它们的时候存储起来。所以可以确定的是，安全的做法是每次你添加一个Log条目，更新currentTerm或者更新votedFor，你或许都需要持久化存储这些数据。在一个真实的Raft服务器上，这意味着将数据写入磁盘，所以你需要一些文件来记录这些数据。如果你发现，直到服务器与外界通信时，才有可能持久化存储数据，那么你可以通过一些批量操作来提升性能。例如，只在服务器回复一个RPC或者发送一个RPC时，服务器才进行持久化存储，这样可以节省一些持久化存储的操作。
最后，有关持久化存储，还有一些细节。有些数据在Raft论文的图2中标记为非持久化的。所以，这里值得思考一下，为什么服务器重启时，commitIndex、lastApplied、nextIndex、matchIndex，可以被丢弃？例如，lastApplied表示当前服务器执行到哪一步，如果我们丢弃了它的话，我们需要重复执行Log条目两次（重启前执行过一次，重启后又要再执行一次），这是正确的吗？为什么可以安全的丢弃lastApplied？
这里综合考虑了Raft的简单性和安全性。之所以这些数据是非持久化存储的，是因为Leader可以通过检查自己的Log和发送给Followers的AppendEntries的结果，来发现哪些内容已经commit了。如果因为断电，所有节点都重启了。Leader并不知道哪些内容被commit了，哪些内容被执行了。但是当它发出AppendEntries，并从Followers搜集回信息。它会发现，Followers中有哪些Log与Leader的Log匹配，因此也就可以发现，在重启前，有哪些被commit了。
另外，Raft论文的图2假设，应用程序状态会随着重启而消失。所以图2认为，既然Log已经持久化存储了，那么应用程序状态就不必再持久化存储。因为在图2中，Log从系统运行的初始就被持久化存储下来。所以，当Leader重启时，Leader会从第一条Log开始，执行每一条Log条目，并提交给应用程序。所以，重启之后，应用程序可以通过重复执行每一条Log来完全从头构建自己的状态。这是一种简单且优雅的方法，但是很明显会很慢。这将会引出我们的下一个话题：Log compaction和Snapshot。
7.5 日志快照(Log snapshot)
Log压缩和快照（Log compaction and snapshots）在Lab3b中出现的较多。
在Raft中，Log压缩和快照解决的问题是：对于一个长期运行的系统，例如运行了几周，几个月甚至几年，如果我们按照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就会有重复，如x的重复赋值。这些记录使用了Log中的大量的空间，但是同时却压缩到了key-value表单中的一条记录。这在多副本系统中很常见。在这里，如果存储Log，可能尺寸会非常大，相应的，如果存储key-value表单，这可能比Log尺寸小得多。这就是快照的背后原理。
所以，当Raft认为它的Log将会过于庞大，例如大于1MB，10MB或者任意的限制，Raft会要求应用程序在Log的特定位置，对其状态做一个快照。所以，如果Raft要求应用程序做一个快照，Raft会从Log中选取一个与快照对应的点，然后要求应用程序在那个点的位置做一个快照。这里极其重要，因为我们接下来将会丢弃所有那个点之前的Log记录。如果我们有一个点的快照，那么我们可以安全的将那个点之前的Log丢弃。
有了快照，并且Raft将它存放在磁盘中之后，Raft将不会再需要这部分Log。只要Raft持久化存储了快照，快照对应的Log槽位号，以及Log槽位号之后的所有Log，那么快照对应槽位号之前的这部分Log可以被丢弃，我们将不再需要这部分Log。
所以这就是Raft快照的工作原理，Raft要求应用程序做快照，得到快照之后将其存储在磁盘中，同时持久化存储快照之后的Log，并丢弃快照之前的Log。所以，Raft的持久化存储实际上是持久化应用程序快照，和快照之后的Log。大家都明白了吗？
不幸的是，这里丢弃了快照之前的Log，引入了大量的复杂性。如果有的Follower的Log较短，在Leader的快照之前就结束，那么除非有一种新的机制，否则那个Follower永远也不可能恢复完整的Log。因为，如果一个Follower只有前两个槽位的Log，Leader不再有槽位3的Log可以通过AppendEntries RPC发给Follower，Follower的Log也就不可能补齐至Leader的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。
当Follower刚刚恢复，如果它的Log短于Leader通过 AppendEntries RPC发给它的内容，那么它首先会强制Leader回退自己的Log。在某个点，Leader将不能再回退，因为它已经到了自己Log的起点。这时，Leader会将自己的快照发给Follower，之后立即通过AppendEntries将后面的Log发给Follower。
不幸的是，这里明显的增加了的复杂度。因为这里需要Raft组件之间的协同，这里还有点违反模块性，因为这里需要组件之间有一些特殊的协商。例如，当Follower收到了InstallSnapshot，这个消息是被Raft收到的，但是Raft实际需要应用程序能吸纳这个快照。所以它们现在需要更多的交互了。
7.6 线性一致(Linearizability)
我们对于正确的定义就是线性一致（Linearizability）或者说强一致（Strong consistency）。通常来说，线性一致等价于强一致。一个服务是线性一致的，那么它表现的就像只有一个服务器，并且服务器没有故障，这个服务器每次执行一个客户端请求，并且没什么奇怪的事情发生。
一个系统的执行历史是一系列的客户端请求，或许这是来自多个客户端的多个请求。如果执行历史整体可以按照一个顺序排列，且排列顺序与客户端请求的实际时间相符合，那么它是线性一致的。
Lab2A and Lab2B
Leader Election
leader election就是在选举超时器结束后，如果自己不是leader，就进入选举状态，向所有服务器发选票。
总体流程就是ticker->candidateJoinElection->RequestVote
要求选票的rpc需要实现图二的两个规则：
1.自身携带的任期号小于当前任期号（term < currentTerm），则返回 false（5.1节） 2.如果votedFor为空或者是candidateId，并且candidate的日志至少和自己的日志一样新，则给该candidate投票（5.2节 和 5.4节）
规则一的实现是：
规则二得实现是：
AppendEntries
AppendEntries 包括发送心跳和日志复制,如果leader日志最后一条的索引大于nextIndex的话，就说明leader有新日志没发，就把这些新的全部添加到args里面发送给那个服务器。
AppendEntries需要遵守的规则：
1.自身携带的任期号小于当前任期号（term < currentTerm），则返回 false（5.1节） 2.没有term号与prevLogTerm相匹配，索引为prevLogIndex的日志条目，则返回 false（5.3节） 3.如果已经存在的日志条目与新的日志条目冲突（索引：index相同但是任期号：term 不同），则删除此日志条目及它之后所有的日志条目（5.3节） 4.添加任何在已有的日志中不存在的新条目 5.如果 leaderCommit > commitIndex，将commitIndex设置为leaderCommit和最新日志条目索引号中较小的那一个。
日志Apply
Raft Persist(Lab 2C)
如果基于Raft的服务器重新启动，它应该在其停止的地方恢复服务。这就要求Raft在重启后仍能保持持久的状态。论文的图2提到了哪些状态应该是持久的。
被标记为持久化的有：
currentTerm
votedFor
log
真正的实现会在每次Raft的持久化状态发生变化时将其写入磁盘，并在重启后重新启动时从磁盘读取状态。你的实现不会使用磁盘；相反，它将从Persister对象（见persister.go）保存和恢复持久化状态。调用Raft.Make()的人提供了一个Persister，它最初持有Raft最近的持久化状态（如果有的话）。Raft应该从该Persister初始化其状态，并在每次状态改变时使用它来保存其持久化状态。使用Persister的ReadRaftState（）和SaveRaftState（）方法。
为了避免内存耗尽，Raft必须定期丢弃旧的日志条目。
持久化和非持久化的区别只在服务器重启时重要。当你更改了被标记为持久化的某个数据，服务器应该将更新写入到磁盘，或者其它的持久化存储中，例如一个电池供电的RAM。持久化的存储可以确保当服务器重启时，服务器可以找到相应的数据，并将其加载到内存中。这样可以使得服务器在故障并重启后，继续重启之前的状态。
Log需要被持久化存储的原因是，这是唯一记录了应用程序状态的地方。Raft论文图2并没有要求我们持久化存储应用程序状态。假如我们运行了一个数据库或者为VMware FT运行了一个Test-and-Set服务，根据Raft论文图2，实际的数据库或者实际的test-set值，并不会被持久化存储，只有Raft的Log被存储了。所以当服务器重启时，唯一能用来重建应用程序状态的信息就是存储在Log中的一系列操作，所以Log必须要被持久化存储。
那currentTerm呢？为什么currentTerm需要被持久化存储？是的，currentTerm和votedFor都是用来确保每个任期只有最多一个Leader。在一个故障的场景中，如果一个服务器收到了一个RequestVote请求，并且为服务器1投票了，之后它故障。如果它没有存储它为哪个服务器投过票，当它故障重启之后，收到了来自服务器2的同一个任期的另一个RequestVote请求，那么它还是会投票给服务器2，因为它发现自己的votedFor是空的，因此它认为自己还没投过票。现在这个服务器，在同一个任期内同时为服务器1和服务器2投了票。因为服务器1和服务器2都会为自己投票，它们都会认为自己有过半选票（3票中的2票），那它们都会成为Leader。现在同一个任期里面有了两个Leader。这就是为什么votedFor必须被持久化存储。
currentTerm的情况要更微妙一些，但是实际上还是为了实现一个任期内最多只有一个Leader，如果（重启之后）我们不知道任期号是什么，很难确保一个任期内只有一个Leader。
在lab的Make函数中：在一个机器加入集群时调用了Make()，而后会进入rf.readPersist()
而在这个函数中，依照lab提供的包实现了currentTerm，votedFor和log的恢复：
当Leader重启时，Leader会从第一条Log开始，执行每一条Log条目，并提交给应用程序。所以，重启之后，应用程序可以通过重复执行每一条Log来完全从头构建自己的状态。这是一种简单且优雅的方法，但是很明显会很慢。这将会引出我们的下一个话题：Log compaction和Snapshot。
这部分内容在上面的 7.4 持久化中
Last updated
