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 个人提案去哪里吃饭，需要保证一些基本的特性：

1. safety：多个副本之间对某个决议能够达成一个共识，且不能被篡改，4 个人最终能决定最终去一个相同的地方吃饭，不能说 4 个被分成两拨，一个去 A 地点吃饭，其他 3 个去 B 地点吃饭
2. 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）：

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

下面给出文献 [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 的意义

1. Block old proposals
2. 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.