fast paxos_知行学社 paxos_一步一步理解paxos算法

淘宝搜索的博客 提到Paxos是zookeeper的灵魂

有一篇文章标题更是以“Zookeeper全解析——Paxos作为灵魂” 作为标题，认为是zookeeper的基础：

“

Google的Chubby，Apache的Zookeeper都是基于它的理论来实现的，Paxos还被认为是到目前为止唯一的分布式一致性算法，其它的算法都是Paxos的改进或简化。有个问题要提一下，Paxos有一个前提：没有拜占庭将军问题。就是说Paxos只有在一个可信的计算环境中才能成立，这个环境是不会被入侵所破坏的。

”

Paxos这个算法是Leslie Lamport在1990年提出的一种基于消息传递的一致性算法.Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。

part-time parliamentPaxos Made Simple里这样描述Paxos算法执行过程：

prepare 阶段：

proposer 选择一个提案编号 n 并将 prepare 请求发送给 acceptors 中的一个多数派；

批准阶段：

在不违背自己向其他 proposer 的承诺的前提下，acceptor 收到 accept 请求后即接受这个请求。

wiki上是两个阶段，论文里却是说三阶段，而且默认就有了个proposer相当于leader。查资料有大侠列出了第三个阶段(?p=2724)：

3. Learn阶段:

当各个Acceptor达到一致之后，需要将达到一致的结果通知给所有的Learner.

zookeeper采用org.apache.zookeeper.server.quorum.FastLeaderElection作为其缺省选举算法

这篇文章?p=162&replytocom=782直接用paxos实现作为标题，提到 zookeeper在选举leader的时候采用了paxos算法(主要是fast paxos)

偶然看到下边有人反驳：

魏讲文：“

FastLeaderElection根本不是Paxos，也不是Fast Paxos的实现。

FastLeaderElection源码与Paxos的论文相去甚远。

Paxos与 FastPaxos算法中也有一个leader选举的问题。

FastLeaderElection对于zookeeper来讲，只是相当于Paxos中的leader选举。

”

二、资料证实

好的，查查资料，分析源码开始调研

首先是魏讲文的反驳 ：

There is a very common misunderstanding that the leader election algorithm in zookeeper is paxos or fast paxos. The leader election algorithm is not paxos or fast paxos, please consider the following facts:

There is no the concept of proposal number in the leader election in zookeeper. the proposal number is a key concept to paxos. Some one think the epoch is the proposal number, but different followers may produce proposal with the same epoch which is not allowed in paxos.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-37027-1.html