zookeeper学习之二:Paxos算法

2021-08-31  本文已影响0人  进击的小鹿

1、paxos是什么,怎么提出来的

Paxos算法是Lamport于1990年提出的一种基于消息传递的一致性算法。Paxos 算法是分布式一致性算法,用来解决一个分布式系统如何就某个 决议 达成一致的问题,目前公认的解决分布式一致性问题最有效的算法之一。

Lamport大师说:The Paxos algorithm, when presented in plain English, is very simple.
Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。

Paxos 协议是一个解决分布式系统中,多个节点之间就某个值(提案)达成一致(决议)的通信协议。

2、作用、用途

在常见的分布式系统中,总会发生诸如机器宕机或网络异常(包括消息的延迟、丢失、重复、乱序,还有网络分区)等情况。paxos算法理论就是 解决这种分布式场景中的一致性问题。

在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个"一致性算法"以保证每个节点看到的指令一致。

chubby锁服务使用paxos作为chubby cell中的一致性算法,paxos的人气从此一路狂飙。

zookeeper的zab协议也是paxos的变种。

PhxPaxos是腾讯公司微信后台团队自主研发的一套基于Paxos协议的多机状态拷贝类库。

“X-Paxos”是阿里巴巴数据库团队面向高性能、全球部署以及阿里业务特征等需求,实现的一个高性能分布式强一致的Paxos独立基础库。

3、原理过程

有的,还有client的角色。

一个进程可以有多种角色。

多个Acceptor(如果是一个,那宕机就完蛋了)

P1:一个Acceptor必须接受它收到的第一个提案。
规定:一个提案被选定需要被半数以上的Acceptor接受

P2:如果某个value为v的提案被选定了,那么每个编号更高的被选定提案的value必须也是v。
P2a:如果某个value为v的提案被选定了,那么每个编号更高的被Acceptor接受的提案的value必须也是v。
P2b:如果某个value为v的提案被选定了,那么之后任何Proposer提出的编号更高的提案的value必须也是v。

示例:

4、优缺点

算法本身的推导过程有点晦涩难懂,理论性算法,工程上实现起来比较麻烦(别人说的)

活锁问题

参考 :
https://www.zhihu.com/question/19787937
http://harry.me/blog/2014/12/27/neat-algorithms-paxos/

上一篇 下一篇

猜你喜欢

热点阅读