Liuye Notebook
0%

Protocol-Paxos

发表于 更新于 分类于 ， 阅读次数： Valine：

阅读更多

1 前言

Paxos算法是莱斯利-兰伯特（英语：Leslie Lamport，LaTeX中的“La”）于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。Paxos算法作为Zookeeper中的leader选举算法

2 问题和假设

分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复，在基础Paxos场景中，先不考虑可能出现消息篡改即拜占庭错误的情况。Paxos算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就没有停止过

为描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的
对应于分布式系统，议员对应于各个节点，制定的法律对应于系统的状态。各个节点需要进入一个一致的状态，例如在独立Cache的对称多处理器系统中，各个处理器读内存的某个字节时，必须读到同样的一个值，否则系统就违背了一致性的要求。一致性要求对应于法律条文只能有一个版本。议员和服务员的不确定性对应于节点和消息传递通道的不可靠性

3 算法

3.1 算法的提出与证明

首先将议员的角色分为proposers，acceptors，和learners（允许身兼数职）

  • proposers：提出提案，提案信息包括提案编号和提议的value
  • acceptor：收到提案后可以接受（accept）提案，若提案获得多数acceptors的接受，则称该提案被批准（chosen）
  • learners：只能“学习”被批准的提案

划分角色后，就可以更精确的定义问题：

  1. 决议（value）只有在被proposers提出后才能被批准（未经批准的决议称为“提案（proposal）”）
  2. 在一次Paxos算法的执行实例中，只批准（chosen）一个value
  3. learners只能获得被批准（chosen）的value

另外还需要保证progress。这一点以后再讨论

作者通过不断加强上述3个约束（主要是第二个）获得了Paxos算法

批准value的过程中，首先proposers将value发送给acceptors，之后acceptors对value进行接受（accept）。为了满足只批准一个value的约束，要求经“多数派（majority）”接受的value成为正式的决议（称为“批准”决议）。这是因为无论是按照人数还是按照权重划分，两组“多数派”至少有一个公共的acceptor，如果每个acceptor只能接受一个value，约束2就能保证
于是产生了一个显而易见的新约束：

P1：一个acceptor必须接受（accept）第一次收到的提案

注意P1是不完备的。如果恰好一半acceptor接受的提案具有value A，另一半接受的提案具有value B，那么就无法形成多数派，无法批准任何一个value

约束2并不要求只批准一个提案，暗示可能存在多个提案。只要提案的value是一样的，批准多个提案不违背约束2。于是可以产生约束P2：

P2：一旦一个具有value v的提案被批准（chosen），那么之后批准（chosen）的提案必须具有value v

注：通过某种方法可以为每个提案分配一个编号，在提案之间建立一个全序关系，所谓“之后”都是指所有编号更大的提案

如果P1和P2都能够保证，那么约束2就能够保证

批准一个value意味着多个acceptor接受（accept）了该value。因此，可以对P2进行加强：

P2a：一旦一个具有value v的提案被批准（chosen），那么之后任何acceptor再次接受（accept）的提案必须具有value v

由于通信是异步的，P2a和P1会发生冲突。如果一个value被批准后，一个proposer和一个acceptor从休眠中苏醒，前者提出一个具有新的value的提案。根据P1，后者应当接受，根据P2a，则不应当接受，这中场景下P2a和P1有矛盾。于是需要换个思路，转而对proposer的行为进行约束：

P2b：一旦一个具有value v的提案被批准（chosen），那么以后任何proposer提出的提案必须具有value v

由于acceptor能接受的提案都必须由proposer提出，所以P2b蕴涵了P2a，是一个更强的约束，但是根据P2b难以提出实现手段。因此需要进一步加强P2b：假设一个编号为m的value v已经获得批准（chosen），来看看在什么情况下对任何编号为n（n>m）的提案都含有value v。因为m已经获得批准（chosen），显然存在一个acceptors的多数派C，他们都接受（accept）了value v。考虑到任何多数派都和C具有至少一个公共成员，可以找到一个蕴涵P2b的约束P2c：

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

P2c有点绕，我们来看看满足上述约束条件的提案是一个怎样的提案

  1. 根据要么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于n的任何提案，这意味着之前没有任何提案被通过，因为任何两个多数派必然存在交集
  2. 根据要么他们已经接受（accept）的所有编号小于n的提案中编号最大的那个提案具有value v，这意味着具有value v的提案必然是之前被批准过的，因此编号为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，所以以上两个条件都不成立，导出矛盾从而推翻假设，证明了提案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是可以通过消息传递模型实现的。另外，引入了P2c后，也解决了前文提到的P1不完备的问题

4 算法内容

要满足P2c的约束，proposer提出一个提案前，首先要和足以形成多数派的acceptors进行通信，获得他们进行的最近一次接受（accept）的提案（prepare过程），之后根据回收的信息决定这次提案的value，形成提案开始投票。当获得多数acceptors接受（accept）后，提案获得批准（chosen），由proposer将这个消息告知learner。这个简略的过程经过进一步细化后就形成了Paxos算法

在一个Paxos实例中，每个提案需要有不同的编号，且编号间要存在全序关系。可以用多种方法实现这一点，例如将序数和proposer的名字拼接起来。如何做到这一点不在Paxos算法讨论的范围之内

如果一个没有chosen过任何proposer提案的acceptor在prepare过程中回答了一个proposer针对提案n的问题，但是在开始对n进行投票前，又接受（accept）了编号小于n的另一个提案（例如n-1），如果n-1和n具有不同的value，这个投票就会违背P2c。因此在prepare过程中，acceptor进行的回答同时也应包含承诺：不会再接受（accept）编号小于n的提案。这是对P1的加强：

P1a：当且仅当acceptor没有回应过编号大于n的prepare请求时，acceptor接受（accept）编号为n的提案

4.1 决议的提出与批准

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

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

这个过程在任何时候中断都可以保证正确性。例如如果一个proposer发现已经有其他proposers提出了编号更高的提案，则有必要中断这个过程。因此为了优化，在上述prepare过程中，如果一个acceptor发现存在一个更高编号的提案，则需要通知proposer，提醒其中断这次提案

5 参考

6 下面的论证转载自知乎

首先我们简单介绍Paxos所保证的一致性的具体含义；达成一致的条件(何时达成一致）；基于的一个基本的数学原理；以及它需要满足的假设

什么是一致性？实际上这个词在不同地方语义并不那么一致，Paxos面向的是一个理论的一致问题，这个问题的通俗描述是：

有一个变量v，分布在N个进程中，每个进程都尝试修改自身v的值，它们的企图可能各不相同，例如进程A尝试令v = a，进程B尝试令v = b，但最终所有的进程会对v就某个值达成一致，即上述例子中如果v = a是v达成一致时的值，那么B上，最终v也会为a。需要注意的是某个时刻达成一致并不等价于该时刻所有进程的本地的v值都相同，有一个原因是进程可能挂掉，你不能要求挂掉的进程保证任何事。最终所有存活的进程本地v的值都会相同

这个一致性需要满足三个要求：

  1. v达成一致时的值是由某个进程提出的。这是为了防止像这样的作弊方式：无论如何，最终都令每个进程的v为同一个预先设置好的值，例如都令v = 2，那么这样的一致也太容易了，也没有任何实际意义
  2. 一旦v就某个值达成了一致，那么v不能对另一个值再次达成一致。这个要求称为安全性
  3. 一致总是能够达成，即v总会被决定为某个值。这是因为不想无休止的等待，这个要求也称为活性

Paxos中变量v达成一致的条件：

N个进程中大多数（超过一半）进程都认为v是同一个值，例如c，那么我们称v被决定为c。这样即使少数进程挂掉了，也不会使得一致无法达成。它保证的一致性如下：不存在这样的情形，某个时刻v被决定为c，而另一个时刻v又决定为另一个值d。由这个定义我们也看到，当v的值被决定后，Paxos保证了它就像是个单机的不可变变量，不再更改。也因此，对于一个客户端可以多次改写值的可读写变量在不同的节点上的一致性问题，Paxos不能直接用于解决该问题，它需要和状态机制结合。

Paxos基于的数学原理：

我们称大多数进程组成的集合为法定集合，两个法定集合必然存在非空交集，即至少有一个公共进程，称为法定集合性质。例如A，B，C，D，F进程组成的全集，法定集合Q1包括进程A，B，C，Q2包括进程B，C，D，那么Q1和Q2的交集必然不在空，C就是Q1，Q2的公共进程。如果要说Paxos最根本的原理是什么，那么就是这个简单性质。同时，可以注意到，这个性质和达成一致的定义相呼应

Paxos中进程之间是平等的，即不存在一个特殊的进程，这是由于如果协议依赖于某个特殊的进程，那么这个进程挂掉势必会影响协议；而对于分布式环境，无法保证单个进程必然存活，能够容忍一定数量的进程挂掉，是分布式协议的必然要求。这是推导过程所要遵循的一个原则，称为平等性原则

消息传递是进程间通信的唯一手段，对于分布式环境来说，这是显然的

Paxos要求满足的前置假设只有一个：消息内容不会被篡改；更正式的说是无拜占庭将军问题

假装的推导总是先从一些具体的场景开始，既然Paxos的假设仅仅只是消息不会被篡改，保证了这点任意场景下都能保证一致性，那么对于举例的场景它必然是能够保证一致性的；因此推导的目标总是先使得协议流程能在当前举例的场景下保证一致性，然后再举出另一个场景，当前的协议流程在这个场景下将不满足一致性，于是再丰富协议流程，满足该场景，如此往复，最终得到完整的Paxos，最后再不失一般性的论证：得到的协议对任意场景都能保证一致性

进程的平等性假设会带来如下的问题，考虑如下的场景1：三个进程的场景P1，P2，P3（n个进程的场景类似），P1尝试使得v = a，P2尝试使得v = b。假设它们都先改写了自身的v值，然后发送消息尝试改修P3的v值。显然如果P3收到两个消息后都满足了它们的企图，那么v就会两次被决定为不同的值，这破坏了之前的定义。因此P3必须得拒绝掉其中一个进程的请求，如何拒绝也是我们最先考虑的问题。一个最简单的拒绝策略是先来后到，P3只会接受收到的第一个消息中，拒绝之后的消息，即只会改写v一次。按照这个策略，如果P1发送的消息首先到达P3，那么P3接受该消息令v = a，拒绝掉后到的来自P2的消息。但是这个策略会引入一个另外的问题：在场景1的基础上考虑这样的场景1’，P3也尝试决定v的值，P3尝试使得v = c，那么P1，P2，P3都尝试修改v的值，首先P1令v = a，P2令v = b，P3令v = c(相当于自己给自己发消息），按照之前的策略，每个进程只会改写v的值一次，那么将永远不会出现两个进程的v值相等的情况，并且永远不存在一个多数派，即v永远无法被决定。更正式的说，这个协议不满足活性，活性要求协议总能达成一致。由此我们也得到第一个结论：进程必须能够多次改写v的值。同时我们也要意识到：当进程收到第一个消息时，进程是没有任何理由拒绝这个消息的请求

拒绝策略总是需要有一个依据，之前我们的依据是消息到达的先后，只接受第一个到达的消息，但这导致不满足活性。现在我们需要另一个拒绝策略，也就是需要另一个依据，这个依据至少能够区分两个消息。为此我们引入一个ID来描述这个消息，这样就可以根据ID的大小来作为拒绝或接受的依据；选择ID更大的消息接受和选择ID更小的消息接受是两种完全对称的策略，不妨选择前者。这个策略不会导致明显的活性问题，ID更大的消息总是能被接受，一个节点可以多次更改v的值。例如在场景1’中，只要P1的消息ID比P3发送给自己的消息ID更大，P3就会接受P1的消息，令v = a，从而令v的值被决定为a。再来考虑最初的场景1，不妨假设P1的消息ID大于P2的消息ID，根据P3收消息的先后可以分为两种情况：

  1. P3先收到P1的消息，记做场景1-2，由于P1的消息是P3收到的第一个消息，P3接受该请求，令v = a；同时为了能对之后的收到的消息作出是否接受的判断，P3需要记录该消息的ID作为判断的依据。之后P3又收到P2的消息，该消息的ID小于P3记录的ID，即P1的消息ID，因此P3拒绝该消息，这样我们的目的就达到
  2. P3先收到P2的消息，记作场景1-3，同样P3接受该消息，令v = b，记录该消息的ID。之后P3收到P1的消息，由于P1的消息ID大于P3记录的ID，因此P3无法拒绝该消息，之前的问题依旧存在

尽管对于场景1-3，目前的策略依旧无法保证一致性，但是起码我们缩小协议无法保证安全性的场景的范围。先总结下我们目前的策略，并定义一些称谓以方便后面的论述。我们称呼进程P发送的尝试修改另一个进程中变量v的值的消息称之为提案，记作Proposal；提案的ID记作proposal_id；如果提案中附带的值被决定为是v的值，即大多数接受者接受了这个提案，那么称提案被通过。进程P记录的接受的提案ID为a_proposal_id。之前我们尚未清晰地定义a_proposal_id，实际上我们也就并未清晰地定义我们的拒绝策略，当P收到一个提案Proposal-i时，可能已经收到过多个提案，Proposal-i.proposal_id该和其中哪个提案的proposal_id比较，我们并未定义。我们定义为其中的最大者，这样实际上进程P只需维护一个a_proposal_id即可，当收到一个Proposal时，更新a_proposal_id = max(Proposal.proposal_id，a_proposal_id）。同时在之前的描述中我们应当注意到实际上一个进程存在两个功能：

  1. 进程主动尝试修改并决定v的值，向进程集合广播提案
  2. 进程被动收到来自其它进程的提案，判断是否要接受它

因此可以把一个进程分为两个角色，称负责功能1的角色是提议者，记作Proposer，负责功能2的角色是接受者，记作Acceptor。由于两者完全没有耦合，所以并不一定需要在同个进程，但是为了方面描述，我们假定一个进程同时担任两种角色，而实际的工程实现也往往如此。接着我们尝试解决场景1-3，这看起来很难。P3作为接受者，收到P2的提案之前未收到任何消息，只能接受该提案，而由于P1的提案proposal_id大于P2的提案，我们的拒绝策略也无法让P3拒绝P2。让我们先不急着推导具体可行的策略，先考虑下解决1-3场景可能的角度，有如下三种角度可以入手：

  1. P3能够拒绝掉P2的提案
  2. P3能够拒绝掉P1的提案
  3. 限制P1提出的提案，如果P1的提案尝试决定的v的值与P2的提案一致，那么接受P1也不会破坏一致性
  • 我的问题：既然P1的提案与P2的提案的v值相同，那P1为什么还要提案？这个提案有什么意义？

接着我们分析三个角度的可行性：

角度1需要P3有做出拒绝的依据，由于消息是进程间通信唯一手段，这要求P3在收到P2的提案之前必须先收到过其它消息。对于场景1-3，只有P1，P2是主动发送消息的进程，P2当然不可能额外还发送一个消息试图令P3拒绝自己随后的提案。那么唯一的可能是P1在正式发送提案前，还发送了一个消息给P3，这个消息先于P2的提案到达，给了P3拒绝P2提案的理由。如果沿用目前的拒绝策略，那么P1只需先发送随后提案的proposal_id给P3，P3更新a_proposal_id为该消息附带的proposal_id，这样a_proposal_id将大于P2的提案的proposal_id，而导致P2的提案被拒绝，似乎这是一个可行的角度

对于角度2，我们目前的策略无法做到这一点，因此除了proposal_id外，我们还得给提案附加上额外的信息作为另外的拒绝策略的依据。提案由进程提出，也许我们可以附加进程的信息，但是就算P3得知P1的提案由P1提出，P3又凭什么歧视P1，这违反进程的平等性假设。似乎这个角度不是一个好角度

最后我们分析一下角度3，角度3提供了与1，2截然不同的思路，它不再是考虑如何拒绝，而把注意力放在如何对提案的值做出恰当的限制上。对于场景1-3而言，从这个角度，由于P3无法拒绝P1和P2的提案中的任何一个，因此P1的提案的值就必须与P2的提案一致；这也意味着了P1在正式提出提案前，需要有途径能获悉P2的提案的值。如我们上面一直强调的，消息是唯一的通信手段，P1必须收到来自其它节点消息才有可能得知P2提出的提案的值。P1可以被动的等待收到消息，也可以主动地去询问其它节点等待回复。后者显然是更好的策略，没有收到想要的消息就一直等待未免也太消极了，这种等待也可能一直持续下去从而导致活性问题

经过上面的分析，我们暂时排除了从角度2入手（实际上后面也不会再考虑，因为从1，3入手已经足以解决问题）。下面将沿着角度1，3进行更深入的分析，我们先尝试从角度1出发，毕竟考虑如何拒绝已经有了经验。先来总结下我们在分析角度1时引入的额外的流程:

进程P在发送提案前，先广播一轮消息，消息附带着接下来要发送的提案的proposal_id。由于该消息和接下来发送的提案相关，且在提案被提出之前发送，不妨称这个消息为预提案，记作PreProposal，预提案中附带着接下来的提案的proposal_id。当作为接受者的进程Pj收到预提案后，更新Pj. a_proposal_id。还记得我们之前的拒绝策略中a_proposal_id的更新策略嘛：a_proposal_id = max(proposal_id,a_proposal_id)，a_proposal_id是递增的。因此如果预提案的proposal_id小于Pj.a_proposal_id，Pj完全可以忽略这个预提案，因为这代表了该预提案对应的提案的proposal_id小于Pj.a_proposal_id，必然会被拒绝。我们沿用之前拒绝策略中a_proposal_id的更新策略。这样当收到预提案或者提案后，a_proposal_id的值均更新为max(a_proposal_id,proposal_id)

一个小问题：每个进程如何确保提案编号的唯一性？似乎这也是一个分布式的问题

接着我们来看看引入了预提案后，能否真正解决场景1-3。根据P1和P2的预提案到达P3的先后也存在两种场景：

  1. 场景1-3-1：P1的预提案先到达，P3更新a_proposal_id为该提案的proposal_id，这导致随后到达的P2的提案的proposal_id小于a_proposal_id，被拒绝。满足一致性
  2. 场景1-3-2：P2的提案先到达，P3接受P2的提案，此时和原始的场景1-3存在同样的问题。归根结底，预提案阶段能否使得P3拒绝P2的提案的，也依赖消息到达的顺序，和提案阶段的拒绝策略存在相同的问题，但至少又缩小了不能保证安全性的场景范围

幸好我们还有角度3可以着手考虑，所以仍有希望完全解决场景1-3。在深入角度3之前，先总结下协议目前为止的流程，现在协议的流程已经分为了两个阶段：预提案阶段和提案阶段。两种消息：预提案和提案。两种角色：接受者和提议者，流程如下：

  1. 阶段一：
    • 提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id
    • 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id)
  2. 阶段二：
    • 提议者Proposer：向接受者Acceptor广播提案，和之前的预提案共享同一个proposal_id
    • 接受者Acceptor：如果收到的提案的proposal_id >= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)

为了更形象，之前的讨论是基于三个进程的场景，实际上对于N进程的场景也是一样的。N进程时，与之前场景1对应的场景是：N个进程，存在两个进程Pi，Pj，Pi尝试令v = a，Pj尝试令v = b，Pi提出的预提案记作PreProposal-i，提案记作Proposal-i；Pj的预提案PreProsal-j，提案Proposal-j。之拒绝策略的讨论都是基于一个关键的进程P3，只要P3最终能拒绝Proposal-i和Proposal-j中的一个，两个提案就不会都被通过，那么一致性不被破坏。Pi的提案被通过代表了存在一个法定集合Q-i，Q-i中的进程都接受了Proposal-i，Pj同理，存在一个Q-j，Q-j中的进程都接受了Proposal-j。由于法定集合的性质，两个多数集Q-i和Q-j中必然存在一个公共进程Pk。Pk即相当于场景1中的P3，只要Pk能够拒绝Proposal-i和Proposal-j中的一个，协议依旧是安全的

为了不失一般性，下面我们都以N个进程的场景作为讨论的基础，称为场景2，由于场景1和场景2可以一一对应，所以接下来顺着限制提案的值的角度，我们直接针对场景2-3-2，对于其他的场景，场景和场景1一样，我们的拒绝策略已经足以应付。v的值被决定代表有一个提案，它被法定数目的集合接受，我们称这为提案被通过

首先我们看下场景2-3-2，Pi对应场景1-3-2中的P1，Pj对应P2，Pk对应P3。Pj的提案Proposal-j最终会被法定集合Q-j接受，即v的值被决定为b，且Proposal-i.proposal-id > Proposal-j.proposal_id。我们需要限制Pi的提案的值，不能让Pi自由的给Proposal-i中的v赋值。在2-3-2中，由于拒绝策略失效，所以只能令Proposal-i.v = Proposal-j.v = b。要做到这一点，正如前面的分析所言，Pi需要先主动询问进程集合，来得知Proposal-j.v = b这一事实。显然Pi是没有先验信息来得知Proposal-j由哪个进程提出，也不知道Q-i和Q-j的公共节点Pk具体是哪个进程，因此Pi只能广播它的查询。由于我们需要允许少数进程失败，Pi可能只能得到大多数进程的回复，而这之中可能不包括Pj。我们称这些进程的集合为Q-i-2，为了描述更简单，无妨假设Q-i-2 = Q-i。尽管Pi的查询可能得不到Pj的回复，好在Proposal-j将会被Q-j内所有进程接受，因此如果接受者在接受提案时，顺便记录该提案，那么Q-j内所有进程都将得知Proposal-j.v = b。由于Pk属于Q-i和Q-j的交集，所以Pk即收到了Pi的询问，又接受了提案Proposal-j。之前我们已经引入了预提案阶段，显然我们可以为预提案附带上查询的意义，Pk作为接受者收到Pi的预提案后，回复它记录的提案。有一个问题是Pk此时是否已经记录了Proposal-j呢？很巧的是在场景2-3-2中，Pj的提案Proposal-j是先于Pi的预提案PreProposal-i先到达，所以Pk已经记录了Proposal-j.v = b，Pj收到的来自Pk的回复中包含了提案Proposal-j，而2-3-2之外的场景，拒绝策略已经足以应付。这里依旧还有两个问题，先讨论第一个：

实际上很可能并不是只有Pi和Pj分别提出了Proposal-i和Proposal-j，其它进程也会发起预提案和提案，所以收到PreProposal-i时Pk可能已经接受过多个提案，并非只有Proposal-j，那么Pk应该回复PreProposal-i其中哪个，或者都回复？Pk并不知道Proposal-j会被通过，它只知道自己接受了该提案。都回复是个效率很低但是可以保证Pk不会遗漏Proposal-j，Pk已经回复了它所能知道的全部，我们也无法要求更多。需要注意到的是进程是平等的，所以Q-i中所有进程都和Pk一样回复了它接受过的所有提案。当Pi收到所有来自Q-i的回复，随之而来的是第二个问题：

Pi收到了多个Proposal作为Acceptor对PreProposal-i的回复，记这些Proposal组成的集合为K-i，那么它应当选择K-i中哪个一个提案的值作为它接下来的提案Proposal-i的v值？记选择的这个提案为Proposal-m。在场景2-3-2中，我们第一直觉是希望选择的Proposal-m即是Proposal-j，但是实际上，我们只要保证Proposal-m .v = Proposal-j.v即可。从另一个角度，K-i中很可能存在这样的提案Proposal-f，Proposal-f.v != Proposal-j.v，我们要做的是避免选择到这类提案。我们可以根据一些依据瞎选碰碰运气，但是这并明智，所以先让我们来分析一下Proposal-f有什么特征。我们不妨假设存在这样的策略cf，cf使得选择出提案Proposal-m满足Proposal-m.v = Proposal-j.v。Proposal-f能够被提出，代表存在一个多数集合Q-f，Q-f中每个进程都接受了PreProposal-f，同时假设是进程P-f提出了PreProposal-f和Proposal-f。Q-f和Q-j必然存在一个公共节点，记做Ps，Ps既接受了PreProposal-f又接受了Proposal-j。Ps收到PreProposal-f和Proposal-j的顺序只有两种可能：

  1. Ps先收到PreProposal-f
  2. Ps先收到Proposal-j

PreProposal-f.proposa-id和Proposal-j. proposal_id的大小也只有两种可能，不妨先假设PreProposal-f.proposal_id > Proposal-j.proposal_id

  1. 对于情形1，Ps先收到PreProposal-f，接受它，更新Ps.a_proposal_id = PreProposal-f.proposal_id > Proposal-j.proposal_id，同时之前的a_proposal_id的更新策略又使得Ps.a_proposal_id是递增的，于是导致Proposal-j由于proposal_id < Ps.a_proposal_id被拒绝，与假设不符合，矛盾。该情况不成立
  2. 对于情况2，Ps将把提案Proposal-j回复给PreProposal-f。由于我们假设了策略cl的存在，于是Pf在收到所有Q-f对PreProposal-f的回复后，将令Proposal-f.v = Proposal-j.v，cl就是干这个的。因此Proposal-f.v != Proposal-j.v矛盾。该情况不成立
  • 由于当假设PreProposal-f.proposal_id > Proposal-j.proposal_id时，情形1，2我们都得出了矛盾，同时两者的proposal_id又不相等(最初的假设），所以必然PreProposal-f.proposal_id < Proposal-j.proposal_id，即Propsoal-f.proposal_id < Proposal-j.proposal_id

于是我们得到的结论是：如果策略cl存在，当提案Proposal-j最终会被通过，对于任意一个预提案PreProposal-i，Preproposal-i.id > Proposal-j.proposal-id，得到的Q-i的回复K-i中任意的Proposal-f，满足Proposal-f.v != Proposal-j.v，那么Proposal-f.proposal_id < Proposal-j.proposal_id

既然K-i中所有v值不等于Proposal-j.v的提案，proposal_id都更小，那代表所有proposal_id比Proposal-j更大的提案，v值都等于Proposal-j.v，因此选择K-i中proprosal_id最大的提案，就能保证Proposal-i.v = Proposal-j.v。于是我们得到了策略cl的具体形式

我们得到了具体可行的策略cl是建立在策略cl存在这一前提之上，因此反过来，对于这个具体的选值策略cl，结合之前我们得到了协议流程，它是否能保证如下的性质CP1，依旧需要进一步的论证 ：

如果一个提案Proposal-j最终会被通过，那么对于任意的一个提案Proposal-i，如果Proposal-i.proposal_id > Proposal-j.proposal_id，那么Proposal-i.v = Proposal-j.v

我们先总结下目前得到的协议流程：

  1. 阶段一：预提案阶段
    • 提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id
    • 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id)，如果预提案的proposal_id大于a_proposal_id，那么回复该预提案的提议者改接受者接受过的所有提案
  2. 阶段二：提案阶段
    • 提议者Proposer：等待直到收到大多数接受者对预提案的回复，从所有回复的提案组合成的集合K中挑选proposal_id最大的提案，以该提案的值作为本次提案的值。如果K是空集，那么可以给提案任意赋值。向接受者Acceptor广播提案，和之前的预提案共享同一个proposal_id
    • 接受者Acceptor：如果收到的提案的proposal_id >= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)

这些流程是为了解决举例的场景而不断丰富的，接着就让我们论证下协议流程是否可以确保CP1

首先假设Proposal-i.v != Proposal-j.v，如果得出矛盾即可证明CP1。在尝试演绎出矛盾前，我们先做一些定义，以便后续的演绎

记大多数接受者组成的法定集合为Q，K是提议者在提案阶段收到的所有Q回复的提案组成的集合，如果K不为空，记K中proposal_id最大的提案是MaxProposal(K)，本次提案的值即是MaxProposal(K).v；如果K是空集，那么MaxProposal(K).v = null。特别的，对于提案Proposal-i，回复它预提案接受者的集合为Q-i，回复的提案组成的集合为K-i，Proposal-i.v = MaxProposal(K-i)，Proposal-i.v=null代表可以随意赋值。为了描述方便，我们令Proposal-i的proposal_id为i，即Proposal-i代表了proposal_id = i的提案，Proposal-j意味着Proposal-j.proposal_id = j

论证过程如下：

  1. Proposal-i.v != Proposal-j.v，即MaxProposal(K-i).v！= Proposal-j.v，即MaxProposal(K)-i != Proposal-j
  2. Proposal-j最终会被通过，代表最终会存在一个多数集合Q-j，Q-j中每个接受者都接受了Proposal-j
  3. 两个多数集必然存在公共成员，故Q-j和Q-i必然存在一个公共的进程Pk，Pk既收到了PreProposal-i又收到了Proposal-j，且都接受了它们；Pk收到消息的先后关系只存在如下两种可能：
    • 1.Pk先收到了PreProposal-i
    • 2.Pk先收到了Proposal-j
  4. 情形1中Pk先收到了PreProposal-i，那么Pk收到Proposal-j时，Pk.a_proposal >= PreProposal-i.proposal_id ＞Proposal-j.proposal_id，Pk会拒绝Proposal-j，与(3)矛盾，因此情况1不可能，Pk必然是先收到Proposal-j
  5. 情形2中Pk收到PreProposal-i时，已经接受了Proposal-j，因此Pk回复PreProposal-i的提案中包含了Proposal-j，因此K-i中必然包含了Proposal-j
  6. 由(1)已知MaxProposal(K-i) != Proposal-j，即存在另一个提案Proposal-m = MaxProposal(K-i)，而Proposal-j属于K-i，因此Proposal-m.proposal_id > Proposal-j.proposal_id，且Proposal-m.v ！= Proposal-j.v
  7. 由预提案阶段，接受者回复预提案的条件可知：Proposal-i.proposal_id大于集合K-i中任意一个提案的Proposal-id，故Proposal-i.proposal_id > Proposal-m.proposal_id
  8. 目前我们已经论证如下一点：

在Proposal-j最终会被通过的前提下，如果存在一个提案Proposal-i.v != Proposal-j.v，且Proposal-i.proposal_id >Proposal-j.proposal_id，我们一个数学符号来带表示这个情况，记CF(j,i)；那么 必然存在一个提案Proposal-m, Proposal-m != Proposal-j.v，且Proposal-m.proposal_id > Proposal-j.proposal_id，同样的我们可以记做CF(j,m)。并且Proposal-m.proposal_id < Proposal-i.proposal_id，m < i

即如果CF(i,j)成立，那么必然CF(m,j)成立，且i>m，即CF(i,j) —> CF(m,j)。这个过程可以继续往下递归，但由于区间[j,i]范围是有限的，因此一定会递归到一个CF(j,e)，此时不可能存在一个提案，它的proposal_id在区间(j,e)内，无法往下递归，这与(8)矛盾。这也就意味着CF(e,j)不成立，而如果CF(i,j)成立，那么CF(e,j)成立，因此CF(i,j)不成立，故假设不成立，即Proposal-i.v必然等于Proposal-j.v，即证CP1

通过归约的方式得出矛盾的方式依旧有些抽象，我们可以通过更好的定义假设来更容易得到的矛盾：

我们加强对Proposal-i的约束。先假设存在一个提案的非空集合KD，KD中的任意一个提案Proposal-k，Proposal-k.v != Proposal-j.v，且Proposal-k.proposal_id > Proposal-j.v。再假设Proposal-i是KD中proposal_id最小的提案。由于KD是非空集合，故Proposal-i必然存在

我们依旧可以从Proposal-i出发，(1)~(7)与上面相同，同理得到：存在一个提案Proposal-m，Proposal-m ！= Proposal-v，且Proposal-m.proposal_id > Proposal-j.proposal_id，且Proposal-m.proposal_id < Proposal-i.proposal_id

显然Proposal-m满足集合KD对提案的要求，故Proposal-m属于KD，又Proposal-m.proposal_id < Proposal-i.proposal_id，这和Proposal-i是KD中proposal_id最小的提案的定义矛盾。因此不存在这样的非空集合KD，即不存在一个提案Proposal-k,Proposal-k.v != Proposal-j.v且Proposal-k.proposal_id>Proposal-j.proposal_id。即如果一个提案Proposal-j最终会被通过，对于任意的一个提案Proposal-i，如果Proposal-i.proposal_id > Proposal-j.proposal_id，那么必定Proposal-i.v = Proposal-j.v，即CP1

CP1约束了proposal_id大于Proposal-j的提案的值，保证了如果一个提案Proposal-j最终会被通过，不会存在另一个proposal-id更大且值不同的提案被通过，因为这些提案的值都和Proposal-j相同。那么对于proposal_id更小的提案呢？我们假设存在一个提案Proposal-o，Proposal-o.proposal_id < Proposal-j.proposal_id，且Proposal-o.v != Proposal-j.v，Proposal-o最终会被通过，将CP1应用于Proposal-o，则可知Proposal-j不存在，这矛盾，故Proposal-o不存在。故由CP1我们可知：如果一个提案Proposal-j最终会被通过，那么不存在另一个值与Proposal-j不同的提案被通过。由此协议必然是安全的。虽然我们得到了一个安全的一致性协议，基本上它就是Paxos，但是真正的Paxos要比我们假装推导出的协议更简单一点

回过头来看下我们的阶段1中接受者Acceptor的行为，它要回复所有的它接受过的提案，从实践的角度，不论是在本地保存所有它接受过的提案还是通过网络将它们传输给提议者，开销都太大且不可控。再看下阶段二中，提议者的选值策略，它只是选择了收到的多数集接受者回复的提案中proposal_id最大的那一个，因此接受者实际上只需要回复它接受过的proposal_id最大的提案即可，因为其它提案根本不可能会被选值策略选中。因此最终的协议如下，它就是Paxos

  1. 阶段一：预提案阶段
    • 提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id
    • 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id)，如果预提案的proposal_id > a_proposal_id，Acceptor回复记录的接受过的proposal_id最大的提案
  2. 阶段二：提案阶段
    • 提议者Proposer：等待直到收到大多数接受者对预提案的回复，从所有回复的提案组成的法定数目的提案集合K中挑选proposal_id最大的提案，以该提案的值作为本次提案的值。如果K是空集，那么可以给提案任意赋值。然后把该提案广播给接受者们，提案和预提案共享同一个proposal_id
    • 接受者Acceptor：如果收到的提案的proposal_id >= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)，更新记录的提案

7 总结

需要解决的问题，或者换句话说，需要达成的一致性

  1. v达成一致时的值是由某个进程提出的。这是为了防止像这样的作弊方式：无论如何，最终都令每个进程的v为同一个预先设置好的值，例如都令v = 2，那么这样的一致也太容易了，也没有任何实际意义
  2. 一旦v就某个值达成了一致，那么v不能对另一个值再次达成一致。这个要求称为安全性
  3. 一致总是能够达成，即v总会被决定为某个值。这是因为不想无休止的等待，这个要求也称为活性
  • 另外，learners只能获得被批准（chosen）的v

下面总结一下上述推导过程

协议v1：

只允许Acceptor通过第一个收到的提案，如果存在一个多数派通过某个提案，那么对该提案具有的v达成一致

在协议v1下，会出现这样的场景（记为场景v1）：P1、P2、P3三个进程各自提出一个提案，三个提案具有不同的值。显然，每个进程总是能优先收到自己提出的提案，根据协议v1，每个进程将通过自己提出的提案，于是永远无法达成一个多数派，无法就某个v值达成一致，因此这个协议v1不满足活性

那么我们该如何优化协议v1？我们可以为每个Proposal加上一个proposal_id，这个proposal_id满足全序关系，我们假定存在一种方式能够为每个Proposal加上一个满足全序关系且递增的proposal_id(如何实现这个proposal_id实际上也是一个分布式的问题，但是不在本文的讨论范围内，我们只需要假定这种方式存在即可)，那么优化后的协议如下

协议v2：

只允许Acceptor通过proposal_id更大的提案(更大指的是该提案的proposal_id比当前进程收到过的所有提案的proposal_id都要大)，如果存在一个多数派通过某个提案，那么对该提案具有的v达成一致

在协议v2下，上述不满足活性的场景v1就能够得到有效的解决。但是此时又出现了另一种场景(记为场景v2)：假定P1.proposal_id > P2.proposal_id，且P2的Proposal-2先被P3收到。根据协议v2，P3将通过这个Proposal-2，此时P2和P3形成一个多数派，就Proposal-2的v值达成一致。随后P3又收到了来自P1的Proposal-1，那么根据协议v2，P3应该接受P1的Proposal-1，于是P1和P3形成一个多数派，就该Proposal-1的v值达成一致。由于v值被两次达成一致，因此协议v2不满足安全性

那么我们该如何优化协议v2？似乎P3必须拒绝掉P1或者P2之中的一个Proposal，存在以下两个角度

  1. 让P3拒绝掉P2，这样P3接受proposal_id更大的Proposal-1就不会存在问题。那么如何让P3拒绝掉一个优先收到的Proposal呢？似乎在收到Proposal-2之前，我们能够获取到某种信息，这种信息能够帮助P3拒绝掉Proposal-2
  2. P3不拒绝掉P2，而是限制Proposal-1的v值，使得Proposal-1具有与Proposal-2有相同的v值，那么这样的Proposal-1的v值即使被达成一致也不会破坏安全性

我们先通过第一种角度对协议v2进行优化，优化后的协议如下

协议v3

  1. 阶段一：
    • 提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id
    • 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id)
  2. 阶段二：
    • 提议者Proposer：向接受者Acceptor广播提案，和之前的预提案共享同一个proposal_id
    • 接受者Acceptor：如果收到的提案的proposal_id >= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)

在协议v3中，如果PreProposal-1先于Proposal-2被P3接收，那么依据协议v3，Proposal-2将被P3拒绝，这种情况下将满足一致性。但是存在另一种场景(称为场景v3)：假定P1.proposal_id > P2.proposal_id，并且Proposal-2先于PreProposal-1到达P3。那么依然存在场景v2中的问题，只不过我们缩小了场景。这种协议仍然不满足安全性

我们该如何优化协议v3？我们通过第二种角度进行优化，我们在预提案阶段增加一个查询操作，所有通过预提案的Acceptor将回复该Acceptor所有通过的提案中具有最大proposal_id的提案以及该提案的v值。随后在提案阶段选择一个具有最大proposal_id的v值

协议v4

  1. 阶段一：预提案阶段
    • 提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id
    • 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id)，如果预提案的proposal_id > a_proposal_id，Acceptor回复记录的接受过的proposal_id最大的提案
  2. 阶段二：提案阶段
    • 提议者Proposer：等待直到收到大多数接受者对预提案的回复，从所有回复的提案组成的法定数目的提案集合K中挑选proposal_id最大的提案，以该提案的值作为本次提案的值。如果K是空集，那么可以给提案任意赋值。然后把该提案广播给接受者们，提案和预提案共享同一个proposal_id
    • 接受者Acceptor：如果收到的提案的proposal_id >= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)，更新记录的提案

上述协议v4就是最终的Paxos协议