raft一致性协议

raft是一个用于管理复制日志的协议，raft首先先选举出一个leader，然后由leader完全管理复制日志，以实现一致性。

使用raft简化了复制日志的管理，如leader在接受了客户端发送的日志条目之后，在不需要询问其他服务器的情况下决定把日志条目放在哪里；且数据流向只能从leader到其他服务器，leader将日志复制到其他服务器，并告诉它们什么时候可以安全的把日志之条目应用到他们的状态机上。如果leader和其他服务器断开连接，这种情况下，新的leader被选举出来。

使用leader方案，Raft把一致性问题分解为三个相关的子问题：

leader选举：当前leader故障时必须选举出一个新的leader。

日志复制：leader必须从客户端接收日志条目并复制到集群中其他服务器上，强制其他日志和它的保持一致。

正确性：Raft的关键属性是图3中描述的状态机正确属性：如果一个服务器把一条日志条目应用到了它的状态机上，那么不会有其他服务器在相同的日志偏移处应用一条不同的指令。5.4节描述了Raft如何保证这一点；解决方案包括了5.2节中描述的对选举机制额外的一些限制。

Focus：

一个Raft集群包含了多个服务器；典型的数字是5个，这样的系统可以容忍两台服务器的故障。在任意给定的时刻，每个server都处于三种状态的一种：leader,follower, 或者candidate。在一般情况下，只有一个leader，其他server都是follower。Followers是被动的：他们不会自己发起请求，只会响应来自leader和candidate的请求。leader处理所有的客户端请求(如果客户端请求到一个follower，follower会把请求重定向到leader)。第三种状态，candidate，是用于选举新leader的。

Raft的leader是任期制的，Raft把时间分为任意长度的terms，如图5所示。Terms用连续的数据来标志。每个term都以一个选举开始，其中一个或多个candidate尝试着成为leader。如果一个candidate在选举中胜出，它会成为leader，并在这个term的后续时间中一直保持是leader。在某些情况下，选举可能会导致投票结果分裂开来。这种情况下这个term会以没有leader的状态结束；新的term(新的选举)会接着开始。Raft保证在一个term中只会有一个leader。

不同的服务器可能会在不同时间段看到terms的转移，某种情况下服务器可能在整个term周期内都不会观察到选举。Terms在Raft中扮演着逻辑时钟的角色，它们使得服务器可以检测到过时的信息，比如一个陈旧的leader。每个服务器都存储着一个当前term数字，这个数字会随着时间单调增加。当前terms会在服务器之间通信时进行交换；如果一个服务器的当前term比其他服务器的小，它会更新自己的当前term为大的值。如果一个candidate或者leader发现它的term过时了，它会立即转移到follower状态。如果一个服务器收到了一个过期的term值，它会拒绝这个请求。

接下来主要介绍下raft算法的主要的三个问题：

1.leader选举

Raft使用一种心跳机制来触发leader选举。服务器启动时，以follower状态开始。只要它受到来自leader或者candidatea的有效RPC请求，它会保持follower状态。leader会持续周期的发送心跳(没有数据的AppendEntries RPC)给所有的followers，以此维持它的权威。如果一个服务器在一个选举超时的时间内没有收到心跳请求，它会认为没有可用的leader，然后一次选举以选择新的leader。

开始一次选举的方式是：follower增加它的当前term值，并转移到candidate状态。然后它为自己投票，并发起并行的RequestVote RPC给集群中的每一个其他服务器。candidate会持续在这个状态直到以下三种情况之一发生：(a)它赢得了选举，(b)其他服务器赢得了选举，(c)一段时间过去了没有胜出者。下面的段落会分别讨论这几种情况。

如果一个candidate在同一个term中收到了集群中大部分服务器的响应，那么它就在选举中胜出。在指定的term中，每个server只能为一个candidate投票，以先到先得的规则来实现。大部分保证了在一个term中最多一个candidate会在选举中胜出。一旦一个candidate赢得了选举，它便成为leader。接下来它会发送心跳消息给所有其他服务器以建立权威并阻止新的选举。

在等待投票结果的时候，candidate可能会收到其他服务器的AppendEntries RPC，声称它自己以及成为了leader。如果这个leader的term值(在RPC中携带)不小于candidate的term值，那么candidate就会承认此leader是合法的并将自己返回到follower状态。如果RPC中的term值比candidate的当前term要小，那么candidate会拒绝RPC并继续保持candidate状态。

第三个可能的结果是一个candidate既没有在选举中胜出也没有失败：如果多个followers同时成为candidate，投票可能会分裂，以至于没有任何candidate能获得大多数的认可。当发生这种情况时，每个candidate都会投票超时，它们会增加自己的term值并发起新一轮的RequestVote RPC。如果不采取额外的措施，投票可能会无限的分裂下去。

Raft使用随机的选举超时值来保证投票分裂很少发生，并能够快速得到解决。为了从源头方式投票分裂的发生，选举超时值会随机的从一段固定范围内选取(比如150-300ms)。这些不同的值分散在服务器中，因此大多数情况下只会有一个服务器会超时；超时的服务器会在其他服务器超时之前赢得选举并发送心跳给其他服务器。这种机制也用来处理投票分裂。每个candidate在一次选举开始的时候会选择一个超时值，等待这个时间过去，然后开始下一次选举；这减少了下次选举出现投票分裂的可能性。

2.日志复制

一旦leader被选举出来，它开始接收客户端请求。每个客户端请求都包含着一个可被状态机执行的指令。leader将指令添加到日志后面作为一个新条目，然后并行的给其他服务器发起AppendEntries RPC，让它们复制这个条目。当此条目被正确的复制后，leader把这个条目应用到它的状态机上，并将结果返回给客户端。如果follower宕机或者运行缓慢，或者出现消息丢失，leader会无限的尝试发送AppendEntries RPC直到所有的follower最终存储了全部的日志条目。

日志被组织为如图6所示的形式。每一条日志条目都保存着一个状态机指令以及一个term值。term值用来检测日志之间的不一致。每条日志条目都有一个整数索引值来识别它在日志中的位置。

leader决定何时才能安全的把一条日志条目应用到状态机上；这样的条目被称作已提交。Raft保证已提交的条目会持久化，并最终被所有可用的状态机执行。一旦leader把某个条目复制到了大多数户服务器中(比如图6中的条目7)，这个条目就提交了。同时被提交的还有leader日志中之前的所有的条目，包括由之前leader创建的条目。leader保持追踪它所知道的最高已提交条目的索引，它会在后续的AppendEntries RPC(包括心跳)中带上这个索引值，这样其他的服务器最终也会知道这个值。当follower发现某个条目已经提交了，它会应用这个条目到它自己的状态机上(按照日志的顺序)。

我们设计Raft日志机制，让不同服务器上日志保持高度一致。这套机制不仅简化了系统行为，使系统更加可预测，也是保证正确性的重要组件。Raft维持以下属性，它们共同构成了日志匹配属性(Log Matching Property):

如果不同日志中的两个条目有相同的索引值和term值，那么他们保存着相同的指令

如果不同日志中的两个条目有相同的索引值和term值，那么他们之前的日志条目全部是相同的

第一个属性可以从如下事实中推演：在指定的term中，leader在日志的某个索引位置只会创建最多一条日志，而且日志条目绝不会改变它们在日志中的位置。第二个属性由AppendEntries RPC所执行的一致性检查来保证。当发送AppendEntries RPC时，leader会带上当前最新添加条目之前的那一条日志条目的term值和index值。如果follower在它的日志的相同位置没有找到相同的条目，它就会拒绝新的条目。这个一致性检查以归纳法的形式运作：最初的空日志符合Log Matching Property，而一致性检查则保证后续的日志仍然满足Log Matching Property。作为结果，任何时候只要AppendEntries返回成功，leader就能知道，这个follower的日志在和自己的日志，直到最新添加的条目这里，全部是相同的。

在常见操作中，leader和followers的日志保持一致，因此AppendEntries一致性检查不会失败。然而，leader宕机会导致日志不一致(老的leader可能没有把它的日志全部复制完成)。这种不一致可能会在一系列leader和followers的宕机过程中叠加。图7展示了followers日志和新leader不一致的几种可能。follower可能缺少leader的部分日志，也可能有一些leader上面没有的日志，或者同时发生这两种情况。确实和多余的日志条目可能跨域多个term。

在Raft中，leader通过强制follower复制自己的日志来达到一致。这就是说follower中的冲突日志条目会被leader的日志内容覆盖。加上适当的约束，这样做是安全的。

为了让follower的日志和自己的一致，leader必须找到两个日志中相同的最近的那条日志条目，从这个点开始，删除follower日志后面的内容，并把leader自这里开始的日志都发送给follower。这些动作都在AppendEntries RPC的一致性检查中进行。leader对每个follower维护着一个nextIndex值，这个值标志着下一条发送给follower的日志索引。当leader开始工作时，它会把所有的nextIndex初始化为它日志的最后一条后面的位置(图7中的11)。如果某个follower的日志和leader不一致，那么后续的AppendEntries RPC的一致性检查就会失败。在RPC被拒绝之后，leader减小nextIndex的值，然后再次尝试发送AppendEntries RPC。最终会得到一个leader和follower的日志内容匹配的nextIndex。当找到这个点后，AppendEntries会成功，它会删除follower中所有冲突的日志，然后添加上leader的日志内容。一旦AppendEntries成功，follower的日志就和leader一致了，并且会在当前term中保持一致。

如果需要的话，可以优化协议以减少AppendEntries RPC被拒绝的次数。比如，在拒绝AppendEntries时， follower可以在回复中带上冲突的条目以及它所保存的当前term的第一个条目的索引。有了这些信息，leader可以确定一个能够绕过冲突条目的nextIndex；解决冲突条目只需要一次AppendEntries RPC，而不是每个条目一个RPC。在实际中，我们怀疑这个优化的必要性，因为故障不会频繁的发生，不太可能出现很多不一致的条目。

使用这种机制，leader在上任后不需要采取额外的措施来恢复一致性。它仅仅开始常规操作，日志就会在AppendEntries一致性检查中自动的汇合。leader绝不会覆盖或者删除自己的日志(leaderAppend-Only属性)。

日志复制机制展示了第2章中描述的一致性属性：在大多数服务器正常的情况下，Raft可以接收，复制，应用新的日志条目；在普通情形下，复制一条新条目只需要一轮RPC；单个慢服务器不会影响性能。

3  正确性

前面的章节描述了Raft是如何选举leader和复制日志的。然而到目前为止，上述的机制并不能保证每个状态机都按照相同的顺序执行完全一样的指令。比如说，某个follower可能在leader复制日志的时候不可用，然后又被选举为leader并用新的日志条目覆盖了之前leader复制的那些条目；这种情况下，不同状态机就可能会执行不同的指令。

这一小节描述了哪些服务器能被选举为leader的限制，从而完善了Raft算法。这个限制保证了任意term中的leader都包含了在之前term中提交的所有日志条目(Leader完整属性)。通过这个限制，我们把提交规则变得更精确。最后，我们给出对Leader完整属性的一个概要证明，并展示了它是如何使复制状态机都正确工作。

1） 选举限制

在任何基于leader的一致性算法中，leader最终都必须存储着所有提交的日志条目。在一些算法中，如Viewstamped Replication[^]，一个leader即使在开始没有包含所有提交的条目也能够被选为leader。这些算法包括了额外的机制，用来发现丢失的条目并将它们传输到新leader上，要么在选举过程中，要么在选举后进行。不幸的是，这导致了大量的额外机制和复杂性。Raft使用了一个简单的方案，它保证在选举开始时，所有在之前term中提交的条目都在新leader上，不需要传输这些条目到leader。这意味着日志条目只会在一个方向上流动，从leader到followers，而且leader绝不会覆盖他自己日志中已有的条目。

Raft在投票过程中会防止某个candidate赢得选举，除非它的日志包括了所有提交的条目。为了赢得选举，candidate必须和集群中的大多数服务器进行通信，这意味着每一条提交的条目至少存在这些服务器中的一台上。如果candidate的日志至少和大多数服务器中的日志都是一样新(up-to-date，后面会精确定义)的，那么它就包括了所有提交的条目。RequestVote RPC实现了这个限制：RPC中包含了candidate的日志信息，如果投票者发现它自己的日志比candidate的更新，它会拒绝此次投票。

Raft通过比较日志中最后一个条目的index和term来决定哪个日志更新一些。如果两个日志最后一个条目的term不同，那么term大的更新。如果两个日志最后条目的term相同，那么更长的那个日志更新。

2） 提交之前term的条目

当一个当前term的条目被存储在集群中大多数服务器上时，leader则认为此条目是已提交了。如果leader在提交某个条目之前崩溃了，新的leader会尝试完成这个条目的复制。然而，leader不能立即断定一个之前term的条目已经提交，即使这个条目存储在大多数服务器上。图8展示了一个情形，其中一个旧的条目存储在大多数服务器上，但仍然可能会被新的leader覆盖。

为了消除图8中的问题，Raft绝不会通过计数副本的数目来提交之前term的日志条目。只有当前term的条目会通过计数来提交；一旦当前term的某个条目通过这种方式提交了，那么之前的所有条目也都提交了，基于Log匹配属性。某些情况下，leader可以安全的断定一个旧的条目以及被提交(比如，每个server上都保存着这个条目)，但是处于简化的考虑，Raft仍然采用一个保守的方式来处理。

Raft在提交规则中引入了这样额外的复杂性，从而使得在leader复制之前的条目时，这些日志条目仍然可以保留他们原始的term值。在其他一致性算法中，当一个新leader复制之前term的条目时，它必须使用一个新的term值。Raft的方案使得理解日志条目更加简单，因为它们总是保持着最初的term值，不管是在不同时间还是不同的日志中。除此之外，相比于其他算法，在Raft中新leader会发送更少的旧条目(其他算法中必须发送冗余的日志条目，并在提交之前进行重新编号)。

3）正确性讨论

给出了完整Raft算法后，我们可以更加精细的证明Leader完整属性是成立的(证明基于正确性证据，查看9.2节)。我们假设Leader完整性不成立，然后得出一个冲突。假设term T的leaderT提交了一个日志条目，但是这个条目不在未来的某个leader中。设定最小的不包含这个条目的leader的term是U，即leaderU中没有这个条目。

在选举的时候，leaderU的日志中就没有这个条目(leader不会删除或者覆盖日志条目)。

leaderT将这个条目复制到大多数服务器上，leaderU收到大多数服务器的投票。因此，至少有一个服务器(投票者)即接收了leaderT的日志条目，又给leaderU投票了。如图9所示，这个投票者是证明冲突的关键所在。

投票者必须是在给leaderU投票之前接受了leaderT的日志条目；否则它会拒绝leaderT的AppendEntries请求(它的当前term比T要大)。

当投票者给leaderU投票时，它仍然存储着这个条目，这是因为中间所有的leader都存储着这个条目(基于假设)，而leader不会删除条目，同时follower只会删除它们和leader冲突的条目。

投票者给leaderU投票了，这样的话leaderU的日志必须是和投票者一样新的。这导致了两个冲突。

第一，如果投票者和leaderU的日志term是相同的，那么leaderU的日志至少是和投票者的日志一样长的，因此它会包含投票者日志中的所有条目。这是一个冲突，投票者包括这个条目，而leaderU中没有(基于假设)。

如果他们的term不同，那么leaderU的最后一个日志条目的term必须是比投票者的term大。进一步的，它的term是比T大的，因为投票者的最后一个日志条目的term至少是T(已提交的这个条目是term T的)。创建leaderU的最后一个日志条目的之前leader是包含了这个提交的条目的(基于假设)。根据Log匹配属性，leaderU的日志中必须包含所有的提交条目，这是一个冲突。

这样就完整了整个冲突证明。因此，所有term比T大的leader的日志中，必须包含了term T中提交的所有日志条目。

日志匹配属性保证了后续的leader也会包括被间接提交的日志条目，如同图8(d)中的第2条。

给出了Leader完整属性，我们可以证明图3中的状态机正确性，即如果一个服务器应用了某个index的指令到它的状态机，那么在这个index位置，不会有其他服务器应用不同的指令。当一个服务器应用某个日志条目到状态机时，它的日志和leader的日志直到这个条目为止应该都是相同的，并且这个条目肯定是已提交的。现在考虑一下任意服务器应用的某个index的日志条目中最低的term。leader完整属性保证所有更高term的leader会存储相同的条目，因此应用这个条目的所有服务器都会应用相同的条目。因此，状态机正确性成立。

最后，Raft要求服务器按照日志顺序来应用条目。和状态机正确性结合起来，这意味着所有服务器都会应用完全相同的日志条目到它们的状态机，按照相同的顺序。

原文地址：https://www.jianshu.com/p/0b2ef4f37ae3