格伯纳作者
2019-08-26 17:20:52
paxos分布式一致性算法

关于paxos的通俗解释,大家可以去围观以下两个博客:用三国场景展现paxos原理

博文1:http://blog.csdn.net/russell_tao/article/details/7244530

博文2:http://blog.csdn.net/russell_tao/article/details/7238783

一、paxos解决什么问题

具体来说是这样:分布式系统中由于网络之间通讯可能会中断,虽然概率很低,但是没有100%完美的网络因此,依靠网络通讯的计算机之间要达成共识就比较困难,假设有X, Y和Z三台计算机谋划在周一攻击人类世界,它们的攻击计划是只要所有计算机可用于战斗时就一起进行攻击,不落下任何一台机器,但是当他们决定具体什么时间开始攻击时,在这个关键问题上往往会出错。

一个基本问题是,每台机器都有自己的攻击时间建议,计算机X可以建议在08:00时间,因为这个时间正是周一早晨,而人们刚刚过完狂欢的周末休息天,但是计算机Z认为13:00比较好,理由当然也有一大堆,让这三台计算机基于某个时刻达成共识是非常困难的,因此,也给人类反击留下了机会。

另外一个情况是,这三台计算机是位于世界不同的位置,之间通讯或许通过电缆或者其他不太可靠的网络设备通讯,如果X建议在08:00,它必须确认它的这个建议能够到达活着的Y和Z,以免一个人战斗。

问题是:我们不能准确地知道某个计算机的延迟的原因:是因为性能慢了还是已经是彻底死机不能用?

那么,X怎么知道其他两个计算机是可用的呢?也就是说,当X和其他两个计算机通讯发现得到响应要过很长时间,它不能确定这两台计算机到底还能不能继续活下去,也许这次通讯有延迟了,下一次它们又活过来了没有延迟了,也许下次延迟更长了一点,也许下次延迟稍微短了一点,这些随机概率问题使得X不能确定Y和Z到底是出了什么问题造成延迟的,是因为处理了某个特别耗费CPU的任务还是因为死锁等原因?当然,有些天真的设计者会说,只要我们将性能监控到位,如果延迟超过一定时间,我们人工介入告诉X确切情况就可以,那么这种人工介入的分布式系统不是一个天然自洽的自动化系统了,不在我们讨论范围之内,而且这样的系统会让人疲于奔命。

因为X不能确定Y或Z是否可用,所以X仅仅只能和Y与Z中一台基于攻击时间达成共识,就无法完全三台机器全部投入战斗的计划。注意的是,X Y Z三台中任何一台都可能会出现延迟,这就造成了三台机器之间任何通讯都是无法确认可靠的,比如X发出消息给Z,Z确认后回执给X,但是这段时间X突然死机了,那么Z要等待X多长时间才能知道它收到确认呢?还是再次等待X回复确认的确认,这样无限循环下去也不能解决它们之间通讯可能出现随机不可靠的问题。

所有关键问题在于:由于这三台机器之间通讯是无法保证100%可靠,它们就不能就任何事情达成共识。

二、paxos来源

Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的"La",此人现在在微软研究院)于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。三、paxos定义算法中的参与者主要分为三个角色,同时每个参与者又可兼领多个角色:

⑴proposer 提出提案,提案信息包括提案编号和提议的value;

⑵acceptor 收到提案后可以接受(accept)提案;

⑶learner 只能"学习"被批准的提案;

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

⑴决议(value)只有在被proposers提出后才能被批准(未经批准的决议称为"提案(proposal)");

⑵在一次Paxos算法的执行实例中,只批准(chosen)一个value;

⑶learners只能获得被批准(chosen)的value;

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

⑴P1:一个acceptor必须接受(accept)第一次收到的提案;

⑵P2a:一旦一个具有value v的提案被批准(chosen),那么之后任何acceptor 再次接受(accept)的提案必须具有value v;

⑶P2b:一旦一个具有value v的提案被批准(chosen),那么以后任何 proposer 提出的提案必须具有value v;

⑷P2c:如果一个编号为n的提案具有value v,那么存在一个多数派,要么他们中所有人都没有接受(accept)编号小于n的任何提案,要么他们已经接受(accpet)的所有编号小于n的提案中编号最大的那个提案具有value v;

四、paxos算法

算法(决议的提出与批准)主要分为两个阶段:

1. prepare阶段: 

(1). 当Porposer希望提出方案V1,首先发出prepare请求至大多数Acceptor。Prepare请求内容为序列号;

(2). 当Acceptor接收到prepare请求时,检查自身上次回复过的prepare请求

a). 如果SN2>SN1,则忽略此请求,直接结束本次批准过程;

b). 否则检查上次批准的accept请求,并且回复;如果之前没有进行过批准,则简单回复;

2. accept批准阶段: 

(1a). 经过一段时间,收到一些Acceptor回复,回复可分为以下几种:

a). 回复数量满足多数派,并且所有的回复都是,则Porposer发出accept请求,请求内容为议案;

b). 回复数量满足多数派,但有的回复为:,……则Porposer找到所有回复中超过半数的那个,假设为,则发出accept请求,请求内容为议案;

c). 回复数量不满足多数派,Proposer尝试增加序列号为SN1+,转1继续执行;

(1b). 经过一段时间,收到一些Acceptor回复,回复可分为以下几种:

a). 回复数量满足多数派,则确认V1被接受;

b). 回复数量不满足多数派,V1未被接受,Proposer增加序列号为SN1+,转1继续执行;

(2). 在不违背自己向其他proposer的承诺的前提下,acceptor收到accept 请求后即接受并回复这个请求。

1
1
ZooKeeper要点分析
创建时间:2019-08-26 17:20:10
从协议到应用,一步步讲解zookeeper在大数据系统中的应用,主要是一些要点分析
展开
购买事项

付费用户可享受文章永久阅读权限;

本课程为虚拟产品,付费后不可退换;

您拥有向专栏作者进行答疑的机会,专栏作者利用业余时间选择性回答;

作者

  • 格伯纳
    作者
戳我,来吐槽~