分布式一致性与共识的前世今生

计算机早起到现在在分布式领域一直聚焦在如何保证分布式系统的集群中所有节点存储的数据是一致的问题，也被称为一致性问题。

首先我们要明确两个概念异步网络通信和 crash-recovery 模型。异步网络通信，指的是消息可能乱序、延迟、丢失、重传，通常利用超时机制来感知丢包并重试，而且有限次重试之后消息一定可以成功送达，且消息传输信道是可靠的，不会被恶意篡改（网络不会被攻击，否则需要采用加密传输）。而 crash-recovery 故障模型指的是节点可能宕机，之后可以重启恢复（也可能无法恢复），这种故障模型比拜占庭故障模型要容易处理。

其次是我们要清楚一致性与共识并不是同个东西。一致性是指分布式系统中的多个服务节点，给定一系列的操作，在约定协议的保障下，使它们对外界呈现的状态是一致的。换句话说，也就是保证集群中所有服务节点中的数据完全相同并且能够对某个提案（Proposal）达成一致。共识算法解决的是对某个提案（proposal）大家达成一致意见的过程。提案的含义在分布式系统中十分宽泛，如多个事件发生的顺序、某个键对应的值、谁是领导……等等。比如 Paxos 是属于共识算法。

我个人认为我们是在用共识算法解决一致性问题。

在分布式计算中，不同的计算机通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候，系统中的成员计算机可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，使得网络中不同的成员关于全体协作的策略得出不同结论，从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

1975 年，纽约州立大学的 Akkoyunlu E. A.、Ekanadham K.、Huber R. V. 在论文《Some constraints and tradeoffs in the design of network communications》中首次提出计算机领域的两军问题及无解性证明，两军问题表明在不可靠的通信链路上想要达到一致共识是几乎不可能的，TCP 协议的三次握手就是在尝试通过简单的方式解决这个问题。

两支军队由不同将军领导，准备进攻一座坚固的城市。军队在城市附近的两个山谷扎营。由于有另一个山谷将两山隔开，两名将军只能透过派信使穿越山谷通讯，但这山谷由城市护卫占领，有可能俘虏途径山谷传递讯息的任何信使。

虽然两军已约定要同时进攻，但尚未约定进攻时间。要顺利攻击，两军必须同时进攻。如果同一时间仅一支军队进攻就会战败，因此两名将军须约定攻击时间，并确保对方知道自己同意了进攻计划。但由于传递确认讯息的信使与传递原始讯息的信使一样，都可能被俘虏而丢失讯息，即使双方不断确认已收到对方的上一条讯息，也无法确保已与对方达成共识。

将军甲首先派信使向将军乙传递讯息“在8月4日9时进攻”。然而，派遣信使后，将军甲不知道信使是否成功穿过敌方领土。由于担心自己成为唯一的进攻军队，将军甲可能会犹豫要否按计划进攻。

为了消除不确定性，将军乙可以向将军甲发送确认讯息“我收到了您的讯息，并会在8月4日9时进攻”，但传递确认讯息的使者同样可能会被敌方俘虏。由于担心将军甲没有收到确认讯息而退缩，将军乙会犹豫要否按计划进攻。

再次发送确认讯息看来可以解决问题——将军甲再让新信使发送确认讯息：“我已收到您确认在 8 月 4 日 9 时进攻”。但是，将军甲的新信使也可能被俘虏。显然，无论确认几次都无法满足该问题的条件二，即两方都必须确保对方已同意计划，两名将军总会怀疑他们最后派遣的使者有否顺利穿过敌方领土。

是由莱斯利·兰波特在 1980 年的其同名论文《The Byzantine Generals Problem》中提出的分布式对等网络通信容错问题，俗称拜占庭将军问题。一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

系统的问题在于，可能将军中出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。

由于将军之间需要通过信使通讯，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。

假使那些忠诚（或是没有出错）的将军仍然能通过多数决定来决定他们的战略，便称达到了拜占庭容错。在此，票都会有一个预设值，若信息没有被收到，则使用此预设值来投票。

Fischer、Lynch 和 Patterson 三位科学家于 1985 年发表《Impossibility of Distributed Consensus with One Faulty Process》提出了FLP 不可能原理，在网络可靠、但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法。

FLP 不可能原理在论文中以图论的形式进行了严格证明。要理解其基本原理并不复杂，一个不严谨的例子如下。三个人在不同房间进行投票（投票结果是 0 或者 1），彼此可以通过电话进行沟通，但经常有人会时不时睡着。比如某个时候，A 投票 0，B 投票 1，C 收到了两人的投票，然后 C 睡着了。此时，A 和 B 将永远无法在有限时间内获知最终的结果，因为他们无法判断究竟是 C 没有应答还是应答的时间过长。如果可以重新投票，则类似情形可以在每次取得结果前发生，这将导致共识过程永远无法完成。

FLP 不可能定理指出异步系统的共识问题不存在有限时间的理论解，因此必须调整问题模型来规避 FLP 不可能定理，比如牺牲确定性（如我们常说的最终一致）、增加时间等等。

1988 年 Brian M. Oki 和 Barbara H. Liskov 提出了《ViewStamped replication revisited》，论文中明确了它是一个复制协议（replication protocol）。VR 工作在异步网络中，能够处理节点 crash。VR 提供 state machine replication，适用于实现 replicated service，例如 lock manager、file system。

因为 Paxos 在后世非常重要，这里会用更大篇幅来介绍。

1990 年，莱斯利·兰波特在提出拜占庭问题十年后发表了 Paxos 算法，他在这个页面中描述了这些年对这个算法的构思。

为描述 Paxos 算法，Lamport 虚拟了一个叫做 Paxos 的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos 岛上的议员是不会反对其他议员提出的决议的。

对应于分布式系统，议员对应于各个节点，制定的法律对应于系统的状态。各个节点需要进入一个一致的状态，例如在独立Cache的对称多处理器系统中，各个处理器读内存的某个字节时，必须读到同样的一个值，否则系统就违背了一致性的要求。一致性要求对应于法律条文只能有一个版本。议员和服务员的不确定性对应于节点和消息传递信道的不可靠性。

在分布式环境下我们先做两个假设：

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

Paxos 算法将分布式系统中的节点分为三类：

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

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

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

两个承诺是指：

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

一个应答是指：

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

当提案节点收到了多数派决策节点的应答（称为 Promise 应答）后，可以开始第二阶段“批准”（Accept）过程。

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

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

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

Paxos 算法可以说是为未来分布式一致性发展做出了巨大贡献，后来的大部分算法包括 Raft 也是属于这个家族的。需要注意的是 VR 和 Paxos 都是假设系统中不存在拜占庭故障节点，因此算得上是非拜占庭容错算法，同类有两阶段提交、一阶段提交等待。

Miguel Castro 和Barbara Liskov 在 1999 年提出《Practical Byzantine Fault Tolerance》也就是 PBFT 算法，也就是所谓的拜占庭容错算法。这个算法解决了原始拜占庭容错算法效率不高的问题，算法的时间复杂度是 \(O(n^2)\)，使得在实际系统应用中可以解决拜占庭容错问题。

PBFT 共识算法可以在少数节点作恶(如伪造消息)场景中达成共识，它采用签名、签名验证、哈希等密码学算法确保消息传递过程中的防篡改性、防伪造性、不可抵赖性，并优化了前人工作，将拜占庭容错算法复杂度从指数级降低到多项式级别，在一个由 \((3*f+1)\) 个节点构成的系统中，只要有不少于 \((2*f+1)\) 个非恶意节点正常工作，该系统就能达成一致性，如：7 个节点的系统中允许 2 个节点出现拜占庭错误。

PBFT 可以算是 Paxos 的变种，通过改进 Paxos 来处理拜占庭错误（前面有提到 Paxos 并不是拜占庭容错，而 PBFT 是，所以区块链广泛用到了）。

2000 年 7 月，加州大学伯克利分校的 Eric Brewer 教授在提出 CAP 猜想，后来被证明称为定理。CAP 认为一个分布式系统不可能满足以下三点：

一致性（Consistency）（等同于所有节点访问同一份最新的数据副本）
可用性（Availability）（每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据）
分区容错性（Partition tolerance）（以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择。）

很多人在讨论 CAP 时常说的 “三选二” 概念可能会误导人，因为系统设计者只有在发生网络分区的时候才需要在一致性和可用性之间做牺牲，但在很多系统里分区是非常少见的。CAP 更多的是一种保证。其次是我认为 CAP 最重要的意义是提出了【分区】的概念。

2013 年斯坦福的 Diego Ongaro 和 John Ousterhout，发表了《In search of an understandable consensus algorithm》提出了 Raft 算法，这是一种比 Paxos 更简单和易于理解的算法。

Raft将共识问题分解三个子问题：

Leader election 领导选举：有且仅有一个 leader 节点，如果 leader 宕机，通过选举机制选出新的 leader；
Log replication 日志复制：leader 从客户端接收数据更新/删除请求，然后日志复制到 follower 节点，从而保证集群数据的一致性；
Safety 安全性：通过安全性原则来处理一些特殊 case，保证 Raft 算法的完备性。

所以，Raft算法核心流程可以归纳为：