vlambda博客
学习文章列表

Paxos协议有四大基本要求，分别是安全性，可用性，一致性和平等性。

安全性要求整个系统只能选择一个完全相同的值，否则就根本无法达成多机共识；可用性需要系统的可靠性不受少部分主机的影响，不会因为少数主机的异常而导致系统停摆，只要系统中绝大部分主机是正常的，可以相互通信，系统就可以保持自运转；一致性要求被系统选择的值应该是被绝大部分主机所承认的，这样基于少数服从多数的原则，就可以保证系统整体的数据一致性；平等性需要系统中各主机的身份是完全具有可替代性的，保证系统中没有不可靠的单点问题。

在Paxos协议中，每台主机需要同时扮演3种角色，依次是Proposer(提案者)，Acceptor(接受者)与Learner(学习者)。

Proposer直接处理对外的请求，并作为提案者向系统提交提案；Acceptor负责处理Proposer提交的提案，遵循统一的规则判断是否接受提案；Learner学习与记录Acceptor确定的提案，并根据习得的值触发状态机的状态流转。

为了区分不同的提案，理清提案提交的顺序，并作为Acceptor选择提案的权重，需要对系统中的所有提案进行唯一编号。

我们很容易设计出满足要求的提案编号规则，例如，我们可以将提案编号按照bit前后切分为服务器ID和选举周期两部分。其中服务器ID与具体的主机绑定，选举周期由每台主机独立维护，从0开始依次递增，通过自行固化存储保证不会重复使用。每次生成提案id时，都会将当前的选举周期加1，更新提案编号propose_id之后再发起提案。

整个系统只有一个Acceptor显然不能满足要求，因为这个单一的Acceptor会造成单点问题，若Acceptor宕机，则整个系统不可用。因此，我们的系统必须由多个Acceptor构成，那么基于系统一致性的要求，提案必须由系统中的绝大部分Acceptor接受，才能视为被系统整体所承认。

上述问题是基于Acceptor是否需要收到多个提案，掌握尽可能多的信息之后，再自行判断是否需要提案而提出的。而基于系统的可用性，Acceptor必须接受他所收到的第一次提案。想象这样一种场景，整个系统由5台主机构成，主机s1在收到请求之后，发起了一轮提案。如果整个系统之后没有收到任何其他的请求，而所有的Acceptor都需要等待收到更多的提案才能对是否接受第一轮提案做出回应，那么整个系统就会陷入卡死状态，虽然所有主机都正常运转，但系统实际上应对这种情形无法继续运转了。

基于上述推理，我们得出了第一条基本规则P1，Acceptor必须要接受他所收到的第一个提案，否则就无法应对上述场景，达成一致。

按照常理，我们一般会天真的认为，为了保证系统的一致性，Acceptor最简单的做法就是只接受一个提案，但是事实证明这种想法真的是太naive了。

想象这样一种情形，整个系统由6台主机s1~s6构成，其中s1和s4同时发起了图中红色和绿色对应的两个提案。需要注意的是，我们系统的通信模型类似于网络通信模型，是可能发生丢失或者重传的。主机s1发起的提案被主机s1~s3收到，但是因为数据丢包提案并没有被主机s4~s6收到；主机s4发起的提案被主机s4~s6收到，但是同样因为数据丢包提案并没有被主机s1~s3收到。基于前文推导的基础规则P1，Acceptor必须要接受他所收到的第一个提案，所以s1的提案被s1~s3接受，s4的提案被s4~s6接受。

基于系统的一致性要求，s1~s6需要达成一致，必须要保证至少4台（大部分，超过一半）主机都接受了相同的提案。上述情形下，即便是丢失的报文发生了重传并被Acceptor接收，如果任何Acceptor都无法接受超过一个提案，那么系统整体就无法继续达成一致。因此，为了保证系统在这种情况下也是可用的，我们可以推导得出，部分Acceptor有时也需要能够接受多个Proposer提交的提案。 

但是因为P2规则过于抽象，据此我们很难设计我们的一致性协议。一种很简单的方式是对P2规则进行强化，找到一种新的规则，这种规则首先能够明确满足P2，并且在条件上更容易进行界定。

基于上述思想，我们将特定Acceptor满足P2强化为所有Acceptor都满足P2，可以得到规则P2a，即一旦有一个值为value的提案被接受，那么之后任何Acceptor再次接受的提案的值也必须为value。

因为Acceptor接受的提案都是Proposer提出的，所以我们可以将Acceptor接受的提案的值都相同的责任转嫁给Proposer，即我们要求一旦有一个值为value的提案被接受，那么之后任何Proposer提出的任何提案（等价为propose_id更大的提案）的值也必须为value。上述规则也称为P2b。

基于推理的强化规则，我们显然可知，若P2b被满足，则P2a一定满足，同样的，也有P2满足。

根据上面的推导，现在我们的问题转换为，需要如何设计我们的协议，使得系统能够满足准则P2b。对此，论文《Paxos made Simple》给出的结论归纳为P2c，即如果一个提案编号propose_id为k的提案值为value，这个提案被接受了，那么整个系统中会存在一个多数派，要么他们之中没有人接受过propose_id小于k的提案，要么他们接受的所有小于k的提案中propose_id最大的那个提案的值也是value。初看这个结论我们难免一脸懵逼，其实我们从本质去思考，可以将P2c理解为对P2b的另一次强化，并将问题转换为如何从P2b推导出P2c，我们的问题转换为如何证明P2c蕴含P2b。

我们首先用图描述一下规则P2b，如果一个propose_id为k的提案值为value，并且当前已经被接受了，那么之后任何Proposer提出的，proposed_id大于k的提案的值也为value，在这种情况下，因为任何Acceptor接受的提案都是由Proposer提出的，也就可以推导出任何之后被接受的，propose_id大于k的提案的值也等于value。利用数学归纳法，我们假设，propose_id小于等于k的提案都被接受了，并且值均为value，如果在满足P2c的条件下，我们能够推理得到，提案编号propose_id为k+1的提案的值，也为value，这样我们就能判明，P2c蕴含P2b，可是怎么去证明这一点呢？

这里我们采用反证法进行证明，判断结论的否定与前提条件之间能否推导出内在的矛盾。如下图所示，对结论进行否定，可以得到两点条件，但是都与前提存在矛盾。首先，①多数派没有接受propose_id小于k+1的提案，但是根据前提，系统整体接受了编号为k的提案，也就是说多数派接受了propose_id小于k+1的提案，这两者之间有矛盾。其次，②多数派已经接受的小于k+1的编号最大的那个提案的值不等于value，这个也与前提条件有矛盾，因为多数派接受了编号为k的提案，这个提案的编号仅次于k+1。由此可见，根据反证法，可以从条件P2c出发，推导得到P2b。

我们对P2c这一条件进行分析，思考一下怎么基于P2c设计我们的协议。首先，我们不能基于条件1来设计协议，因为系统在接受完一轮提案之后，无法继续满足条件，会导致系统停摆。但是，基于条件2来设计协议，在消息可能发生延时的情况下，设我们即将发出的提案的编号为k，那么我们就要预测propose_id小于k，并且编号最大的被接受的提案的值是什么。而这个小于k的编号最大的被接受的提案可能会不断变化，我们很难确定。所以与其预测这个编号最大的提案是什么，不如就限制Acceptor不要继续接受propose_id小于k的任何提案，这也是Paxos协议中，第一轮投票环节，Acceptor会对Proposer做出不会接受提案编号小于所投递提案编号的承诺的原因。

以上就是Paxos协议的推理部分，我个人对此的评价是环环相扣，精妙绝伦，不由得不从内心对Lamport深为拜服。我认为推理背后的思想比推理本身更为重要，对于Paxos协议，羊哥认为背后的核心思想就是恰当的逻辑思考，条件的不断强化，以及数学归纳法，对此，你怎么看？