Paxos
Paxos
Paxos算法是Leslie Lamport于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。
问题提出
分布式系统基于消息传递，不可避免的会发生以下错误：进程执行慢、被杀死或重启，消息在网络中延迟，丢失，重复。由于这些问题，想要在分布式系统中就某个值达成一致变得非常困难。
应用场景
在已知不存在错误消息（拜占庭错误）的情况下，Paxos算法可以在一个可能发生上述异常的系统中令所有节点对某个值达成一致。
算法流程
Paxos将节点角色分为Proposer，Acceptor，Learner，一个节点可以同时有多个角色。只有Proposer可以发起提案，Acceptor负责接受提案，而Learner只能学习被批准的提案。一个提案被批准当且仅当半数以上的Acceptor接受了该提案。
提案定义为(n,v)，其中n是唯一序号，而v是提案的值。n可以本地自动生成后拼装上节点ID。
Paxos算法分为两个阶段：
阶段一：
- Proposer选择一个提案序号n，之后向半数以上的Acceptor发送编号为N的Prepare请求。
- 如果一个Acceptor收到一个编号为N的prepare请求，若N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就将它已经接受过的编号最大的提案（如果存在）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。
阶段二：
- 如果Proposer收到半数以上Acceptor对其编号为n的提案的prepare请求的响应，那么它就发送一个提案(n,v)的Accept请求给半数以上的Acceptor。如果所有返回的prepare请求响应都不带之前提案的信息，则v可以为proposer自定义的值，否则v为编号最大的提案的值。
- 如果Acceptor收到一个编号为n的提案的Accept请求，只要该Acceptor没有对编号大于n的prepare请求做出过响应，那么它就将接受该提案。
证明
下面证明paxos算法的正确性：
如果提案(n,v)已经被批准，那么对于任意m>n，且u!=v的提案(m,u)，都不会被批准
如果提案(n,v)已经被批准，那么对于任意m>n，且u!=v的提案(m,u)，没有Acceptor会接受
如果提案(n,v)已经被批准，那么对于任意m>n，且u!=v的提案(m,u)，没有Proposer会提出Accept请求
证明：我们首先必须意识到对于同一个acceptor，不可能同时执行两个操作。因此下述两个操作：
- 接受提案的操作
- 承诺prepare操作
必定有一个先后顺序。由于批准提案和承诺prepare都需要多数派，二者所涉及的acceptors必定有非空交集。而考虑到提案被批准，因此我们可知在交集中的acceptors一定时先执行对编号为n的提案的接受后才执行对编号为m的prepare。因此我们可知当编号为m的提案被prepare时一定有之前接受的提案的信息返回。
我们可以利用归纳法，当m=n+1时，考虑到提案(n,v)已经被批准，因此返回的最大提案即为(n,v)。而对于m<k成立时，则当m=k时，仅可能返回的编号最大的已接受的提案为(n,v), (n+1,v), … , (m - 1, v)，而值均为v。
因此编号为m的提案一定为采用v作为自己的值发起提案，而这也对应的(m,u)不会被提出accept请求。
有了上面的三条性质后，我们就可以得出paxos不会批准不同值的提案，换言之，一致性得到了保障。
学习过程
在提议被批准后，该proposer需要广播给所有learner让它们得知。一般的方式是从learner中挑选出一个子集，每个acceptor在接受了一个提案后，就将接受信息发送给子集中的learner，而子集中的learner再广播给所有其余的learner。其总共发送的消息数目为O(|Learners|* C)，其中C是子集的大小。
如果learner从休眠中醒来，可能无法得知v的最新值，可以通过prepare过程获得。
异常恢复
在算法的执行过程中可能会产生很多的异常情况，其中在特定流程下的宕机会影响系统的一致性。比如proposer早发起accept之前宕机，acceptor在accept时宕机等等。
为了保证paxos算法的正确性，我们必须保证节点在恢复后能正常运作。我们需要采用持久化技术：
- proposer需要持久化已提交的最大proposal编号。
- acceptor存储已经promise的最大编号，已经accept的最大编号，value。
- learner存储已经学习过的最大编号和value。
MultiPaxos
尽管Paxos可以保证一致性，但是不能保证多个提案中至少有一个可以获批。
当自己的Accept请求失败了，一般的处理方法增大本地序号后重新发起prepare-accept流程。
但是这会导致活锁问题，假设有两个提案A，B被分别提出，A在prepare完后，所有acceptors承诺了B，这导致A的accept请求失败。而A增大了自己的序号后重新发起prepare，导致所有acceptors承诺了A，这又将导致B的accept请求失败。虽然这种情况发生的可能性很小，但是理论上还是可能发生的。
Lamport认为应该引入Leader机制来解决这一问题。我们要从所有的proposers中寻取出一个leader，所有的proposer都通过向leader发送消息来提交自己的提案，而leader负责为它们执行prepare-accept流程。
PaxosLease
考虑到paxos本身就是分布式协调算法，而Leader选举也是分布式协调算法，那么是否能用paxos解决自身的Leader选举呢？
先看看master选举和value选举的区别，master选举必定伴随着之前master的下线，是低频率事件。因此我们允许在master选举上耗费额外的时间。还有一个区别就是不需要持久化master的信息。
PaxosLease是Kespace开发的基于Paxos、Lease的Master选举算法，算法基本与Paxos一致，除了增加accept失败后的随机时长等待机制以避免死锁。包括Keyspace、Libpaxos、Zookeeper、Chubby等实现中都采用了该算法。
在一个proposer与Leader通信超时后（心跳超时），该proposer选择自己作为新的Leader并发起选举（类似于值选举），如果prepare失败（即有acceptor返回之前的租约信息或者返回ERROR），则等待T时后重启prepare-accept请求，如果accept失败，则随机等待一段时间后重启prepare-accept流程。
在PaxosLease中，我们为每个paxos设置一个计时器，计时器的时间为租约时长T，每当某个acceptor接受租约时，都将重置本地计时器，一旦计时器到期，则会清除内部记录的租约信息（清除为空）。
我们一般不为acceptor持久化租约信息，而是当acceptor宕机重启后，会等待额外M时间（M>T)，之后才加入系统。
Leader可以在租约结束之前重新发送租约，以重置acceptors中的计时器。也可以发送提前结束租约的请求，所有acceptor会检查内部状态，如果发现接受了该leader的租约，则清空租约信息。