技术记录栈

记录点滴:java、datebase、linux、spring、javascript、nginx

2018/10/09

Paxos世上唯一的一致性算法

”只有一个一致性算法,那就是Paxos,所有其他的一致性算法都只是Paxos的不完整版”,Google Chubby的作者Mike Burrows曾这样说道。

1990年Leslie Lamport向ACM Transactions on Computer Systems (TOCS)提交了Paxos这一算法的论文The Part-Time Parliament。

一致性问题在哪个时代好像并没有凸显出来,并且论文阅读难度相对较高,所以并未受到太多关注。

几经修改于2001年发布了通俗简化版本的Paxos Made Simple,并从中剔除了公式部分。

对于大众而言即便能够读懂如果没有案例结合,好像也就不会体会它的价值所在。Google的Chubby和Apache的Zookeeper则是这一理论的产物。

这一理论到底解决了什么现实问题呢。可以看看关于这一理论的故事原型。

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

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

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

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

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

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

有一个编号为1的提议需要通过,其他议员在收到通知后看了一下自己的记事本,手上记录的提议编号为0,认为这个提议是可接受的,

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

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

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

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

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

能否从Zookeeper中看到这一过程的影子,是对Paxos算法理解的一个验证,当然也有很多外来特性被加入到Zookeeper Server中。

Paxos岛:Zookeeper Server Cluster

总统:ZK Server Leader

议员:Zookeeper Server

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

提议编号:Zxid(ZooKeeper Transaction Id)

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