谈谈分布一致性协议

在分布式系统中, 为了解决多数据副本的一致性问题, 需要一种协议机制, 来确保分布式数据的明确状态, 并能对外提供 (最终) 一致性的读写服务。

1. 两阶段提交协议(Two-Phrase Commit, 2PC)

两阶段提交的语境下, 存在两类实体: 唯一协调者 (Coordinator, 下文简称 C) 和多个参与者 (Participants, 下文简称 P) , C 负责管理协调。

两阶段提交将事务的提交过程分为两阶段:

  1. Voting: C 向 P 发送 VOTE_REQUEST, P 如果可提交, 回应 VOTE_COMMIT 并锁定本地资源, 否则回应 VOTE_ABORT, 表示暂时无法提交。
  2. Commit: C 收集所有 P 的回应
    • 如果都是 VOTE_COMMIT, 即可认为事务最终可提交, C 向所有 P 发送 GLOBAL_COMMIT, 通知 P 本地提交, P 本地处理后回复 ACK。
    • 如果至少有一个 P 超时没回应, 或者回应 VOTE_ABORT, 即认为事务无法达成, C 向所有 P 发送 VOTE_ABORT, 通知取消事务, 释放资源, P 本地处理后回复 ACK。

2PC 的实现简单, 但在事务提交过程中, C、P 节点处于阻塞, 要么全成功, 要么全失败。

但是对大规模分布式系统来说, 单节点异常是常态, 对异常的处理, 2PC 比较差:

  1. 如果 C 在发起 Voting 后宕机 (包括 Commit 阶段), 所有的 P 节点会被阻塞, 直到 C 节点恢复。
  2. 如果 C 在宕机后恢复前, 有一个 P 节点发生宕机, 那么即便 C 节点恢复, 其余的 P 节点也会被阻塞, 因为此时新 C 节点无法感知宕机的 P 状态。
  3. 如果 P 在 Voting 阶段宕机失去响应, C 无法确认 P 状态, 只能等 P 恢复后响应, 否则会阻塞。当然, 这里可以通过引入超时机制来保护, 但需要处理 P 恢复后的异常响应, 且有 throughput 低的问题。
  4. 如果 P 在 Commit 阶段宕机, 会导致本地提交失败, 全局数据不一致, 丢失了正确性!此时 C 的状态同第 4 种异常。

综上, 在分布式系统中单独使用 2PC 是比较少见的, 一般常用在其他协议中, 作为更新数据的原子手段。

2. 三阶段提交协议(Three-Phrase Commit, 3PC)

三阶段提交协议 (3PC) 是学术界提出的解决 2PC 阻塞和异常的一种方法, 核心思想是将 2PC 的提交拆分成: Pre-Commit 和 Commit 两个阶段。

从上图可以看出, 相比 2PC, 3PC 多了一步 PreCommit, PreCommit 过程中, P 节点需要准备好资源后锁定, 并保证操作可回滚 (例如 binlog + redolog) , 因为可回滚的特性, 如果在整个事务过程中中有单个节点失败, 恢复后可以自行回滚或者提交, 不会阻塞整个网络:

  1. 如果 P 收到 VOTE_COMMIT 后 C 宕机, P 节点可以等超时后自行取消事务并结束。
  2. 如果 P 收到 PreCommit 后 C 宕机, P 节点可以在超时后自行提交事务。
  3. Voting 阶段 P 宕机, 同 2PC 的第 3 种异常。
  4. PreCommit 阶段 P 宕机, C 接收 ACK 超时, 事务取消并结束, C 通知 P 回滚。
  5. Commit 阶段 P 宕机, C 接收 HaveCommited 超时, 事务取消并结束, C 通知 P 回滚。

从上面异常情况的分析, 可以得知, 3PC 协议中因为多了一步 PreCommit, 所以 P 节点可以根据 PreCommit 信息自行决策提交或者取消事务, 进而解决了 C 节点异常时的阻塞问题, 但 3PC 仍需要依赖复杂的状态机超时来保证 work, 并且由于增加了一次 RTT 开销, 效率更低, 所以实际应用极少。

3. Quorum 协议

Quorum 协议是 Amazon 在 Dynamo KV 中提出的, 是一种投票算法, 其数学思想源自鸽巢原理

描述一下基本概念:

  • N: 分布式系统中, 数据有多少份副本。
  • W: 一次成功的写操作, 至少有 W 份数据写入成功。
  • R: 一次成功的读操作, 至少有 R 份数据成功读取。
  • 当满足 R + W > N, 且 W > N/2 时, 可以满足数据一致性, 所以又常被叫做 RWN 协议。

理论上, 违背了 RWN 规则的, 都是"单点"的存在, 例如 MySQL 主备, N=2, R=1, W=1.

Quorum 协议最大的好处, 是可以灵活配置, 既可以支持数据的强一致性, 也可以支持最终一致性。

当然, 仅靠 Quorum 本身不足以完成一致性保证, 还需要一些其他方式: 例如 R > 1 时, 还需要通过对多个副本的读结果进行比对, 结合向量时钟版本号, 判断哪些数据是最新的。

除了保证一致性之外, Dynamo 还需要保证自己的 SLA, 当发生分区或者节点故障时, 也要能提供服务, 所以 Amazon 采取了一种 "Sloppy Quorum" 的方式, 读写跳过故障节点, 具体细节可参照 paper, 不在此深入。

4. 向量时钟(Vector Clock)

向量时钟不是分布式协议, 只是一种算法, 可以在分布式网络下生成事件偏序关系, 典型的应用场景是根据事件来判断其时间顺序 (因果关系) 。

向量时钟的规则如下:

  1. 假设分布式系统中存在 N 个节点, 每个进程 Pi (1 <= i <= N) 记录一个初值为 0 的 N 维向量时钟 Vi = {0, 0, ... 0}。
  2. 当进程 Pi 发送消息、接收消息、或者处理内部事件后, 更新 V[i] = V[i] + 1。
  3. 当进程 Pi 发送消息时, 要把自己的向量时钟一并发出去。
  4. 当进程 Pi 收到 Pj 的向量时钟时, Vi = Max{Vi, Vj}, 对每一位都取大值。

举个例子:

  • 某个时刻, 进程 P1 的时钟向量 V1 = {1, 2, 3} 。
  • P1 收到 P3 的消息, V3 = {0, 4, 2}, 根据规则2, V1 -> {2, 2, 3}, 再根据规则4, V1 -> {2, 4, 3}。
  • P1 要发送消息给 P2, 根据规则2, V1 -> {3, 4, 3}, 根据规则3, 将 V1 带上一并发给 P2。

下图是一个更复杂的例子:

Dynamo 中使用向量时钟进行多副本的数据版本管理, 并配合 RWN 协议共同完成数据一致性维护:

  • Dynamo 客户端写数据时带版本号, 这个版本号就时通过向量时钟来获得。
  • Dynamo 客户端读数据时, 如果读出多个副本, 则根据向量时钟来判断因果关系, 并得出最新的数据。

5. Paxos 协议

Paxos 无疑是最近些年来, 分布式领域的最热的话题之一。有这么一种说法: 所有一致性协议要么是 Paxos, 要么是其变种。Paxos 算法的提出者 Leslie Lamport 也是一位传奇大神, 他对分布式领域作出的杰出贡献, 为其赢得了 2013 年的图灵奖。

Paxos 协议提出了三种角色:

  • Proposer, 倡议者, 下文简称 P, 可以提议供投票表决。
  • Acceptor, 接受者, 下文简称 A, 可以对倡议者发的提议进行投票表决。
  • Learner, 学习者, 下文简称 L, 可以从接受者里获知哪个协议最终被选中。

上面每个角色都可能在分布式网络中存在多个, 并可能并存。

Paxos 分为 Basic Paxos 和 Multi Paxos, 我们分别来看。

5.1 Basic Paxos

基本流程如下图(From Wiki):

一次选举的过程有四次交互:

  1. Prepare. 某个 P 提议编号 n, 向大多数的 A 发送 Prepare 请求
  2. Promise. 某个 A 收到 P 的提议编号 n:
    • 如果 A 曾经 Accepted(m), 且 m >= n, 则不回应。
    • 如果 A 曾经 Promise(m), 且 m >= n, 则不回应。
    • 如果 A 曾经 Accepted(m), 且 m < n, 则 A 回应 Promise {n, m, Vm}
    • 如果 A 之前没有收到过 Prepare, 则回应 Promise(n)
    • 如果 A 曾经 Promise(m), 且 m < n, 则回应 Promise(n)
    • A 一旦 Promise, 意味者承诺不会再 Promise 编号小于 n 的请求。
  3. Accept. 如果 P 收到了大多数 A 对提议 n 的 Promise, 那么 P 向这些 A 发送 Accept(n, Vn) 请求
    • 如果 A 返回的是 Promise(n), P 可以倡议一个新值 Vn。
    • 如果 A 返回的是 Promise(n, m, Vm), 那么 P 需要选取一个编号最大的 m 所对应的 Vm, 作为本次提议的 Vn。
    • 由上可见: 一旦被选举过, 必然保证一致, 哪怕有新的倡议, 也必须服从大局。
  4. Accepted. 如果 A 收到了 P 的 Accept(n, Vn) 请求
    • 如果 A 没有收到过 Prepare, 则接受。
    • 如果 A 收到过 Prepare(m), 且 n >= m, 则接受。
    • 否则, 忽略请求。

通过上述流程, 如果有多个并发进程提出各自的倡议值, Paxos 算法可以保证从中选出, 且只选出一个作为唯一确定的倡议值, 以此达到副本状态机一致的目标。每个副本的值不保证完全一致, 但可以通过算法确认出一个一致的值。

另外, wiki 中分别列举了 A、L、P 异常的场景, 有一种特殊的场景这里也列一下: 当一个 P 异常后再次恢复, 可能会导致多个 P 相互交替发起提议, 类似互锁, 无法快速恢复, 非常低效。场景流程如下图:

5.2 Multi Paxos

Basic Paxos 协议因为有多个 P 的存在, 系统运行时在保证了正确性的前提下, 效率不高, 例如上节所描述的极端场景。

所以 Multi Paxos 对这种情况做了改进, 将整个过程分成了两阶段:

阶段一:初始阶段, 选主, 更新 V, 同 Basic Paxos。

阶段二:稳定状态, 已经确定了主, 可以跳过 Prepare-Promise 的一次交互, 进而提高效率。

5.3 Paxos 的应用

在 2N+1 个节点的分布式网络中, 只要不超过 N 个节点故障, Paxos 协议都可以保证正常运转, 当然节点越多, 系统的 throughput 越低。

换言之, Paxos 一致性协议, 为了保证 C 而妥协的 A, 可以通过增加节点数来提升, 所以在工程实践中, 选取合适的节点数, 可以做到对可用性的影响极低。

当然, Paxos 协议也是符合 RWN 规则的, 假设 N = 2n + 1, Paxos 要求的 R >= n+1, W >= n+1。

Paxos 协议在分布式系统中, 应用非常之广泛, 实现包括有著名的 Google ChubbyApache Zookeeper, 以及Tencent PaxosStore, 应用范围包括但不限于: 名字服务(内部DNS)、服务发现、分布式锁、分布式配置中心、分布式 KV 存储等。

6. Raft 协议

因为 Paxos 是出了名的难理解, 且工程实现非常困难 (Chubby 曾经踩了很多坑, ZooKeeper 也并非严格意义上的 Paxos 完备实现) , 所以 Standford 研究出了一种新的分布式协议 Raft, 注重落地和可理解性。

Raft 和 Paxos 类似, 也提出了三种角色:

  • Leader: 处理所有客户端交互, 日志复制等, 下文简称 L, 一次只有一个 Leader
  • Follower: 只负责投票, 下文简称 F
  • Candidate: 候选人, 下文简称 C, 可以被选为一个新的 Leader

简单来说, Raft 的运行分三个阶段:

  1. 选举阶段(Leader Election): 任何 C 可以向所有的 F 发送 Vote 请求, 只要有超过半数的 F 同意了, 这个 C 就称为了 L。
  2. 日志复制阶段(Log Replication): L 向所有的 F 发送日志复制指令(和 Paxos 类似, 有两次交互), 以及心跳通知。参考上一节可以看出, 此时和 Multi Paxos 的阶段二几乎一样。
  3. 异常阶段: 当 L 宕机崩溃后, F 通过超时机制称为 C (因为超时算法中包含随机性, 所以出现 Split 的概率比较低), 并再次发起选举, 直到集群中出现一个 L。

Raft 服务节点的状态可以用下图来表示:

更深入的运行过程, 强烈建议大家去读一下 Raft 的一个 E文演示动画, 效果非常赞。

Raft 协议本质是 Paxos 的变种, 和 Paxos 最大的不同之处就在于 Raft 的强领导特性:Raft 使用领导人选举作为一致性协议里必不可少的部分, 并且将尽可能多的功能集中到了领导人身上。 这样, Raft 在保证了正确性的同时, 更容易理解, 实现性能也相较 Paxos 有所提升。

7. 延伸阅读

  1. Consensus Protocols: Two-Phase Commit
  2. Consensus Protocols: Three-phase Commit
  3. Wiki: Three-phase commit protocol
  4. Wiki: Vector Clock
  5. Consistency and availability in Amazon's Dynamo
  6. Wiki: Paxos (computer science)
  7. Wiki: Leslie Lamport
  8. The Chubby lock service for loosely-coupled distributed systems
  9. Apache ZooKeeper
  10. In Search of an Understandable Consensus Algorithm (Extended Version)
  11. 比较raft , basic paxos以及multi-paxos
  12. Raft 一致性算法论文译文