Leslie Lamport 于 1990 年提出的 经典 Paxos 是分布式共识算法的开山鼻祖, Google Chubby 的作者 Mike Burrows 就曾说过: 「这个世界上只有一种一致性算法, 那就是 Paxos」, 其他所有的一致性算法, 本质上都是对 Paxos 在实现层面的变体、优化或扩展;
因此 Paxos 算法是分布式理论入门的第一块基石, 欲涉足该领域, 就必须将其完全地、彻底地研究清楚;
分布式系统
我们为什么需要分布式系统?
因为物理硬件是不可靠的, 磁盘损坏、服务器宕机、网络丢包等各种问题都会造成传统单机服务的不可用, 所以我们必须使用分区冗余容错的方式 (多副本) 来对抗物理硬件的不可靠, 也就是说, 我们只有使用分布式系统, 才能架设起高可用、高可靠的业务服务;
但要让一群原本毫无关联的机器实现协调统一的默契合作却绝非易事, 我们设计出的分布式算法至少要满足以下能力:
- 高可靠性: 当客户端写入数据, 服务端返回成功, 必须保证客户端下次读取时一定能查询到, 不能丢失;
- 高可用性: 当分布式系统内的若干台机器宕机时, 系统整体依然能够对外正常提供服务;
- 强一致性: 整个系统必须对外保持一致的状态视图, 即同一时刻下客户端无论怎么请求读, 总能获取到相同的值;
有一个值得注意的点是: 并不是说, 凡存在多台机器分区部署的系统都叫做分布式系统; 比如我们绝大部分的业务应用, 会在很多台机器上部署相同的代码, 通过流量接入层的反向代理与负载均衡, 对外提供统一的服务, 这些机器之间没有任何交互, 甚至感知不到其他机器的存在, 这显然不能算分布式系统, 只能算是分布式集群;
区别分布式系统和分布式集群最关键的一点是有无状态:
- 当提供的是有状态服务 (比如存储系统), 需要多副本和跨机器复制, 需要使用共识算法来协调各机器间的状态同步时, 叫做分布式系统;
- 当提供的是无状态服务 (如普通的业务服务), 无需亲自实现状态存储的逻辑 (通常是代理给了下游的分布式系统去实现, 比如数据库), 叫做分布式集群;
Paxos 之前的分布式算法
在 Paxos 诞生之前, 其实已经有很多方案尝试去解决分布式系统的难题, 但他们都有自己的局限性和缺陷, 无法全部解决上述三个问题;
主从异步复制
主从异步复制是最简单的策略, 但存在一个最基本的问题: 客户端请求写入数据, 收到服务端的响应成功, 离数据真正安全 (数据复制到全部的机器上) 在时间上有一个空隙, 如果接收请求的 master 在响应成功后立刻宕机, 数据就会丢失, 因此主从异步复制不可靠;
主从同步复制
跟主从异步复制相比, 主从同步复制提供了完整的可靠性: 直到数据真的安全的复制到全部的机器上之后, master 才会向客户端响应成功; 但主从同步复制有个致命的缺点: 整个系统中有任何一个机器宕机, 写入就进行不下去了, 相当于系统的可用性随着副本数量的增加而指数性降低, 因此主从同步复制不具有高可用性;
主从半同步复制
如果在主从同步复制和主从异步复制之间做一个折中, 要求 master 在应答客户端之前必须把数据复制到足够多的机器上, 但不需要是全部, 这就是主从半同步复制; 这样副本数够多可以提供比较高的可靠性, 同时在 1 台机器宕机时也不会让整个系统 hang 住;
这种方案似乎同时解决了高可靠和高可用的问题, 但是主从半同步复制依然无法解决一种情况,例如:
- 数据 a 复制到了 slave1, 但没有复制到 slave2;
- 数据 b 复制到了 slave2, 但没有复制到 slave1;
这时如果 master 挂掉了需要从某个 slave 恢复出数据, 任何一个 slave 都不能提供完整的数据 a 和 b, 因此主从半同步复制不完全可靠;
多数派读写
为了解决半同步复制中数据不一致的问题, 可以将这个复制策略稍做改进: 多数派 (Quorum) 读写, 每条数据必须写入到半数以上的机器才能返回成功, 每次读取数据也都必须从半数以上的机器获取, 以确认数据是否存在;
这种方案已经同时解决了可靠性和可用性, 但可惜它解决不了一致性的问题, 例如:
- 第一次更新向 node1 和 node2 写入了 a = x;
- 第二次更新向 node2 和 node3 写入了 a = y;
那么此时客户端分别从 node1、node2 读取 a, 将读出两个不同的值, 从而无法确定真正的结果, 因此多数派读写不具有强一致性;
带版本的多数派读写
针对上述多数派读写的一致性问题, 可以给每次请求写入带上一个全局单调递增的 version, 读取的过程中优先采纳版本更高的值; 只不过这种方式依然有缺陷: 当客户端没有完成一次完整的多数派写时, 比如:
- 第一次更新向 node1 和 node2 写入了 a = x (version=1);
- 第二次更新只向 node3 写入了 a = y (version=2) 后就宕机或后续逻辑执行延迟;
若另一个客户端此时试图读取 a 时:
- 当从 node1 和 node2 读取时, 得到的结果为 x;
- 当从 node2 和 node3 读取时, 得到的结果为 y;
因为这种方式不能做到事务性更新 (没有原子性、没有隔离性), 因此带版本的多数派读写仍不具备严谨的强一致性;
Paxos 的实现
Paxos 是多数派读写的进一步升级, 其通过 2 次原本并不严谨的带版本多数派读写, 实现了严谨的强一致性共识算法;
Phase-1: Prepare
phase-1 的 Proposer 请求与 Acceptor 响应:1
2
3
4
5
6
7
8
9
10
11> request (Proposer):
rnd: int
> response (Acceptor):
if (rnd < last_rnd):
return fail // 中断拒绝
return {
last_rnd: int
last_v: "xxx"
last_vrnd: int
}
Proposer 对 phase-1 中 Acceptor 响应的处理:1
2
3
4
5
6
7
8
9
10
11
12> response (Acceptor):
last_rnd: int
last_v: "xxx"
last_vrnd: int
> resp_process (Proposer):
// 所有 acceptor 应答的 last_v / last_vrnd 都是空: 用自己的 v / vrnd
if (last_v == nil && last_vrnd == nil):
use(v, vrnd)
// 从所有 acceptor 应答中选择 last_vrnd 最大的 last_v 作为 phase-2 要写入的值, 但 vrnd 依旧用自己的
v_with_biggest_rnd = chooseBiggestRndV(last_v, last_vrnd)
use(v_with_biggest_rnd, vrnd)
注意: 如果 Proposer 收到了某个应答包含被写入的 last_v 和 last_vrnd, 这时当前 Proposer 必须假设有其他客户端 (Other Proposer) 正在运行, 虽然不知道对方是否已经成功结束, 但任何已经写入的值都不能被修改, 所以当前 Proposer 必须保持原有的值: 将看到的最大 last_vrnd 对应的 last_v 作为下一阶段将要写入的值;
Phase-2: Commit
phase-2 的 Proposer 请求与 Acceptor 响应:1
2
3
4
5
6
7
8request (Proposer):
v: "xxx"
rnd: int
reponse (Acceptor):
if (rnd < last_rnd):
return fail // 中断拒绝
record (v, vrnd)
Acceptor 通过比较 phase-2 请求中的 rnd 和自己本地记录的 last_rnd, 来确定当前请求的 Proposer 是否还有权写入:
- 当 rnd == last_rnd: 这次写入是被允许的, Acceptor 将 v 写入本地, 并将 phase-2 请求中的 rnd 记录到本地的 vrnd 中;
- 当 rnd < last_rnd: 拒绝返回失败;
- 不可能存在 rnd > last_rnd 的情况: 因为 phase-1 保证了 Proposer 的 rnd 一定曾被 Acceptor 记录下来过;
