分布式系统——Paxos算法推导

Paxos算法是Leslie Lamport于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。

一、一切的源头

下面就是著名的拜占庭将军问题，由Lamport 1982年提出：

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

系统的问题在于，将军中可能出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。

但是在分布式计算领域中，大多分布式系统都是在局域网进行的，所以消息被篡改十分罕见，另一方面，硬件和网络造成的不完整性使用简单的校验算法就可以解决，所以实际工程中，可假设不存在拜占庭将军问题。

如果在消息完整没有被篡改的情况下，如何保证算法的一致性呢？

又是Lamport在1990年提出了一个理论上的一致性解决方案。

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

二、Paxos算法论述与证明

Paxos算法的目的:保证最终有一个提案会被选定，当提案被选定后，其他进程最终也能获取到被选定的提案。

算法提出

首先将议员的角色分为 proposers，acceptors，和 learners（允许身兼数职）。proposers 提出提案，提案信息包括提案编号和提议的 value；acceptor 收到提案后可以批准（accept）提案，若提案获得大多数（majority）的 acceptors 的批准，则称该提案被选定（chosen）；learners 只能接受被选定的提案。

更加精确的描述问题：

决议（value）只有在被 proposers 提出后才能被选定,未经选定的决议称为提案（proposal）；
在一次 Paxos 算法的执行实例中，只选定（chosen）一个 value；
learners 只能获得被选定（chosen）的 value。

以上是对各个名词的描述，作者通过不断加强上述三个约束来获得Paxos算法。然后我们看一下Lamport原文对问题的描述：

一致性算法需要保证的几点：

提案中只有一个会被选定。
如果没有提案提出，就不会有被选定的提案。
当一个提案被选定后，进程应该可以获取选定的提案信息。

一致性算法最重要的两个属性是安全性（Safety）与活性(Liveness)。
1.安全性是需要保证永远都不会发生的事情。
2.活性是指那些最终一定会发生的事情。

这里安全性需要保证如下几点:

只有一个值被选定
只有被提出的提案才能被选定
如果某个进程认为某个提案被选定，那么这个提案必须是真的被选定那个。

活性不需要精确定义

因为Paxos最终会保证有一个议案被选定，之后线程也能获取到该议案。

推导过程

首先要选择一个提案最简单的方式是，就一个acceptor,默认将接收到的第一个提案作为被选定的提案。简单是简单，就是怕这个acceptor被刺杀了，系统就挂了。

所以我们要看多Acceptor的情况。只要足够多的Acceptor选定，就认为该提案被选定。足够多的Acceptor是整个集合的子集，任意两个足够多的集合交集都不为空。

然后我们继续规定每个Acceptor都只能批准一个提案，这样就能保证只有一个提案被选定了。

正式处理

阶段一：

如果我们希望只有一个提案被提出的情况下也应该被选定（Paxos最终的目标就是保证一个提案被选定），就有下面的要求：

1 2	P1:一个Acceptor必须批准它收的的第一个提案。 An acceptor must accept the first proposal that it recevies.

但这个约束缺陷明显。

看看，即使每个Acceptor都批准了第一个提案，结果还是没有一个提案被足够多的acceptor批准。

然后还有这种情况，右面的提案被多个acceptor批准了结果，审判者5被敌军刺杀，结果又没有提案被足够多的acceptor批准。

阶段二：

我们知道一个提案如果要被选定，需要足够多的acceptor接受，也就是1半以上，但P1又规定了必须接受第一提案，所以可以推导出一个acceptor可以批准多个提案。并且给不同的提案不同的有序编号，一个提案由编号和值组成，并且任意两个提案的编号不同。

基于上面描述，我们允许多个提案被选定，但Paxos算法的大前提是只有一个值被选定，所以这些被选定的提案必须有相同的value。

在P1的基础上增加条件：

1
2

P2:如果编号为M0、Value值为V0的提案[M0,V0]已经被选定，那么比M0编号更高的，且被选定的提案value一定是V0。
If a proposal wiht value v is chosen, then every higher-numbered proposal that is chosen has value v.

我们知道，如果提案想被选定那么必须被至少一个acceptor批准。所以可以在P2的基础上继续延伸。

1
2

P2a:如果编号为M0、Value值为V0的提案[M0,V0]已经被选定，那么比M0编号更高的，，且被批准的提案value一定是V0。
If a proposal whth value v is chosen, then every heigher-numbered proposal accepted by any acceptor has value v.

由于分布式系统是异步的，而且此时P1是成立，如果有一个提案[M1,V0]（右侧提案）已经被选中，此时另一个proposer被唤醒，产生了一个编号更大的提案，并且值也不是V0，而acceptor1还没有接到提案，这个被发过去提案一定会被接受，此时与P2a我约束违背，所以我们要对P2a进行加强。

1
2

P2b:如果[M0,V0]被选定后，那么之后Proposer产生的编号更高的提案，其值一定是V0。
If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

P2b是包含P2a的，因为一个提案一定是被提出后才会被批准，因此P2b也包含P2。

但是根据 P2b 难以提出实现手段。因此需要进一步加强 P2b。

假设一个编号为 M0 的 value V0 已经被选定（chosen），来看看在什么情况下对任何编号为 Mn（Mn>M0）的提案都含有 value V0。因为 M0 已经被选定（chosen），显然存在一个 acceptors 的多数派 C，他们都接受（accept）了V0。考虑到任何多数派都和 C 具有至少一个公共成员，可以找到一个蕴涵 P2b 的约束 P2c：

1
2
3

P2c:对于任意的Mn和Vn，如果提案[Mn,Vn]被提出，那么肯定存在一个由半数以上的Acceptor组成的集合，满足下面任何一个条件
- S中不存在任何批准过小于编号Mn的提案的Acceptor。
- 选取S中所有的Acceptor批准的编号小于Mn的提案，其中最大的那个提案的Value是Vn

使用数学归纳法证明P2c蕴含P2b

第二数学归纳法原理是设有一个与正整数n有关的命题，如果：
①当n=1，2时，命题成立；
②假设当n≤k（k∈N）时，命题成立，由此可推得当n=k+1时，命题也成立。
那么根据①②可得，命题对于一切正整数n来说都成立。

使用第二数学归纳法证明以下结论：

1	假设编号在M0到Mn-1之间的提案，其值都是V0，证明编号为Mn的提案Value值也是V0。

因为编号为M0的已经是被批准的提案，所以一定存在半数以上的Acceptor组成的集合C，C中的每一个Acceptor都批准了该提案。如果要让Mn的value也是V0，那么需要满足下面条件。

证明：

假设[M0,V0]提案被批准，当M1=M0+1时，采用反证法，假设提案M1的值不是V0，而是V1。

根据P2c存在一个足够多的集合C1，要么他们中没人批准过编号小于M1的任何提案，要么C1中所有被批准的小于M1的提案Value都是V1，然而这与[M0,V0]是不符合的，所以M1的值一定是V0

若M1到Mn-1的值都是V0，加入新的提案Mn的值是Vn，根据P2c，存在一个足够多的集合Cn中要么没有批准过M0到Mn-1中的任何提案，要么批准的提案中最大编号的value为Vn。我们现在指导M0曾被选定，而根据最初假定M1到Mn-1的值都是V0，所以批准的最大编号的提案value一定是V0，至此产生矛盾，所以Mn的值一定是V0。

所以得出结论，若P2c成立，那么P2b成立。

所以现在我们已经可以推导出：

P2c->P2b->P2a->P2;然后就可以用P2、P1来保证一致性。

对于P2c，我们可以规定每个Proposer如何产生提案：对于产品的每个提案[Mn,Vn],需要满足如下条件。

1
2
3

存在一个超过半数的Acceptor组成的集合S:
	- 要么S中没有Acceptor批准过的编号小于Mn的任何提案
	- 要么S中所有的Acceptor批准的所有编号小于Mn的提案中，编号最大的那个提案的Value值为Vn。

提案生成算法

Proposer选择一个新的提案编号Mn，然后向某个Acceptor集合的成员发送请求，要求该集合中的Acceptor作出如下回应。
- 向Proposer承诺，保证不再批准任何编号小于Mn的提案
- 如果Acceptor已经批准过任何提案，他就向Proposer反馈当前该Acceptor已经批准的编号小于Mn但为最大的编号那个提案的值。
如果Proposer收到来自半数以上的Acceptor的响应结果那么它就可以产生编号为Mn，值为Vn的提案，这个Vn是所有的相应中编号最大的Value值。如果半数以上的Value都没有批准过任何提案，那么Value为任意值。
在确定提案后，Proposer会将该提案发送给某个Acceptor集合，这里是发送Acceptor请求，并期望获得批准。这里的集合未必是之前相应

提案批准方案

Acceptor会接收到两种请求，分别是Prepare请求，另一种是Acceptor请求。

Prepare请求：Acceptor可以在任何时候响应Prepare请求

Acceptor请求：在不违背Accept现有的承诺前提下，可以任意相应Acceptor请求。

可以对P1进行扩展

1	P1a:一个Acceptor只要为响应过任何编号大于Mn的Prepare请求，那么他就可以接收这个编号为Mn的提案。

算法的陈述

上面已经将算法的推倒阐述完毕，下面对算法进行一下陈述。

阶段一：

Proposer选择一个提案编号为Mn，然后向Acceptor的某个超过半数的子集成员发送编号为Mn的Prepare请求。
如果一个Acceptor收到一个编号为Mn的Prepare请求，且编号Mn大于该Acceptor已经响应的所有Prepare请求的编号，那么它会将批准过的最大编号的value值响应给Proposer,同时该Acceptor不会再批准任何编号小于Mn的提案。

阶段二：

如果 Proposer收到来自半数以上的Acceptor对于其发出编号为Mn的Prepare的响应，那么它就会发送一个[Mn,Vn]提案给Acceptor集合，Vn是收到响应中编号最大的提案值，如果响应中不包含其他值，则为任意值。
如果Acceptor收到的Acceptor请求，只要该Acceptor未对编好大于Mn的Prepare请求做出响应，他就可以通过这个提案。

值得一提的是，每个Proposer都可能产生多个提案，并且提案可能会丢失，但只要遵循上述规则，就不会出错。

提案的获取

上面是Proposer和Acceptor来选定提案，下面介绍Learner如何获取提案。

方案一：

Acceptor批准一个提案，然后将提案发送给Learner,但是需要每个Acceptor与所有Learner进行通信，通信次数是Acceptor与Learner的积。

方案二：

Acceptor统一与一个主Learner通信，主Learner与其他Learner通信，但是主Learner可能会出现故障。

方案三:

解决单点问题就是将主Learner扩展为一个Learner集合，Acceptor将批准的提案发送到特定的集合。

三、总结

本文概述了Paxos算法推导过程进行了描述，paxos算法在分布式一致性中得到广泛的应用。谷歌公司（Google公司）在其分布式数据库spanner中使用Multi-Paxos作为分布式一致性保证的基础组件，Apache ZooKeeper 使用一个类Multi-Paxos的一致性算法作为底层存储协同的机制。

重点在于不要在推导时忘记Paxos算法是为了选出一个最终提案的算法。

参考资料：

1.Paxos Made Simple

2.从Paxos到Zookeeper,倪超