拆解事务型系统（Decomposing Transactional Systems）

1. 执行事务（execute）

2. 排序事务（order）

3. 验证事务（validate）

4. 持久化事务（persist）

执行事务

• 写操作可以在这一阶段立即落到存储，也可以先缓存在本地，最后一次性提交。

• 同一个事务出于不同目的可能被执行不止一次。

排序事务

• 可能是版本号、时间戳、日志序列号（LSN），或者更复杂的“先后发生”描述。

• MVCC 数据库通常会给出两个版本：初始读版本和最终提交版本。

• 这里我们主要关注选择提交版本的那个时刻——数据库宣称所有读写在此刻原子性地发生。

验证事务

• 如果事务因为系统定义的原因（例如与现有事务存在可串行化冲突）而需要被拒绝，就在此阶段发生。

• 若验证发生在排序之后，它会检查分配的顺序是否仍然有效；

• 若验证发生在排序之前，它会给出一系列可接受的提交版本，由排序阶段最终选定一个。

持久化事务

• 有些系统在执行过程中就会逐步把写操作刷盘；

• 关键点在于：所有写操作以及标记事务已提交的提交记录都完成持久化时，事务才算真正耐久。

• 这一阶段常与系统的复制机制和原子提交协议挂钩，两者界线有时并不清晰。

例子（Examples）

经典 OCC 的步骤拆解

OCC │ Execute │ Order │ Validate │ Persist │

经典 PCC 的步骤拆解 [1]

PCC │ Execute │───────────────Validate───────────────│ Order │ Persist │

➔ FoundationDB

客户端 首先联系集群中的某个 Proxy 以获得读版本（即时间戳）。Proxy 随后向 Sequencer 请求一个读版本，该版本保证不小于之前任何已发放的事务提交版本，并将该读版本返回给客户端。客户端随后可使用该读版本向 StorageServer 发起多次只读请求，获取该版本下的数据。事务期间产生的写操作在本地缓冲，无需再联系集群。提交阶段：客户端将读写集合（即键范围）连同写操作一起发送给某个 Proxy，等待 commit 或 abort 的回复。如果事务无法提交，客户端可能选择从头重试。

Proxy 以三步提交事务：向 Sequencer 申请一个大于所有现存读/提交版本的 提交版本（Sequencer 以每秒一百万的速率递增）。将事务信息发送给分片的 Resolver，使用 FoundationDB 的乐观并发控制算法检测读写冲突。若所有 Resolver 均返回 无冲突，事务继续；否则标记为 abort。对于已确认提交的事务，将其发送给一组 LogServer 进行持久化。当所有指定的 LogServer 回复成功后：Proxy 将 已提交版本 报告给 Sequencer（确保后续事务的读版本在此之后），并回复客户端。同时，StorageServer 持续从 LogServer 拉取变更日志并将已提交的更新写入磁盘。

1. 客户端执行 事务。

2. Proxy 获取 提交版本。

3. Resolver 进行 冲突检测。

4. 事务被持久化。

FoundationDB 的步骤拆解

FoundationDB │ Execute │ Order │ Validate │ Persist │

➔ Spanner

执行 / 验证

• 和 Bigtable 类似，事务中的写操作在客户端缓冲，直到提交才发送。

• 因此，事务内的读看不到自己写入的内容。

• 读操作期间，客户端向相应数据分片的领导副本发起请求；领导副本获取读锁后返回最新数据。

• 事务打开期间，客户端会定期发送 keep‑alive，防止参与分片超时。

• 当客户端完成所有读且写缓冲完毕后，就启动两阶段提交：选择一个协调者分片，将「协调者身份 + 缓冲写集」发送给每个参与分片的领导者。由客户端驱动 2PC 避免了跨广域网重复传输数据。

排序（prepare / commit 决议）

• 参与分片（非协调者）：
1. 先获取写锁；
2. 选择一个 prepare 时间戳（须大于该分片之前发出的所有时间戳以保持单调性）；
3. 通过 Paxos 记录 prepare；
4. 将该 prepare 时间戳汇报给协调者。

• 协调者分片：
1. 同样先获取写锁，但跳过 prepare 阶段；
2. 在收到所有参与者的 prepare 时间戳后，选择全局 commit 时间戳 s，要求
• s ≥ 所有 prepare 时间戳，
• s > TT.now().latest（协调者收到 commit 消息时的物理时间上界），
• s > 协调者此前分配给其他事务的任何时间戳；
3. 通过 Paxos 记录 commit（或在等待参与者超时后记录 abort）。

验证（commit‑wait 规则）

• 任何协调者副本在真正应用 commit 前，都会等待到 TT.after(s)，以满足论文 §4.1.2 的 commit‑wait 规则；预计等待 ≥ 2 ε，通常与 Paxos 通信并行。

• 之后，协调者把 commit 时间戳发送给客户端及所有参与者；各参与者通过 Paxos 记录结果并在同一时间戳应用写入，然后释放锁。

作者拆解

1. 执行与验证交织：读锁在执行阶段即被持有。

2. 写操作在客户端缓冲，等提交时再发送。

3. 发起 2PC，检查所有参与者是否可提交。

4. 协调者在 prepare 阶段收齐最小必要时间戳后，决定最终 commit 版本。

5. 事务被持久化。

6. 最后释放读写锁。

Spanner 的流程示意

Spanner │───────── Validate ─────────│

│ Execute │ Order │ Persist │

➔ TAPIR

事务执行（Execute）

1. Write(key, object)
客户端将 key 和 object 暂存在写集合（write set）中，直到提交才发送，操作立即返回。

2. Read(key)
• 如果 key 已在事务的写集合中，客户端直接返回写集合中的 object；
• 如果此次事务之前已读过该 key，返回缓存的结果；
• 否则，客户端向某个副本发送 Read(key) 请求。

3. 副本响应
收到 Read 后，副本返回对应的 object 及其版本号 version（version 是写入该版本的事务的时间戳）。

4. 客户端处理
客户端收到响应后，将 (key, version) 加入事务的读集合（read set），并将 object 返回给应用层。

排序与校验（Order & Validate）

1. 选取候选时间戳
客户端生成一个提议时间戳（timestamp），为保证全局唯一，通常使用本地时钟与客户端 ID 的元组。

2. Prepare 共识
客户端通过 IR（一致性复制层）向所有分片并发发起 Prepare(txn, timestamp)，其中 txn 包含事务 ID、读集合和写集合。

3. 副本处理 Prepare
• 若事务日志已存在该 txn.id，则返回 PREPARE-OK（若事务已提交）或 ABORT（若已中止）；
• 否则，若 txn.id 已在本地的 prepared 列表中，也返回 PREPARE-OK；
• 否则，副本执行 TAPIR 的 OCC 校验，检测读写集合在该 timestamp 下的冲突（详见论文图 8）。

4. 汇总结果
• 若所有分片均回复 PREPARE-OK，客户端发送 Commit(txn, timestamp)；
• 若任一分片回复 ABORT 或 ABSTAIN，客户端发送 Abort(txn, timestamp)；
• 若有分片回复 RETRY，客户端更换时间戳重试（限制重试次数）。

持久化与完成（Persist）

• Commit 接收
分片收到 Commit 后：
1. 将事务记录写入本地事务日志；
2. 在版本化存储中应用写集合；
3. 从 prepared 列表移除该事务（如存在）；
4. 向客户端回应完成。

• Abort 接收
分片收到 Abort 后：
1. 记录中止日志；
2. 从 prepared 列表移除该事务（如存在）；
3. 向客户端回应完成。

1. 执行事务

2. 客户端选取提交时间戳并运行 Prepare

3. 各分片并行执行 OCC 校验并持久化到 prepare 日志

➔ Calvin

Calvin 的核心在于将系统分为三个独立的处理层

1. 排序层（Sequencer）：截获事务输入，将其放入全局事务输入序列——该序列即所有副本在执行时必须保持的事务顺序。排序层同时负责该输入序列的复制和日志记录。

2. 调度层（Scheduler）：使用确定性锁机制，按照排序层给定的全局顺序调度事务执行，同时借助一组执行线程实现并发执行。（虽然在图 1 中这些执行线程绘制在调度器组件下方，但在逻辑上它们属于调度层。）

3. 存储层（Storage）：负责所有物理数据布局。Calvin 事务通过简单的 CRUD 接口访问数据；任何支持相同接口的存储引擎都可方便地插入到 Calvin 中。

1. 将事务按序写入全局日志。

2. 将该日志持久化。

3. 获取锁，以在并发环境中确保按全局顺序安全执行。

4. 执行事务。

5. 释放所有已获取的锁。

Calvin 的步骤拆解图

Calvin │ Order │ Persist │ Validate │ Execute │

• 提交阶段完全免疫于并发竞争，延迟和吞吐表现稳定；

• 同时也带来缺点：长事务会阻塞后续所有已提交事务的执行。

➔ CURP

1. 客户端–主节点交互
客户端向主节点（masters）发送更新 RPC 请求。如未收到响应则重试；若主节点宕机，可向其他服务器重试。

2. 1 RTT 更新与持久化保证
为了实现 1 RTT 更新，主节点会在将数据复制到备份前就回复客户端。与此同时，客户端在等待主节点响应时，会并行地将该请求记录到 f 个见证者（witnesses）上。只有当所有 f 个见证者都接受后，客户端才确认该请求可以抵抗主节点宕机，然后才用主节点返回的结果完成操作。

3. 见证者的冲突校验
见证者仅在新请求与其已保存的所有操作可交换时，才接受客户端的 record RPC；若不可交换，见证者因无法保证与主节点执行顺序一致，就会拒绝该 RPC。例如，若见证者已接受 x←1，则不能接受 x←5。

4. 见证者的独立性
每个见证者独立运行，无需就操作的顺序或持久性达成一致。即使在异步网络中，RPC 到不同见证者的先后顺序各异，也不会破坏一致性：
• 如 §3.2.1 所述，客户端只有在所有 f 个见证者均接受其 record RPC 后，才能跳过与备份的同步；
• 每个见证者都只保证自身保存的操作可交换，且恢复时仅需选用其中一个见证者（§3.3）。

5. 主节点的传统角色
在 CURP 中，主节点（masters）与传统主备复制一致：接收、串行化并执行所有更新 RPC；如果操作更新了系统状态，主节点再将更新后的值或已排序操作日志同步（sync）给备份。

1. 客户端从主节点读取数据，并将写操作同时发送给复制组的领导者和所有追随者。

2. 各副本并行执行冲突检测，并将事务记录到本地。

3. 向客户端回复后，最后完成事务排序。

CURP 的步骤拆解

CURP │ Execute │ Validate │ Persist │ Order │

➔ TicToc

• 它为每个数据项分配读时间戳（rts）和写时间戳（wts），

• 并利用这两组时间戳来延迟计算事务的最终提交时间戳。

1. 不需要集中式地分配时间戳；

2. 能够提交那些传统时间戳排序方案会因为冲突而中止的事务。

协议流程（节选自 §3.2）

1. 执行阶段（Execute）
• 在读阶段，DBMS 为每个事务维护读集合(read set)和写集合(write set)。
• 访问过的数据项：
• 将其拷贝到读集合；
• 若被修改，则写到写集合。
• 读／写集合中的每条记录均编码为 (tuple, data, wts, rts)：
• tuple：指向数据库中该元组的指针；
• data：元组的值；
• wts、rts：分别是事务首次写入或读取该元组时所见版本的时间戳。
• 对于读集合条目，TicToc 保证 wts ≤ rts，即该条目在 [wts, rts] 时间段内对本事务可见。

2. 排序阶段（Order）
• 验证阶段第一步：按照主键顺序对写集合中的所有元组加锁，以防其他并发事务更新同一行。
• 这种固定的加锁顺序可保证与其他同时提交的事务之间不会产生死锁。

3. 验证与排序（Validate & Order）
• 验证阶段第二步：根据读／写集合中已存的时间戳，计算提交时间戳 (commit_ts)：
• 对于只在读集合中出现的元组，commit_ts ≥ wts，以保证该元组版本在 commit_ts 时依然有效；
• 对于写集合中的元组，commit_ts ≥ (previous rts + 1)，以维护时间戳单调递增。

4. 持久化阶段（Persist）
• 验证阶段最后一步：对读集合再做一次检查——若 commit_ts ≤ rts，说明读到的版本在 commit_ts 时依然有效；
• 否则，该事务必须中止；或（若没有冲突）可将读集合中相应条目的 rts 延展到 commit_ts，使其在 commit_ts 时合法。
• 通过所有验证后，事务进入写入阶段：将写集合中的所有更新持久化到数据库。

简化拆解

1. 执行事务，并将写操作缓冲到本地。

2. 执行期间记录每个元组的 wts/rts，逐步收窄可选的 commit_ts 区间。

3. 验证开始时，选择一个最靠前仍合法的 commit_ts，检查是否有冲突。

4. 验证通过后，将写入应用并持久化。

TicToc 的四步示意图

TicToc │ Execute │──────── Validate ────────│ Persist │

│Order_│

作业（Homework）

• Ocean Vista：Gossip‑Based Visibility Control for Speedy Geo‑Distributed Transactions

• Chardonnay：Fast and General Datacenter Transactions for On‑Disk Databases

• Warp：Lightweight Multi‑Key Transactions for Key‑Value Stores

• ROCOCO：Extracting More Concurrency from Distributed Transactions

• Granola：Low‑Overhead Distributed Transaction Coordination

• CockroachDB：The Resilient Geo‑Distributed SQL Database
• 建议先从 CockroachDB 的事务层文档入手，之后再作为后续步骤研究其并行提交（parallel commit）和读重启（read restart）优化。

• Aurora DSQL

• Firebolt

构造事务系统（Composing Transactional Systems）

1. 任选一种你“编造”的执行（execute）、排序（order）、验证（validate）、持久化（persist）这四步的排列或交错方式，画出对应的图示；

2. 然后回答：我需要如何设计一个数据库，才能让它恰好分解成这个图示？

• 找到一个文献里尚未充分探索过的步骤顺序；

• 设计一个按该方式执行事务的系统；

• 然后分析它在性能和语义上的优缺点。