Raft算法
如何复制日志
你可以把Raft算法的日志复制理解成一个优化后的二阶段提交(将二阶段优化成了一阶段)。优化后减少了一半的往返消息，也就是降低了一半的消息延迟，那日志复制的具体过程又是什么呢？
首先，领导者进入第一阶段，通过日志复制RPC消息将日志项复制到集群中的其他节点上。接着如果领导者接收到大多数的"复制成功"响应后，它会将日志项应用到它的状态机，并返回成功给客户端。如果领导者没有接收到大多数的"复制成功"响应，那么就返回错误给客户端。有人可能会有这样的疑问，领导者将日志项应用到它的状态机，为什么没有通知跟随者应用日志项呢？
这是Raft算法实现的一个优化，即领导者不需要直接发送消息通知其他节点应用指定日志项。因为领导者的日志复制RPC或心跳消息包含了当前最大的、将会被提交(Commit)的日志项索引值，所以通过日志复制RPC消息或心跳消息，跟随者就可以知道领导者的日志提交位置信息。
因此，当其他节点接收到领导者的心跳消息或者新的日志复制RPC消息后，它就会把这条日志项应用到它的状态机，从而降低了处理客户端请求一半的消息延迟。如图所示是Raft算法的日志复制的实现过程示意图。
- 1.接收到客户端请求后，领导者基于客户端请求中的指令创建一个新日志项，并附加到本地日志中
- 2.领导者通过日志复制RPC消息将新的日志项复制到其他服务器
- 3.当领导者将日志项成功复制到大多数的服务器上时，领导者会将这条日志项应用到它的状态机中
- 4.领导者将执行的结果返回给客户端
- 5.当跟随者接收到心跳信息或者新的日志复制RPC消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没应用，那么跟随者就会将这条日志项应用到本地的状态机中。
不过这是一个理想状态的日志复制。在实际环境中，你可能会遇到进程崩溃、服务器宕机等问题，导致日志不一致。那么在这种情况下，Raft算法是如何处理不一致，实现日志的一致的呢？
如何实现日志的一致性
在Raft算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。也就是说，Raft算法是通过以领导者的日志为准，来强制实现各节点日志的一致的。具体分为以下两个步骤。
- 1.领导者通过日志复制RPC消息的一致性检查，找到跟随者节点上与自己相同的日志项的最大索引值。也就是说，领导者和跟随者的日志在这个索引值之前是一致的，在之后的日志是不一致的。
- 2.领导者强制跟随者更新不一致的日志项，以实现日志的一致性。
下面我们来详细走一遍这个过程，如图苏轼，为了方便演示，我们引入两个新变量.
- 1.PrevLogEntry:表示当前要复制的日志项的前面一条日志项的索引值。比如在图中的，如果领导者将索引值为8的日志项发送给跟随者，那么此时PrevLogEntry值为7
- 2.PrevLogTerm:表示当前要复制的日志项的前面一条日志项的任期编号，比如图中的，如果领导者将索引值为8的日志项发送给跟随者，那么此时PrevLogTerm值为4
领导者处理不一致的具体实现过程分析如下:
- 1.领导者通过日志复制RPC消息，发送当前最新日志项到跟随者(为了演示方便，假设当前需要复制的日志项是最新的)，这个消息的PrevLogEntry值为7，PrevLogTerm值为4
- 2.如果跟随者在它的日志中找不到与PrevLogEntry值为7、PrevLogTerm值为4的日志项，也就是说它的日志和领导者的不一致，那么跟随者就拒绝接收新的日志项，并返回失败给领导者
- 3.这时，领导者会递减要复制的日志项的索引值，并发送新的日志项到跟随者，新的日志项的PrevLogEntry值为6，PrevLogTerm值为3.
- 4.如果跟随者在它的日志中找到了PrevLogEntry值为6、PrevLogTerm值为3的日志项，那么日志复制RPC消息返回成功，这样一来，领导者就知道在PrevLogEntry值为6、PrevLogTerm值为3的位置，跟随者的日志项与自己的日志项相同。
- 5.领导者通过日志复制RPC消息复制并更新该索引值之后的日志项(也就是不一致的日志项)，最终实现集群个节点日志的一致。
从上面步骤可以看到，领导者通过日志复制RPC消息的一致性检查，找到跟随者节点上与自己相同的日志项的最大所引致。然后复制并更新该索引值之后的日志项，实现各节点日志的一致。需要注意的是，跟随者中的不一致的日志项会被领导者的日志覆盖，而且领导者从来不会覆盖或者删除自己的日志。
