Skip to content

Paxos

如果你有一份很重要的数据，要确保它长期存储在电脑上不会丢失，你会怎么做？

这不是什么脑筋急转弯的古怪问题，答案就是去买几块硬盘，在不同硬盘上多备份几个副本。
假设一块硬盘每年损坏的概率是 5%，把文件复制到另一块备份盘上，两块硬盘同时损坏而丢失数据的概率只有 0.25%,如果使用三块硬盘存储则丢失数据的概率是 0.00125%，四块是 0.0000625%，换言之，四块硬盘就可以保证数据在一年内有超过 99.9999% 的概率是安全可靠的

在软件系统里，要保障系统的可靠性，采用的办法与上面用几个备份硬盘来保障的方法并没有什么区别。
单个节点的系统宕机导致数据无法访问的原因可能有很多，譬如程序出错、硬件损坏、网络分区、电源故障，等等，
一年中出现系统宕机的概率也许还要高于 5%，这决定了软件系统也必须有多台机器，并且它们拥有一致的数据副本，才有可能对外提供可靠的服务

在软件系统里，要保障系统的可用性，面临的困难与硬盘备份面临的困难又有着本质的区别。
硬盘之间是孤立的，不需要互相通信，备份数据是静态的，初始化后状态就不会发生改变，由人工进行的文件复制操作，很容易就保障了数据在各个备份盘中的一致性。
然而在分布式系统中，我们必须考虑动态的数据如何在不可靠的网络通信条件下，依然能在各个节点之间正确复制的问题。

将我们要讨论的场景做如下修改:

如果你有一份会随时变动的数据，要确保它正确地存储于网络中的几台不同机器之上，你会怎么做？

相信最容易想到的答案一定是“数据同步”: 每当数据发生变化，把变化情况在各个节点间的复制视作一种事务性的操作，只有系统里每一台机器都反馈成功、完成磁盘写入后，数据的变化才宣告成功。
一种真实的数据同步应用场景是数据库的主从全同步复制(Full Synchronous Replication)，譬如 MySQL 集群，它在进行全同步复制时，会等待所有 Slave 节点的 Binlog 都完成写入后，才会提交 Master 节点的事务(这个场景中 Binlog 本身就是要同步的状态数据，不应将它看作指令日志的集合)
然而这里有一个明显的缺陷，尽管困难确保 Master 节点和 Slave 节点中的数据时绝对一致的，但任何一个 Slave 节点因为任何原因未响应均会阻塞整个事务，每增加一个 Slave 节点，就会造成整个系统可用性风险增加一分

以同步为代表的数据复制方法，被称为状态转移(State Transfer)，是较符合人类思维的可靠性保障手段，但通常要以牺牲可用性为代价。
我们在建设分布式系统的时候，往往不能承受这样的代价，一些关键系统，也对可用性有非常高的要求，譬如系统要保证数据达到 99.999999% 可靠，同时系统自身也要达到 99.999% 可用的程序。

这就引出了我们的第三个问题:

如果你有一份会随时变动的数据，要确保它正确地存储于网络中的几台不同机器之上，并且要尽可能保证数据是随时可用的，你会怎么做？

可靠性与可用性的矛盾造成了增加机器数量反而带来可用性的降低。
为缓解这个矛盾，在分布式系统里主流的数据复制方法是以操作转移(Operation Transfer) 为基础的。
我们想要改变数据的状态，除了直接将目标状态赋予它之外，还有另一种常用的方法是通过某种操作，令源状态转换为目标状态。
能够使用确定的操作促使状态间产生确定的转移结果的计算模型，在计算机科学中被称为状态机 (State Machine)

状态机的特性

状态机有一个特性: 任何初始状态一样的状态机，如果执行的命令序列一样，则最终达到的状态也一样。
如果将此特性应用在多参与者的协商共识上，可以理解为系统中存在多个具有完全相同的状态机(参与者)，这些状态机能最终保持一致的关键就是起始状态完全一致和执行命令序列完全一致

根据状态机的特性，要让多台机器的最终状态一致，只要确保它们的初始状态是一致的，并且接收到的操作指令序列也是一致的即可，无论这个操作指令是新增、修改、删除抑或是其他任何可能的程序行为，都可以理解为要将一连串的操作日志正确地广播给各个分布式节点。
在广播指令与指令执行期间，允许系统内容状态存在不一致的情况，即并不要求所有节点的每一条指令都是同时开始、同步完成的，只要求在此期间的内部状态不能被外部观察到，且当操作指令序列执行完毕时，所有节点的最终状态是一致的，则这种模型就被称为状态机复制(State Machine Replication)

考虑到分布式环境下网络分区现象是不可能消除的，甚至允许不再追求系统内所有节点在任何情况下的数据状态都一致，而是采用“少数服从多数”的原则，一旦系统中过半数的节点完成了状态的转换，就认为数据的变化已经被正确地存储在了系统中，这样就可以容忍少数(通常是不超过半数)的节点失联，减弱增加机器数据对系统整体可用性的影响，这种思想在分布式中被称为“Quorum 机制(大多数投票机制)”

根据上述讨论，我们需要设计出一种算法，能够让分布式系统内部暂时容忍不同的状态，但最终保证大多数节点的状态达成一致；
同时，能够让分布式系统在外部看来始终表现出整体一致的结果。
这个让系统各节点不受局部的网络分区、机器崩溃、执行性能或者其他因素影响，都能最终表现出整体一致的过程，就被称为各个节点的协商共识(Consensus)

世界上只有一种共识协议，就是 Paxos，其他所有共识算法都是 Paxos 的退化版本
-- Mike Burrows, Google Bhubby 作者

Paxos 是由 Leslie Lamport(就是大名鼎鼎的 LaTeX 中的"La")提出的一种基于消息传递的协商共识算法，是当今分布式系统最重要的理论基础，几乎就是"共识"二字的代名词。
这个极高的评价出自于提出 Raft 算法的论文，更显分量十足。
虽然有些夸张，但是如果没有 Paxos，那后续的 Raft、ZAB 等算法，ZooKeeper、etcd 等分布式协调框架、Hadoop、Consul 等在此基础上的各类分布式应用都很可能会延后好几年面世

Paxos 的诞生

为了解释清楚 Paxoos 算法，Lamport 虚构了一个名为 "Paxos" 的希腊城邦，这个城邦按照民主制度制定法律，却没有一个中心化的专职立法机构，
而是靠着“兼职议会”(Part-Time Parliament)来完成立法，无法保证所有城邦居民都能够及时了解新的法律提案，也无法保证居民会及时为提案投票。
Paxos 算法的目标就是让城邦能够在每一位居民都不承诺一定会及时参与的情况下，依然可以按照少数服从多数的原则，最终达成一致意见。
但是 Paxos 算法并不考虑拜占庭将军问题，即假设信息可能丢失也可能延迟，但不会被错误传递。

Lamport 在 1990 年首次发表了 Paxos 算法，选的论文题目就是 "The Part-Time Parliament".
由于算法本身极为复杂，用希腊城邦作为比喻反而使得更晦涩，论文的三个审稿人一致要求他把希腊城邦的故事删掉。
这令 Lamport 感觉颇为不爽，干脆就撤稿不发了，所以 Paxos 刚刚被提出的时候并没有引起什么反响。
八年之后(1998 年)，Lamport 将此文章重新整理后投到 ACM Transactions on Computer Systems。
这次论文发表成功，Lamport 的名气也确实吸引了一些人去研究，但并没有多少人能弄个你都给你他在说什么。
时间又过去了三年(2001 年)，Lamport 认为前两次的论文没有引起反响，是因为同行们无法理解他以 "希腊城邦" 来讲故事的幽默感，所以这一次他以 "Paxos Made Simple" 为题，在 SIGACT News 杂志上发表文章，放弃了 "希腊城邦" 的比喻，尽可能用(他认为)简单直接、(他认为)可读性较强的方式去介绍 Paxos 算法。
情况虽然比前两次要好上一些，但以 Paxos 本应获得的重视程度来说，这次依然只能算是应着寥寥。
这一段听起来如同网络段子一般的经历被 Lamport 以自嘲的形式放到了他的个人网站上。

虽然 Lamport 本人连发三篇文章都没能让大多数同行理解 Paxos，但 2006 年，在 Google 的 Chubby、Megastore 以及 Spanner 等分布式系统都使用 Paxos 解决了分布式共识的问题，并将其整理成正式的论文发表之后，得益于 Google 的行业影响力，辅以 Chubby 作者 Mike Burrows 那略显夸张但足够吸引眼球的推波助澜，Paxos 算法一夜间成为计算机科学分布式这条分支中最炙手可热的概念，开始被学术界众人争相研究。
Lamport 本人因其对分布式系统的杰出理论贡献获得了 2013 年的图灵奖，随后才有了 Paxos 在区块链、分布式系统、云计算等多个领域大放异彩的故事

算法流程

下面，我们来正式学习 Paxos 算法(这里 Paxos 均特指最早的 Basic Paxos 算法)。
Paxos 算法将分布式系统中的节点分为三类。

  • 提案节点: 称为 Proposer，提出对某个值进行设置操作的节点，设置值这个行为就被称为提案(Proposal)，值一旦设置成功，就是不会丢失也不可变的。
    注意，Paxos 是典型的基于操作转移模型而非状态转移模型来设计的算法，不要把这里的“设置值”类比成程序中变量赋值操作，而应该类比成日志记录操作，在后面介绍的 Raft 算法中就直接把 "提案" 叫做 "日志" 了
  • 决策节点: 称为 Acceptor，是应答提案的节点，决定该提案是否可被投票、是否可被接受。提案一旦得到过半数决策节点的接受，即称该提案被批准(Accept)。
    提案被批准即意味着该值不能被更改，也不会丢失，且最终所有节点都会接受它
  • 记录节点: 称为 Learner，不参与提案，也不参与决策，只是单纯地从提案、决策节点中学习已经达成共识的提案，譬如少数派节点从网络分区中恢复时，将会进入这种状态

在使用 Paxos 算法的分布式系统里，所有的节点都是平等的，它们都可以承担以上某一种或者多种的角色，不过为了便于确保有明确的多数派，决策节点的数量应该被设定为奇数个，
且在系统初始化时，网络中每个节点都应该知道整个网络所有决策节点的数量、地址等信息。

在分布式环境下，如果我们说各个节点 "就某个值(提案)达成一致"，指的是 "不存在某个时刻有一个值 A，另一个时刻又有 B 的情景"。
解决这个问题的复杂度主要来源于以下两个方面因素的共同影响。

  • 系统内部各个节点通信是不可靠的，不论是对于系统中企图设置数据的提案节点亦或是决定是否批准设置操作的决策节点，其发出、收到的信息可能延迟送达、可能丢失，但不去考虑消息有传递错误的情况。
  • 系统外部各个用户访问是可并发的，如果系统只会有一个用户，或者每次只对系统进行串行访问，那单纯地应用 Quorum 机制，少数节点服从多数节点，就足以保证值被正确地读写。

第一点是网络通信中客观存在的现象，也是所有共识算法都要重点解决的问题。

对于第二点，详细解释如下。
现在我们讨论的是 "分布式环境下并发操作的共享数据" 的问题，即使先不考虑是否在分布式的环境下，只考虑并发操作，
假设有一个变量 i 当前在系统中存储的数值为 2，同时有外部请求 A、B 分别对系统发送操作指令，"把 i 的值加 1" 和 "把 i 的值乘 3"，如果不加任何并发控制，
将可能达到 (2 + 1) * 3 = 9 与 2 * 3 + 1 = 7 这两种可能的结果。
因此，对同一个变量的并发修改必须先加锁后操作，不能让 A、B 的请求被交替处理，这也可以说是程序设计的基本常识。
而在分布式的环境下，由于要同时考虑到分布式系统内可能在任何时刻出现的通信故障，如果一个节点在获得锁之后、在释放锁之前发生崩溃失联，这将导致整个操作被无限期的等待所阻塞，
因此算法中的加锁就不完全等同于并发控制中以互斥量来实现的加锁，还必须提供一个其他节点能抢占锁的机制，以避免因通信问题而出现思索

为了解决这个问题，分布式环境中的锁必须是可抢占的。
Paxos 算法包括两个阶段，第一阶段 "准备"(Prepare)就相当于上面抢占锁的过程。
如果某个提案节点准备发起提案，必须先向所有的决策节点广播一个许可申请(称为 Prepare 请求)。
提案节点的 Prepare 请求中会附带一个全局唯一且单调递增的数字 n 作为提案 ID，决策节点收到后，将会给予提案节点两个承诺与一个应答

两个承诺是指:

  • 承诺不会再接受提案 ID 小于或等于 n 的 Prepare 请求
  • 承诺不会再接受提案 ID 小于 n 的 Accept 请求

一个应答是指:

在不违背以前的承诺的前提下，回复已经批准过的提案中 ID 最大的那个提案所设定的值和提案 ID，如果该值从来没有被任何提案设定过，则返回空值。
如果违反此前作出的承诺，即收到的提案 ID 并不是决策节点收到的最大的 ID，那允许直接对此 Prepare 请求不予理会

当提案节点收到了多数派决策节点的应答(称为 Promise 应答)后，就可以开始第二阶段的 "批准"(Accept)过程，这时有如下两种可能的结果:

  • 如果提案节点发现所有响应的决策节点此前都没有批准过该值(即为空)，那说明它是第一个设置值的节点，可以随意地决定要设定的值，将自己选定的值与提案 ID 组成一个二元组 "(id,value)"，再次广播给全部决策节点(称为 Accept 请求)；
  • 如果提案节点发现响应的决策节点中已经有至少一个节点的应答中包含值了，那它就不能够随意取值，而是必须无条件地从应答中找出提案 ID 最大的那个值并接收，组成一个二元组 "(id,maxAcceptValue)"，再次广播给全部决策节点(称为 Accept 请求)

当每一个决策节点收到 Accept 请求时，都会在不违背以前的承诺的前提下，接收并持久化当前提案 ID 和提案附带的值。
如果违反此前做出的承诺，即收到的提案 ID 并不是决策节点收到过的最大的 ID，那允许直接对此 Accept 请求不予理会

当提案节点收到了多数派决策节点的应答(称为 Accepted 应答)后，协商结束，共识决议形成，然后将形成的决议发送给所有记录节点进行学习。
整个过程的时序图如下所示:

工作实例

假设一个分布式系统有五个节点，分别命名为 S1、S2、S3、S4、S5，五个节点都同时扮演着提案节点和决策节点的角色。
这个例子中只讨论正常通信的场景，不涉及网络分区。
此时，有两个并发的请求希望将同一个值分别设定为 X(由 S1 作为提案节点提出) 和 Y (由 S5 作为提案节点提出)，
以 P 代表准备阶段，以 A 代表批准阶段，这时可能发生以下几种情况

  • 情况一: 譬如，S1 选定的提案 ID 是 3.1(全局唯一 ID 加上节点编号)，先取得了多数派决策节点的 Promise 和 Accepted 应答，
    此时 S5 选定提案 ID 4.5，发起 Prepare 请求，收到的多数应答中至少会包含 1 个此前应答过 S1 的决策节点，
    假设是 S3，那么 S3 提供 Promise 中必将包含 S1 已设定好的值 X，S5 就必须无条件地用 X 代替 Y 作为自己提案的值，
    由此整个系统对 "取值为 X" 这个事实达成一致
    如下图所示

  • 情况二: 事实上，对于情况一，X 被选定为最终值是必然结果，但从上图中可以看出，X 被选定为最终值并不是必须得到多数派的共同批准，而是只取决于 S5 提案时 Promise 应答中是否已经包含了批准过 X 的决策节点，譬如下图所示，S5 发起提案的 Prepare 请求时，X 并未获得多数派批准，但由于 S3 已经批准，所以最终共识的结果仍然是 X

  • 情况三: 另外一种可能的结果是 S5 提案时 Promise 应答中并未包含批准过 X 的决策节点，譬如应答 S5 提案时，节点 S1 已经批准了 X，节点 S2、S3 未批准但返回了 Promise 应答，此时 S5 以更大的提案 ID 获得了 S3、S4、S5 的 Promise 应答，由于这三个节点均为批准过任何值，所以 S3 将不再接收来自 S1 的 Accept 请求，因为它的提案 ID 已经不是最大的了，这三个节点将批准 Y 的取值，整个系统最终会对 "取值为 Y" 达成一致

  • 情况四: 从情况三可以推导出另一种极端的情况，如果两个提案节点交替使用更大的提案 ID，使得准备阶段成功、批准阶段失败，那么这个过程理论上可以无限持续下去，形成活锁(Live Lock)，如下图所示。在算法实现中会引入随机超时时间来避免活锁的产生。

虽然 Paxos 是以复杂著称的算法，但以上介绍都是基于 Basic Paxos、以正常流程(未出现网络分区等异常)、通俗方式讲解的 Paxos 算法，并未涉及严谨的逻辑和数学原理，也未讨论 Paxos 的推导证明过程，理解起来应该不算太困难。

Basic Paxos 的价值在于开拓了分布式共识算法的发展思路，但由于它有如下缺陷，一般不会直接用于实践:
Basic Paxos 只能对单个值形成决议，并且决议的形成至少需要两次网络请求和应答(准备和批准阶段各一次)，
高并发情况下将产生较大的网络开销，极端情况下甚至可能形成活锁。
总之，Basic Paxos 是一种很学术化但对工业化并不友好的算法，现在几乎只用来做理论研究，实际的应用都是基于 Multi Paxos 和 Fase Paxos 算法
比如 Multi Paxos 以及一些与它的理论等价的算法(如 Raft、ZAB 等算法)