6.3.2 Basic Paxos
希望你没有对前篇 Paxos 的「复杂」做的铺垫所吓倒，多副本一致性其实已经算是一个古老的领域，30余年间已经有无数简洁直白的视频、论文等资料进行过描述。譬如在网络中流传甚广的 raft 和 paxos 视频讲解[1]，即使没有多少技术背景，也能通俗地理解 Paxos。
这一节，我们从故事回到算法本身，正式开始学习 Paxos。
Paxos 算法包含两个部分：其中一部分是核心算法（Basic Paxos）；另外一部分是基于核心算法扩展的完整算法（Multi Paxos）。在笔者看来 Basic Paxos 是 Multi-Paxos 思想的核心，说直接点 Multi-Paxos 就是多执行几次 Basic Paxos，所以掌握了 Basic Paxos，我们便能更好的理解后面基于 Multi-Paxos 思想的共识算法（譬如 raft 算法）。
那么接下来我们就看看 Basic Paxos 是如何解决共识问题的。
背景设定
很久以前，在遥远的爱琴海上，有一座与世隔绝的小岛，叫做 Paxos。。。算了，还是换个更对口味的例子吧。
从前有个村，老村长退休了，需要选一个新村长，选取新村长的事件称之为提案（Proposal）。张三、李四都想当村长（张三、李四我们称为提议节点，Proposer），但当村长需要多位村委（决策节点，Acceptor）的投票同意，村委使用少数服从多数投票机制。选举结束之后，要把结果同步给村民（记录节点，Learner）。
如果继续把问题讲下去，笔者似乎通篇都要讲张三、李四的段子，我们还是把背景再转换为分布式工程问题吧。
假如我们设计一个由三个节点 A、B、C（3 个村委）组成分布式集群，提供只读的 KV 存储服务。既然要创建一个只读服务，必须先要对只读变量赋值，而且后续不能对该变量进行修改（村长选定了，结果就不能再更改）。所以，多个节点中，所有的节点必须要先对只读变量的值（提案）达成共识，然后所有的节点再一起创建这个只读变量。
如图 6-3 所示，当有多个客户端（张三、李四，Proposer）访问这个系统，试图创建同一个只读变量（发起一个提案 Proposal，set x=1，提议张三当村长）时，集群中所有的节点（村委）该如何达成共识，实现各个节点中的 x 值的一致呢（所有的民村一致认为张三是村长）？
图 6-3 如何实现多个节点 x 值一致性
实现多个节点 x 值一致的复杂度主要来源于以下两个因素的共同影响：
- 系统内部各个节点的通信是不可靠的。不论是系统中企图设置数据的提议节点，还是决定操作是否批准的决策节点，其发出、收到的信息都可能存在延迟、丢失的情况。
- 客户端写入是并发的，如果是串行的修改数据，仅单纯使用少数服从多数原则，就足以保证数据被正确读写。而并发访问就变成了「分布式环境下多个节点并发操作共享数据」的问题。
我们把上面的背景问题总结转化，其实就是下面两个核心需求：
- 安全性 Safety：
- 一个变量只会被确定一个值（只能一个人当村长），一个变量只有在值被确定之后，才能被学习。
- 活性 Liveness：
- 提案最终会被接受（一定能选出个村长）；一个提案被接受之后，最终会被所有的村民（Learner）学习到。
- 必须在有限时间内做出决议（不能有太多轮投票）。
Basic Paxos 的问题背景相信已经讲清楚了，那怎么解决？
如图 6-4 所示，最简单的场景是多个提议节点、单个决策节点，决策节点接受第一个发给它的值，作为被选中的值，但问题是如果决策节点故障，整个系统就会不可用。
图 6-4 只有一个决策节点会有单点故障
为了克服单点故障问题，我们借鉴多数派（Quorum）的机制，思路就是写入一半以上的节点。如果集群中有 N 个节点，客户端需要写入 W >= N/2 + 1 个节点，那么使用多数派的机制最多可容忍 (N-1)/2 个节点故障。但是问题还是存在，每个决策节点该接受几个提案呢?
我们先看第一种情况，按时序决策节点只接受它收到的第一个提案。但考虑多个提议节点同时对一个提案进行提议，最后可能没有一个提议能够取得多数的投票，出现了平票问题（Split Votes）。如图 6-5 所示，red 和 blue 各有 2 票，没办法确定谁被选择？ 这也就意味着我们无法保证在一轮投票中达成共识，这就无法实现活性（Liveness）需求。
图 6-5 多个决策节点会遇到平票问题
再看第二种情况，决策节点就需要允许接受多个不同的提案，用多数派的机制解决平票问题问题。但新的问题是有了少数服从多数原则，就会碰到冲突的问题。如图 6-6 所示，不同提案节点提议不同的值，可能都会被选择（S3 收到了 blue 和 red，S3 该确认选择哪个值？ ），这就破坏了每个提案只有一个值的原则，这违背了安全性（Safety）的需求。
图 6-6 接受多个不同的提案会遇到冲突问题
注意，Paxos 强调
Once a value has been chosen, future proposals must propose the same value.
也就是说，我们讨论的 Basic-Paxos 只会 Chosen 一个值。基于此，就需要一个两阶段（2-phase）协议，对于已经 Chosen 的值，后面的提案要放弃自己的提议，提出已经被选中的值。例如，S5 发起提案之前，先广播给 S3、S4、S5 这 3 个节点，询问是否已经有接受的提案，如果已有，则撤销自己的提案，S5 的题案由 blue 改为 red，这一阶段在 Basic Paxos 称为准备（Prepare）阶段。
第一阶段实际是分布式抢占锁的过程
如果并发操作一个变量不使用锁，会出现各种意外情况，假设有一个变量 x 在当前系统存储的值是 2，同时有外部请求 A、B 分别对系统发送操作指令，把 x 的值加 1 和 把 x 值乘 3，如果不加任何控制，将可能得到 (2+1)*3=9 或者（2*3+1）=7。
到了分布式环境下，由于要考虑到分布式系统内可能任何时刻出现的通信故障，如果一个节点取得锁之后、释放锁之前发生故障，这将导致整个系统被无限期的等待所阻塞，因此分布式环境中的加锁就不能完全等同于单机系统并发控制中以互斥量实现的加锁，还要提供一个其他节点能抢占锁的机制，以避免因通信问题出现死锁。
仅单纯使用二阶段协议仍然无法解决这个问题，分布式系统中的网络延迟无法忽视。如图 6-7 所示，S1 和 S5 在第一个阶段都发现没有其他的值被选中，因此提出自己的提案，但在这个时序下会有两个不同的值被选中。
图 6-7 网络延迟导致冲突
所以你会发现，矛盾的点其实就是这个 S3，也就是少数服从多数原则，能保证任意的大多数都是有交集的。交集中的点会发现矛盾（和之前接受的值有矛盾理应选择拒绝）。
思考：3 个节点的容忍度是 1，那么 4 节点的容忍度是多少？
答案也是 1，因为要形成发现矛盾的交集对于 4 来说，要达到 3/4，才能构成大多数，这就是为什么集群选单数的原因，因为双数从算法的角度来说没什么帮助。
如图 S3 应该拒绝 S1 的提案，这样就可以保证 S5 的提案成功，S1的提案因为冲突而失败。这种方式我们需要对提案进行排序，有了排序，决策节点就可以拒绝老的提议。如果你熟悉分布式系统，应该能想到《Time, Clocks and the Ordering of Events in a Distributed System》[2] 这篇论文，我们不能简单用时间来判断提案的先后顺序。
1. Basic Paxos 算法描述
现在我们终于可以开始描述 Paxos 算法了。
Basic Paxos 对于此问题的解决方案是，定义一个 Proposal Number 来标识唯一的提案。
一个简单的 Proposal Number 的定义为：<seq_id, server_id>，seq_id 可以是一个自增的 ID，同时为了避免崩溃重启，必须能在本地持久化存储，最后再拼接上 server_id，确保是分布式系统中唯一 ID。
当决策节点收到这个提案后，将会给两个承诺一个应答。
- 两个承诺：
- 承诺不会再接受提案 ID 小于或者等于 n 的 Prepare 请求；
- 承诺不会再接受提案小于 n 的 Accept 请求。
- 一个应答：
- 不违背以前作出的承诺下，回复已经 Accept 过的提案中提案 ID 最大的那个提案的值和提案 ID，没有则返回空值。
我们再具体一点描述 Basic Paxos 算法，首先是准备阶段，选择一个提交号 n，提交 Prepare(n)，接受者需要返回自己接受的值和已经接受的提交号。当从大多数收到回复以后就可以做判断了，如果有返回接受值，选择提交号最大的值进行下一阶段（这个行为对应的是发现有值可能被接受了，尝试服从或者学习这个接受），不然就可以用自己的值进行下一阶段。
下一阶段就是接受阶段 accept(value,n)，如果接受者发现自己目前收到的 n，没有比 accpet 给的 n 大，就接受这个值，并且更新自己的 n，否则就拒绝（这里就保证提交者能够发现自己变老了或者被拒绝了）。如果接受者发现提交号大于自己当前的最大提交号，就接受这个值，不然就拒绝。当提交者从大多数人那里接受到返回以后发现有拒绝的情况，就进行重试拿一个新的 n 开始，否则这个值就被接受了。
总结 Basic Paxos 中的值就是设置一次，不存在再设置一次的情况，整个流程如下图 6-8 所示。
图 6-8 Basic Paxos 流程
2. Basic Paxos 验证
那这样的一个二阶段提交，看看能不能解决前面的问题。假设一个分布式系统中有五个节点，分别是 S1、S2、S3、S4、S5，这 5 个节点同时扮演着提案节点和决策节点的角色。此时，有两个并发请求希望将同一个值分别设定为 X（由 S3 作为提案节点提出）和 Y（由 S5 作为提案节点提出），以 P 代表准备阶段，以 A 代表批准阶段，这时会发生以下几种情况。
情况一：提案已 Chosen 譬如，S1 选定的提案 ID 是 3.1（全局唯一 ID 加上节点编号），先取得了多数派决策节点的 Promise 和 Accepted 应答，此时 S5 选定提案 ID 是 4.5，发起 Prepare 请求，收到的多数派应答中至少会包含 1 个此前应答过 S1 的决策节点，假设是 S3，那么 S3 提供的 Promise 中必将包含 S1 已设定好的值 X，S5 就必须无条件地用 X 代替 Y 作为自己提案的值，由此整个系统对“取值为 X”这个事实达成一致。整个流程如下图所示。
图 6-9 提案已 Chosen
情况二：提案未 Chosen，Proposer 可见 事实上，对于情况一，X 被选定为最终值是必然结果，但从上图中可以看出，X 被选定为最终值并不是必定需要多数派的共同批准，只取决于 S5 提案时 Promise 应答中是否已包含了批准过 X 的决策节点，譬如图 6-3 所示，S5 发起提案的 Prepare 请求时，X 并未获得多数派批准，但由于 S3 已经批准的关系，最终共识的结果仍然是 X。
图 6-10 提案未 Chosen，Proposer 可见
情况三：提案未提交，Proposer 不可见 当然，另外一种可能的结果是 S5 提案时 Promise 应答中并未包含批准过 X 的决策节点，譬如应答 S5 提案时，节点 S1 已经批准了 X，节点 S2 、S3 未批准但返回了 Promise 应答，此时 S5 以更大的提案 ID 获得了 S3、S4、S5 的 Promise，这 3 个节点均未批准过任何值，那么 S3 将不会再接收来自 S1 的 Accept 请求，因为它的提案 ID 已经不是最大的了，这 3 个节点将批准 Y 的取值，整个系统最终会对“取值为 Y”达成一致，如图下图所示。
图 6-11 提案未提交，Proposer 不可见
情况四：出现活锁
从情况三可以推导出另一种极端的情况，如果 2 个提案节点交替使用更大的提案 ID 使得准备阶段成功，但是批准阶段失败的话，这个过程理论上可以无限持续下去，形成活锁（Live Lock）。例如 S3、S4、S5 拿着更高的提交号导致 S1、S2、S3 的 accept 被拒绝重新进行提交，又把 S3、S4、S5 给拒绝了，提议者没有看到先前提议的情况下，当 S1 发现自己的提议没有通过，就会发起新一轮 Prepare RPC，然后就有可能又封锁了 S5 的提议，S5 又会回到 Prepare 阶段，有概率双方都轮流封锁对方的协议，导致无法达成共识。
图 6-12 出现活锁问题
解决这个问题的办法就是把重试时间进行一些随机化，减少这种巧合发生，或者把重试的时间指数增长等等。
总结 Paxos 中保证一致性的最核心的两个原则其实就是少数服从多数和后者认同前者。Paxos Basic 只能对一个值形成决议，而且决议形成至少需要两次网络来回，高并发情况还有可能形成活锁，因此 Basic Paxos 几乎只是用来做理论研究，并不直接应用在实际工程中。