本文为《Raft 实战》系列第3篇，讲述什么是日志复制，以及 raft 如何通过日志复制实现状态复制机（状态复制机，也是分布式系统对外展现成统一视图及实现分布式一致性的基础）。
笔者期望通过该系列文章帮助读者深入理解 raft 协议并能付诸于工程实践中，同时解读不易理解或容易误解的关键点，看完不懂你来拍我 
！
系列历史链接：
------------
1. 什么是日志复制？
在前文中我们讲过：共识算法通常基于状态复制机（Replicated State Machine）模型，所有节点从同一个 state 出发，经过一系列同样操作 log 的步骤，最终也必将达到一致的 state。也就是说，只要我们保证集群中所有节点的 log 一致，那么经过一系列追加操作（apply）后最终得到的状态机也就是一致的。
Raft 负责保证集群中所有节点 log 的一致性。
此外我们还提到过：raft 赋予了 leader 节点更强的领导力（Strong Leader）。那么 raft 保证 log 一致的方式就很容易理解了，即所有操作（log）都必须交给 leader 节点处理（follewer 接收写操作会转交给 leader 处理），并由 leader 节点复制给其它节点，来保证整个集群的 log 实现层面的一致。
这个过程，就叫做日志复制（Log replication），更形象的名称就是“日志复制机”。
2. Raft 日志复制机制解析
2.1 整体流程解析
一旦 leader 被票选出来，它就承担起领导整个集群的责任了，开始接收客户端请求，并将操作包装成日志，并复制到其它节点上去。
整体流程如下：
1. Leader 为客户端提供服务，客户端的每个请求都包含一条即将被状态复制机执行的指令。
2. Leader 把该指令作为一条新的日志附加到自身的日志集合，然后向其它节点发起附加条目请求（AppendEntries RPC），来要求它们将这条日志附加到各自本地的日志集合。
3. 当这条日志已经确保被安全的复制，即大多数（N/2+1）节点都已经复制后，leader 会将该日志 apply 到它本地的状态机中，然后把操作成功的结果返回给客户端。
整个集群的日志模型可以宏观表示为下图（x ← 3 代表x赋值为3 ）：
Raft集群日志模型
每条日志除了存储状态机的操作指令外（譬如 x ← 3 这种赋值指令，代表 x 赋值为3），还会拥有一个唯一的整数索引值（log index）来表明它在日志集合中的位置。此外，每条日志还会存储一个 term 号（日志条目方块最上方的数字，相同颜色 term 号相同），该 term 表示 leader 收到这条指令时的当前任期，term 相同的 log 是由同一个 leader 在其任期内发送的。
当一条日志被 leader 节点认为可以安全的 apply 到状态机时，称这条日志是committed（上图中的committed entries）。那么什么样的日志可以被 commit 呢？答案是：当 leader 得知这条日志被集群过半的节点复制成功时。因此在上图中我们可以看到 (term3, index7) 这条日志以及之前的日志都是 committed，尽管有两个节点拥有的日志并不完整。
Raft 保证所有 committed 日志都已经被持久化，且“最终”一定会被状态机apply。
注：这里的“最终”用词很微妙，它表明了一个特点：Raft保证的只是日志的一致性，而我们真正期望的状态机的一致性需要我们做一些额外工作，这一点在后续《线性一致性与性能优化》一篇会着重介绍。
2.2 Raft 日志复制流程图解
我们通过 raft 动画（https://raft.github.io/）来模拟常规日志复制这一过程：
图1
如图1，S1 当选 leader，此时还没有任何日志。我们模拟客户端向 S1 发起一个请求。
图2
如图2，S1 收到客户端请求后新增了一条日志 (term2, index1)，然后并行地向其它节点发起 AppendEntries RPC。
图3
如图3，S2、S4 率先收到了请求，各自附加了该日志，并向 S1 回应响应。
图4
如图4，所有节点都附加了该日志，但由于 leader 尚未收到任何响应，因此暂时还不清楚该日志到底是否被成功复制。
图5
如图5，当 S1 收到2个节点的响应时，该日志条目的边框就已经变为实线，表示该日志已经安全的复制，因为在5节点集群中，2个 follower 节点加上 leader 节点自身，副本数已经确保过半，此时 S1 将响应客户端的请求。
图6
如图6，leader 后续会持续发送心跳包给 followers，心跳包中会携带当前已经安全复制（我们称之为 committed）的日志索引，此处为 (term2, index1)。
图7
如图7，所有 follower 都通过心跳包得知 (term2, index1) 的 log 已经成功复制 （committed），因此所有节点中该日志条目的边框均变为实线。
2.3 Raft 对日志一致性的保证
前边我们使用了 (term2, index1) 这种方式来表示一条日志条目，这里为什么要带上 term，而不仅仅是使用 index？原因是 term 可以用来检查不同节点间日志是否存在不一致的情况，阅读下一节后会更容易理解这句话。
Raft 保证：如果不同的节点日志集合中的两个日志条目拥有相同的 term 和 index，那么它们一定存储了相同的指令。
为什么可以作出这种保证？因为 raft 要求 leader 在一个 term 内针对同一个 index 只能创建一条日志，并且永远不会修改它。
同时 raft 也保证：如果不同的节点日志集合中的两个日志条目拥有相同的 term 和 index，那么它们之前的所有日志条目也全部相同。
这是因为 leader 发出的 AppendEntries RPC 中会额外携带上一条日志的 (term, index)，如果 follower 在本地找不到相同的 (term, index) 日志，则拒绝接收这次新的日志。
所以，只要 follower 持续正常地接收来自 leader 的日志，那么就可以通过归纳法验证上述结论。
2.4 可能出现的日志不一致场景
在所有节点正常工作的时候，leader 和 follower的日志总是保持一致，AppendEntries RPC 也永远不会失败。然而我们总要面对任意节点随时可能宕机的风险，如何在这种情况下继续保持集群日志的一致性才是我们真正要解决的问题。
日志不一致的场景
上图展示了一个 term8 的 leader 刚上任时，集群中日志可能存在的混乱情况。例如 follower 可能缺少一些日志（a~b），可能多了一些未提交的日志（c~d），也可能既缺少日志又多了一些未提交日志（e~f）。
注：Follower 不可能比 leader 多出一些已提交（committed）日志，这一点是通过选举上的限制来达成的，会在下一篇Safety部分介绍。
我们先来尝试复现上述a~f场景，最后再讲 raft 如何解决这种不一致问题。
场景a~b. Follower 日志落后于 leader
这种场景其实很简单，即 follower 宕机了一段时间，follower-a 从收到 (term6, index9) 后开始宕机，follower-b 从收到 (term4, index4) 后开始宕机。这里不再赘述。
场景c. Follower 日志比 leader 多 term6
当 term6 的 leader 正在将 (term6, index11) 向 follower 同步时，该 leader 发生了宕机，且此时只有 follower-c 收到了这条日志的 AppendEntries RPC。然后经过一系列的选举，term7 可能是选举超时，也可能是 leader 刚上任就宕机了，最终 term8 的 leader 上任了，成就了我们看到的场景 c。
场景d. Follower 日志比 leader 多 term7
当 term6 的 leader 将 (term6, index10) 成功 commit 后，发生了宕机。此时 term7 的 leader 走马上任，连续同步了两条日志给 follower，然而还没来得及 commit 就宕机了，随后集群选出了 term8 的 leader。
场景e. Follower 日志比 leader 少 term5~6，多 term4
当 term4 的 leader 将 (term4, index7) 同步给 follower，且将 (term4, index5) 及之前的日志成功 commit 后，发生了宕机，紧接着 follower-e 也发生了宕机。这样在 term5~7 内发生的日志同步全都被 follower-e 错过了。当 follower-e 恢复后，term8 的 leader 也刚好上任了。
场景f. Follower 日志比 leader 少 term4~6，多 term2~3
当 term2 的 leader 同步了一些日志（index4~6）给 follower 后，尚未来得及 commit 时发生了宕机，但它很快恢复过来了，又被选为了 term3 的 leader，它继续同步了一些日志（index7~11）给 follower，但同样未来得及 commit 就又发生了宕机，紧接着 follower-f 也发生了宕机，当 follower-f 醒来时，集群已经前进到 term8 了。
2.5 如何处理日志不一致
通过上述场景我们可以看到，真实世界的集群情况很复杂，那么 raft 是如何应对这么多不一致场景的呢？其实方式很简单暴力，想想 Strong Leader 这个词。
Raft 强制要求 follower 必须复制 leader 的日志集合来解决不一致问题。
也就是说，follower 节点上任何与 leader 不一致的日志，都会被 leader 节点上的日志所覆盖。这并不会产生什么问题，因为某些选举上的限制，如果 follower 上的日志与 leader 不一致，那么该日志在 follower 上一定是未提交的。未提交的日志并不会应用到状态机，也不会被外部的客户端感知到。
要使得 follower 的日志集合跟自己保持完全一致，leader 必须先找到二者间最后一次达成一致的地方。因为一旦这条日志达成一致，在这之前的日志一定也都一致（回忆下前文）。这个确认操作是在 AppendEntries RPC 的一致性检查步骤完成的。
Leader 针对每个 follower 都维护一个 next index，表示下一条需要发送给该follower 的日志索引。当一个 leader 刚刚上任时，它初始化所有 next index 值为自己最后一条日志的 index+1。但凡某个 follower 的日志跟 leader 不一致，那么下次 AppendEntries RPC 的一致性检查就会失败。在被 follower 拒绝这次 Append Entries RPC 后，leader 会减少 next index 的值并进行重试。
最终一定会存在一个 next index 使得 leader 和 follower 在这之前的日志都保持一致。极端情况下 next index 为1，表示 follower 没有任何日志与 leader 一致，leader 必须从第一条日志开始同步。
针对每个 follower，一旦确定了 next index 的值，leader 便开始从该 index 同步日志，follower 会删除掉现存的不一致的日志，保留 leader 最新同步过来的。
整个集群的日志会在这个简单的机制下自动趋于一致。此外要注意，leader 从来不会覆盖或者删除自己的日志，而是强制 follower 与它保持一致。
这就要求集群票选出的 leader 一定要具备“日志的正确性（原文是 Safety，但用“正确性”可以帮大家更好理解）”，这也就是前文提到的：选举上的限制。
下一篇文章我们将对此详细讨论。
