Paxos！有没有高端大气上档次！实际上，算法过程很是接地气，没有复杂的计算过程，没有炫酷的数据结构。可以说，算法的推导过程，就是摆事实将道理的过程，合情合理。
需求场景
假如项目需要一个数据中心，我们有一台装了mySQL的机器。哈！完成了！数据中心！当然这是不可能的，各种突发问题（硬盘烧坏，机器异常宕机）都可能造成数据中心不可用，甚至是数据丢失。自然而然的，我们可以引入多台机器，一主多备，这样一台机器挂了，备用机器就可以拉起来用。当然，要保证备用机器数据正确，即保证备用机器拉起来用的时候，数据状态完全与最新的一致。如何尽可能好的做到这一点，就是Paxos算法的应用场景。
一致性算法
问题描述。首先，让我们忘记上面的内容，从基础过程说起。假设很多机器可以提案数值。一致性算法保证只有一个被提案的数值最终被选中。如果一个值被选中，那么所有机器可以学习到这个值。于是，我们说的一致性就可以拆分如下：
只有被提案的数值可能被选中
只有一个数值被选中
当某个值被选中，机器才能学习到这个值
在这个一致性算法中，我们设置了三种角色：提案者、决策者、学习者。每台机器都可以扮演多个角色。当然，每台机器可以互相通信。我们假设通信过程是异步的，不考虑拜占庭模型的：
通信传输速度是任意的，可以有机器宕机、重启等造成的失败。当然机器需要有存储。
消息可以很慢很慢才到达另一台机器，可以重复，可以丢失，但不能有假消息错误消息（没有坏人啊）。
如何选择一个值。可以想象，最简单的模型就是只有一个决策者。一个提案者像这个决策者发起一个提案，决策者决定选择他最先看到的提案的值。但缺点很明显，一旦这个决策者挂了，整个系统就挂掉了。
所以要说多个决策者。一个提案者向这些决策者发送提案，当多数决策者接受这个提案后，就可以认定系统选择了这个值。不考虑异常情况，为了保证某个值被选中，可以这样指定约束：
P1. 决策者必须接受他看到的第一个提案。
但是这会引起一个问题。例如有偶数个决策者，有两个提案者分别发送了不同的提案，刚好各一半的决策者分别接受了两个提案，这就尴尬了。P1和“多数决策者接受的提案被选中”约束意味着，一个决策者必定允许接受多个提案。
我们通过给不同提案者的提案附上编号来记录不同的提案。也就是说一个提案由，一个提案编号和提案数值组成。上面我们允许一个决策者接受多个提案，但是我们必须保证所有被选中（被大多数决策者接受）的提案值一致。为了这个目的，我们可以再指定一个约束：
P2. 如果一个提案被选中，那么被选中的更大编号的提案的提案值，必须跟最初被选中的提案值一样。
只有被至少一个决策者接受，一个提案才可能被接受。所以我们可以通过满足下述约束满足P2：
P2a. 如果一个提案被选中，那么被决策者接受的更大编号的提案的提案值，必须跟最初被选中的提案值一样。
这是一个更强的约束，选中 --> 接受。狡猾的提案者可以发现这里的一个漏洞，P1要求决策者必须接受他看到的第一个提案，假如一个决策者一直神游天外，很久很久之后第一次看到一个提案，而这个提案值与已被选中的提案值不一样，他也许就会郁闷而宕机。因此，我们可以再一次强化P2a约束：
P2b. 如果一个提案被选中，那么被提案者提出的更大编号的提案值，必须跟最初被选中的提案值一样。
那么又如何满足P2b呢？提案者需先向决策者们询问，是否某个提案被选中，选中了呢这个提案者就只能提案这个值，若提案者新提案可能被选中呢，则他可以提案新值：
P2c. 一个编号为n值为v的提案被提出，需要满足：存在一个包含多数决策者的集合S，要么他们都没接受过编号小于n提案（下面说明为什么只约束小于n），要么他们接受的编号小于n的提案中最大编号的提案值是v。
这就形成了一个包月约束P2b的更强的约束。上面提到，提案者要先向决策者们询问，并且要判断新的提案是否可能被接受，单纯的预测未来是困难的。但是我们可以让决策者们作出承诺，当提案者询问时带着编号n，决策者们承若不再接受编号小于n的提案。这样，提案过程可以如下描述：
一个提案者构造了一个新提案（编号n），发送预备请求到所有决策者，希望得到如下回应：
一个不再接受编号小于n的提案的承诺
如果接受过提案，同时恢复编号小于n中编号最大的提案的内容
当提案判断有多数决策者没有接受过小于n的提案时，提案者可以任意提案；当提案者判断有多数决策者恢复的提案内容跟自己的一样时，他可以发起这个提案。随即可以发送接受请求。
决策者做出过承诺，承诺接受预备请求后不再接受编号小于n的提案。也即：
P1a. 决策者收到一个提案（编号k），只有当决策者没有回复于编号大于k的预备请求时，才可以接受它。
这是一个包含P1的约束。把提案者和决策者的行为放在一起，可以看到整个算法的过程分为下述两个阶段（啪啪啪！拍黑板！这是重点！！！）：
第一阶段：
一个提案者构造一个提案（编号n），先发送预备请求。
决策者收到一个预备请求，如果这个预备请求的编号n，比他已经回复的预备请求的编号大（没回复过当然可以回复这个），那么久回应它，承诺不再接受小于该编号的任何提案，附带已接受提案中编号最大的提案值（没接受过则不带）。
第二阶段：
如果这个提案者收到回复，判断有多数决策者没有接受过小于n的提案时，提案者可以任意提案；当提案者判断有多数决策者恢复的提案内容跟自己的一样时，他可以发起这个提案。随即发送接受请求。
决策者收到一提案编号n（这个接受请求），接受它，除非期间回复过编号大于n的预备请求。
如何学习一个值。我们有一些学习者需要学习到最终的选中结果。简单的，每当一个决策者接受一个提案，则发消息到所有学习者，但是这样请求量太大；相对的，可以只发给一个预先指定的学习者，由改学习者再转发给其他学习者，当然，这样可靠性又有损失。折中，我们可以指定几个学习者，由这几个学习者判定一致提案被选中后，再发送给其他学习者。
预备请求的冲突。想象一个场景，两个提案者都发起预备请求，他们都能在对方发起接受请求前发起更大编号的预备请求，这个算法过程也就在这里锁住了。为了解决这个问题，可以事先进行选举leader，只有这个leader在冲突时可以尝试重试发起预备请求。具体选举过程请参考Lamport在The Part-Time Parliament一文中描述。
好了，以上就是基本Paxos算法的全部内容了，是不是合乎情理呢？
简单应用
现在我们回到最开始提到的需求场景中，尝试用最简单的方式应用Paxos算法。还是数据中心，假如我们搞了5台机器，一主4备。数据数据库系统的同学可以知道，数据库的变化是由一条条SQL执行产生的，也就是说如果最初的5台数据一致，那么相同顺序执行相同的SQL，那么他们最终的数据也应该是一致的。
第一个SQL语句到了主机，主机通过Paxos算法发起请求给备机，备机们现在是决策者与学习者，通过一个Paxos算法实例，记录第一次应该执行这条SQL。当有2台备机回复接受后，主机就可以返回客户端执行完毕的应答了，因为Paxos嘛。之后，每次主机收到SQL，每一条SQL都对应一个Paxos实例，同时Paxos实例编号，这样可以知道SQL的执行顺序。
当主机挂掉了，备机们可以通过一次Paxos发起选举，竞选成为主机，之后根据本地存储的Paxos实例的情况，向其他备机们学习自己漏掉的SQL，补全至与挂掉主机最近的状态，继续服务。
OK，that's all！我理解的Paxos算法。
还没有评论，来说两句吧...