Paxos是用于一种分布式系统并且具有容错性的一致性算法，是目前业界公认能解决分布式系统一致性的问题算法之一。它晦涩难懂的程度完全可以跟它的重要程度相匹敌。Paxos于1990年由Lamport提出，但直到1998才正式被计算机科学界接受。因为Lamport刚开始采用描述故事的方式来描述算法，但不被相关的出版社接受。后来Lamport发表《Paxos Make Simple》论文使得Paxos加速被广大计算机工程师理解并接受。但一直以来计算机的工程师抱怨Paxos算法是难以理解、晦涩，本人在学习之初也有深有体会。我在之前的文章有写过Paxos算法的原理，但那时理解的不够透彻，这里再对Paxos算法的原理做分析记录，加深理解。
拜占庭将军问题
拜占庭将军问题也被称为“拜占庭容错”，拜占庭将军问题是Leslie Lamport（2013年的图灵讲得住）用来为描述分布式系统一致性问题（Distributed Consensus）在论文中抽象出来一个著名的例子。这个例子大意是这样的：
拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队（一半以上）同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻，从而赢取战斗？拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问题。拜占庭问题，假设将军总数是N，叛徒将军数为F，则当 N >= 3F+1 时，问题才有解，共识才能达成，这就是Byzantine Fault Tolerant（BFT）算法。拜占庭算法不在本文章的范围之内，本文的Paxos算法是假设集群中不存在拜占庭问题，即不存在数据被篡改的情况，数据要么到达，要么不到达，不存在被篡改后送达。
Paxos算法
Paxos算法有三种角色，两个大阶段，每个大阶段下又有两个小阶段，每种角色在不同阶段有不同的操作。就本人的学习经验而言觉得Paxos算法难以理解的地方在于，仅靠文字难以描述清楚Paxos算法的收敛过程。本文将全力把算法讲的通俗易懂，并配上小例子，Paxos算法中的参与者主要分为三个角色，同时每个参与者又可兼领多个角色。在整个算法过程中提案中的提案号只能递增。
三个角色
- proposer： 提议者，提出提案（proposal），提案信息包括提案编号和提议的value
- acceptor： 表决者，收到提案后可以接受(accept)提案
- learner： 学习者，只能”学习”被批准的提案，并广播给未学习的learner学习提案。
三个承诺
- promise(v)：acceptor对proposer承诺，如果没有更大编号的proposal会accept它提交的proposal
- accept(v)：acceptor没有发现有比之前的proposal更大编号的proposal，就批准了该proposal
- chosen(v)：当acceptor的多数派都accept一个proposal时，该proposal就被最终chosen，也称为决议
提案是Paxos算法的一个重要概念，一个提案中有两个值Proposal Number和Proposal Value，简称Number和Value。其中Number是每次提案的版本号，而Value是提案的值，在分布式系统中Value可以是一个具体的字段，一个文本，或是一个命令。下面是先贴上算法的官方描述，是算法保证一致性的基本语义：
- 决议（value）只有在被proposers提出后才能被批准（未经批准的决议称为“提案（proposal）”）；
- 在一次Paxos算法的执行实例中，只批准（chosen）一个value；
- learners只能获得被批准（chosen）的value。
Paxos算法的作者Lamport通过不断加强上述3个约束（主要是第二个）获得了Paxos算法，因此又衍生出四个约束f分别是P1，P2，P2a，P2b，P2c。这也是Paxos算法的推导过程
P1：一个acceptor必须接受（accept）第一次收到的提案。
注意P1是不完备的。如果恰好一半acceptor接受的提案具有value A，另一半接受的提案具有value B，那么就无法形成多数派，无法批准任何一个value。约束2并不要求只批准一个提案，暗示可能存在多个提案。只要提案的value是一样的，批准多个提案不违背约束2。于是可以产生约束P2。
P2：一旦一个具有value v的提案被批准（chosen），那么之后批准（chosen）的提案必须具有value v。
注：通过某种方法可以为每个提案分配一个编号，在提案之间建立一个全序关系，所谓“之后”都是指所有编号更大的提案。如果P1和P2都能够保证，那么约束2就能够保证。批准一个value意味着多个acceptor接受（accept）了该value.因此，可以对P2进行加强。
P2a：一旦一个具有value v的提案被批准（chosen），那么之后任何acceptor再次接受（accept）的提案必须具有value v。
由于通信是异步的，P2a和P1会发生冲突。如果一个value被批准后，一个proposer和一个acceptor从休眠中苏醒，前者提出一个具有新的value的提案。根据P1，后者应当接受，根据P2a，则不应当接受，这中场景下P2a和P1有矛盾。于是需要换个思路，转而对proposer的行为进行约束。
P2b：一旦一个具有value v的提案被批准（chosen），那么以后任何proposer提出的提案必须具有value v。
由于acceptor能接受的提案都必须由proposer提出，所以P2b蕴涵了P2a，是一个更强的约束。但是根据P2b难以提出实现手段。因此需要进一步加强P2b。假设一个编号为m的value v已经获得批准（chosen），来看看在什么情况下对任何编号为n（n>m）的提案都含有value v。因为m已经获得批准（chosen），显然存在一个acceptors的多数派C，他们都接受（accept）了v。考虑到任何多数派都和C具有至少一个公共成员，可以找到一个蕴涵P2b的约束P2c。
P2c：如果一个编号为n的提案具有value v，那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于n 的任何提案，要么他们已经接受（accept）的所有编号小于n的提案中编号最大的那个提案具有value v。
可以用数学归纳法证明P2c蕴涵P2b，根据数学归纳法，我们证明了若满足P2c，则P2b一定满足。假设具有value v的提案m获得批准，当n=m+1时，采用反证法，假如提案n不具有value v，而是具有value w，根据P2c，则存在一个多数派S1，要么他们中没有人接受过编号小于n的任何提案，要么他们已经接受的所有编号小于n的提案中编号最大的那个提案是value w。由于S1和通过提案m时的多数派C之间至少有一个公共的acceptor，所以以上两个条件都不成立，导出矛盾从而推翻假设，证明了提案n必须具有value v；若（m+1）..（N-1）所有提案都具有value v，采用反证法，假如新提案N不具有value v，而是具有value w’,根据P2c，则存在一个多数派S2，要么他们没有接受过m..（N-1）中的任何提案，要么他们已经接受的所有编号小于N的提案中编号最大的那个提案是value w’。由于S2和通过m的多数派C之间至少有一个公共的acceptor，所以至少有一个acceptor曾经接受了m，从而也可以推出S2中已接受的所有编号小于n的提案中编号最大的那个提案的编号范围在m..（N-1）之间，而根据初始假设，m..（N-1）之间的所有提案都具有value v，所以S2中已接受的所有编号小于n的提案中编号最大的那个提案肯定具有value v，导出矛盾从而推翻新提案n不具有value v的假设。根据数学归纳法，我们证明了若满足P2c，则P2b一定满足。P2c是可以通过消息传递模型实现的。另外，引入了P2c后，也解决了前文提到的P1不完备的问题。
算法过程
前面看不懂没关系，那是论文中的内容，晦涩难懂，下面开始用大白话来剥开Paxos算法。用一句话总结就是：proposer将发起提案（value）给所有accpetor，超过半数同意(accpet)后，提案获得批准(chosen)，提案写入accpetor内，最终所有accpetor获得一致性的确定性取值。
prepare阶段
- 第一阶段A：Proposer选择一个提案号n，向所有的Acceptor广播proposal [n , null]提案请求。
- 第一阶段B：Acceptor接收到proposal [n , null] 提案请求，分为两种情况
- 如果自己没有批准过提案，并且提案号n比之前收到过的proposal提案号都要大，回复[OK]并承诺将不会接受提案号比n小的提案号，如果提案比之前收到过的提案号小，则忽略当前提案请求。简而言之，在没批准过提案之前的Acceptor会不断接受新的提案。
- 如果自己已经批准过提案，则回复自己批准过的提案信息
accept阶段
- 第二阶段A：整个协议最为关键的点：Proposer得到了Acceptor响应。有以下几种情况
- 如果没有收到超过半数accpetor回复，直接提议失败，proposer回到prepare阶段继续发起新提案
- 如果收到了超过半数的accpetor回复，又分为两种情况
- 收到所有的accpetor回复都是[OK]，说明accpetor都没有批准过提案，那么向所有的Acceptor发起自己的提案信息[n , value]，这里要注意一定是所有的回复都是 [OK]。
- 收到所有的accpetor回复中有一部分回复的是批准的提案 [n1, value]，[n2, value]。那么从所有收到的提案中选择提案号最大的作为提案的值，提议编号仍然为n。作为提案向accpetor发起请求
- 第二阶段B：Acceptor接收到提议后，如果该提议版本号不等于自身保存记录的版本号（第一阶段记录的），不接受该请求，相等则写入本地。
整个paxos协议过程盘根错节，复杂难懂，但只要把握和理解这两点就基本理解了paxos的精髓，这也是使得paxos算法最终收敛到一个提案的关键点：
理解第一阶段accpetor的处理流程：如果Acceptor已经批准过提案，会保存当前请求过来的提案号，但不会接受提案，而是返回之前批准过的提案信息；如果Acceptor没有批准过提案，则本地记录当前请求的提案号，并承诺不再接受低于提案号的提案，简单来说只信任最后一次提交的版本号的请求；
理解第二阶段proposer的处理流程：未超过半数accpetor响应，提案失败，重新回到第一阶段发起提案请求；返回的accpetor值都为空才提交自身要写入的值，否则选择非空值里版本号最大的值提交，最大的区别在于是提交的值是自身的还是使用以前提交的。
活锁
在第一阶段，proposer提出提案后，Acceptor收到该提案比本地以前收到过的提案记录小会拒绝。因此proposer会继续提出编号更大的提案。这时Paxos算法存在一种极端情况，如果2个proposer都发现自己的编号过低转而交替提出更高编号的提案，如此这两个proposer会陷入死循环，这种情况称为活锁。Paxos算法的改进版Multi Paxos解决了这个问题。
三军问题
这里用三军问题，通过现实场景来描述一下Paxos算法是过程，三军问题比较切合Paxos算法的场景，也有很多博文使用三军问题来解释Paxos算法，这里三军是虚数，可以是五军也可以是七军，为了简单起见故用三军。故事背景是这样的：
- 三支军队准备进攻攻打一个城邦，他们中任意一支军队单独攻打城邦，必败。其中两支军攻打城邦才有胜算，因此他们必须约定一个统一的时间，至少联合两支军队，才可以进攻。
- 每支军队有1个参谋负责提议进攻时间，每支军队也有1个将军批准参谋提出的进攻时间。
- 三支军队的唯一媒介是派通信兵告诉其他军队，自己军队提议的进攻时间信息。但通信兵可能被城邦的侦察兵捕获俘虏，导致信息丢失不能送达。（如果城邦的人把通信兵抓了后，修改了进攻时间信息，并放回了通信兵。就会出现拜占庭问题，即信息被篡改了。这里假设不存在这种情况）
为了通过Paxos算法来使三军决策出一个进攻时间，还需要做出一些约束：每个军队的参谋在提出进攻时间的提案时，必须使用一个全局递增的编号，一个军队的将军在收到另外两支军队的提案时，只接受编号最大的提案。下面开始算法过程：
- 参谋1发起提议，派通信兵带信给3个将军，内容为 [编号1 , null]；
- 三个将军的情况如下
- 将军1和将军2收到参谋1的提议，将军1和将军2把 [编号1 , null] 记录下来，如果有其他参谋提出更小的编号，将被拒绝；同时让通信兵带信回去，内容为[Accepted]；
- 派往军队3的通信兵被抓，因此将军3没收到参谋1的提议；
- 参谋2在同一时间也发起了提议，派通信兵带信给3个将军，内容为 [编号2 , null]；
- 三个将军的情况如下
- 将军2和将军3收到参谋2的提议，将军2和将军3把 [编号2 , null] 记录下来，如果有其他参谋提出更小的编号，将被拒绝；同时让通信兵带信回去，内容为 [Accepted]；
- 派往军队1的通信兵被抓，因此将军1没收到参谋2的提议；
- 参谋1收到至少2个将军的回复，再次派通信兵带信给有答复的2个将军，内容为 [编号1，进攻时间1]；
- 两个将军的情况如下
- 将军1收到了 [编号1，进攻时间1] ，和自己保存的历史编号相同，因此把 [编号1，进攻时间1] 保存下来；同时让通信兵带信回去，内容为 [Accepted]；
- 将军2收到了 [编号1，进攻时间1]，由于编号1小于已经保存的编号2。因此让通信兵带信回去，内容为[Rejected，编号2]；
- 参谋2收到至少2个将军的回复，再次派通信兵带信给有答复的2个将军，内容为 [编号2，进攻时间2]；
- 两个将军的情况如下
- 将军2收到了 [编号2，进攻时间2]，和自己保存的编号相同，因此把[编号2，进攻时间2]保存下来，同时让通信兵带信回去，内容为 [Accepted]；
- 将军3收到了 [编号2，进攻时间2]，和自己保存的编号相同，因此把[编号2，进攻时间2]保存下来，同时让通信兵带信回去，内容为 [Accepted]；
- 参谋2收到至少2个将军的 [Accepted] 内容，确认进攻时间已经被多数派接受；
- 参谋1只收到了1个将军的（Accepted）内容，同时收到一个 [Rejected，编号2]；参谋1重新发起提议，派通信兵带信给3个将军，内容为（编号3）；
- 三个将军的情况如下
- 将军1收到参谋1的提议，由于[编号3]大于之前保存的[编号1]，因此把[编号3]保存下来；由于将军1已经接受参谋1前一次的提议，因此让通信兵带信回去，内容为[编号1，进攻时间1]；
- 将军2收到参谋1的提议，由于[编号3]大于之前保存的[编号2]，因此把[编号3]保存下来；由于将军2已经接受参谋2的提议，因此让通信兵带信回去，内容为[编号2，进攻时间2]；
- 负责通知将军3的通信兵被抓，因此将军3没收到参谋1的提议；
- 参谋1收到了至少2个将军的回复，比较两个回复的编号大小，选择大编号对应的进攻时间作为最新的提议；参谋1再次派通信兵带信给有答复的2个将军，内容为[编号3，进攻时间2]；
- 将军1和将军2收到了[编号3，进攻时间2]，和自己保存的编号相同，因此保存[编号3，进攻时间2]，同时让通信兵带信回去，内容为[Accepted]；
- 参谋1收到了至少2个将军的[accepted]内容，确认进攻时间已经被多数派接受；
