Basic Paxos

背景介绍

分布式一致性问题

在一个靠Messages passing作为节点通信方式的分布式系统中，多个参与者需要就某一个变量var的值v达成一致。多个参与者A、B、C，可能对于v的值，A想设成value_a，B想设成value_b。但只能有一个值最终设置成功，形成决议。且形成决议后，后面无论何时参与者获取v的值一定是最初决议的值，不会再变。

拜占庭将军问题

拜占庭将军问题是Lamport老爷子编出来的一个故事，用来描述点与点通信中的基本问题。

拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了防御目的，因此每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军必需达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序，在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员不可靠的情况下，其余忠诚的将军在不受叛徒或间谍的影响下如何达成一致的协议，拜占庭问题就此形成。拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现不可预料的行为。

在分布式系统中，不同的参与者之间通过Messages passing，尝试达成共识，但有的时候，会存在参与者因为系统错误或者通讯问题传递错误的信息，导致影响系统的最终一致性。

Paxos岛

Paxos是Lamport在1990年就提出的一种基于Messages passing且具有高度容错特性的一致性算法。为了描述保持分布式系统一致性的Paxos算法，Lamport老爷子又虚拟出了古希腊Paxos岛上议会临时议员们面临的问题。不过这个故事一些人不喜欢，审稿人让Lamport把Paxos到内容换掉，不然无法发表。Lamport就把文章发在了自己网站上。最终论文发表时间成了1998年。

有一个叫Paxos的希腊岛屿，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题，消息可能传两次，但绝对不会出现错误消息；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的。

Paxos能接受的异常情况：在基于Messages passing的分布式系统中，可能会存在参与者处理速度非常慢，宕机或者重启的问题，而消息可能会延迟、丢失或者重复。Paxos就是要解决分布式系统在可能发生的上述任意异常情况下保持一致性的问题。不过Paxos，有一个假设是不存在拜占庭问题，不会有信息错误存在。

多数派（法定集）

设分布式节点总集合为{C}，定义集合{Q_i},Q_i是{C}子集，且{Q_i}中任意两个成员的交集不为空，则称Q_i为{C}的法定集合（或者称多数派）。

Paxos算法描述与证明

Lamport在《The Part-Time Parliament》中提出的算法Paxos，并且使用了大量数学证明，但对于大多数人太晦涩难懂，Lamport在《Paxos Made Simple》中又用纯英语逻辑推导讲了一遍。这篇文章纯度很高，很多细节，都会影响对Paxos的准确理解。《Paxos Made Simple》先定义问题后，先用数学归纳法提出了可以用Messages Passing模型实现的约束，然后介绍了满足约束的Paxos算法内容。在这里我们会先描述算法内容，然后给出简单的归纳证明。

问题定义

一致性的要求如下：

1、value只有在被提出（proposed）之后才可能形成决议（chosen）。
2、在一个Paxos执行实例中，只会有一个value被作为决议（chosen)。
3、参与者只能获取到被chosen的value。

Paxos算法把参与者分成三个角色：proposers，acceptors，和learners（注：允许一个参与者扮演多个角色）。Proposers会发出预提案（prepare request, proposal number），提出提案(accept request proposal, proposal)。Acceptor可以回复（respond）预提案，可以接受提案。当提案获得多数acceptors接受后，则该提案被批准（chosen)。Learner可以‘学习’被批准的提案。

Paxos算法能接受的异常如Paxos岛中所述。

算法的提出

Note：不同的提案需要有不同的id，具有全局唯一性，而且‘之后’的提案，就是编号更大的提案。

《Paxos Made Simple》中算法的提出是定义问题后，为了解决单个参与者带来的不可靠问题，提出多个参与者，当多数派选择一个value后形成决议。而后通过一步步的提出requirements来明确在异步消息模型中需要保证的条件，进而提出满足这些条件的Paxos算法。

这里对论文中这些requirements做一个精简描述，后面再给出简单的证明。

忽略信息丢失情况，即使只有一个提案被提出，我们也希望能够形成决议。那么：

P1、一个Acceptor必须接收它收到的第一个提案。

但是P1不是完备的条件，因为如果有两个提案提出，一半接受了value A，一半接受了value B，那么就可能无法形成决议。所以只有当多数派接受的value才算是形成决议。因此，就需要让Acceptor接收不止一个提案。由于网络的延迟或参与者lost，我们允许先后可以有多个提案形成决议，但这些提案必须由相同的值。

P2、如果一个具有值v的提案被决议，那么之后每一个形成决议的提案都有值v。

形成决议意味着有acceptor接受这个提案，那么加强P2假设。

P2a、如果一个值v的提案被决议，那么每一个之后被acceptor接受的提案都具有值v。

但是这有一个问题，可能形成决议后，有一个不知道已经形成决议的proposer提出了一个不同值的提案。所以进一步加强：

P2b、一旦一个值v的提案形成决议，那么之后任何proposer提出的提案必须拥有值v。

论文在这里提出了一个包含P2b的一个约束P2c：

如果一个编号为n，value为v的提案被提出，那么存在一个多数派，要么他们全都没有接受（accept）过编号小于n的任何提案，要么他们已经接受（accept）的所有编号小于n的提案中编号最大的那个提案具有value v。

用反证法和归纳法可以证明P2c包含了P2b。

假设具有value v的提案m获得批准，当提案编号n=m+1时，采用反证法，假如提案n不具有value v，而是具有value w，根据P2c，则存在一个多数派S1，要么他们中没有人接受过编号小于n的任何提案，要么他们已经接受的所有编号小于n的提案中编号最大的那个提案是value w。由于S1和通过提案m时的多数派C之间至少有一个公共的acceptor，而这个acceptro具有小于n最大的编号m，所以以上两个条件都不成立，导出矛盾从而推翻假设，证明了提案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和P1那么就能够满足一致性问题要求。

算法描述

Paxos算法在《Paxos Made Simple》中是分阶段分角色介绍，下面除了这种方式也会分角色分阶段介绍。

分阶段描述-决议的提出与批准

通过一个决议分为两个阶段：

• 1、 prepare阶段
  1.1、 proposer选择一个提案编号n并将prepare请求发送给acceptors中的多数派（法定集合）；
  1.2、 acceptor收到prepare消息后，如果提案的编号大于它已经回复的所有prepare消息，则acceptor将回复proposer，同时回复中带有自己上次接受的提案，并承诺不再接受小于n的提案；
• 2、 Accepet阶段
  2.1、当Proposer收到多数派对其prepare request（proposal id n）的回复后，会从这些回复中选择proposal id最大的提案的value v作为要发起提案的value，向所有参与者提出提案（n, v）。如果回复的多数派没有应答过任何提案，那么这个值可以由proposer自己填写。
  Note:收到的回复中，要么最大那个proposal id的value是v（chosen value），要不回复中没有提案。
  2.2 Acceptor在不违反自己做出承诺的前提下，即没有应答过任何proposal id大于n的提案，在收到Accept请求后即接受(n, v)的提案。

在1.2步骤中，方便记忆，可以记住Acceptor对回复的proposer做出了两个承诺，一个应答。即：
承诺一，不再应答 Proposalid 小于等于当前请求的 PrepareRequest；
承诺二，不再应答 Proposalid 小于当前请求的 AcceptRequest
应答：返回自己已经 Accept 过的提案中 ProposalID 最大的那个提案的内容，如果没有则返回空值。

proposer发出的提案，最初response其proposal id的某个acceptor没有收到没有任何影响。上面的过程中，proposal在任意阶段被放弃都不会影响正确性。实现过程中，也往往会做出优化，中断一些proposal。如果一个proposer发现已经有其他proposer提出了编号更高的提案，则有必要中断自己的过程。prepare过程中，如果一个acceptor发现存在一个更高编号的提案，那么可以通知proposer，提醒其中断后续过程。

分角色描述-proposer和acceptor各自行为

由于就Paxos算法本身，proposer和acceptor都是按照各自规则行动，只需要‘照顾好’自身的proposal id和value，记录好自己的状态即可，分角色算是面向对象的思考方式，所以这里分角色再对paxos做一次介绍。

Proposer：
Prepare阶段：发送自身proposal id的预提案给一个acceptors多数派集合。
Accept阶段：如果收到来自一个多数派集合的承诺，就从回复中中挑选出proposal id最大的那个proposal value v作为value的值。如果回复中没有提案就自由赋值。

Acceptor:
Prepare阶段：如果收到预提案proposal id大于所有它已经回复的prepare消息，则acceptor将自己上次接受的提案回复给proposer，并承诺不再接受小于n的提案；
Acceptor阶段：Acceptor在不违反自己做出承诺的前提下，即没有应答过任何proposal id大于收到id未n的提案，在收到Accept请求后即接受(n, v)的提案。

问题思考

在阐述逻辑推导前，下面有三个简单问题，读者可以考虑一下，下面三种场景各自是否可能出现。如果能够出现举例说明出现这种情形的前后过程，如果不能出现，考虑一下为什么不会出现。

在一个分布式系统中，存在参与者A，B，C。我们用数据结构proposal(proposal_id, value)来表示提案。横轴的两格分别代表参与者和其存储的提案。

Case1:

Case2:

Case3:

论述

这一部分非论文部分，属于按自己的理解做出的论述，这只是一个论述，不能算是严格证明。

每一个参与者会存储一个min_proposal_id，用来记录预提案时的proposal_id。同时记录accept的提案proposal(a_proposal_id, value)。

1、首先证明第一次决议不会出现下面情况，不同proposer提出自己想写入的值都获得多数派接受形成决议。

不同proposer都写入了各自的值，那么写入各自值的proposer在accept阶段，都有多数派回复了他们，且多数派都没有自己accept的提案。

不同proposer都形成了决议，即多数派的acceptor都接受了他们的提案。

根据多数派定义，这些不同proposer之间，一定存在一个acceptor A1，在accept任何提案之前，回复了他们的prepare request，随后又都accept了他们的提案。

假设存在具有不同值的提案p1, p2均在第一次形成了决议。由于不同提案的proposal_id，我们大可设定p2.proposal_id大于p1.proposal_id。

A1，同时回复了他们的prepare request，根据承诺只有当proposal_id大于已回复的proposal_id，A1才会做出回复。那么A1一定先回复了p1，后回复了p2。

但是根据Acceptor做出的另一个承诺，不再Accept比min_proposal_id更小的提案，因此回复p2后，A1就不可能再accept了p1的提案。因此一定不存在第一次决议中有两个提案通过的情况。

2、形成决议后，后面再形成的决议，一定是保持了先前决议的值。即proposer获得多数派回复的时候，其中最大proposal_id的提案的值一定是形成决议的值。（如果回复中没有任何提案，那么一定是没有未形成过决议）。

对于回复中没有任何提案的情况，这里不再论述。这里证明一下最大proposal_id的提案值一定是形成决议的值。

2.1 证明第一次决议，通过决议的proposal_id是最大的。

如果第一次决议acceptor中任意多数派最大a_proposal_id不是形成决议的值，而是由某个proposer写入。那么最大max_proposal_id的预提案（prepare request）获得了多数派的回复，但还没有获得多数派的accept，同时多数派回复中均没有人accept过提案。形成决议值的chosen_proposal_id获得了多数派的回复，同时获得多数派的accept。

根据多数派定义，一定存在一个acceptor，在accept了chosen_proposal_id的提案之前，回复了max_proposal_id的预提案（prepare request），但这就违反了承诺。因此第一次决议，最大a_proposal_id的值一定是最后获得决议的值。

2.2 证明如果保证了，当前任意多数派最大a_proposal_id的提案值是决议值，那么就能够保持任意多数派最大a_proposal_id的提案值是决议值。

如果最大proposal_id的提案值不是之前形成决议的值，即最大proposal_id不是获得多数派accept的值。那么：

该最大max_proposal_id的预提案（prepare request）获得了多数派的回复。形成决议值的chosen_proposal_id获得了多数派的回复，同时获得多数派的accept，即存在一个多数派他们任意一个都accept了chosen_proposal_id的值。

根据多数派的定义，存在一个acceptor，回复了max_proposal_id，chosen_proposal_id，accept了chosen_proposal_id的提案。

如果回复max_proposal_id如果发生在accept了chosen_proposal_id之前，那么不可能。

如果之后，那么这个acceptor就给max_proposal_id的预提案回复了带有chosen_value的提案，那就又要证明在回复max_proposal_id的预提案时候，chosen_value的提案是不是最大的那个proposal_id。

问题就变成了上一次是不是最大的那个proposal_id带有chosen_value。如果上一次能够保证，那么本次max_proposal_id提案带有的value就是chosen_value。这就证明了2.2。

在2.1中我们证明了第一次决议的情况，通过递归归纳，我们可以证明2。

Paxos的特性：

当一个acceptor回复一个proposal_id，一定是大于存储下来上一次回复的min_proposal_id的。即min_proposal_id是一个递增的值。

同时a_proposal_id大于等于min_proposal_id，那么a_proposal_id也就是一个递增的值。

问题思考

Paxos是否会出现活锁，如何出现。