云南昆明做网站,深圳市易百讯科技有限公司,电商网站开发需要多少钱,垦利区建设局网站Abstract
Raft是一种用于管理replicated log的consensus algorithm。它能和Paxos产生同样的结果#xff0c;有着和Paxos同样的性能#xff0c;但是结构却不同于Paxos#xff1b;它让Raft比Paxos更易于理解#xff0c;并且也为用它构建实际的系统提供了更好的基础。为了增强…Abstract
Raft是一种用于管理replicated log的consensus algorithm。它能和Paxos产生同样的结果有着和Paxos同样的性能但是结构却不同于Paxos它让Raft比Paxos更易于理解并且也为用它构建实际的系统提供了更好的基础。为了增强可理解性Raft将例如leader election, log replication以及safety等共识的关键元素进行了分离并且提供了更强的一致性用于减少必须考虑的状态。从用户调查的结果来看Raft比Paxos更易于学生学习。Raft包含了一种新的机制用于改变cluster membership并通过overlapping majority来保证安全性。
1 Introduction
Consensus algorithm允许一群机器像一个整体一样工作即使其中的一些成员发生故障也不会出现问题。正因为这一点它在构建可靠的大规模软件系统的过程中起着关键的作用。Paxos一直主导着过去十年对consensus algorithm的讨论许多共识的实现都基于Paxos或者受到它的影响并且Paxos已经成为了用来教授学生关于共识的主要工具。
不幸的是Paxos太难以理解了尽管已经做了很多尝试想使它变得更加平易近人。另外为了支持实际的系统它的结构需要做非常复杂的改变。因此系统架构师和学生都对Paxos感到很痛苦。
在我们自己和Paxos经历了一番痛苦挣扎之后我们决定发明一种新的consensus algorithm来为系统的构建和教学提供更好的基础。我们的主要目标有点特别是为了让它更加易于理解我们是否能为实际的系统定义一个consensus algorithm并且描述它的方式能比Paxos更加易于理解此外我们想要该算法有利于the development of intuitions而这对系统构建者是必不可少的。算法能工作很重要但是能清楚地显示它为什么能工作同样非常重要。
这项工作的结果就是一个叫做Raft的consensus algorithm。在设计Raft的时候我们使用了一些额外的技术用于提供可理解性包括decompositionRaft分离了leader election, log replication和safety以及状态空间的减少和Paxos相比Raft降低了不确定性以及sever之间能达到一致的方法。一个由来自两个大学的43位学生组成的用户调查显示Raft要比Paxos易于理解的多在同时学习了两种方法之后其中的33名学生回答Raft的问题要比回答Paxos更好。
Raft在很多方面和现存的consensus algorithm类似但是它有以下这些独特的特性
Strong leaderRaft比其他consensus algorithm使用了更强形式的leadership。比如log entry只能从leader流向其他server。这简化了对于replicated log的管理并且使Raft更加易于理解。Leader electionRaft使用随机的时钟来选举leader。这只是在原来所有的consensus algorithm都需要的heartbeats的基础上增加了小小的一点东西但是却简单快速地解决了冲突。Membership changesRaft通过一种新的joint consensus的方法来实现server集合的改变其中两个不同配置下的majority在过度阶段会发生重合。这能让集群在配置改变时也能继续正常运行。
我们相信不论对于教学还是用于真实系统实现的基础Raft都要优于Paxos和其他的共识算法。它比其他算法更简答也更加易于理解它能完全满足实际系统的需求它有很多开源的实现并且被很多公司使用它的安全性已经被完全证实了并且它的效率也完全可以和其他算法相媲美。
论文的剩余部分介绍了replicated state machine问题Section 2讨论了Paxos的优缺点Section 3描述了可理解性的一般方法Section 4描述了Raft consensus algorithmSection 5-7评估RaftSection 8并且讨论了相关工作Section 9。Raft中的一小部分元素在这里因为篇幅的原因省略了但是它们可以在一份扩展的技术报告里找到。其余的内容描述了client怎么和系统进行交互以及Raft log的空间怎么被回收。
2 Replicated state machines
consensus algorithm通常在replicated state machine的上下文中出现。在这种方法中一群server上的state machine对同一个状态的拷贝进行计算即使其中一些server宕机了也能正常运行。Replicated state machine通常用于解决分布式系统中的容错问题。例如拥有单一的cluster leader的大规模系统例如GFSHDFS和RAMCloud通常会用一个单独的replicated state machine来管理leader的选举以及存储一些在拯救leader崩溃的配置信息。Replicated state machine典型的例子包括Chubby和ZooKeeper。 Replicated state machine通常用一个replicated log来实现如Figure 1所示。每一个server存储了一个包含一系列命令的log而它的state machine顺序执行这些命令。每一个log以同样的顺序包含了同样的指令所以每一个state machine都会处理相同的命令。因为每一个state machine都是确定性的因此计算将得到同样的状态和输出结果。
Consensus algorithm的作用是保证replicated log的一致性。server中的consensus module用于从client处接受命令并且将它们加入log。它会和其他serer的consensus module进行通信从而确保每一个log都以相同的顺序包含相同的请求每一个server的state machine都按顺序处理它们的log并且将输出返回给client。最终这些server呈现出的是一个单一的高度可靠的state machine。
用于实际系统的consensus algorithm通常具有以下特性
在所有的non-Byzantine条件下要确保正确性从不返回一个错误的结果包括网络延迟分区以及网络包的丢失重复和乱序。只要majority of servers是可操作的并且能相互之间进行通信以及和client进行通信那么系统必须是可用的。因此一个由五台server组成的集群必须能忍受两台server的故障。Server发生故障时可以认为是暂停了它们可能稍后会从恢复到存储在stable storage中的状态并且重新加入集群。它们不依赖于时间来确保log的一致性fault clocks和extreme message delays在最差的情况下也只能导致系统不可用的问题。通常情况下当集群中的大多数server已经对单一的RPC做出相应时可以认为一个命令完成了。少数慢的server不应该影响整个系统的性能。
3 Whats wrong with Paxos?
在过去的十年中Leslie Lamport的Paxos协议几乎成了consensus的同义词它是在课程中最常被教授的协议并且很多consensus的实现都以它作为起点。Paxos首先定义了一个在单一的decision上能达到agreement的协议例如一个单一的replicated log entry。我们将这样的一个子集称之为single-decree Paxos。之后Paxos可以将该协议的多个实例组合在一起去形成一系列的decision作为logmulti-Paxos。Paxos保证了safety和liveness并且它支持cluster membership的改变。它的正确性已经被证明了并且在一般的情况下也被证明是高效的。
不幸的是Paxos有两个重要的缺陷。第一个缺陷是Paxos太难以理解了。它的完整描述是出了名的晦涩很少有人能成功理解它即使能也是花了很大的功夫。因此已经做了很多尝试试图用一个更简单的版本解释Paxos。虽然它们都着力于single-decree版本但是仍然非常具有挑战性。在一项针对NSDI 2012与会者的调查中我们发现很少有人对Paxos感到舒服即使是那些经验丰富的研究人员。我们自己也对Paxos感到非常痛苦我们在不能理解完整的协议直到我们阅读了几个简化版的描述以及设计了我们自己的替代协议而这整个过程持续了将近一年。
我们认为Paxos的晦涩来源于它将single-decree subset作为自己的基础。Single-decree Paxos被认为是微妙的它被划分为两个不能用直觉来显示的阶段并且不能单独理解。因此这就导致了很难对single-decree protocol是如何工作的建立起直觉。而multi-Paxos的composition rule则更加添加了复杂性。我们坚信对于在multiple decision的情况下到达consensus这个问题肯定能以其他更直接更明显的方式被分解。
Paxos的第二个问题是它并没有为实际的实现提供一个很好的基础。一大原因是对于multi-Paxos没有一个广受认可的算法。Lamport的描述主要针对的是single-decree Paxos它为multi-Paxos提供了一个大概的框架但是很多细节并没有提及。对于充实以及优化Paxos已经做了很多努力但是它们各自之间以及和Lamport的概述都不相同。像Chubby这样的系统已经实现了类Paxos算法但是它的很多细节并没有公开。
另外Paxos的架构也不利于构建实际系统这是它按single-decree分解的另一个后果。例如独立地选取一系列的log entry并且将它们融合成一个顺序的log并没有太多好处仅仅只是增加了复杂度。相反构建一个围绕按顺序扩展log的系统是更简单和高效的。Paxos的另一个问题是它将对称的peer-to-peer作为核心虽然在最后为了优化性能建议了一种弱形式的leadership。这在只需要做一个decision的简单场景中是可行的但是很少有实际的系统会使用这种方法。如果要有一系列的decision要决定那么先选择一个leader然后再让leader去协调decision。
因此实际系统很少和Paxos类似。各种实现都以Paxos开始然后发现实现起来很困难于是最后开发出了一个完全不同的架构。这是极其费时并且容易出错的而Paxos的难以理解则更加加剧了这个问题。Paxos的正确性理论很好证明但是实际的实现和Paxos太过不同因此这些证明就没什么价值了。接下来这段来自Chubby的评论是非常典型的
Paxos算法的描述和现实世界的系统的需求之间有巨大的矛盾....而最终的系统都将建立在一个未经证明的协议之上
因为这些问题的存在我们得出这样的结论Paxos并没有为实际系统的构建或者是教学提供一个很好的基础。基于在大规模软件系统中consensus的重要性我们决定尝试能否设计出另外一种比Paxos有着更好性质的consensus algorithm。而Raft就是我们实验得到的结果。
4 Designing for understandability
我们在设计Raft的时候有以下几个目标它必须为系统的构建提供完整并且实际有效的基础而这能极大地减少开发者的设计工作它必须在所有条件下都是安全的在典型的操作条件下是可用的在通常的操作中是高效的。但我们最重要的目标也是最大的挑战就是可理解性。我们必须让广大的读者能比较容易地理解这个算法。并且要能够建立对这个算法的直觉从而让系统构建者能做一些实际实现中必要的扩展。在设计Raft的很多节点上我们要在很多可选方法之间做出选择。在这些情况下我们基于可理解性对这些方法进行评估对于每一个可选方案的描述是否困难比如它的状态空间的复杂度是多少以及它是否有subtle implication以及读者是否能轻松地完全理解这种方法。
后来我们意识到这种分析方法具有很强的主观性于是我们使用了两种方法让分析变得更具通用性。第一种是关于问题分解的众所周知的方法是否有可能我们可以将问题分解为可以被相对独立地解释理解并且被解决的几部分。例如在Raft中我们分解了leader election, log replication, safety和membership changes这几部分。
我们的第二种方法是通过减少需要考虑的状态数尽量让系统更一致以及尽可能地减少非确定性来简化state space。另外log不允许存在holeRaft限制了log之间存在不一致的可能。虽然在大多数情况下我们都要减少不确定性但是在某些情况下不确定性确实提高了可理解性。特别地随机化的方法会引入不确定性但是通过以相同的方式处理所有可能的选择choose any; it doesnt matter确实减少了state space。我们就使用了随机化来减少了Raft的leader election algorithm。 5 The Raft consensus algorithm
Raft是一种用于管理Section 2中所描述的形式的replicated log的算法。Figure 2以精简的形式概述了这一算法而Figure 3列出了该算法的关键特性而这些特性将在本节的剩余部分分别进行讨论。
Raft首先通过选举一个distinguished leader来实现consensus然后将管理replicated log的责任全部给予这个leader。leader从client处接收log entry再将它备份到其他server中接着告诉server什么时候能安全地将log entry加入state machine中。leader的存在简化了replicated log的管理。比如leader可以在不询问其他leader的情况下决定将新的entry存放在log的什么位置并且数据简单地从leader流向其他server。leader可能会发生故障或者和其他server断开在这种情况下会有新的leader被选举出来。
通过选举leaderRaft将consesus problem分解成三个相对独立的子问题它们会在接下来的子章节中讨论
Leader election在一个已有的leader故障之后必须要有一个新的leader被选举出来Section 5.2Log replicationleader必须从client处接收log entry并且将它们在集群中进行备份强制使其他log与它自己一致Section 5.3SafetyRaft中最关键的safety property就是Figure 3所示的State Machine Safety Property如果有任何的server已经将一个特定的log entry加入它的state machine中那么其他的server对于同一个log index的log entry必须相同
在展示了consensus algorithm之后本节将讨论可用性以及时间在系统中扮演的角色 5.1 Raft basics
一个Raft集群包含多个server一般都是五个因此系统能忍受两台机器的故障。在任意给定时刻每个server都处于以下三个状态中的一个leaderfollower或者candidate。在正常情况下只有一个leader其他都是follower。follower是很被动的它们不会自己发送请求只是简单地对来自leader和candidate的请求进行回复。leader对所有来自client的请求进行处理如果一个client和follower进行交互follower会将它重定向给leader第三种状态candidate是用来选举Section 5.2中描述的新的leader。Figure 4显示了各种状态以及它们之间的转换关于转换将在下文进行讨论。 Raft将时间划分成任意长度的term如Figure 5所示。Term以连续的整数进行编号。每个term以一个election开始这个阶段会有一个或多个candidate竞选leader如Section 5.2所示。 如果一个candidate竞选成功那么它将在term剩下的时间里作为leader。在有些情况下一个election可能导致一个split vote。在这种情况下term将以一种没有leader的状态结束而一个新的term伴随着一个新的选举将马上开始。Raft将保证在给定的一个term中总是最多只有一个leader。
不同的server可能在不同的时间观察到term的转换而在有些情况下一个server可能会观察不到election甚至是一个完整的term。term在Raft中扮演的是一个logical clock的角色它能够让server去检测那些需要淘汰的信息例如过时的leader。每个server都存储了一个current term number它会随着时间单调递增。current term会随着server之间的交互而改变如果一个server的current term比其他的小那么它就会将自己的current term更新到更大的值。如果一个candidate或者leader发现它的term已经过时了那么它就会立即恢复到follower state。如果一个server接收到一个来自过时的term的请求那么拒绝它。
Raft servers之间通过RPC进行通信而consensus algorithm需要两种类型的RPC。RequestVote RPC由candidate在election期间发起Section 5.2AppendEntries RPC由leader发起用于备份log entry和提供heartbeatSection 5.3。如果一个server没有收到回复那么它会及时重发RPC并且它们会并行发送RPC用于提高性能。
5.2 Leader election
Raft使用一种heartbeat mechanism 来触发leader election。当server启动的时候默认作为follower。server如果能持续地从leader或者candidate处获取合法的RPC那么它将始终保持follower状态。为了保持自己的权威性leader会阶段性地发送heartbeats(不带有log entry的AppendEntry RPC)给所有的follower。如果一个server在一个叫做election timeout的时间段中没有收到交互信息那么它就会认为不存在一个viable leader并且开始一轮新的election选出新的leader。
为了开始一个electionfollower会增加它的current term并且转换为candidate state。接着它会投票给自己并且并行地给集群中的其他server发送RequestVote RPC。candidate将持续保持这种状态直到以下三个条件中的一个被触发(a) 它赢得了选举(b) 另一个server宣布它自己是leader或者(c) 过了一段时间之后也没有winner。这些情况将在接下来分别进行讨论。
如果一个candidate收到了来自集群中的majority个server对于同一个term的投票那么它将赢得election。每一个server在给定的term中都最多只会投票给一个candidate并且基于first-come-first-serverd原则Section 5.4中将对于投票添加一个额外的约束。majority原则确保了在一个给定的term中最多只有一个candidate可以赢得electionFigure 3中的Election Safety Property。一旦一个candidate赢得了election它将成为leader。之后它将向所有其他的server发送hearbeat用以确保自己的权威并且防止新一轮的election。
当在等待投票时一个candidate可能会收到来自另一个server的AppendEntry RPC声称自己是leader。如果该leader的term包含在该RPC中至少和candidate的current term一样大那么candiate认为该leader是合法的并且返回到follower的状态。如果RPC中的term比candidate的current term要小那么candidate会拒绝该RPC并且依然保持为candidate状态。
第三种可能的情况是一个candidate在election中既没有赢也没有输如果在同一时刻有很多follower成为了candidate投票将会分裂因此没有candidate会获得majority。当这种情况发生时每个candidate都会timeout并且通过增加term和发送新一轮的RequestVote RPC来开始新的election。然而如果没有额外的措施splite vote可能会一直重复下去。 Raft使用随机的election timeout来确保split vote很少会发生并且保证即使发生了也很快会被解决。为了在一开始就避免split ovteelection timeout会在一个固定区间内随机选择e.g., 150-300ms。这就将server铺散开来从而保证在大多数情况下只有一个server会timeout它将赢得election并且在其他的server timeout之前发送heartbeat。同样的机制也被用在处理split vote上。每个candidate在election开始的时候重新随机确定一个election timeout并在下一次election开始前静静等待timeout的到来这就减少了在下一个新的election的时候发生split vote的可能。Section 8.3展示了使用这种方法快速选择一个leader的过程。
Election是一个展示可理解性作为指导我们做出设计选择的一个很好的例子。一开始我们计划使用一个rank system每个candidate都会赋予一个唯一的rank它会被用来在相互竞争的candidate之中做出选择。当一个candidate发现另一个candidate有更高的rank那么它就会退回到follower的状态从而让有更高rank的candidate能更容易赢得下一轮election。但我们发现这种方法会在可用性方面产生一些微妙的问题如果有着更高rank的server发生了故障一个低rank的server可能需要timeout并且重新成为candidate但是这个过程发生地太快则会引发新的leader选择过程。我们对这一算法做了多次调整但是每次调整之后都有新的corner cases产生。最后我们得出结论随机重试的方法是更明显也更易理解的方法。
5.3 Log replication
一旦一个leader被选择出来以后它开始处理client request。每个client request都包含了需要由replicated state machine执行的command。leader用command扩展log作为新的entry接着并行地给其他server发生AppendEntry RPC来备份entry。当该entry被安全地备份之后如下所述leader会让它的state machine执行该entry并且将执行结果返回给client。如果follower崩溃了或者运行很慢抑或是丢包了leader会不停地重发AppendEntry RPC直到所有的follower最终都保存了所有的log entry。 Log以Figure 6中的形式被组织。当一个entry被leader接收的时候每个log entry都会包含一个state machine command和term number。log entry中的term number是用来检测log之间的不一致性并且确保Figure 3中的一些特性的。同时每个log entry都有一个整数的index用于标示它在log中的位置。
leader决定何时让state machine执行log entry是安全的而这样的entry叫做committed。Raft保证所有committed entry都是durable并且最终会被所有可用的state machine执行。一旦创建它的leader已经将它备份到majority个server中log entry就会被committede.g., Figure 6中的entry 7。同时它也会commit leader的log中所有前缀的entry包括那些由之前的leader创建的entry。Section 5.4中会讨论在leader改变之后应用这条规则会产生的一些微妙的问题同时它也会展示这样的关于的commitment的定义是安全的。leader会追踪它已知被committed最高的index并且会在之后的AppendEntry RPC包括heartbeat包含这个index从而让其他server能发现它。一旦follower知道了一个log entry被committed它最终会让本地的state machine运行这个entry以log的顺序。
我们设计了Raft log mechanism来保持不同server的log之间的高度一致性。这不仅简化了系统行为让它们变得可预测并且这也是确保安全性的重要组件。Raft维护了以下特性它们合起来构成了Figure 3所示的Log Matching Property
如果不同的log中的两个entry有相同的index和term那么它们存储相同的command如果不同的log中的两个entry有相同的index和term那么它们前缀的entry都是相同的
第一个特性确保了leader对于给定的log index和term它最多产生一个entry,并且log entry永远不会改变它在log中的位置。第二个特性则由AppendEntry一个简单的一致性检查来保证。在发送一个AppendEntry RPC的时候leader会在其中包含新的entry之前的那个entry的index和term。如果follower没有在log中有同样index和term的entry那么它就会拒绝新的entry。一致性检查扮演了induction steplog的initial empty state是满足Log Matching Property的而一致性检查则在log扩展的时候保证了Log Matching Property。因此当AppendEntry成功返回的时候leader就知道该follower的log和它自己是一致的。
在进行正常操作的时候leader和follower的操作始终是一致的因此AppendEntry的一致性检查用于不会失败。但是leader崩溃会导致log处于不一致的状态老的leader可能还没有将它log中的所有entry完全备份。而这些不一致性可能随着一系列的leader和follower的崩溃而叠加。Figure 7说明了follower的log可能和新的leader不一致的情况。follower中可能会遗漏一些leader中的entry同时它里面也可能有一些leader中没有的额外的entry或者两者都有。log中遗失的或者额外的entry中可能跨越多个term。 为了让follower的log和自己保持一致leader必须找到两个log一致的最远的entry并且删除follower该entry之后所有的entry。所有这些操作都用于回应AppendEntry RPC的一致性检查。leader为每一个follower维护了一个nextIndex它代表了leader将会发送给follower的下一个log entry。当一个leader刚刚开始执行的时候它会将所有的nextIndex都初始化为它自己log的最后一个entry的index加一Figure 7中的11。如果follower和leader的log不一致AppendEntry RPC的一致性检查会在下一个AppendEntry RPC的时候失败。在收到一个rejection之后leader会减小它的nextIndex并且重发AppendEntry RPC。最终nextIndex会达到leader和follower的log匹配的状态。此时AppendEntry会成功返回移除了follower的log中冲突的entry并且会根据leader的log进行扩展如果有的话。一旦AppendEntry成功follower已经和leader的log一致了而且将在term的接下来部分保持。该协议可以通过减少rejected AppendEntry RPC的数目来优化。
在这种机制下leader不用在它刚刚成为leader的时候执行任何额外的动作用于恢复log的一致性。它只是正常地开始执行并且log会随着AppendEntry一致性检查的失败而不断收敛。leader从来不会覆写或者删除它自己log的entryFigure 3中的Leader Append-Only Property。
该log replication mechanism展示了Section 2中想要达到的consensus propertyRaft可以接收备份并且执行新的log entry只要有majority个server活着在正常情况下一个新的entry会在单一的一轮RPC中被备份到cluster的一个majority中因此一个运行较慢的follower并不会影响性能。
5.4 Safety
在前面的章节中描述了Raft如何选举leader以及备份log entry。但是之前描述的机制并不足以保证每个state machine以同样的顺序执行同样的command。比如follower可能在leader commit多个log entry的时候一直处于不可用的状态而之后它可能被选作leader并且用新的entry覆写这些entry因此不同的state machine可能会执行不同的command sequences。
本节中我们通过给哪些server能被选举为leader增加约束来完善Raft算法。该约束确保任何给定的term的leader会包含之前term所有commit的entryFigure 3中的Leader Completeness Property。通过增加election restriction我们更加细化了commitment的规则。最后我们展示了Leader Completeness Property的证明草图并且展示了它如何能让replicated state machine正确操作。
5.4.2 Election restriction
任何leader-based consensus algorithmleader最终都必须存储所有的committed log entry。在一些consensus algorithm中例如Viewstamped Replication即使一开始没有包含全部的committed entry也能被选为leader。这些算法都会包含额外的机制用于识别遗失的entry并且将它们传输给新的leader要么在election期间要么在这不久之后。不幸的是这需要额外的机制以及复杂度。Raft使用了一种更简单的方法它保证在选举期间每个新的leader都包含了之前term都包含的所有entry从而不需要将这些entry传输到leader。这意味着log entry的流动是单方向的只从leader流向follower而leader从不会覆写log中已有的entry。
Raft使用voting process来防止那些log不包含全部committed entry的candidate赢得election。candidate为了赢得选举必须和cluster的majority进行交互这意味着每个committed entry必须都在其中的一个majority存在。如果一个candidate的log至少和任何majority中的log保持up-to-dateup-to-date将在下文精确定义那么它就包含了所有committed entry。RequestVote RPC实现了这一约束RPC中包含了candidate的log信息voter会拒绝投票如果它自己的log比该candidate的log更up-to-date。
Raft通过比较log中last entry的index和term来确定两个log哪个更up-to-date。如果两个log的last entry有不同的term那么拥有较大term的那个log更up-to-date。如果两个log以相同的term结束那么哪个log更长就更up-to-date。 5.4.2 Committing entries from previous terms
如Section 5.3中所述leader知道current term中的entry已经被提交了一旦该term已经被majority个server存储了。如果一个leader在committing an entry之前就崩溃了那么未来的leader就会试着完成该entry的备份。但是leader很难马上确认之前term的entry已经commited一旦它被存储于majority个server中。Figure 8展示了这样一种情况一个old log entry已经被存储在majority个server中但是它仍然可以被future leader覆写。
为了防止Figure 8中这样问题的发生Raft从不会通过计算备份的数目来提交之前term的log entry。只有leader的当前term的log entry才通过计算备份数committed一旦当前term的entry以这种方式被committed了那么之前的所有entry都将因为Log Matching Property而被间接committed。其实在很多情况下leader可以非常安全地确定一个old entry已经被committed了比如如果该entry已经被存储在所有server中了但是Raft为了简单起见使用了一种更保守的方法。
因为leader从之前的term备份entry时log要保留之前的term number这会让Raft在commitment rule中引入额外的复杂度。在其他consensus algorithm中如果一个新的leader从之前的term备份entry时它必须使用它自己的新的term number。因为log entry的term number不随时间和log的不同而改变这就能让Raft更加容易地进行推导。另外Raft中的新的leader与其他算法相比只需要从之前的term传输更少的log entry其他的算法必须传输备份的log entry进行重新编号在它们被committed之前。
5.4.3 Safety argument
给出了完整的Raft算法之后我们可以进一步论证Leader Completeness Property成立该论据基于safety proof参见Section 8.2。我们假设Leader Completeness Property是不成立的接着推出矛盾。假设term T的leader(leaderT) commit了一个该term的log entry但是该log entry并没有被未来的term的leader存储。考虑满足大于T的最小的term U它的leader(leaderU)没有存储该entry。 1、该committed entry在leaderU选举期间一定不存在于它的log中leader从不删除或者覆写entry。
2、leaderT将entry备份到了集群的majority中并且leaderU获取了来自集群的majority的投票如Figure 9所示。而voter是达到矛盾的关键。
3、voter一定在投票给leaderU之前已经接受了来自leaderT的committed entry否则它将拒绝来自leaderT的AppendEntry request因为它的current term高于T。
4、当voter投票给leaderU的时候它依然保有该entry因为每个intervening leader都包含该entry(根据假设)leader从不删除entry而follower只删除它们和leader矛盾的entry。
5、voter投票给leaderU因此leaderU的log一定和voter的log一样up-to-date。这就导致了两个矛盾中的其中一个矛盾。
6、首先如果voter和leaderU共享同一个last log term那么leaderu的log至少要和voter的log一样长因此它的log包含了voter的log中的每一个entry。这是一个矛盾因为voter包含了committed entry而leaderU假设是不包含的。
7、除非leaderU的last log term必须比voter的大。进一步说它必须大于T因为voter的last log term至少是T它包含了term T的committed entry。之前创建leaderU的last log entry的leader必须在它的log中包含了committed entry根据假设。那么根据Log Matching PropertyleaderU的log必须包含committed entry这也是一个矛盾。
8、这完成了矛盾。因此所有term大于T的leader必须包含所有来自于T并且在term T提交的entry。
9、Log Matching Property确保了future leader也会包含那些间接committed的entry例如Figure 8(d)中的index 2。
给定Leader Completeness Property证明Figure 3中的State Machine Safety Property就比较容易即让所有的state machine以相同的顺序执行同样的log entry。
5.5 Follower and candidate crashes
直到现在我们一直关注leader failures。follower和candidate的崩溃比起leader的崩溃要容易处理得多而且它们的处理方式是相同的。如果一个follower或者candidate崩溃了那么之后发送给它的RequestVote和AppendEntry RPC都会失败。Raft通过不断地重试来处理这些故障如果崩溃的服务器重启了之后RPC就会成功完成。如果server在完成了RPC但是在回复之前崩溃了那么它会在重启之后收到一个同样的RPC。但是Raft的RPC是幂等的因此不会造成什么问题。比如一个follower接收了包含一个已经在log中存在的entry的AppendEntry request它会直接忽略。
5.6 Timing and availability
我们对于Raft的一个要求是它的安全性不能依赖于时间系统不会因为有些事件发生地比预期慢了或快了而产生错误的结果。然而可用性系统及时响应client的能力将不可避免地依赖于时间。比如因为server崩溃造成的信息交换的时间比通常情况下来得长candidate就不能停留足够长的时间来赢得election而没有一个稳定的leaderRaft将不能进一步执行。
leader election是Raft中时间起最重要作用的地方。当系统满足以下的timing requirement的时候Raft就能够选举并且维护一个稳定的leader
broadcastTime electionTimeout MTBF
在这个不等式中broadcastTime是server并行地向集群中的每个server发送RPC并且收到回复的平均时间electionTimeout就是如Section 5.2中描述的选举超时MTBF是单个server发生故障的时间间隔。broadcastTime必须比electionTimeout小几个数量级这样leader就能可靠地发送heartbeat message从而防止follower开始选举通过随机化的方法确定electionTimeout该不等式又让split vote不太可能出现。electionTimeout必须比MTBF小几个数量级从而让系统能稳定运行。当leader崩溃时系统会在大概一个electionTimeout里不可用我们希望这只占整个时间的很小一部分。
broadcastTime和MTBF都是底层系统的特性而electionTimeout是我们必须选择的。Raft的RPC通常要求接收者持久化信息到stable storage因此broadcastTime的范围在0.5ms到20ms之间这取决于存储技术。因此electionTimeout可以取10ms到500ms。通常server的MTBF是几个月或者更多因此很容易满足timing requirement。
6 Cluster membership changes 直到现在为止我们都假设集群的configuration(参与consensus algorithm的server集合)是固定的。但实际上偶尔改变configuration是必要的比如在server发生故障时将其移除或者改变the degree of replication。虽然这可以通过停止整个集群更新configuration file再重启集群实现但是这会让集群在转换期间变得不可用。另外如果这其中存在手动操作的话还会有操作失误的风险。为了防止这些情况的发生我们决定自动化configuration change并且将它们和Raft consensus algorithm结合起来。
为了保证configuration change mechanism的安全在转换期间不能有任意时刻对于同一个term有两个leader。不幸的是任何从old configuration转换到new configuration的方法都是不安全的。不可能一次性对所有server进行自动转换所以在转换期间集群会被潜在地分隔为两个独立的majority见Figure 10。 为了保证安全性configuration change必须使用two-phase的方法。有很多种方法实现two-phase比如有些系统使用first phase来禁用old configuration从而不能处理client request然后在second phase中使用new configuration。在Raft中集群首先转换到一个transitional configuration我们称作joint consensus一旦joint consensus被committed之后系统就过渡到new configuration。joint consensus 同时结合了old configuration和new configuration。
log entry会被备份到两个configuration的所有server中来自任意一个configuration的server都可能会成为leaderAgreementelection和entry的commitment需要同时得到old configuration和new configuration的majority
joint consensus允许单个的server在不妥协安全性的情况下在不同的时间对进行configuration的过渡。另外joint consensus允许集群在configuration转换期间依旧能够处理来自client的请求。
集群的configuration被存储在replicated log的special entry中并且通过它来通信Figure 11说明了configuration改变的过程。当leader收到了一个将configuration从Cold转换到Cnew请求它会将joint consensus的configurationfigure中的Cold,new作为一个log entry存储并且使用上文描述的机制进行备份。一旦一个给定的server将一个new configuration entry加入它的log中它就会在以后所有的decision中使用该configurationserver总是使用它log中的latest configuration而不管该entry是否被committed。这意味着leader会使用Cold,new来决定何时Cold,new被committed。如果该leader崩溃了一个新的leader可能使用Cold或者Cold,new这取决于winning candidate是否收到了Cold,new。在任何情况下Cnew都不能在这个阶段做单方面的决定。 一旦Cold,new被committedCold或者Cnew就不能在没有对方同意的情况下单独做decision了而Leader Completeness Property则确保了Cold,new的log entry的server才能被选作leader。现在leader创建一个描述Cnew的log entry并且将它备份到整个集群是安全的。同样这个configuration只要server看到它就会生效。当新的configuration在Cnew的规则被committed时old configuration就不再有效了而那些不在new configuration中的server就会被关闭。如Figure 11所示没有一个时刻Cold或者Cnew会单方面做决定这就保证了安全性。 对于reconfiguration还有三个问题需要处理。第一个问题是新加入的server可能初始的时候没有存储任何log entry。如果它们以这种状态直接添加进集群可能会花费相当多的时间让它们赶上来而在这期间就不能commit新的log entry了。为了避免availability gapsRaft在configuration change之前引入了一个additional phase在这期间新的server作为non-voting memberleader将log entry向它们备份但是在计算majority时并不考虑它们加入集群。一旦新加入的server赶上了集群中的其他server之后reconfiguration就会按照上面描述的步骤进行。
第二个问题是集群的leader可能并不包含在new configuration中。在这种情况下leader一旦commit了Cnew log entry之后leader就会step down(返回follower的状态)。这意味着会有这样一段时间当在commit Cnew时leader可能会管理一个并不包含它自己的集群它备份log entry但是并不把它自己考虑在majority的计算中。leader的转换会在Cnew被committed之后发生因为这是第一次new configuration可以独立运行总是可以在Cnew中选出一个leader。在这之前只有Cold中的server能被选为leader。
第三个问题是removed server那些不在Cnew中的server可能会破坏集群。这些server不会收到heartbeats所以它们会timeout并且开始new election。于是它们会用新的term number发送RequestVote RPC这会导致current leader恢复到follower的状态。一个新的leader最终会被选举出来但是removed server还会再次timeout而这个过程会不断重复最终导致可用性非常差。
为了防止这样的情况发生server会无视RequestVote RPC如果它们认为current leader依旧存在的话。特别地如果一个server在election timeout内收到了一个RequestVote RPC它不会更新它的term或者进行投票。这不会影响正常的election在开始election之前每个server都至少等待一个最小的election timeout。然而这避免了removed server带来的破坏如果一个leader能够从它的集群中得到heartbeat那么它就不会受到更大的term number的影响。
7 Clients and log compaction
由于篇幅的原因本章就略过了但是相关的资料在本论文的扩展版中可以获得。其中描述了client如何和Raft进行交互包括client怎么找到cluster leader以及Raft如何支持linearizable semantics。扩展版本中还描述了如何利用snapshotting的方法回收replicated log的空间。这些问题在所有consensus-based system中都会出现Raft的解决方案和它们是类似的。
8 Implementation and evalution
我们已经将Raft作为存储RAMCloud配置信息的replicated state machine实现并且协助RAMCloud coordinator的故障转移。Raft的实现大概包含2000行C代码不包括测试注释以及空白行。源代码可以自由获取。同时还有25个基于本论文的关于Raft的独立第三方开源实现。同时还有各种公司在部署Raft-based systems。本节的剩余部分将从可理解性正确性以及性能三个标准来评估Raft。
....
10 Conclusion
算法的设计通常以正确性效率以及简洁作为主要目标。虽然这些目标都是非常有意义的但是我们认为可理解性同样重要。在开发者将算法实际实现以前这一切都不可能实现而这些实现往往都会偏离或者扩展算法的本意。除非开发者对算法有了深刻的理解并且能够对它建立直觉否则将很难从它们的实现中获得想要的特性。
一个被普遍接收但是难以理解的算法Paxos已经困扰了学生和开发者很多年了而在本篇论文中我们解决了distributed consensus的这个问题。我们开发了一种新的算法Raft就像上面展示的它比Paxos更加易于理解。我们同样相信Raft为实际系统的构建提供了一个更好的基础。以可理解性作为主要目标改变了我们对Raft的设计随着设计的进行我们发现我们在不断重用一些技术例如解构问题以及简化状态空间。这些技术不仅提高了Raft的可理解性同时也更让我们相信它的正确性。
