etcd系列-----raft协议：理论基础篇（二）-------日志复制

71 阅读 0 评论 47 点赞

我是靠谱客的博主包容板栗，最近开发中收集的这篇文章主要介绍etcd系列-----raft协议：理论基础篇（二）-------日志复制，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

通过前面介绍的Leader选举过程，集群中最终会选举出一个Leader节点，而集群中剩余的其他节点将会成为Follower节点。 Leader节点除了向Follower节点发送心跳消息，还会处理客户端的请求，并将客户端的更新操作以消息（AppendEntries消息）的形式发送到集群中所有的Follower节点。当Follower节点记录收到的这些消息之后，会向Leader节点返回相应的响应消息。当Leader节点在收到半数以上的Follower节点的响应消息之后，会对客户端的请求进行应答。最后，Leader会提交客户端的更新操作，该过程会发送Append Entries消息到Follower节点，通知Follower节点该操作己经提交，同时Leader节点和Follower节点也就可以将该操作应用到自己的状态机中。

为了方便描述，我们依然假设当前集群中有三个节点（A、 B、 C），其中A是Leader节点， B、 C是Follower节点，此时有一个客户端发送了一个更新操作到集群，如图1所示。前面提到过，集群中只有Leader节点才能处理客户端的更新操作，这里假设客户端直接将请求发给了节点A。当收到客户端的请求时，节点A会将该更新操作记录到本地的Log中，如图2所示。

之后，节点A会向其他节点发送AppendEntries消息，其中记录了Leader节点最近接收到的请求日志，如图1所示。集群中其他Follower节点收到该AppendEntries消息之后，会将该操作记录到本地的Log中，并返回相应的响应消息，如图2所示。

当Leader节点收到半数以上的响应消息之后，会认为集群中有半数以上的节点已经记录了该更新操作， Leader 节点会将该更新操作对应的日志记录设置为己提交（committed），并应用到自身的状态机中。同时Leader节点还会对客户端的请求做出响应，如图1所示。同时，Leader节点也会向集群中的其他Follower节点发送消息，通知它们该更新操作己经被提交，Follower节点收到该消息之后，才会将该更新操作应用到自己的状态机中，如图2所示。

在上述示例的描述中我们可以看到，集群中各个节点都会维护一个本地Log用于记录更新操作，除此之外，每个节点还会维护commitlndex和lastApplied两个值，它们是本地Log的索引值，其中commitlndex表示的是当前节点已知的、最大的、己提交的日志索引值，lastApplied表示的是当前节点最后一条被应用到状态机中的日志索引值。当节点中的commitlndex值大于lastApplied值时，会将lastApplied 加l，并将lastApplied对应的日志应用到其状态机中。

在Leader节点中不仅需要知道自己的上述信息，还需要了解集群中其他Follower节点的这些信息，例如，Leader节点需要了解每个Follower节点的日志复制到哪个位置，从而决定下次发送Append Entries 消息中包含哪些日志记录。为此，Leader 节点会维护nextlndex［］和matchlndex［］两个数组，这两个数组中记录的都是日志索引值，其中nextlndex［］数组记录了需要发送给每个Follower 节点的下一条日志的索引值，matchlndex［］表示记录了己经复制给每个Follower节点的最大的日志索引值。

这里简单看一下Leader 节点与某一个Follower 节点复制日志时，对应nextlndex 和matchlndex值的变化：Follower节点中最后一条日志的索引值大于等于该Follower节点对应的nextlndex值，那么通过Append Entries 消息发送从nextlndex开始的所有日志。之后，Leader节点会检测该Follower 节点返回的相应响应，如果成功则更新相应该Follower 节点对应的nextlndex值和matchlndex值；如果因为日志不一致而失败，则减少nextlndex值重试。

下面我们依然通过一个示例来说明nextlndex[]和matchlndex［］在日志复制过程中的作用，假设集群现在有三个节点，其中节点A是Leader节点（Term=l ），而Follower节点C因为宕机导致有一段时间未与Leader节点同步日志。此时，节点C的Log中并不包含全部的己提交日志，而只是节点A的Log的子集，节点C故障排除后重新启动，当前集群的状态如图所示（这里只关心Log、 nextlndex［］、 matchlndex［］，其他的细节省略，另外需要注意的是，图中的Term=l表示的是日志发送时的任期号，而非当前的任期号）。

A作为Leader节点，记录了nextlndex[]和matchlndex[]，所以知道应该向节点C发送哪些日志，在本例中， Leader节点在下次发送Append Entries消息时会携带Index=2的消息（这里为了描述简单，每条消息只携带单条日志， Raft协议采用批量发送的方式，这样效率更高），如图1所示。当节点C收到AppendEntries消息后，会将日志记录到本地Log中，然后向Leader 节点返回追加日志成功的响应，当Leader 节点收到响应之后，会递增节点C对应的nextlndex和matchlndex，这样Leader节点就知道下次发送日志的位置了，该过程如图2所示。

在上面所述中，当Leader节点并未发生过切换，所以Leader节点始终准确地知道节点C对应nextlndex值和matchlndex值。如果在上述示例中，在节点C故障恢复后，节点A宕机后重启，并且导致节点B成为新任期（Term=2）的Leader节点，则此时节点B并不知道旧Leader节点中记录的nextlndex［］和matchlndex[]信息，所以新Leader节点会重置nextlndex［］和matchlndex［］，其中会将nextlndex[]全部重置为其自身Log的最后一条己提交日志的Index值，而matchlndex［］全部重置为0，如图所示。

随后，新任期中的Leader节点会向其他节点发送AppendEntries 消息，如图1所示，节点A己经拥有了当前Leader的全部日志记录，所以会返回追加成功的响应并等待后续的日志，而节点C并没有Index=2和Index=3两条日志，所以返回追加日志失败的响应，在收到该响应后， Leader节点会将nextindex前移，如图2所示。

然后新Leader节点会再次尝试发送Append Entries 消息，循环往复，不断减小nextlndex值，直至节点C返回追加成功的响应，之后就进入了正常追加消息记录的流程，不再赘述。

了解了Log 日志及节点中基本的数据结构之后，再回顾前面描述的选举过程，其中Follower节点的投票过程并不像前面描述的那样简单（先收到哪个Candidate节点的选举请求，就将选票投给哪个Candidate节点），Follower节点还需要比较该Candidate节点的日志记录与自身的日志记录，拒绝那些日志没有自己新的Candidat巳节点发来的投票请求，确保将选票投给包含了全部己提交（commited）日志记录的Candidate 节点。这也就保证了己提交的日志记录不会丢失： Candidate节点为了成为Leader节点，必然会在选举过程中向集群中半数以上的节点发送选举请求，因为己提交的日志记录必须存在集群中半数以上的节点中，这也就意味着每一条己提交的日志记录肯定在这些接收到节点中的至少存在一份。也就是说，记录全部己提交日志的节点和接收到Candidate节点的选举请求的节点必然存在交集，如图示。

如果Candidate节点上的日志记录与集群中大多数节点上的日志记录一样新，那么其日志一定包含所有己经提交的日志记录，也就可以获得这些节点的投票并成为Leader。在比较两个节点的日志新旧时， Raft协议通过比较两节点日志中的最后一条日志记录的索引值和任期号，以决定谁的日志比较新：首先会比较最后一条日志记录的任期号，如果最后的日志记录的任期号不同，那么任期号大的日志记录比较新：如果最后一条日志记录的任期号相同，那么日志索引较大的比价新。