分布式一致性Raft算法日志复制

　　第2部分日志复制介绍
　　Raft是一种共识算法，旨在以分布式方式编排副本。Raft在设计时考虑了可理解性，只有几个活动部件并且易于实施。在上一篇文章中，我讲了Raft的基础知识，并解释了领导者选举机制。在这篇文章中，我们将关注另一个重要问题日志复制。基础知识
　　Raft本质上是一堆复制的状态机。每当领导节点收到请求时，都会将其附加到日志中以确保持久性。相同的日志被复制到多台机器上以实现冗余。
　　图0。Raft日志，作者图
　　例如，在图1中，当前领导者的日志中有四个条目。关注者1完全同步，但关注者2缺少最新条目。如果你不明白图0中的Term是什么，可以看看我之前的文章。
　　用于日志复制的RPC
　　为便于理解而设计，Raft仅使用两个RPC调用进行所有通信：
　　AppendEntry：这个RPC由leader发起，携带最新收到的命令。它还用作心跳消息。当追随者收到此消息时，选举计时器将重置。AppendEntry消息是这样的结构（我在这里使用Golang）typeAppendEntryArgsstruct｛Termintcurrenttermoftheleader，veryIMPORTANTLeaderIdintidoftheleader，0toN1whereNtotalserversEntries〔〕EntrynewdatatosyncPrevLogIndexintimportantmetadataforlogcorrectnessPrevLogTermintimportantmetadataforlogcorrectnessLeaderCommitintwhatindexhavebeenreceivedbythemajority｝typeAppendEntryReplystruct｛TermintcurrenttermofthereceivingnodeSuccessboolAppendEntrydeclinedoracceptedConflictIndexintifdeclined，specifyingtheconflictingindexConflictTermintifdeclined，specifyingtheconflictingterm｝
　　如果您不了解每个字段的含义也没关系。我们将一一检查。
　　RequestVote：这个RPC用于leader选举，在上一篇文章中有介绍。我将跳过它，因为我们只关心日志复制。日志复制详细信息
　　让我们从普通日志复制算法开始。每当领导者收到请求时，它会将日志条目转发给所有追随者并等待大多数人确认。
　　问题1：日志排序
　　香草算法会在追随者到达后立即向他们发送消息。为此，它只需要消息中的两个字段leaderID和Entry。一个主要问题是由于潜在的消息延迟而无法保留日志顺序。考虑图1中的场景。
　　图1。日志排序问题，作者图
　　Raft使用两个额外的字段来确保日志的完整性PrevLogIndex和PrevLogTerm。当一个新条目发出时，leader也会发出之前条目的索引和任期号。接收方在将新请求附加到其本地日志之前确保其最新条目具有相同的索引和任期。
　　图2。附加记账的AppendEntry，作者图
　　有了这两个额外的参数，我们可以实现一些很棒的东西：给定日志索引，如果来自两个日志（在两台不同机器上）的条目共享相同的术语，则它们是相同的如果不同日志中的两个条目具有相同的索引和任期，则所有前面的条目都是相同的
　　第一个性质很容易证明。假设索赔是错误的。如果存在两个具有相同任期的不同条目，则其中一个必须比另一个更晚被领导者接收。由于日志是仅附加的，因此其中一个条目将具有更大的PrevLogIndex。但是，如果它们出现在两个不同日志的相同索引中，则它们必须具有相同的PrevLogIndex。（否则接收方拒绝）矛盾！！
　　第二个主张可以通过归纳证明：
　　图3。声明2的归纳证明，作者图
　　这两个保证共同构成了Raft的日志匹配特性。
　　问题2：具有冲突条目的关注者
　　如果leader日志是集群中唯一的权限，它将覆盖follower的任何冲突。是否有可能丢失一些日志条目？考虑以下情况：
　　图4。日志冲突，作者图
　　在深入探讨这个问题之前，我想说服您上述情况确实会发生。日志在索引2之前同步。从那里开始，创建这些日志可能会发生以下情况：1）节点2成为领导者（从自己投票，1和0）任期22）节点2收到来自客户端的请求，但未能与其他节点同步3）节点0成为领导者（来自1和它自己的投票），任期为34）节点0收到来自客户端的请求。但未能同步
　　现在，如果节点0重新与节点2联系，它将尝试复制其日志，如图5所示
　　图5。覆盖冲突，作者图
　　如您所见，绿色条目确实被丢弃了。按照目前的设计，这个问题是不可避免的。然而，这里的一个关键观察是绿色条目没有在大多数（至少两个节点）上复制。如果是，它将永远不会被丢弃，原因如下：如果一个条目在大多数情况下被复制，则至少有N21个节点拥有它对于没有进入选举的节点，它需要其他节点的N2票（候选人总是为自己投票）由于候选人没有条目，因此具有条目的N21个节点不会投票给它（选举限制在第1部分中解释）Itwontgetenoughvotestowintheelection
　　这就是Raft的第二个关键特性日志完整性属性。如果一个条目在majority上被复制，它将始终出现在未来的领导者日志中，无论它可能是哪个节点。如果没有在大多数人身上复制，则如果领导层发生变化，条目可能会被删除。
　　对于日志完整性属性，重要的是不要在大多数人收到之前确认客户端请求。
　　问题3：何时提交？
　　最后，我们到了最后一个问题什么时候提交条目？首先什么是commit，为什么要commit？Raft是一种低级共识算法，供上层应用程序使用，如键值存储（例如ZooKeeper）。当一个条目被Raft安全地复制时，我们要确保客户端可以通过应用程序看到它。因此，Raft需要决定何时告诉上层应用程序一个条目已准备好使用（一个部分复制的条目，因为领导者日志中的最后一个条目不应该是可见的！）。
　　图6。提交，作者图
　　到目前为止，我们的香草算法没有携带任何关于提交索引的信息。因为数据流是单向的，从领导者流向追随者，所以节点不知道一个条目是否在大多数节点上被复制。
　　为了解决这个问题，我们可以在AppendEntry消息中添加另一个字段，称为LeaderCommit。如果大多数接收到一个条目，领导者会增加提交索引。下面是跟踪领导节点使用的提交索引的实际代码。forn：rf。getLastIndex（）；nrf。commitIndex；n｛startfromthelatestentrycount：1ifrf。log〔n〕。Termrf。currentTerm｛leaderonlycaresaboutentriesofitstermentrieswithsmallertermsarecommitedautomaticallywhenhighertermsarecommittedfori：0；ilen（rf。peers）；i｛ifrf。peer〔i〕。hasEntry（n）｛count｝｝｝ifcountlen（rf。peers）2｛rf。commitIndexnnoneedtogofurtherback，forreasonsstatedinline7and8break｝｝
　　领导者如何跟踪提交索引概括
　　在这篇文章中，我们从普通的日志复制算法（广播条目，没有任何额外的簿记）开始，并通过考虑各种极端情况将其发展为成熟的版本。日志复制中最重要的RPC是AppendEntryRPC，它使用具有四个字段的结构：Term：对于日志复制和领导者选举非常重要LeaderId：显示候选人的身份。条目：领导者希望复制的条目列表。PrevLogIndex：在Entries〔0〕之前的日志条目的索引。用于确保日志完整性和日志匹配属性PrevLogTerm：在Entries〔0〕之前的日志条目的任期。用于确保日志完整性和日志匹配属性LeaderCommit：对上层应用很重要。只有已提交的条目才能应用于应用程序并且对客户端可见。