一：一致性算法Paxos
Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。
1.1 Paxos解决了什么问题
在常见的分布式系统中，总会发生诸如通信异常、节点故障、网络分区等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。
注意：这里某个数据的值并不只是狭义上的某个数，它可以是一条日志，也可以是一条命令（command）。根据应用场景不同，某个数据的值有不同的含义。
1.2 Paxos的相关概念
提案 (Proposal)：Proposal信息包括提案编号 (Proposal ID) 和提案的值 (Value)
在Paxos算法中，有三种角色）：
- Proposer：提案发起者，提案者提倡客户请求，试图说服Acceptor对此达成一致，并在发生冲突时充当协调者以推动协议向前发展
- Acceptor：决策者，可以批准提案，Acceptor可以接受（accept）提案；如果某个提案被选定（chosen），那么该提案里的value就被确定了
- Learners：最终决策的学习者，学习者充当该协议的复制因素
1.3 推导过程
参考博客：https://www.cnblogs.com/linbingdong/p/6253479.html
1.4 Proposer生成提案规则
Proposer生成提案之前，应该先去『学习』已经被选定或者可能被选定的value，然后以该value作为自己提出的提案的value。如果没有value被选定，Proposer才可以自己决定value的值。这样才能达成一致。这个学习的阶段是通过一个『Prepare请求』实现的。
下图为多数Acceptor集合（半数以上）没有接收提案的情况：
![]()
Proposer提案生成算法：
- Proposer选择一个新的提案编号N，然后向某个Acceptor集合（半数以上）发送请求，要求该集合中的每个Acceptor做出如下响应（response）。
(a) 向Proposer承诺保证不再接受任何编号小于N的提案。
(b) 如果Acceptor已经接受过提案，那么就向Proposer响应已经接受过的编号小于N的最大编号的提案。
我们将该请求称为编号为N的Prepare请求。
- 如果Proposer收到了半数以上的Acceptor的响应，那么它就可以生成编号为N，Value为V的提案[N,V]。这里的V是所有的响应中编号最大的提案的Value。如果所有的响应中都没有提案，那 么此时V就可以由Proposer自己选择。
生成提案后，Proposer将该提案发送给半数以上的Acceptor集合，并期望这些Acceptor能接受该提案。
我们称该请求为Accept请求。（注意：此时接受Accept请求的Acceptor集合不一定是之前响应Prepare请求的Acceptor集合）
1.5 Acceptor接收提案规则
一个Acceptor可能会收到来自Proposer的两种请求，分别是Prepare请求和Accept请求，对这两类请求作出响应的条件分别如下：
- Prepare请求：Acceptor可以在任何时候响应一个Prepare请求
- Accept请求：在不违背Accept现有承诺的前提下，可以任意响应Accept请求
因此，对Acceptor接受提案给出如下约束：
p1a：一个Acceptor只要尚未响应过任何编号大于N的Prepare请求，那么他就可以接受这个编号为N的提案。
Acceptor算法优化
由上面可知，如果Acceptor收到一个编号为N的Prepare请求，在此之前它已经响应过编号大于N的Prepare请求。根据P1a，该 Acceptor不可能接受编号为N的提案。因此，该Acceptor可以忽略编号为N的Prepare请求。
通过这个优化，每个Acceptor只需要记住它已经批准的提案的最大编号以及它已经做出Prepare请求响应的提案的最大编号就行了
1.6 Paxos算法描述
![Paxos算法描述]( "Paxos算法描述")
阶段一：
- (a) Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。
- (b) 如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。
阶段二：
- (a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。
- (b) 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。
1.7 Learner学习被选定的value
三种方式：
![Learner学习被选定的value]( "Learner学习被选定的value")
1.8 如何保证Paxos算法的活性
假设存在这样一种极端情况，有两个Proposer依次提出了一系列编号递增的提案，导致最终陷入死循环，没有value被选定,具体流程如下:
![Paxos算法活性保证]( "Paxos算法活性保证")
解决：通过选取主Proposer，并规定只有主Proposer才能提出议案。这样一来只要主Proposer和过半的Acceptor能够正常进行网络通信，那么但凡主Proposer提出一个编号更高的提案，该提案终将会被批准，这样通过选择一个主Proposer，整套Paxos算法就能够保持活性。
