Paxos 的魔法学研究报告

Paxos 算法并不长，写在纸上也仅有短短的四句话。它之所以看起来有些像是微言大义的天书，主要是我们并不清楚这几条简单规则背后的设计意图是什么，为什么它能起作用，不采用这些规则是不是就不行？分布式系统的底色是生的自由、死的随机的一片混沌，矛盾冲突无处不在，但是 Paxos 算法却偏偏在这一片混沌之上建立了统一一致的共识世界，这看起来宛如神迹。但是，凡人是很难理解神迹的，他无法站在神的高度俯瞰众生，只能凭借自己有限的生活经验去追索揣摩神的意图，最终必然会产生属于凡人的困惑。本文试图从异次元魔法学的角度对 Paxos 算法做一个解读，建立 Paxos 算法背后简明的魔法学图像，从而实现我们对这个算法的直观理解。

一. 神的烦恼

首先我们来看一下神所面临的问题，以及他可能的烦恼之处。

假设神需要让一队人马去集体完成同样的事情。他所遇到的第一个问题就是所有人都不靠谱。你向 A 分配任务，他可能因为神游物外压根没有听见，也可能反应迟钝、磨磨蹭蹭，最过分的是直接中途躺倒，拒绝工作。这个问题相对来说比较好解决，一个人不靠谱无所谓，只要一堆人中有几个靠谱的就行，先进可以带动后进。神只要每次抓住几个骨干，指导他们把事情做好，剩下的人再从骨干那里学习神谕即可。

真正棘手的问题是，总有很多事情在并行的发生。神刚给 A 分配好工作，正在给 B 讲解的时候，A 的情况又发生了变化（比如接到了别的神的神谕）。神只能屁颠屁颠的跑回 A 处，给他分配新的神谕。这边 A 刚搞定，那边 B 又出新的幺蛾子了，神又忙不迭的拍马赶到。这么搞了几次之后，作为至高无上、全知全能、无远弗届的神，即使脾气再好，他也会忍不住发作的。

二. 九级魔法：时间静止

神是凌驾于一切有限客体之上的最完满的存在，所以他并不会真的遇到上述烦恼。因为，他只要轻轻说一声：定，施展一个九级魔法”时间静止“就可以让这个嘈杂的世界彻底安静下来，然后从容的去做任何他想做的事情。

按照我们这个位面的现代物理学的理解，所谓的时间只是对变化的一种度量。我们通过比较钟摆的周期运动和其他运动的关系来建立时间的概念。如果没有发现任何变化，实际上意味着感知到的时间保持不变。特别的，如果宇宙中所有原子的振荡齐齐的慢了一拍，身处其中的人类是无从发现的。

回顾一下 Paxos 算法的步骤，Proposer 先通过 promise 步骤，从所有 Acceptor 处确定一个唯一的 ProposalID，然后当发生任何需要识别的事件时，例如接到了新的消息，ProposalID 都会自动增加，因此 ProposalID 实际上就是某种时间的标记。当 Acceptor 接收到 accept 消息时，如果发现 ProposalID 与此前 promise 时相比没有变化，则可以判定在此过程中时间保持静止，没有任何需要关注的事件发生。

每一个 Acceptor 都记录了一个只增不减的 ProposalID，相当于建立了本地的时间箭头。而整个系统通过 ProposalID 对齐到同一时间点，相当于是将多个局部的时间箭头对齐后，捆绑为一个粗粒化的、整体性的时间箭头（对齐的前提条件是同样的时间点上发生的事件完全相同，例如设置同样的值）。时间的流逝类似于波阵面扫过整个系统。

所以，从神的视角来看，Paxos 算法不过是通过时间静止魔法，强行将多条时间线对齐为唯一的一条主时间线的雕虫小技而已。

这种”停止-对齐“的技术是我们在分布式系统中获得共识的一种基本策略。例如，在 kafka 消息队列中，同一个消费者分组中的多个消费者是独立行事的，但同时它们必须就如何分配工作达成共识。因此，当消费者分组中的成员增减或者 topic 结构发生变化时，会触发所谓的再平衡（Rebalance）过程。再平衡过程中，Coordinator 首先要求所有 worker 停止当前的工作，集体切换到下一个世代(epoch)，然后再下发新的分配方案。一个分配方案仅在一个世代中有效。

我们在数据库中常用的乐观锁也是同样的处理策略。刚进入处理程序的时候去读取 MainRecord 的版本号，然后再修改 MainRecord 以及相关联的 SubRecord，最后在一个事务中批量提交修改，同时尝试更改主记录的版本号。

  update MainRecord  set version = version + 1  where version = :record_version

如果能够更新成功，说明在整个处理过程中时间静止，没有其他人执行相冲突的动作。

三. 八级魔法：大傀儡术

施展九级魔法是相当消耗魔力的行为。一个具有社会主义核心价值观、勤俭节约的神绝对不会无端的浪费魔力。所以一旦时间静止下来，为了维系分处多地的节点的行为一致，神的最佳选择是施展一个八级魔法”大傀儡术“，将一个节点上的行为复刻到其他所有节点上。

这种复刻源自于神的力量，因此一旦 leader 发动新的动作，它将穿越千山万水，无视物理阻隔直接降临于远端的 follower 身上，follower 没有反驳的权利，只有执行的自由。不过，俗话说的好，上面动动嘴，下面跑断腿。在我们这样一个低魔世界中，实现大傀儡术并不是一件很轻松的事情，一般通过在发送端和接收端各自增加一个日志文件来实现。

发送端把动作决定写入日志，从而使它成为不可变的神谕。发送组件扫描日志系统，确保将其逐条传达到远端。如果连接不上接收端，或者发送出错，或者发送后没有接收到期待的响应信息，发送组件不能抱怨，不能放弃，唯有努力工作，不断重试，直到接收到成功响应为止，这一过程可以保证至少成功发送一次（At Least Once）。接收端必须无条件接收所有消息，不能拒收，不得篡改。因为有可能多次接收到同一个消息，它必须通过本地日志进行幂等检查，过滤掉所有重复消息，从而实现最多成功处理一次（At Most Once）。如果消息需要通过一个流式处理系统（Stream）进行接力处理，为避免每次从源头开始不断重播，需要中间节点能够通过快照机制把已经完成的处理结果记录下来。

毫无疑问，MultiPaxos 和 Raft 算法都是以上复刻策略的一种具体实现。一旦选主成功，代表任期的 Term 编号就可以被多次复用，通过同一个 Term 编号可以发出多条执行指令，只要这些指令通过 log index 能够区分即可。

如果仔细分析一下，我们会发现，从网络上接收到的消息可以分成两类：一类是请求（Request），接收方可以自由选择相应的处理方式，处理结果也是不确定的，可以成功返回也可以抛出异常。另一类是单向的通知（Notice），它对应的处理方式是固定的，接收方不能有反驳的意见。i

一个有趣的例子是两阶段提交。在 Prepare 阶段，Participant 接收到的是请求消息，因此它可以根据自己的独立意志选择提交或者回滚。一旦 Participant 将自己可能的选择返回给 Coordinator，它就向 Coordinator 让渡了自身的自主权，许诺今后只接收通知消息，将行为与 Coordinator 保持一致。当 Coordinator 决定提交时，Participant 绝不会选择回滚。同样的，Participant 如果回滚，我们知道 Coordinator 的选择也只能是回滚。它们两者的选择不再是独立的做出，而是纠缠在了一起。

如果我们单独看待各个 Participant 和 Coordinator，它们各自都可能随机的处于提交和回滚两种状态。但是如果我们把它们作为整体来看待，我们会发现并不是所有状态都是可能的，只有|提交，提交>和|回滚，回滚>是整个状态空间中允许的状态，也就是说 2PC 运行的过程中，整个系统实际处在|提交，提交>和|回滚，回滚>所构成的量子纠缠态中！

基于上面的考虑，在我们这个位面中，量子纠缠不失为实现傀儡术的一种可行机制。

四. 魔法学的秘奥：看不见的即不存在

作为一介凡人，我们并没有魔力去驱动魔法。但是我们都看过魔术，也都经历过所谓”见证奇迹的时刻“。奇迹的诞生源于魔术师引导我们只去观察显露出来的事实，under the hood 的秘密则是不足为外人道也。魔法作为魔术的加强版，本质上的原理也是类似的：只要确保所有不符合魔法学原理的事实都从我们的认知中删除就好了！

Paxos 算法运行起来之后，我们试图让时间静止下来，但是恼人的干扰信息总是不停出现。Acceptor 有可能会接收到来自过去的消息（ProposalID 小于当前值），Paxos 算法的解决方案就是假装没看见，直接扔掉！另一方面，Acceptor 也有可能会接收到来自未来的消息，最简单的解决方案仍然是直接扔。但是这样的话会产生类似分布式锁的情况，导致容错性不够：在本次时间静止的周期里，有可能 Proposer 已经挂掉，没法继续完成向 Acceptor 设值的任务。所以面对当前和未来两个抉择，为稳妥起见，Acceptor 只能放弃本次周期已经取得的成果，选择未来的可能性（魔法失败并不丢人，假装没看见，继续下一轮呗）。当然，如果 Acceptor 已经通过 Learner 机制知道当前值已经被选定，那就没有必要继续运行下一轮 Paxos 算法了，可以直接拒掉来自未来的请求。类似的，在 Raft 协议中，为了避免集群不断重新选举导致振荡，在一定时间内只要通过心跳信息确定 Leader 仍然存在，则来自未来的 RequestVote 消息也会被无情的抛弃。

在需要 Leader 选举的算法中，一个经典的问题是如何避免脑裂？如果新生代的 Leader 已经得到了人民的拥护，而老一代的 Leader 却不肯退位，总在那里不停的搅局怎么办？一个一般性的解决方案就是：直接把旧 Leader 定义为 zombie, 彻底忽略来自上一个世代的所有信息（比如拒绝所有 epoch 较小的请求）。实际上，我们并没有限制旧 Leader 的行为，在自己的小世界中，它完全可以自以为是的为所欲为，只不过它的行为最终无法上升为集体意志，无法对主世界产生影响而已。新的 Leader 一继位，需要未读先写，先在主世界中打上自己的 epoch 标记（类似于更改全局共享变量），这样老的 Leader 在提交计算结果的时候通过乐观锁发现自己已经失势，最终只能无奈放弃自己的处理结果。

在我们这个位面的物理学中，随着量子力学的发展，观察或者说测量已经具有了非常独特的理论意义。按照量子场论所描绘的视图，在我们看不见的虚时间中，无数狂野的事物在相互竞争、湮灭，最终反映到现实世界中的只是某种综合运算后的结果而已。透过诡异的量子隧道效应，实际上我们也可以窥见这背后的惊涛骇浪。

掩耳盗铃并不是一个荒唐的笑话，而是在我们这个世界中可以真实运行的法则。如果能有效的制造遮蔽一切的信息茧房，它是可以操纵我们所认知的世界真相的。所以，懂王，一个号称无限接近于神的男人，一直在疯狂的暗示：不检测，新冠肺炎就不存在！作为一个泄漏天机的盗火者，懂王，他真的很懂。

五. 凡人的共识：对称的破缺

神说，众生平等。用数学的语言来解释，就是每个人都没有特殊性，他们是对称的（Symmetric）！一个社会不能只有一种声音，每个人都可以有自己的意见，每一种意见都值得得到同样的尊重，那凭什么最后有一个人的声音被选择出来，盖过所有其他人的声音，最终成为所有人的共识？本质上，这是一个打破平等的过程，数学上称之为对称破缺（Symmetry Broken）。

最基本的一种对称破缺技术是多数派投票。因为一个集合里不可能同时存在两个多数派，所以只要在任意一个时刻（由 ProposalID 来确定），我们知道多数 Acceptor 都接受了某个值，我们就说这个值成为了被选定的值（chosen value），共识就达成了。

什么时候达成的共识？

当共识出现的时候，参与者中有谁知道已经达成了共识吗？一个有趣的事实是，当共识达成的那一刹那，系统中所有的参与者，包括 Acceptor 和 Proposer，没有任何人知道共识已经达成！只不过，随着时间的推移，算法的运行会把共识已经达成这一事实逐步的揭示出来。

考虑有 5 个 Acceptor，多个 Proposer 的情况。在 ProposalID=t1 的时候，提案 P1 被 A1 和 A2 接受，但是没有达到多数派，因此在这一轮处理中值并没有被确定下来。ProposalID=t2 的提案 P2 同样没有达到多数派。ProposalID=t3 的提案 P3 被多数派 A2、A3、A4 接受，从而达成共识。

首先，我们注意到当共识没有达成之前，Acceptor 是有可能改变自己接受的值的，例如 A3 先接受了 P2，后面又接受了 P3。因为 Proposer 随时有可能失联，所以 Acceptor 只能选择接受新的值。这导致当 A3 接受 P3 的时候，它不可能知道共识已经达成，P3 就是最终选定的值。同样的道理，A2 和 A4 也只知道自己局部的情况，无从判断系统整体是否已经达成共识。而在 Proposer 一端，在接收到多数派 Acceptor 的成功响应之前，它也不知道自己提交的 P3 能否被多数 Acceptor 接受，成为最终的共识。所以说共识是属于整体的，单个参与者对于共识是否达成需要有一个理解的过程。

已经达成的共识能否被推翻？

在上一节的例子中，当 ProposalID=t3 达成共识之后，有没有可能在 t4 时刻我们达成一个新的共识 P4？这样的话，t3 的共识是 P3，t4 的共识是 P4，而 t1 和 t2 时刻没有达成共识。对神来说，不同的时刻选定不同的值是完全 OK 的，No Problem，因为神是全知全能的。但是对于鲁钝的凡人而言，如果允许不同的时刻有不同的共识，他会出现认知障碍。

假如允许共识被推翻，一个只有有限认知能力的凡人，他怎么知道哪个值才是要用的值呢？很多时刻根本没有达成共识（例如 t1 和 t2），他要从 t1 到 tn 遍历所有的时刻来获知所有共识的值吗？

现在，考虑上图中的情况。假设 A3 在处理 P3 的时候直接宕机了。从外部看来，存在两种情况：

1. A3 已经接受 P3，所以达成了共识

2. A3 还没有接受 P3, 所以尚未达成共识

除了 A3 自己之外，没有任何人知道它的处理情况。但是，A3 已经挂掉了，它不能回答任何问题！所以，如果不同的时刻可能有不同的共识，那么我们有可能会陷入一个尴尬的境地，那就是历史结果完全处于一种量子不确定状态，无法简单的回答是或者否。

对于凡人而言，最理想的选择是系统具有某种单调性：它只会向着一个方向不断迈进，而且一旦到达目标状态，就永远禁锢于该状态中。这样的话，任何时候我们想从系统中提取信息，都可以直接将系统向前推进一步。如果系统已经达成共识，则继续前进一步得到的仍然是共识的值，如果没有达成共识，则我们将实际选定一个值，从而摆脱不确定的状态。例如，在上面的例子中，我们继续运行一步 Paxos 算法，无论 t3 时 A3 做出何种选择，我们一定会在 t4 得到 P3 的结果，从而在 t4 之后消除了系统中的不确定性。在郁白的文章中，这也称为最大提交原则。

注意，我们有可能因为多运行一趟 Paxos 算法，从而把系统从原本不确定的状态带到了确定状态。这就类似于量子系统，你观察一下它，它的状态就塌缩为某个本征态。如果此前它已经处于本征态，则观察行为不改变系统的状态。

如果确保共识保持不变？

共识是在主世界的主时间线上存在的知识。根据现代魔法学的研究，时间线的两个不同点上的知识是完全独立的！如果我们希望给这两个点上的知识建立关系，那必须引入某种**”联络“**机制，使得信息可以从一个时间点传递到另一个时间点。

首先我们知道所有主时间线上的事实肯定能按照发生的”时间点“排序，而共识是在主时间线的某个时间点上发生的写入。那么保持共识一致的最简单的方案就是，未写先读，写入之前先偷看一眼前面的情况。

在 t4 写入的时候如果能够偷偷看一眼 t3 的结果，直接使用 t3 的结果作为 t4 写入的值不就可以确保一致了吗？

在九级魔法的加持下，只需神念一动，即可在主时间线的任意一点完成读-处理-写这样一个复合的原子事件。主时间线上的事件可以分解对应到下级小世界中的事件。西游记中曾经记载：天上一日，人间一年。所以主世界的一点就映射为小世界中的一个区间了（小世界中如果有一个本地时钟，它会发现起始-处理-结束是一个较长的过程，而不是一个时间静止的点）。这种映射是保持了事件的原子性和相对位置关系的。例如，在上图中，A5 的 t4 和 t3 都是不可分的，它们不会交叉。如果 t3 和 t4 交叉了，说明时间静止的区间内发生了意料之外的事情，这与时间静止的假定相矛盾。t4 一定处于 t3 的后面，而且不会与 t3 相交，因此它一定可以看到 t3 的结果。

Paxos 算法在第一阶段会收集多数派 Acceptor 上已经接受的值。

1. 如果共识已经达成，则第一阶段一定会返回这个共识的值，而且它一定是 ProposalID 最大的那个值。证明：如果 t3 时刻达成了共识，则紧随其后的 t4 一定看到了 t3 的结果，按照规则，它的值一定是共识的值。所以如果 ProposalID 最大的值不是共识的值，则表示在它之前不可能已经达成共识。

2. 如果共识尚未达成，则 Proposer 可以自由选择自己心仪的值，所以他主动成全别人，选择 ProposalID 最大的那个值也是完全允许的。

也许有些人会感到奇怪，Proposer 提交别人的值，那他自己的值怎么办？请注意，Paxos 算法的目的是实现共识，并不是为了满足个人的私欲，将自己的值变成共识。其实 Proposer 发现自己的值无法提交之后，他完全可以放弃后面的工作，并不影响算法的正确性。他主动帮助别人只是加速了系统的收敛过程。如果某个 Proposer 接收到了所有 Acceptor 的响应，他经过分析发现尚未达成共识，那么他完全可以选择不支持别人，坚持提交自己的值。互相帮助是人类的美德，这一次帮助别人推波助澜，下一次说不定别人也会帮助自己不是。

六. 不确定性之上的确定性

在凡人的眼中，这个世界充斥着令人心烦意乱的不确定性，每一步行为都产生三种可能的结果：1. 成功，2. 失败 3. 不知道什么结果。曾几何时，孤立的单机系统为我们提供了一种乌托邦式的幻象，世界是二分的，好与坏，成功与失败，光明与黑暗。但是真实的世界让人清醒，在由偶然所主宰的世界中，这种内在的不确定性造就了分布式系统的本质性的困难。

为了在一个偶然的、不确定的世界中奋力求生，我们唯有精诚合作，形成超越个体的集体意识。个体可以消亡，而集体通过新陈代谢实现永生。一个有趣的问题是，多数派（Majority）是否是形成集体意识的唯一选择？显然不是。精神的传承，只需要种子的存在。

来看一个 Grid Quorum 的例子，

对于上面3*6个 Acceptor 所组成的一个 Grid，我们可以规定只要写入任意一列所构成的 Quorum 即可认为共识达成。显然，任意两列都是不相交的。为了避免做出自相矛盾的选择，我们需要横向架设一个桥梁，规定 Paxos 第一阶段读取的时候必须至少读取一行。假设某个时刻共识已经诞生，则下一个共识必然先经过一个行读取再执行一个列写入。因为任意的行和任意的列都是相交的，行读取必然会读到共识的值，因此写入的新值必然是和此前的共识保持一致的。注意到这个例子中的行 Quorum 与相交的列 Quorum 都没有达到多数派，而且它们的总元素个数为 3+6-1=8 个，也没有构成多数派。所以，读取和写入时候的 Quorum 既不需要相同，也不需要占据多数，只要能够相交，足以传递信息即可。

要超越个体，只需要把个体升华为 Quorum 中的一员。一个个体可以属于多个 Quorum。只要过去和未来所有的 Quorum 协调一致，不会做出相互冲突的选择，最终我们就可以形成统一的集体意志。

七. 时间的秘密

对于凡人而言，时间是一种神奇的先验存在。似乎我们所有的协调工作本质上都是在利用时间箭头所提供的方向指引。在我们这个位面，牛顿爵士第一个发现，时间切分了因果，时间的左边是因，右边是果，为此他写下了伟大不朽的牛二定律

F = m* a，因 = 线性系数 * 果

后来，爱因斯坦通过想象发射一个光子去探测周围的世界，不经意间揭示出一个惊天的秘密：时间线并不是唯一的！

如果时间线不唯一，我们该如何避免迷失方向？一个选择是，记住所有的时间线，这形成了所谓的向量时钟（Vector Clock）技术。而如果我们选择将所有的时间线对齐为唯一的一个，就成为了 Paxos 算法。

我们还有其他的选择吗？想象一下，如果可以彻底摆脱因果的枷锁，在时间线上自由的穿梭，无所谓过去，也无所谓未来，那是何等的拉风。因在左，果在右，为什么不能颠倒过来？本质上这是因为系统不满足交换律，当左右颠倒的时候得不到同样的结果。只有在一个高魔的世界中，无所谓左右，无所谓前后，在那里才可以施展真正的十级魔法：逆乱因果。CRDT 数据结构了解一下？

八. 结语

人神之分，在于神域。神域之中，言出法随。制定规则，是神的起点，而谦卑的接纳规则、并狡诈的利用规则则是人之本质。

凡人中的一小撮人，名为程序员，自诩程序世界的伪神，总是试图僭越这一道鸿沟。但只有真正模拟过神的行为，人才能真正认识到自身的局限性和神的伟大。为什么发送了消息能接收到回应？因为所有的服务器都存放在地球上，它们之间距离有限。为什么可以通过本地时钟决定 Lease 租期？因为所有的服务器都存放在地球上，所处的引力场相近，本地时钟具有可比性。站在人的尺度上，我们是无法想象如何才能穿越大半个银河去实现共识的。

最后，让我们再次聆听一下神的意旨：

• 神说：要有时间

• 神说：时间静止

• 神说：大千世界

• 神说：亿万分身

• 神说：薪火相传