Paxos

1 Introduction

一致性问题就是通过一些列的处理过程来选择某个特定的结果。这篇论文以存在 non-Byzantine 问题的异步消息传送系统来讨论一致性问题。解决这个问题的思路就是，在任何情况下都不能有两个被选择的值。即使一些处理过程失败了。并且在假定最终有足够多的处理过程处理成功了并且能够彼此通信，那么必须有唯一的一个值需要被选出作为一致性的结果。

在传统的一致性问题描述中，每个参与的过程提交一个提案，最终的结果也必须从这些提交的提案中选择。不难看出，任何基于此的解决方案，参与的过程要获取到最终选择的提案都需要经过至少两次消息通信延迟。许多算法在最好的情况下达到了这种要求。经典的Paxos算法之所以流行，是因为它在实际的应用中，正常情况下，能够获得最优次数的延迟处理。

传统一致性算法描述的最优消息延迟次数在实际中是不能达到的。因为它假定的是最终选择的提案是由提交此提案的处理过程来选择的。但是在实际应用中，并非如此。例如，在客户端/服务器系统中是客户端提交提案，服务端处理提案选择。如果使用传统的一致性算法，那么就需要三次消息延迟。

在快速一致性算法中，处理过程可以只经过两次消息延迟就获悉最终的提案，即使提案的提出和选择是由不同的处理过程集群来处理。但是如果发生提案冲突竞争，也就是，不同的提案并发的被提出，那么任何一种一致性算法都将无法保证两次消息延迟。快速一致性算法在提案冲突的情况下也不总是快的。

快速Paxos是院系经典Paxos的一种快速一致性算法的变种。通常情况下，提案识别可以在没有冲突的前提下通过两次消息延迟完成。或者在提案冲突的情况下通过三次消息延迟完成。另外它也可以使用尽可能少的处理过程来实现任何程度的系统容错。

快速Paxos的核心思想源于早期的 Brasileiro et al. 算法，但是当时他们只考虑了传统的一致性问题。并没有意识到，这种算法可以很容器的演化到快速一致性算法。 Pedone 和 Schiper’s R-Consensus 也可以修改成为快速一致性算法，但是修改后的算法在提案冲突的情况下至少需要四次消息延迟。 Zielinski最近发布了一种快速一致性算法，某种程度上可以视为快速Paxos的变种。

快速Paxos核心上是经典Paxos的扩展，理解了经典Paxos，也就理解了快速Paxos。因此我将从第二章开始，先介绍经典Paxos算法，然后第三章解释快速Paxos是怎么从经典Paxos修改而来。这些描述可能会稍微有点非正式。目的只是向大家解释这种算法是如何工作的。而并不提供通常的使用伪代码或者其它语言描述的的准确的算法说明。经典Paxos的精确描述可以在其它地方找到。快速Paxos的TLA+说明附在结尾附录。理解快速Paxos的最好方法就是用伪代码或者其它语言实现它。

结论部分讨论了快速Paxos的优化，解释了快速Paxos和 Brasileiro et al.之间的关系，并且简要概述了经典Paxos和快速Paxos，是如何解决 Byzantine 问题的。

2 The Classic Paxos Algorithm

2.1 The Problem

一致性问题使用以下三种agents进行表述： proposers 提出提案 acceptors 选择提案 learners 获取提案的选择。agents就是参与一致性算法的过程所扮演的一种角色，一个过程可能扮演多种角色，例如，在客户端/服务器系统中，客户端可能扮演proposers和learners角色，服务器可能扮演acceptors和learners角色。

我们假定通常的异步，分布式， non-Byzantine模型的计算如下：

• agents运行速度不确定，可能停止，也可能重启，但是，不会执行错误的行为。
• agents通过消息发送来进行通信，消息发送速度不确定，可能乱序，冗余，或者丢失，但是，不会崩溃。

一致性协议的安全性要求如下：

• 非平凡性：只有被提交的提案可以被学习到
• 一致性：至多只有一个提案可以被学习到。

大部分一致性算法都能满足非平凡性。因此将不在做过多解释。一致性需要满足acceptors只能选择一个提案，同时只有一个提案可以被learners学习到。其中最难的部分是确保只有一个提案被选择。后则则相对简单。所以我将集中介绍前者。

安全性需求需要的满足不应受成员失败影响。一致性算法同时应该满足一个运行需求，即，只要有足够多的正常运行的agents，就应该能够选出最终的提案。我们不期望依赖于proposers和learners，因为他们并不可靠。例如，客户端/服务器系统中，客户端可能扮演proposers和learners角色，我们不希望系统因为客户端无法响应而宕掉。系统正常运行应该只要求有足够正常运行的acceptors，和至少一个能提案的proposers，至少一个能学习的learner。然而这样的条件需求也是被质疑的。。。因此需要一些额外的限制。针对不同的算法，添加相应的设定。稍后，我会详细介绍Paxos算法的运行属性，涉及对于“nonfaulty”的定义，及这些属性是如何满足安全性要求的。

在所有agents正常运行的情况下，系统必须能够正常运行。即使这些agents失败并重启过。因为提案可能在agents宕机前已经被学习过，因此agents必须拥有不受宕机和重启影响的稳定的存储机制。我们假定agents重启后，通过稳定的存储恢复到之前的状态。因为系统无法区分agents的宕机和暂定，所以也没有必要去定义过于明确的失败模型。

2.2 Safety

2.2.1 The Basic Algorithm

我们首先描述一个满足安全性要求的Paxos一致性协议算法的简单版本，章节2.3会继续讲述满足安全属性要求的完整算法。

算法需要执行多个轮次，每个轮次使用一个正数来标记。轮次执行不必按照标记的顺序，单个轮次也不必完全执行，有时候甚至可以被跳过。多个轮次也可以并发的执行。每个轮次可能会选出一个提案，提案也本就是为了在某个轮次被选择而定义的。在每个轮次期间，acceptors可以选择投票接受某个提案或者不投票拒绝某个提案。提案如果在一个轮次里被大多数acceptors投票选择，则此提案即被选择。为了简化说明，我将以一个永不停止的算法来描述，即使已有提案在某个轮次被选择。算法的终止和优化将会在章节2.4进行讨论。

一致性要求只能有一个提案被选择。因为一个acceptor在一个轮次里只能投票选择一个提案。因为一个agents可能存在于连个majority中，所以可能存在一个轮次里一个agents存在两个选择的提案的情况。然而一个acceptor可以在不同的轮次里选择不同的提案。所以如何保障acceptors在不同的轮次里不选择不同的提案就成为实现一致性最难的部分。

虽然我们会详细描述算法中每个acceptor每一次的投票，但是acceptor却并不需要对此进行记录，一个acceptor a需要只需要维护以下数据：

• rnd[a] a参与的轮次的最高序号（序号为正数，rnd[a]=0代表为参与任何轮次。
• vrnd[a] a参与投标的轮次最高序号，初始为0（ vrnd[a] ≤ rnd[a] ）。
• vval[a] a在轮次vrnd[a]中投票选择的提案； vrnd[a] = 0)时，无值。

Paxos使用一系列成为之 coordinator的agents，通常coordinator和acceptor是是由同一个处理过程担任的。对于每个轮次i，一些 coordinator是预设的。另外，每个coordinator可以服务于无限次轮次。proposers提交提案到 coordinator。轮次i的 coordinator从此次伦次中选择一个提案作为被选择的提案。每个 coordinator c维护一下数据：

• crnd[c] c开始服务的最高轮次号，初始为0.
• cval[c] c在crnd[c]中选择的提案，未选择提案，则为none。crnd[c]为0时，没有关联性。

c作为 coordinator，在轮次i的执行过程如下：

1：

a) 如果crnd[c] < i时，c开始轮次i，然后设置crnd[c]=i，cval[c]=none，发送消息要求各个acceptor a参与轮次i。

b) 当acceptor a接收到请求，并参与到轮次i，如果i>rnd[a]，则 a 设置 rnd[a]=i，然后发送包含轮次序号i及vrnd[a]和vval[a]的消息到 coordinator c；如果i<=rnd[a]（a已经开始轮次i，或者更高的轮次），则 a忽略此次请求。

2：

a) 如果crnd[c]=i（c还没有开始新的轮次），cval[c]=none（c还没执行2a选提案过程），同时，c也没有收到轮次i中，1b步骤大多数acceptors返回的消息。那么执行以下规则，c从提交的提案中选择一个提案v，设置cval[c]=v，然后发送消息到acceptors，要求他们在轮次i中为提案v投票。

b）当一个acceptor a收到要求在轮次i中投票提案v的消息，同时i>=rnd[a]，vrnd[a]!=i；那么a就在轮次i中投票接收提案v。并设置vrnd[a]=i，rnd[a]=i，vval[a]=v,发送消息告知所有的learners它在轮次i中的投票；如果i<rnd[a]或者vrnd[a]=i（a已经开始了更高的轮次，或者已经在轮次i中投了票），则选择忽略此次请求。

当learners在轮次i中接收到大多数acceptors发送的投票提案v的消息后，则认为learner学习到了提案v。

coordinator 可以在任何时候开始1a步骤，然而，却不能发起轮次序号小于当前已经发起的轮次的序号的轮次。不同的轮次可以并发的启动。但是一个acceptor接收到更高序号的轮次消息时，将不再参与低序号的轮次。同一个轮次里，2a步骤只能发送相同的消息。

2.2.2 Picking a Value in Phase 2a

coordinator 在2a步骤选择提案的实现时通过算法确保如下基本属性来实现的：

CP. 对于轮次i和j，j<i，如果一个提案v在轮次j已经或者可能被选择。则在轮次i中，acceptor将只能选择此提案。

同理，如果一个提案v在轮次i中被选择，则在轮次j中将只能选择v。

轮次i中有足够多acceptor投票提案v时，提案v被选中，CP意味着不同的轮次只能选择相同的提案。一个轮次只能选择一个提案。所以CP就说明了一致性。

因为CP表述了一致性要求。所以算法就可通过保持CP来实现一致性。acceptor可以投票的提案v是coordinator在步骤2a中选择的。所以我们只需要确保v符合以下要求：

CP（v，i）：队友任何小于i的轮次j，只有提案v可以被选择。

假定一系列acceptor的majority，其中的acceptor已经或者将要投票提案v，则v表征已选择或者将要被选择。acceptor永远不会减小rnd[a]，并且当轮次j<rnd[a]时，会会略请求。所以我们有以下结论：

观察1：提案v表征在轮次j中被选择或者将要被选择，当且仅当，有足够的acceptor a满足rnd[a]<=j，或者a已经投票选择了提案a。

因为两个majority可能存在acceptor交叉。观察1很容易推到出如下两个观察：

观察2：对于majority中acceptor a，如果rnd[a]>j，并且在轮次j中没有投票，那么轮次j将没有选中的提案。

观察3：对于majority中acceptor a，rnd[a]>j，a投票选择提案v，或者不投票，则对于轮次j，只能是提案v被选中，或者没有选中的提案。

假设coordinator收到轮次i中1b过程大多数acceptors的消息。因为acceptor a会设置rnd[a]=i，同时发送1b过程消息到a，rnd[a]不会被减小，所有的acceptors满足当前的rnd[a]>=i，相应的设置vrnd[a] vval[a]的值，并报告a的轮次i步骤1b的消息。假定vrnd[a]的值k：

K1：k=0

K2：k>0

。。。 。。。