Paxos——分布式一致性算法

Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。

Paxos算法问世已经有将近30年的历史了，是目前公认最有效的解决分布式场景下一致性问题的算法之一，但是缺点是比较难懂，工程化比较难。本文希望能够辅以图例和通俗易懂的实例把Paxos算法讲清楚。

Paxos算法的价值

在分布式系统中，在异步通讯的过程中，总会发生网络波动、机器宕机等情况，那么如何在这样复杂的情况下，快速且安全的就某一数值达成一致呢？Paxos算法主要就是解决此类问题，在布式锁、主从复制、命名服务、分布式协调等常见场景下，Paxos算法都有着广泛的应用。

基本概念

参与角色

在Paxos算法中，所有的参与者被分为了以下几个角色

• 提案：提案是由编号及Value组成，Paxos算法需要我们保证提案的编号Id全局唯一有序（具体有很多种实现，不在本文的讨论范围内）。
• Quorum：直译为法定人数，在Paxos中意为任意两个Quorum都包含至少一个公共成员，可以理解为包含Acceptor集合中的大多数成员。如一共有2F+1位Acceptor，则Quorum人数为F+1位。
• Proposer、Acceptor、Learner只是角色的分工，在具体实现中，一个进程可能担当不止一种角色。

Paxos算法正确的必要条件

现在将算法的参与者分为了这样三个角色，那么是为了让他们完成什么样的工作目标呢？

一个分布式算法有两个最重要的属性：活性、安全性

• 活性意为“预期的事情最终一定会发生”，最终一致性就是一种活性。
• 安全性意为违背了安全性规则，则系统会发生损失。

我们可以从这两个方面来考察Paxos算法的正确性

活性：

​ 保证最终有一个提案会被选定，当提案被选定后，进程最终最终也能获取到被选定的提案。

安全性：

• 提案(value)只有在被 proposers 提出后才能被批准。
• 在一次 Paxos 算法的执行实例中，只批准(chosen)一个 value。
• learners 只能获得被批准(chosen)的 value。

那么我们下面来看看具体的算法流程

算法流程

算法描述来自于倪超《从Paxos到ZooKeeper分布式一致性原理与实践》

提案的提出和批准

• 阶段一
  1. Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。
  2. 如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。
• 阶段二
  1. 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。
  2. 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。

提案的发布

1. acceptors需要将accept消息发送给learners的一个子集，然后由这些learners去通知所有learners。
2. 但是由于消息传递的不确定性，可能会没有任何learner获得了决议批准的消息。当learners需要了解决议通过情况时，可以让一个proposer重新进行一次提案。注意一个learner可能兼任proposer。

从上图看到,作为Acceptor只需要存储批准/保证过的提案的最大编号(MaxN)，批准过的提案的最大编号(AcceptN)，批准过的提案的Value值(AcceptV)，然后通过阶段一(2)和阶段二(2)的两种规则进行对提案的审批，即能够保证审批的安全性。

而Proposer需要保证在阶段一(1)时提出的提案编号唯一且单调递增，而在阶段二(1)时只对获取到了足够多的保证（即获得了大多数Acceptor对Proposer的保证）的提案进行提交，即能够保证提案申请的安全性。

那么为什么这样能够满足上面所述的分布式算法的安全性呢？这个要从Paxos算法的推导来看。完整的推导过程可以在wikipedia上看到。

下面我来谈一谈我的理解，在推导过程中有这么几个重要的约束：

P1：一个 acceptor 必须接受（accept）第一次收到的提案。 P1a：当且仅当acceptor没有回应过编号大于n的prepare请求时，acceptor接受（accept）编号为n的提案。 P2：一旦一个具有 value v 的提案被批准（chosen），那么之后批准（chosen）的提案必须具有 value v。 P2a：一旦一个具有 value v 的提案被批准（chosen），那么之后任何 acceptor 再次接受（accept）的提案必须具有 value v。 P2b：一旦一个具有 value v 的提案被批准（chosen），那么以后任何 proposer 提出的提案必须具有 value v。 P2c：如果一个编号为 n 的提案具有 value v，那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于 n 的任何提案，要么他们已经接受（accept）的所有编号小于 n 的提案中编号最大的那个提案具有 value v。

他们之间的关系可以用下图来说明

当Acceptor仅可批准一个提案时，仅依靠P1，也是能够只批准出一个Value的，但是在这种情况下，很有可能需要多次重复投票过程才能够达到一致性的状态，也就是说虽然能够保证安全性，但是牺牲了部分的活性。如下图所示：

Proposer总是能够优先获得同机房内的Acceptor的批准，但是很难获得其他机房的Acceptor的批准，这时ProposerA、ProposerB、ProposerC各获得一票，每个Proposer的提案都没有通过，此时Proposer只能生成编号更大的提案，以期许能够获得大多数的Acceptor(2个)的批准，也许未来不久，某个lucky dog最终能够获得大多数的Acceptor的批准，但是我们已经等的花儿都谢了。

所以为了能够快速到达一致性，又引入了P2c和P1a，在P1a中解除了Acceptor只能批准一个提案的限制，但是增加了对于批准提案的编号的限制，在P2中增加了对Proposer提出提案的Value值的限制，这两个限制带来的直接效果有两个：

1. 原本Proposer只需要和Acceptor交互一次，现在变成了两次，在Proposer正式提交提案前，Proposer要先获得大多数的Acceptor的状态（prepare请求），以确保提出的提案时，没有已经通过了的提案。因为是大多数的Acceptor，所以如果有已审批的提案，那么一定能够通过这批Prepare请求获知，如果得知已经有审批过的提案，那么代表Proposer已获知本次Paxos执行实例中的决议，并将自己的提案的Value值替换为已审批过的提案的Value值，保证安全性。
2. 因为Proposer在正式提交提案前，已经经过了“严格”的问询和保证，Acceptor也会对审批的编号做审核，所以即使Acceptor能够批准多个提案，但是会保证审批通过的提案的值都具有相同的Value值。从而保证了安全性。

这样讲可能还是比较难以理解，我们现在就上面那个例子做一个图示，分别看看选出提案为A、和提案为B的流程。

• P代表Acceptor对Proposer的Promise
• A代表Acceptor对Proposer提案的Accept
• PE代表保证失败，即图一中的
• AE代表审批失败，即图一中的
• 提案编号由时间戳和机器Id组成，如编号为1.2，则代表在时间戳为1时，机器Id2提出的提案。
• 字母右边的数字代表提案编号，如P1.1代表Acceptor对于编号为1.1提案的Promise
• 中括号[]内为回应内容，如P1.1[1.2:A]代表Acceptor对于编号1.1提案的Promise，并回应“我已经审批通过了编号为1.2，值为A”的提案。

如图四所示，最终形成了值为A的提案。

如图五所示，最终形成了值为B的提案。

这时候停下来思考一下，严格来说，上面描述的牺牲活性问题并没有解决，只是降低了发生了的概率，在极端情况下还是能够发生一种类似于“活锁”的状态的。如下图所示

在极端情况下，这种循环会一直进行下去。所以为了解决这种问题，又提出了Multi-Paxos算法，Multi-Paxos具体算法在这里不做陈述，它是在Proposer中又搞了一个Leader的概念，在初期，所有的Proposer中竞选出一个Leader，然后只有Leader能够向Acceptor提出提案，当Leader发生问题时，再竞选一个Leader出来，没有了Proposer的竞争，两阶段也变成了一阶段，提高了效率，也解决了活锁的问题。但是仔细想想，竞选Leader的过程中也可能会发生活锁的，我估计这也是Raft算法被提出来的真正原因（狗头），毕竟最后绕了一大圈，最终还是搞出了单点的Leader出来进行管理，还不如用上面P1+重试的机制选出Leader，效率平时是差不多的，仅在选举Leader时会比较慢而已。

总结

本文分析了Paxos算法的应用价值和具体实现原理，希望能让大家在学习Paxos算法的过程中能够少掉一点头发。后续可能还会更新我对Raft算法的理解。

作者：王老魔 链接：https://juejin.im/post/5ccc454bf265da03a54c2cb5