Paxos算法
Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。
Paxos：多数派决议（最终解决一致性问题）
Paxos算法有三种角色：Proposer，Acceptor，Learner
Proposer：提交者（议案提交者）
提交议案(判断是否过半)，提交批准议案(判断是否过半)
Acceptor：接收者（议案接收者）
接受议案或者驳回议案，给proposer回应(promise)
Learner：学习者（打酱油的）
如果议案产生，学习议案。
- 如果Acceptor没有接受议案，那么他必须接受第一个议案
- 每个议案必须有一个编号，并且编号只能增长，不能重复。越往后越大。
- 接受编号大的议案，如果小于之前接受议案编号，那么不接受
- 议案有2种(提交的议案，批准的议案)
1）Prepare阶段（议案提交）
a）Proposer希望议案V。首先发出Prepare请求至大多数Acceptor。Prepare请求内容为序列号K
b）Acceptor收到Prepare请求为编号K后，检查自己手里是否有处理过Prepare请求。
c）如果Acceptor没有接受过任何Prepare请求，那么用OK来回复Proposer，代表Acceptor必须接受收到的第一个议案（设定1）
d）否则，如果Acceptor之前接受过任何Prepare请求（如：MaxN），那么比较议案编号，如果K<MaxN，则用reject或者error回复Proposer
e）如果K>=MaxN，那么检查之前是否有批准的议案，如果没有则用OK来回复Proposer，并记录K
f）如果K>=MaxN，那么检查之前是否有批准的议案，如果有则回复批准的议案编号和议案内容（如：<AcceptN, AcceptV>， AcceptN为批准的议案编号，AcceptV为批准的议案内容）
2）Accept阶段（批准阶段）
a）Proposer收到过半Acceptor发来的回复，回复都是OK，且没有附带任何批准过的议案编号和议案内容。那么Proposer继续提交批准请求，不过此时会连议案编号K和议案内容V一起提交（<K, V>这种数据形式）
b）Proposer收到过半Acceptor发来的回复，回复都是OK，且附带批准过的议案编号和议案内容（<pok，议案编号，议案内容>）。那么Proposer找到所有回复中超过半数的那个（假设为<pok，AcceptNx，AcceptVx>）作为提交批准请求（请求为<K，AcceptVx>）发送给Acceptor。
c）Proposer没有收到过半Acceptor发来的回复，则修改议案编号K为K+1，并将编号重新发送给Acceptors（重复Prepare阶段的过程）
d）Acceptor收到Proposer发来的Accept请求，如果编号K<MaxN则不回应或者reject。
e）Acceptor收到Proposer发来的Accept请求，如果编号K>=MaxN则批准该议案，并设置手里批准的议案为<K，接受议案的编号，接受议案的内容>，回复Proposer。
f）经过一段时间Proposer对比手里收到的Accept回复，如果超过半数，则结束流程（代表议案被批准），同时通知Leaner可以学习议案。
g) 经过一段时间Proposer对比手里收到的Accept回复，如果未超过半数，则修改议案编号重新进入Prepare阶段。
场景
先后提议的场景
角色：
proposer：参谋1，参谋2
acceptor：将军1，将军2，将军3（决策者）
1）参谋1发起提议，派通信兵带信给3个将军，内容为（编号1）；
2）3个将军收到参谋1的提议，由于之前还没有保存任何编号，因此把（编号1）保存下来，避免遗忘；同时让通信兵带信回去，内容为（ok）；
3）参谋1收到至少2个将军的回复，再次派通信兵带信给3个将军，内容为（编号1，进攻时间1）；
4）3个将军收到参谋1的时间，把（编号1，进攻时间1）保存下来，避免遗忘；同时让通信兵带信回去，内容为（Accepted）；
5）参谋1收到至少2个将军的（Accepted）内容，确认进攻时间已经被大家接收；
6）参谋2发起提议，派通信兵带信给3个将军，内容为（编号2）；
7）3个将军收到参谋2的提议，由于（编号2）比（编号1）大，因此把（编号2）保存下来，避免遗忘；又由于之前已经接受参谋1的提议，因此让通信兵带信回去，内容为（编 号1，进攻时间1）；
8）参谋2收到至少2个将军的回复，由于回复中带来了已接受的参谋1的提议内容，参谋2因此不再提出新的进攻时间，接受参谋1提出的时间；
交叉场景
角色：
proposer：参谋1，参谋2
acceptor：将军1，将军2，将军3（决策者）
1）参谋1发起提议，派通信兵带信给3个将军，内容为（编号1）；
2）3个将军的情况如下
a）将军1和将军2收到参谋1的提议，将军1和将军2把（编号1）记录下来，如果有其他参谋提出更小的编号，将被拒绝；同时让通信兵带信回去，内容为（ok）；
b）负责通知将军3的通信兵被抓，因此将军3没收到参谋1的提议；
3）参谋2在同一时间也发起了提议，派通信兵带信给3个将军，内容为（编号2）；
4）3个将军的情况如下
a）将军2和将军3收到参谋2的提议，将军2和将军3把（编号2）记录下来，如果有其他参谋提出更小的编号，将被拒绝；同时让通信兵带信回去，内容为（ok）；
b）负责通知将军1的通信兵被抓，因此将军1没收到参谋2的提议；
5）参谋1收到至少2个将军的回复，再次派通信兵带信给有答复的2个将军，内容为（编号1，进攻时间1）；
6）2个将军的情况如下
a）将军1收到了（编号1，进攻时间1），和自己保存的编号相同，因此把（编号1，进攻时间1）保存下来；同时让通信兵带信回去，内容为（Accepted）；
b）将军2收到了（编号1，进攻时间1），由于（编号1）小于已经保存的（编号2），因此让通信兵带信回去，内容为（Rejected，编号2）；
7）参谋2收到至少2个将军的回复，再次派通信兵带信给有答复的2个将军，内容为（编号2，进攻时间2）；
8）将军2和将军3收到了（编号2，进攻时间2），和自己保存的编号相同，因此把（编号2，进攻时间2）保存下来，同时让通信兵带信回去，内容为（Accepted）；
9）参谋2收到至少2个将军的（Accepted）内容，确认进攻时间已经被多数派接受；
10）参谋1只收到了1个将军的（Accepted）内容，同时收到一个（Rejected，编号2）；参谋1重新发起提议，派通信兵带信给3个将军，内容为（编号3）；
11）3个将军的情况如下
a）将军1收到参谋1的提议，由于（编号3）大于之前保存的（编号1），因此把（编号3）保存下来；由于将军1已经接受参谋1前一次的提议，因此让通信兵带信回去，内容为（编号1，进攻时间1）；
b）将军2收到参谋1的提议，由于（编号3）大于之前保存的（编号2），因此把（编号3）保存下来；由于将军2已经接受参谋2的提议，因此让通信兵带信回去，内容为（编号2，进攻时间2）；
c）负责通知将军3的通信兵被抓，因此将军3没收到参谋1的提议；
12）参谋1收到了至少2个将军的回复，比较两个回复的编号大小，选择大编号对应的进攻时间作为最新的提议；参谋1再次派通信兵带信给有答复的2个将军，内容为（编号3，进攻时间2）；
13）将军1和将军2收到了（编号3，进攻时间2），和自己保存的编号相同，因此保存（编号3，进攻时间2），同时让通信兵带信回去，内容为（Accepted）；
14）参谋1收到了至少2个将军的（accepted）内容，确认进攻时间已经被多数派接受。
