A-A+

Raft论文解读

2016年10月04日 分布式系统 暂无评论 阅读 881 次
摘要:

Raft论文解读,本文根据Raft会议论文,参考Raft博士论文,解读了部分内容。Raft跟(Multi)Paxos差别较大,相比Paxos加强了很多约束,尤其是strong leader,直接影响了Raft协议的架构。

Raft论文解读

 

摘要

Raft是针对复制日志的一致性协议。效果上,Raft等价于multi-paxos协议;效率上和Paxos一样。但是Raft协议的整体结构与Paxos差别比较大,Raft协议更加容易理解,也更加适合工程实现。Raft为了使协议更加容易理解,将一致性协议拆分为独立的几个要素:选主、日志复制、safety。相比Paxos,Raft通过加强对状态一致性的约束来减少需要考虑的状态数目。实际课堂授课测验显示,对学生来说,Raft比Paxos更加容易理解。Raft也提出了一种新的成员变更方案,通过重叠多数派的方法来保证safety。

1. Introduction

一致性协议是通过将一组机器协同工作,来对抗其中部分机器宕机。因此,一致性协议在构建高可靠的大规模分布式系统中,发挥了关键的作用。Paxos在过去十年统治了分布式系统一致性协议,各种实现要么是Paxos的变体,要么深受Paxos影响。课堂上也通过Paxos讲授一致性协议。然而Paxos难以理解,另外,Paxos距离实用还要做很复杂的修改。因此,作者实现了Raft。Raft的一个重要的目标就是understandability。
为了提高understandability,Raft解耦了选主、日志复制、safety,另外Raft减小了状态空间(相比Paxos,Raft减小了不确定性的程度,减少了机器之间的不一致性的程度)。

Raft的一些特色:

  • Strong leader:Raft约束日志只能从leader流向follower。
  • Leader election:Raft使用随机化的定时器来选主。
  • Membership change:Raft使用joint consensus方案来做成员变更。

 

2. Replicated State Machine

一致性协议通常在复制状态机Replicated State Machine的场景下出现。在复制状态机中,状态机复制在多台机器之上来对抗部分机器的宕机。Chubby、Zookeeper就是使用复制状态机的典型例子。
复制状态机的结构如图。

 

state_machine

每台机器都存储了一系列的日志,每条日志都是一条command。已确认的日志会被状态机顺序执行。一致性协议模块会保证每台机器上的已确认的日志是一样的,因此内存中的状态机也是一致的,输出也是一致的。一致性协议模块从客户端接收到一条命令,并添加到日志中,然后和其他机器的一致性模块通信,来保证日志最终都是一样的。一旦一条日志被确认了,那么,少数派的机器宕机并不会影响对外服务。整个系统看起来就像是一个高可用的状态机。

一致性协议有如下的特点:

  • 保证safety:不管网络延迟或者分区,网络包丢失、重复或者乱序,都要保证一致性。
  • 可用性:只要多数派机器在线,就应该能提供服务。
  • 不依赖时钟来保证正确性:时钟出错或者网络消息延迟过大只是会导致可用性,并不会导致一致性错误。
  • 通常,一次网路来回的事件就可以对一个command确认。

 

3. What’s wrong with Paxos?

Paxos第一个问题:不易理解。

Paxos第二个问题:Paxos距离构建一个实用的分布式系统还差很多,原始论文更多强调Basic Paxos,对Multi Paxos涉及不多,只是讲述了原理,并没有形成一个完整的算法。

Paxos第三个问题:Paxos协议的架构太差。主要强调了Basic Paxos协议的正确性,且对选主是弱依赖。

Raft作者反复提及Paxos不好理解,给出的理由如很多论文继续解释Paxos或者课堂授课实验等,其实都不太充分。Lamport在原始论文中虚构了一个海岛上的议会制度,除了单词陌生之外,其实大部分内容都是比较清晰的。实际只要多看下Basic Paxos证明过程应该就能理解了,Multi-Paxos是基于在Accept阶段才明确需要什么内容进行投票。

至于Paxos不能开箱即用、选主依赖问题等,这并不是Paxos论文的侧重点。

不管怎么说,Raft确实比Paxos简单了。

 

4. Designing for understandability

Raft的几个目标:对于系统实现来说,协议要完整实用;协议安全性有保证;通常场景下效率高;易理解。

Raft解决”难理解”这个问题上,采用了两个思路:

其一,问题分解,将复杂问题分解成几个简单的问题;

其二,简化状态空间,更强的一致性,减少不确定性。

 

5. The Raft consensus algorithm

Raft首先选主,然后leader全权负责同步日志。有了leader极大地简化了日志复制:leader可以单方面决定日志写在什么位置上;日志流只能是从leader到follower。

Raft保证了如下的safety:

Election Safety:在一个给定的term内,最多一个leader被选出来。

Leader Append-Only:leader从来不覆写或者删除日志,只会追加新日志。

Log Matching:如果两个主机的副本上的日志文件中,包含一条相同term和log id的entry,那么,这两个日志文件在这条日志之前的内容都是相同的(字节流级别的一致)。

Leader Completeness:如果一条日志已经commit了,那么这条日志一定会出现在term最大的leader的日志文件中。

State Machine Safety:如果一个主机应用了一条日志,那么,其他主机不可能应用一条相同log id而内容却不同的日志。

 

5.1 Raft Basic

Raft中的server只有三种状态:Leader / Follower / Candidate。通常情况下(无主备切换时),一个leader其他是follower。Follower处于被动的状态,它不能发起任何请求,只能回应leader和candidate的请求。Leader处理客户端的请求,如果客户端请求发到了follower,follower负责将请求重定向到leader。Candidate是选主过程中用于选出新主。状态转移图如下:

state

Raft将时间划分为term。Term可以是任意长度的时间段。Term有一个连续递增的id。每个term以选主开始,选主过程中,若干candidate尝试成为leader。选主过程成功之后进度normal operation的阶段,leader开始服务。选主可能因为选票分裂而失败,此时当前term没有leader,在下一个term继续选主。

election

Term是需要持久化保存的。因为是分布式环境,所以不同的机器维护的term可能不一样,term是一个逻辑时钟(参见分布式系统下的时间 时钟 事件序 论文解读),因此,当一台机器在与其他机器通信时发现自己的term比较小,应该推进本地的term。如果一台机器发现请求方的term比较小,则要拒绝请求。如果一个candidate发现自己的term落后了,就要退回到follower。

机器之间使用RPC通信,Raft中只有两种RPC:RequstVote和AppendEntries。RequstVote RPC用于candidate在选主期间拉票。AppendEntries RPC用于leader复制日志到follower,同时也作为主备之间的心跳RPC。RPC请求收不到任何结果时,要定时重试。为了优化性能,RPC可以并发发起。

5.2 Leader Election

Raft使用了心跳机制来触发选主。Server刚启动时,状态处于follower,只要follewer一直收到leader或者candidate发来的rpc,就保持为follower。Leader周期性地向follower发送心跳(用的是AppendEntries RPC,里面不带日志内容)来保持leader的权限。如果一个follower在election timeout时间内没有收到leader的心跳,follower就认为没有leader了,就会开始选主。

开始选主时,follower先递增本地term(要持久化),然后主机状态切换为candidate。然后主机向其他发送拉票请求,同时也给自己投票。Candidate在这个状态等待,直到如下三种情况发生:

  • a) 该candidate赢得了选主
  • b) 其他机器成为了leader
  • c) 超时间内未能选主成功

一个candidate赢得选主的判定:在相同的term内,收到了多数派的投票。在给定的term内,每台机器都只能按照先来先服务的规则投一个candidate(要持久化)。收到多数派才可能成为leader,可以避免出现双主。选主成功之后,新主向其他主机发送心跳AppendEntries RPC,宣告自己当选了。

在选主时间内, candidate如果收到了其他主机宣告当选的心跳AppendEntries RPC且RPC中携带的term比本机维护的term更大或相等,本机就自动退为follower。

超时时间未能内选主成功,可能是发生了选票分裂。同时有若干参与者拉票,选票分流,没有candidate能够拉倒多数派的选票。选主失败时,所有candidate递增term开始下一轮。为了减少选票分裂出现的概率,选举超时时间使用随机化的方法避开多个candidate同时拉票。

Raft的选主方案的进化。一开始Raft使用的是ranking system,每个candidate都分配一个唯一的rank,低rank的主机收到高rank的主机的拉票请求,就把自己转为follower,这样rank高的就能尽快被选出来(可能在下一轮选主中)。这个方案有些微妙的可用性问题:如果高rank的主机宕机了,低rank的主机还要等超时才有机会转为candidate。这个方案调整了几次,每次调整都引入新的corner case。最后才选择了这个随机化方案。
Raft的选主方案还要加上一些约束,以支持log replication实现。

5.3 Log replication

Leader被选出来之后,就开始服务客户端的请求。Leader收到客户端请求之后,将命令记入日志并同步到follower。当这条日志被确认之后,就把日志对应的命令应用到状态机。如果某个follower没有收到AppendEntries RPC,leader会不停地重试,确保follower最终有全部的日志。

日志组织方式如图,

log_org

每条日志都记录了term值,这个值是提交这条日志的leader当时的term值。这个term值可以用以检测不一致性。

当leader将日志复制到多数派的时候,这条日志就commit了。Raft保证任何commit的日志最终都会被副本的状态机执行。

Raft约束日志是连续commit的,leader维护最大已经commit的日志id,并将这个信息附加到AppendEntries告知follower,follower了解到之后即可将本机已有的且已经commit的日志应用到本地的状态机。

Raft维护了更高级别的不同主机之间的日志的一致性,简化了系统的行为、使得系统行为更加可预测、更容易保证safety。

Raft保证了如下的约束(Log Matching Safety):

  • 不同主机上日志文件中,相同term和相同log id的日志内容一定相同。
  • 这条相同的日志之前的日志文件内容也一定相同。

实现这两点也很简单。第一点,只要保证leader给每一条log id只分配一条日志即可。第二点,由AppendEntries RPC保证,AppendEntries RPC在消息中携带term和前一条log id。如果follower发现自己本地的日志并不匹配这个AppendEntries RPC中的log id时,会拒绝这条日志。因此按照归纳法,就可以证明只要某条日志被接收了,那么前面的日志都被接收了,前面的日志文件内容都是一致的。

正常运行时,主备之间通常都是一致的,AppendEntries RPC也一直成功。但是如果有leader宕机了,就会有不一致。例如如图。

diff

主备不一致可能有如下几种情况:少了一些日志(term可能相同或者少了);多了一些未commit的日志(term可能多了也可能少了);某些term多了一些日志且某些term少了一些日志。

Raft中如何解决这些不一致呢?leader强制让follower的日志文件复制leader的日志文件,即follower上不一致的日志文件内容被覆写。新主上任之后,在和某个follower同步日志时,先确定和这个follower最后一条相同的日志,然后用leader上的内容覆盖之后不相同的部分。当然,为了避免已经commit的日志被覆盖,选主时需要特别注意,后面会讨论这个问题。

Leader确定与follower不一致点的方法:leader维护一个log id,初始为leader本地最大的log id,然后发送AppendEntries RPC到follower,follower在收到AppendEntries之后,检查RPC中携带的term和log id(leader上被追加的这条日志的前面一条日志的term和log id),如果follower本地没有这条日志,就拒绝此次AppendEntries RPC,leader就能知道follower的同步点更靠前,逐渐就能知道同步点的位置。当然,实际实现时,会使用更有效率的方法。

通过这种方法,leader上任后,并不需要做特殊的操作,只用AppendEntries就可以逐渐使follower上的日志文件保持一致。Leader从不覆写自己的日志文件,即Leader Append-Only Property。

5.4 Safety

5.4.1 Election restriction

这节描述如何保证日志流只从leader流向follower。

如果不对选主加约束,那么,可能一个落后的follower被选为主,落后的那些日志可能已经commit了,要保证log matching property,就必然要有从旧主或者其他不落后的follower上拉取这些已经commit的日志。

Raft使用的方案是:确保包含所有commit日志的candidate才能有机会被选为leader。因为一条日志commit,必然在任意一个多数派中,至少有一台主机包含了这条日志。选举时,candidate要和至少多数派的主机通信,通信时带上自己本地的日志信息(本地最后一条的term和log id),接收消息的主机发现发送消息的candidate的日志并不比我本地更新,就拒绝投票。也就是说,candidate至少是某个多数派中拥有最新日志的主机,才能被选为leader。

5.4.2 Commit entries from previous terms

考虑如下的场景:
prev_term

假设宕机和恢复比较频繁,就可能出现上图的场景(具体过程见原文此图的注解)。在(c)时,S1在将log id=2的日志同步到S3之后,就会发现log id=2的日志已经在多数派上复制成功了。假设这时Raft将log id=2的日志应用到了本地状态机。在(d)中,log id=2(term=3)的日志也被复制到多数派了,且已经覆盖了所有的term=2的log id=2的日志。因此已经应用到状态机上的term=2,log id=2的日志就丢失了。

相比起如何解决这个问题,思考这个问题是如何引入的更加有意思。S1上的term=2,log id=2的日志,在进行复制时,使用的term仍然是term=2,而不是S1最新的term。在本地term较大的时候去复制term小的日志,这个是不合理的。但是为了维持Leader Append-Only的性质,只能想办法解决。

虽然问题复杂,但是解决方却案很简单:leader只能对本term的日志通过counting replica的方式确定commit与否,对与之前的term,则通过确定本term日志commit和Log Matching Property来间接确定commit。

没有持久化的信息来记录当前最大commit id,给宕机重启带来了一些问题。集群宕机重启之后,主备应该如何设置最大commit id?只能是先设置到最近一次checkpoint之后的第一条log id。然后等有最新term的日志被commit了,才能将最大commit id推进到最新log id,apply id也一样,此时才能开始不断递增apply id逐条日志开始应用到状态机。

5.4.3 Safety argument

这节主要证明Leader Completeness Property。证明要点:选主时要获得多数派的支持,一条已经确认的日志被多数派保存下来,两个多数派一定有交集。
证明过程略。

5.5 Follower and candidate crash

Raft处理follower和candidate失败的方式是一致的:AppendEntries和RequestVote RPC重,Raft的RPC都是幂等的。

5.6 Timing and availability

Raft协议的正确性本身不依赖时钟同步、事件耗时长短,但是可用性受影响比较大。

 

6. Cluster Membership changes

之前的讨论都是假设成员组是不变的。这一节描述Raft的成员变更方案。

要保证成员变更过程中的safety,就要保证在任何时候,都不会出现双主。

如果一次成员变更中,将成员组立刻切换为新的成员组,那么就会因为各个成员之间不能同时生效而导致双主,如图。

disjoint-majorities

从(S1,S2,S3)变为(S1,S2,S3,S4,S5)的变更中,因为各个成员上变更生效时间不同,可能导致在中间某个时刻,出现两个disjoint majorities,两个多数派能够分别选主并服务客户端,导致一致性无法保证。

为了保证safety,常规的解法是使用两个阶段。例如,在Viewstamped Replication协议里,成员变更先停止旧的成员组,然后启用新的成员组,但是这样导致中间会有停服务的问题。

Raft里采用的两阶段方案是,集群先进入一个称之为Joint Consensus的过渡状态,等过渡状态commit了,再只使用新的成员组。在Joint Consensus中,不管是日志复制(客户端提交的普通日志)还是选主,都要在新旧两个成员组C_old、C_new内分别形成多数派。

成员变更命令通过成员变更日志作为载体复制到其他副本。一个副本只要收到了成员变更日志,之后的日志就立刻使用新的成员组开始工作,不管这条成员变更是不是commit了。也就是说,leader要用两个多数派C_old,new同时满足来commit这条成员变更日志。

因为有Joint Consensus,所以在C_old,new commit之前,C_new无法单方面确认任何事情。那么,在C_old,new commit之前如果leader宕机了呢?这种情况下,C_old或者C_old,new可能选出新的leader(取决于新主上是否有C_old,new这条日志)。同样,C_new仍然无法单方面确认任何事情。

一旦C_old,new commit了,那么即使leader宕机,选出来的新leader也一定有C_old,new这条日志了(选主的约束:Leader拥有全部commit的日志)。此时,leader发起一个成员变更,将状态转为只使用C_new的状态(这条日志也记为C_new)。直到C_new被commit了,C_old便不再被需要。成员变更的两个阶段就完成了。
这个过程如图示:

joint_consensus

成员变更保证safety,要遵循的原则是:在任何时候都不允许C_old和C_new同时可以单方面做决定。例如图中上半部分,C_old和C_new分别可以单方面做决定的时间段是没有重叠的,中间使用C_old,new过渡。

成员变更还有三个延伸的问题:

问题1:新加入的主机上可能没有任何日志,在实际执行成员变更前,我们希望这台主机先作为观察者基本追上leader的日志,再做成员变更。否则加入的这台空机器在追上之前,几乎起不到高可用的目的。

问题2:如果leader并不是C_new的一员,那么leader要卸任。因为C_new的commit是这个leader主导的,因此在C_new commit之后,leader要卸任。

问题3:如果是机器下线的变更,被下线的机器因为不会再收到C_new中的leader的心跳而超时触发选主了。C_new中的leader因为term比下线机器的term小,因此会卸任,又因为C_new中的副本拥有最多的日志,选主约束仍会从C_new中选出一个leader。同样,下线的机器会再次超时,又触发选主,周而复始,虽然不会有safety问题,但是可用性却因为leader反复卸任再上任而降低。Raft的方法也很简单:如果一台主机认为还有leader,那么就不会给其他人投票。这是一个非常有效的补丁(是补丁),这个补丁完美躲避了对选举核心机制的修改,我真是不知道说什么好了。

Raft在Joint Consensus之后,引入了一阶段成员变更:在一次只变更一个成员组的情况下,成员变更可以直接从C_old变为C_new,接收到C_new的成员立刻使用新的成员组。

因为每次只变更一个成员,所以新旧多数派必有交集(可以按照奇偶加减成员四种情况穷举推算)。 那么,即使没有过渡阶段,也不会出现新旧成员组同时能够单方面做决定的情况。
在Raft博士论文中有论述,读者可以参考。

7. Client and log compaction

讲的是API,state machine checkpoint,本节略。

8. Implementation and evaluation

略。

 

 

给我留言