分布式系统入门笔记(二):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提出的决议Prepare/Accept进行表决;
  c. Proposer:起到客户代理的作用,请求Acceptor批准客户的请求,同时当发生冲突的时候起着协调者的作用,增加提案号重新请求;
  d. Learner:学习已经被Chosen通过的提案,大部分起到replication备份的作用,当客户的请求被批准后,采取相应的行为动作,如果其想要知道某提案是否被通过,比如遗漏了某个命令的决案消息,也可以主动(向Acceptor)发起查询;

一、Paxos算法原理

  Paxos算法中根据Client的请求,由Proposer发起提案,其中每个提案都有一个全局唯一的数字编号来进行标识,这个编号由外部组件负责生成并且不断地递增,所以在Paxos中每个提案应该是以[提案编号, Value]的组合形式来表示。在Multi-Paxos中每个instance之间是完全独立的,所以不要求这些instance提案编号是相互不同的,而且在一些实现中会同时发送[instance_id, 提案编号, value]的,下文仅考虑一个instance中的Basic-Paxos算法的过程。
  下面的描述中,对于每个节点,假设[n_a, n_value]是已经被accept的提案编号及其值,n_h表示Acceptor已经遇到并处理过的最大提案编号,n_my表示Proposer当前使用的提案编号:
  (1). 阶段一:Prepare阶段
Paxos-Prepare
  a. Proposer选择一个提案编号n_my>n_h,然后向某个多数派Acceptor所组成的集合发送请求,要求该集合中的Acceptor作出回应;
  b. 当Acceptor收到这个消息后,如果发现n_my,否则n_h=n,同时返回已经被accept的值,同时该Proposer不会再响应小于n_h(n)的提案了;
  (2). 阶段二:Accept阶段
Paxos-Accept
  a. 如果Proposer没有接收到绝大多数的回应,则延时后重试,采用更大的提案编号;否则
  b. 如果Proposer接收到大部分Acceptor的回应,那么查看前面的返回消息,如果之前所有回复的Acceptor都还没有accept任何值(当V=null时),Proposer可以自己选择任何的V值(当然不会乱选啦,就是原先提案值),否则V设置为所有中最大n_a对应的n_value,然后返回给所有的节点;
  c. 当被发送的Acceptor节点接受到的时候,如果n,否则更新n_a=n, n_value=V, n_h=n,同时返回
  (3). 阶段三:Decide阶段(Learner获取提案)
Paxos-Decide
  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日志写盘操作)。而且,Paxos的算法保证可以在短时间(比如选举Leader)的情况下,允许有多少个Leader同时存在,此时退化到Basic-Paxos算法了,但是算法的正确性不会被破坏。
  实现中可以把Proposer、Acceptor、Learner看成整体的Server端,而且文章中也是将他们和StateMachine融合在一个进程中去,Client向Server端发送请求以组成C/S模型架构。因为单Server端是不可靠的,所以通常会部署多个Server端,只要给这些Server端以相同的序列输入,那么根据决定状态机他们的输出肯定是相同的,所以Client可以使用任意一个Server的输出作为结果,而这里需要保证的,就是这多个Server执行输入状态机命令的顺序是相同的。
  上面的说法还是比较的抽象,可以使用PhxPaxos的一张图来表明:
Paxos-Instance
  为了保证所有的机器(以Node来称呼)都以相同的顺序执行状态机命令,多个Node定义为网络进程,可以在一台物理主机上也可以分布在多台机器上,以IP:Port标识,我们定义顺序连续编号的Instance代表一个状态机命令(同时也就是对应一个Client请求)以用来确定一个Value,每个Instance都由单个Proposer、Accetpor、Learner和StateMachine组成,当我们假定Node的组成是固定的,那么所有Node上面相同编号的Instance的角色将组合成一个集合被Paxos算法所使用。每个编号的Instance负责确定相应编号的值,顺利的情况下可能一次提案就能通过,也有可能被否决后, Proposer增加提案号多次操作才被接收选定。上图的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,这些命令有些可能会执行失败,正常情况下该instance的Proposer会重新提启动预案再次尝试,但是此时如果Leader挂掉之后,就在命令序列中留下一些间隔(gap),新Leader会为这些gap重新执行Phase-I操作以便去获取其Chosen Value。但是后面说到节点使用不改变状态机状态的”no-op”命令占用这些间隔,然后继续执行,那么占用这些命令号原先的指令怎么办呢?丢弃?
  PS:上面这个问题,刚才跟PhyPaxos的作者沟通过,至少在他们PhxPaxos里面,Chosen Value可以是并行的,但是状态机转移是完全序列化的,也就是当出现gap的时候状态机无法转移,所以才需要填充no-op指令让状态机跳过这些Instance Number然后执行下去。按照我的理解,Chosen Value可以在预取窗口中并行执行,而且Value以任意顺序被Chosen出来,但是commit使得状态机转移必须是严格串行化的,查看Paxos Made Live中,状态转移就是过各个Node执行callback函数,而这个过程是被严格序列化的,并且通常真正的业务变更和执行操作也是体现在callback中的。或许上面no-op占用命令就是通过某种机制告知客户端该命令执行失败了吧,猜的别打我!
  前面说到开始打算从PhxPaxos入手了解Paxos机制的,但是后续发现Phxteam还是对Paxos做了一些的更改,因为纯粹的Paxos太过于理论,原版的协议是不可能直接拿来工程应用就达到可用性和可靠性的需求的,往往工程化的过程中会这里改改那里改改的,最终发现已经不是原版协议了,到头来改造成的协议其正确性也难以得到证明了。对于Paxos的实现,可以查阅Marco Primi的硕士论文《Paxos made code - Implementing a high throughput Atomic Broadcast》,这篇论文对Paxos算法进行了通俗的阐述,其合作者Daniele Sciascia将其中的LibPaxos库进行了开源,采用C语言实现并配备sample,虽然距离线上使用可能还有所欠缺,但是整个代码结构思路清晰、通俗易懂,本来想写篇文章说说它的,但是实现的真是太直白了,提笔后发现也没啥好写的了。
  还有,学术级别的论文《Paxos Made Live》虽不够详细,但总结的也是工程实践中的精华,如果作者能开源其实现就棒极了!

三、后言

  在工程上得到验证的分布式协议并不多,2PC在数据库中使用较多,但是现在分布式系统肯定不是2PC、3PC协议所能解决的。Paxos算法的出现就是要异步、去中心化,通过陪审团民主选取的方式来确定一个值。无论是Multi-Paxos极其改进的ZAB、Raft现在是红的发紫(还有个Viewstamped Replication是什么鬼),但归根结底其本质还是Paxos,只是在某些情况下增加了一些限制以便于工程化实现,因为Paxos本身过于的理论,实现起来确实是“reliable implementation proves to be nontrivial”!
  关于ZAB和Raft,自己还了解的不太多。据说他们是限制命令提交是严格序列化的,当某一个命令没有被提交后后续的命令都全部阻塞在内存里面,所以性能和Multi-Paxos相比是他们被诟病的槽点,不过其设计思路后续还是可以了解借鉴的,尤其是Raft作者Diego Ongaro洋洋洒洒两百多页的PhD论文和算法伪代码的表述,大大增加了工程化的便捷性。
  “Paxos只是个协议,用于在分布式环境下确定一个值”,现在念起来意味深长。Paxos的实现也只是在分布式系统中作为基础服务,然后构建上层的分布式存储、分布式数据库、分布式日志等服务还需要跟具体的业务相关联,分布式日志系统好理解,而将数据库的binlong作为分布式对象就可以得到分布式数据库了,当然分布式存储还不知道什么原理,因为目前的论文看来Paxos无法进行大尺寸文件的传输,期待PaxosStore早日开源吧!

参考