Raft(三) log replication

日志复制模块

日志结构

我们可以看到第一个节点是leader，其他是follower，图中最后一个节点所包含的log entries就可以看做committed entries。

committed entries：在领导人将创建的日志条目复制到大多数的服务器上的时候，日志条目就会被提交了。

领导人跟踪了最大的将会被提交的日志项的索引，并且索引值会被包含在未来的所有附加日志 RPCs （包括心跳包），这样其他的服务器才能最终知道领导人的提交位置。一旦跟随者知道一条日志条目已经被提交，那么他也会将这个日志条目应用到本地的状态机中（按照日志的顺序）。

我们先不考虑任何宕机，网络丢包，分区等因素造成的错误！
一旦一个领导人被选举出来，他就开始为客户端提供服务

从此处开始讲各种容错机制，首要谈的就是Raft的日志匹配特性。

Raft维护着以下的特性:

下面阐述的是对以上两条的保证：

领导人最多在一个任期里在指定的一个日志索引位置创建一条日志条目，同时日志条目在日志中的位置也从来不会改变
附加日志 RPC 的一个简单的一致性检查所保证。在发送附加日志 RPC 的时候，领导人会把新的日志条目紧接着之前的条目的索引位置和任期号包含在里面（preLogIndex,preLogTerm）如果跟随者在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝接收新的日志条目。

一致性检查就像一个归纳步骤：一开始空的日志状态肯定是满足日志匹配特性的，然后一致性检查保护了日志匹配特性当日志扩展的时候。因此，每当附加日志 RPC 返回成功时，领导人就知道跟随者的日志一定是和自己相同的了。

上图是不是五颜六色，有长有短、各种数字。下面会对Raft算法在复制过程出现的不一致情况进行分析。

如上图所示，各种节点所持久化的日志可能不尽相同
原因:网络、运行缓慢、follower宕机、leader宕机导致选举重选

a、b可能是运行缓慢，再或者网络丢包、或者崩溃（缺失部分log）
c、d有可能曾经是leader，收到了client指令请求，但是还没有来得及发送给其他follower复制日志的请求，就崩溃了（比leader的log多）
而e、f是两种情况都存在的（既多也少），就f这样的情况，可能在第二任期是leader，复制了一些请求到本地log，没来得及发送复制请求，崩溃了；崩溃的时间很短，恢复后成为了任期3的leader，然后又复制了一些请求到log，依旧还是在提交前崩溃了，之后就一直处在宕机的状态。

在 Raft 算法中，领导人处理不一致是通过强制跟随者直接复制自己的日志来解决了。

具体细节：

领导人针对每一个跟随者维护了一个nextIndex数组，这表示下一个需要发送给跟随者的日志条目的索引地址。
刚上任时，初始化nextIndex数组为本地log的下一个

如图，任期8刚上任的leader，nextIndex[11,11,11,11,11,11]
一致性检查：发送prevLogIndex、prevLogTerm，如果不匹配，拒绝leader的请求；如果匹配就返回一个成功确认，进行附加日志的操作。
e.g 发送给{prevLogIndex：10、prevLogTerm：6…}给a，而a发现本地日志里index为10的并不存在，拒绝此次附加日志RPC
在被follower拒绝之后，leader就会减小 nextIndex 值并进行重试。最终nextIndex会在某个位置使得leader和follower的日志达成一致。
在某个位置达成一致后，附加日志RPC成功，这时就会把follower冲突的日志条目全部删除并且加上领导人的日志。
e.g leader与f冲突的位置 index为4，f中从index4开始删除，然后附加上leader index为4以后的日志。

当然follower拒绝leader的rpc后，leader缩小index重试，这个过程是可以优化的，当附加日志 RPC的请求被拒绝的时候，跟随者可以包含冲突的条目的任期号和自己存储的那个任期的最早的索引地址。通过减少被拒绝的附加日志 RPCs 的次数来优化

但是论文中说这种优化可能不是那么中重要。

领导人在获得权力的时候就不需要任何特殊的操作来恢复一致性。他只需要进行正常的操作，然后日志就能自动的在回复附加日志 RPC 的一致性检查失败的时候自动趋于一致。领导人从来不会覆盖或者删除自己的日志(领导人只附加特性)

由领导人负责调用来复制日志指令；也会用作heartbeat