raft论文学习-log replication

日志复制

当leader被选举出来之后，就可以为客户端提供写入和读取服务了。客户端的每个请求都包含一条指令，该指令将会被状态机执行。leader收到客户端发来的指令之后，会做下面几个动作：

1. 将指令作为一个新的条目追加到日志里面
2. 并发的发出AppendEntries RPC消息给其他的节点
3. 当2中的条目被安全的复制之后，leader会应用该条目到自己的状态机中
4. 返回给客户端执行的结果

日志结构如下，包含状态指令、任期号和索引三部分。状态指令为业务层的增删改操作,例如 x <- 3. 任期号为leader收到该指令时的任期值，索引用于指明每个日志条目在日志中的位置。

下图中集群包含5个节点，每个小方框中的x<-3，y<-3是状态指令，方框中的1、2和3表示任期，最上面的1到8位日志索引。

下面为日志Entry的数据结构定义(来自 etcd/raft/raftpb/raft.pb.go)，除了包含上面介绍的日志结构包含的三个部分，还有一个Type字段表示日志的类型，该字段用于区分该条Entry是普通数据操作还是集群变更操作。

type Entry struct {
 // 任期
 Term  uint64    `protobuf:"varint,2,opt,name=Term" json:"Term"`
 // 日志索引
 Index uint64    `protobuf:"varint,3,opt,name=Index" json:"Index"`
 // 有3中类型，分别表示普通数据操作，集群变更操作，集群变更操作V2
 Type  EntryType `protobuf:"varint,1,opt,name=Type,enum=raftpb.EntryType" json:"Type"`
 // 日志数据
 Data  []byte    `protobuf:"bytes,4,opt,name=Data" json:"Data,omitempty"`
}

前面说了每条日志都包含任期和日志索引信息，那它们的值在哪里设置的呢？客户端发出的状态指令只是业务数据，里面是不包含任期和索引信息的。客户端发出的状态指令可能被follower节点或leader节点接收，如果是follower节点接收，它会转发给leader节点，无论如何状态指令都会到达leader节点。任期和日志索引信息值添加是在leader节点中的appendEntry方法中添加的，见下面的代码，可以看到Index值是连续增加的。

// raft.go
func (r *raft) appendEntry(es ...pb.Entry) (accepted bool) {
 li := r.raftLog.lastIndex()
 for i := range es {
  // 设置日志条目的任期值和索引值，即向es中添加Term和Index
  // 日志条目从客户端发过来的时候，只有es.Data和es.Type有填充
  // 内容，经过这里的处理之后，es中所有的字段值都有了
  es[i].Term = r.Term
  es[i].Index = li + 1 + uint64(i)
 }
 ...
 return true
}

如果leader成功将日志复制到超过一半的节点上，这个日志为已提交日志(committed entries)，raft算法保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行，结合下面的图示加以理解。

为了维持不同节点之间日志的一致性，raft算法维护着下面两个特性：

• 如果不同日志中的两个条目拥有相同的索引和任期号，那么它们存储了相同的指令
• 如果不同日志中的两个条目拥有相同的索引和任期号，那么它们之前的所有日志条目也都相同

leader在特定的任期号内的一个日志索引位置最多创建一个日志条目，该特性保证了每条日志的{term,index}是唯一的。如果两个不同的日志条目它们的{term,index}是相同的，那么它们存储的相同的状态指令。对应到下面的entry1和entry2，它们的Term和Index值是相同的，那么它们的Data值也是相同的。这个点保证了上面的特性1，不会存在一个Term+Index对应多个日志数据的情况。

entry1:=Entry{Term:1,Index:3,Data:[]byte{...}}
entry2:=Entry{Term:1,Index:3,Data:[]byte{...}}

follower节点会对收到的AppendEntries RPC做一个一致性检查来保证上面的特性2，具体来说就是，在leader发送AppendEntries RPC时会将前一个日志条目中的索引位置和任期号包含在里面。如果follower在它的日志中找不到包含相同索引位置和任期号的条目，它会拒绝此新的日志条目。这个处理其实是数学中的归纳法：一开始空的日志状态肯定是满足特性2的，随后每增加一个日志条目时，都要求上一个日志条目信息与leader一致，那么最终整个日志集肯定是一致的。

节点之间消息传递是放在下面的Message对象中的，像上面说的AppendEntries RPC消息。前一个日志条目中的索引位置和任期号就是Message结构体中的LogTerm和Index字段，Message中的Entries是存放日志条目的。

type Message struct {
...
 // 下面Index索引值对应的日志的所在的任期
 LogTerm    uint64   `protobuf:"varint,5,opt,name=logTerm" json:"logTerm"`
 // follower节点之前已收到的日志条目的索引的最大值
 Index      uint64   `protobuf:"varint,6,opt,name=index" json:"index"`
 // 日志条目集合
 Entries    []Entry  `protobuf:"bytes,7,rep,name=entries" json:"entries"`
...
}

在正常情况下，follower节点和leader节点的日志保持一致，所以follower节点对AppendEntries RPC一致性检查不会失败。然而，leader崩溃的情况会使日志处于不一致的状态。比如旧的leader可能还没有完全复制完它里面的所有日志条目，甚至在一系列leader和follower节点崩溃的情况更槽糕，下图展示了这些情况。

上图中最上面的一行是leader成功当选时候的日志，图中格子中的数字表示任期号，follower节点可能是a-f中的任意一种情况。a和b是缺少日志条目的情况，a缺少Index为10的日志，b缺少Index在[5,10]范围内的日志。c和d是存在未提交日志条目的情况，c存在未提交的Index为11的日志，d存在未提交的Index为11和12的日志。e和f是缺少日志和存在未提交的日志都有的情况，e缺少Index在[6,10]范围内的日志，多了Index为6和7的任期值为4的日志。f的情况可能是这样产生的，f节点在任期2的时候是leader，追加了一些日志条目到自己的日志中，一条都还没提交(commit)就崩溃了，该节点很快重启，在任期3又被重新当选为leader，又追加了一些日志条目到自己的日志中。在任期2和任期3中的日志都还没提交之前，该节点又宕机了，并且在接下来的任期里面一直处于宕机状态。

raft算法通过强制follower节点复制leader节点的日志来解决不一致问题。那现在就有一个问题，leader节点怎么知道从哪个日志索引位置发送日志条目给follower，以及follower已经复制的日志最大索引值是多少？

leader对每个follower节点都维护了一个nextIndex和一个matchIndex字段，nextIndex表示leader要发送给follower的下一个日志条目的索引, matchIndex表示follower节点已复制的最大日志条目的索引。要使得follower的日志跟leader的一致，leader必须找到两者达成一致的最大的日志条目，删除follower日志中从最大日志条目所在索引之后的所有日志条目，并将自己从最大日志条目索引之后的日志发送给follower.

当选出一个新的leader时，该leader将所有nextIndex的值都初始化为自己最后一个日志条目的index+1. 如果follower的日志和leader的不一致，在下一次AppendEntries RPC中的一致性检查就会失败，在follower拒绝之后，leader会减小nextIndex值并重试AppendEntries RPC. 最终nextIndex的值会在某个位置，leader和follower在此处达成一致，此时AppendEntries RPC成功，follower会将跟leader冲突的日志条目全部删除然后追加leader中的日志条目(如果需要追加的话)。追加成功后，follower的日志和leader就一致了，并且在该任期接下来的时间里保持一致。

通过上述机制，leader在当选之后不需要进行任何特殊的操作便可以将日志恢复到一致状态。leader只需要进行正常的appendEntries RPC，然后日志就能在回复AppendEntries一致性检查失败的时候自动趋于一致，leader从来不会覆盖或者删除自己的日志条目。