Paxos算法原理与推导

发表于 | 分类于

一、Paxos介绍

我们常见的分布式系统中，总会发生网络异常（包括消息的延迟、丢失、重复、乱序，还有网络分区）、机器宕机等异常情况。如何才能保证在发生诸如此类问题的情况下，快速且正确的在集群内部对某个数据的值达成一致，不会破坏系统的一致性，这就需要Paxos算法的支撑。

Paxos算法是莱斯特-兰伯特与1990年提出的一种基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。接下来将一步一步推导Paxos，做到不仅要理解Paxos的选举步骤，更要理解推导证明过程。理解算法的核心和精髓，是对我们思想的一种锻炼，对以后工作中解决问题有一定的帮助。

二、背景&解决的问题

如上述提到，分布式系统中，如果出现网络异常（包括消息的延迟、丢失、重复、乱序，还有网络分区）、机器宕机等异常情况时，容易造成各个节点数据不一致的情况。如下图所示：

down

机器宕机、网络异常等，导致消息不可达等异常流程，会造成数据不一致的情况。比如未收到消息的节点与其他节点数据不一致，宕机机器重启后数据不一致以及恢复策略等。也就是面对如下异常问题时，算法需要保证的就是，对某个数据的值达成最终一致。

issure

三、概念&定义

3.1，角色类型

Paxos算法模型中定义了三种角色类型：

  1. Proposer，模型中的提议者，作用是提出建议。
  2. Acceptor，模型中的批准者，作用是针对提议者的提议进行接受批准。
  3. Learner，模型中的学习者，也就是会从批准者获取数据并应用。

role

需要注意的一点就是，模型中三种角色类型，并不是一开始就完全定死的。每一个节点并不止一种角色类型，可以即是提议者，又是批准者，还作为学习者获取数据应用。这一点理解起来不难，想象这么一个场景，Zookeeper集群中，在开始启动选主的过程中，每一个服务节点并不是单纯的提议者或者批准者（zk中节点类型并不是这么定义，但是核心算法是Paxos）。如下图所示，每一个node在发起自己的投票的时候为Proposer，接收到投票后做决策时为Acceptor（类似Acceptor）。

node_example

3.2，提案（Proposal）

Proposer提出请求，Acceptor针对此请求作出响应。这个由proposer产生的请求，我们称之为提案——Proposal。Proposal由两部分组成，提案编号和提案值。提案编号可以理解为Proposer发起提案的一个唯一标识；提案值则代表此次提案投票选定的值。为什么提案包含两部分内容（编号+值）？只有编号或者只有值可不可以？下面在算法的推导过程中，会具体讲解这些疑问。提案的表示定义为：Proposal(N,V)。

四、问题描述

假设有一组可以提出提案的进程集合，那么对于一个一致性算法来说需要保证以下几点：

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

相对于一致性的需求来说，算法的安全性定义如下：

  • 只有被提出的提案才能被选定。
  • 只能有一个值被选定。
  • 如果某个进行获取到某个提案被选定，那么这个提案必须是真正被选定的那个。

同时我们需要对问题的复杂性做一些定义：

  • 每个节点角色不是固定的，可能是Proposer、Acceptor、Leaner。
  • 每个节点运行的速率是不固定的，也就是在发起提案、作出决策的时间是不固定的。
  • 每个节点可能因为机器问题宕机、重启。
  • 消息在传输过程中由于网络问题丢失、重复、延迟。但是消息不会被损坏（发送和接受到的消息肯定是完全完整的）。

阐述完整体问题描述，接下来我们将针对此问题的算法进行推导。

五、 算法推导

要满足提出个提案有一个被选定，我们可以先假定只有一个Acceptor。当Proposer提出提案，并且此Acceptor收到提案，就批准该提案。这样不会出现到底哪个提案会被选定还是是否还存在商议的过程。但是这样也出现了一个问题，那就是当这个Acceptor挂掉宕机，那就失去了可靠性的保证，也就没有任何意义。

acceptor down

所以我们选定一组节点作为Acceptor，Proposer向一组Acceptor发送提案，那么我们就要讨论这一组Acceptor如何决议出最后一个提案。另外我们规定每一个Acceptor最多只能批准一个提案，那么就能保证只有一个提案被选定。

5.1，多个Accptor

为了使算法推导、理解简单，我们先假定有一组Proposer和一组Acceptor，两组角色定义不会更改（实际在系统运转过程中，每一个进程或者每一个节点，可能为Proposer或Acceptor）。Proposer组向Acceptor组发起提案，Acceptor组批准提案。如下：

mutil

Proposer集合中的每个节点向Acceptor集合中的每个节点发送提案请求，请求可能有延迟、重复、不可达，怎么保证批准一个提案呢？于是我们定义以下一个原则：

1
原则P1:一个Acceptor必须批准它接受到第一个提案。

基于此原则，Acceptor收到Proposer发出的提案，如果是第一个，则批准。这就保证了最后肯定会有提案批准成功。但是又产生了另外一个问题，那就是多个Proposer分别提出提案到不同的Acceptor，那么就出现了多个提案都被批准的情况，违背我们的安全性原则。

mutil_fail

或者出现如下异常case（其中一个Acceptor宕机，导致P1、P2提出的提案分别被相同数量的Acceptor批准）：

mutil_err_same

由于我们定了“Acceptor必须接受它接受的第一个提案”，但是上述两个异常情况，导致最终可能会有多个提案被选定，所以我们需要加一个规定：

1
规定：一个提案被选定需要被半数以上的Acceptor接受。

当Acceptor组中绝大多数Acceptor批准一个提案的时候，我们就认为这个提案被选定。绝大多数定义为本组Acceptor数量的一半以上，任意两个一半以上的子集肯定包含有至少一个公共成员Acceptor。因为这个规定，所以意味着每个Acceptor可能需要批准多个提案，不然类似上述异常case情况下，约束为每个Acceptor只能批准一个，那么最终不会有唯一一个最终提案产生。

5.2，提案(Proposal)&批准(Accept)升级

开始第一阶段我们的提案可以认为只是单纯的一个编号，Acceptor批准提案批准的只是这个提案的编号。但是由于提案的最终选定需要多数Acceptor批准，所以每个Proposer提出的提案，需要得到超过半数的Acceptor的批准，若没有超过半数，需要再次发起一次提案，这时就需要重新发起的提案更换提案编号。更换编号的策略，简单直接点就是每次每个Proposer产生一个新的提案，所属编号为全局递增。编号生成器规则这里不再阐述。

从Acceptor角度讲，由于允许可以批准多次提案，但是由于需要保证一个提案产生，所以需要对Acceptor的多次批准做一个限制，规定如下：

1
规定：一个Acceptor不能批准编号小于它已经响应过的所有提案中编号最大的编号值。

什么意思呢？假设Acceptor A，已经对收到的提案编号（4，5）作出过响应（Acceptor需要记录它批准过的提案中最大的提案编号），这时由于网络延迟等问题，来了一个编号为3的提案，A对这个提案直接返回error或者忽略这个提案。此时发出提案的Proposer收到了error或者没收到对它提案的响应（非ok的响应），那么也就意味着它丧失了对应Acceptor的表决。

我们通过从Proposer和Acceptor角度分析得出：

  1. 提案编号全局递增
  2. Acceptor可以批准多个提案但是不能批准编号小于它已经批准过的最大的提案编号

这样我们解决了一个提案怎么才能让大多数Acceptor批准的问题，但是并没有解决大多数Acceptor对所收到的提案达成最终一致的问题。继续从Acceptor和Proposer来看，我们可以得出，每个角色只是单独负责自己的职责功能，对彼此的交互并没有一个统一协调的进步。Acceptor只管负责批准提案，Proposer只管负责产生提案。所以我们就需要要求Acceptor和Proposer进一步加强交互，做到信息互通。

我们对Proposer产生的提案作出如下定义，Proposal由两部分内容组成，编号和值。也就是Proposal(N,V)。N代表本次提案的编号，V代表本次提案的值。提案的值V就是Acceptor和Proposer多次交互最终需要达成一致的值。

5.3，算法原则推导

上述提到，我们允许多个提案被选定，但是同时必须保证所有被选定的提案都必须拥有相同的V值。对于提案value值的约定，结合提案编号，我们有如下原则：

P2:如果编号为 M0 、Value值为V0 的提案（即[M0,V0 ]）被选定了，那么所有比编号M0更高的，且被选定的提案，其Value值也必须是V0。

一个提案要被选定，首先必须被至少一个Acceptor批准，因此我们可以通过满足如下条件来满足P2。

P2a:如果编号为 M0 、Value值为V0 的提案（即[M0,V0 ]）被选定了，那么所有比编号M0更高的，且被Acceptor批准的提案，其Value值也必须是V0。

到目前为止，我们通过P1、P2可以保证有一个提案会被选定，但是还会存在这样一个问题。由于Proposer和Acceptor的通信涉及到网络延迟，很可能出现某个Proposer提出的提案已经被大多数Acceptor选定，另外一个Proposer又提出一个其他value值且编号比被选定提案编号还高的提案，同时从未批准过任何提案的Acceptor A接收到了，根据P1，此Acceptor A必须批准该提案。这就出现了Acceptor A批准的提案和其他Acceptor批准的不一致，违反了P2a原则。如下图所示：

p2a_error

因此我们需要针对P2a进行强化：

P2b:如果一个提案[M0,V0 ]被选定后，那么之后任何Proposer产生的编号更高的提案，其value值都为V0 。

通过P2b，我们可以推导出P2a，进而也可以推导出P2。

如何保证某个Value为v的提案被选定后，Proposer提出的编号更高提案的value都是v呢？可以通过第二数学归纳法证明。假设：

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

因为编号为M0的提案已经被选定了，这就意味着肯定存在一个由半数以上的Acceptor组成的集合C，C中的每个Acceptor都批准了该提案。在结合假设，编号为M0的提案被选定意味着：

  • C中的每一个Acceptor都批准了一个编号在M0到Mn-1范围内的提案，并且每个编号在M0到M0-1范围内的都被Acceptor批准的提案，其Value值都为V0。

我们再定义一个存在半数以上Acceptor的集合S，S中肯定包含且至少包含C中的一个成员，因此我们可以认为如果保证了如下P2c的不变性，那么编号为Mn的提案的Value也为V0.

P2c:对于任意的Mn和Vn，如果提案[Mn,Vn]被提出，那么肯定存在一个半数以上的集合S，满足以下任意一点：

  1. S中不存在任何批准过编号小于Mn的提案的Acceptor。
  2. 选取S中所有Acceptor批准的编号小于Mn的提案，其中编号最大的那个提案其Value值是Vn。

我们通过P2c可以知道每个Proposer如何产生一个提案：对于产生的每个提案[Mn,Vn]，需要满足以下条件：

存在一个由半数以上Acceptor组成的集合S：

  1. 要么S中没有Acceptor批准过任何提案，那么S接收到任何提案，都会直接批准。
  2. 要么S中所有Acceptor批准的所有编号小于Mn的提案中，编号最大的那个提案的Value值为Vn。

我们接下来使用第二数学归纳法来证明。首先假设提案[M0,V0]被选定了，那么比这个提案编号大的提案[Mn,Vn]，我们需要证明在P2c的前提下，对于所有的[Mn,Vn]，存在Vn=V0。

  1. 当Mn=M0+1时，如果有这样一个编号为Mn的提案，首先我们知道[M0,V0]已经被选定了，那么就一定存在一个Acceptor的子集S，且S中的Acceptor已经批准了小于Mn的提案，于是Vn只能是批准的所有编号小于Mn提案中编号最大提案的Value。此时Mn=M0+1，因此编号小于Mn的编号只能是M0，也就是批准的提案为[M0,V0]。同时由于S和通过[M0,V0]的Acceptor集合都是多数集，也就是二者肯定至少有一个Acceptor的交集，这样Proposer在确定Vn取值的时候，就一定会选择V0。

这是数学归纳法的第一步，证明了n=0+1的情况下，是符合我们预期的。接下来我们就要假设在n=0+1到n=n-1这个区域符合预期，并在此基础上推导出当编号为Mn也成立。

  1. 根据假设，编号在M0+1到Mn-1区间内的所有提案的Value值为V0，需要证明的是编号为Mn的提案的Value值也为V0。根据P2c，首先同样一定存在一个Acceptor集合S，且S中的Acceptor已经批准了小于Mn的提案，那么编号Mn的提案的Value值只能是这个多数集S中编号小与Mn但为最大编号的那个提案的值。如果这个最大提案编号的值落在M0+1到Mn-1区间，那么Value值肯定是V0。如果不落在这个区间，那么它的编号不可能比M0更小，肯定就是M0，以为S也肯定与批准[M0,V0]这个提案的Acceptor集合S1有交集，而如果编号是M0，那么它的Value值也是V0。

5.4，算法描述

上文我们提到，要通过加强Proposer和Acceptor之间的交互，来完成最终提案值的选定；同时我们在P2c的推导过程中，确定了Proposer要感知Acceptor的批准的提案的值，也就是Proposer需要有一个拿到Acceptor批准的提案值的环节。于是我们可以将获取最终值分为两个阶段：

  1. Proposer发起提案请求，Acceptor处理请求，并有一定的返回。
  2. Proposer处理Acceptor的返回，并进行提案最终值的确认。Acceptor处理Proposer发起的确认，达成一致。

专业一点的讲法就是分为Prepare阶段和Acceptor阶段。

5.4.1，Proposer生成提案

  1. Proposer选择一个新的提案编号Mn，然后向某个Acceptor集合的成员发送请求，要求该集合中的Acceptor作出如下回应
    • 向Proposer承诺，保证不再批准任何编号小于Mn的提案。
    • 如果Acceptor已经批准过任何提案，那么就向Proposer反馈当前该Acceptor已经批准的编号小于Mn但为最大编号的那个提案的值

我们将此类请求称之为编号为Mn提案的Prepare请求。

  1. 如果Proposer收到了来自半数以上的Acceptor的响应结果，那么它就可以产生编号为Mn、Value值为Vn的提案，这里的Vn是所有响应中编号最大的提案的Value值。如果半数以上的Acceptor没有批准过任何提案，即响应中不包含任何提案，那么此时Vn值就可以由Proposer任意选择。

Proposer向Acceptor发起请求并期望得到批准，我们称此次请求为Accept请求。

5.4.2，Acceptor批准提案

由上文内容我们知道，一个Acceptor可能会收到Proposer两种请求，分别是Prepare请求和Accept请求，对这两类请求做出响应的条件如下：

  • Prepare请求：Acceptor可以在任何时候响应一个Prepare请求。
  • Accept请求：在不违背Accept现有承诺前提下，可以任意响应Accept请求。

所以针对Acceptor我们定义以下原则：

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

针对此原则，我们还可以进行优化，那就是针对编号小于Mn的提案Prepare请求，可以忽略；同样提案编号的Prepare，不再重复响应。接下来我们针对这两阶段Acceptor的动作，做一个描述。

阶段一

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

举例：如果一个Acceptor已经批准过所有Prepare请求对应的提案编号分别为[4、5、6]，那么该Acceptor收到一个编号为7的Prepare请求后，就会将编号为7的提案作为响应返回给Proposer。

阶段二

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

整个算法的执行流程如此，文字表述比较晦涩，我们通过下面这幅图来说明：

两阶段

坚持原创分享