Paxos算法简介

Paxos算法的目的

Paxos算法是用来解决一致性问题。

什么是一致性问题？

考虑如下的场景：有一组进程p1，p2.....pn，一个变量v。所谓的一致性问题就是：如何让这组进程就变量v的值达成一致。为了解释何谓达成一致，考虑如下情形：
p1令v=a，p2令v=b，那么显然进程p1和p2就v的值没有达成一致。如果p2令v=a，那么认为p1，p2就v的值达成一致。让各个进程对变量v的值达成一致需要两个过程：
（1）给变量v选择一个值，假设是c
（2）让各个进程都认为v=c，即进程就c达成一致，这时我们认为变量v的值被决定。

法定集合性质

我们将一个超过半数的集合称之为法定集合，比如数字1，2，3，4，5，共5个元素，{1，2，3}有三个元素就是法定集合。法定集合性质：任意两个法定集合，必定存在一个公共的成员；这个性质是Paxos的基石，如果要回答Paxos基于什么原理，那么就是这个。下面我们将会看到利用这个性质在协议所发挥的作用。

值被决定的定义

实际上我们不能等所有进程都认为v是同个值，才认为v的值被决定。这样一旦有一个进程挂了，v的值永远就无法被决定。这里我们直接给出v的值被决定的定义：当法定集合的进程，令v为某个相同的值，比如都是c，那么称v的值被决定为c。一旦变量v的值被决定为c，那么不会再有另外一个不为c的值被决定，Paxos通过保证这个性质来解决一致性问题，这也称为安全性。

进程的平等假设

我们认为进程之间是互相平等的，这代表了每个进程都能令v为某个值，假设为c，并尝试令其它进程v的值也为c，也不存在一个上帝进程。正因为没有一个进程是特殊的，所以才不会因为单个进程而导致协议无法进行下去。

安全性和进程的平等假设所导致的冲突

假设进程全集为p1，p2，p3。p1令v=c并成功令p2.v=c，那么根据定义，v的值被决定为c。如果此时p3令v=d，接着尝试令p2.v=d，如果最后p2.v=d，值d已经符合了被决定的要求，这破坏了安全性。如果能够保证p2必然拒绝p3，那么这一切就不会发生，下面论述并不现实。为了让最终总有一个值被决定，一个进程不能只接受一个值，不然只要每个进程都赋予本地v不同的值，比如上面的例子在p1令p2.v=c之前，p2自己令v=e，由于只能接受一个值，p2拒绝了p1，此时p1.v=c，p2.v=e，p3.v=d且每个进程不再更改v的值，一致性无法达成。对于这种一致性总能达成的要求称之为活性。既然出于活性的要求，一个进程必然能接受多个值，那么显然总存某些情况下p3无法拒绝p2令p3.v=d的。既然我们无法保证p2总能拒绝p3，那么剩下唯一的办法就是当v的值被决定为c后，阻止p3令自身的v=d，强制p3.v=c。由此我们可以导出一个结论，一旦变量v的值被决定为c，尽管一个进程pi尚未给v赋值，但是pi已经没有了给变量v随意赋值的自由，pi只能选择值c赋予给变量v。

pi如何得知v已经被决定了或者如何选择值c赋予给变量v呢，一个最傻的办法是pi向其它所有进程询问你是不是已经给v赋值了，值是多少。收集到所有结果后，pi根据v的值被决定的定义自然可以判定v的值已经被决定并且被决定为c。这种策略的问题在于，进程是可能崩溃的，例如进程pj崩溃了，那么pi还要不要等待pj的回复呢，不等待，当整个集合只有三个进程pi，pj，pk，且pk和pj记录了v=c时，pi由于无法判定pj是否记录了v=c，因此无法直接判定v的值是否被决定，强行判定不满足安全性；等待，pj崩溃后如果没有恢复，pi就会一直等待，不满足活性。这个策略是不可行的，下面我们稍微改动一下这个策略。

我们假设v的值已经被决定为c，根据变量v的值被决定的定义，存在一个法定集合Q1，Q1中每个进程都记录了v=c。我们让进程pi向一个法定集合（而不是全部进程）Q2中的每个进程询问v的值，这样少数派的进程崩溃协议依然可以运转下去，当然这会存在难以判定v的值是否被决定的情形。根据法定集合性质，Q1和Q2必然至少有一个公共的进程p。p记录了v=c，p告知pi：v=c，存在这样的情形：Q2中有另一个进程pk告知pi：v=d，关键的问题是为何pi要相信p，而不是相信pk，从而挑选p记录的值赋予给变量v，这个问题称之如何选值。

上面我们已经明确了这样一步：一个进程pi需要先向一个法定集合中的每个进程询问它们保存的v的值，这一步称为询问，再从中挑选某个进程v的值作为自己的v的值。考虑v的值还未被决定时的情形，比如初始时，询问的结果会是没有一个进程v的值已被确定，显然这个时候进程pi需要有自由赋予变量v任何值的权利。因此我们规定，当pi完成询问后，如果法定集合中的每个进程告知pi它们都未给v赋予值，那么pi有自由赋值的权利。随之产生的问题是，如果有两个进程pi，pj同时获得了自由赋值的权利，如何保证安全性。考虑如下的情形，当获得自由赋值的权利后，pi令v=c，pj令v=d，pi试图向一个法定集合Q3写入v=c，pj试图另一个法定集合Q4写入v=d，使得v的值被决定，同时Q3和Q4必然至少有一个公共成员q2。为了安全性，我们必须保证pi和pj中只有一个的写入企图能够实现。为了保证这一点，作为公共成员的进程q2能够只接受一个进程的写入，拒绝掉另一个进程，q2总是需要一些东西来作为拒绝的依据，这个问题我们称之为如何拒绝。

提议者和接受者

为了满足安全性，上面遗留了两个重要问题，如何选值和如何拒绝。为了让描述更清晰，我们赋予进程两种角色，提议者（Proposer）和接受者（Acceptor）。提议者负责处理如何选值，接受者负责处理如何拒绝，显然一个进程可以同时有两种职能，顺便我们总结下两者的职责。
提议者：提议者首先向接受者进程进行询问，得到一个法定集合的进程的回复后，如果法定集合的进程均未给v赋予值，那么提议者拥有自由赋值的权利，不然提议者从回复中选择一个值赋予给v。当询问结束后，提议者选择或者自由的给v赋予某个值，例如c后，提议者尝试将v=c写入到一个法定集合的进程，从而令v=c被决定。不防令接受者角色负责写入v的值。我们将这种提议者进程尝试令接受者写入自身v的值的行为叫做提议，这个过程中提议者发送给接受者的消息称之为提案，显然提案中包括了提议者自身的v的值。
接受者：接受者负责处理提议者的询问和提议。上面我们已经导出接受者必须有能力拒绝提议者的提议才能保证安全性。

如何拒绝

回顾一下这个场景：提议者pi，pj在询问之后，都获得了自由赋值的权利，对于变量v，pi尝试让法定集合Q3的接受者们接受提案pq1（令v的值为c)，pj尝试向法定集合Q4的接受者接受它的提案pq2（令v的值为d)。
Q3与Q4至少存在一个公共的接受者q2，上面我们已经得出关键之处在于进程q2必须能够拒绝掉其中一个提议者的提案。目前我们的流程并没有提供任何信息让q2能够做到这一点，提案中只包括了提议者建议的v的值。至少我们需要一些信息来区分两个提案，最简单的方式是用一个唯一的数字来标识这个提案，不妨称为proposer-id。那么一种简单的策略是：q2根据提案proposer-id的大小从pq1和pq2当中选择一个接受，不妨选择proposer-id大的议案来接受。我们令接受者q2用变量a-proposer-id记录它接受过的提案的proposer-id，如果一个议案pq的proposer-id>a-proposer-id，那么接受者q2接受这个提案，并更新a-proposer-id=pq.proposer-id。不防假设pq1.proposer-id>pq2.proposer-id，有两种情形：
(1) q2先收到提案pq1
(2) q2先收到提案pq2。
情形一，显然q2将拒绝后到的提案pq2；但是对于情形二，q2接受pq2后也会接受后到的提案pq1，这违背了我们的目标（拒绝其一）。根据我们目前为止的规则，看起来似乎没有办法解决这个问题，情形二中q2无法拒绝pq1，但是如果q2能够拒绝pq2呢？这也符合我们的目标。q2如何拒绝pq2呢？如果q2收到提案pq2时，接受者q2.a-proposer-id=pq1.proposer-id，那么就能做到这一点。然而q2并未收到议案pq1，如何能令q2.a-proposer-id=pq1.proposer-id？显然只有提案pq1的提议者p1能够预先知道pq1的proposer-id，而p1在提议之前，还有一个询问阶段，只要在询问阶段提议者p1告知接受者q2它在提议阶段将提出的议案的proposer-id，q2记录下这个proposer-id，那么就可以做到这一点。我们将询问阶段提议者发送给接受者的消息称之为预提案，预提案包含了即将发送的提案的proposer-id，它的作用是告知接受者在下一阶段该提议者的提案的proposer-id。
整理一下上面说述，接受者在收到提议者的包含proposer-id的预提案后，会设置它的a-proposer-id=proposer-id。如果接受者每接受一个预提案，就更新它的a-proposer-id，那么对于上面的例子中的情形二，无法保证收到pq2时，q2.a-proposer-id=pq1.proposer-id。例如q2收到请求的顺序如下：
(1)接受者q2收到提议者pi的预提案ppq1
(2)q2收到另一个提议者pj的预提案ppq2
(3)q2再收到pj的提案pq2
此时q2.a-proposer-id=ppq2.proposer-id=pq2.proposer-id。而我们希望无论ppq1和ppq2的到达顺序如何，q2收到pq2时，q2.a-proposer-id=ppq1.proposer-id=pq1.proposer-id。我们已知ppq1.proposer-id>ppq2.proposer-id，因此自然的我们只要对更新操作加一个前置条件：对于一个预提案ppq，当接受者q.a-proposer-id<ppq.proposer-id时，才更新q.a-proposer-id=ppq.proposer-id；也就是说无论是提案还是预提案，接受只接受proposer-id比它自身的a-proposer-id更大的消息。现在即使q2后收到pj的预提案ppq2，由于此时q2.a-proposer-id=q1.proposer-id>q2.proposer-id，将拒绝预提案ppq2。考虑如下的情况，提议者发送预提案ppq给接受者q，q尚未接受任何预提案和提案，故q.a-proposer-id=ppq.proposer-id，系统中不存在其它提议者，因此pq收到法定集合的接受者回复后发送提案pq给接受者q，由于此时pq.proposer-id=ppq.proposer-id=q.a-proposer-id，而我们之前的约束要求pq.proposer-id>q.a-proposer-id，这会导致q拒绝提案pq，只存在一个提议者的系统，提议者的提案竟然无法被接受，这显然不合理，为了这种情况下q能接受pq，修改接受者接受提案的约束为pq.proposer-id>=q.a-proposer-id。上面我们已经彻底保证如果提议者pi和pj在询问之后都获得了自由赋值的权利，无论接受者q2以如何的顺序接受到它们的预提案和提案，q2只会接受它们中一个的提案。显然p1和p2可以是任意两个进程，c和d可以时任意两个值，因此目前为止协议已经保证如下的一点：任意时刻，就算存在多个提议者在询问之后提出了不同的值的提案，最终只有其中一个提议者的提案中的值将会被法定集合的接受者接受，即只有一个值能够被决定。
回顾下目前为止我们的协议对于如何决定变量v的值的流程：

提议者：
询问：询问法定集合的进程自身v的值
预提议：发送包含自身proposer-id的预提案给法定集合接受者
提议：发送的预提案得到一个法定集合接受者的回复后，如果询问的结果是法定集合的接受者均未给v赋予值，那么提议者拥有自由赋值的权利，不然提议者从中选择一个值赋予给v。假定自由赋予或者选择的值为c。发送包含c和proposer-id的提案给接受者。

接受者：
处理询问：回复自身v的值
处理预议案：如果收到的预提案ppq.proposer-id>a-proposer-id，那么更新a-proposer-id=ppq.proposer-id，接受这个预提案，不然则拒绝这个预提案。
处理提议：如果收到的提案的pq.proposer-id>=a-proposer-id，那么更新a-proposer-id=pq.proposer-id，接受这个提案，记录v的值为提案中的值，即v=pq.c。
提议者需要得到一个法定集合接受者的回复预提议，同时回复询问后才进行选值，询问和预提议都是向法定集合进程发送消息并获取回复，因此可以把询问和预提议合并，预提案附带了询问功能。这就要求接受者在处理询问时，如果根据规则接受预提案，就会回复一个消息给提议者，称这个消息为诺言，诺言中包含了接受者记录的v的值。似乎我们只剩下了最后一个问题，如何选值。

如何选值

上面我们已经论证了当变量v的值被决定为c时，提议者pi在询问阶段收到的法定集合Q2的接受者的回复中，必然存在一个接受者q2回复了它记录了v=c。选值的关键在于我们从什么地方来判断q2记录的v的值c才是v被决定了的值。接受者必须向提议者提供额外的信息来使得提议者有能力做出这种判断。我们重新回到v的值被决定的定义，v的值被决定为c，代表存在一个法定集合Q的接受者，记录了q.v=c。由于我们上面已经丰富了我们的协议，所以此时接受者还在变量a-proposer-id中记录了接受的提案的proposer-id。我们假设是提案pq最先另q.v=c，由提议者p在提议阶段提出。那么v被决定为值c后，Q中每一个接受者:q.v=c，并且可以论证q.a-proposer-id >=p.proposer-id。论证如下：
当q接受议案pq时，q.a-proposer-id=pq.proposer-id=p.proposer-id。而q.a-proposer-id更新的条件是pq.proposer-id>=q.a-proposer-id和ppq.proposer-id>q.a-proposer-id，故q.a-proposer-id单调递增，故结论成立。

假设pi收到的来自法定集合Q2接受者的诺言中，其中一个接受者qj回复的诺言记录了v=d != c。此时，pi要如何相信q2回复的值c才是v被决定的值而不是qj回复的值d？我们的目的是找出一种策略，不妨称这种策略为cl，策略cl使得当v的值被决定为c后，pi能够从收到的来自Q2的诺言集合中，挑选出v=c的诺言。不妨假设是提议者pj提出议案pqj令qj.v=d，pj向法定集合Q3发送预提案和提案。由于我们已经引入了预提案阶段，一个提案pq被提出，代表存在一个集合Q，对于Q中的任意一个进程q.a-proposer-id>=pq.proposer-id。这一点论证非常容易，pq被提出，代表存在一个集合Q,Q中的接受者q收到了预提案ppq,并接受了它。由于一个接受者q接受预提案的条件是q.a-proposer-id<ppq.proposer-id，且会更新q.a-propposer-id=ppq.proposer-id，同时只有收到的其它提案或预提案的proposer-id大于q.a-proposer-id，q.a-proposer-id才会更新，即q.a-proposer-id是单调递增的，故Q中每个接受者q.a-propsoer-id>=ppq.proposer-id=pq.propser-id,得证。根据这个结论，我们可以得知对于Q3中任意一个接受者q,q.a-proposer-id>=pqj.proposer-id,又知存在一个法定集合Q，Q中任意一个接受者q都接受了决定v的值为c的提案pq，而Q3和Q至少存在一个公共接受者qk，qk接受了提案pq，又收到了预提案ppqj。我们假设（pqj.proposer-id=ppqj.proposer-id）>pq.proposer-id。有两种情况：
(1)如果qk先收到预提案ppqj，那么代表qk收到pq时，qk.a-proposer-id>=ppqj.proposer-id>pq.proposer-id,qk就会拒绝pq，与Q中每个q都接受了pq矛盾。
(2)如果qk先接受了提案pq，再接受预提案ppqj，那么qk会回复一个包含v=qp.v=c的诺言给qj，即提案pqj的提出在v的值被决定后。