Distributed Consensus Algorithm

There is only one consensus protocol, and that's “Paxos” — all other approaches are just broken versions of Paxos

世界上只有一种共识协议，就是 Paxos，其他所有共识算法都是 Paxos 的退化版本。

—— Mike Burrows，Inventor of Google Chubby

问题产生的背景

Paxos 问题是指分布式的系统中存在故障（fault），但不存在恶意（corrupt）节点场景（即可能消息丢失或重复，但无错误消息）下的共识达成（Consensus）问题。因为最早是 Leslie Lamport 用 Paxon 岛的故事模型来进行描述而命名。

• 少数服从多数，最终达成一致意见。
• 基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。
• Paxos 是第一个被证明的共识算法，其原理基于 两阶段提交 并进行扩展。

Paxos 算法分为核心算法和完整算法两部分。Paxos 算法的核心部分解决了分布式领域当中非常重要的基础问题，也就是共识问题；完整算法是用来实现状态机的算法。

两个比较明显的缺点：

1. 难以理解
2. 工程实现更难。

共识问题

不严格地说，共识问题就算多个进程对一个值达成一致，每个进程都可以提议（propose）一个自己想要的值，但是最终只有一个值会被选中，并且所有进程对这个选中的值达成一致。

共识算法注意点

• 可以是任意多个进程
• 所有进程都可以提议一个值
• 所有进程都可以学习到被选中的值

共识算法的要求

共识算法有两个要求，安全要求和存活要求

安全要求是指：

• 只有一个被提议的值可能被选中
• 只有唯一的一个值被选中
• 只有一个值实际已经被选中，一个进程才能学习到这个值

存活要求是指：某个被提议的值最终一定会被选中，并且如果一个值被选中，那么一个进程最终能够学习到这个值。

Paxos共识算法

算法的角色

作为现在共识算法设计的鼻祖，以最初论文的难懂（算法本身并不复杂）出名。算法中将节点分为三种类型：

• proposer：提出一个提案，等待大家批准为结案。往往是客户端担任该角色；
• acceptor：负责对提案进行投票。往往是服务端担任该角色；
• learner：被告知结案结果，并与之统一，不参与投票过程。可能为客户端或服务端。

在多副本状态机中，每个副本同时具有Proposer、Acceptor、Learner三种角色。

Paxos-Roles

并且，算法需要满足 safety 和 liveness 两方面的约束要求（实际上这两个基础属性是大部分分布式算法都该考虑的）：

• safety：保证决议结果是对的，无歧义的，不会出现错误情况。

  • 决议（value）只有在被 proposers 提出的 proposal 才能被最终批准；
  • 在一次执行实例中，只批准（chosen）一个最终决议，意味着多数接受（accept）的结果能成为决议；

• liveness：保证决议过程能在有限时间内完成。

  • 决议总会产生，并且 learners 能获得被批准（chosen）的决议。

基本过程包括 proposer 提出提案，先争取大多数 acceptor 的支持，超过一半支持时，则发送结案结果给所有人进行确认。一个潜在的问题是 proposer 在此过程中出现故障，可以通过超时机制来解决。极为凑巧的情况下，每次新的一轮提案的 proposer 都恰好故障，系统则永远无法达成一致（概率很小）。

Paxos 能保证在超过的正常节点存在时，系统能达成共识。

读者可以试着自己设计一套能达成共识的方案，会发现在满足各种约束情况下，算法自然就会那样设计。

考虑的场景

单个提案者+多接收者

如果系统中限定只有某个特定节点是提案者，那么一致性肯定能达成（只有一个方案，要么达成，要么失败）。提案者只要收到了来自多数接收者的投票，即可认为通过，因为系统中不存在其他的提案。

但一旦提案者故障，则系统无法工作。

多个提案者+单个接收者

限定某个节点作为接收者。这种情况下，共识也很容易达成，接收者收到多个提案，选第一个提案作为决议，拒绝掉后续的提案即可。

缺陷也是容易发生单点故障，包括接收者故障或首个提案者节点故障。

以上两种情形其实类似主从模式，虽然不那么可靠，但因为原理简单而被广泛采用。

当提案者和接收者都推广到多个的情形，会出现一些挑战。

多个提案者+多个接收者

既然限定单提案者或单接收者都会出现故障，那么就得允许出现多个提案者和多个接收者。问题一下子变得复杂了。

一种情况是同一时间片段（如一个提案周期）内只有一个提案者，这时可以退化到单提案者的情形。需要设计一种机制来保障提案者的正确产生，例如按照时间、序列、或者大家猜拳（出一个数字来比较）之类。考虑到分布式系统要处理的工作量很大，这个过程要尽量高效，满足这一条件的机制非常难设计。

另一种情况是允许同一时间片段内可以出现多个提案者。那同一个节点可能收到多份提案，怎么对他们进行区分呢？这个时候采用只接受第一个提案而拒绝后续提案的方法也不适用。很自然的，提案需要带上不同的序号。节点需要根据提案序号来判断接受哪个。比如接受其中序号较大（往往意味着是接受新提出的，因为旧提案者故障概率更大）的提案。

如何为提案分配序号呢？

一种可能方案是每个节点的提案数字区间彼此隔离开，互相不冲突。为了满足递增的需求可以配合用时间戳作为前缀字段。

此外，提案者即便收到了多数接收者的投票，也不敢说就一定通过。因为在此过程中系统可能还有其它的提案。

算法的选择值和学习值的过程

共识算法分为两个过程，即选择一个值和学习一个值，具体如下：

• 在选择一个值的过程中，一组 proposer 中每一个 proposer 都可以提议任意一个值给一组 acceptor ，这组 acceptor 会从所有的 proposer 提议的值中选出唯一的一个值。
• 在学习一个值的过程中，learner 从 acceptor 中学习到被选中的值

选择值具体过程

选择值过程是一个二阶提交的过程，第一阶段选择提议编号，第二阶段接受提议的值。

• 1.1：一个 proposer 生成一个新的提议编号 n，n 大于上一次使用的提议编号。并且发送 prepare(n) 消息给大多数 acceptor

• 1.2：如果一个 acceptor 收到一个提议消息，并且 n 大于本地承诺过的提议编号，则用 n 更新本地承诺过的提议编号。如果有接受过其他的提议，则将提议的编号和值一起返回，如果没有返回提议的编号和 null；

• 2.1：如果一个 proposer 收到大多数 acceptor 回复的承诺编号为 n 的 promise 消息，则构建一个新的提议，提议编号为 n，提议值为 v。v 按照如下规则确定：

• 如果在所有的这些 promise 消息中有携带提议的，则用提议编号最大的提议中的值

• 如果在所有的这些 promise 消息中没有携带提议的，则可以用 proposer 自己要提议的值。这个 proposer 给这些 acceptor 中的每一个节点都发送确认消息

• 2.2: 如果一个 acceptor 收到确认消息，且 n 大于本地承诺过的编号，则接受提议中的值，并持久化存储。

  
  Paxos-chooseValueProcess1
  

  从这个过程可以看出，acceptor3、acceptor4、acceptor5 接收到 (2, X) 的提议后，会接受这个提议。5 个 acceptor 最终接受的提议是不同的，有 (1, X) 以及 (2, X)。但是其中的值是相同的，也就是对值达成了共识，不要求提议编号也一致。

学习值具体过程

学习值和选择值类似，也是一个二阶提交的过程：

3.1 当 acceptor 接受一个提议后，向所有的 learner 通知这个提议

3.2 如果 learner 收到 acceptor 的通知，则接受这个提议。如果 learner 接受从大多数 acceptor 收到的某个提议，则这个 learner 接受提议中的值。

Paxos-chooseValueProcess2

从图中可以看出，learner 消息的数量是 acceptor 的数量与 learner 的数量的乘积，为了减少消息的数量，可以指定一个learner 为 Leader，acceptor 接受提议后，向 learner 的 Leader 发送 learn 消息，Leader 收到大多数消息后，接受请求中的值再向其他 learner 发送 learn 消息。

详细流程说明

准备阶段

• 一个节点选择成为leader，选择一个序列号x和值v来创建一个提议P1(x, v)。leader将这个提议发送给acceptor，等待大多数节点的返回。

• acceptor在收到提议P1(x, v)后，判断：

  • 如果提议是该acceptor要接受的第一个提议，回复“同意”，承诺leader该acceptor未来不会接受小于x的请求。

  • 如果该acceptor之前有接受过提议：

    • 比较x和之间和之前接受的最高序列号的提议，比如P2(y,v2)
    • 如果x<y，回复拒绝和y值
    • 如果x>y，回复同意和P2(y, v2)

提交阶段

• 如果大多数的acceptor回复“拒绝”或者没有回复，leader取消本次提议。

• 如果大多数的acceptor回复“同意”，leader也能知道acceptor已经接受的提议。leader从这些值中任选一个值（如果没有值被接受，选择自己的值），发送“接受请求”消息，带着提议的序列号和值(x, v)。

• 当acceptor收到“接受请求”消息，如果满足下面的两个条件，就发送“接受”，否则返回“拒绝”。

  • v和之前接受的某个值相同
  • x是该acceptor所接受提议中序列号的最大值

• 如果leader没有从大多数节点中收到“接受”消息，leader取消这次提议然后重新开始；如果leader从大多数节点中收到了“接受”消息，本次协商就结束了。作为优化，leader可以发送“提交”消息给其他的节点。

一旦多数接受了共同的提案值，则形成决议，成为最终确认的提案。

共识算法总结

整合前面的选择值和学习值的过程，共识算法一共有如下步骤：

• proposer 向大多数 acceptor 发起提议编号。
• acceptor 根据规则(编号最大)接受提议编号，并回复 proposer
• proposer 接受到大多数 acceptor 的回复后，再根据规则(是否存在已承诺的值)选择一个值发送确认消息。
• acceptor 接受到确认消息后接受消息中的值，并向 learner Leader 发送 learn 请求
• learn Leader 接受到大多数的学习请求后，向其他的 learner 发送学习请求，同步这个值。

到此，proposer 提议的值就被同步到所有的 learn 中，共识算法结束。

总结一下，其实Paxos算法通过一个决议分为两个阶段（Learn阶段之前决议已经形成）：

1. 第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。
2. 第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。

3. 第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。

   
   01-technology_C-architecture_C01-archBase_Paxos-ElectionProcess.png

Paxos算法流程中的每条消息描述如下：

• Prepare: Proposer生成全局唯一且递增的Proposal ID (可使用时间戳加Server ID)，向所有Acceptors发送Prepare请求，这里无需携带提案内容，只携带Proposal ID即可。
• Promise: Acceptors收到Prepare请求后，做出“两个承诺，一个应答”。

两个承诺

1. 不再接受Proposal ID小于等于（注意：这里是<= ）当前请求的Prepare请求。

2. 不再接受Proposal ID小于（注意：这里是< ）当前请求的Propose请求。

一个应答

不违背以前作出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。

Multi-Paxos（Paxos 完整算法）

Paxos 共识算法只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。如果想连续确定多个值，Paxos 共识算法搞不定了。因此 Paxos 共识算法几乎只是用来做理论研究，并不直接应用在实际工程中。

实际应用中几乎都需要连续确定多个值，而且希望能有更高的效率。Multi-Paxos正是为解决此问题而提出。Multi-Paxos基于Paxos 共识算法做了两点改进：

1. 针对每一个要确定的值，运行一次Paxos算法实例（Instance），形成决议。每一个Paxos实例使用唯一的Instance ID标识。
2. 在所有Proposers中选举一个Leader，由Leader唯一地提交Proposal给Acceptors进行表决。这样没有Proposer竞争，解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下，Prepare阶段就可以跳过，从而将两阶段变为一阶段，提高效率。

Paxos 完整算法——Multi Paxos，就是多次运行 Paxos 共识算法，形成多个实例的算法。类似于每个进程都会形成一个数组，数组中的每个元素都是一个达成一致的值。

异常情况处理

脑裂问题

Paxos 共识算法会保证即使有多个进程认为自己是 Leader ，也就是出现脑裂的情况，每个实例最终也只能有一个值被选中——每个 Leader 提议值的时候都有提议 id，而 learn 每次只能接受一个提议 id。

进程1 (Leader 1) 不一定每次都能成功，也会出现失败的情况。当进程1 成为 Leader，提议通过了一个值，该值还未被进程2(learn) 完全学习，这时进程3 也认为自己是 Leader 并让进程2 接受了自己的提议(更大的提议编号)，导致进程1 同步给进程2 的内容失效。

空洞处理

各实例是可以并发执行的，这可能会导致一个问题：如果在第一个实例的值的确认过程中出现消息丢失或者网络延时，第一个值没有被确定。同时 Leader 开始了第二个实例，并且第二个实例的值成功确定，那个第一个实例的值是空的，第二个实例的值是确定的，这种情况被成为空洞。

如果 Leader 法西安某个消息在一定时间内没有得到回复，那么 Leader 可以重发这个消息。通过重发机制，空洞最终会被填补上。

如果是这时发生 Leader 切换，则情况会有所不同。如果旧的 Leader 的提议已经被接受，那么新的 Leader 会继续保持这个提议——新的 Leader 重发相同的消息；如果旧的 Leader 的提议还没有被接受，则新的 Leader 可以提议一个新的值。不管怎样，这个空洞最终都会被填补上。

Paxos 算法应用

A. database replication, log replication等

如bdb的数据复制就是使用paxos兼容的算法。Paxos最大的用途就是保持多个节点数据的一致性。

B. naming service

naming service, 如大型系统内部通常存在多个接口服务相互调用。

1. 通常的实现是将服务的ip/hostname写死在配置中，当service发生故障时候，通过手工更改配置文件或者修改DNS指向的方法来解决。缺点是可维护性差，内部的单元越多，故障率越大。
2. LVS双机冗余的方式，缺点是所有单元需要双倍的资源投入。
   通过Paxos算法来管理所有的naming服务，则可保证high available分配可用的service给client。象ZooKeeper还提供watch功能，即watch的对象发生了改变会自动发notification, 这样所有的client就可以使用一致的，高可用的接口。

C. config配置管理

1. 通常手工修改配置文件的方法，这样容易出错，也需要人工干预才能生效，所以节点的状态无法同时达到一致。
2. 大规模的应用都会实现自己的配置服务，比如用http web服务来实现配置中心化。它的缺点是更新后所有client无法立即得知，各节点加载的顺序无法保证，造成系统中的配置不是同一状态。

D. membership用户角色 / access control list

在权限设置中，用户一旦设置某项权限比如由管理员变成普通身份，这时应在所有的服务器上所有远程CDN立即生效，否则就会导致不能接受的后果。

E. 号码分配

通常简单的解决方法是用数据库自增ID, 这导致数据库切分困难，或程序生成GUID, 这通常导致ID过长。更优雅的做法是利用paxos算法在多台replicas之间选择一个作为master, 通过master来分配号码。当master发生故障时，再用paxos选择另外一个master。

F. 原子广播

原子广播协议用于把消息向广播对象进行广播，并且保证消息能够被可靠地收到，且所有广播对象以相同的顺序收到。

原子广播协议通常被定义包含以下两个动作：

• ABroadcast(v)：广播动作，当客户端想广播值 v 时，调用这个动作。
• v=ADeliver()：投递动作，客户端通过这个动作接收其他客户端提交的值。这个动作一般是一个回调，当有值要被接受时，客户端会被回调。

原子广播的特性——原子广播保证：如果一个进程调用了广播动作，那么所有的客户端的投递动作都会被回调，并且调用顺序与调用广播的顺序一致。

Paxos算法与原子广播

在基于 Paxos 算法的原子广播的实现中，原子广播黑盒内部由一组进程组成，原子广播内部包含 proposer 和 acceptor 角色，接收广播回调(aDeliver)的 client 作为 learner 角色。

当一个 client 调用 ABroadcast(v) 动作时，这个请求会作为一个提议给到 proposer ，经过大多数 acceptor 达成共识后，该值同步给所有的 learner。learner 接受到这个值后，完成对 aDeliver() 动作接口的回调。

其他

Google 的 Chubby；

Yahoo! 的 ZooKeeper 是一个开源的类 Paxos 实现。

总结

Paxos 又分为两个算法，Basic Paxos (共识算法) 和 Multi Paxos (完整算法)。共识算法包括选择值和学习值两个具体过程，具体步骤可以概况为三个阶段：

• 第一阶段：确认大多数节点可接受提议编号
• 第二阶段：提交提议，同步值给大多数 acceptor
• 第三阶段：同步值给所有 learn 节点

完整算法则是多次运行 Paxos 共识算法，解决共识算法在工程中的应用问题。完整算法中的 Leader 也是通过共识算法达成一致。