参考文献：Lamport L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.
一、Paxos简介
Paxos是Lamport提出的最著名的基于消息传递的一致性算法，在2006年Google将其运用于Chubby锁服务器上后便受到了巨大的关注。Paxos Made Simple这篇论文中Lamport用了比较通俗的叙述方式来讲解了Paxos这个模型，也是Paxos的基础版本，支持单提案的达成一致与提交。
在这个模型中进程一共有三种角色，分别是
- 提案者(Proposers)
- 接受者(Acceptors)
- 学习者(Learners)
而每一个进程不限于一种角色。
Paxos一共分为两个阶段(Phrase)，分别是
- 提案阶段
在这个阶段内，提案者会向接受者发送准备请求(ready request)，准备请求中带有一个编号n。 - 接受阶段
在提案阶段一个提案者收到了超过半数的接受着返回的准备请求的应答，那么提案者将会向回复他的接受者发送一个带有编号n以及提案的接受请求(accept request)。
这篇笔记将会介绍Paxos如此设计的思路以及过程的详细细节，后面还会将Paxos与近几年比较火的另一种一致性算法Raft进行简单的比较。
二、要求与假设
Paxos是一个一致性算法，而一致性算法的目标是让所有的进程最终都能够对提案达成一致。所以实现Paxos的最终效果是若没有提出一个提案，那么就不会有提案被选中，而若有提案被提出，那么最终只有一个提案会被选中。文中提到了三个一致性的安全性(safety)需求：
- 只有提出的提案能最终能被选中
- 只有一个提案能被选中
- 除非一个提案真的被选中了，否则进程不会选择这个提案
而系统的活性(liveness)则是某些提出的提案最终能被选中，并且进程最终能够学到这个提案。
文章讨论基于以下几个假设：
- 每个实体的执行速度不同，甚至会在任何时候崩溃、重启。因为有可能在提案选择后失效，因此想要得到一个解，必须要实现持久化某些信息。
- 消息传递的事件可以任意长，可以重复或丢失，但不会被破坏(无拜占庭问题)。
三、选择提案
要保证上述的只有一个提案被最终选中的要求，同时保证系统的鲁棒性，那么需要做到一个提案能够被超过半数的接受者(majority)接受，因为无法找到两个majority能够接受不同的提案，只有所有进程都遵守这一规则，才能最终只有一个提案被选中。而要保证一定要有一个提案被选中，接受者应该对第一个提案进行接受。如果只有一个提案被提出却不接受，就无法得到majority，这就得到了第一个需求：
P1. 接受者必须接受它所接收到的第一个提案
但是这个要求在有两个或更多提案的时候可能会得不到一个majority，所以每个进程不能仅被允许接收这一个提案。于是每个提案除了要带有一个值(value)以外，还要带上一个互不相同的数(number)来区分它们。这样一来就可以允许选择多个不同的提案了。但是由于最终选出的提案的值必须唯一，所以要添加另外一个条件：
P2. 如果值为v的提案被选择了，那么所有被选择的数更大的提案的值也是v
由于提案的值被选中，那么这个提案一定要被某些接受者接受，所以P2的可以改写为
P2a. 如果值为v的提案被选择了，那么所有被任何一个接受者接受的数更大的提案的值也是v
但是还存在这样一种情况，有些接受者(c)还没有接受到任何的提案，但是这时一个新的数更大但值不同提案被提出且被发送给了c，由于P1的要求，c必须接受这个提案，那么这样一来就违反了P2a，所以P2a还应该进一步修改为：
P2b. 如果值为v的提案被选择了，那么任何一个提案者提出的数更大的提案的值也是v
根据提出-接受-选中的因果关系，可以得出P2b -> P2a -> P2，而要具体实现P2b，只需要满足另一个变体
P2c. 如果提出了一个值为v，数为n的提议，那么一定存在一个接受者majority集合S，满足下面的其中一个条件
- S内不存在任何接受过数小于n的提案
v是S中接受者接受的数小于n的最大数提案的值v
为了维护P2c，提案者在提出数为n的提案的时候就需要去学习当前不大于n的最大数提案的值，这些提案有的已经被接受，有的还没被接受。如果已被接受的话，那么就直接让接受者告知提案者就行。如果还未接受，那就会造成困难，因为提案者无法预测未来。所以文中又做了一个限制，那就是提案者会请求接受者不再去接受那些数小于自己提案的数的提案。
而接受者这边，只要不违背安全性要求的请求都可以回复，也就是接受者可以回复所有的准备请求，除了前面承诺过的不再接受的提案的接受请求以外的其他请求也都可以回复，这就可以提出一个比P1更强的需求：
P1a. 接受者可以接受一个数为n的提案，当且仅当接受者只要没有回复过大于n的准备请求
这里还有一些隐含的优化可以做，那就是虽然接受者可以回复一个数小于当前已经回复过的最大为n准备请求，但是这个没有必要，因为最终接受者也不会接受后续的接受请求，所以接受者可以直接忽略这样的请求。同时，对于已经和接受的提案相同的准备请求，也不予以回复。
要做这些优化，接受者也只需要记住两个变量，一个是当前已经回复过的最大的准备请求以及已经接受的数最大的提议。第一个用来确定是否要回复一个准备请求以及是否要接受一个提案，第二个用来告知后面更大数的提议者去修改自己的提议。
综合上面的推导，就可以合理地提出Paxos提出并一致通过提案的算法流程了：
Phase1.
- 提案者要提出一个提案，赋予数n和值v，那么他将向至少过半数的(majority)接受者发送准备请求(prepare request)
- 接受者受到准备请求后，只要这个请求中的数n大于自己曾经回复过的最大的数，那么就向提案者发送回复信息，回复中包含两个内容
- 向提案者承诺不再接受小于n的提案
- 如果已经接受过提案，则把已经接受过的提案的值v返回给提案者
Phase2.
- 如果提案者收到了半数以上接受者对自己数为n的准备请求的回复，那么就可以向这些接受者发送自己的提案(n, v)，v要根据接受者的回复进行修改。如果接受者的回复中带有曾经接受过的提案的值，那就改成这个值，否则就按照原来提出的值v
- 接受者如果在这段事件内没有回复其他的准备请求(其他提议者提出了n更大的提议，改变了这个接受者记录的最大回复值)，那么就可以接受这个提案。
只要遵守上面的流程，就可以保证算法的正确性，提案者可以在任何时候废除自己的提案。作为优化，提案者可以在得知已经有n更大的提案提出时放弃自己现在的提案。
四、学习被选择的值
上面一个章节主要是一个提案提出后要如何得到一致通过，就像是一个公司的董事会对一个方案进行讨论，当得出最终结果或是得到半数董事通过后，就要讲这个最终结果通知给下面的员工。在Paxos模型中，学习者(learner)就扮演着员工这样一个角色。文中提出了三种不同的由接受者将通过的提案通知学习者的方案。
- 第一种方法最简单，接受者在接受提案后，立即将自己接受的提案广播给所有的学习者。但是这么做，会产生大约n_{acceptor} * n_{learner}的信息量，信息量过大。所以要进行一定的优化，减少网络负载。
- 第二种方案是将方案都发送给指定的单个学习者，再由这个学习者转发给所有其他的学习者(不存在拜占庭问题)来避免不必要的信息量，这样一来就可以将复杂度降至比较理想的n_{acceptor} + n_{learner}，但这种方案容易产生单点失效的问题，单个学习者一旦失效后，所有的学习者都无法直到通过的提案。
- 最后一种是前两种方案的折中，接受者将自己的方案发送给一个特定集合S的学习者，然后由这个集合中的学习者将结论转发给其他的学习者，这个方法会在方案二的基础上带来| S |倍的复杂度提升，但是却可以大大提高可靠性。
以上就是对Paxos算法的理解与讨论，可以看出Paxos算法设计的极为简洁，但却极为有效，这也是它能够逐渐被人们接受并流行的原因。然而这只是Paxos的Basic版，比较偏向理论，对于实现的讨论比较少，后续以此为基础还提出了很多优化和增强的版本。下一篇将会介绍近几年比较流行的一个算法Raft。