分布式选举算法Paxos

标签: 分布 选举 算法 | 发表时间:2015-04-25 00:12 | 作者:cfyme
出处:http://www.iteye.com

什么是Paxos算法?

 

Paxos算法是分布式计算领域中一个非常重要的算法,主要解决分布式系统如何就某个值(决议)达成一致的问题。一个典型的场景是分布式数据库的一致问题:如果分布式数据库的各个节点初始状态一致,又能执行相同的操作序列,那么最后能达到一个一致的状态。但是如何保证在每个节点上执行相同的命令序列呢?这就需要在每条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。Paxos算法便是这样一种一致性算法,它由大牛Lamport于1990年提出,在Lamport的论文中,他虚拟了一个叫“Paxos”的城邦并以讲故事的方式阐述算法,因此叫做Paxos算法。

 

1.应用场景

 

(1)分布式中的一致性

Paxos算法主要是解决一致性问题,关于“一致性”,在不同的场景有不同的解释:

NoSQL领域:一致性更强调“能读到新写入的”,就是读写一致性

数据库领域:一致性强调“所有的数据状态一致”,经过一个事务后,如果事务成功,所有的表数据都按照事务中的SQL进行了操作,该修改的修改,该增加的增加,该删除的删除,不能该修改的修改了,该删除的没删掉;如果事务失败,所有的数据还是在初始状态;

状态机:在状态机中的一致性更强调在每个初始状态一致的状态机上执行一串命令后状态都必须相互一致,也就是顺序一致性。Paxos算法中的一致性指的就是这种情况,接下来我们会对这种场景进一步讨论。

(2)MQ

假如所有系统的Log信息都写入一个MQ Server,然后通过MQ把每条Log指令发异步送到多个Log Server写入文件(写入多个Log Server的原因是对Log文件做备份以防数据丢失),则所有Log Server上的数据肯定是一致的(Log内容及顺序完全相同),因为MQ本身就有排序功能,只要进了Q数据也就有了序,相当于编了全局唯一的号,无论把这些数据写入多少个文件,只要按编号,各文件的内容必定是一致的,但一个MQ Server显然是一个单点,如果宕机,会影响整个系统的可用性。

 

(3)多MQ

要解决MQ单点问题,首选方案是采用多个MQ Server,即使用一个MQ Cluster,客户端可以访问任意MQ Server,不同的客户端可能访问不同MQ Server,不同MQ Server上的数据内容、顺序可能不一致,如果不解决这个问题,每个MQ Server写入Log Server的内容就不一致,这显然不是我们期望的结果。

 

(4)NoSQL中的数据更新

一般的NoSQL都会通过数据复制的形式保证其可用性,但客户端对多数据进行操作时,可能会有很多对同一数据的操作发送的某一台或几台Server,有可能执行:Insert、Update A、Update B....Update N,就一次Insert连续多次Update,最终复制Server上也必须执行这一的更新操作,如果因为线程池、网络、Server资源等原因导致各复制Server接收到的更新顺序不一致,这样的复制数据就失去了意义,如果在金融领域甚至会造成严重的后果。

 

上面这些不一致问题性正是Paxos算法要解决的,当然这些问题也不是只有Paxos能解决,在没有Paxos之前这些问题也得到了解决,比如通过使用双Master模式的MQ解决MQ单点问题;通过使用Master Server解决NoSQL的复制问题,但这些解决方法都存在一些缺陷,要么难水平扩展,要么影响可用性。当然除了Paxos算法还有其他一些算法也试图解决这类问题,比如:Viewstamped Replication算法。

 

 

2.Paxos如何解决这类问题

Paxos对这类问题的解决就是试图对各Server上的状态进行全局编号,如果能编号成功,那么所有操作都按照编号顺序执行,一致性就不言而喻。当Cluster中的Server都接收了一些数据,如何进行编号?就是表决,让所有的Server进行表决,看哪个Server上的哪个数据应该排第一,哪个排第二...,只要多数Server同意某个数据该排第几,那就排第几。

很显然,为了给每个数据唯一编号,每次表决只能产生一个数据,否则表决就没有任何意义。Paxos的算法的所有精力都放在如何在一次表决只产生一个数据。再进一步,我们称表决的数全可以得出最终结果。

 

 

 



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [分布 选举 算法] 推荐:

分布式选举算法Paxos

- - 互联网 - ITeye博客
Paxos算法是分布式计算领域中一个非常重要的算法,主要解决分布式系统如何就某个值(决议)达成一致的问题. 一个典型的场景是分布式数据库的一致问题:如果分布式数据库的各个节点初始状态一致,又能执行相同的操作序列,那么最后能达到一个一致的状态. 但是如何保证在每个节点上执行相同的命令序列呢. 这就需要在每条指令上执行一个“一致性算法”以保证每个节点看到的指令一致.

图解zookeeper FastLeader选举算法

- - C++博客-首页原创精华区
zookeeper配置为集群模式时,在启动或异常情况时会选举出一个实例作为Leader. 其默认选举算法为 FastLeaderElection. 不知道zookeeper的可以考虑这样一个问题:某个服务可以配置为多个实例共同构成一个集群对外提供服务. 其每一个实例本地都存有冗余数据,每一个实例都可以直接对外提供读写服务.

分布式搜索算法

- - 杨尚川的个人页面
对于搜索引擎来说,索引存放在成千上万台机器上,如何进行分布式搜索呢. 假设搜索结果是以分页的方式显示,以PageNumber代表当前页,从1开始,以PageSize代表页面大小,默认为10,以N代表搜索服务器数量. 最简单的分布式搜索算法为:有一台 合并服务器负责接受用户的搜索请求,然后分别向N台机器获取前PageNumber*PageSize条结果,得到的结果数为N*PageNumber*PageSize,然后把这些数据重新进行排序,根据所要显示的页面PageNumber,获取从(PageNumber - 1) * PageSize + 1开始的PageSize条结果返回给用户.

NoSQL数据库的分布式算法

- - NoSQLFan
本文英文原文发表于知名技术博客《 Highly Scalable Blog》,对NoSQL数据库中的 分布式算法和思想进行了详细的讲解. 文章很长,由@ 可观 进行翻译投稿. 英文原文:《 Distributed Algorithms in NoSQL Databases》. 译文地址:《 NoSQL数据库的分布式算法》.

zookeeper__leader选举

- - 开源软件 - ITeye博客
ZooKeeper进行领导者选举是比较容易的. <1>判定是否存在/zxeample/leader路径. <2>如果不存在,那么试图创建一个会话znode(Ephemeral Path)(path = /zxeample/leader,data=client id). <2.1>创建成功,标识自己是leader.

Twitter的分布式自增ID算法Snowflake

- - 企业架构 - ITeye博客
Twitter-Snowflake算法产生的背景相当简单,为了满足Twitter每秒上万条消息的请求,每条消息都必须分配一条唯一的id,这些id还需要一些大致的顺序(方便客户端排序),并且在分布式系统中不同机器产生的id必须不同. Snowflake算法核心. 把 时间戳, 工作机器id, 序列号组合在一起.

分布式系统的一致性算法简介

- - 互联网 - ITeye博客
在分布式系统中,我们经常遇到多数据副本保持一致的问题,在我们所能找到的资料中该问题讲的很笼统,模模糊糊的,把多个问题或分类糅合在一起,难以理解. 在思考和翻阅资料后,通俗地把一致性的问题可分解为2个问题:. 1、任何一次修改保证数据一致性. 2、多次数据修改的一致性. 在弱一致性的算法,不要求每次修改的内容在修改后多副本的内容是一致的,对问题1的解决比较宽松,更多解决问题2,该类算法追求每次修改的高度并发性,减少多副本之间修改的关联性,以获得更好的并发性能.

SnowFlake 分布式ID生成算法Java实现

- - ITeye博客
SnowFlake 分布式ID生成Java实现. SnowFlake不依赖第三方介质,不像基于ZK,Redis等,每次用完一个区间还得通过网络去获取下一个区间,效率较低,基于SnowFlake的分布式ID生成是目前我见过的最快的. SnowFlake生成的是一个64位的数字,其中42位时间戳,接下来10位是自定义的数,其作用就是区分集群中的所有机器,最后12位是毫秒内序列,集群内每个机器能够在1毫秒内生成2^12 - 1个ID.