Paxos唯一的一致性算法

"Paxos唯一的一致性算法,其他一致性算法都是Paxos的不完整版",Google Chubby作者Mike Burrows曾这样评价Paxo算法。

1990年Leslie Lamport向ACM Transactions on Computer Systems (TOCS)提交了Paxos算法论文The Part-Time Parliament。一致性问题在那个时代并没今天这么受重视,加上论文阅读难度也比较高,所以,并未受到太多关注。

几经修改后于2001年发布了通俗简化版本的Paxos Made Simple,并从中剔除了公式部分。如果没有成功的案例,Paxos的价值恐怕很难得到大众认可。Google的Chubby和Apache的Zookeeper则是这一理论的实践产物。

Paxos算法解决了什么问题呢

在爱琴海一个叫Paxos的岛上住着一群居民,它们用议会形式取代了神权政治,所以事情都要通过议会选举决定。议员的总数是确定的,岛上每一个提议,都有一个编号,编号不断增长的并且不能回退。

提议超过半数议员同意就会生效。每个议员都一个记事本,记录曾经同意过或通过的提议编号,编号会随着提议不断的更新。

每个议员只会同意大于当前编号的提议。如果议员收到小于或等于当前编号的提议,就会拒绝这个提议并通知提出方。

由于这个岛上的议员以义工的方式出现,所以不能保证对每一个提议的投票都能在同一时间完成,所以议员手上记事本的编号并不统一。

议会的目标只有一个:议员对提议达成一致的看法。

Paxos投票原则

Paxos提议投票过程

议会开始运作时,议员的记事本中编号都为统一0。当一个议员需要发出了一个提议时,首先会看自己的记事本,如果当前提议记录的编号为0,则把这个(新)提议的编号定为1,然后向所有议员发出通知。

有一个编号为1的提议需要通过。其他议员在收到通知后看了看自己的记事本,该提议的记录目前编号为0,所以这个提议是可以接受的。

于是收到通知的议员,记下这个提议的编号,并回复接受1号提议。发起提议的议员在收到超过半数的回复时,会接着发出通知告诉所有人,1号提议通过并生效。

收到通知的议员会修改自己记事本中的记录,并将1号提议记下。当有人发出请求问1号提议时,会立刻得到答复。

Paxos提议冲突解决

假设议会有5个议员,a和b都各自发出了一个(不同的)提议,他们都把各自提议的编号定为2(基于手中的记录),如果其他3个议员先收到a的提议,他们在比对完手中的记录时,会一致同意a的提议。

当b的提议到达时,议员查看手中的记事本,发现该提议的编号没有大于记事本中的编号。于是b的提议被否决了,a的提议通过后通知了所有人,b得知新提议的编号后进行了更新,然后,在当前编号的基础之上做了新的提议。

Paxos通知机制

在议会中有一个议员被定为”总统","总统"是通过算法选举出来的,所有的提议由“总统”统一发给所有议员。

Paxos算法的应用场景

Zookeeper

Paxos岛:Zookeeper Server Cluster

总统:ZK Server Leader

议员:Zookeeper Server

提议:ZNode Change(Create/Delete/SetData等等)

提议编号:Zxid(ZooKeeper Transaction Id)

通过的提议:所有ZNode及其数据