|   登录   |   注册   |   设为首页   |   加入收藏   

用户登录

close

用户名:

密码:

新用户注册

close

用户名:

密码:

密码确认:

电子邮箱:

关注内容:

个人主页:

帮助

close

龙宇网成立于2008年3月,网站进入整体运作于2010年10月1日。

在这里,我们把它做成了一个真正意义上的网站,完全以个人的信息为内容,以网友的需要为主导,全力搜罗各种信息,建立完善的网站功能,使网友在这里可以第一时间找到所需要的信息。

现在,经过三年的努力,网站的资料已经相当丰富,而网站得到了大家的喜爱和认可。

但,我们还是会继续努力下去,让网间的这份快乐继续持续下去,让这份闲暇时的日子,与快乐一并同行。

寻觅快乐,网住快乐,关注网络,是龙宇网的宣言与承诺。

Paxos算法

分类: 机器学习 发布时间: 2016-12-01 17:25:34 浏览次数: 2185
内容提要: Hadoop是一个由Apache基金会所开发的分布式系统基础架构。Zookeeper是Hadoop的一个子项目,是一个开源的分布式服务, 它提供了分布式协作、分布式同步、配置管理等功能。Zookeeper最重要的就是解决分布式系统中”部分失败”的问题, Zookeeper不能避免”部分失败”的问题,而是在出现“部分失败”的情况下,可以让分布式系统正常的运行。而Zookeeper是如何做到呢?

引言

Hadoop是一个由Apache基金会所开发的分布式系统基础架构。Zookeeper是Hadoop的一个子项目,是一个开源的分布式服务, 它提供了分布式协作、分布式同步、配置管理等功能。Zookeeper最重要的就是解决分布式系统中”部分失败”的问题, Zookeeper不能避免”部分失败”的问题,而是在出现“部分失败”的情况下,可以让分布式系统正常的运行。而Zookeeper是如何做到呢?

Paxos算法历史

“拜占廷帝国有许多支军队,军队的将军们必须制定一个统一的行动计划—进攻或者后退。将军们是地理上分隔开来的,只能靠通讯员进行通讯。并且将军中存在叛徒。叛徒可以任意篡改消息,欺骗某些将军进攻或者后退。”

 

这个是著名的拜占廷问题

 

“在古希腊有一个Paxos小岛,岛上以议会的形式通过法令。议会中的议员通过信使传递消息,议员和信使都是兼职的,随时可能离开议会厅,并且信使可能重复投递消息,也可能一去不复返。议会协议要保证在这种情况下法令仍然能够正确的产生,并且不会出现冲突”

 

这个是paxos的由来,Paxos算法解决通信不可靠的分布式系统中的一致性问题。通信不可靠包括:消息会延迟、重复投递甚至丢失,但是消息不会被篡改(没有拜占庭问题)。

 

在随后的几年,Lamport陆续发表了《Consensus on Transaction Commit》、《Cheap Paxos》、《Fast Paxos》等一系列论文,阐述了Paxos算法的各种演化、优化、简化和变种。

在Zookeeper中完全实现了Paxos算法。

 

Paxos算法原理

 

Paxos算法角色

Paxos算法中的参与者主要分为三个角色,同时每个参与者又可兼多个角色:

  • Proposer:提出提案, 提案信息包括提案编号和提议的value
  • Acceptor:收到提案后可以接受提案
  • Learner:只能“学习”被批准的提案

Paxos算法约束

Paxos算法保持一致性的基本语义:

  • 决议(value)只有在被Proposer提出后才能被批准(未经批准的决议称为“提案(proposal)”);
  • 在一个Paxos算法的执行过程中,只批准(chosen)一个value;
  • Learners只能获得被批准(chosen)的value;

 

在上面的三个语义可演化为四个约束:

  • 一个Acceptor必须接受(accept)第一个收到的提案;
  • 一旦一个具有value 的提案被批准(chosen), 那么之后任何Acceptor再次接受的提案必须具有value
  • 一旦一个具有value的提案被批准(chosen), 那么之后任何Proposer提出的提案必须具有value
  • 如果一个编号为n的提案具有value, 那么存在一个多数派,要么他们中所有人都没有接受编号小于n的任何提案, 要么他们接受的所有编号小于n的提案中编号最大的那个提案具有value

 

Paxos算法实现

在上述约束条件基础上,一个决议的通过可以分为两个阶段:

  • Prepare阶段(准备)
  1. Proposer创建一个编号N的决议, N必须大于之前创建的决议编号,并发送Prepare消息给所有Acceptor
  2. 当Acceptor接收到Prepare请求时,检查自身上次回复过的Prepare请求编号:
    1. 如果上次回复的编号大于这次的编号,则忽略这次请求,直接结束本次批准过程。
    2. 否则检查上次批准的accept请求,并回复上次批准的编号和决议(N,value);如果之前没有进行过批准,则简单回复OK, 并承诺不再回复小于N的提案。
  • Accept阶段(批准)
    1. Proposer收到Acceptor的prepare回复,回复分为几种情况:
      1. 回复数量满足多数,并且所有回复都是OK,则Proposer发出accept请求,请求内容为提案(N,value)
      2. 回复数量满足多数,但回复内容不一致,则Proposer找到回复中超过半数的那个,并发出accept请求,请求内容为(Xn,Xvalue)
      3. 回复数量不满足多数,Proposer则随机选择一个进行accept请求
    2. Proposer收到Acceptor的accept请求回复(accepted),回复分为几种情况:
      1. 回复数满足多数,则确认被接受。同时,Acceptor会发送accepted到Learner。
        • 回复确认的时候需要满足上述提到的约束,否则Acceptor直接忽略请求。
    3. 回复不满足多数,Proposer需要重新创建N+1的决议,继续请求。

在上述Acceptor接收请求中,如果Acceptor接收多个Proposer请求的时候,则直接拒绝编号小的请求,并通知Proposer结束请求。

 

通过下面图,来看一下Paxos算法的消息流:

Vn=last of(Va, Vb, Vc)

 

在上述的Paxos算法中,如果有三个或者三个以上的Proposer在发送prepare请求后,很难有一个Proposer收到半数以上的回复而不断执行prepare请求,导致出现竞争。为了避免这种情况的出现,在Paxos算法中引入了Leader角色,在正常情况下,最多只有一个参与者扮演Leader角色,而其他参与者扮演Acceptor角色,同时所有人又都是Learner。此种优化算法被称为Fast Paxos。

在Fast Paxos中只有Leader可以提出议案, 一个Leader的工作流程主要分为三个阶段:

  • 学习阶段         向其他参与者学习自己不知道的决议
  • 同步阶段         让绝大多数参与者保持决议的一致性
  • 服务阶段         为客户端服务,提提案

 

通过上述Leader角色的加入,避免在Base Paxos中出现的竞争。下面是Fast Paxos的消息流:

 

Zookeeper中Paxos算法

FastLeaderElection选举算法是标准的Fast Paxos实现,它首先向所有server提议自己要成为Leader,当其他server收到提议后,会发送接收提议的完成消息。

FastLeaderElection算法通过异步的通讯方式来收集其他节点的选票,同时分析选票时又根据投票者的当前状态来做不同的处理,以加快Leader的选举过程。

 

下面是选举过程的流程图:

        

         

 

Follower节点处理读写请求

 

 

Leader节点处理读写请求

 

通过上述选举算法,Zookeeper实现了Master的选举,在分布式系统中,出现“部分失败”的情况下,仍能保证系统的正常运行。

 

Paxos算法应用

  1. DataBase Replication,log Replication等,如DB的数据复制就是使用Paxos的兼容算法,Paxos保持多个节点数据的一致性。
  2. naming service, 在大型系统内部通常存在多个接口服务相互调用
    1. 通常实现是将服务的IP/hostname写死在配置中,当server发生故障是,通过手工更改配置文件或者修改DNS指向的方法来解决。缺点是可维护性差,内部的单元越多,故障率越大。
    2. LVS双机冗余的方式,缺点是所有单元需要双倍的资源投入。

通过Paxos算法来管理所有的naming服务,则可保证high available分配可用的service给client。

  1. config配置管理
    1. 通常手工修改配置文件的方法,这样容易出错,也需要人工干预才能生效,所以节点的状态无法同时达到一致。
    2. 大规模的应用都会实现自己的配置服务,比如用http web服务来实现配置中心化。它的缺点是更新后所有client无法立即得知,各节点加载的顺序无法保证,造成系统中的配置不是同一状态。
  2. membership用户角色/access control list, 比如在权限设置中,用户一旦设置某项权限比如由管理员变成普通身份,这时应在所有的服务器上所有远程CDN立即生效,否则就会导致不能接受的后果。
  3. 号码分配。通常简单的解决方法是用数据库自增ID, 这导致数据库切分困难,或程序生成GUID, 这通常导致ID过长。更优雅的做法是利用paxos算法在多台replicas之间选择一个作为master, 通过master来分配号码。当master发生故障时,再用paxos选择另外一个master。

 

上述列举了一些常见的Paxos应用场合,对于类似上述的场合,如果用其它解决方案,一方面不能提供自动的高可用性方案,同时也远远没有Paxos实现简单及优雅。

 

参考文献

http://zookeeper.apache.org/

http://hadoop.apache.org/

The Part-Time Parliament

http://delivery.acm.org/10.1145/280000/279229/p133-lamport.pdf?ip=107.178.200.222&id=279229&acc=OPEN&key=

4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E6D218144511F3437&

CFID=468133395&CFTOKEN=92446023&__acm__=1419825159_867935c9e5e2cf6a108c0aec1f20f308

Paxos Made Simple

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

Consensus on Transaction Commit

http://research.microsoft.com/pubs/64636/tr-2003-96.pdf

Cheap Paxos

http://research.microsoft.com/pubs/64634/web-dsn-submission.pdf?q=cheap

Fast Paxos

http://research.microsoft.com/pubs/64624/tr-2005-112.pdf

http://en.wikipedia.org/wiki/Paxos_(computer_science)

22
30

分类: 机器学习   |   评论: 0   |   引用: 0   |   浏览次数: 2185