Raft保证的safety

Leader Append-Only：leader从来不覆写或者删除日志，只会追加新日志。

Log Matching：如果两个主机的副本上的日志文件中，包含一条相同term和log id的entry，那么，这两个日志文件在这条日志之前的内容都是相同的（字节流级别的一致）。

Leader Completeness：如果一条日志已经commit了，那么这条日志一定会出现在term最大的leader的日志文件中。

State Machine Safety：如果一个主机应用了一条日志，那么，其他主机不可能应用一条相同log id而内容却不同的日志。

初选Leader后的日志同步

当一个新的Leader被选出来时，它的日志和其它的Follower的日志可能不一样，这个时候，就需要一个机制来保证日志的一致性。

主备不一致可能有如下几种情况：少了一些日志（term可能相同或者少了）；多了一些未commit的日志（term可能多了也可能少了）；某些term多了一些日志且某些term少了一些日志。Raft中如何解决这些不一致呢？leader强制让follower的日志文件复制leader的日志文件，即follower上不一致的日志文件内容被覆写

首先记住一个前提, raft选举保证选出来得leader拥有最新最多commit的日志。

因此leader只需要知道follower缺哪些日志（确定最后一条相同的日志），就可以主动给follower同步所缺的日志，follower只要覆盖掉不一致的部分即可。

如何确定不一致的点？

leader维护一个log id，初始为leader本地最大的log id，然后发送AppendEntries RPC到follower，follower在收到AppendEntries之后，检查RPC中携带的term和log id（leader上被追加的这条日志的前面一条日志的term和log id），如果follower本地没有这条日志，就拒绝此次AppendEntriesRPC，leader就能知道follower的同步点更靠前，逐渐就能知道同步点的位置。当然，实际实现时，会使用更有效率的方法。

例如，当附加日志 RPC 的请求被拒绝的时候，跟随者可以包含冲突的条目的任期号和自己存储的那个任期的最早的索引地址。借助这些信息，领导人可以减小 nextIndex 越过所有那个任期冲突的所有日志条目；这样就变成每个任期需要一次附加条目 RPC 而不是每个条目一次。在实践中，我们十分怀疑这种优化是否是必要的，因为失败是很少发生的并且也不大可能会有这么多不一致的日志。

image

1. 在阶段a，term为2，S1是Leader，且S1写入日志（term, index）为(2, 2)，并且日志被同步写入了S2；

2. 在阶段b，S1离线，触发一次新的选主，此时S5被选为新的Leader，此时系统term为3，且写入了日志（term, index）为（3， 2）;

3. S5尚未将日志推送到Followers变离线了，进而触发了一次新的选主，而之前离线的S1经过重新上线后被选中变成Leader，此时系统term为4，此时S1会将自己的日志同步到Followers，按照上图就是将日志（2， 2）同步到了S3，而此时由于该日志已经被同步到了多数节点（S1, S2, S3），因此，此时日志（2，2）可以被commit了（即更新到状态机）；

4. 在阶段d，S1又很不幸地下线了，系统触发一次选主，而S5有可能被选为新的Leader（这是因为S5可以满足作为主的一切条件：1. term = 3 > 2, 2. 最新的日志index为2，比大多数节点（如S2/S3/S4的日志都新），然后S5会将自己的日志更新到Followers，于是S2、S3中已经被提交的日志（2，2）被截断了，这是致命性的错误，因为一致性协议中不允许出现已经应用到状态机中的日志被截断。(论文描述)

这个问题的本质是，S1上的term=2,log id=2的日志，在进行复制时，使用的term仍然是term=2，而不是S1最新的term（4）。在本地term较大的时候去复制term小的日志，这个是不合理的。但是为了维持Leader Append-Only的性质，只能想办法解决。

为了避免这种致命错误，需要对协议进行一个微调：

只允许主节点提交包含当前term的日志

针对上述情况就是：即使日志（2，2）已经被大多数节点（S1、S2、S3）确认了，但是它不能被Commit，因为它是来自之前term(2)的日志，直到S1在当前term（4）产生的日志（4， 3）被大多数Follower确认，S1方可Commit（4，3）这条日志.

commit的时候并不需要发给followers，commit就是回复client。 leader只允许commit当前term的entry，其实是指积压着之前已经被majority认可的entry，直到当前term也被majority认可，然后统一commit。

日志压缩与快照

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响availability。Raft采用对整个系统进行snapshot来处理，snapshot之前的日志都可以丢弃。Snapshot技术在Chubby和ZooKeeper系统中都有采用。

Raft使用的方案是：每个副本独立的对自己的系统状态进行Snapshot，并且只能对已经提交的日志记录（已经应用到状态机）进行snapshot。

Snapshot中包含以下内容：

• 日志元数据，最后一条commited log entry的 (log index, last_included_term)。这两个值在Snapshot之后的第一条log entry的AppendEntriesRPC的consistency check的时候会被用上，之前讲过。一旦这个server做完了snapshot，就可以把这条记录的最后一条log index及其之前的所有的log entry都删掉。

• 系统状态机：存储系统当前状态（这是怎么生成的呢？）

snapshot的缺点就是不是增量的，即使内存中某个值没有变，下次做snapshot的时候同样会被dump到磁盘。当leader需要发给某个follower的log entry被丢弃了(因为leader做了snapshot)，leader会将snapshot发给落后太多的follower。或者当新加进一台机器时，也会发送snapshot给它。发送snapshot使用新的RPC，InstalledSnapshot。

做snapshot有一些需要注意的性能点，1. 不要做太频繁，否则消耗磁盘带宽。 2. 不要做的太不频繁，否则一旦节点重启需要回放大量日志，影响可用性。系统推荐当日志达到某个固定的大小做一次snapshot。3. 做一次snapshot可能耗时过长，会影响正常log entry的replicate。这个可以通过使用copy-on-write的技术来避免snapshot过程影响正常log entry的replicate。

客户端命令执行过程

1. 当Leader被选出来后，即可接受客户端发来的请求，每个请求包含一条需要被状态机执行的命令。leader会把它作为一个log entry append到日志中，然后给其它的server发AppendEntriesRPC请求。

2. 当Leader确定一个log entry被safely replicated了（大多数副本已经将该命令写入日志当中），就apply这条log entry到状态机中然后返回结果给客户端。

3. 如果某个Follower宕机了或者运行的很慢，或者网络丢包了，则会一直给这个Follower发AppendEntriesRPC直到日志一致。

当一条日志是commited时，Leader才可以将它应用到状态机中。Raft保证一条commited的log entry已经持久化了并且会被所有的节点执行。