Goal
1.必须并且只能在一个提案上达成一致
2.有且仅有有一个提案能被选中
Requirements
1.安全性(保证paxos不会做出错误的选择)
a)仅有一个提案将被选中
b)如果一个节点已经得知某个提案被选中，那么这个提案一定是被集群所选中
2.活性 (不做错误的选择还不够，我们需要保证paxos能做出正确的选择)(保证活性的前提是集群中的大多数在正常运行并且以合理的及时性进行沟通)
a)最终一定会对某一个提案达成一致
b)如果对一个提案达成一致，那么集群一定会感知到
Components
1.Proposers
a)提出将要被选举的提案
b)处理客户端的请求
2.Acceptors
a)回复来自Proposers的请求
b)回复可以想象成用来达成一致性的投票
c)储存被达成一致的提案还有给出的投票等等
d)最终想要知道集群对哪个提案达成一致
依据上面的要求，我们先设想几种最简单的paxos实现方法
第一种:只有一个Acceptor
缺点:假设一个提案被唯一的acceptor选中之后，这个acceptor stop或者crash掉了，我们没办法在该acceptor恢复之前知道被选中的提案是什么。
解决方案(Quorum)
a)我们需要多个Acceptor(一般来说3,5,7....)
b)当acceptors中的大多数都对一个提案达成一致的时候，这个提案才被选中
c)这样的话如果只有少部分的acceptor stop/crash/partion的时候，集群仍然能够感知到被选中的提案
多个Acceptor带来的问题，如何就某个提案达成一致?
1.尝试一个最简单的方案-->每个acceptor只接受它收到的第一个提案,那么当有多个提案同时提给acceptors时，可能会造成提案没办法被选中的情况，如下图:
注意:提案被acceptor 接受的时候不代表这个提案被选中，只有大多数acceptors都接受同一个提案的时候，这个提案才意味着被选中。
这违反了Paxos算法的活性要求。那么得出结论，acceptor必须可以多次接受不同的提案(当然前提是在有提案被集群选中之前)，换句话说就是如果只有一轮投票的话集群和可能不能对某一个提案达成一致，我们需要更多轮的投票。
2.尝试另一个方案-->每个acceptor接受他收到的每一个提案，那么这样出现集群对不同的提案达成一致，如下图所示。
S1提出提案red，这时候S1，S2，S3接受提案red，此时集群中的大多数就red提案达成一致，red被选中。之后提案blue被S5提出，之后S3，S4，S5接受blue提案，此时集群中的大多数就blue提案达成一致，blue被选中。这违背了Paxos算法的基本原则--仅有一个提案将被选中。目前能想到规避这个问题的方法就是当提案被提出的时候检查此时是否已经有提案被选中，如果有，则将此次提案换成已经被选中的提案。这样的话即使集群选中了第二次的提案，该提案也和之前选中的提案一致，所以没有影响。
这种方案可以称之为"两阶段协议"
一阶段-->proposer先查询集群是否已经选中某个提案，如果选中，将已经选中的提案替换成原本想要提出的提案
二阶段-->通知其他acceptors接受提出的提案
这种方案是否没有问题？答案是否，考虑如下场景
过程如下
1)S1提出提案red，发现当前并没有被选中的提案，则通知S1，S2，S3接受提案red
2)在S123还未相应接受提案的请求之前，S5提出提案blue，同样检查是否有被选中的提案，此时S123并没有接受提案red，所以提案blue被发送往S345，并且由于种种原因，对S345接受提案blue的请求比S123接受提案red的请求更早完成，那么此时集群选中提案blue
3)当S345完成接受提案之后，S123也完成接受提案red，此时S3存储的提案被改写成red，集群此时选中的提案为red。
很不幸，我们又违反了Paxos的基本原则。。
对于这个问题我们还是有解决方案的-->如果集群已经选定了某个提案，那么任何带有竞争关系的提案必须被放弃，在上面那个case中，S3已经接受了提案blue，他必须拒绝提案red
为了做到这一点，我们必须对提案的进行排序，以便达到新的提案可以拒绝老的提案的需求(因为S3作为acceptor并不知道存储在自身的提案是否被集群选中，所以他需要有一个方案能判定后来的提案能否接受，所以我们需要排序)
那么问题来了，如何对提案进行排序？
我们需要给每一个提案一个唯一的proposal_no，并且有如下规则
1)proposal_no越大，proposal优先级越高
2)proposer提出提案时选择的proposal_no要比之前使用过的更高
我们可以这样设计一个简单的proposal_no = round_no + server_id
server_id是每一个server的编号，他是唯一的，把他加入proposal_no可以保证当某个proposer提出proposal的时候新的proposal_no不会被其他proposer生成过。
round_no会随着时间增加，每个proposer都保留maxRoundNo(此proposer见过的最大的round_no,此数据必须落盘，如果该proposer刚从故障中恢复，请不要使用该maxRoundNo)，每次新的proposal提出的时候令round_no=maxRoundNo+N
总结一下，目前方案还是两阶段
Phase1:广播Prepare rpc请求
1)寻找是否有被选中的提案
2)阻塞正在提交中老提案
Phase2:广播Accept rpc请求
1)请求Acceptors接受提案
我们用伪代码表示下:
Prepare阶段
1)Proposer生成一个新的proposal_no
2)Proposer调用prepare(proposal_no)方法请求每一个server
3)Acceptors响应prepare(proposal_no)方法
//minProposalNo 此Proposer见过最大的proposal_no
//acceptedProposalNo 接受提案时的proposal_no
//acceptedValue 接受的提案
if(proposal_no > minProposalNo){
minProposalNo = proposal_no;
}
return acceptedProposalNo,acceptedValue;
4)当Proposer收到大多数Acceptors的回复时
//value 本次提案
//acceptedValue 从大多数Acceptors返回的最大acceptedProposalNo对应的acceptedValue
if(List<acceptedValue> != null){
value = acceptedValue
}
Accept阶段
5)Proposer 调用 accept(proposal_no,value)请求每一个server
6)Acceptors处理accept请求
if(proposal_no >= minProposalNo){
acceptedProposalNo = proposal_no = minProposalNo;
}
return minProposalNo;
7)如果Proposer接收到了大多数Acceptors的返回
if(any result > proposal_no){
//返回第一步重新开始
goto 1;
}else{
value has been choosen
}
注意:acceptedProposalNo,acceptedValue,minProposalNo必须在Acceptors服务器中可靠存储。
下面来看几个例子，要搞清楚为何Paxos能正常的工作关键就时分析出新的Proposal发出prepare请求的时间点。该时间点可以出现在三个位置，分别如下
1.当新的proposal到达时，之前的proposal已经完全执行完毕换句话说已经有提案被选定
P 3.1 P表示Prepare阶段, 3表示proposal_no，1表示server_id，意思就是S1发送prepare请求到S1，S2，S3服务器。
A 3.1 X表示Accept阶段，3表示proposal_no，1表示server_id，X是提案
在这种情况下，P 4.5 发起后检测到已有选定的提案X，则将自己的提案从Y更换成X
2.当新的proposal到达时，之前的proposal执行了一半，部分server已经接受了提案但是还未选定,而且新的proposal在prepare阶段能感知到之前proposal 执行accept的结果
此时的情况和1一样，在新的proposal prepare阶段执行的server恰好和老的proposal accept阶段执行的server有重合-->S3,那么S5发起的proposal将会将提案由Y改成X并调用accept
3.当新的proposal到达时，之前的proposal执行了一半，部分server已经接受了提案但是还未选定,而且新的proposal在prepare阶段不能感知到之前proposal 执行accept的结果
新的proposal prepare阶段无法感知老proposal accept阶段执行结果，所以当新的proposal发起accept阶段时，使用的还是新的提案Y并且在S5，S4上执行成功，这时候老的proposal accept阶段到达，因为accept也必须要请求到集群中的大多数server，所以必然会与新的proposal 的prepare阶段server有交集，这时发现S3上的proposal_no(4.5) > 自己的proposal_no(3.1)则老的proposal accept阶段会被放弃，并且回到1重新来过。
Liveness
提案间的竞争可能会导致Basic Paxos失活(无法选择一个提案)
如上图所示
P3.1在执行A3.1X之前，P3.5到达，则A3.1X放弃并回到步骤1重新发起新的proposal P4.1，不巧的是此时A3.5Y又发现P4.1已经执行，只能放弃并且回到步骤1重新开始，如此循环往复集群将永远无法就某一个提案达成一致。
解决方案
在A3.1X被拒绝之后不要马上发起新的proposal而是等待一个合理的时间让A3.5Y能够有机会完成。
原视频在此，真的将的非常好
https://www.bilibili.com/video/av16805461/
