想用好分布式框架，先学会Paxos算法吧

tips：觉得难理解多看几遍

可靠与可用、共识与一致在正式开始探讨分布式环境面临的各种技术问题和解决方案之前，我们先把目光从工业界转到学术界，学习两三种具有代表性的分布式共识算法，为后续分布式环境中操作共享数据打好理论基础。

我们先从一个最简单、最常见的场景开始：如果你有一份很重要的数据，要确保它长期存储在电脑上不会丢失，你会怎么做？

这不是什么脑筋急转弯的古怪问题，答案就是去买几块磁盘，把数据在不同磁盘上多备份几个副本。假设一块磁盘每年损坏的概率是 5%，那把文件复制到另一块磁盘上备份后，数据丢失的概率就变成了 0.25%（两块磁盘同时损坏才会导致数据丢失）。以此类推，使用三块磁盘存储数据丢失的概率就是 0.00125%，使用四块则是 0.0000625%。

换句话说，使用四块磁盘来保存同一份数据，就已经保证了这份数据在一年内有超过 99.9999% 的概率是安全可靠的。

那对应到软件系统里，保障系统可靠性的方法，与拿几个磁盘备份似乎没什么不同。

但是，在软件系统里，要保障系统的可用性，面临的困难与磁盘备份有本质的区别。

其中的原因也很好理解：磁盘之间是孤立的不需要互相通讯，备份数据是静态的，初始化后状态就不会发生改变，由人工进行的文件复制操作，很容易就能保证数据在各个备份盘中是一致的。但是，到了分布式系统里面，我们就必须考虑动态的数据如何在不可靠的网络通讯条件下，依然能在各个节点之间正确复制的问题。

现在，我们来修改下要讨论的场景：如果你有一份会随时变动的数据，要确保它能正确地存储在网络中几台不同的机器上，你会怎么做？

这时，你最容易想到的答案一定是“数据同步”：每当数据有变化，就把变化情况在各个节点间的复制看成是一种事务性的操作，只有系统里的每一台机器都反馈成功地完成磁盘写入后，数据的变化才能宣布成功。

在分布式事务下，就可以实现这种同步操作。同步的一种真实应用场景是，数据库的主从全同步复制（Fully Synchronous Replication）。比如，MySQL Cluster 进行全同步复制时，所有 Slave 节点的 Binlog 都完成写入后，Master 的事务才会进行提交。

不过，这里有一个显而易见的缺陷，尽管可以确保 Master 和 Slave 中的数据是绝对一致的，但任何一个 Slave 节点、因为任何原因未响应都会阻塞整个事务。也就是说，每增加一个 Slave 节点，整个系统的可用性风险都会增加一分。以同步为代表的数据复制方法，叫做状态转移（State Transfer）。这类方法属于比较符合人类思维的可靠性保障手段，但通常要以牺牲可用性为代价。

也就是——CAP中的CP。

但是，我们在建设分布式系统的时候，往往不能承受这样的代价。对于一些关键系统来说，在必须保障数据正确可靠的前提下，对可用性的要求也非常苛刻。比如，系统要保证数据要达到 99.999999% 可靠性，同时也要达到 99.999% 可用的程度。

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

系统高可用和高可靠之间的矛盾，是由于增加机器数量反而降低了可用性带来的。为缓解这个矛盾，在分布式系统里主流的数据复制方法，是以操作转移（Operation Transfer）为基础的。我们想要改变数据的状态，除了直接将目标状态赋予它之外，还有另一种常用的方法，就是通过某种操作，把源状态转换为目标状态。

能够使用确定的操作，促使状态间产生确定的转移结果的计算模型，在计算机科学中被称为状态机（State Machine）。

状态机有一个特性：任何初始状态一样的状态机，如果执行的命令序列一样，那么最终达到的状态也一样。在这里我们可以这么理解这个特性，要让多台机器的最终状态一致，只要确保它们的初始状态和接收到的操作指令都是完全一致的就可以。

无论这个操作指令是新增、修改、删除或者其他任何可能的程序行为，都可以理解为要将一连串的操作日志正确地广播给各个分布式节点。

广播指令与指令执行期间，允许系统内部状态存在不一致的情况，也就是不要求所有节点的每一条指令都是同时开始、同步完成的，只要求在此期间的内部状态不能被外部观察到，且当操作指令序列执行完成的时候，所有节点的最终的状态是一致的。这种模型，就是状态机复制（State Machine Replication）。

在分布式环境下，考虑到网络分区现象是不可能消除的，而且可以不必去追求系统内所有节点在任何情况下的数据状态都一致，所以采用的是“少数服从多数”的原则。也就是说，一旦系统中超过半数的节点完成了状态的转换，就可以认为数据的变化已经被正确地存储在了系统当中。这样就可以容忍少数（通常是不超过半数）的节点失联，使得增加机器数量可以用来提升系统整体的可用性。在分布式中，这种思想被叫做Quorum 机制。

根据这些讨论，我们需要设计出一种算法，能够让分布式系统内部可以暂时容忍存在不同的状态，但最终能够保证大多数节点的状态能够达成一致；同时，能够让分布式系统在外部看来，始终表现出整体一致的结果。

这个让系统各节点不受局部的网络分区、机器崩溃、执行性能或者其他因素影响，能最终表现出整体一致的过程，就是各个节点的协商共识（Consensus）。

这里需要注意的是，共识（Consensus）与一致性（Consistency）是有区别的：一致性指的是数据不同副本之间的差异，而共识是指达成一致性的方法与过程。

Lamport（就是大名鼎鼎的LaTeX中的“La”）是Paxos算法的提出者。2013 年，因为对分布式系统的杰出理论贡献，Lamport 获得了 2013 年的图灵奖。随后，才有了 Paxos 在区块链、分布式系统、云计算等多个领域大放异彩的故事。

Paxos 算法，是一种基于消息传递的协商共识算法。现在，Paxos 算法已经成了分布式系统最重要的理论基础，几乎就是“共识”这两字的代名词了。

这个极高的评价来自提出 Raft 算法的论文“In Search of an Understandable Consensus Algorithm”，更是显得分量十足。

如果没有 Paxos，那后续的 Raft、ZAB 等算法，ZooKeeper、etcd 这些分布式协调框架，Hadoop、Consul 这些在此基础上的各类分布式应用，都很可能会延后好几年面世。

为了解释清楚 Paxos 算法，Lamport 虚构了一个叫做“Paxos”的希腊城邦，这个城邦按照民主制度制定法律，却又不存在一个中心化的专职立法机构，而是靠着“兼职议会”（Part-Time Parliament）来完成立法。

这就无法保证所有城邦居民都能够及时地了解新的法律提案，也无法保证居民会及时为提案投票。Paxos 算法的目标，就是让城邦能够在每一位居民都不承诺一定会及时参与的情况下，依然可以按照少数服从多数的原则，最终达成一致意见。但是，Paxos 算法并不考虑拜占庭将军问题，也就是假设信息可能丢失也可能延迟，但不会被错误传递。

Paxos 算法将分布式系统中的节点分为提案节点、决策节点和记录节点三类。

提案节点：称为 Proposer，提出对某个值进行设置操作的节点，设置值这个行为就是提案（Proposal）。值一旦设置成功，就是不会丢失也不可变的。

需要注意的是，Paxos 是典型的基于操作转移模型（状态机）而非状态转移模型来设计的算法，所以这里的“设置值”不要类比成程序中变量的赋值操作，而应该类比成日志记录操作。因此，我在后面介绍 Raft 算法时，就索性直接把“提案”叫做“日志”了。(redis中aof是基于操作转移，rdb是基于状态转移)

决策节点：称为 Acceptor，是应答提案的节点，决定该提案是否可被投票、是否可被接受。提案一旦得到过半数决策节点的接受，就意味着这个提案被批准（Accept）。提案被批准，就意味着该值不能再被更改，也不会丢失，且最终所有节点都会接受它。(记录一下。和zk的leader，flower，observer相似)

记录节点：被称为 Learner，不参与提案，也不参与决策，只是单纯地从提案、决策节点中学习已经达成共识的提案。比如，少数派节点从网络分区中恢复时，将会进入这种状态。

在使用 Paxos 算法的分布式系统里，所有的节点都是平等的，它们都可以承担以上某一种或者多种角色。不过，为了便于确保有明确的多数派，决策节点的数量应该被设定为奇数个，且在系统初始化时，网络中每个节点都知道整个网络所有决策节点的数量、地址等信息。另外，在分布式环境下，如果说各个节点“就某个值（提案）达成一致”，代表的意思就是“不存在某个时刻有一个值为 A，另一个时刻这个值又为 B 的情景”。

而如果要解决这个问题的复杂度，主要会受到下面两个因素的共同影响：

第一点“系统内部各个节点间的通讯是不可靠的”，是网络通讯中客观存在的现象，也是所有共识算法都要重点解决的问题。所以我们重点看下第二点“系统外部各个用户访问是可并发的”，即“分布式环境下并发操作的共享数据”问题。

为了方便理解，我们可以先不考虑是不是在分布式的环境下，只考虑并发操作。假设有一个变量 i 当前在系统中存储的数值为 2，同时有外部请求 A、B 分别对系统发送操作指令，“把 i 的值加 1”和“把 i 的值乘 3”。如果不加任何并发控制的话，将可能得到“(2+1)×3=9”和“2×3+1=7”这两种结果。因此，对同一个变量的并发修改，必须先加锁后操作，不能让 A、B 的请求被交替处理。这，可以说是程序设计的基本常识了

但是，在分布式的环境下，还要同时考虑到分布式系统内，可能在任何时刻出现的通讯故障。如果一个节点在取得锁之后、在释放锁之前发生崩溃失联，就会导致整个操作被无限期的等待所阻塞。因此，算法中的加锁，就不完全等同于并发控制中以互斥量来实现的加锁，还必须提供一个其他节点能抢占锁的机制，以避免因通讯问题而出现死锁的问题。

我们继续看 Paxos 算法是怎么解决并发操作带来的竞争的。

Paxos 算法包括“准备（Prepare）”和“批准（Accept）”两个阶段。

第一阶段“准备”（Prepare）就相当于抢占锁的过程。如果某个提案节点准备发起提案，必须先向所有的决策节点广播一个许可申请（称为 Prepare 请求）。提案节点的 Prepare 请求中会附带一个全局唯一的数字 n 作为提案 ID，决策节点收到后，会给提案节点两个承诺和一个应答。

其中，两个承诺是指：承诺不会再接受提案 ID 小于或等于 n 的 Prepare 请求；承诺不会再接受提案 ID 小于 n 的 Accept 请求。

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

提案节点收到了多数派决策节点的应答（称为 Promise 应答）后，可以开始第二阶段“批准”（Accept）过程。这时有两种可能的结果：

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

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

1

说人话就是

小帅是提案节点，小美们是决策节点，小黑是记录节点，(有一个前提，每个承诺都不违背以前的承诺，在这个前提下只接受提案ID最大的消息)

小帅发广播说我要把a的值改成1，id是2，然后小帅日志记录a=1（Prepare），小美们接收到了这个广播，小美们看了下自己的日志，a的值没有记录过变化，然后返回null，小帅看到多数决策节点都返回null（称为 Promise 应答），意味着a的值没被改过很开心，没有发生冲突，然后发了第二个广播我要把a的值改成1，id是2，现在根据日志操作真实数据啦（称为 Accept 请求），然后小美们开始改数据，多数小美改完发了应答（称为 Accepted 应答），共识决议形成，小黑们按照小帅发的广播开始改值。

下面是发生冲突的情况

小帅发广播说我要把a的值改成1，id是2，然后小帅日志记录a=1（Prepare），小美们接收到了这个广播，小美们看了下自己的日志，有的小美a的值有记录过a=5，id是3，返回小帅看到至少一个小美记录了其他值（称为 Promise 应答），很遗憾发生冲突了，然后看小美应答的a=5，id是3，选择id大的哪一个提案，然后发了第二个广播我要把a的值改成5，id是3，现在根据日志操作真实数据啦（称为 Accept 请求），然后小美们开始改数据，多数小美改完发了应答（称为 Accepted 应答），共识决议形成，小黑们按照小帅发的广播开始改值。

有一个前提，每个承诺都不违背以前的承诺，在这个前提下只接受提案ID最大的消息

到这里，整个 Paxos 算法的工作流程就结束了。

虽然 Paxos 是以复杂著称的算法，但我们上面学习的是基于 Basic Paxos、以正常流程（未出现网络分区等异常）、以通俗的方式讲解的 Paxos 算法，并没有涉及到严谨的逻辑和数学原理，也没有讨论 Paxos 的推导证明过程。所以，这对于大多数不从事算法研究的技术人员来说，理解起来应该也不会太过困难。但是Basic Paxos 是一种很学术化、对工业化并不友好的算法，现在几乎只用来做理论研究。实际的应用都是基于 Multi Paxos 和 Fast Paxos 算法的，在下一讲我们就会了解 Multi Paxos 以及和它理论等价的几个算法，比如 Raft、ZAB 等算法。

今天这节课，我们从分布式系统的高可靠与高可用的矛盾开始，首先学习了分布式共识算法的含义，以及为什么需要这种算法。我们也明确了“共识”这个词，在这个上下文中所指含义，就是“各个分布式节点针对于某个取值达成一致”。其次，我们了解了 Basic Paxos 算法的主要工作流程。尽管我们很少有机会去研究或者实现分布式共识算法，但理解它的基本原理，是我们日后理解和使用 etcd、ZooKeeper 等分布式框架的重要基础。