日志复制
问题
- 目的是什么？ 保持集群中大多数服务器的状态一致。
- 复制过程的关键点是什么？处理日志不一致。
日志
日志由一个个顺序编号的日志项组成。每个日志项都存储了：
- 领导者接收到这个日志项时的任期编号。它可以用来探测不同服务器日志间的不一致，也确保了一些属性（待续）。
- 一个状态机命令。
- 一个整型索引，指定日志项在日志中的位置。
流程
领导者被选举出来后，就开始处理客户端的请求。
- 每个客户请求里都包含了一个命令，这个命令将被可复制状态机执行。
- 领导者把这个命令作为一个新的日志项追加到日志中，然后并行地发送
AppendEntries消息给其余的每一台服务器，把新的日志项复制给它们。 - 当这个日志项被安全地复制后（即领导者接收到大多数服务器的正确响应），领导者将这个日志项应用到自己的状态机，然后返回执行结果给客户端。
- 然后领导者发送
AppendEntries消息通知其他服务器，将这个日志项应用到各自的状态机。 - 如果跟随者宕机或网络包丢失，领导者会无限重发
AppendEntries消息（即使它已经响应了客户端），直到所有的跟随者最终存储了这个日志项。
客户端怎么知道哪台服务器是领导者呢？
其实，客户端无须知道谁是领导者，只要把请求发到集群中的任何一台服务器就行。一台服务器接收到请求后，先检查自己是不是领导者，如果不是，就把请求转发给领导者。
已提交日志
一旦日志项已经被领导者复制给了大多数服务器，我们称这个日志项是已提交的。这个也会提交所有先前的日志项，包括以前的领导者创建的。（因为可能出现大多数服务器已复制该日志项，但是还没提交，领导者就宕机的情况）
Raft保证已提交的条目是持久化的并且将最终会被所有可用的状态机执行。
领导者会跟踪已提交的日志项的最大索引。它会把这个索引包含在未来的 AppendEntries 消息中，以至于别的服务器最终能发现。一旦一个跟随者发现一个日志项已经被提交了，它就可以应用这个日志项到自己的状态机。
日志匹配特性
Raft 维护了下列特性，它们一起构成了 Log Matching Property，保证了不同服务器日志的高度一致性。
- 如果在不同日志中的两个条目有相同的索引和任期，那么它们保存了相同的命令。
- 如果在不同日志中的两个条目有相同的索引和任期，那么之前的所有条目也是相同的。
第一个特性来自于事实：在一个给定任期内，一个领导者在一个给定日志索引最多创建一个条目，并且日志项不会改变它们在日志中的位置。
第二个特性由 AppendEntries 消息执行的一致性检查来保证。当发送 AppendEntries 消息时，领导者会在消息中包含这个新的日志项前面一个日志项的索引和任期。如果跟随者没有在自己的日志中发现有相同的索引和任期的日志项，它就拒绝这个新的日志项。这个一致性检查表现的像归纳法步骤：日志的初始状态满足日志匹配特性，而当日志扩展时，一致性检查保证了日志匹配特性成立。因此，任何时候 AppendEntries 消息返回成功，领导者就知道跟随者的日志跟自己的日志在这个新的日志项及新的日志项之前是保持一致。
日志不一致
在正常运行时，领导者和跟随者的日志保持一致。但是，领导者宕机会使日志不一致，因为它可能还没有把自己日志中的所有条目复制给其他服务器。随着一系列领导者和跟随者宕机，这些不一致会互相混合。可能出现下列情况：
- 跟随者缺少领导者的某些日志项。
- 跟随者的日志中存在领导者没有的日志项。
- 跟随者同时出现以上两种情况。
在Raft中，领导者通过强制跟随者复制自己的日志来解决日志不一致的问题。这意味着跟随者日志中跟领导者冲突的日志项会被来自领导者的日志项覆盖。这个方法和选举中的一个约束来保证这样做是安全的。
- 领导者必须为每个跟随者维护一个
nextIndex，它是领导者发送给那个跟随者的下一个日志项的索引。 - 当一个领导者出现后，它初始化所有跟随者的
nextIndex为自己日志中最后一个日志项索引的下一个索引。 - 如果跟随者的日志跟领导者的不一致，那么下一个
AppendEntries消息的一致性检查就会失败。当这个消息被拒绝后，领导者就会减少这个跟随者的nextIndex，然后再尝试发送AppendEntries消息。 - 最终，
nextIndex会到达一个点，领导者和跟随者这个点之前的日志都是相同的。 - 这之后的
AppendEntries消息都将会成功（因为两者的日志相同，能通过一致性检查），跟随者日志中跟领导者冲突的日志项会被移除，并且将领导者的日志追加到跟随者的日志中（如果有的话）。一旦AppendEntries消息成功，跟随者的日志和领导者的日志就会保持一致（不懂就参考日志匹配特性的第二个特性）。
