Paxos算法 -- 学习

原创
2012/07/24 18:11
阅读数 454
     Paxos算法解决的问题是保证分布式系统每次执行的操作强一致性。在其他文档也提到这个算法适合高带宽低延迟网络,如果是低带宽网络可以选择PNUTS模式 。每次执行Paxos算法都是相对独立的,Paxos算法在整个系统运行中迭代前进。 (建议先看了wiki对Paxos解释之后再看本文)

1、作用
     
     
     要使用Paxos算法必须保证所在的 网络可靠,所谓可靠,只数据传输包不会被更改,但是可以丢失。而且允许最多n台Server暂停或者宕机(总Server台数为2n+1),宕机或者休眠的Server要参与Paxos算法(或说选举),必须先学习之前已经通过Paxos算法的操作。(chosen value)

2、实现解析及流程
    
      沿用wiki中文,首先将角色分成三种 proposers,acceptors,和 learners。 Leslie Lamport给出了paxos算法的精确定义:
  •      决议(value)只有在被 proposers 提出后才能批准(未经批准的决议称为“提案(proposal)”);
  •      在一次 Paxos 算法的执行实例中,只批准一个 Value;
  •      learners 只能获得被批准(chosen)的 Value。
      其实,最难懂的还是第二个(感觉 Leslie  Lamport解释得也有点太难理解 ),在wiki中文提到的P1、P2、P2a等其实都是为了保证约束2能过实现。paxos核心实现就是通过大多数(超过一半)的acceptor投票通过决议(value),一旦通过决议,就代表此次决议(这一轮的paxos算法) 结束。之后value会记录到每个server中,以及被learner角色所学习。宕机的服务器,可通过学习之前通过决议的value恢复到与其他server一致的状态

     整个的流程就是:

     客户端C1发起请求 -->  
          S1服务端发起一轮paxos算法 -->  
               生成编号(整个分布式系统中唯一的标识)广播给S2、S3、...  (Perpare(N)) - -> 
     其他服务器检查自己是否有大于N的编号,如果有,则告知S1,S1则重新生成比该编号大的新编号再Prepare(M),M > N,否则返回Promise,   Promise包含最近通过决议的value值和该value对应的编号(可以为null,Promise是其他服务器对S1的承诺,承诺不会表决比N编号还小的决议,并且保存N为服务器接收到的最大编号)  - ->  
     S1接到Promise之后(超过半数Server),发起表决accept(N,value), 如果 Promise里面的value为空,则S1可以使用任意的值写入accept,否则只能从超过半数的Server中取Promise编号最大的value作为值  --> 
     accept() 到其他服务器之后,其他服务器会比较所接收到的accept所含有的编号是否小于当前保存的最大编号,如果是的话,则决绝accept,否则accepted(N, value)通过,将回复给S1 --> 
至此S1就会广播最终的决议,结束  -->
     learner学习决议 
    
     这样一次 paxos 算法完成,其他客户端再请求时,已经是另一轮paxos了。一轮paxos中,可能多个客户端会发起请求,在这个请求竞争中会决胜出一个请求执行,没有拿到执行的请求可以通过递增编号,最终有机会得到执行。
     
3、约束
      Lamport所提到的一些约束都是为了保证每次角逐中能生成一个唯一的value,而且该value的编号在这次paxos中是最大的。如果某次proposer给acceptor的prepare被reject,那么proposer会递增编号n+i (n为服务器的个数)。
P1:一个 acceptor 必须批准它接收到的第一个 value。
     在这里,有个歧义,并不是真的批准value,其实如果,批准了第一个value,那第二个 proposal呢?根据 Paxos算法1-算法形成理论 这篇文章,其实是promise,而不是accept。
P2:一旦一个 value 被批准(chosen),那么之后批准(chosen)的 value 必须和这个 value 一样。
     因为一次角逐中,可能存在多个大于半数的集合(Ua、Ub...)在决议,因为都大于半数,Ua 与 Ub 交集不为空,一旦其中一个集合的决议批准,那么另一个也要跟着表决为该value。
     
P2a:一旦一个 value v 被批准(chosen),那么之后任何 acceptor 再通过(accept)的 value 必须是 v。
P2b:一旦一个 value v 被批准(chosen),那么以后 proposer 提出的新提案必须具有 value v。
P2c:如果一个编号为 n 的提案具有 value v,那么存在一个多数派,要么他们中没有人通过(accept)过编号小于 n 
的任何提案,要么他们进行的最近一次批准(chosen)具有 value v。
     P2a、P2b、P2c都是为了保证P2, 其实 联想整个流程,P2c -> P2b -> P2a -> P2 是有理可寻的,如果proposer提案的动作被限制只能是value v,那么P2a里面acceptor也就只能收到value v了。
     请记住Paxos是迭代进行的,value决议之后,就是该次Paxos算法结束。
     这样C1、C2、C3先后提出R1(请求)、R2、R3,在每一次Paxos算法的角逐之中,会按一定的顺序保存到每个服务器中。但是不一定按着1、2、3来,网络传输的延迟或者丢失是很正常的。
     对Paxos算法的进一步了解可参照:  http://www.doc88.com/p-052298384596.html

     
展开阅读全文
打赏
1
6 收藏
分享
加载中
算法,呵呵.
看不怎么懂,但是要收藏起来以后研究,嘻嘻
2012/07/24 22:26
回复
举报
更多评论
打赏
1 评论
6 收藏
1
分享
返回顶部
顶部