分布式协议之raft介绍


   最近在工作中接触了分布式协议,对这个很感兴趣,因此特地看了下raft的论文内容。以下就是对论文的粗浅翻译,如果翻译的有不妥的地方,欢迎随时指正

    摘要

Raft协议是管理副本日志的一致性算法。它产生的结果等同于(multi-)Paxos(分布式协议的起源),并且效率和Paxos相同,但是它的结构有别于Paxos协议;而也正是这,让Raft协议比Paxos协议更加易懂,也为构建实际系统提供了更好的基础。为了加强可理解性,Raft将一致性协议的关键元素进行分离,比如leader的选举、日志的复制、安全性,并且为了减少需要考虑到的状态的数目,它加强了更强程序的一致性。从Raft的用户学习演示的结果看,Raft比Paxos更易于学生学习。Raft还包含有一个全新的机制,用于修改集群成员,利用重叠优势去保证安全性。

   1 介绍

     一致性算法允许一组机器作为一个一致的组,能够在一些成员失败时幸存下来,继续工作。因为这个原因,他们在构建可靠的大规模软件系统上扮演着关键角色。Paxos协议在过去十年里统治了一致性算法的所有讨论:大部分一致性实现都是基于Paxos 或者受它影响,并且Paxos已经成为了教导学生关于一致性的首要工具。

     不幸的是,Paxos很难理解,尽管为了让它更容易接近而做了许多尝试、此外,它的结构需要复杂的变更来支持实际的系统。结果就是系统构建者和学生都在与Paxos中斗争。

    我们经过与Paxos的斗争,我们开始寻找一个可以为系统构建和教育提供更好的基础的一致性算法。我们的方法是不寻常的,因为我们的首要目标是“易理解性”:我们能为实际的系统定义一个一致性算法,并且可以用一种比学习Paxos更容易的方式去描述它?并且我们还想算法促进对系统开发者至关重要的直觉开发。重要的不仅是算法可以运行,而且是它为什么可以运行。

    这个工作的结果就是称为“Raft”的一致性算法。在设计Raft过程中,我们应用了特定的技术用于提高易理解性,包括分解(Raft分离leader选举,日志复制、安全)和状态空间简化(相对于Paxos,Raft减少了非确定性、服务器之间可能不一致的方式等的程度)。对43名学生、两所大学的用户研究表明,Raft比Paxos更容易理解:在学习了两个算法之后,33名学生回答关于Raft的问题比回答Paxos的问题要更好、

    Raft在很多方面与现有的一致性算法相似,但它有几个新特点:

  • 强leader:Raft 使用比其他一致性算法更强的leader形式。例如,日志记录只能从leader流通到其他服务器上、这个简化了复制日志,也让Raft更容易理解。
  • Leader选举:Raft使用随机计时器来选举leader。这个只是在已有的一致性算法要求的心跳中添加少量的机制,而简单快速地解决冲突。
  • 成员变更:Raft为改变集群中的一组服务器,在转换期间,两个不同配置的大多数重叠的部分,使用 新的“联合一致”方法。这允许集群在成员变更过程中继续正常的操作。

    我们相信Raft比Paxos和其它的一致性算法更优秀,包括在教育目的和作为实施的基础。它比其他算法更加简单、也更加的易于理解。它的描述完全满足实际系统的需要;它有一些开源的实现,并且也在一些公司中使用;它的安全性已得到正式的规定和证明;它的性能与其他算法相当

    论文的剩余部分介绍复制状态机问题(章节2),讨论Paxos的优点和缺点(章节3),描述可理解性的一般方法(章节4),介绍Raft一致性算法(章节5-8),评估Raft(章节9),讨论相关工作(章节10)

2 复制状态机

    一致性算法通常出现在复制状态机的环境中。用这种方法,状态机在一系列服务器中计算相同状态下的相同副本,并且在即使一些服务器离线的情况也能继续运行。复制状态机被用来解决分布式系统中的各种错误容忍问题。例如,拥有单一集群leader的大规模系统,像 GFS、HDFS、RAMCloud等,通常使用单独的复制状态机来管理leader选举、保存必须在leader崩溃后幸免的配置信息。复制状态机的例子还包括Chubby 和 ZooKeeper.

    复制状态机通常使用复制日志实现。如图1显示。

                                       

                                图1 :复制状态机结构。一致性算法管理副本日志,日志中包含来自客户端的状态机命令。状态机处理来自日志的相同命令序列,因此他们产生相同的输出

    每个服务器保存日志,日志中包含一系列的命令,而这些命令在状态机中按顺序执行。每个日志以相同的顺序包含相同的命令,这样每个状态机处理相同的命令顺序。因为状态机是确定性的,每个状态机计算相同的状态,有着相同顺序的输出。

    保证副本日志一致是一致性算法的工作。服务器上的一致性模块接收来自客户端的命令,并且将命令加入日志中。它还同其他服务器上的一致性模块通信,以确保每个日志最终包含相同的顺序的相同请求,即使一些服务器故障。一旦命令被正确地复制,每个服务器的状态机按照日志的顺序处理这些命令,并且将输出结果返回给客户端。结果,服务器形成了一个独独立的、高度可靠的状态机

    实用系统的一致性算法通常具有以下属性:

  • 他们保证安全性(从不返回错误的结果),在non-Byzantine (非拜占庭)的条件下,包括网络延迟、网络分区以及包的丢失、复制、重新排序等。
  • 他们是功能齐全(可用)的,只要大部分服务器正在运行,并且能与客户端和其它服务器通信、因此,一个典型的有5个服务器的集群能够容忍2个节点的故障。假设服务器因为停止而故障,他们稍后可能会从稳定的存储器上的状态中恢复,并且重新加入集群.
  • 他们不依赖于时间来确保日志一致性:错误的时钟和极端的消息延迟可能会导致可用性问题。
  • 在通常情况下,命令在集群的大多数节点回应了远程调用之后就会完成,少数慢服务器不会影响总体系统性能。

3. Paxos有什么问题?

    在过去的十年中,Leslie Lamport(莱斯利·兰伯特:Pxos算法的提出者)的Paxos协议已经成为几乎一致性的代名词:它是课程中最常教授的协议,并且大多数一致性的实现都用它作为起始点。Paxos第一次定义了一个协议能够在一个决定中达成共识,例如一个单一复制日志条目。我们将此子集称为 single-decree Paxos。Paxos之后结合该协议的多个实例促进一系列决策,例如日志(multi-paxos)。Paxos保证了安全性和活跃,并且它支持集群的成员变更。它的正确性是已经被证明了的,在正常情况下很有效率。

    不幸的是,Paxos有两个显著的缺陷。第一个缺陷是Paxos很难理解。完整的论文阐述是众所周知地晦涩。很少有人成功地理解它,即使理解,也必须付出很大的努力。因此,有一些尝试去用更简单的术语描述Paxos。这些描述集中在 single-decree Paxos,但他们仍然充满挑战。在NSDI 2012参加者的非正式的调查中,我们发现很少有人对Paxos满意,即便是经验丰富的研究者。我们自己与Paxos斗争,我们不能理解全部的协议,直到读了一些简化版的说明,并且设计我们自己的替代的协议,这个过程需要花费一年的时间。

    我们假设Paxos的晦涩来源于它选择single-degree Paxos 作为它的基础。 single-degree Paxos被分为两个阶段,这两个阶段没有简单直观的说明,也不能被独立地理解。因此,很难理解single-degree 协议为何起作用。Multi-Paxos的合成规则大大增加了复杂性。我们认为,就多项决定达成共识的总体问题可以通过更直接、更明显的方式来分解。

    第二个Paxos的问题是它没有为构建实际的实现提供一个好的基础。一个原因是multi-Paxos没有广泛认可的算法。兰伯特的描述大部分都是关于单一决策 Paxos的;他描述了multi-Paxos的可能方法,但是缺少了许多细节。已经有一些对Paxos的充实和优化的尝试,比如【26】,【39】和【13】,但是这些各不相同,也与兰伯特的描述不同。像Chubby系统实现了类Paxos的算法,但是大多数情况下,实现的细节没有发布。

5. Raft一致性算法

Raft算法,是用来管理章节2中描述的上述形式的复制日志。图2简要总结算法以供参考,图3列举出了算法的关键属性;这些图里的元素将在本章节的其余部分进行分段讨论

 å›¾2

                    图2 -关于Raft一致性算法的简要总结(包括成员变更和日志合并)。服务器的行为在左上角,描述一组独立且反复触发的规则。章节号,比如§5.2 表明讨论的特殊特性。正式规范【31】更精确地描述了该算法

        图3

                                        图3- Raft保证这些属性总是为真。章节号说明属性将在哪个章节讨论

        Raft实现一致性,首先选举一个leader,之后通过leader去管理副本日志。Leader接收来自客户端的日志条目,把它们复制到其他服务器上,并且当条目可以提交到状态机时通知其他服务器。拥有Leader,极大地简化了副本日志的管理。比如说,Leader可以决定将新的条目集合放到哪里而不用同其他服务器协商,并且数据可以以简单的方式从Leader传送到其他服务器。一个Leader可以故障或者与其他服务器失去连接,在这种情况下,一个新的Leader会被选出来。

    通过Leader这种方式,Raft将一致性问题分解成了三个相对独立的子问题,将在下面的子章节中讨论:

  • Leader选举:当一个已存在的Leader故障时,必须选出新的Leader(章节5.2)
  • 日志复制:Leader必须接受来自客户端的日志条目,并且在集群中复制它们,强制其他日志同意自己的日志(章节5.3)
  • 安全性:Raft的安全属性的关键就是图3中的状态机的安全性:如果有服务器已经提交了特定的日志条件到状态机中,那么其他服务器不能提交一个有相同日志索引但是命令不同的条目。章节5.4描述了Raft怎么保证这个属性;对选举机制的额外限制的解决方案将在章节5.2中描述

    展现了一致性算法之后,这个章节讨论易用性的问题和系统中定时的角色。

5.1 Raft基础

Raft集群包含了一些服务器;典型的是5个,因此系统允许容忍2个故障。在任意时间,每个服务器处于以下三个状态的其中之一:Leader、Follower或者Candidate。通常情况下,集群中有一个Leader,其他服务器都是Follower。Follower是被动的:他们自己不发出请求,只简单地响应来自Leader或者Candidate的请求。Leader处理所有的客户端请求(如果客户端与Follow接触,Follower要将客户端重定向到Leader)。第三个状态:candidate,是用于选举新Leader,将在章节5.2中描述。图4显示了服务器的状态以及他们的转换;转换在下面讨论。

                                            在这里插入图片描述

    Raft将时间分为任意长度的任期,如图5所示。

                                        在这里插入图片描述

  任期是连续的整形数字。每个任期从选举开始,也就是一个或多个candidate尝试成为Leader的阶段,将在章节5.2中描述。如果candidate赢得了选举,那么它在接下来的任期内作为Leader提供服务、在有些情况下,选举将产生分裂投票。在这种情况下该任期会结束,同时不会有Leader;一个新的任期(伴随着新一轮的选举)会在很短的时间内开始。Raft保证在一个任期内,最多只有一个Leader。

    不同的服务器可能会在不同的时间的任期间观察状态的转换,在有些情况下,一个服务器可能没有观察到一次选举、甚至是整个任期内。任期的行为就如同Raft的逻辑时钟,他们允许服务器检测过时的消息,比如过时的Leader。每个服务器保存当前的任期号,任期号随着时间的推移单调递增。服务器通信时,交换各自的任期;如果服务器的任期小于其他服务器,那么它会更新当前的任期为更大的那个值。如果candidate或者leader发现它的任期已经过时了,它会立即转换到follower状态。如果服务器接收到一个包含过期任期的请求,它会拒绝这个请求。

    Raft服务器之间使用RPC进行通信,基本的一致性算法仅要求两种类型的RPC,RequestVote RPC由candidate在选举时发起(见章节5.2),AppendEntries RPC由leader在复制日志条目和心跳(章节5.3)时发起。章节7增加了第三个RPC请求,为服务器间传输快照。服务器在没有收到及时的响应时,重试RPC。并且服务器为了保证性能,并行发出RPC

    5.2 Leader选举

    Raft使用心跳机制触发leader选举。服务器启动时,他们的状态是follower。服务器只要收到有效的来自leader或者candidate的RPC请求,就会一直保留它的follower状态。Leader发送定期的心跳(使用不带日志条目的AppendEntries RPC请求)到各个follower中,以维护它们的leader权威。如果follower在定时的时间内,也被称为选举超时,没有收到通讯,那么它假设没有可用的leader,并且开始选举,以选出新的leader。

    开始选举时,follower增加当前任期,并且状态从follower转换成candidate。然后它给自己投票,并发的发出RequestVote RPC到集群的其他服务器上。candidate继续它的状态,直到以下三个条件的任意一个发生:(a)它赢得选举,(b)另外一个服务器成为leader,(c)该时间段结束时没有赢家。这些结果会在下面的段中分别讨论。

    candidate赢得选举,当它在相同任期内收到了集群中大多数服务器的投票。每个服务器在一个任期内只能投票最多一个候选人(candidate),且基于先来先得的原则(注意:章节5.4中在投票时,增加了一个额外的限制)。多数投票的规则保证了在一个特定的任期内,最多只有一个候选人能够赢得选举(图3中的选举安全性属性)。一旦候选人赢得选举,它就成为了leader。然后它会发送心跳到其他的服务器上,用以建立它的权威并且防止新的选举。

    在等待投票的时候,候选人可能会收到来自另外一个声称为leader的服务器的AppendEntries RPC请求。如果leader的任期(RPC请求中包含)至少和候选人的当前任期一样大,候选人识别leader是合法的,并且返回到follower状态。如果RPC请求的任期小于候选人的当前任期,那么候选人拒绝该RPC请求,继续保持它的候选人状态。

    第三种可能的结果是候选人即没有赢得选举,也没有输掉选举:如果许多follower同时成为了候选人,投票会被分裂,以致于没有候选人获得大多数的投票。当这种情况发生时,每个候选人会超时,并且开始新的选举,增加任期,发起新一轮的RequestVote RPC。然而,如果没有额外的措施,投票分裂会无尽地重复发生。

    Raft使用随机选举超时时间来保证投票分裂很少发生,并且发生了也能快速地解决。首先要防止投票分裂,选举超时时间会在固定的间隔(比如150-300ms)内随机。这分散了其他服务器,因此大多数情况下只有一个服务器会超时;它会在其他服务器超时之前赢得选举,发送心跳。同样的机制也被用来处理投票分裂。每个候选人在选举开始时重置它的随机超时时间,在开始下一个选举之前,等待超时时间过去;这样减少了新选举时另一次投票分裂的可能性。章节9.3显示了这种方法可以快速的选出leader。

    选举是一个样例,体现了可理解性是怎么指导我们在设计方案之间进行选择。起初我们计划使用排名系统:每个候选人分配一个唯一的排名,用来在竞争的候选人之间选择。如果候选人发现另外一个候选人有更高的排名,它会回到follower状态,这样更高排名的候选人可以更容易地赢得下一次选举。我们发现这种方法围绕可用性上有一个细微的问题(低排名的服务器可能会超时以再次成为候选人,如果有更高排名的服务器故障,这一切发生太快,它可以重置leader选举的进度)。我们对这算法做了几次调整,但是每次调整之后,总是有新的边角情况出现。最终我们断定随机重试的方法更明显也更容易理解。

5.3 日志复制

    一旦当选为leader,它就开始为客户端请求提供服务。每个客户端请求包含要在复制状态机中执行的命令。leader追加命令到它的日志中作为新的条目,然后并发的发出AppendEntries RPC请求到其他服务器上以复制该条目。当条目安全地复制之后,leader就应用该条目到它的状态机中,然后返回指向结果给客户端。如果follower崩溃或者执行缓慢,或者如果网络包丢失,leader会无限地重试AppendEntries RPC请求(即使它已经回复客户端)直到所有follower最终保存了所有的日志条目。

    日志如图6所示组织。 图6

                  图6 :日志由条目组成,条目按顺序编号。每个条目包含创建时候的任期(框中的编号)和状态机要执行的命令。如果可以安全地将该条目应用于状态机,则认为该条目已提交(committed)。

     leader收到该条目时,每个日志条目都会存储一个状态机命令以及任期号。日志条目中的任期号被用来检测日志间的不一致性,并且用来确保图3中的一些属性。每个日志条目也有一个整形的索引号,表明条目在日志中的位置。

    leader决定何时条目可以安全地应用到状态机中;这样的日志条目被称为已提交。Raft保证已提交的条目是持久化的,并且最终都会被所有可用的状态机执行。一旦条目被复制到多数服务器上时,日志条目就被认为是已提交的(例如,图6中的条目7)。这样也会提交所有之前的leader日志中之前的条目,包括前leader创建的那些条目。章节5.4讨论了一些当leader切换之后应用这个规则的微妙之处。,并且它也说明了这样定义承诺是安全的。leader记录已提交的最大的index,并且包含在将来的AppendEntries RPC(包括心跳)中,这样其他服务器最终了解已提交的index。一旦follower知道日志条件已提交,它会立即应用该条目到本地的状态机中(按日志顺序)。

    我们设计Raft的日志机制去维护一个高水平的在不同服务器的日志间的连贯性。不仅是因为这样会简化系统的行为,也是因为会让系统更加可预测。,但是它是保证安全性的最要组成部分。Raft维护以下属性,这些属性一起构成图3中的日志匹配属性:

  • 如果两个不同日志中的条目,有相同的index和任期,那么他们保存了相同的命令
  • 如果两个不同日志中的条目,有相同的index和任期,那么所有前面的日志条目的日志均相同

    第一个属性来自一个事实,leader在指定的任期和指定的index中最多创建一个条目,并且日志条目在日志中的位置永不发生变化。第二个属性由AppendEntries执行的简单一致性检查来保证。当发送AppendEntries RPC时,leader包含了紧随新条目之前的那个日志条目的index和任期。如果follower在它的日志条目中没有找到相同的index和任期,那么follower会拒绝这笔新的日志条目。这个一致性检查表现为以下的归纳步骤:日志的初始空白状态满足日志匹配属性,一致性检查不管日志何时扩展都保持日志匹配属性。最终,不管AppendEntries RPC何时返回成功,leader通过自身的新条目知道follower的日志是相同的。

    在正常操作期间,leader和follower的日志总是保持一致,因此AppendEntries 一致性检查从不会失败。然而,leader崩溃会导致日志不一致(旧的leader可能没有复制日志中的所有条目到其他服务器上)。这些不一致会加剧一系列leader和follower的  崩溃。图7演示了一种follower的日志可能与新leader不同的一种方式。follower可能缺少leader中的一些条目,可能有leader没有的额外的条目,又或者两种情况都有,缺少和多余额外条目可能跨越多个任期。

 图7 

             图7 : 当leader成功当选时(最上面那条日志),follower的日志可能发生任何一种场景(a-f)。每个盒子表示一个日志条目;盒子中的编号是它的任期。follower有可能缺少条目(a-b),可能有额外未提交的条目(c-d),或者两种情况都有(e-f)。举例来说,场景f可能发生,如果服务器在任期2时是leader,增加了一些条目到它的日志中,然后一个条目都没提交就崩溃了;服务器很快重启,在任期3时重新成为leader,增加了更多的条目到日志中;在任期2或者任期3的任意一个条目被提交前,服务器又崩溃了。并且在接下来的几个任期里一直处于宕机状态。

    在Raft中,leader通过强制follower复制它的日志来解决不一致的问题。这意味着follower中的冲突的日志将会被来自leader的日志覆盖。章节5.4显示增加一个限制可以保证安全性。

    要使得follower的日志与自己保持一致,leader必须找到两者达成一致的最大日志条目,删除在这个点之后的所有日志条目,并且给follower发送自从那个点之后的所有leader的日志条目。所有这些行为发生在AppendEntries 一致性检查的回复中。leader为每个follower维护一个nextIndex,记录了leader将要发送给follower的下一个条目的index。当选出一个新leader时,它初始化所有的nextIndex值为本地的最后日志条目的index +1(图7中的11).如果follower中的日志与leader的不一致,AppendEntries的一致性检查会在下一次AppendEntries RPC时失败。拒绝之后,leader减少nextIndex,并且重发AppendEntries RPC,最终nextIndex会抵达leader和follower日志匹配的那个点。当这发生了,AppendEntries就会成功,将删除follower中与leader存在冲突的所有条目,并且追加leader中的条目(如果有需要追加的日志条目的话)。一旦AppendEntries成功,follower的日志就会与leader的一致,并且在接下来的任期中都会保持一致。

    如果需要,协议可以优化减少拒绝的AppendEntries RPC请求的数量。比如,当拒绝AppendEntries请求,follower可以在回复中包含与leader冲突的条目的任期和它存储的这个任期的第一个index,有了这些信息,leader可以直接跳过所有的那个任期的冲突条目来减少nextIndex;这样就变成每个包含冲突条目的任期都需要一个AppendEntries RPC ,而不是每个条目一次RPC。在实践中,我们怀疑这个优化的必要性,因为失败不经常发生,并且不大可能有许多不一致的条目。

    通过这个机制,leader不需要做任何特殊的行动来恢复成为leader时的日志的一致性。它仅仅只是开始简单的通常操作,然后日志就会自动地汇聚在AppendEntries 的一致性检查失败中。leader从不覆盖或者删除它自己的日志(图3中的leader的只追加属性)。

    日志复制机制展示了章节2中描述的一致性属性:Raft能接收、复制并且应用新日志条目,只要多数服务器能正常运行;通常新条目在一轮RPC中就会被复制到集群的多数服务器中,并且一个运行慢的follower不会影响整体的性能。

5.4 安全性

    前面的章节描述了Raft怎么选举leader以及日志条目的复制。然而,迄今为止介绍的机制在保证每个状态机按照相同的顺序执行相同的命令上并不足够。例如,一个follower在leader提交一些日志条目时并不可用,然后它还能被选为leader,并且使用新的条目覆盖这些条目,结果,不同的状态机可能按照不同的顺序执行命令。

    这个章节通过添加一个关于哪些服务器可以被选为leader的限制来完善Raft算法。这个限制保证了leader,对任意给定的任期,都包含之前任期的所有已提交的条目(图3中的 Leader Completeness 性质)。有了这一选举的限制,我们可以让提交规则更加精确。最后,我们展示关于 Leader Completeness 性质的简要证明,并且显示它是怎么引导指向复制状态机的正确行为的。

5.4.1 选举限制

    在任何一个基于leader的一致性算法中,leader一定最终存储所有的已提交的日志条目。在一些一致性算法中,比如Viewstamped Replication,服务器即使初始时没有包含所有的已提交日志条目,也可以被选为leader,这些算法包含了额外的机制识别缺少的条目并且在选举过程中或是之后不久将这些条目传递到新leader中。不幸的是,这导致相当多的附加机制和复杂性。Raft使用更简单的方法,它保证之前任期内的所有的已提交的日志条目从每一个新leader当选之时起都包含,这样就没有了传送那些缺少条目的必要。这意味着日志条目的流动仅是单向的,从leader到follower,并且leader从不会覆盖本地已经存在的日志条目。

    Raft使用投票流程来防止候选人赢得选举,除非候选人的日志包含了所有已提交的日志条目。候选人必须能够联系上集群中的多数服务器以便能够当选,这意味着每个已提交的日志必须出现在其中至少一个服务器上。如果候选人的日志至少与其它多数日志一样是最新的(怎么才是最新的将在下面精确定义),那么它将持有所有的已提交条目。RequestVote RPC实施这么一条约束:RCP请求中必须包含候选人的日志信息,并且如果投票人的自身日志比候选人的日志更加新时,投票人要拒绝投票,

    Raft决定两个日志哪个是最新的,是通过对比各自日志中的最后一个条目中的index和任期号。如果日志中的最后条目有不同的任期号,那么包含较后的任期的日志就是最新的。如果日志最后条目有着相同任期,那么哪个日志的index更大,则哪个是最新的。

5.4.2 提交以前任期中的条目

正如章节5.3所描述的,一旦来自leader当前任期的条目被多数服务器存储,那么leader就知道该条目已经被提交了。如果leader在提交某个条目之前崩溃,将来的新leader会尝试完成该条目的复制。然而,一个leader不能立即得出结论说,来自之前任期的条目一旦被存储在多数服务器上,就被提交。图8展示了旧日志条目被存储到多数服务器上,然而依然被将来的leader覆盖的一种情形。

                  图8

    图8: 按照时间顺序显示为什么leader不能决定提交来自旧的任期的日志条目。框中编号是任期号,最上面的表示日志的index。 在(a)中,S1是leader,并且部分地复制了idnex 2的条目。 在(b)中,S1崩溃;S5通过S3、S4和自身的投票成为了leader,任期号是3。接收了index 2的不同的条目。 在(c)中,S5崩溃;S1重启,被选为leader,继续复制。在这个时间点上,index 2中任期为2的条目被复制到了多数服务器上。但它还没有被提交。如果S1像(d)中的那样崩溃,S5可能被选举为leader(通过S2、S3、S4的投票)并且用当前任期3的条目覆盖之前任期2的条目。然而,如果S1在崩溃前,复制了当前任期的条目到多数服务器上,如(e)所示,那么这个条目就会被提交(S5不可能赢得选举)。在这个时间点上,所有之前的条目也会被提交。

    为了消除像图8中的问题,Raft绝不使用通过计算副本数的方式来提交之前任期的条目。只有来自当前任期的日志条目才使用计算副本数来提交;一旦来自当前任期的条目被提交,那么所有之前的条目也会间接地提交。因为Log Matching性质。有一些情形能够很安全地得出结论说旧的日志条目已经被提交(比如说,如果条目存储在所有的服务器上),但是为了简化问题,Raft使用了更保守的方式。
    Raft在提交策略上引出额外的复杂度,是因为leader复制之前任期内的日志条目时, 保留了条目原来的任期。在其他的一致性算法中,如果新的leader需要复制志气任期内的日志条目时,它必须使用当前的任期号。Raft的方法让推导日志条目时更简单,因为这些条目一直都保留着相同的任期号。另外,Raft的新leader在发送之前任期的条目时,相比其他算法,发送的更少。(其他算法必须在提交之前,发送更多的冗余条目来为它们重新编号)。

5.4.3 安全性论证

    给出了完整的Raft算法之后,我们现在可以更加精确地讨论Leader完整性性质的成立(这个讨论是基于安全性证明;见章节9.2)。我们假设leader完整性不成立,然后我们证明存在矛盾。假设任期T的leader,在它的任期中提交了一个日志条目,但是这个日志条目在一些将来的任期的leader中没有存储。假设任期U是没有存储那个日志条目的leader中所有任期 > T中最小的任期。

                              图9

    图9:如果S1(任期T内的leader)提交了一个该任期的新的日志条目,并且S5在之后的任期U中选为leader,那么至少存在一个服务器(S3)即接收了那个日志条目,也为S5投了票

  1. LeaderU在选举时,日志中肯定没有那个已提交的日志条目(leader不会删除或者覆盖条目)。
  2. LeaderT复制了那个日志条目到集群的多数服务器删个,并且LeaderU接收到了集群中多数服务器的投票。那么,至少存在一个服务器(投票者),即接收了来自LeaderT的那个条目,也投票了LeaderU。正如图9所示的那样,投票者是达成矛盾的关键
  3. 投票者必须在LeaderU投票之前接收来自LeaderT的那个条目;否则它会拒绝来自LeaderT的AppendEntries请求(它的当前任期肯定大于T)
  4. 投票者在给leaderU投票时,肯定存储了那个条目,因为之前的每一个leader都包含那个条目(根据假设),leader从不删除条目,而follower只删除与leader冲突的条目
  5. 投票者给LeaderU投票,那么LeaderU的日志至少和投票者的日志一样新。这导致了两个矛盾的其中一个。
  6. 首先,如果投票者和LeaderU的最后一个日志的任期相同,那么LeaderU的日志必须至少和投票者的一样新,那么它的日志肯定包含了投票者的每一个条目。这是一个矛盾,因为投票者包含了那个条目,但是LeaderU假设是没有包含的
  7. 否则,LeaderU的最后一个日志的任期必须大于投票者,此外,它还大于T,因为投票者的最后一个日志的任期至少是T(投票者包含了任期T内的那个日志)。创建了LeaderU的最后一个日志的之前的leader的日志中肯定包含那个已提交的条目(根据假设)。那么,根据日志匹配性质,LeaderU的日志必须也包含那个已提交的日志,这就是矛盾
  8. 矛盾的证明完成了。因此,任何任期大于T的leader,都必须包含来自任期T的所有已提交的条目。
  9. 日志匹配性质保证了将来的leader也会包含间接提交的条目,比如图8(d)中的index 2

    通过Leader完整性性质,我们可以证明图3中的状态机安全特性,即如果服务器应用了某个给定index的日志条目,那么没有其他服务器会在相同的index处应用不同的条目到状态机中。在一个服务器应用一个日志条目到状态机时,它的日志和leader的日志从开始到该日志条目都相同,并且该日志条目已经被提交。现在考虑如下最小任期号:一个服务器应用了该任期的某个给定的index;日志完整性质保证更高任期的leader存储了相同的条目,这样服务器在之后的任期中应用该index的日志条目时,肯定会是相同的值。因此,状态机安全性成立。

    最终,Raft要求服务器按照日志index的顺序应用条目。结合状态机安全性,这意味着所有的服务器,都将按照相同的顺序,应用相同的日志条目集合到他们的状态机中。

5.5 Follower和candidate崩溃

    在这个点之前,我们一直聚焦于leader的故障。Follower和candidate的崩溃相比leader的崩溃要更容易处理,并且它们都使用相同的方式处理。如果一个follower或者candidate崩溃,那么将来发送RequestVote和AppendEntries RPC给它就会失败。Raft通过无限地重试来处理这些失败;如果崩溃的服务器重启了,那么RPC将会成功完成。如果服务器在完成了RPC之后,回复RPC之前崩溃,那么在服务器重启之后,它会收到相同的RPC请求、Raft RPC是幂等的,因此不会有问题。例如,如果follower收到AppendEntires请求,包含了本地已经存在的条目,那么它会忽略新请求中的这些条目。

5.6 定时和可用性

    我们对Raft的其中一个要求就是安全性必须不依赖定时:系统不能仅仅因为一些事件的发生比预期的更快或者更慢而产生不正确的结果。然而,可用性(系统及时响应客户端的能力)必将依赖于定时。例如,服务器崩溃之后,与该服务器之间的信息交换必然比通常的时候花费更长的时间,候选人的等待时间将不足以完成选举;没有一个稳定的leader,Raft就不能取得进展。

    Leader选举是Raft定时最关键的部分。Raft将能够选举并维护一个稳定的leader,只要系统满足接下来的定时要求:

广播时间(broadcastTime) << 选举超时时间(electionTimeout) << 平均故障间隔时间(MTBF)
在这个不等式中,广播时间是并发发送RPC到集群中的各个服务器,并且接收到它们的响应的平均花费时间;选举超时时间是章节5.2描述的选举超时时间;平均故障间隔时间,是一个服务器,两次故障的平均时间。广播时间应该比选举超时时间少一个量级,这样leader能够可靠地发送心跳消息,用来防止follower发起选举。给定的超时时间中使用随机化的方法,这个不等式也会使得投票分裂不可能。选举超时时间应该比平均故障间隔时间少上几个量级,这样系统才能稳定运行。当leader崩溃时,系统将在粗略的选举超时时间内不可用;我们希望这只代表整个时间的一小部分。

    广播时间和平均故障时间是底层系统的属性,然而选举超时时间是我们必须选择的。Raft的 RPC通常要求接受者将信息保留到稳定的存储中,因此广播时间的范围一般是 0.5毫秒到20毫秒,取决于存储的技术。因此,选举超时时间可能需要再10毫秒到500毫秒之间。通常服务器的平均故障时间是几个月或者更久,很容易满足定时的要求。

6. 集群成员变更

    直到现在为止,我们一直假设集群的配置(一致性算法中参与的服务器集合)是固定的。实际上,修改配置偶尔是有必要的,例如当服务器故障时替换它们,或者更改复制程度。尽管这些可以通过,让集群离线,更新配置文件,然后重启集群来完成,但是这样会导致集群在成员转换过程中不可用。此外,如果其中有手动的操作,他们有操作错误的风险。为了避免这些问题,我们决定让配置变更自动化,并且在Raft一致性算法中包括他们。

    为了保证配置更改的机制安全,必须保证在转换的过程中,不会出现相同任期内选举出两个leader的可能。不幸的是,服务器直接从旧配置切换到新配置的任何方法都不安全。不可能自动的立刻完成所有服务器的切换,因此集群在转换过程中有潜在的分裂成两个独立的多数的问题(见图10)

                       å›¾10

            图10:直接从旧的配置切换到新的配置不安全,因为不同的服务器会在不同的时间发生切换。再这个例子中,集群从3个服务器扩展到5个服务器。不幸的是,存在一个时间点,两个不同的leader会当选,有着相同的任期,一个有着旧配置的多数(Cold),另外一个有着新配置的多数(Cnew)。

    为了确保安全,配置变更必须使用两阶段的方法。有许多中方法实现一个两阶段。例如,有些系统(比如【22】)使用第一阶段禁用旧配置这样它不会处理客户端请求;然后在第二阶段启动新配置。在Raft中,集群的第一个阶段,切换到过渡的配置,我们称为联合一致性;一旦联合一致性被提交,系统就可以切换到新的配置。联合一致性结合了旧的配置和新的配置:


  • 日志条目复制到两个配置的所有服务器上
  • 来自任何一个配置的服务器都可以成为leader
  • 达成一致(选举和条目提交)需要满足各自配置的多数

联合一致性允许单个服务器在不妥协安全性的前提下,在不同的时间上进行配置切换过程。另外,联合一致性允许集群在配置变更的过程中继续服务器客户端请求。

    集群配置在复制日志中,使用特殊的条目存储和通信。图11展示了配置变更的过程。

图11

        图11:配置变更的时间线。虚线显示配置实体已经被创建,但是还没被提交,实线显示最新的被提交的配置条目。leader首先创建Cold,new配置实体在它的日志中,并且提交该条目到Cold,new(Cold的多数服务器和Cnew的多数服务器)。然后它创建Cnew条目,并且将它提交到Cnew的多数服务器上。ColdCnew没有时间点两者都可以独立地做决定。

    当leader收到配置从ColdCnew的变更请求时,它就为联合一致性将配置作为日志条目存储(图11中的Cold,new ),并且使用之前介绍的机制复制日志。一旦一个服务器添加新的配置条目到它的日志中,它就在将来的决定(服务器总是使用日志中最新的配置,而不管该条目是否已经被提交)中使用该配置。这意味着leader将要使用Cold,new的规则来决定Cold,new的条目什么时候被提交。如果leader崩溃,新的leader可能在Cold或者Cold,new中选择,取决于获胜的候选人是否收到了Cold,new。在任何情况下,在这个阶段,Cnew不能做出单方面的决定。

    一旦Cold,new被提交,不管是Cold还是Cnew,都不能不通过对方批准就做决定,并且leader完整性性质保证只有包含Cold,new日志条目的服务器才能被选举为leader。现在leader创建和复制描述的Cnew日志条目是安全的。再次的,这个配置在服务器收到之后就立即生效。当新的配置在Cnew的规则下被提交,旧的配置就是不相干的,并且不在新配置中的服务器就可以被关闭了。像图11中显示的那样,没有ColdCnew可以一起做单方面决定的时刻;这样保证了安全性。

    关于配置变更,还有三个问题需要解决。第一个问题是新的服务器初始时可能没存储任何日志条目。如果这些服务器以这样的状态加入集群,它们会花一段时间去追赶,在这段时间内,它们不能提交新的日志条目。为了避免系统在这段时间内的不可用,Raft在配置变更前引入了一个额外的阶段,在这个阶段内,新的服务器作为无投票权成员(leader会复制日志条目给它们,但是考虑多数的时候不考虑它们)加入集群,一旦新的服务器已经追上了集群中的其他服务器,配置变更就可以按照上面的方式进行了。

    第二个问题是集群leader可能不在新的配置中。这种情况下,一旦Cnew的日志条目被提交,leader就退回到follower。这意味着有这么一个时期(leader提交Cnew期间),leader管理着一个不包括自己的集群;它复制日志条目,但是考虑多数时不计算自己。当Cnew被提交后,leader发生切换,因为这是新的配置独立运行的第一个时间点(将总是能够在Cnew的配置中选出leader)。在这个点之前,可能只能从Cold中选出leader。

    第三个问题是移除的的服务器(那些不在Cnew中的服务器)可能破坏集群。这些服务器不再收到心跳,因此它们会超时,并且开始发起新的选举。然后它们会发送带有新的任期号的RequestVote RPC。这个会导致当前leader退回到follower状态。一个新的leader最终会选举出来,但是被删除的服务器会再次超时,并且这个过程会一直重复,导致系统非常差的可用性。

    为了防止这个问题,服务器忽视RequestVote RPC当它们相信当前的leader存在时。特别地,如果一个服务器在最短的选举超时时间内收到一个来自当前leader的RequestVote RPC,它不会更新它的任期或者投票。这个不会影响正常的选举,每个服务器在开始选举前,都要等待最短的选举超时时间。然而,它帮助我们避免移除服务器的破坏:如果leader能够发送心跳给集群,那么它就不会被更大的任期号罢免。

 7. 日志压缩

    Raft的日志在正常操作中,随着包含更多的客户端请求而不断增长,但是在实际的系统中,它不能没有边界地增长。

----------------未完待续



评论

发表评论