日志复制（Log Replication）

Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行的向其他服务器发起AppendEntries RPC复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

日志结构

Log Replication分为两个主要步骤：复制（Replication）和 提交（Commit）。当一个节点被选为主节点后，它开始对外提供服务，收到客户端的command后，主节点会首先将command添加到自己的日志队列中，然后并行地将消息发送给其它所有的节点，在确保消息被安全地复制（下文解释）后，主节点会将该消息提交到状态机中，并返回状态机执行的结果。如果Follower挂了或因为网络原因消息丢失了，主节点会不断重试直到所有从节点最终成功复制该消息。

日志由许多条目（log entry）组成，条目顺序编号。条目包含它生成时节点所在的term（小方格中上方的数字），以及日志的内容。当一个条目被认为安全地被复制，且提交到状态机时，我们认为它处于“已提交（committed）”状态。

是否将一个条目提交到状态机是由主节点决定的。Raft要保证提交的条目会最终被所有的节点执行。当主节点判断一个条目已经被复制到大多数节点时，就会提交/Commit该条目，提交一个条目的同时会提交该条目之前的所有条目，包括那些之前由其它主节点创建的条目（还有些特殊情况下面会提）。主节点会记录当前提交的日志编号(log index)，并在发送心跳时带上该信息，这样其它节点最终会同步提交日志。

日志同步

上面说的是“提交”，那么“复制”是如何进行的？在现实情况下，主从节点的日志可能不一致（例如在消息到达从节点前主节点挂了，而从节点被选为了新的主节点，此时主从节点的日志不一致）。Raft算法中，主节点需要处理不一致的情况，它要求所有的从节点复制自己的所有日志。

要复制所有日志，就要先找到日志开始不一致的位置，如何做到呢？Raft当主节点接收到新的command时，会发送AppendEntries让从节点复制日志，不一致的情况也会在这时被处理（AppendEntries消息同时还兼职作为心跳信息）。某些Followers可能没有成功的复制日志，Leader会无限的重试AppendEntries RPC直到所有的Followers最终存储了所有的日志条目。下面是日志不一致的示例：

主节点需要为每个从节点记录一个nextIndex，作为该从节点下一条要发送的日志的编号。当一个节点刚被选为主节点时，为所有从节点的nextIndex初始化自己最大日志编号加1（如上图示例则为11）。接着主节点发送AppendEntries给从节点，此时从节点会进行一致性检查（Consistency Check）。

所谓一致性检查，指的是当主节点发送AppendEntries消息通知从节点添加条目时，需要将新条目A之前的那个条目B的log index和term，这样，当从节点收到消息时，就可以判断自己第log index条日志的term是否与B的term相同，如果不相同则拒绝该消息，如果相同则添加条目A。

主节点的消息被某个从节点拒绝后，主节点会将该从节点的nextIndex减一再重新发送AppendEntries消息。不断重试，最终就能找主从节点日志一致的log index，并用主节点的新日志覆盖从节点的旧日志。当然，如果从节点接收AppendEntries消息后，主节点会将nextIndex增加一，且如果当前的最新log index大于nextIndex则会继续发送消息。

同步保证

Raft日志同步保证如下两点：

• 如果不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
• 如果不同日志中的两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的。

第一条特性源于Leader在一个term内在给定的一个log index最多创建一条日志条目，同时该条目在日志中的位置也从来不会改变。第二条特性源于AppendEntries的一个简单的一致性检查。当发送一个AppendEntries RPC时，Leader会把新日志条目紧接着之前的条目的log index和term都包含在里面。如果Follower没有在它的日志中找到log index和term都相同的日志，它就会拒绝新的日志条目。

一般情况下，Leader和Followers的日志保持一致，因此AppendEntries一致性检查通常不会失败。然而，Leader崩溃可能会导致日志不一致：旧的Leader可能没有完全复制完日志中的所有条目。

上图阐述了一些Followers可能和新的Leader日志不同的情况。一个Follower可能会丢失掉Leader上的一些条目，也有可能包含一些Leader没有的条目，也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。Leader通过强制Followers复制它的日志来处理日志的不一致，Followers上的不一致的日志会被Leader的日志覆盖。

Leader为了使Followers的日志同自己的一致，Leader需要找到Followers同它的日志一致的地方，然后覆盖Followers在该位置之后的条目。Leader会从后往前试，每次AppendEntries失败后尝试前一个日志条目，直到成功找到每个Follower的日志一致位点，然后向后逐条覆盖Followers在该位置之后的条目。

日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃。每个副本独立的对自己的系统状态进行snapshot，并且只能对已经提交的日志记录进行snapshot。

Snapshot中包含以下内容：

• 日志元数据。最后一条已提交的log entry的log index和term。这两个值在snapshot之后的第一条log entry的AppendEntries RPC的完整性检查的时候会被用上。
• 系统当前状态。

当Leader要发给某个日志落后太多的Follower的log entry被丢弃，Leader会将snapshot发给Follower。或者当新加进一台机器时，也会发送snapshot给它。发送snapshot使用InstalledSnapshot RPC。

做snapshot既不要做的太频繁，否则消耗磁盘带宽，也不要做的太不频繁，否则一旦节点重启需要回放大量日志，影响可用性。推荐当日志达到某个固定的大小做一次snapshot。做一次snapshot可能耗时过长，会影响正常日志同步。可以通过使用copy-on-write技术避免snapshot过程影响正常日志同步。