Paxos算法简介

本介绍是 Paxos Made Simple 的中文说明。会摘录一些原来的段落讲解。如果大家发现有问题的地方，参照原文。说明中部分内容摘自维基百科。
Paxos Made Simple 是因为最初的论文比较难懂，作者又写了这篇比较形象好懂的介绍。首先要明确的是 Paxos 算法，是为了解决分布式环境下一致性的问题而提出的算法。这里将牺牲一些严格性，采用比较好懂的具体例子对文章加以解读。

注意：对这个说明进行理解的时候要先理解这个过程方法：目的是在分布式环境里解决一致性问题。那么先提出了两个约束。只要保证着两个约束就保证了问题解的 正确性。但是因为开始的约束很难实现，于是对约束进行加强(满足了加强了的约束就一定满足原来的约束。比如我们提的一个约束是明天的约会对象必须是个人， 然后对这个约束做了一次加强，加强成明天的约会对象必须是个女人)，最终找到可以实现的一组约束。

原文提出了一个问题，如何选择一个值。这里形象化成一个更实际的问题，如何确定一把锁的归属。假设一个场景，一个唯一资源被一把锁保护着，现在又很多分布 在不同主机上的进程开始争用这把锁。不妨让争用锁的进程分别是S1，S2，S3……。 锁名称L1. 那么回归到原文的例子上，就是对变量L1选择一个值，可能值为(S1,S2,S3….). 当然，最简单的办法是用一个单一进程来实现，S进程向其申请锁，谁先到归谁。这样的结果是，系统产生了一个单点瓶颈。那么我们现在考虑用一个小集群如何来 实现。这个小集群有一些要求：其中任何一台机器可能失效，但是这台机器恢复回来的时候，应该是有记忆的，就是说，能找到其失效前的一些必要数据。
首先介绍两种角色，提案者和批准人。提案者是提出议案的，批准人进行批准。注意，本文只介绍这两者之间的交互关系，不介绍 learners。一个进程可以身兼多种角色。
现在再假设批准人有5个，组成了一个小的集群（A1-A5）。S系列的进程是提案者，他们希望的提案就是自己占有锁资源。比如S1的提案是L1 = S1。 S2的提案是 L1 = S2 …… 他们其实是同一个提案，就是对L1取值的提案。只是各个S进程提案的value不一样。显然，只有一个提案可以获得通过，那么5个批准人的集群如何确定谁 获得通过呢？简单来说，少数服从多数。就是获得超过半数批准人支持的提案获胜。我们称超过半数的一群批准者为一个多数派。因为两个多数派至少有一个批准者 是重叠的。所以只要我们约定，一个批准者只能批准一个提案。那么我们就可以保证不会产生1个以上提案被批准的情况了。也就是说L1不会取得超过一个的值。 因为要求一个提案者提出唯一提案的时候也要接受。就是说，S系列进程只有一个要求锁资源，这当然要接受的。所以我们有要求：
P1 一个批准者必须接受他收到的第一个提案。
这产生一个问题，当几个S进程一起要求锁的时候，可能每个批准者批准了一个。从而无法形成多数派。即便只有两个S进程提出锁要求，假设我们的5人集团当掉 一个，剩下四个有两个同意S1，有两个同意S2，还是形不成多数派。问题还是无法解决。这种情况实际上要求一个批准者应该可以批准超过一个的提案。慢着， 如此一来，谁请求都批准那不是没有一样吗？所以还要有限制。为了方便，让我们把每个提案者提出的提案进行编号。每个提案者的编号不同，而且编号是偏序的。 具体实现随意。在我们的例子里，就先用机器名加变量名S1_L1，S2_L1来作为提案的编号。当多数派批准一个提案比如S1_L1（提案S1_L1在我 们的例子中应该是L1 = S1）的时候，值被选定，提案被通过（注意“通过”这个词，后续中，对于经过多数派批准的生效的提案，我用“通过”这个词）。我们允许多个提案被通过，只 要他们提案的值是一样的。比如S1_L1被通过之后，如果机器S2提出提案S2_L1，要求把锁给S1（S2_L1:L1=S1）那么这个提案应该也被通 过。当然我们的例子里，S2是不会这么干的。那么有下面的要求
P2 一个值为V的提案被通过了，那么编号比这个提案大的提案通过的条件是提案的值是V。
因为一个提案被通过，那么至少要被一个批准者批准。所以我们可以对P2做加强。
p2a 一个值为V的提案被通过了，那么编号比这个提案大的提案被批准的条件是提案的值是V。
请注意p2和p2a的区别，别糊涂了。
注意，这里又有一个问题，假设S1_L1提案被A1,A2,A3批准，从而获得了通过。现在S2提出提案S2_L2，提给了A5.A5跟据P1的要求，应该批准该提案，但是这是违反p2a的。所以我们需要对p2a继续加强
p2b 一个值为V的提案被通过了，那么编号比这个提案大的提案的值应该是V。
只有被提出的提案才可能被批准，我们规定了提出的提案的值应该是V，自然保证了被批准以及被通过的值。所以P2b蕴含了p2a和p2.那我们的例子来说，一旦L1的值被确定了，后续的提案只能同意。
p2b 难以实现。这里我们引入另一个约束
p2c 提出一个编号为n具有值v的提案的前提是：存在一个多数派，要么他们中没有人批准过编号小于n的任何提案，要么他们批准的提案中编号小于n的最大的提案值是v。
下面通过数学归纳法证明p2c蕴含了p2b：
假设具有值 v 的提案 m 获得通过，当 n=m+1 时，根据 P2c，由于任何一个多数派中至少有一个批准了 m，因此提案n具有值 v；若 (m+1)..(n-1) 所有提案都具有值v，根据 P2c，若反设新提案 n 不具有值v 则存在一个多数派，他们没有批准过 m..(n-1) 中的任何提案。但是我们知道，他们中至少有一个人批准了 m。于是我们导出了矛盾，获得了证明。也就是说，只要满足p2c，那么p2b就得到满足。
以上这么啰嗦的一堆，其实是证明了，只要保证了p2c，我们就能保证选出唯一值。那么下面看如何设计算法保证p2c。
保证p2c的关键问题，其实是要批准者做出不批准某种类型提案的承诺。所以：提案者提出一个提案前，首先要和足以形成多数派的批准者进行通信，获得他们进 行的最近一次批准活动的编号，并且得到他们不批准比当前提案编号小的提案的承诺（prepare 过程），之后根据回收的信息决定这次提案的 value，形成提案开始投票。当获得多数批准者批准后，提案获得通过。这个简略的过程经过进一步细化后就形成了 Paxos 算法。

如果一个批准者在 prepare 过程中回答了一个编号为n的提案，但是在开始对 n 进行投票前，又批准另一个提案编号小于n的提案，如果两个提案具有不同的 value，这个批准就会违背 P2c。因此在 prepare 过程中，批准者对于不会再批准编号小于 n 的提案的承诺是保证算法正确的基础。所以又有一个对 P1 的加强：
P1a：当且仅当批准者没有收到编号大于 n 的提案请求时，批准者批准编号为 n 的提案。

现在已经可以提出完整的算法了。

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

1. prepare 阶段：
1. 提案者选择一个提案编号 n 并将 prepare 请求发送给批准者中的一个多数派；
2. 批准者收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则批准者将自己上次的批准回复给提案者，并承诺不再批准小于 n 的提案；
2. 批准阶段：
1. 当一个提案者收到了多数批准者对 prepare 的回复后，就进入批准阶段。它要向回复 prepare 请求的批准者发送批准的请求，包括编号 n 和根据 P2c 决定的 value（如果根据 P2c 没有决定 value，那么它可以自由决定 value）。
2. 在不违背自己向其他提案者的承诺的前提下，批准者收到批准请求后即批准这个请求。

这个过程在任何时候中断都可以保证正确性。

这个算法的正确性和完备性就是上面的证明。但是为了便于理解，我们可以用我们上面的例子来描述一个决议过程。这个描述仅仅是便于大家理解。描述中有一些在实际算法上不合适的地方，这里不考虑。

批准者是A1-A5.申请者是S系列。提案是决定L1的取值。

首先S2提出编号是0001S2的提案内容是L1=S2.我们采用 提案者:编号[值]这种记录方式记做 S2:0001S2[S2]。它要先进行prepare阶段，于是向A1，A2，A3，A4发送了请求。

同时S1提出S1:0001S1[S1]，发给A1-A5.进行prepare。

我们来看这5个A的回复：我们用 批准者[收到的提案：给出的回复]这个格式来描述一下A系列的行为。回复有三种1 ok表示做出承诺（没有做出批准的时候）2 null表示没有给回复（提案编号比承诺过的编号小）3value表示做出承诺，同时给出value（已经做出过批准的时候）

A1[0001S1:ok] [0001S2:ok] A1先接到s1的prepare请求，做出了承诺，又接到s2的请求，做出了承诺 现在A1的承诺是不批准<0001S2 A1要记住他的承诺和值 记做 A1-(0001S2,null)

A3[0001S2:ok] [0001S1:null] A3-(0001S2,null)

A2[0001S1:ok] A2-(0001S1,null)

A5[0001S1:ok] A5-(0001S1,null)

注意，到此时，S1已经收到了一个多数派的回复(A1,A2,A5) A3因为违反承诺，没有给S1回复。这时S1开始批准阶段的请求,其中提案的值是S1（因为prepare阶段没有批准者返回值）。请求顺序是 A5，A4，A3，A2，A1（A3虽然没有给回复，但是是可以向它发批准请求的。算法优化的问题现在不讨论，只讲正确性）。那么这个时候的回复应该是什 么样呢？

A5[0001S1:ok] A5要记住当前的提案编号是0001S1 value是S1。记做 A5-(0001S1，S1)

A4 我们假设A4由于网络原因，没有收到prepare阶段的请求，直接受到了批准阶段请求。按照规则，他应该做出批准，并且记住状态

A4[0001S1:ok] A4-(0001S1，S1)

A3 已经做出承诺不能批准所以不回复

A3[0001S1:null] A3-(0001S2,null)

A2[0001S1:ok] A2-(0001S1,S1)

已经达到多数派，提案通过，A1其实不会给出回复。不过没关系了。现在我们再看后来的提议者S2. S2向A1，A2，A3，A4发出请求，到目前为止，只有A1,A3收到了请求。我们继续推演后续的A收到请求的反应。

假设现在A4收到请求 考虑A4的状态A4-(0001S1，S1) 因为新的提议编号更大，所以A4要回复给S2提议的值,状态不变

A4[0001S2:S1] A4-(0001S1，S1)

A2[0001S2:S1] A2-(0001S1，S1)

这个时候S2妄图提出值为S2的提案的企图没能得到多数派的同意，不会进入批准阶段了。

————————————————————————–

这个例子只是形象的看了一下算法是如何工作的。实际算法的正确性和完备性是上面的证明过程。这种举例只是为了帮助形象化理解，有兴趣的同学可以自己再推演 一下其他情况，比如S2胜出，比如S1在得到多数派prepare ok后 只向两个A发出了批准请求然后挂掉等情况。

真正在做算法实现的时候还是有一些注意的事情的，比如我们假设一个比价极端的情况，S1在prepare时候向A1-A5发申请，都得到了回复。然后S2 也发了一遍申请，当然也都得到回复，这个时候S1发出提案，实际上是得不到回复的。现在假设S2突然挂掉。那么对于我们的例子，没人得到锁。如果是用来选 master，到现在还没人是master。这个时候S1应该再做一次提案采用更大的一个编号（这就是为什么我的例子中，提案编号前面是几位的序号）。但 是这样实现，又面临着S1，S2交替增大编号，谁也得不到批准的问题。这些问题都是需要注意的（实现的时候足够注意就可以解决）。这些不属于本文讨论内 容，这里只是提醒一下。