一种区分读写操作的对工程实践友好的分布式一致性协议

一种区分读写操作的对工程实践友好的分布式一致性协议

摘要

流行的共识算法如 Paxos[1] 和 Raft[2] 被广泛地应用于分布式系统中, 用于实现一致性. 但是, 这些算法本质上并不区别读和写操作, 因而给工程实践带来了极大的困扰. 这种困扰导致在具体实现时, 开发者往往基于性能优化方面的考虑, 对这些算法做没有经过理论验证的更改.

我想在区分读写操作的前提下, 设计一种对工程实践友好的分布式一致性协议, 能适应读多写少或者读少写多等不同场景的需求. 这个分布式协议基于 Quorum 机制, 采用 2PC 策略和复制状态机模型, 适用于有强一致性要求的分布式数据库系统和其它分布式系统.

区分读写操作

无论是从用户的角度还是从实现的角度, 数据库系统等分布式系统都明确地区分读和写操作. 读操作不改变系统的状态, 同时被认为系统在处理读操作时, 不会写任何数据. 实际上, 读操作的处理过程往往会涉及到写数据, 但写数据不会导致从用户的角度所看到的系统的状态发生改变, 而且, 从性能的角度考虑, 要求在处理读操作过程中写得越少越好. 写操作则会改变系统的状态.

读操作被认为是成本低的, 至少是应该实现成低成本的. 而写操作被认为是成本高的. 经验表明, 很多系统是读多写少型, 但也有不少是读少写多型. 一个好的分布式一致协议应该能适用于不同类型的系统.

Paxos 和 Raft 不区分读写操作, 而是把读和写都当做”操作”统一对待, 所以读和写的成本应该是相等的. 其中, 以 Paxos 最为明显, Paxos 本质上是一种读修复算法, 并且 Basic Paxos 暗示每一次操作都要进行修复. 实现上, 很多人对 Paxos 进行了本质改进, 但仍然冠以 Paxos 之名, 我认为这种乱冠名的做法增加了学习者和使用者的困扰.

本文所设计的协议基于 Quorum 机制, 即 W + R > N , 天生地区别对待读和写操作, 因此对使用者不会造成困扰, 反而呼应了使用者的诉求. 这个协议还针对不同读写比例的场景提供了优化方案, 在测试场景中相比 Paxos 和 Raft 有不少性能提升.

线性一致性

线性一致性是指, 如果认为所有的写操作是串行化有先后顺序的, 当一个读请求读取到某一次写 W 操作的结果之后, 那么在这个读请求之后的所有读请求, 都不能读取到该写操作之前的任何写操作的结果.

也即, 我们认为读操作也是串行化有先后顺序的, 后面的读操作读取的数据, 不得比前面的读操作读取到的数据更旧.

Quorum 机制

在一个多副本的集群系统(组)中, 一个实例(instance)的数据被保存为 N 个副本(replica). 实例在唯一标识(identifier), 对应的实例值和状态. 实例会被多次更新成不同的值, 每一次更新值时会同时更新状态, 所以值和状态是绑定的, 每一次更新所对应状态不一样. 状态包含了用于区分同一个实例的不同值的新旧程度, 一般只有版本号(num, version number), 也有采用时间戳, 后面会介绍如何维护版本号, 以提供一致性保证.

每次更新实例时, 需要更新至少 W 个副本之后才算是成功. 读取实例时, 至少要读到 R 个相同的副本才算成功. W, R, N 的关系必须满足

W + R > N

这样才能确保读操作能读到之前写的最新值. 一般会设定为 W + R = N + 1 , 在这个设定下, Paxos 等算法让 W = R = N/2 + 1 , 也即所谓的多数派(majority). 本文不限定多数派, 在不同的系统中设定不同的 W 和 R 的值, 但仍然保证 W + R = N + 1 , 这也是针对不同读写比例做优化的基础.

角色

客户端(Client)的请求一般通过网络发往服务器(Server), 服务器处理后给客户端返回一个响应.

在服务器内部, 请求的接收者和副本的维护者往往模糊地作为一个整体, 但我们需要区分这两个对象. 请求的接收者被称为 Proposer, 它处理完客户端的请求后, 进行处理, 如操作 Acceptor 读写副本, 然后返回一个响应. 副本的维护者被称为 Acceptor, 负责数据的实际读写, 一个 Acceptor 绑定一个副本.

一般每个 Acceptor 会绑定一个 Proposer, 但 Proposer 是独立的, 和 Acceptor 不必一一对应, Proposer 的数量可能多于副本的数量也可能少于副本的数量, 而且还可能在物理上是分离的.

写操作的过程

1. Proposer 收到客户端的写请求, 写请求中带有客户端想设置的实例的标识和新值
2. Proposer 以一个新的版本号作为实例的新状态, 向所有 Acceptor 发送请求, 要求更新实例
3. 如果 Proposer 收到了至少 W 个 Acceptor 的正面响应, 那么就可以给客户端返回一个成功标记的响应

我们没有讨论如何产生一个”新的版本号”, 这个问题留在后面讨论.

这个流程还有未解决的地方, 当 Proposer 过了一段时间仍然无法收集到至少 W 个 Acceptor 的正面响应, 它应该如何处理? 它能给客户端返回一个失败标记的响应吗?

事实上, 此种情况 Proposer 不能告诉 Client 操作失败了, 因为在未来某个时间也许能收到至少 W 个响应. 或许, 虽然 Proposer 没有收到响应, 但 Acceptor 确实更新了自己所维护的副本.

脏写

在所描述的正常流程之外, 还存在一种可能, 那就是我们从上帝视角观察, 有 X 个 Acceptor 确实更新了自己的副本, 但 Proposer 并没有知晓. 如果 X >= W , 那么我们从上帝视角判断, 这个写操作应该算是成功的. 如果 X < W , 那么就是所谓的” 脏写 ”.

“脏写”是影响一致性的关键因素, 如何处理”脏写”导致的”脏数据”, 是一致性算法和协议所具有一致性的关键.

读操作的过程

1. Proposer 收到客户端的读请求, 读请求中带有客户端想读取的实例的标识
2. Proposer 向所有 Acceptor 发送读请求, 要求返回实例的状态(版本号)和对应的值
3. 如果存在 R 个响应的版本号和值是完全相同的, 那么以这个值返回给客户端
4. 如果不存在 R 个完全相同状态的值, 也许 会返回最新的值

这个流程描述的是如何做, 但并不表示这样做是”正确的”. 而且, 需要特别指出的是, 这个所谓的 Quorum Read 流程, 是众所周知的 无法保证一致性的 . 之所以这样做, 是因为这个流程有一定的意义, 但对于一个要求一致性的分布式系统中, 它是错误的, 这一点必须非常明确. 我们将介绍为什么 Quorum Read 无法满足一致性 .

设想在一个 N=4, W=3, R=2 的集群里, 因为某一次脏写导致所有实例副本的状态如下:

A: num=1; B: num=1; C: num=2; D: num=2

按照读流程, Proposer 可能读取 A, B, 即 num=1, 或者读到 C, D, 即 num=2, 这种行为被称为不一致, 显然不符合一致性的要求.

如果 Proposer 读到了 B 和 C, 也即 num=1 和 num=2, 它也许可以选择(正如大众的朴素认识)返回最新版本的数据, 即 num=2. 但是, 这种策略仍然无法保证一致性.

对 Quorum 机制的改进

传统的 Quorum 机制最大的问题是读操作的前提是假设写操作必须是成功的, 否则就无法满足我们对一致性的期望. W + R > N 能确保读和写有交集的前提是写必须完全成功, 不能出现脏写, 否则读的结果是不可预测的. 而脏写是不可避免的, 所以我们只能在读流程上进行改进.

我试图从两个方向来进行改进:

1. 脏数据检测
2. 读修复

脏数据检测

首先, 考虑读取 R 个副本是否能检测到是否存在脏数据. 很遗憾, 无法判断. 考虑一个有 3 个副本的集群, R=2, 那么当只有一个副本存在”脏数据”时, 读取另外两个副本是无法发现脏数据的. 那么, 读取 W 个副本是否可以呢? 同样不行.

唯一能检测到脏数据的方案是读取 N 个副本. 但读取 N 个副本造成系统没有任何容灾能力.

读修复

既然脏数据是不可避免的, 而又不存在可靠的手段检测脏数据, 剩下的手段就是对所有副本产生一个共识, 让读请求读到的是共识的值, 如果共识算法能产生可预期的一致的结果, 那么就实现了系统的一致性.

在处理读请求的过程, 在给客户端返回响应前, 确认一个旧的共识, 或者创造一个新的共识, 我们称之为”读修复”. 这不同于传统意义上的读操作, 因为传统意义上的读操作被认为不应该写任何数据, 而读修复操作明显会写一些数据.

读修复的过程便是这样的:

1. Proposer 向所有 Acceptor 发送读取各自副本最新值的请求
2. 如果收到 X 个响应表明这 X 个副本完全相同, 那么以其中一个的值返回给客户端
3. 如果收到 X 个响应后, 这些副本并不是完全相同, 那么, Proposer 可以继续等待全部 N 个响应, 或者立即执行下一步操作, 即修复数据
4. 从 X 个副本中选取最新的一个, 绑定一个新状态, 执行写操作流程

其中, X = max(W, R) .

这正是 Paxos phase 2 所做的.

线性一致性的保证

经过改进的 Quorum Read 操作是符合线性一致性的, 我们应该给它取一个新名字, 避免与传统的 Quorum Read 相混淆. 在取新名字之前, 我们不再使用 Quorum Read 这个名词.

读修复的意义在于, 必须读取到 X 个相同的副本, 才算是一次成功的读取操作. 因为 W + R > N 限制, 集群中不可能同时存在两组不同的副本且每一组的数量都至少是 X, 因此, 一致性得以保证.

Paxos 本质上就是一种读修复算法, 任何对 Paxos 的改变丢失了读修复步骤, 例如引入固定的 leader, 或者等待别人修复, 都不应该再冠以”Paxos”之名.

2PC

前面提到了版本号, 但没有讨论如何产生版本号. 产生版本号, 是非常关键的步骤, 否则两个 Proposer 可能使用了相同的版本号. 虽然我们在检查副本是否相同时, 既依赖版本号, 也依赖检查版本号对应的值是否相同, 但是, 如果能仅仅通过版本号来判断, 那么就不必检查对应的值. 现实中这样做是有用的, 因为检查值可能是一个成本非常高的操作, 而检查版本号仅仅是整数比较.

我们希望不依赖外部的版本号分配器类似的额外组件, 仅通过集群内部自主产生不可重复的版本号. 基于多数派的技术可以达到这个目的.

1. 申请版本号

1. 首先, 集群的每一个成员都记录着自己所知道的集群的最新版本号 lastnum. 当任何一个成员(Proposer) 想申请一个新版本号时, 它将自己所知道的 lastnum 加 1, 得到 num
2. Proposer 向全部 Acceptor 发送 Prepare 类型的消息, 带上自己期望的版本号 num
3. 如果 Acceptor 收到的 num 比自己的 lastnum 更大, 则同意, 更新自己的 lastnum, 返回响应
4. 当 Proposer 收到超过半数同意时, 表明它申请到了新的版本号
5. 如果 Proposer 申请地成功, 它更新自己的 lastnum, 继续申请

这正是 Paxos phase 1 所做的事. 能否通过少于或者等于半数成员就申请到版本号呢? 不行. 这个结论非常显然.

2. 写操作

Proposer 将申请到的版本号附加于其希望更新的值, 然后执行前面所提到的写操作流程.

读写优化

前面我们已经分析了 Quorum 机器和 2PC 策略, 我们总结一下分布式系统中实现一致性所必须几个必要条件:

1. 写操作先申请版本号, 然后再写 W 个副本
2. 读操作先检测脏数据, 然后再读 R 个副本
3. 如果读操作检测到脏数据, 应主动修复或者等待修复

其中, 申请版本号操作需要与至少 M = N/2 + 1 个 Acceptor 交互, 检测脏数据需要与至少 X = max(W, R) 个 Acceptor 交互.

因此, 系统的成本组合就显而易见了. 通过设定不同的 W, R, 增加和减少各个步骤的成本, 可以达到针对不同的场景优化的目的.

申请版本号优化

如果由集群自主地分配版本号, 则每一个申请版本号的 Proposer 必须与至少 M 个 Acceptor 交互. 在 N 固定的情况下, M 也是固定的. 所以, 唯一优化的方向就是打破我们的原则, 不由集群自主分配, 而是引入外部的版本号分配器. 这里不讨论.

这里提一句, Raft 通过选举产生固定的 leader, 然后由 leader 充当版本号分配器的角色. 我认为某种层面看这仍然适用于外部的概念, 虽然 leader 确实是集群内部的成员. 我们说的自主, 是指各个成员的角色和地位是平等的, 改变任何一个成员的角色, 等同于引入外部的新角色.

检测脏数据优化

如同申请版本号优化, 在 W 和 R 已定的情况下, 优化的唯一方法是引入外部角色. 这里不讨论.

W 与 R 的选取

W = 1
R = 1
W = R = N/2 + 1

很显然, Paxos 或者 Raft 是基于 majority 的算法, 只能在版本号分配和检测脏数据上面进行优化. Paxos, 或者说 Basic Paxos 本质上不考虑优化问题. Raft 本身包含了优化方案.

复制状态机模型

[1] Paxos Made Simple

[2] Raft - In Search of an Understandable Consensus Algorithm