上一章接头了一种强一致性的环境，即需要漫衍式事务来办理，本章我们来接头一种最终一致的算法，paxos算法。

paxos算法是由大牛lamport发现的，关于paxos算法有许多趣事。好比lamport论文最初由故事描写来引入算法，以至于那班习惯数学公式的评委将该论文打回，导致该论文耽搁了8年才果真颁发。别的，google的chubby的作者Mike Burrows说过，世界上只有一种一致性算法，那就是paxos。

两将军问题

为了引入该算法，首先提出一种场景，即两将军问题（见文献1）：

有两支部队，它们别离有一位将军率领，此刻筹备进攻一座修筑了防止工事的都市。这两支部队都驻扎在那座都市的四周，分占一座山头。一道山谷把两座山脱离开来，软件开发，而且两位将军独一的通信方法就是派各自的信使交往于山谷双方。不幸的是，这个山谷已经被那座都市的守卫者占领，而且存在一种大概，那就是任何被派出的信使通过山谷是会被捕。 请留意，固然两位将军已经就进攻那座都市告竣共鸣，但在他们各自占领山头阵地之前，并没有就打击时间告竣共鸣。两位将军必需让本身的部队同时打击都市才气取得乐成。因此，软件开发，他们必需相互相同，以确定一个时间来进攻，并同意就在当时进攻。假如只有一个将军举办进攻，那么这将是一个劫难性的失败。

两将军问题本质上就是通信被改动时可否办理一致性问题。这个问题已经被许多人证明不能。（见文献1）。因而由此推及的拜占庭将军问题（多将军问题）也同样不能被办理。

PAXOS算法

一个叫做Paxos的希腊城邦，这个岛凭据议会民主制的政治模式制订法令，可是没有人愿意将本身的全部时间和精神放在这种工作上。所以无论是议员，议长可能通报纸条的处事员都不能理睬别人需要时必然会呈现，也无法理睬核准决策可能通报动静的时间。可是这里假设没有拜占庭将军问题（Byzantine failure，即固然有大概一个动静被通报了两次，可是绝对不会呈现错误的动静）；只要期待足够的时间，动静就会被传到。别的，Paxos岛上的议员是不会阻挡其他议员提出的决策的。

这里不再赘述算法的推导及证明进程，参考文献2和3。这里简朴描写下算法领略。

根基思想也是两阶段提交。可是与两阶段目标差异。

1. 第一阶段主要目标是选出提案编号最大的proposer。

其描写如下，所有的proposer向高出半数的acceptor提出编号为n的提案，acceptor收到编号为n的请求，会呈现两种环境

a. 编号n大于所有acceptor之前已经核准过的proposal的最大编号及内容m。acceptor同意该proposal，响应[n, m]回proposer，而且理睬此后不再核准任何编号小于n的提案。

b. 编号n小于acceptor之前核准过的任意proposal的编号。acceptor拒绝该proposal。

2. 第二阶段实验对某一proposal告竣一致。
proposer收到高出半数的acceptor返回的响应，proposer就会将响应的最大编号[n, m]对应的提案提交到acceptor要求acceptor核准该提案。

acceptor收到最大编号[n, m]的提案，也分为两种环境

a. 未响应过编号大于n的prepare请求。通过该提案。

b. 已响应过编号大于n的prepare请求。拒绝该提案。

整个算法外貌上并不难领略，难在实现细节的难易水和善各类异常环境的推导及思量。假如对上述算法有领略坚苦的，参考文献4和文献5的例子，个中文献5更容易领略，这里 把他的图贴出来，实际进程就不再反复赘述了。

两个照料先后提议的场景：

两个照料交错提议的场景：

需要留意的是照料1在失败时再次提倡请求的进程。

这里着重强调几个重点：

1. 算法描写里有好几个处所要求投票必需高出半数，这个高出半数恰恰是担保一致的一个须要条件；
2. 算法里也有多处要求只选择编号最大的，这种选择编号最大的方法，是一种最为简朴经济的告竣共鸣的要领，可以或许快速在多个斗嘴中找到一个打破口；
3. paxos算法的要害是，假如一个值m被选中了，那么必需担保更高的proposal其值也为m；
4. 留意第一阶段较量的是已经核准过的proposal的最大编号，而第二阶段较量的是prepare请求。即第一阶段较量的是第二阶段的功效，而第二阶段较量的是第一阶段的功效，看似很绕，实际上正好是断绝了阶段外的担保，进入第一阶段的我要担保他是新的开始，跟上一阶段没啥干系，软件开发，而进入第二阶段的我要担保他是从前面阶段来的，而不是新起的一个阶段，有点像是断绝锁，锁住了阶段一到阶段二这个进程。