四步搞定分布式事务数据库

• 执行交易事务 - 像跑程序一样把交易事务里的操作都做一遍
• 给交易事务排序 - 给每个交易事务发个"时间号码牌"
• 验证交易事务 - 检查这个交易事务会不会和别人打架
• 持久化交易事务 - 把结果永久存进硬盘

1. 执行事务
就像你玩游戏时要先操作角色移动、攻击一样，系统会把事务里的命令（比如读数据、改数据）都执行一遍。不同系统做法不同：

• 有的直接改数据库（像直接往本子上写字）
• 有的先记小本本，最后一起改（像草稿纸写完了再誊抄）

特殊情况下，一个事务可能要反复执行多次

2. 给事务排序
系统会给每个事务发个"时间号码牌"，用来确定谁先谁后。这个牌子可以是：

• 版本号（像作业本的"第3次修订版"）
• 时间戳（像"2023年9月1日14:00"）
• 日志序号（像食堂排队叫号）

MVCC数据库（比如MySQL）会发两个牌子：

• 读版本号（开始读数据时的号）
• 提交版本号（最终确定的号）

3. 验证事务
主要检查两件事：
(1) 会不会打架：比如两个事务同时改同一条数据（像两个同学同时改同一份作业）
(2) 是否守规矩：比如转账时不能出现负数余额
如果发现有冲突，就直接取消事务（类似老师没收打架同学的作业）

4. 持久化事务
就是把最终结果：

• 存进硬盘（像把作业存进档案袋）

可能还要复制到多台机器（像交作业时同时给课代表和班长各一份）

只有这步完成，系统才会告诉你"事务成功啦！"

举个栗子：
乐观锁系统（比如Git版本控制）：

• 先自由修改代码 →
• 提交时检查冲突 →
• 没冲突就存仓库

悲观锁系统（比如银行转账）：

• 先锁住账户 →
• 改金额 →
• 存盘 →
• 才解锁

为什么顺序可以调换？

• 就像做菜可以先切菜再开火，也可以先热锅再备菜：
• 先验证再排序：像体育课分组，先确认没人受伤再排比赛顺序
• 先排序再持久化：像发试卷时先学号排序，再统一登记分数

（关键点：这四步就像乐高积木，不同组合能搭出MySQL、Redis等各种数据库）

具体到每个不同数据库：
我们来快速过几个现实世界的例子。

1、FoundationDB
FoundationDB 是一个分布式的、支持事务的数据库，它把传统数据库架构拆成一堆可以独立扩展的微服务。论文里是这么描述它的事务处理流程的：
客户端开始一个事务时，会先联系一个代理（Proxy）来拿一个读版本（也就是时间戳）。代理会问序列器（Sequencer）要一个读版本，这个版本得保证不低于之前任何事务的提交版本。然后这个读版本会发回给客户端。客户端可以用这个读版本去存储服务器（StorageServers）读数据。客户端的写操作会先在本地存着，不用联系集群。到了提交的时候，客户端会把事务数据（包括读写集合，也就是键的范围）发给一个代理，等着代理说“提交成功”还是“取消”。如果事务没法提交，客户端可以选择从头再跑一遍。

代理提交客户端事务分三步：

1. 代理找序列器拿一个提交版本，这个版本得比所有已有的读版本或提交版本都大。序列器会以每秒一百万个版本的速度推进版本号。
2. 代理把事务信息发给按范围分区的解析器（Resolvers），它们用 FoundationDB 的乐观并发控制检查有没有读写冲突。如果所有解析器都说没冲突，事务就可以进入最后提交阶段。不然，代理就标记事务取消。
3. 提交的事务会被发到日志服务器（LogServers）永久保存。等所有指定的日志服务器都回复代理后，事务就算提交了。代理会把提交版本报给序列器（确保之后事务的读版本在这个提交之后），然后回复客户端。同时，存储服务器会不断从日志服务器拉取变更日志，把提交的更新写到磁盘上。

• 客户端执行事务。
• 代理拿到提交版本。
• 检查事务有没有冲突。
• 把事务永久保存。

FoundationDB 就是个经典的乐观并发控制数据库。所以如果你想搞懂系统某一部分（比如解析器里的分布式冲突检查），可以把其他部分暂时想象成最简单的乐观数据库实现（比如把日志服务器想象成只在一块磁盘上追加写日志）。

2、Spanner
Spanner 是 Google 的旗舰数据库，在 Google 内部用得很多，还启发了一堆 NewSQL 数据库跟着它的架构走。它的事务协议是这么描述的：
跟 Bigtable 一样，事务里的写操作会在客户端缓存，直到提交。所以事务里的读操作看不到自己写的效果。这种设计在 Spanner 里挺好用，因为读操作会返回数据的提交时间戳，而没提交的写操作还没被分配时间戳。

读写事务里的读操作用“伤等”（wound-wait）机制避免死锁。客户端会向对应分片的领导副本（leader replica）发读请求，领导副本会拿读锁，然后读最新数据。事务没完时，客户端会发“保活”消息，防止参与的领导副本超时。当客户端读完所有数据、缓存好所有写操作后，就开始两阶段提交。客户端会选一个协调者分片，把提交消息发给每个参与者的领导副本，消息里包括协调者的身份和缓存的写操作。让客户端驱动两阶段提交，可以避免数据跨广域网传两次。
非协调者的参与者领导副本会先拿写锁，然后选一个准备时间戳，这个时间戳得比它之前分配的所有时间戳都大（保持单调性），然后通过 Paxos 协议记一个准备日志。每个参与者会把准备时间戳通知协调者。

协调者领导副本也会先拿写锁，但跳过准备阶段。等收到所有参与者的准备时间戳后，它会为整个事务选一个提交时间戳。这个时间戳得满足：比所有准备时间戳大、比协调者收到提交消息时的“现在时间”大、比领导副本之前分配的所有时间戳大（还是为了单调性）。然后协调者通过 Paxos 记一个提交日志（如果等其他参与者超时了，就记取消日志）。

在允许协调者副本应用提交日志前，协调者领导副本会等到时间戳确认是“过去时间”，遵守提交等待规则。因为时间戳是基于“现在时间”选的，等待时间通常至少是 2 倍误差。这段等待通常跟 Paxos 通信重叠。提交等待后，协调者把提交时间戳发给客户端和其他参与者领导副本。每个参与者领导副本通过 Paxos 记事务结果。所有参与者在同一时间戳应用更新，然后释放锁。

分解步骤：

• 执行和验证混在一起，因为执行事务时会拿读锁。
• 写操作缓存到客户端准备提交。
• 两阶段提交开始，检查事务能不能在所有参与者上提交。
• 协调者收到所有参与者的最小时间戳后，决定最终提交版本。
• 事务被永久保存。
• 最后释放读写锁。

还是经典的悲观并发控制数据库的样子！虽然 Spanner 的事务执行解释复杂得多，但你可以从“它咋跟 SERIALIZABLE 的 MySQL 一样？”的角度去读论文，逐步思考两个系统哪儿不一样。

3、TAPIR
TAPIR 是个严格序列化的数据库，号称比 Spanner 更好，延迟更低、吞吐量更高，因为它用了新颖的复制协议。它的核心协议是这么描述的：

先说 TAPIR 怎么执行事务：

• 写操作（Write(key, object)）：客户端把键和对象缓存到写集合，直到提交时才处理，立即返回。
• 读操作（Read(key)）：如果键在写集合里，客户端从写集合返回对象。如果事务已经读过这个键，就返回缓存的副本。不然，客户端就把读请求发给副本。
• 副本收到读请求后，返回对象和版本，对象是键的最新版本，版本是写这个版本的事务时间戳。
• 客户端收到回复后，把（键，版本）放进读集合，然后把对象返回给应用。

提交时，TAPIR 客户端会协调所有参与者（负责读写集合里键的分片），找到一个跟严格序列顺序一致的时间戳，分配给事务的读写操作，流程如下：

• 客户端选一个建议时间戳。建议时间戳得唯一，所以用本地时间和客户端 ID 组成一个元组。
• 客户端通过 IR 共识操作调用 Prepare(txn, timestamp)，时间戳是建议时间戳，事务包括事务 ID 和读写集合。客户端在所有参与者上调用 Prepare。
• 收到 Prepare 的 TAPIR 副本先检查事务日志里有没有这个事务 ID。如果有，就返回 PREPARE-OK（如果事务提交了）或 ABORT（如果事务取消了）。
• 如果事务 ID 在准备列表里，也返回 PREPARE-OK。
• 不然，副本会跑 TAPIR 的乐观并发控制验证，检查读写集合在时间戳下有没有冲突。
• 客户端收到所有分片的回复后，如果所有分片都回 PREPARE-OK，就发 Commit(txn, timestamp)；如果有分片回 ABORT 或 ABSTAIN，就发 Abort(txn, timestamp)。如果有分片回 RETRY，客户端就用新时间戳重试（有重试次数限制）。
• 收到 Commit 的副本会：（1）把事务提交到日志，（2）用写集合更新版本存储，（3）从准备列表移除事务（如果有），（4）回复客户端。
• 收到 Abort 的副本会：（1）记取消日志，（2）从准备列表移除事务（如果有），（3）回复客户端。

• 执行事务。
• 客户端选一个建议提交时间戳。
• 每个副本并发跑乐观并发控制检查，并把数据存到准备日志。

这也突出了 TAPIR 的关键点：它把并发控制验证和提交结果保存协议混在一起了。

4、Calvin
Calvin 是确定性数据库的标志性系统，后来改进它设计的论文都保留了相似的特点。Calvin 的架构是这么介绍的：
Calvin 的核心是把系统分成三个独立处理层：

• 序列层（Sequencer）：拦截事务输入，把它们放进一个全局事务输入序列，这个序列就是事务的执行顺序，所有副本都会保证跟这个顺序等价。序列器还负责复制和记录这个输入序列。
• 调度层（Scheduler）：用确定性锁方案协调事务执行，保证跟序列层指定的序列顺序等价，同时允许事务被一堆执行线程并发跑。（虽然图里执行线程画在调度器下面，但它们属于调度层。）
• 存储层：处理所有物理数据布局。Calvin 的事务用简单的 CRUD 接口访问数据，任何支持类似接口的存储引擎都能轻松接入 Calvin。

• 把事务排进全局日志。
• 把日志永久保存。
• 拿锁，确保能在序列顺序安全执行，即使有并发。
• 执行事务。
• 释放所有拿到的锁。

Calvin 是最有名的例子，它在提交事务前不执行事务。这带来了一些大优势，比如提交过程完全不受工作负载竞争的影响；也有缺点，比如长事务会卡住后面提交的事务执行。

5、CURP
《利用可交换性实现实用快速复制》定义了一个一致无序复制协议（CURP），允许客户端复制还没排序的请求，只要这些请求是可交换的。它的正常操作是这么描述的：

客户端跟主节点的交互跟没用 CURP 时差不多。客户端把更新 RPC 请求发给主节点。如果没收到回复，客户端会重试。如果主节点挂了，客户端会换个服务器重试。

对于 1 RTT（一往返）的更新，主节点在复制到备份前就回复客户端。为了确保持久性，客户端会在等待主节点回复时，直接并发地把请求记录到见证者（witnesses）。等所有 f 个见证者都接受了请求，客户端就确信请求能扛住主节点崩溃，于是用主节点的回复完成操作。

见证者只接受客户端的新记录 RPC，如果新操作跟见证者当前保存的所有操作可交换。如果新请求跟某个已有请求不可交换，见证者得拒绝，因为它没法给两个不可交换的操作定顺序。比如，如果见证者已经接受了“x←1”，就不能接受“x←5”。

每个 f 个见证者独立操作，见证者不用在操作的顺序或持久性上达成一致。在异步网络里，记录 RPC 可能以不同顺序到达见证者，导致见证者接受或拒绝不同的操作集合。但这不影响一致性。因为：（1）客户端只有在所有 f 个见证者接受记录 RPC 后，才会继续而不等备份同步；（2）每个见证者的请求得独立可交换，恢复时只选一个见证者

CURP 里主节点的角色跟传统主备复制差不多。主节点接收、序列化、执行所有客户端的更新 RPC 请求。如果执行的操作更新了系统状态，主节点会通过复制更新值或有序操作日志，跟备份同步状态。

分解步骤：

• 客户端从主节点读数据，把写操作发给领导者和复制组的所有跟随者。
• 每个副本并发检查冲突，并在本地记录事务。
• 回复客户端后，事务才被排序。

这也清楚地展示了 CURP 的独特之处：排序事务是它最后做的事，排序放最后是它所有优势的来源。

6、TicToc
TicToc 介绍了一种新的事务协议，给数据项分配读写时间戳，懒惰地算出每个事务的合法提交时间戳。这样就不用集中分配时间戳，还能提交一些传统时间戳排序方案会取消的事务。

听起来很酷。把协议规格的描述拼起来，事务协议是这样的：
在读阶段，数据库为每个事务维护单独的读集合和写集合。执行时，访问的元组（tuple）会被复制到读集合，修改的元组写到写集合，只对当前事务可见。读写集合的每个条目编码为 {元组, 数据, 写时间戳, 读时间戳}，元组是数据库里元组的指针，数据是元组的值，写时间戳和读时间戳是事务访问元组时从元组复制的。对于读集合条目，TicToc 保持不变性：版本在写时间戳到读时间戳之间有效。

验证阶段第一步是按主键顺序锁住写集合里的所有元组，防止其他事务并发更新。固定锁顺序保证不会跟其他同时提交的事务死锁。

验证阶段第二步是从读写集合里每个元组条目的时间戳算出事务的提交时间戳。对于只在读集合、不在写集合的元组，提交时间戳得不少于它的写时间戳，因为在这之前元组会有不同版本。对于写集合的元组，提交时间戳得不少于当前读时间戳 + 1，因为之前版本到读时间戳都有效。

最后一步是验证读集合里的元组。如果事务的提交时间戳小于或等于读集合条目的读时间戳，说明不变性（写时间戳 ≤ 提交时间戳 ≤ 读时间戳）成立，元组版本在提交时间戳有效，不用再处理。如果条目的读时间戳小于提交时间戳，就不清楚本地值在提交时间戳是否还有效。可能有其他事务在本地读时间戳和提交时间戳之间改了元组，这时事务得取消。如果没被改，读时间戳可以扩展到大于或等于提交时间戳，让版本在提交时间戳有效。

如果事务访问的所有元组都通过验证，事务进入写阶段，把写集合写入数据库。

分解步骤：

• 执行事务，写操作缓存到提交。
• 执行时记录时间戳，缩小可能的提交版本范围。
• 开始验证时，选最终提交时间戳，检查冲突。
• 如果前面步骤都成功，事务被永久保存。

TicToc 做动态时间戳分配。它不是在执行前选时间戳，也不是在提交前建议时间戳，而是在执行时不断缩小可能的提交时间戳范围。

总之：
从所有可能的排序和并发执行步骤集合来看，至少有 74 种不同类型的数据库。我们只介绍了其中的几种，但每种数据库都因其不同的事务处理步骤排序而衍生出一些有趣的特性。您是否正在寻找一个新颖的事务系统来构建和发布相关内容？找到一种文献中尚未深入探讨过的排序，设计一个以这种方式执行事务的系统，然后找出它的独特优势和劣势。