Part 06：Raft论文翻译-《CONSENSUS BRIDGING THEORY AND PRACTICE》（基础Raft-Log副本机制）
3.5 Log Replication（日志副本）
一旦选出了一个Leader，它就开始为客户的请求提供服务。每个客户端请求都包含一个要由已复制的状态机执行的命令。引导将命令作为新的log entry附加到日志中，然后与其他服务器并行发布AppendEntries rpc消息/请求以复制该log entry。当log entry被安全复制后（如下所述，也就是大多数的Follower已经复制了这个log entry，这是这个log entry已经处于commited的状态了），Leader就在本地的状态机上apply这个log entry然后回复客户端执行结果。如果Follower崩溃或运行缓慢，或者网络数据包丢失，Leader将重新尝试AppendEntries RPC（即使在它响应了客户端之后），直到所有Follower最终存储所有log entry。（这里有几个问题，如果Leader apply这个log entry失败怎么办？它怎么回复客户端？然后就是这个apply失败的log entry怎么处理？） （理论上，已经commit的log entry最终一定会被apply，但是Leader是等确认apply成功后返回？还是apply失败一次后就回复客户端？如果是等待apply成功的再回复的话，是不是响应时间过长？如果失败就回复失败，那么这个已经commit的log entry就需要撤销，但是Leadr应该不会删除自己的log entry的，没记错的话，而且这相当于回滚，会增加算法复杂度。个人估计还是第一种策略可能性大，看看后面的文章内容有没有这块的描述）
Log的组织方式如图3.5所示。当Leader收到一个客户端的command时，Leader将在相应的log entry里存储这个command和对应的term。log entry中的term用于检测log之间的不一致，并确保图3.2中的一些属性。每个log entry也有一个整数索引index，标识其在日志中的位置。
Leader判断何时在状态机apply这个log entry是安全的（这里安全的意思就是这个log entry已经被commit，而某个log entry是否被commit的是通过其被复制的状态来决定的，即如果集群中超过半数的服务器在相应的位置复制了这个log entry，那么这个log entry就处于了“已提交状态”（commited），这时候，Leader在其状态机上apply这个log entry就是安全的）。Raft保证已提交的log entry是持久化存储的，一旦某个log entry被commit了，那么在这个log entry之前的所有log entry都将处于commited状态，包括前任Leader创建的log entry。第3.6节讨论了在Leader变更后应用此规则时的一些微妙之处，它也表明了该承诺的定义是安全的。Leader将跟踪它知道要commit的最高的log entry的index，并在未来的AppendEntries RPC（包括心跳）中包括该index，以便其他服务器最终发现。一旦Follower得知某个log entry已经被commit，Follower将该log entry apply于其本地状态机（按日志顺序）。（这里一个Follower如何指导现在那个log entry被commit了？Leader知道哪个log entry需要commit，所以也知道哪些log entry已经被commit了，如前面说的，Leader在AppendEntries RPC中会携带需要Follower复制的log entry的index，这个RPC过程中，Leader会和Follower沟通以确定Follower中合法的已经commit的最新的log entry的index。这就保证了Follower确定自己已经commit的log entry，那么这个log entry以及之前的log entry都可以被apply至Follower的状态机了。但是Follower怎么知道从那个log entry的index开始apply呢？前面说到的，每个服务器会保存本地信息有一个lastApplied变量，这个变量就存储了这个服务器已经apply的最新的log entry的index，这样起始位置都确定了，Follower可以将起始及之间的log entry apply到自己的状态机了。）
我们设计了Raft的日志机制来保持不同服务器上的日志之间的高度一致性。这不仅简化了系统的行为，使其更可预测，而且它是确保安全的一个重要组成部分。Raft维护了以下属性，它们共同构成了图3.2中的日志匹配属性：
（1）如果两个服务器上的两个log entry具有相同的term和log entry index，那么这两个log entry里面存储的command是一样的；
（2）如果两个服务器上的两个log entry具有相同的term和log entry index，那么这两个log entry之前的所有log entry一定是一样的。
第一个属性，因为在某个term内Leader每次只会产生一个log entry，而且log entry不会在log中改变位置。
第二个属性，由AppendEntries RPC的沟通机制来保证。
当发送AppendEntries RPC时，Leader将在RPC消息中携带需要同步的log entry（也可能是一组，为了提升性能）以及这个（或这些）log entry前面那个log entry的index，如果Follower在自己的log中没有找到这个index，那么就说明Follower的最新的日志还在这个index之前，并且Follower会拒绝这个RPC请求指导这个index比较成果，Follower回复同意请求。Raft算法中初始状态的log全部为空，以及后面每次AppendEntries RPC的匹配检测保证了日志一致性。也就是说只要AppendEntries RPC收到成功的回复，那么Leader就知道这个Follower在这个index之前的log entry是与自己的是一样的（包括这个index所在的log entry）。
在正常操作过程中，Leader和Follower的日志保持一致，因此AppendEntries RPC我一致性检查永远不会失败。但是，Leader崩溃可能会导致日志不一致（旧的Leader可能没有完全复制其日志中的所有log entry）。这些不一致可能会在一系列的Leader和Follower的碰撞中发生叠加。图3.6说明了Follower日志与新Leader日志的不同方式。Follower可能缺少Leader存在的log entry，它可能拥有Leader上没有的log entry，或者两者都有可能。日志中缺少和无关的条目可能跨越多个term。
在Raft中，Leader通过强迫Follower复制自己的日志来处理不一致。这意味着Follower日志中的冲突log entry将被Leader日志中的相应的log entry所覆盖。第3.6节将表明，如果再加上限制选举，这一点是安全的。（这里选举的一些限制就限制了新Leader日志的合法性，保证了算法的安全性，后面内容会叙述这些限制。）
要使Follower的日志与自己的日志保持一致，Leader必须找到两个日志一致的最新的那个log entry的index，删除Follower日志中这个index之后的所有其它log entry，并在此之后将此index之后的所有log entry同步给给Follower。所有这些操作都是为了满足AppendEntries RPC执行的一致性检查。Leader为每个Follower维护一个nextIndex，这个nextIndex就是Leader将要在下一次AppendEntries RPC中发送给Follower的log entry的index。当某个Leader刚刚胜选成为新Leader时，Leader将每个Follower的nextIndex设置成为自己的最新的log entry后面那个log entry的index（在图3.6中，这个nextIndex=11）。然后，Leader通过AppendEntries RPC与其它的Follower来同步这个nextIndex并更新自己的nextIndex的值。然后Leader和Follower之间就通过AppendEntries RPC同步log entry并在以后就按照这个方案继续同步（这里就不在赘述AppendEntries RPC的逻辑过程了，前面已经讲过了）。
在Leader发现它和Follower的日志匹配的位置之前，Leader可以发送没有log entry的AppendEntries RPC（如心跳）来节省带宽。然后，一旦发现matchIndex在nextIndex之前，Leader应该开始发送log entry。
如果需要，可以优化协议，以减少被拒绝的AppendEntries RPC的次数。例如，当拒绝AppendEntries RPC请求时，Follower可以在回复中携带这个冲突的log entry的term。有了这些信息，Leader可以减少AppendEntries RPC请求，以绕过该term中的所有冲突log entry；每个有冲突的log entry的term将需要一个AppendEntries RPC，而不是每个log entry需要一个AppendEntries RPC。或者，Leader可以使用二进制搜索方法来查找Follower日志不同的第一个log entry；这有更好的最坏情况行为。在实践中，我们怀疑这些优化是否必要，因为失败很少发生，也不太可能有许多不一致的log entry。**（这是对log日志匹配的一种性能优化手段）**
使用这种机制，Leader在通电时不需要采取任何特殊操作来恢复日志一致性。它刚刚开始正常操作，日志会随着AppendEntries RPC的一致性检查的失败而自动收敛。Leader永远不会覆盖或删除自己日志中的log entry（图3.2中的Leader具有“仅追加”log entry的属性）。
此日志复制机制显示了第2.1节中描述的理想一致属性：只要大多数服务器启动，Raft就可以accept、replicate和apply新log entry；在正常情况下，新log entry可以通过单轮AppendEntries RPC复制到大多数集群；一个慢的Follower不会影响性能。日志复制算法也很实用，因为AppendEntries RPC请求的大小是可管理的（Leader从来不需要在一个AppendEntries RPC请求中发送多个log entry）。其他一些共识算法被描述为通过网络发送整个日志；这给实现者带来了开发实际实现所需的优化的负担。
