首页 » 漏洞 » 分布式系统入门笔记(二):Paxos算法

分布式系统入门笔记(二):Paxos算法

 

Paxos算法是一种基于消息传递通信模型的分布式系统中,使得各节点就某个值达成一致的问题的算法,其既可以工作在单机的多个进程上面,也可以工作在网络上面的多个主机上面。Paxos协议假定各个节点之间的通信采用异步的方式,且基于非拜占庭模型,也就是允许消息的延迟、丢失或者重复,但是不会出现内容损坏、篡改的情况,在实践中通过添加额外的校验信息很容易保证收到的消息是完整的。

在Paxos算法中主要有以下几种角色:Client、Acceptor、Proposer、Learner。由于本文是直接从 《Paxos Made Simple》 开始学习研究的,其已经是一个被优化过的所谓Multi-Paxos,算是针对原始Basic-Paxos的改进模型了,所以通常还会在多个Proposer和Learnner中选取出Leader,后面涉及的时候再讨论。

a. Client :主要是向分布式系统发送请求,并等待分布式系统的响应,虽然实现的时候也有跟Proposer联系在一起的,但是通常不建议这么做;

b. Acceptor (Voters):被组织成投标团体,对Proposer提出的决议进行表决;

c. Proposer :起到客户代理的作用,请求Acceptor批准客户的请求,同时当发生冲突的时候起着协调者的作用,增加提案号重新请求;

d. Learner :学习已经被Chosen通过的提案,大部分起到replication备份的作用,当客户的请求被批准后,采取相应的行为动作,如果其想要知道某提案是否被通过,也可以主动发起查询;

一、Paxos算法原理

Paxos算法中根据Client的请求,由Proposer发起提案,其中每个提案都有一个全局唯一的数字编号来进行标识,这个编号由外部组件负责生成并且不断地递增,所以在Paxos中每个提案应该是以[编号, Value]的组合形式来表示。

下面的描述中,对于每个节点,假设[n_a, n_value]是已经被accept的提案编号及其值,n_h表示Acceptor已经遇到并处理过的最大提案编号,n_my表示Proposer当前使用的提案编号:

(1). 阶段一:Prepare阶段

分布式系统入门笔记(二):Paxos算法

a. Proposer选择一个提案编号n_my>n_h,然后向某个多数派Acceptor所组成的集合发送请求

,要求该集合中的Acceptor作出回应;

b. 当Acceptor收到 这个消息后,如果发现n_my ,否则n_h=n,同时返回已经被accept的值

,同时该Proposer不会再响应小于n_h(n)的提案了;

(2). 阶段二:Accept阶段

分布式系统入门笔记(二):Paxos算法

a. 如果Proposer没有接收到绝大多数的

回应,则延时后重试,采用更大的提案编号;否则

b. 如果Proposer接收到大部分Acceptor的 回应,那么查看前面 的返回消息,如果之前所有回复的Acceptor都还没有accept任何值(当V=null时),Proposer可以自己选择任何的V值(当然不会乱选啦,就是原先提案值),否则V设置为所有 中最大n_a对应的n_value,然后返回 c. 当被发送的Acceptor节点接受到 ,否则更新n_a=n, n_value=V, n_h=n,同时返回

(3). 阶段三:Decide阶段 (Learner获取提案)

分布式系统入门笔记(二):Paxos算法

a. 如果Learner从绝大多数Acceptor节点获得 ,则发送

给所有Learner学习;否则

b. 如果Learner没能获得绝大多数Acceptor的

,则放弃;

Learner获取一个已经被Chosen选定提案的前提,是这个提案被大多数的Acceptor通过发送 所批准。最简单的方式是所有的Acceptor将所有的

回复消息发送给所有的Learner,那么通信的数量将会是Acceptor和Leaner数量相乘;优化方法之一是选取一个主Learner,主Leaner得知提案被通过后,再将结果送达给其他Learner,但是这样会引入单点故障的问题;还可以选择一个小范围的Learner集合,这里面的Learner直接接收Acceptor的Chosen消息,然后将结果转达给其他的Learner。当然这里也是假定非拜占庭模型,Learner传播给其他Learner的Chosen Value是可信完整的。

实现上为了可能崩溃或者失效后处理,所有Acceptor在发送响应前必须持久化存储该响应,每一次Paxos结算至少要记录propose、promise、

accept、acknowledgment、commit五类消息,而且为了可靠性必须刷新到磁盘上面。

二、Multi-Paxos

虽然最初Lamport爷爷幽默感的Basic-Paxos没有拜读过,但是从网上资料以及 《Paxos Made Simple》 的Multi-Paxos也得知之前Basic-Paxos的一些问题。其实 《Paxos Made Simple》 中的各种优化,算是已经为工程实现提供了较多的预备和考量了。

Basic-Paxos中所有的Proposer都可以发布提案,用后面的话来说就是所有的Proposer都认为自己是Leader,那么可能出现的问题就是产生活锁——当多个Proposer的提案被否决后,都增加自己的提案编号再次尝试,最终导致的结果就是循环下去而没有任何的提案被Chosen。而Multi-Paxos的解决方式是在稳定的状态下,只有一个唯一的Proposer Leader,因为只有这个Leader能够发起Prepare增加提案值,所以正常情况下他的提案总能够被接受和选择,Phase-I的Prepare阶段就可以被省略优化了(同时也省略了prepare、promise日志写盘操作),后续新的instance只需要直接增加提案号发送Accept请求给大多数Acceptor去表决就可以了。

实现中可以把Proposer、Acceptor、Learner看成整体的Server端,而且文章中也是将他们和StateMachine融合在一个进程中去,Client向Server端发送请求以组成C/S模型架构。因为单Server端是不可靠的,所以通常会部署多个Server端,只要给这些Server端以相同的序列输入,那么根据决定状态机他们的输出肯定是相同的,所以Client可以使用任意一个Server的输出作为结果,而这里需要保证的,就是这多个Server执行输入状态机命令的顺序是相同的。

上面的道理还比较的抽象,可以使用PhxPaxos的一张图来表明:

分布式系统入门笔记(二):Paxos算法

为了保证所有的机器(以Node来称呼)都以相同的顺序执行状态机命令,多个Node定义为网络进程,可以在一台物理主机上也可以分布在多台机器上,以IP:Port标识,我们定义顺序连续编号的Instance代表一个状态机命令(同时也就是对应一个Client请求)以用来确定一个Value,每个Instance都由单个Proposer、Accetpor、Learner和StateMachine组成,当我们假定Node的组成是固定的,那么所有Node上面相同编号的Instance的角色将组合成一个集合被Paxos算法使用。每个编号的Instance负责确定相应编号的值,顺利的情况下可能一次提案就能通过,也可能被否决后增加提案号多次提案才被接收选定。

上图上面的Paxos group是按照业务逻辑进行划分的,跟实现原理没有关系,当我们关注每一个单独的Paxos group,里面都是一个完整的Multi-Paxos的实例。对于Node A/B/C通常会产生一个Leader Proposer负责代理Client的请求提出议案,然后Node A/B/C的所有Acceptor组成Quorums负责投票表决,最后Learner整理表决的结果得到Chosen Value。

上面单独编号的Instance之间是完全隔离的,他们单独执行互不干涉,也正是因为如此,Multi-Paxos使得多个Instance并行执行成为了可能。实际上在Lamport爷爷文章中也提到了,Leader可以预取r个命令——也就是说,在命令1到i被选择Chosen之后,它就可以同步提出命令i+1,…, i+r,这些命令有些可能会执行失败,在命令序列中留下一些间隔(gap),当然这些错误怎么处理没有说明,但是服务器需要尽快填充这些间隔才能执行后面的命令,可以使用不改变状态机状态的”no-op”命令占用这些间隔,然后继续执行。

PS:上面这个问题,刚才跟PhyPaxos的作者沟通过,至少在他们PhxPaxos里面,Chosen Value可以是并行的,但是状态机转移是完全序列化的,也就是当出现gap的时候状态机无法转移,所以才需要填充no-op指令让状态机跳过这些Instance Number。按照我的理解,Chosen Value可以在预取窗口中并行执行,而且Value以任意顺序被Chosen出来,但是commit使得状态机转移必须是严格串行化的。查看Paxos Made Live中,状态转移就是过各个Node执行callback函数,而这个过程是被严格序列化的,并且通常真正的业务变更和执行操作也是体现在callback中的。

在此,还不得不说一下 《Zab vs. Paxos》 这篇文章提到的Paxos和Zab的差异:Zab致力于primary-backup而Paxos致力于state machine replication,前者即使在失败切换Leader的同时还是会保证所有的事件顺序提交的,但是Paxos在切换Leader后对未提交的命令执行顺序是不一定的,当然可以严格Paxos序列化操作,每次提交一个命令后再Propose新的命令,当然性能会有很大影响。

参考

原文链接:分布式系统入门笔记(二):Paxos算法,转载请注明来源!

0