Paxos & Raft 算法

28. 三月 2017 分布式 0

在分布式系统中,有很多场景需要对某一个值达成一致。比如:冗余系统的选主(主节点的id就是那个值),分布式日志备份系统(日志中的每条记录就是那个值)等。

Paxos和Raft算法是两种一致性算法(或者说是协议),下面就详细解释一下。

写在前面:这块内容我在网上学习了快两周,感觉零零碎碎还是看论文最直接也最明确。如果有跟我有过同样疑惑的朋友,建议去花时间看看原文,比在网上乱看强多了。

Basic Paxos

Lamport的论文The Part-Time Parliament,简化版Paxos Made Simple

Stanford的一个课件

Paxos算法其实是一个两阶段提交的过程,每个提议只要有超过半数节点通过即最终通过。Paxos中有三种角色:Proposer—提案发起者;Acceptor—提案批准者;Learner—学习提案,这个后面再说。每个节点可以分饰三角,也就是说可以自己投自己。

变量解释:

Proposal number,提案的唯一ID,保证如果两个ID a和b,若a>b,则a比b新且a的优先级高。通常使用timestamp+serverId的形式保证唯一和递增。

minProposal:当前可以接受的最小的ProposalId值。

acceptedProposal:当前已经接受的ProposalId值。

acceptedValue:当前已经接受的提议的值。

 

两阶段具体内容如下:

第一阶段:Proposer选择一个proposal number n,广播Prepare(n)给所有Acceptor。Acceptor收到prepare(n)后,如果n比任何之前收到的proposal number都大,则该提案当前优先级最高,更新minProposal并返回成功;否则返回当前接受的最大proposal number和value。若Proposer收到了拒绝,则用返回值更新自己的提案。

第二阶段:经过第一阶段之后,无论原始提案被接受还是被其他节点更新,都应该是该节点已知的最高优先级的提案。收到大多数节点的反馈之后,向这些节点发送Accept(n, v)。Acceptor收到accept(n)后,如果该提案是当前最大的,则直接接受;否则返回自己已知的最大提案(n, v)。如果proposer收到(n, v),则证明有更新的提案,则重新提交提案。

在前面给出的课件链接中讨论了几种情况可以作为一种简单证明。

另外还有一个角色Learner,因为每个节点并不知道自己的提案是不是被大多数接受了,只有proposer才知道。所以learner的作用就是去”学习“,去验证自己是不是那个被接受的提案。网上很多介绍中都不提这个角色,但是这个角色很重要(下一节说)。

但是Basic Paxos的流程中有个缺点,在高并发情况下,可能出现多个提案交替获得多数支持的情况,被称为”活锁“,会严重降低性能。

Multi-Paxos

Multi-Paxos是Paxos的进化版,通过选主来去掉prepare阶段(因为只有一个leader,所以不需要prepare进行一致性确认)。在一个任期内,只有选出的leader可以进行提案,其他节点只被动接受。

选主是一个Paxos过程,参照Basic-Paxos选出一个主机ID。但是刚才提到了,并发情况下可能出现短暂的多主,虽然多主情况是可以接受的,即退化为Basic-Paxos,但是也可以先确认主节点:主节点一旦被选出,就会立即向所有节点群发StartWorking日志。整个系统中只有一个主节点会被大多数节点接受,失败的主节点自动退化成普通节点。

但是Paxos并不要求日志连续,比如说某节点上有连续的ABCDE五条日志,但是CD两条可能并不是那个”大多数“,可能因为没来得及学习或者网络问题,没更新上(如图)

所以被选出的主节点上可能日志并不是完整的。通常工程上的做法是:每个提案被接受之后,leader另外广播一条信息说某个ProposalId被接受了,然后收到这个信息的节点会默默记下这个节点是最终提案的记录(网称Confirm日志),这样在新主启动之后,就知道自己哪些是确定被接受的,哪些可能不是。新主通过询问其他节点”当前能确认的连续最大的ID是多少“,比如上图中”2“就是能确认的最大ID,然后从2之后的所有未确定的log全部执行一次paxos。

性能优化:log可以分组,不用细说了吧……

关于Multi-Paxos这块有很多种不同的实现方案,不必非要固守某一种方法。

Raft

论文:In Search of an Understandable Consensus Algorithm

UIUC课件

Raft之所以出现就是因为Paxos太复杂、太不容易实现(加上Multi-Paxos只是lamport随口一提,实现各异)。Raft强调主节点至高无上,强调日志连续性。Raft可以给出简单的解释和伪代码,容易工程实现。

Raft算法主要有两个部分:选主和备份。其中也就有两种RPC调用:AppendEntryRPC用来插入一条记录,RequestVoteRPC用于请求其他人选主(选自己)。

Raft中有两个角色,Follower和Leader(中间的Candidate角色暂不当做一个独立角色讨论)。Leader会定期向所有Follower发送心跳包(payload为空的AppendEntryRPC包),当某个Follower隔了某段时间没收到心跳包了,他就认为原Leader已经挂了,开始启动选主,此时Follower变身成为Candidate,向所有节点发送RequestVoteRPC。此时有三种情况:

  1. 收到了大多数支持票——变身Leader
  2. 收到了AppendEntryRPC请求——变回Follower
  3. 超时,未满足前两要求,重新选举。

这个时候如果所有Candidate都参选,都投自己,那么选举就失败了,要进行下一轮。Raft的做法是,在下一轮开始前,每个Candidate都会随机地等待一段时间,先被唤醒的节点先发送RequestVoteRPC,那么就更容易当选。

选主是不是随便选的呢?当然不是的。在最开始我们就说到Raft注重的连续性。注意这个AppendEntryRPC的内容:

  • term表示的是第几个”任期“,每个节点自己都保存了currentTerm,选主时肯定要选比自己term大的。
  • commitIndex表示的是当前已经提交的最大的Index,(每个提案或者每条log都有一个term和一个递增的index),这个东西就像TCP协议中的sequence number一样,在让Follower提交b任务时,一定会把前一个a任务的index带上,从而保证整个任务线是串行的(当然这里也可以让Follower严格按照index递增的顺序提交来实现)。

既然任务是串行的,那选主就容易多了:只选commitIndex最大的节点(我们可以看到在RequestVoteRPC中要把自己的lastLogIndex带上)。这样选出来的主节点一定是当前保存log最多的(此处可以数学归纳法证明,略)。

另外性能上,Raft也可以用batch commit的方式来优化。

 

不管你信不信,我也是个手写过Raft的人,但是那个时候我还不知道这个叫Raft。。。

最后

无论是Raft还是Paxos,都是eventually consensus,所以一般读写(对外提供服务)都是在Leader上的。

 

参考资料:

论文、课件(文中链接)

https://zhuanlan.zhihu.com/p/20417442

https://www.zhihu.com/question/36648084

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据