知识要点:
Paxos协议详解
Paxos协议理解示例
Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos,其它的算法都是残次品。
一致性协议的重要性
为保证分布式系统的高可靠和高可用性，数据在系统中一般存储多个副本。当某个副本所在的节点出现故障时，分布式系统能够自动将服务切换到其他的副本，从而实现自动容错。同-份数据的多个副本中往往有一
个副本为主副本，其他为备副本。从一份数据的角度讲，主副本所在的节点为主节点，备副本所在的节点为备节点。但在整个系统范围上看，每个节点即是主节点，也是备节点。
一致性解决方案
■2PC/3PC
■Paxos
■Raft (RAFT协议)
Paxos协议详解
拜占庭将军问题
Lesle Lamport教授在三十多年前发表了论文《拜占庭将军问题》
拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现不可预料的行为。
拜占庭是5~15世纪的东罗马帝国，拜占庭即现在土耳其的伊斯坦布尔。我们可以想象，拜占庭军队有许多分支，驻扎在敌人城外，每一分支由各自的将军指挥。将军们只能靠通讯员进行通讯。在观察敌人以后，忠诚
的将军们必须制订一个统-的行动计划一进攻或者撤退。 然而，这些将军中有叛徒，他们不希望忠诚的将军们能达成一致，因而影响统一行动计划的制订与传播。
问题是:将军们必须有一个协议,使所有忠诚的将军们能够达成一致，而且少数几个叛徒不能使忠诚的将军们作出错误的计划一使有 些将军进攻而另一些将军撤退。 如果这1 1位将军中有间谍呢?
假设:
有9位忠诚的将军，5位判断进攻，4位判断撤退，还有2个间谍恶意判断撤退，虽然结果是错误的撤退，但
这种情况完全是允许的。因为这1 1位将军依然保持着状态一致性。
Lamport.一直研究这类问题发表了一系列论文,但总结一下就是下面三个问题:
■类似拜占庭将军这样的分布式- 致性问题是否有解?
■如果有解的话需要满足什么样的条件?
■在特定前提条件的基础上，提出一种解法(Paxos)
Paxos背景故事
故事发生在一个商业繁荣、政治清明的小岛(Paxos)，这里建立了政府国会取代了之前的神权政治。小岛上所有法令(Decress)都由议会的议员(Legislator)表决通过,然后由议员记录在各自手中的律薄(Ledgen上。
但是由于这里商业繁荣，没有人愿意做专职的议员，都是由小岛居民兼职的。由于平时工作很忙，所以兼职议员们会经常进出国会大厅，甚至中途去出海捕鱼，半年后再回到国会大厅。
好在兼职议员们相互高度信任,所有提议都会被通过，不会有人反对。并且,兼职议员们只要待着议会厅，总会积极的完成工作。
附:《Paxos小岛的故事》
Paxos协议设定
三种角色:
■Proposer: 提交者(议案提交者) 提交议案(判断是否过半)，提交批准议案
■Acceptor: 接收者(议案接收者) 接受议案或者驳回议案，给proposer回应(promise)
■Learner:学习者(打酱油的)如果议案产生，学习议案。
条件设定:
■设定1:每个议案比必须有一个编号，并且编号只能增长，不能重复。越往后越大。
■设定2:议案有2种(提交的议案，批准的议案)
■设定3:如果Acceptor没有接受任何议案，那么他必须接受第一个议案
■设定4: 接受编号大的议案，如果小于之前接受议案编号，那么不接受
Paxos详解
K=议案编号V=议案内容
议员对于一个提交的议案: 0K=接受, error|reject= 不接受|驳回 Prepare阶段(提交阶段，只提交议案编号)
- Proposer希望议案V。 首先发出Prepare请求至大多数Acceptor. Prepare请求内容为序列号K;
-
Acceptor收到Prepare请求为编号K后， 检查自己手里是否有处理过Prepare请求;
3)如果Acceptor没有接受过任何Prepare请求，那么用OK来回复Proposer,代表Acceptor必须接受收
到的第一个议案;
4)否则， 如果Acceptor之 前接受过任何Prepare请求(如: MaxN)，那么比较议案编号，如果
K <MaxN,则用reject或者 error回复Proposer; :
5)如果K>=MaxN, 那么检查之前是否有批准的议案，如果没有则用OK来回复Proposer,并记录K;
6)如果K>=MaxN, 那么检查之前是否有批准的议案,如果有则回复批准的议案编号和议案内容(如:<AcceptN, AcceptV>，AcceptN为批准的议案编号， AcceptV为批准的议案内容)。
Accept阶段(批准阶段)
- Proposer收到过半Acceptor发来的回复， 回复都是OK,且没有附带任何批准过的议案编号和议案内容。那么Proposer继续提交批准请求，不过此时会连议案编号K和议案内容V-起提交(<K, V>这种数据形式)
- Proposer收到过半Acceptor发 来的回复，回复都是OK,且附带批准过的议案编号和议案内容(<pok,议案编号,议案内容>)。那么Proposer找到所有回复中AcceptN最大的那个AccpetV (假设为<pok, AcceptNx, AcceptVx>) 作为提交批准请求(请求为<K, AcceptVx>)发送给Acceptor.
- Proposer没有 收到过半Acceptor发来的回复，则修改议案编号K为Kx,并将编号重新发送给Acceptors (重复Prepare阶段的过程)
- Acceptor收到Proposer发 来的Accept请求，如果编号K <MaxN则不回应或者reject.
- Acceptor收到Proposer发来的Accept请求， 如果编号K> =MaxN则批准该议案，并设置手里批准的议案为<K,接受议案的编号，接受议案的内容>，回复Proposer.
6)经过一段时间Proposer对比手里收到的Accep回复，如果超过半数，则结束流程(代表议案被批准)，同时通知Leaner可以学习议案。
7)经过一 段时间Proposer对比手里收到的Accept回复，如果未超过半数，则修改议案编号重新进入Prepare阶段。
Paxos手绘流程图
Paxos协议算法理解示例
先后型
角色
■proposer:参谋1,参谋2 (提议者)
■acceptor:将军1,将军2，将军3 (决策者)
■目的:确定进攻时间
流程解析
1.参谋1发起提议,派通信兵带信给3个将军，内容为(编号1) ;
2.三个将军收到参谋 1的提议，由于之前还没有保存任何编号，因此把(编号1)保存下来，避免遗忘;同时让通信兵带信回去，内容为(ok) ;
- 参谋1收到至少2个将军的回复，再次派通信兵芾信给3个将军，内容为(编号1,时间1) ;
4.三个将军收到参谋1的时间， 把(编号1,时间1)保存下来，避免遗忘;同时让通信兵带信回去，内容为(Accepted) ;
5.参谋1收到至少2个将军的 (Accepted) 内容，确认进攻时间已经被大家接收; "
6.参谋2发起提议，派通信兵带信给3个将军，内容为(编号2) ;
7.》3个将军收到参谋2的提议，由于(编号2)比(编号1)大，因此把(编号2)保存下来，避免遗忘;又由于之前已经接受参谋1的提议，因此让通信兵带信回去，内容为(编号1, 时间1) ; - 参谋2收到至少2个将军的回复， 由于回复中带来了已接受的参谋1的提议内容，参谋2因此不再提出新的进攻时间，接受参谋1提出的时间。
交叉型
角色
■proposer:参谋1,参谋2 (提议者)
■acceptor:将军1,将军2，将军3 (决策者)
■目的: 确定进攻时间
流程解析
1 参谋1发起提议,派通信兵带信给3个将军，内容为(编号1) ;
2三个将军的情况如下
■将军1和将军2收到参谋1的提议，将军1和将军2把(编号1)记录下来，如果有其他参谋提出更小的编号，将被拒绝;同时让通信兵带信回去，内容为(ok) ;
■负责通知将军3的通信兵被抓，因此将军3没收到参谋1的提议;
3参谋2在同一 时间也发起了提议,派通信兵带信给3个将军，内容为(编号2) ;
4三个将军的情况如下
■将军2和将军3收到参谋2的提议，将军2和将军3把(编号2)记录下来，如果有其他参谋提出更小的编号，将被拒绝;同时让通信兵带信回去，内容为(ok) ;
■负责通知将军1的通信兵被抓，因此将军1没收到参谋2的提议;
5参谋1收到至少2个将军的回复，再次派通信兵带信给有答复的2个将军，内容为(编号1,时间1) ;
6两个将军的情况如下
■将军1收到了(编号1,进攻时间1)，和自己保存的编号相同，因此把(编号1,时间1)保存下来;同时让通信兵带信回去，内容为(Accepted) ;
■将军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三个将军的情况如下
■将军1收到参谋1的提议， 由于(编号3)大于之前保存的(编号1)，因此把(编号3)保存下来;由于将军1已经接受参谋1前一次的提议，因此让通信兵带信回去，内容为(编号1,时间1) ;
■将军2收到参谋1的提议，由于(编号3)大于之前保存的(编号2) ,因此把(编号3)保存下来;由于将军2已经接受参谋2的提议，因此让通信兵带信回去，内容为(编号2，时间2) ;
■负责通知将军3的通信兵被抓，因此将军3没收到参谋1的提议;
12参谋1收到了至少2个将军的回复，比较两个回复的编号大小，选择大编号对应的进攻时间作为最新的提议;参谋1再次派通信兵带信给有答复的2个将军，内容为(编号3,时间2) ;
13将军1和将军2收到了/ (编号3,时间2) ,和自己保存的编号相同，因此保存(编号3,时间2)，同时让通信兵带信回去，内容为(Accepted) ;
14参谋1收到了至少2个将军的(Accepted) 内容， 确认进攻时间已经被多数派接受。
