paxos协议_从paxos到zookeeper_raft算法paxos算法(6)

proposer已知的最大值来自两部分：proposer自己对编号自增后的值和接收到acceptor的reject后所得到的值

以3个proposer P1、P2、P3为例，开始m=0,编号分别为0，1，2

P1提交的时候发现了P2已经提交，P2编号为1 > P1的0，因此P1重新计算编号：new P1 = 1*3+0 = 4

P3以编号2提交，发现小于P1的4，因此P3重新编号：new P3 = 1*3+2 = 5

整个paxos算法基本上就是围绕着proposal编号在进行：proposer忙于选择更大的编号提交proposal，acceptor则比 较提交的proposal的编号是否已是最大，只要编号确定了，所对应的value也就确定了。所以说，在paxos算法中没有什么比proposal的 编号更重要。

活锁

当一proposer提交的poposal被拒绝时，可能是因为acceptor promise了更大编号的proposal，因此proposer提高编号继续提交。 如果2个proposer都发现自己的编号过低转而提出更高编号的proposal，会导致死循环，也称为活锁。

Leader选举

活锁的问题在理论上的确存在，Lamport给出的解决办法是选举出一个proposer作leader，所有的proposal都通过leader来提交，当Leader宕机时马上再选举其他的Leader。

Leader之所以能解决这个问题，是因为其可以控制提交的进度，比如果之前的proposal没有结果，之后的proposal就等一等，不着急提高编号再次提交，相当于把一个分布式问题转化为一个单点问题，而单点的健壮性是靠选举机制保证。

问题貌似越来越复杂，因为又需要一个Leader选举算法，但Lamport在fast paxos中认为该问题比较简单，因为Leader选举失败不会对系统造成什么影响，因此这个问题他不想讨论。但是后来他又说，Fischer, Lynch, and Patterson的研究结果表明一个可靠的选举算法必须使用随机或超时（租赁）。

Paxos本来就是选举算法，能否用paxos来选举Leader呢？选举Leader是选举proposal的一部分，在选举leader时再用 paxos是不是已经在递归使用paxos？存在称之为PaxosLease的paxos算法简化版可以完成leader的选举，像Keyspace、 Libpaxos、Zookeeper、goole chubby等实现中都采用了该算法。关于PaxosLease，之后我们将会详细讨论。

虽然Lamport提到了随机和超时机制，但我个人认为更健壮和优雅的做法还是PaxosLease。

Leader带来的困惑

Leader解决了活锁问题，但引入了一个疑问：

既然有了Leader，那只要在Leader上设置一个Queue，所有的proposal便可以被全局编号，除了Leader是可以选举的，与Paxos算法1 提到的单点MQ非常相似。

那是不是说，只要从多个MQ中选举出一个作为Master就等于实现了paxos算法？现在的MQ本身就支持Master-Master模式，难道饶了一圈，paxos就是双Master模式？

仅从编号来看，的确如此，只要选举出单个Master接收所有proposal，编号问题迎刃而解，实在无须再走acceptor的流程。paxos协议但 paxos算法要求无论发生什么错误，都能保证在每次选举中能选定一个value，并能被learn学习。比如leader、 acceptor,learn都可能宕机，之后，还可能“苏醒”，这些过程都要保证算法的正确性。

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