Paoxs算法
首先看一下Paoxs算法,一般说到zookeeper,我们都会提起Paoxs算法和Lesile Lamport.
Paoxs算法是zookeeper的灵魂,这个算法是Leslie Lamport在1990年提出的一种基于消息传递的一致性算法.Paxos 算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。在ZooKeeper中的应用场景就是Leader选举。
该算法由Leslie于1990年在文章The Part-Time Parliament中首次提出,但是这篇文章相当的晦涩难懂(也有一些轶事,可以看文章链接中Leslie自己写的内容),于是,Lesilie在2001年写下了Paxos Made Simple.他对此解释道:
At the PODC 2001 conference, I got tired of everyone saying how difficult it was to understand the Paxos algorithm, published in [122]. Although people got so hung up in the pseudo-Greek names that they found the paper hard to understand, the algorithm itself is very simple. So, I cornered a couple of people at the conference and explained the algorithm to them orally, with no paper. When I got home, I wrote down the explanation as a short note, which I later revised based on comments from Fred Schneider and Butler Lampson. The current version is 13 pages long, and contains no formula more complicated than n1 > n2.
Paxos Made Simple的abstract只有一句话:
The Paxos algorithm, when presented in plain English, is very simple.
在上文中是这样描述Paoxs算法执行过程的:
Phase 1.
(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.
Phase 2.
(a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.
这几乎就是Paxos的全部了. 这里就不一句一句翻译了。
Zab协议
Zab是一个高性能的广播协议,主要用于主备系统,它是专门为ZooKeeper设计的。Zab协议的详细内容请参考论文《Zab: High-performance broadcast for primary-backup systems》。
ZAB相比Paxos的优点有: