spring mvc工作原理_redis aof_paxos 算法(2)

P2c：如果一个编号为n的提案具有value v，那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于n 的任何提案，要么他们已经接受（accept）的所有编号小于n的提案中编号最大的那个提案具有value v。

可以简单描述为：Proposer先从大多数Acceptor那里学习提案的最新内容，然后根据学习到的编号最大的提案内容组成新的提案提交，如果提案获得大多数Acceptor的投票通过就意味着提案被通过。

由于学习提案和通过提案的Acceptor集合都超过了半数，所以一定能学到最新通过的提案值，两次提案通过的Acceptor集合中也一定存在一个公共的Acceptor，在满足约束条件b时这个公共的Acceptor时保证了数据的一致性，于是Paxos协议又被称为多数派协议。

算法本质上很简单，保证一致性所依赖的物理事实是：两个多数集合至少有一个公共成员。把全局信息存储在多数集合返回的统计结果上。

如果一个值曾经被通过了，多数集合中至少有一个成员记得它。

所以提议新值之前，先通过一个prepare阶段就是从一个多数集合中收集到可能已经通过的值，并同步时钟。

然后在accept阶段就是发送可能已通过的值，或者在没有值的情况下提议一个新值。

PaxosLease 是 Kespace 开发的基于 Paxos、Lease 机制的 Master 选举算法

在Paxos中，如果能够选举出一个leader（在Lamport的论文中称之为总统），那么有助于提高投票的成功率。另外这个leader在多个决议的选举中有很重要的作用（要靠他得到决议的连续id）。因此，如何通过某种方法得到一个leader就是PaxosLease所说明的。

Master选举的过程是这样的：从众多的Node中选择一个作为Master，如果该Master 一直 alive则无需选举，如果master crash，则其他的node进行选举下一个master。选择正确性的保证是：任何时刻最多只能有一个master。

逻辑上Master更像一把无形的锁，任何一个节点拿到这个锁，都可成为master，所以本质上Master选举是个分布式锁的问题，但完全靠锁来解决选举问题也是有风险的：如果一个Node拿到了锁，之后crash，那锁会导致无法释放，即死锁。一种可行的方案是给锁加个时间（Lease），拿到锁的Master只能在Lease有效期内访问锁定的资源，在Lease timeout后，其他Node可以继续竞争锁，这就从根本上避免了死锁。

Master在拿到锁后，如果一直alive，可以向其他node”续租“锁，从而避免频繁的选举活动。

算法过程略，详见参考资料 #10：PaxosLease － 老码农的专栏

1、算法的角色与Paxos一样，也分Proposer、Acceptor、Learner，各角色的行为也与paxos基本一致。

2、accept 的 1a) 阶段

原始的paxos规定，如果接收的value v不为空，则使用v继续accept阶段，以保证每次选举仅选出一个决议；

PaxosLease选举的目的是使其他node接受自己作为master，当接收的value不为空时，自己应该退出选举，而不是继续提交其他Node的value。paxos 算法也就是说，只要当前node知道其他Node可能会优先自己成为master，则退出选举，成就他人。

3、Master选举因为频率低。PaxosLease在失败重新提交proposal时随机等待一段时间，因为各Node等待时间的不一致，只要运行足够长的时间，活锁总能避免。

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