跳到主要内容

并行和分布式事务处理

23.1 分布式事务​

分布式事务(distributed transaction)指一个事务的读写涉及多台节点上的数据。相比单机事务,它面临三大新问题:如何在多节点上原子提交、如何在多节点上做并发控制、如何应对独立故障与网络分区。

23.1.1 系统结构​

一个典型的分布式事务系统包含以下角色:

  • 事务协调者(Transaction Coordinator,TC):接收客户端请求,跨节点分发子事务,驱动提交协议。
  • 参与者(Participant / Resource Manager,RM):每台数据节点上的本地事务子系统,执行本地读写、持久化 WAL、响应协调者。
  • 锁管理器 / 时间戳服务:本地或全局的并发控制部件。
  • 目录 / 元数据服务:记录数据分片位置、副本关系、事务全局 ID。

事务在逻辑上是一个整体,物理上被切分为若干子事务(sub-transaction),每台参与者上一个。协调者负责把这些子事务的提交或中止"绑在一起",任何一个不成功都必须让全体回滚,任何一个提交都必须让全体提交。

23.1.2 系统故障模式​

分布式事务需要处理比单机复杂得多的故障:

  • 节点故障(fail-stop):进程崩溃或机器宕机后停止响应,恢复后可从 WAL 重建状态。
  • 通信故障(omission):消息丢失或迟到,尚未收到 ≠ 对方未发出。
  • 网络分区(partition):网络被切成互不可通的两半,各自认为自己是正常一方。
  • 拜占庭故障(Byzantine):节点行为任意,可能发出不一致或恶意消息。传统数据库通常假设非拜占庭(fail-stop),共识协议如 PBFT 才处理拜占庭。

后续讨论以fail-stop + 异步网络为默认假设:进程可能宕机、消息可能丢失或延迟任意长时间,但没有恶意节点。


23.2 提交协议​

提交协议(commit protocol)的核心目标是原子性:所有参与者要么全部提交,要么全部中止;即便协调者或参与者中途宕机,恢复后也能达成一致结论。

23.2.1 两阶段提交​

两阶段提交(Two-Phase Commit,2PC) 是最经典的方案:

阶段 1(准备 / prepare / voting):

  1. 协调者向所有参与者发送 PREPARE。
  2. 参与者持久化 <PREPARE T> 到本地 WAL,并保持全部锁;若能提交则回复 READY,否则回复 ABORT。

阶段 2(提交 / commit):

  1. 若协调者收到全部 READY,则持久化 <COMMIT T>,向所有参与者广播 COMMIT;否则持久化 <ABORT T> 并广播 ABORT。
  2. 参与者收到 COMMIT/ABORT 后写本地日志并释放锁,回 ACK。

关键不变式:一旦协调者写下 <COMMIT T>(阶段 2 的第一条日志),事务就已经决定提交——即使随后协调者宕机,恢复后仍会重发 COMMIT。同理,若协调者尚未写 <COMMIT T> 之前宕机,则事务必然中止。

故障恢复:

  • 参与者宕机:恢复后查看 WAL,若有 PREPARE 但无 COMMIT/ABORT,则询问协调者结果。
  • 协调者宕机:若已在 WAL 写 COMMIT,重发;否则询问参与者的投票再决定。
  • 参与者在 READY 后、收到决定前处于不确定态(in-doubt),只能等;这是 2PC 最著名的缺陷——阻塞协议。

23.2.2 提交期间的阻塞避免​

2PC 的阻塞根源:参与者投出 READY 之后、协调者写决定日志之前,若协调者宕机 + 与其他参与者失联,任何单个参与者都无法独立决定。

缓解方案:

  • 三阶段提交(3PC):在 2PC 中间插入一个 PRE-COMMIT 阶段。协调者收到全部 READY 后先发 PRE-COMMIT,参与者回 ACK-PC 后协调者才发 COMMIT。任何时候只要多数派到达 PRE-COMMIT,即使协调者失联,参与者也能通过与其他参与者通信推断出决定。3PC 在同步网络假设下非阻塞,在异步网络下仍不能完全避免阻塞。
  • 基于 Paxos/Raft 的提交:用共识协议复制协调者的决定日志——即所谓Paxos Commit。协调者本身是一个副本组,任何单点宕机都不会阻塞整体。这是现代系统(Spanner、CockroachDB)的做法,见 23.8.5。

23.2.3 事务处理的可选模型​

不是所有跨节点更新都需要 2PC 级别的原子性:

  • Saga:把长事务拆成一串本地事务 T1,T2,…,TnT_1, T_2, \ldots, T_n,每个 TiT_i 有对应的补偿事务 CiC_i。若中途失败,按逆序执行 CiC_i。语义为最终一致、可读到中间状态。
  • 补偿事务(compensating transaction):与 Saga 相同思路。
  • 可靠消息 + 幂等:写本地事务时同时把"下一步待做操作"入本地队列,异步投递给下一节点;接收方以幂等方式执行。这是微服务架构下最常见的模式。

选择原则:如果业务要求读已提交/可串行化,走 2PC;如果只要最终一致且可以接受补偿,走 Saga/可靠消息。


23.3 分布式数据库中的并发控制​

分布式并发控制在单机基础上加了一层:跨节点操作如何达成可串行化。

23.3.1 封锁协议​

分布式两阶段封锁(Distributed 2PL):每台节点各自维护本地锁表,一个事务在多台节点上分别持有锁;协调者负责在事务结束前不释放任何锁(严格 2PL)。

  • 中心锁管理器:全局单点,简单但性能瓶颈。
  • 分布式锁管理器:每个节点管自己数据的锁,锁请求就近处理;但死锁检测更复杂。

23.3.2 死锁处理​

分布式死锁可以跨节点形成:T1T_1 在节点 A 等 T2T_2,T2T_2 在节点 B 等 T1T_1。检测方法:

  • 等待图汇总:各节点周期性把本地等待图上报给中心,中心合并后寻找环。
  • 消息追踪:探测消息沿等待链传递,若消息回到起点则说明存在环。
  • 超时避免:不做主动检测,等待超过一定时间就中止事务;简单但可能误杀。
  • Wound-Wait / Wait-Die:基于事务时间戳打破死锁——老事务优先,年轻事务被迫等待或直接夭折。

23.3.3 租赁​

租赁(lease) 是"带时限的锁":主节点获得对某资源的租约,在 τ\tau 秒内独享写权限,τ\tau 秒后必须续租或让位。租赁常用于:

  • 主节点选举:拿到租约的节点是主。
  • 本地缓存:客户端缓存元数据一段时间,无需每次查询目录。
  • 避免脑裂:老主的租约到期前不允许新主写。

租赁的时钟依赖:需要各节点时钟不偏差过大(通常在租约期内 < 秒级)。

23.3.4 基于时间戳的分布式协议​

分布式时间戳排序(Distributed Timestamp Ordering,DTO):每个事务在开始时获得一个全局递增时间戳 TS(T)\text{TS}(T),所有节点按 TS\text{TS} 决定读写顺序。核心规则:

  • 读 xx 时,若 TS(T)<W-TS(x)\text{TS}(T) < W\text{-TS}(x),中止 TT;否则读并更新 R-TS(x)R\text{-TS}(x)。
  • 写 xx 时,若 TS(T)<R-TS(x)\text{TS}(T) < R\text{-TS}(x) 或 TS(T)<W-TS(x)\text{TS}(T) < W\text{-TS}(x),中止 TT;否则写并更新 W-TS(x)W\text{-TS}(x)。

不需要跨节点加锁,但需要一个全局时钟源。

23.3.5 时间戳的产生​

产生全局时间戳的方式:

  • 中心时间戳服务(TSO,Time-stamp Oracle):单点递增计数器,如 TiDB 的 PD。简单但可能成为瓶颈,需要批量分配。
  • Lamport 逻辑时钟:Li←max⁡(Li,Lj)+1L_i \leftarrow \max(L_i, L_j) + 1,保证因果顺序但不反映真实时间。
  • 向量时钟:Vi[j]V_i[j] 保存节点 ii 对节点 jj 已知的最新时刻,能检测并发关系但空间 O(N)O(N)。
  • 物理时钟 + 不确定性(TrueTime):Google Spanner 用 GPS + 原子钟为每台节点提供带界限的物理时间 [earliest,latest][\text{earliest}, \text{latest}],事务提交前commit-wait 至 latest\text{latest} 过去以保证外部一致性(external consistency)。
  • 混合逻辑时钟(HLC):物理时钟 + 逻辑计数器,兼具因果与近实时的优点。CockroachDB 使用 HLC。

23.3.6 分布式时间戳排序​

在多节点上并行执行 DTO 的关键:所有节点必须对同一事务使用同一 TS\text{TS},且能就"该 TS\text{TS} 之前的写都已可见"达成一致。工程上常用 TSO + WAL 复制 + commit-wait 组合。

23.3.7 分布式有效性检查​

乐观并发控制(OCC) 在分布式下的做法:

  1. 读阶段:事务在私有工作区读写,不加锁。
  2. 有效性检查阶段:提交前跨节点检查读写集是否与其他并发已提交事务冲突。
  3. 写阶段:无冲突则跨节点原子提交(2PC)。

FoundationDB、Percolator、Spanner 都属于 OCC 家族。冲突较少时性能极佳,冲突多时中止率升高。


23.4 复制​

复制在事务层引入两个新问题:多副本读写如何看起来像单副本(副本一致性)、副本故障与恢复。

23.4.1 副本一致性​

理想目标是强一致(linearizability):任何读能看到最近已提交的写。实现方式:

  • 主从复制(primary-backup):所有写走主节点,同步复制到副本;读可以走主或副本。
  • 多主复制(multi-master):多个副本都可写,需要冲突检测与合并。
  • 法定人数复制(quorum):读写各自要求多数派响应,配合版本号检测新旧。

23.4.2 使用副本的并发控制​

主流做法是**"逻辑上单副本、物理上多副本"**:

  • 每份数据的副本组内选出一个 leader,读写都由 leader 定序,再通过 Paxos/Raft 复制到 follower。
  • 跨副本组的事务由分布式提交协议(2PC)串起来。

这样并发控制只在 leader 上做,副本组内的复制不引入新的并发问题。

23.4.3 故障处理​

  • 副本宕机:leader 若失联,副本组用共识协议选新 leader;client 通过目录服务重新定位。
  • 协调者宕机:如前所述,用 Paxos 复制的日志避免 2PC 阻塞。
  • 网络分区:多数派侧继续服务,少数派侧对外只读或彻底停写(避免脑裂)。

23.4.4 重构和重组​

副本组的运维操作:

  • 副本重新配置:把某个失效副本替换为新节点,通过日志/快照初始化。
  • 成员变更(joint consensus):Raft/Paxos 中在过渡期同时用"新旧配置"投票,避免双主。
  • 数据再平衡:把分片从繁忙节点迁到空闲节点,同时保证服务不中断。

23.5 扩展的并发控制协议​

23.5.1 多版本 2PL 和全局一致性时间戳​

多版本 2PL(MV2PL) 在读写锁之上引入多版本:读事务读取一个一致性快照(对应某个提交时间戳),无需与写事务争锁;写事务仍走 2PL。这大幅减少了读写冲突。

要让快照对整个集群一致,需要一个全局一致性时间戳——每个事务的读版本、提交时间戳都由 TSO/TrueTime/HLC 统一分配。

23.5.2 分布式快照隔离​

分布式快照隔离(Distributed Snapshot Isolation) 提供:

  • 读:读事务开始时取一个全局 TSstart\text{TS}_{\text{start}},跨所有节点读该 TS\text{TS} 之前的最新版本。
  • 写:写事务提交时取 TScommit\text{TS}_{\text{commit}},与其他并发事务检查写-写冲突(first-committer wins)。

代表实现:

  • Percolator:Bigtable 之上的分布式快照隔离,使用中心 TSO + 每行的锁与写记录。
  • Spanner:TrueTime 提供全球外部一致性 + 快照隔离 + 可串行化。
  • CockroachDB:HLC + Raft,提供可串行化 SI。

需注意:SI 存在写偏斜(write skew),若需要严格可串行化,需引入 SSI(Serializable SI)。

23.5.3 联邦数据库系统中的并发控制​

联邦数据库跨越多个自治 DBMS,每个源有自己的并发控制。挑战:

  • 各源可能只提供本地可串行化,而不暴露锁 API;
  • 无法在源之间加全局锁。

常用手段是票据机制(ticket):在每个源引入一个"票据表",每个全局事务在源内更新其票据行,从而借用源的本地并发控制在全局层强加一次冲突。牺牲性能换取语义。


23.6 具有弱一致性级别的复制​

23.6.1 用一致性换取可用性​

CAP 定理(Brewer, 2000):在网络分区(P)发生时,系统只能在一致性 C 与可用性 A 中二选一:

  • CP 系统:分区时拒绝服务,保证不返回旧值。例:ZooKeeper、etcd、Spanner。
  • AP 系统:分区时继续服务,允许副本发散。例:DynamoDB(可配置)、Cassandra、Riak。
  • CA 系统(无分区):仅在假设网络永不分区的场景中成立,如单机 DB。

真实网络分区总会发生,因此 CP vs AP 是所有分布式数据库的核心取舍。进一步的 PACELC 定理指出:即使没有分区(E),仍要在延迟 L 与一致性 C 间取舍。

23.6.2 异步复制​

异步复制:主节点写完立即返回,副本在后台追齐。优点是延迟低、可用性高;代价是副本滞后导致的读旧值与主宕机丢数据。工业系统通常提供多档配置:

  • async(默认):最快,可能丢最近若干事务。
  • semi-sync:主等至少一个副本确认再返回。
  • sync:主等全部副本确认。

23.6.3 异步视图维护​

物化视图/派生表异步维护:基表事务提交后只写日志(如 CDC binlog),视图消费日志异步更新。

好处:写路径快,视图不阻塞事务;代价:视图与基表存在延迟差,读视图可能读到旧结果。

23.6.4 检测不一致性更新​

多主/异步复制中,同一行可能在不同副本被并发修改。检测手段:

  • 版本号:每次更新递增;读时比较版本判断新旧。
  • 向量时钟:能区分"并发修改" vs "先后修改"。DynamoDB 早期采用。
  • CRDT 元数据:数据类型自身携带合并信息。

23.6.5 解决冲突的更新​

冲突解决策略:

  • Last Writer Wins(LWW):按时间戳选最新,简单但可能丢更新。
  • 应用侧合并:读时把所有并发版本返回给应用,由应用合并(Riak sibling)。
  • CRDT(无冲突可复制数据类型):数据结构本身保证任意合并顺序都收敛,如 G-Counter、OR-Set、LWW-Register。

23.6.6 使用默克尔树来检测集合之间的差异​

反熵(anti-entropy) 用于周期性修复副本差异。若逐行比对代价过高,可用默克尔树(Merkle tree):

  • 把键空间分层切分;
  • 每个叶子节点是该键区间内所有值的散列;
  • 每个中间节点是其子节点散列的组合。

两副本比对时只交换根散列,若相等则完全一致,否则递归比较子节点,只到差异叶子处才交换实际数据。

Dynamo、Cassandra、Riak 均使用默克尔树做副本反熵;比特币等区块链系统也用它验证交易集合。


23.7 协调器的选择​

23.7.1 备份协调器​

传统 2PC 有单点协调器,一旦宕机将阻塞不确定态事务。改进方案:

  • 热备份协调器:主协调器把决定日志同步复制到备份;主宕机后备份接管。
  • 协调器日志外置:把日志放到分布式存储(Paxos/Raft 组),任何一台机器都可以在读取日志后接管。

23.7.2 选举协调器​

当现任协调器失联,需要一致地选出新协调器。经典选举算法:

  • Bully 算法:优先级最高的存活节点当选。当某节点检测到协调器宕机,它向所有更高优先级节点发起挑战;若无人应答则自宣当选。
  • Ring 算法:节点组成逻辑环,选举消息沿环传递,携带所有候选者 ID,最终最大 ID 胜出。
  • 基于共识的选举:把"当前协调器是谁"作为共识状态,通过 Paxos/Raft 达成一致。Raft 的 leader election 是这类方案的标准实现。

工业界普遍已抛弃 Bully/Ring,改用 Raft/Paxos 的 leader election——它把选举与日志复制统一在一个协议内。


23.8 分布式系统中的共识​

共识(consensus):让一组节点就某个值达成一致,即便存在故障与网络异常。它是所有可靠分布式系统的基石。

23.8.1 问题概述​

共识问题的形式化定义要求四个性质:

  1. 终止性(Termination):所有非故障节点最终决定某个值。
  2. 一致性(Agreement):所有非故障节点决定的值相同。
  3. 完整性(Integrity):决定值必须是某个节点提议过的。
  4. 有效性(Validity):若所有节点提议同一值 vv,则决定值就是 vv。

FLP 不可能定理:在完全异步网络下,只要有 1 个节点可能故障,就不存在既满足安全性又保证终止性的确定性共识协议。工程上通过部分同步假设(大部分时间网络正常)与随机化/超时来绕过。

23.8.2 Paxos 共识协议​

Paxos(Lamport, 1998)是最早的实用共识算法,节点分三种角色:

  • Proposer:提出提议值。
  • Acceptor:接受或拒绝提议。
  • Learner:学习最终被选定的值。

一次实例分两个阶段:

Phase 1 (prepare)

  1. Proposer 选一个全局递增编号 nn,向多数派 Acceptor 发送 PREPARE(n)。
  2. Acceptor 收到 PREPARE(n):若 nn 大于它见过的所有编号,回 PROMISE(n, v_{\text{prev}})——承诺不再接受 <n< n 的提议,并汇报此前已接受的最大编号提议值 vprevv_{\text{prev}}(若有);否则拒绝。

Phase 2 (accept) 3. Proposer 收到多数派的 PROMISE:若其中有 vprevv_{\text{prev}},则必须复用编号最高的 vprevv_{\text{prev}}(保证不覆盖已选定值),否则可用自己想提的值 vv。用 ACCEPT(n, v) 广播。 4. Acceptor 收到 ACCEPT(n, v):若未在此期间承诺过更高编号,则接受并持久化,回 ACCEPTED;否则拒绝。 5. 一旦多数派 Acceptor 接受了同一 (n,v)(n, v),vv 即被选定(chosen),Learner 学习之。

Paxos 的两大不变式:

  • P1:Acceptor 必须接受它收到的第一个 PREPARE(n)。
  • P2c:若某 (n,v)(n, v) 被选定,则所有更高编号的提议都必须使用 vv——由 Phase 1 的 PROMISE 回带 vprevv_{\text{prev}} 保证。

原始 Paxos 只能就单一值达成一致(Single-Decree Paxos)。实际系统需要Multi-Paxos:把一系列命令按序编号,每个位置跑一次 Paxos;由稳定 leader 跳过大量 Phase 1 以提升吞吐。

23.8.3 Raft 共识协议​

Raft(Ongaro & Ousterhout, 2014)以"可理解性"为设计目标,把共识拆成三个相对独立的子问题:领导选举、日志复制、安全性。

领导选举:

节点有三种状态:Follower、Candidate、Leader。任意时刻至多一个 Leader。

loop forever
case state
Follower:
if timeout without heartbeat:
state <- Candidate
Candidate:
currentTerm <- currentTerm + 1
votedFor <- self
向所有节点发 RequestVote(currentTerm, lastLogIndex, lastLogTerm)
if 收到多数派赞成: state <- Leader
elif 收到更新 term 的心跳: state <- Follower
elif 超时: 重新竞选
Leader:
周期性广播 AppendEntries 作为心跳

选举安全性:每个 term 内每个节点至多投一票,故至多一个 Candidate 拿到多数派——每个 term 至多一个 Leader。

日志复制:

Leader 收到客户端命令 cmd:
1. 追加 (term, cmd) 到本地日志
2. 并行向所有 Follower 发 AppendEntries(prevIdx, prevTerm, entries)
3. Follower 校验 prevIdx/prevTerm 与本地一致后追加,回 ACK
4. 当多数派 ACK, Leader 提交该 entry, 应用到状态机
5. 心跳中把 commitIndex 带给 Follower, 让其也提交

AppendEntries 一致性检查保证:若 Leader 与 Follower 在同一 (index, term) 处的 entry 相同,则之前的所有 entry 也都相同——这个不变式让日志修复变得简单,Leader 只需回退 nextIndex[Follower] 直到匹配。

安全性(Log Matching + Leader Completeness):

  • Log Matching:不同节点的日志在相同 (index, term) 上必然内容相同。
  • Leader Completeness:一个已提交的 entry 必然出现在所有更高 term 的 Leader 日志中——由投票规则保证:Candidate 的日志必须至少与投票者一样"新"(比较 lastLogTerm、lastLogIndex)才能得票。

Raft 因此避免了 Paxos 中"提议值必须回带 vprevv_{\text{prev}}"的复杂性——新 Leader 必然已经包含所有已提交日志。

23.8.4 使用复制状态机的容错服务​

复制状态机(Replicated State Machine,RSM) 是共识协议最经典的应用:

  1. 把服务建模为确定性状态机:给定初始状态与相同命令序列,输出必然相同。
  2. 用共识协议(Paxos/Raft)复制命令日志到多个副本。
  3. 各副本按同一序列 apply 命令,状态自然收敛。

例子:

  • ZooKeeper(ZAB 协议,与 Raft 精神接近):分布式协调服务,元数据 + 分布式锁。
  • etcd(Raft):Kubernetes 的元数据库。
  • Spanner:每个分片的多副本用 Paxos 复制;跨分片用 2PC 串起。
  • CockroachDB / TiDB:底层用 Raft 复制 range,之上用 MVCC + 2PC。

23.8.5 使用共识的两阶段提交​

Paxos Commit(Gray & Lamport, 2006)把 2PC 与共识结合:

  • 每台参与者用一个 Paxos 组表决"这台参与者的投票是 READY 还是 ABORT"。
  • 事务的最终结果 = 所有参与者组投票的逻辑与。
  • 协调者的角色变成"读取所有 Paxos 组的决定并聚合",其本身不再是单点。

好处:任何单点宕机(协调者或参与者)都不阻塞提交——只要每个参与者组多数派存活即可。Spanner 的分布式事务、CockroachDB 的跨 range 事务都是这一模式的工业实现。

现代分布式数据库的通用架构可以总结为一张图:

总结要点:

  • 分布式事务的原子性由 2PC 保证,但传统 2PC 存在阻塞与单点问题;用Paxos/Raft 复制协调者日志解决。
  • 并发控制在分布式下依赖统一的时间戳/时钟(TSO、TrueTime、HLC),并配合 2PL/OCC/SI 多版本方案。
  • 复制层通过主-副本 + 共识做到"逻辑上单副本",事务层再叠加 2PC 处理多分片。
  • CAP 定理在分区发生时强迫系统在 C 与 A 之间取舍;CP 系统(Spanner/etcd)与 AP 系统(Cassandra/Dynamo)代表两条主流路线。
  • 共识协议(Paxos、Raft、ZAB)是所有强一致分布式系统的地基,Raft 通过 leader 选举/日志复制/安全性三段结构提升了可理解性并成为工业主流。
  • 现代分布式数据库(Spanner/CockroachDB/TiDB/YugabyteDB)的通用蓝图:范围分区 + Raft/Paxos 副本组 + 2PC 跨组事务 + MVCC 快照隔离——本章描述的所有机制共同支撑起这一体系。