1. 背景

今天刚开始接触 paxos （basic paxos）的时候，真的是觉得其超级晦涩，总感觉不解其意，其实主要还是对其核心解决的问题本身理解不够到位。也就是要很好的理解 Paxos，首先需要理解 Paxos 解决的是什么问题。

在描述之前，我们先统一一个词汇，那就是共识（consensus）和 一致性（consistency），consistency 是数据库中 ACID 中语义，这里我们将 consensus 来描述 Paxos 解决的问题（更多的讨论可以参考 [1]），也就是多个副本（或者多个角色）对一个提案（Proposal 一个提案可能就是一个 Op或者命令）达成共识。（实际 Paxos 算法本身只描述了一个提案的达成，实现者可以根据需要来实现多个连续的提案达成，当然 Paxos 工程实现的难度比较，也因此产生了 Paxos 的衍生算法 Zab 和 Raft 等）

在分布式系统中，其实为了提高可用性、可靠性等，总是会有多个副本，meta server 有多个副本，data 也有多个副本，多个副本虽然能提高可靠性和可用性，但是也带来了新的问题，那就是需要保证多个副本之间的共识，也就是多个副本对任何一个提案（或者说 Op）是一致的，一个 Op 如何来达到共识，就像 4 个人提案去哪里吃饭，需要保证一些基本的特性：

• safety：多个副本之间对某个决议能够达成一个共识，且不能被篡改，4 个人终能决定终去一个相同的地方吃饭，不能说 4 个被分成两拨，一个去 A 地点吃饭，其他 3 个去 B 地点吃饭
• liveness：多个副本之间对某个决议能够在有限的时间内形成，不能说 12 点开始决议去吃饭，结果 14 点了还没形成共识，那么也是不行的

这两点会在第 3 小节详细分析。Paxos 算法就是解决多个副本之间如何来形成一个共识。

2. 算法描述

paxos 算法分为两个阶段，Prepare 和 Accept 阶段，下面将详细描述：

2.1. Proposal Numbers

一个 Proposal 是由 Proposal number 和 Proposal value 组成的，首先来看 Proposal number，既然针对一个 Proposal，那么每个 Proposal 都必须有一个的 ID，也就是 Proposal Number，其有几个基本特性（注意后文不区分 Proposal number 和 Proposal Id）：

• 全局，无论是相同的 Proposer 的不同 Proposal 还是，还是不同的 Proposer 的相同或者不同 Proposal
• 单调递增，越大优先级越高

下面给出文献 [3] 的一个简单方法：

2.2. Persistent state per server

接着来看需要每个机器需要持久化哪些状态，参考文献 [2]

• minProposal：server 接收到的小的即将 accept 的 Proposal number，如果是 0 表示 server 没有收到任何的 Prepare request
• acceptProposal：server 后一次 accept 的 Proposal 的 number ，如果是 0 表示 server 没有 accept 任何 Proposal
• accept value ：近 server accept 的 Proposal 的 value，如果是 null 表示 server 还没有 accept 任何的 Proposal
• maxRound：server 所看见的大 round number，这个和 2.1 的 Proposal number 实现有关

2.2. Prepare 阶段

哈哈，这里直接使用文献 [4] 何登成老师的中文版啦，非常赞的 PPT。

第二个承诺是为了保证，自己的 Proposal 能够被 accept

2.3. Accept 阶段

继续用何老师的图啦。

有一个关键点，也就是大多数（也就是通常所说的 quorum 机制），也就是收到大多数 server 的应答 propose。大多数其实也就是保证 safety 的核心机制。

（Notes：算法介绍完啦，不过还是建议读者可以参考文献 [2] 的 basic paxos 描述，非常的短小精悍，相比原论文，更加简单，相比一般的博客，更加准确，让读者理解不会陷入任何误区）

3. 算法分析

算法本身是比较抽象，还是需要通过很多的例子来慢慢理解，并且分析 Paxos 的一些关键特性，这里主要参考文献 [3] 的例子。

3.1. Safety

• quorum 机制

因为两个半数必然有相交，这样就不可能到存在两个value被同时终接受造成不一致。而且可用性更好，可以容忍半数以下机器失效

• 后者认同前者

就是一旦一个acceptor接受一个确定性取值之后，后者会认同前者，不会进行破坏（这个取值其实是学习到的，认同前者，就是）。这样实现一种自动的往“某个提议值被多数派接受并生效”这一终目标靠拢。如下例子：

就是 Proposal 3.1 X 被 accept 之后，S5 将会学习到这个 value 并提交，这就保证了一个 Proposal 一个单被 accept，后面 Proposer 不会去破坏这个 Proposal。

再看一个后者认同前者的例子：

图，Proposer Y，在s3中学习到了A X，那么它会继续促成X值这个决议的达成，对proposer X来说，只要大多数，s1，s2和s3都返回，那么x值这个决议就达成了，就可以放心的干其他的事情了。因为尽管proposer Y还是运行，但是它一定会学习到这个X值，并且进入accpet阶段，终也是形成X值的这个决议。

这实际上也paxos核心解决的问题。

当一个提议被多数派接受后，这个提议对应的值被Chosen（选定），一旦有一个值被Chosen，那么只要按照协议的规则继续交互，后续被Chosen的值都是同一个值，也就是这个Chosen值的共识问题。

3.2. Liveness

• 不会死锁（抢占式）

在 Proposal 和 Accept 有两个阶段都有两个承诺，例如，大的 Proposal Id 会覆盖让前一个 Proposal accept 失败，这样有什么好处呢 ？这里其实就是为了保证不会出现死锁，如可以让大 Proposal Id 可以抢占前面小的 Proposal id propose 权利，继续进行，因为如何 S1 在收到大多数的 Propose 回复之后挂了，不支持抢占的模式将会造成死锁

• 但是会活锁

如下例子，两个提案不断的出现 Prepare 阶段抢占。尽管出现的概率很小，但是从理论，确实存在活锁的可能性。

不过解决方案也相对不难，只需要随机超时重试即可。

4. 思考

4.1. 为什么需要 Propose 阶段？

因为对 paxos 来说，是假定一个集群中会有多个paxos instance（也就是多个提案）同时存在竞争的（并发冲突）。那么 propose 阶段就是选择出需要进行投票的paxos instance。如果能够保证只有一个paxos instance，那么就无需 propose 阶段了，直接进行accept即可。所以对于multi-paxos中，存在一个leader，可以控制每个时刻只有一个paxos instance在集群中，所以不需要propose阶段，只需要执行accept阶段即可。

这里就相当于一个add 1 的paxos instance，一个 delete key 的paxos instance。只有当整个集群指定的 paxos instance 的顺序是相同的，也就是，也就是每个节点都是先add 1，然后在 delete key，或者先delete key，再add 1，后的数据才会一致。它本质上解决的就是有多个议案的情况下， 达成一个一致的议案，例如，一群人决定聚餐，有想吃鱼的，想吃火锅的，这样多个决议进行 paxos 提案投票，就会得到一个一致的聚餐结果。如果没有多个决议，只有一个决议，那就不会冲突，直接accept投票即可。

Paxos Propose 的意义

• Block old proposals
• Find out about (possibly) accepted values

4.2. Paxos 只负责达成一个决议？

paxos只负责达成一个提案，一旦达成之后，其他的proposer就没有办法修改了，也就是说其他 proposer 再怎么重复的提交 propose，都只会学习到已经达成一致的 Value 值，然后重复提交：比如说多一个人决议去哪里吃饭，有些人是 proposer，所有人都是 acceptor，这些 proposer 都提除不同的吃饭地点，然后发表提案，终paxos 达成吃饭地点的提案就可以了。如果是多个不同的提案都需要做，实际上 paxos 并没有定义如何去实现，这是 multi-paxos 做的事情，后面会单独讨论。

5. 总结

Basic Paxos 算法作为共识算法的鼻祖，值得细细体会和学习，只是入门的时候稍微会比较难以正确理解，但是一旦理解了，就会觉得很简单精妙，

Notes

水平和时间有限，论文很多细节没看那么细，难免有错误和理解不到位的地方，欢迎指出和交流，除此之外，部分图片来源其他的文献，尽管指出了文献出处，但难免会存在侵权等行为，如有，麻烦联系我，将时间修改和删除。

参考文献

[1]. https://www.zhihu.com/question/275845393/answer/386816571

[2]. . paxos-summay. https://ramcloud.stanford.edu/~ongaro/userstudy/paxossummary.pdf

[3]. Implementing Replicated Logs with Paxos. https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pdf

[4]. PaxosRaft 分布式一致性算法原理剖析及其在实战中的应用

[5]. Lamport L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.