本文新版本： Paxos Made Simple（完整翻译），结合了自己的理解。
第一部分：原文粗略翻译
1.Introduction
用来实现容错的分布式系统的Paxos算法被认为是难以理解的，大部分原因是因为作者在原始的论文中【Leslie Lamport. The part-time parliament. ACM Transactions on ComputerSystems, 16(2):133–169, May 1998.】使用了希腊城邦等这些与计算机相差比较远的故事来描述该算法。实际上该算法的核心就是一个一致性算法。下文中将展示这个一致性算法不可避免的需要满足我们想要其满足的属性/特点。文献【Leslie Lamport. Time, clocks, and the ordering of events in a distributedsystem. Communications of the ACM, 21(7):558–565, July 1978.】是分布式系统学习者都该了解的。
2.一致性算法
2.1 问题
假设一组进程可以用来提出不同的值（例如在数据库系统中，不同的事务可能对同一个表格中的同一行中的同一个元素进行更新，而且这些事务所修改的值也不相同）。一致性算法就是用来保证仅有一个进程/事务所提出的值能够被选中（这里的仅有一个我想可能是说每次更新表格元素时仅有一个值被选中，不同的值可能在下一次更新时被选中）。如果没有值被提出，那么就没有值被选中。如果某个值被选中，那么这些进程应该能够学习到被选中的值。（即被选中的值最终会被所有进程学习到），（这里的一下描述时为了形式化/逻辑推理的需要，如果有兴趣可以看一下Leslie Lamport的关于动作时序逻辑的书TLA+，改书是关于分布式算法的形式化说明以及正确性验证的。个人觉得做分布式系统相关的很有必要学一下，真的很有必要。对算法设计的建模和逻辑性思考能力有提升帮助。书中有关于Liveness和Safety的定义以及说明。）该一致性算法的安全性要求如下：
（1）仅有一个被提议的值可以被选中。
（2）仅有一个值被选中，且
（3）一个进程不可能学习到一个被选中的值，除非这个值真的被选中。
这里作者不想说明算法的详细Liveness特性的要求。Liveness属性的目的大致就是为了保证某些被提议的值最终能够被选中，且，如果一个值被选中，那么一个进程最终能够学到这个被选中的值。（这里的最终（eventually）在上述的TLA+中是一种时序逻辑，Liveness笼统的含义就是“某些好的事情最终能够发生”，Safety的笼统含义就是“某些坏的事情一定不会发生”）。
文中用三种代理（即名称）来表示算法中三种不同的进程角色：proposer，acceptor和learner。在具体的工程实践中一个进程可能同时具有三种角色，这不会影响算法的正确性，但这里作者不关心这个情况。我们可以认为一个进程仅有一个角色。
假设进程间可以通过消息传递来进行通信（大多数分布式算法/协议的通信模型都是基于消息传递）。文中基于的通信模型是异步的、非拜占庭模型【The Byzantine Generals Problem】，其中：
（1）每个Agent/角色以任意的速度处理事务，可能失败并停止，也可能重启。因为所有的进程可能在一个值被选出后失败并重启，那么失败重启前已知的信息需要被保存，使得在重启后仍保留之前已知的信息。
（2）消息传递的时间可能很长，消息可能被重复发送，消息可能丢失，但是消息的内容不会被篡改。
2.2 选出一个值Value
一个最简单的选值的办法就是仅仅使用一个acceptor agent（集中式）。一个proposer发送一个proposal给acceptor，acceptor选择第一个接收到的proposal中的value。虽然简单，但是该方法会存在单点故障：这个acceptor失效后，无法进行下面的操作。
因此作者使用了另一种方法，也就是分布式的方法。在系统中使用多个acceptor。一个proposer可以向一组acceptor发送proposal（问题一：这里的一组是所有的acceptor还是其中的一部分？）。一个acceptor可能接受proposer发送的proposal（意味着也可能不接受/决绝）。一个proposal中的value被选中的条件是：大部分的aceptor接受了该proposal。大部分指的具体数量是多少呢？大部分就是指的大多数（超过一半的数量，假设一个proposer将一个proposal发送给n个acceptor，那么这里的大多数就是指超过n/2个acceptor。由此可知，n最好是奇数）。这样就能保证任意两拨接收了proposal的acceptor之间存在至少一个相同的acceptor，也就保证了这两拨acceptor接收的是同一个proposal。关于大多数的选择具体可以参考文献【Idit Keidar and Sergio Rajsbaum. On the cost of fault-tolerant consensus when there are no faults—a tutorial. TechnicalReport MIT-LCS-TR-821,Laboratory for Computer Science, Massachusetts Institute Technology,Cambridge, MA, 02139, May 2001. also published in SIGACT News 32(2) (June 2001).】
在这我们假设大多数这个约束条件为rule 1：
R1：大多数acceptor接受了某个值后，该值才算被接受。
在没有进程失效或者消息丢失的情况下，我们想要选择一个value就需要当仅有一个proposer提出一个value时，acceptor就要选中这个value。这需要我们的算法满足如下的条件：
P1：一个acceptor需要接受/同意其第一次收到的proposal中的value。
这个条件是保证被提出的proposal能够被接受。但是这存在一个问题，不同的proposer可能提出不同的proposal且proposal中的value都不一样。极端的情况下：n个proposal提出了n个不同的proposal，正好有n个acceptor分别接受了其中一个proposal。这就导致了每个acceptor接受的proposal和将要选中的value都不一样。这就不满足上述的大多数同意的要求（即R1）。即使仅有两个proposer提出proposal，当系统中的一个acceptor失效后，也存在每个proposal被一般的acceptor接受的情况，这时候，失效的那个acceptor无法学习到那个proposal中的value最终被接受了。（这里说的是一个acceptor在某个value被选出来之前失效。）
P1和R1意味着一个acceptor必须能够接受超过一个proposal。为了便于区分proposal，我们使用编号来为每个proposal做记号（编号就是一个数字）。因此，一个proposal需要包含两个元素：编号和value。（这里将这个proposal表示为p<n,v>，n表示标号，v表示value）。为了保证不同的proposer提出的proposal上面的编号不一样，需要特殊的机制来获取编号（比如可以根据系统中的acceptor的数量n以及这个proposer的编号m，例如编号为m的proposer提出的proposal的编号变化方式为m+i*n，i是提出proposal的次数，即i>=0）。一个value被接受的条件就是一个带有该value的proposal被大多数的acceptor接受。这样，我们就说这个value和该proposal被接受了。
我们允许多个proposal被接受，但是我们需要保证所有的被选中的proposal里面带有的value是相同的。我们得出了下面的约束条件：
P2：如果一个带有某个value的proposal被选中，那么所有的带有较高编号的proposal中的值必须也是这个value。
即，如果p<n,v>被选中，那么对于所有的其它proposal p<n',v'>，必须满足：如果n'>n，那么v'=v。既然编号n是全局编号的，那么P2就保证了算法的Safety，即仅有一个value会被选中。（这里意味着，某个值被选中后，仍然有可能存在一些proposer继续对某个值提出proposal。所以这里要求后续的proposal中携带的value需要满足一些条件以实现唯一的value被选择。）
某个proposal被选中，这个proposal就需要被至少一个acceptor接受。（接受操作在选中操作之前，二者具有时间的先后顺序）。因此，我们将约束向向前推：
P2a：如果一个带有某个value的proposal被选中，那么所有被acceptor接受的带有较高编号的proposal中的值必须也是这个value。
P2a保证了P1，为了同时保证P2和P2a，进一步提出了约束条件：
P2b：如果一个带有某个value的proposal被选中，那么所有proposer提出的带有较高编号的proposal中的值必须也是这个value。
因为proposal只有proposer能够发出，因此P2b就隐含了P2a和P2。
既然proposer的行为被约束了，那么acceptor的行为也要发生改变，这种改变要保证P2b的满足。P2c给出了acceptor需要满足的条件P2c：
P2c：对于任意的v（value）和n（number），如果一个有<n,v>构成的proposal被某个proposer发出，那么形成大多数acceptor集合S中的acceptor具有这样的特点：要么，S中没有一个acceptor接受过任何一个编号小于n的proposal；要么，S中的acceptor接受过的编号小于n的proposal中编号最高的那个proposal携带的value为v。
P2c的满足隐含了P2b的满足（证明略）。
为了保证P2c，一个proposer想要发出一个编号为n的proposal时需要学习小于编号n的所有proposal中编号最高的proposal，这个proposal是将要或者已经被S中的acceptor接收的proposal。（有点绕，意思就是，一个proposer想要发出更高编号的proposal之前需要learn系统中已经被大多数acceptor接收或者将要接收的proposal的编号）。这里原文说明的不是很详细，首先proposer想要发出一个proposal时候如何获得已经被接受的proposal的编号呢？其实这和步骤是在proposer发送上一个proposal'是从acceptor的回复中获得的。同时，此处也没说细说acceptor的如何回复接受到的proposal。后面会详细说。
这里的P2c的目的就是要保证每一个新的proposal的编号大于之前的编号，而且新的proposal的value要与已经接受的proposal的value保持一致（如果之前没有value被接受的话，那么新value可以为任意值）。
为了保证P2c，下面的两个算法描述了一个proposer发送proposal时需要执行的步骤：
（1）一个proposer选择一个新的编号并发送一个request给某个大多数acceptor组成的acceptor集合中的每一个，并要求acceptor承诺以下两件事：
（a）不再接受编号小于n的其它的proposal，且
（b）将这个acceptor已经接受过的编号小于n的proposal中编号最大的那个proposal放在回复消息中（如果这个acceptor确实接受过其它的proposal，否则回复空）。
我们将这个步骤称为带有编号为n的prepare request阶段。
（2）如果一个proposer收到了大多数的acceptor的满足上述承诺的回复消息，那么这个proposer就可以发送一个编号为n，且带有value为v的proposal给acceptor（给多少个acceptor？我觉得大多数的acceptor就可以。或者比较低效的方法就是每一个acceptor，这里原文也没有细说）。这里的value就是上一个prepare request阶段中收到的回复消息中的value。这个value是编号小于n中最大的那个proposal携带的value，如果所有的acceptor回复的消息中显示没有任何的proposal被接受，bane这个proposer就可以根据自己的需要设定value值。
此处要注意，proposer通过发送一个proposal给某些acceptor来提交最终的proposal。这里作者也没有细说发送给哪些acceptor。只是说了这次发送的acceptor可以和上一轮发送回复的acceptor不一样。当然，肯定是超过半数的acceptor会接收到这次的proposal消息。这个阶段被称为accept request阶段。（此阶段也可能会选不出value，即accept request也可能不会被接受，因为在prepare request回复和accept request被acceptor接收之间，acceptor可能接受一个编号大于n且value同样为v的新的proposal，这样的情况不断循环出现的话，没完没了了--活锁。死锁basic paxos还没什么彻底的方法解决活锁问题）。
下面来介绍acceptor可能执行的操作，一个acceptor可能会接收到两种请求：prepare请求和accept请求。一个acceptor可以拒绝任何请求而不会导致算法出现Safety问题（但是没有必要的情况下，acceptor还是会好好工作，而不会任性的随意拒绝一个request）。也就是说，当这个acceptor允许回复request请求时，它总是会回复的。其总是会回复一个prepare request，但是，当且仅当一个acceptor没有对其它的带有更高编号的proposal做出承诺时，该acceptor才会回复accept request并接受这个proposal。也就是对P1的加强：
P1a：一个acceptor仅在没有对含有比当前收到的accept request请求中的proposal携带的编号还要高的其它proposal做出上述承诺时，该acceptor才可接受此次accept request中的proposal。（也就是说acceptor虽然对你做出了不接受较小编号的proposal的承诺，但是它不承诺不会接受较高编号的新proposal。意思就是现在你的身份只是备胎，在没有找到新备胎之前我还是你女朋友，否则你就成前任备胎了）。
一个acceptor将不再回复带有低编号的proposal（你都称为前任备胎了，我也就不用回你短信了，你自己就清楚状况了）。同时，一个acceptor也不会再次回复已经回复过的相同的prepare request（可能是因为消息重复接受，没有必要再回复一次）。
所以一个acceptor仅需要记住已经接受过的编号最大的那个proposal，和回复这个proposal所对应的proposer。因为P2c必须要能够保证才能保证算法的正确性（Safety），也就是说一个acceptor必须记住这个信息，即使它失效后重启（持久化这个信息）。而一个proposer可以不负责任的随时忘记自己发送过的proposal，只要之后别再发送具有相同编号的proposal即可。
将proposer和acceptor的操作放在一起，我们可以看出，这个算法可以分为两个阶段：
Phase 1：
（1）一个proposer选择一个编号n，并发送一个携带该编号的prepare request给大多数的acceptor；
(2) 当一个acceptor接收到一个prepare request，如果n大于之前已经恢复过的所有prepare request中的编号，那么acceptor将回复这个prepare request（带上承诺：不再接受编号小于n的prepare request，和，当前已经接受的编号最高的proposal的信息）给这个proposer（如果这个acceptor之前确实回复过这样的prepare request，如果这个acceptor第一次被prepare request，那么其承诺：不再接受编号小于n的prepare request，并回复一个空给proposer）。
Phase 2：
（1）如果一个proposer收到了来自大多数的acceptorprepare request的回复，那么其将再次发送一个accept request给这些acceptor（这儿又说回复相同的acceptor）带上编号n和value v。这里的v时根据acceptor对prepare request的回复消息来定的，如果回复消息中有前一个proposal已经提出的value，那么v就等于之前的value，否则这个proposer可以自己确定想要的value。
（2）如果一个acceptor收到了一个编号为n的accept request，除非在此之前其又接受了一个编号比n大的新的proposal，否则，这个acceptor将接受这个accept request。
一个proposer可以发出多个proposal，只要遵守上述的协议。一个proposer也可以在任何时候放弃自己的请求。从性能方面来考虑的话，如果一个acceptor接受了一个编号较高的新的proposal后，它应该通知之前回复过的proposer一遍这个proposer能够及时放弃后续操作而避免性能损失。这里仅仅是一个性能优化方面的考虑，不涉及到正确性问题。
2.3 学习一个被选中的value
一个learner如果想要 学习被选中的value的话，那么其就要去查询被大多数acceptor接受的proposal。最简单的做法就是，每当一个acceptor接受了一个新的proposal后就主动将该信息发送给所有的learner。这种方法能够保证所有的learner及时的更新被选中的value，但是会导致性能上的问题，因为这个方法在更新learner的知识时候需要的消息发送条数为：acceptor的个数 * learner的个数。
前面的非拜占庭消息发送模型保证了一个learner可以从其它的learner处学习某个被选中的value。那么一个acceptor在接受一个proposal后仅仅需要通知其中一个不同的learner就可以，其它的learner可以从这个learner处学习到。但是这优惠导致一个问题，如果这个learner在传播新学到的value之前挂掉的话，那么这个心value就无法被学习了。 同样，那就折中考虑吧，选择更新部分learner，这里就要在具体实现的时候综合考虑性能和一致性之间的平衡问题了。
如果一个learner实在学不到新value的话，那么还有最后一招，这个learner自己起一个proposer来提交proposal，这时候肯定就能学到最新的value了。
其余的就不翻译了，主要就是Liveness和具体实现时候要考虑的一些问题。
第二部分：个人理解
1. 不要深究细节，因为论文中根本就没有说明细节，这需要具体的实现时候去考虑。
2. 为什么acceptor需要保证不接受编号较小的proposal？
为了保证编号能够一直增加？
3. proposer如何学习已经被accepted的proposal？
proposer在prepare request的回复消息中获取当前被接受的proposal的信息。
4. 活锁？
Basic paxos中的活锁问题理论上还未解决。
5. Paxos算法需要保证的是一致性，重点是Safety。Liveness能否保证？
Github上已经有Paxos的TLA+ Specification了，其中已经验证了Safety属性，但是死锁没有验证Liveness。因为Lamport认为算法的Liveness是所有需要被检验的属性中放在最后一位的。
6. Paxos算法大体上来看很简单，但是具体细节真的想起来还是模糊不清。
这是因为Leslie Lamport在文章中根本就没有深入细节，其对算法的描述进行了高度的抽象。这从他在TLA+的书中对Algorithm和Program定义的区别中能够看出。Algorithm仅仅是解决问题的思想的靠度抽象的表述（类似伪代码），而算法是解决问题的具体实现（必须深入到每个实现细节）。一旦抽象，容易理解，但是到具体实现时候就比较麻烦。一，未能真正理解算法，似懂非懂如我；二，实现方式有很多种，想从Algorithm中找到依据可能很困难；三，Coding水平有限，又如我。
7. 与Lamport其它文献的关系？
请看Leslie Lamport的个人发表物主页关于Paxos的文献，http://lamport.azurewebsites.net/pubs/pubs.html
8.占位符
...
第三部分：Paxos的TLA+
https://github.com/bringhurst/tlaplus/tree/master/examples/Paxos Paxos的TLA+ Specification（有时间把这个源码注释一下，时间待定）
第四部分：实例
时间待定...
第五部分：备注
占位符...
纯手码，欢迎批评指正！也欢迎有兴趣的朋友留言讨论。
网友评论