分布式架构的根基：深入浅出一致性算法

分布式算法的介绍文章可谓汗牛充栋，但或是过于学术证明或是过于简单，笔者将尝试挑战用一篇文章，让近乎 0 基础的同学都可以理解一致性算法的原理。

分布式服务的困局

我们试想一个常见的电商场景：超时订单自动关闭，在下单后 X 小时内未支付的话自动关闭订单并释放库存。这时我们需要有一个定时器定时触发相关的业务操作，从高可用的角度看这个定时器需要部署多个实例，但对同一订单仅只允许触发一次。要实现这个需求有多种方案，最常见的就是集群领导者选举，可以以实例或订单组为维度选出领导者并由其负责执行特定订单的触发。领导者选举有着广泛的应用场景，我们可以尝试将之抽象成独立的服务。

如上图，实现非常简单：

• 创建一个领导者选举服务，使用 CAS 原子化地设置变量 leader 其值等于对应的实例 Id， leader 的值在一定的存活周期后自动销毁以避免服务实例不可达导致没有可用的领导者

• 多个订单服务向领导者选举服务定期提交请求，希望将自己设置成领导者

• 领导者选举服务中 leader 的值如果存在则直接返回，反之根据先到先得原则设置 leader 的值为对应的实例 Id 并返回

但这个方案的问题也很明显：“领导者选举服务”单点了，一个节点挂了会导致服务不可用。那么能用多实例吗？

如上图，这是两种多实例扩展的方案。

方案一下不同的订单实例会随机路由到不同的领导者选举服务实例，再由领导者选举服务各实例自身实现数据同步。那么怎么同步？当然可以使用数据库、Redis 等中间件实现，但这导致了该服务并不纯粹，我们希望这个服务不依赖于三方服务或中间件。

方案二下要求订单服务向所有领导者选举服务实例发送请求，只要有一个领导者选举服务实例存活服务整体就还是可用的，但这一方案的问题在于请求发送与接收存在网络时延，导致不同领导者选举服务实例收到的顺序可能是不一样的，进而无法形成统一的结果。而这正是我们所面临的最棘手的一致性问题。

一致性算法

分布式架构涉及很多方面的知识，但如果要刨根问底，探寻根基的话，那么一定是一致性（Consistency）算法无疑了。一致性算法是分布式架构的基础，为节点伸缩提供了核心保障。

如何在多个实例中选择领导者，如何实现数据多副本存储，如何设计分布式锁，如何确定全局 ID……这一切的基石都在于一致性保障。

一致性算法很晦涩难懂，一代 IT 人试图用各种方式“深入浅出”地介绍一致性问题的算法实现，但真正能被大众接受的少之又少。接下来不先不介绍一致性的算法派系，也不去做严格的算法推导，我们先从问题出发，逐步深入。

我们回顾上文遇到的问题：网络的时延导致各实例接收到请求的顺序可能各不相同，那么我们是否可以从时序保证上入手呢？比如将所有请求先发到 MQ，再由 MQ 分发请求，这的确可以解决，但是要知道的是 MQ 本身也需要一致性支持，这是就先有鸡还是先有蛋的问题了，所以去要求严格的消息时序以解决一致性问题是不可能的。

我们大致上总结一下分布式数据一致性要解决的问题：

在多实例中确定一个变量的值，一旦确定后只能获取不能修改。

比如上文的领导者选举就是为确定 leader 变量的值，所谓“确定”即要求领导者选举服务同一时间周期内（比如一个选举周期）对外输出的领导者是唯一的，即要求领导者选举服务的不同实例间对 leader 的取值达成共识（同一时间周期内不能订单服务 inst1 拿到的是 leader = inst1 ，订单服务 inst2 拿到的是 leader = inst2 ），并且这同一时间周期内确定的值不能被更改（同一时间周期内在确定 leader = inst1 的前提下订单服务 inst3 发起选举不可以更改 leader 的取值）。

我们将确定变量值的过程看做“投票”，为规范后续的用词，我们先做以下简单的定义：

• Proposer 提案人，发起提案的请求方，比如上文的各订单服务实例

• Acceptor 投票人，负责对提案发起投票，比如上文的各领导者选举服务实例

那么我们思考下这投票的过程中带来的实现难点：

难点一：存在多个 Proposer 提案人并发请求导致接收到投票的时序无法保证

要解决这个难点最直接的做法是加锁，如下图；

我们将原本一步完成的操作分成两个步骤：

• 准备阶段：Proposer 向 Accepters 发起加写锁的请求 Accepter 收到请求返回成功或失败（已被加过锁）

• 投票阶段：Proposer 在收到所有 Accepter 都加锁成功时发起投票各 Accepter 同意投票结果，形成确定性取值各 Accepter 释放锁

我们暂不考虑算法的效率问题，这样的确可解决时序问题，但这要求所有 Accepter 都能响应请求显然是不合理的。

难点二：部分 Accepter 故障时仍然可用

要解决这个问题我们只要修改加锁成功的条件为“半数以上”，如下图：

这样服务可做到 2F+1 的容错能力，即在 2F+1 个 Accepter 实例的服务中最多允许 F 个 Accepter 实例同时出现故障。

既然 Accepter 允许故障，那么 Proposer 也应如此，但这述算法中如果某 Proposer 实例获取到锁后发生了故障即会引发死锁导致服务不可用。

诚然我们可以为锁加过期时间（由 Proposer 指定本次锁的到期时间以确保可以在同一时间释放），但这样做以及加锁本身对服务的可用性/性能影响都比较大。

难点三：任意 Proposer 故障时仍然可用

我们推演到现在，使用锁的方式遇到了严重的挑战，但我们可以按上述两阶段投票的方式进行改进。

由于放弃加锁的方式，那么就不得不去直面并发请求带来的时序问题，首先想到的应该是为投票的提案带上时间戳以区别提案的前后时间。

我们先以只有一个 Accepter 的情况分析，如下图：

对于 Proposer1 而言，它的流程如下：

1. Proposer1 发起了提案号为 n1 的提案请求，这里要求提案号是有序递增的，多可使用时间戳组成

2. Acceptor 收到了提案请求，将自身的 maxN （收到的最大提案号）修改成 n1 ，并承诺 不接收小于等于 maxN 提案号的请求

3. 返回提案请求允可

4. Proposer1 正式发起提案，内容为之前的提案号及提案的值

5. Acceptor 收到了提案，将自身的 acceptN （接受的提案号） 更新为 n1 、 acceptV （接受的提案值，即确定的值） 设置成 v1 , 并承诺 不处理小于 maxN 提案号的提案

6. 返回提案成功

对于 Proposer2 而言，它的流程如下：

1. Proposer2 发起了提案号为 n2 的提案请求

2. Acceptor 收到了提案请求，将自身的 maxN 修改成 n2
   

3. 由于已形成了确定性值，所以直接返回已确定的值

从上面流程中可见，值的确定性是由 后者认可前者 的原则保障，只要有确定性的值，后续的提案都会认可这个值。

我们再看复杂些的情况：

如上图，Proposer1 与 Proposer2 交叉执行，它们的流程如下：

p1-1.2.3. 同前面流程 p2-1. 此时 Proposer2 发起了提案号为 n2 的提案请求 p2-2. Acceptor 收到了提案请求，将自身的 maxN 修改成 n2p2-3. 返回提案请求允可 p1-4. 此时 Proposer1 正式发起提案，提案号 n1 提案值 v1p1-5. 由于已有更大的提案号 maxN = n2 ，所以返回错误 p2-4. 此时 Proposer2 正式发起提案，提案号 n2 提案值 v2p2-5. Acceptor 收到了提案，将自身的 acceptN 更新为 n2 、 acceptV 设置成 v2p2-6. 返回提案成功 p1-6. 由于 Proposer1 的第一次提案没有通过，所以增加提案号后重新发起提案申请，提案号为 n3p1-7. Acceptor 收到了提案请求，将自身的 maxN 修改成 n3p1-8. 由于前面已经形成了确定性值，所以直接返回之前的提案值

从上面流程中可见，Proposer2 可以抢占 Proposer1 的提案权，即后发起的提案在未形成确定性值时可以抢占现有的提案权。

至此，我们可以容忍任意 Proposer 的故障，那么存在多个 Acceptor 时又如何呢？

实际上，Acceptor 做的事与前面单一 Acceptor 场景一样，核心在于确保 Proposer 向所有的 Acceptor 发起请求，仅当超半数 Acceptor 返回成功时才算请求成功，否则重试。

上图略显复杂，我们逐步分析：

p1-1-6. 同前面流程 p2-1-9. 抢占式提案，使当前各 Acceptor 的 maxN 修改成 n2p1-7.8. Proposer1 向 Acceptor3（网络时延）发起了提案请求，但在提案请求阶段 Acceptor 不接受 ⇐ maxN 的提案号，故返回错误 p1-9-12. 由于超半数 Acceptor 返回成功（前一幅图），可以提交提案，但在提案提交阶段 Acceptor 不接受 < maxN 的提案号，故返回错误 p2-10-14. 此时 Proposer2 超半数 Acceptor 返回成功，可以提交提案，由于提案请求返回中都没有确定性值时，故使用 Proposer2 预设的值 v2 提交，超半数提案提交成功，故已形成确定性值 p1-13-21. Proposer1 更新提案号重新发起提案请求，各 Acceptor 更新 maxN 为最新的提案号 n3 并返回各自已确定的值 p1-22-30. 提案请求返回中存在确定性值： Acceptor1的(n2, v2) 及Acceptor2的(n2, v2) 使用提案号最大的确定性值做为新提案的值，对于上例是最大提案号 n2 , 对应的值为 v2，最终 Proposer1 与 Proposer2 都得到了确定性值 v2

如果各位能理解上述流程，那么恭喜你，你已经掌握了一致性算法中最著名的 Paxos算法 核心。

Paxos:开山鼻祖

Paxos ，这是公认的最伟大的分布式一致算法，可能没有之一。Google 的 Chubby、Spanner 都使用了 Paxos 以保证数据副本更新序列的一致性。

Paxos 协议见于 Leslie Lamport 在 1998 年发的 《The Part-Time Parliament》 ，在此论文中他假设了一个叫 Paxos 的小岛，岛上的各项决定要经议会同意，议会成员都是兼职的，议员的核心角色分为提案者（Proposers）、表决/投票者（Acceptors）。Proposer 提出提案（Proposal），提案信息包括提案编号和提议的值（Value），Acceptor 收到提案后可以接受（Accept）提案，若提案获得多数 Acceptors 的接受，则称该提案被批准（Chosen）。

此论文的描述晦涩难懂，以至于很多专业人士也一头雾水，所以 Lamport 在 2001 年又发表了 《Paxos Made Simple》 以简化说明，但这还是过于晦涩。

Paxos 算法有很多变种，包含但不限于：Basic Paxos、Multi Paxos、Fast Paxos、Byzantine Paxos……

值得一提的是 Paxos 能容忍消息丢失（节点不可达）、乱序，但存储必须可靠（没有数据丢失和错误），即这是“非拜占庭算法”，而 Byzantine Paxos 则解决了拜占庭场景。关于拜占庭问题我们后文会介绍。

如果上文的图示没有看懂，那么下文我们以 Basic Paxos 这一经典算法为例写伪代码进一步阐述。

Basic Paxos

Paxos 流程描述的文章太多了，但文字的描述过于苍白，上文我们用示例加示意图的形式已经描述了其核心流程，下面我们再用伪代码的形式更严格地描述 Basic Paxos 的核心流程：

Multi Paxos

从上文我们可以看到 Basic Paxos，算法的过程也比较复杂，确定一个值需要至少 2 次 RPC 并且可能存在活锁（即多个 Proposer 交替发起提案申请，见 Wikipedia Paxos （https://en.wikipedia.org/wiki/Paxos_(computer_science)） 的 Basic Paxos when multiple Proposers conflict 章节，本文不赘述），所以一般的 Paxos 实现都是基于 Multi Paxos，它只要约一次 RPC，算法复杂度也低一些。

Basic Paxos 之所以需要至少 2 次 RPC 是 prepare 阶段无法形成确定性取值，而其中的原因在于存在多个 Proposer 同时提案，所以 Multi Paxos 的核心思想是先为多个 Proposer 选举出 Leader，后续所有的提案都由这个 Leader 发起，这样可以省略 prepare 阶段，直接发起 accept。

Leader 选举的过程类同 Basic Paxos，需要至少 2 次 RPC，Leader 确定之后即只需要 1 次 RPC。

读者可能会有疑问：为什么这叫 Multi Paxos？这是个好问题，Multi Paxos 要解决的问题其实不止于减少 RPC 调用，Basic Paxos 在多轮 Prepare/Accept 下只能确定一个值，而 Multi Paxos 则可以在降低延时的同时确定多个值并且保证其顺序，这才是 Multi Paxos 被广泛地工程化应用的核心原因。

关于 Multi Paxos 的更多介绍可参见此 wiki phxpaxos https://github.com/Tencent/phxpaxos/wiki。

总结

本文我们通过图示及伪代码讲解了经典的 Paxos 算法实现原理，一致性算法还有很多，比如Raft、Zab，不同算法间实现的逻辑有很多的共通性，可以举一反三，如有必要笔者也会持续更新相关的内容。

关注我的公众号：

分布式架构的根基：深入浅出一致性算法​mp.weixin.qq.com