【分布式系统百科】Calvin 与确定性事务：另一条路

在分布式事务处理领域，2012 年是极为特殊的一年。这一年，Google 发表了著名的 Spanner 论文，展示了如何通过 TrueTime API 和原子钟实现全球范围内的强一致性事务。同年，耶鲁大学的 Daniel Abadi 和 Alexander Thomson 在 SIGMOD 上发表了 Calvin 论文，提出了一个完全不同的技术路线：确定性事务处理（Deterministic Transaction Processing）。两篇论文几乎同时问世，却代表了两种截然不同的设计哲学——一个依赖硬件和精确时间同步，另一个则是纯软件方案，通过预先排序和确定性执行来避免分布式协调的复杂性。

Calvin 的出现并非偶然。传统的分布式事务处理方案，如两阶段提交（Two-Phase Commit，2PC），虽然能够保证 ACID 特性，但存在显著的性能问题。2PC 需要多轮网络通信，协调者（Coordinator）与参与者（Participant）之间的消息往返会引入高延迟。更严重的是，2PC 在协调者故障时会出现阻塞问题，参与者必须等待协调者恢复才能完成事务，这在广域网环境下尤其致命。此外，传统方案中的并发控制机制，如两阶段锁（Two-Phase Locking，2PL）或时间戳排序（Timestamp Ordering），在分布式环境下容易产生死锁，死锁检测本身又需要额外的分布式协调开销。

Calvin 的核心洞察是：如果我们能够预先确定事务的执行顺序，并且保证在所有副本上以完全相同的顺序执行相同的事务，那么就可以避免大部分分布式协调的复杂性。这种确定性执行（Deterministic Execution）的思想看似简单，但其背后蕴含着深刻的技术洞察和严格的前提条件。本文将深入探讨 Calvin 的设计原理、与其他系统的比较、实际应用案例以及这一技术路线的局限性。

一、确定性执行的核心思想

确定性执行的基本原理可以用一句话概括：给定相同的输入和相同的初始状态，系统总是产生相同的输出和最终状态。在分布式事务的上下文中，这意味着如果所有副本以相同的顺序执行相同的事务，它们最终会达到相同的状态，而无需额外的协调。

这与传统的非确定性执行（Non-Deterministic Execution）形成了鲜明对比。在传统系统中，事务的执行顺序通常是动态决定的，取决于锁的获取顺序、网络延迟、线程调度等不确定因素。假设有两个事务 T1 和T2 同时访问同一数据项，在不同的副本上，它们可能以不同的顺序执行——一个副本可能先执行 T1，另一个副本可能先执行 T2。为了保证最终一致性，系统必须通过复杂的协调机制（如 2PC）来解决冲突。

Calvin 通过引入一个全局的顺序器（Sequencer）来消除这种不确定性。所有事务在执行之前，都会被 Sequencer 赋予一个全局唯一的序列号。这个序列号确定了事务在所有副本上的执行顺序。无论网络延迟如何变化，无论线程如何调度，所有副本都严格按照这个序列号的顺序来执行事务。

确定性执行带来的最大好处是消除了分布式死锁。在传统的 2PL 中，死锁是一个严重问题。例如，T1 持有资源 A 的锁并等待资源 B，而 T2 持有资源 B 的锁并等待资源 A，这就形成了死锁。在分布式环境下，检测和解决死锁需要全局信息，代价高昂。但在 Calvin 中，由于所有事务按预定顺序执行，如果 T1 在序列中排在 T2 之前，那么 T1 总是先获取所有需要的锁，T2 只能等待。这种严格的顺序保证了不会出现循环等待，从而从根本上避免了死锁。

确定性执行还简化了副本之间的同步。在传统系统中，主副本执行事务并产生结果，然后将结果或操作日志复制到从副本。从副本需要以某种方式重放这些操作以达到相同的状态。如果操作的执行是不确定的（例如，依赖于当前时间戳或随机数），从副本可能无法准确重现主副本的状态。Calvin 通过确保执行的确定性，使得副本只需要知道事务的输入和执行顺序，就能够独立地计算出相同的结果。

然而，确定性执行并非银弹。它的核心约束是：系统必须在事务执行之前就知道事务将要访问的所有数据项。这个前提条件对很多应用场景来说是一个重大限制，我们将在下一节详细讨论。

二、读写集预知：Calvin 的关键约束

Calvin 的确定性执行模型建立在一个关键前提之上：事务必须提前声明其读写集（Read Set 和 Write Set）。读写集是指事务将要读取和写入的所有数据项的集合。这个信息必须在事务开始执行之前就确定下来，并提交给 Sequencer。

为什么这个前提如此重要？因为 Calvin 的调度器（Scheduler）需要根据读写集来决定锁的分配。如果两个事务的读写集没有交集，它们可以并行执行；如果有交集，则必须按照 Sequencer 给定的顺序串行执行。这个决策过程必须在实际执行事务逻辑之前完成。如果事务在执行过程中才发现需要访问额外的数据项，整个确定性假设就会被打破。

这个约束排除了许多常见的事务模式。例如，考虑以下事务逻辑：

def transfer_with_fee(from_account, to_account, amount):
    balance = read(from_account)
    if balance >= amount:
        fee_rate = read_fee_rate(from_account)  # 根据账户类型读取费率表
        actual_amount = amount * (1 + fee_rate)
        write(from_account, balance - actual_amount)
        write(to_account, read(to_account) + amount)
        write(fee_account, read(fee_account) + actual_amount - amount)

在这个例子中，事务需要访问哪个费率表项取决于账户的类型，而账户类型只有在读取了 from_account 之后才能确定。这种依赖于数据的读取模式（Data-Dependent Reads）在 Calvin 中是不被支持的。

为了应对这个限制，Calvin 论文提出了侦察查询（Reconnaissance Query）技术。基本思路是将事务分为两个阶段：第一阶段执行只读的侦察查询，确定事务的完整读写集；第二阶段将读写集和实际的事务逻辑一起提交给 Sequencer。例如：

# 阶段 1：侦察查询
def reconnaissance(from_account, to_account, amount):
    balance = read(from_account)
    fee_rate = read_fee_rate(from_account)
    # 返回读写集
    return {
        'read_set': [from_account, fee_rate_key, to_account, fee_account],
        'write_set': [from_account, to_account, fee_account]
    }

# 阶段 2：确定性执行
def execute_with_read_write_set(read_write_set, from_account, to_account, amount):
    # 现在可以按照预定的读写集执行
    pass

侦察查询看似解决了问题，但它引入了额外的延迟和复杂性。而且，侦察查询本身必须是只读的，否则会产生副作用。如果数据在侦察查询和实际执行之间发生了变化，事务可能会基于过时的信息做出决策。

哪些工作负载适合 Calvin 的模型？主要是那些读写模式可预测的场景：

1. 键值存储操作：简单的 GET、PUT、DELETE 操作，读写集在 API 调用时就已明确。
2. 预定义的存储过程：事务逻辑固定，读写集可以通过静态分析确定。
3. 批处理任务：例如，对特定范围内的所有记录进行更新，读写集在批处理开始前就已知。

不适合的场景包括：

1. 复杂的交互式事务：用户输入驱动的多步骤事务，每一步依赖前一步的结果。
2. 图遍历：从一个节点开始，根据边的属性决定下一步访问哪些节点。
3. 条件复杂的业务逻辑：需要根据多个条件动态决定访问哪些表和记录。

这个约束使得 Calvin 在实际应用中的适用范围受到了一定限制。然而，对于那些确实能够预先确定读写集的应用，Calvin 提供了出色的性能和可扩展性。

三、三层架构：Sequencer、Scheduler 与 Execution

Calvin 的系统架构由三个主要层次组成，每一层都承担着明确的职责。这种分层设计使得系统的各个组件可以独立优化和扩展。

3.1 Sequencer 层：全局排序与批处理

Sequencer 是 Calvin 架构的核心。它的主要职责是为所有传入的事务请求分配全局唯一的序列号，并将这些序列号广播给所有副本。这个序列号定义了事务的执行顺序。

Sequencer 采用批处理（Batching）机制来提高效率。系统以固定的时间间隔（论文中建议 10 毫秒）为一个 epoch，将该时间窗口内到达的所有事务打包成一个批次（Batch）。批次内的事务被赋予相同的 epoch 编号，但有不同的批内序号。这种批处理有几个好处：

1. 摊销网络开销：一次网络通信可以传输多个事务的序列信息，减少了网络往返次数。
2. 提高吞吐量：批处理允许系统在同一个 epoch 内并行处理多个不冲突的事务。
3. 简化复制：整个批次可以作为一个单元进行复制，简化了容错机制。

Sequencer 的容错机制基于异步复制。系统通常部署多个 Sequencer 副本，主 Sequencer 负责生成序列号，并将批次信息异步复制到备份 Sequencer。如果主 Sequencer 故障，备份可以接管并继续分配序列号。由于确定性执行的特性，只要所有副本都按照相同的顺序处理相同的批次，系统的状态就会保持一致。

需要注意的是，Sequencer 并不执行任何事务逻辑，它只是一个排序服务。这使得 Sequencer 可以非常轻量级和高效。在实践中，一个 Sequencer 可以支持极高的吞吐量。

3.2 Scheduler 层：确定性锁管理

Scheduler 接收来自 Sequencer 的事务批次，并负责锁管理和调度。与传统的锁管理器不同，Calvin 的 Scheduler 是完全确定性的——它严格按照 Sequencer 给定的顺序来分配锁。

Scheduler 为每个数据项维护一个锁队列。当事务到达时，Scheduler 根据事务的读写集，将事务加入到相应数据项的锁队列中。锁的授予遵循以下规则：

1. 严格按序列号顺序：序列号小的事务优先获得锁。
2. 读写锁语义：多个读锁可以同时持有，写锁是排他的。
3. 无死锁：由于锁的分配顺序是全局确定的，不会出现循环等待。

考虑以下示例：

Batch 1:
  T1: read(A), write(B)  [seq=1]
  T2: read(B), write(C)  [seq=2]
  T3: write(A), read(C)  [seq=3]

锁队列状态：
  A: [T1(read, seq=1), T3(write, seq=3)]
  B: [T1(write, seq=1), T2(read, seq=2)]
  C: [T2(write, seq=2), T3(read, seq=3)]

执行流程：
1. T1 获取 A 的读锁和 B 的写锁，开始执行
2. T2 等待 T1 释放 B 的写锁
3. T3 等待 T1 释放 A 的读锁
4. T1 完成后，释放所有锁
5. T2 获取 B 的读锁和 C 的写锁，开始执行
6. T3 继续等待（A 的锁已释放，但 C 的锁被 T2 持有）
7. T2 完成后，T3 获取 A 的写锁和 C 的读锁，执行

这个过程完全是确定性的。无论系统负载如何变化，无论网络延迟多大，这三个事务的执行顺序总是 T1 → T2 → T3。

下图展示了单个数据键上锁队列的工作机制：

flowchart TD
    subgraph LQ["数据键 K 的锁队列"]
        direction TB
        H["队列头部"] --> TXN1["txn1 (seq=3)\n写锁 - 持有中"]
        TXN1 --> TXN3["txn3 (seq=8)\n读锁 - 等待"]
        TXN3 --> TXN7["txn7 (seq=15)\n写锁 - 等待"]
    end

    TXN1 -- "执行完成" --> RELEASE["释放写锁"]
    RELEASE -- "授予下一个" --> GRANT["txn3 获得读锁"]
    GRANT -- "执行完成" --> RELEASE2["释放读锁"]
    RELEASE2 -- "授予下一个" --> GRANT2["txn7 获得写锁"]

    style H fill:#4a90d9,color:#fff
    style TXN1 fill:#e74c3c,color:#fff
    style TXN3 fill:#f39c12,color:#fff
    style TXN7 fill:#f39c12,color:#fff
    style RELEASE fill:#27ae60,color:#fff
    style GRANT fill:#27ae60,color:#fff
    style RELEASE2 fill:#27ae60,color:#fff
    style GRANT2 fill:#27ae60,color:#fff

每个数据键维护一个按序列号严格排序的锁请求队列。队列头部的事务持有锁并执行，后续事务按序等待。当持有锁的事务完成后，锁自动授予队列中的下一个事务，整个流转过程无需任何协商或冲突检测。

3.2.1 确定性锁管理器的内部机制

Calvin 的确定性锁管理器（Deterministic Lock Manager）是实现确定性执行的关键组件。它与传统的锁管理器有着本质区别：传统锁管理器根据事务的运行时行为动态分配锁，而 Calvin 的锁管理器在事务执行之前，就根据预声明的读写集和全局序列号完成了所有锁分配决策。

工作流程如下：

1. 锁请求入队：当一个新的事务批次到达 Scheduler 时，Scheduler 按照序列号从小到大的顺序，依次处理每个事务。对于每个事务，将其读锁请求和写锁请求分别加入对应数据键的锁队列末尾。
2. 锁授予判定：对于队列中的每个事务，检查它是否可以获得锁。规则是：（a）写锁请求：该事务必须位于队列头部，且前面没有任何其他事务持有该键的锁；（b）读锁请求：该事务前面没有写锁请求在等待或持有中。
3. 事务就绪判定：当一个事务在其读写集中的所有数据键上都获得了锁，该事务标记为”就绪”，可以交给 Execution 层执行。
4. 锁释放与传播：事务执行完成后，释放其持有的所有锁，并触发对应锁队列中后续事务的锁授予判定。

读写冲突与写写冲突的处理：

• 读-写冲突：如果 T1（seq=1）持有键 K 的读锁，T2（seq=2）请求键 K 的写锁，则 T2 必须等待 T1 完成。反之，如果 T1 持有写锁，T2 请求读锁，T2 同样必须等待。
• 写-写冲突：如果 T1 和 T2 都请求键 K 的写锁，则严格按序列号顺序，T1 先获得锁。
• 读-读兼容：如果 T1 和 T2 都只请求键 K 的读锁，且它们之间没有写锁请求，则两者可以同时持有读锁并行执行。

为什么不需要死锁检测？

在传统锁管理器中，死锁的根源是循环等待：T1 等待 T2 释放资源 A，同时 T2 等待 T1 释放资源 B。Calvin 中不可能出现这种情况，因为锁的授予严格遵循全局序列号顺序。如果 T1 的序列号小于 T2，则 T1 在所有数据键上都排在 T2 前面。T1 不可能等待 T2，因此不会形成循环依赖。这是一种天然的等待图无环保证（Wait-For Graph Acyclicity）。

具体示例：5 个事务的锁管理过程

假设一个批次包含以下 5 个事务：

T1 (seq=1): read(X), write(Y)
T2 (seq=2): write(X), write(Z)
T3 (seq=3): read(Y), read(Z)
T4 (seq=4): write(X)
T5 (seq=5): read(Z), write(Y)

锁队列初始状态：

X: [T1(R,seq=1), T2(W,seq=2), T4(W,seq=4)]
Y: [T1(W,seq=1), T3(R,seq=3), T5(W,seq=5)]
Z: [T2(W,seq=2), T3(R,seq=3), T5(R,seq=5)]

执行时间线：

时刻 0: T1 获得 X(读锁) + Y(写锁)，标记就绪，开始执行
         T2 等待 X(T1 持有读锁)
         T3 等待 Y(T1 持有写锁)
         T4 等待 X(T1 持有读锁)
         T5 等待 Y(T1 持有写锁)

时刻 1: T1 执行完成，释放 X(读锁) + Y(写锁)
         T2 获得 X(写锁) + Z(写锁)，标记就绪，开始执行
         T3 仍等待 Z(T2 持有写锁)

时刻 2: T2 执行完成，释放 X(写锁) + Z(写锁)
         T3 获得 Y(读锁) + Z(读锁)，标记就绪，开始执行
         T4 获得 X(写锁)，标记就绪，开始执行
         （T3 和 T4 无冲突，可并行执行）

时刻 3: T3、T4 执行完成
         T5 获得 Z(读锁) + Y(写锁)，标记就绪，开始执行

时刻 4: T5 执行完成，批次处理结束

可以观察到，尽管 5 个事务存在多处冲突，整个过程中没有发生任何死锁，也没有任何事务被中止重试。锁管理器的行为完全由序列号决定，所有副本上的执行结果完全一致。

Scheduler 还需要处理分布式场景。在 Calvin 中，数据通常被分区（Partitioning）存储在多个节点上。对于跨分区事务，Scheduler 需要协调多个节点上的锁。但是，由于全局序列号的存在，这种协调是简单的：每个分区的 Scheduler 独立地按照序列号顺序处理本分区的锁请求，不需要额外的分布式协议。

3.3 Execution 层：实际执行与存储交互

一旦事务获得了所有需要的锁，它就进入 Execution 层执行。这一层负责运行实际的事务逻辑，包括读取数据、执行计算、写入结果等。

Execution 层与底层的存储引擎交互。Calvin 本身并不规定特定的存储引擎，它可以与各种存储系统（如 B-Tree、LSM-Tree、内存哈希表等）配合使用。这种分离使得 Calvin 可以适应不同的性能和持久化需求。

在执行过程中，事务只能访问其预先声明的读写集中的数据项。这个约束由 Scheduler 强制执行。如果事务试图访问未声明的数据项，系统会拒绝该访问。

对于跨分区事务，Execution 层需要从多个节点读取数据。Calvin 采用了一种称为”Active Participants”的机制。对于跨分区事务，其中一个分区被指定为协调者（通常是读写集中第一个数据项所在的分区），该协调者负责收集其他分区的数据，执行事务逻辑，并将结果发送回各个分区进行写入。这个过程不需要 2PC，因为所有分区都已经按照相同的顺序预留了锁，执行一定会成功。

执行完成后，事务释放所有锁，Scheduler 可以继续调度下一个事务。事务的结果被写入本地存储，并通过 Sequencer 层的复制机制同步到其他副本。

下图展示了一个完整批次从客户端提交到执行完成的全生命周期：

sequenceDiagram
    participant C as 客户端
    participant S as Sequencer
    participant R1 as 副本1
    participant R2 as 副本2
    participant Sch as Scheduler
    participant E as Executor

    C->>S: 提交事务 T1, T2, T3
    Note over S: 收集事务，组装 Epoch N

    S->>R1: 复制批次 (Epoch N)
    S->>R2: 复制批次 (Epoch N)

    Note over R1,R2: 所有副本收到相同批次

    R1->>Sch: 按序列号排列事务
    Sch->>Sch: 按序分配锁：T1 → T2 → T3

    Sch->>E: T1 就绪，执行
    E->>E: 执行 T1 事务逻辑
    E->>Sch: T1 完成，释放锁

    Sch->>E: T2 就绪，执行
    E->>E: 执行 T2 事务逻辑
    E->>Sch: T2 完成，释放锁

    Sch->>E: T3 就绪，执行
    E->>E: 执行 T3 事务逻辑
    E->>Sch: T3 完成，释放锁

    Note over S: Epoch N 完成，开始 Epoch N+1

    C->>S: 提交新事务
    Note over S: 收集事务，组装 Epoch N+1

该时序图清晰地展示了 Calvin 的三层协作机制：Sequencer 负责收集和复制事务批次，Scheduler 按照全局序列号有序地分配锁，Executor 在获得全部所需锁后执行事务逻辑。每个 Epoch 的处理是流水线化的，当 Epoch N 的事务在执行时，Sequencer 已经在收集 Epoch N+1 的事务。

3.4 批处理执行追踪：从 Epoch 到完成

为了更直观地理解 Calvin 的执行过程，下面以一个具体的 Epoch 为例，完整追踪从事务到达到执行完成的全过程。

假设 Epoch N 到达，包含以下 4 个事务：

T10 (seq=10): read(A, B),    write(A)        — 读取账户 A 和 B，更新 A
T11 (seq=11): read(C),       write(C, D)     — 读取账户 C，更新 C 和 D
T12 (seq=12): read(A, D),    write(D)        — 读取账户 A 和 D，更新 D
T13 (seq=13): read(B),       write(B, C)     — 读取账户 B，更新 B 和 C

第一步：排序（Sequencer 已完成）

事务按序列号排列：T10 → T11 → T12 → T13。所有副本收到的批次内容和顺序完全相同。

第二步：锁队列构建（Scheduler）

Scheduler 按序列号顺序依次处理每个事务的读写集，构建锁队列：

第三步：锁授予与并行执行分析

关键观察：

1. 并行度分析：尽管有 4 个事务，但由于读写集的交叉关系，执行被分为 2 个并行阶段。T10 与 T11 无冲突可并行，T12 与 T13 无冲突可并行。实际并行度取决于事务间的冲突关系，而非序列号的绝对顺序。
2. 确定性保证：无论在哪个副本上执行，锁队列的构建方式、锁授予的时机、事务的执行顺序都完全相同。这就是确定性执行的核心价值——所有副本无需协调即可达到相同状态。
3. Epoch 边界：只有当 Epoch N 的所有事务都执行完成后，Epoch N+1 的事务才开始锁授予。这保证了跨 Epoch 的顺序性。

四、与 Spanner 的本质区别

Calvin 和 Spanner 都是为了解决分布式事务问题，但它们的设计哲学截然不同。理解这些区别有助于我们认识到分布式系统设计中的权衡取舍。

4.1 时间同步 vs 确定性排序

Spanner 的核心是 TrueTime API，它提供了全局的时间界限。通过 GPS 和原子钟，Spanner 能够将不同数据中心的时钟误差控制在几毫秒以内。基于这个能力，Spanner 为每个事务分配一个时间戳，并使用时间戳来确定事务的顺序和可见性。

Calvin 则完全不依赖时间同步。它通过 Sequencer 显式地为事务排序。这种排序是逻辑上的，与物理时间无关。即使系统中各个节点的时钟完全不同步，Calvin 依然可以正常工作。

这个区别带来了不同的部署要求：

• Spanner：需要专门的硬件（GPS 接收器、原子钟）和精心设计的数据中心网络。这在 Google 的规模和资源下是可行的，但对于大多数组织来说是一个高门槛。
• Calvin：纯软件方案，可以在普通硬件上运行。部署和维护成本较低。

4.2 延迟特征对比

Spanner 的读写延迟主要来自两个方面：

1. Commit Wait：为了保证外部一致性，Spanner 在提交事务时需要等待，确保事务的提交时间戳已经过去。这个等待时间等于 TrueTime 的误差界限，通常是 5-10 毫秒。
2. Paxos 协议：Spanner 使用 Paxos 进行副本间的一致性协调，需要多数派确认。

Calvin 的延迟来自：

1. Sequencer 批处理延迟：事务需要等待下一个 epoch（10 毫秒）才能被处理。
2. 锁等待时间：如果事务的读写集与其他事务冲突，需要等待前序事务完成。

对于低冲突的工作负载，Calvin 的延迟可能更低，因为它避免了 2PC 的多轮通信。但对于高冲突的场景，由于严格的串行化顺序，Calvin 可能会出现较长的队列等待。

4.3 吞吐量特征对比

Spanner 的吞吐量受限于 Paxos 写入和快照读取的开销。但它的优势在于：

1. 只读事务无锁：Spanner 的快照隔离允许只读事务在不获取任何锁的情况下执行，只要选择合适的时间戳。
2. 冲突处理灵活：事务可以在检测到冲突时中止并重试，而不会阻塞其他事务。

Calvin 的吞吐量优势在于：

1. 批处理效率：通过批处理摊销了协调开销，可以在一个 epoch 内并行处理大量不冲突的事务。
2. 确定性副本：副本可以独立执行，不需要等待主副本的结果。

但 Calvin 也有劣势：

1. 严格的串行化：即使两个事务在逻辑上可以并行（例如，它们最终不会冲突），如果 Sequencer 给它们分配了顺序，它们也必须按顺序执行。
2. 跨分区事务开销：虽然避免了 2PC，但跨分区事务仍然需要多节点协调。

4.4 适用场景差异

Spanner 适合：

1. 全球分布的应用：需要跨多个大陆的强一致性。
2. 读多写少的场景：可以充分利用无锁的快照读。
3. 需要外部一致性的应用：例如，分布式银行系统，需要严格的因果顺序保证。

Calvin 适合：

1. 读写模式可预测的应用：例如，社交网络的时间线更新、广告投放系统等。
2. 高吞吐量的事务处理：可以通过批处理获得更高的每秒事务数（TPS）。
3. 成本敏感的部署：不需要昂贵的硬件和复杂的基础设施。

4.5 具体场景对比：同一事务在 Calvin 与 Spanner 中的执行路径

为了更直观地理解两种架构的差异，我们以一个具体的分布式事务为例：从分区 1 的账户 A 向分区 2 的账户 B 转账 100 元。

在 Spanner 中的执行路径：

步骤 1：客户端向协调者发起事务
步骤 2：协调者从 TrueTime 获取开始时间戳 t_start
步骤 3：协调者向分区 1 发送读请求，获取账户 A 的余额
        → 分区 1 获取 A 的读锁，返回 balance_A = 500
步骤 4：协调者向分区 2 发送读请求，获取账户 B 的余额
        → 分区 2 获取 B 的读锁，返回 balance_B = 200
步骤 5：协调者计算新余额：A = 400, B = 300
步骤 6：2PC 准备阶段（Prepare Phase）
        → 协调者向分区 1 发送 Prepare(A = 400)
        → 协调者向分区 2 发送 Prepare(B = 300)
        → 分区 1 获取 A 的写锁，写入预写日志（WAL），通过 Paxos 复制到多数派，回复 Prepared
        → 分区 2 获取 B 的写锁，写入预写日志（WAL），通过 Paxos 复制到多数派，回复 Prepared
步骤 7：协调者从 TrueTime 获取提交时间戳 t_commit
步骤 8：Commit Wait — 等待直到 TrueTime.now().earliest > t_commit（约 5-10ms）
步骤 9：2PC 提交阶段（Commit Phase）
        → 协调者向分区 1、分区 2 发送 Commit(t_commit)
        → 各分区通过 Paxos 复制提交记录，释放锁
步骤 10：协调者向客户端返回成功

在 Calvin 中的执行路径：

步骤 1：客户端提交事务请求，声明读写集 {read: [A, B], write: [A, B]}
步骤 2：Sequencer 将事务加入当前 Epoch 的批次，分配序列号 seq=42
步骤 3：Sequencer 将整个批次复制到所有副本（异步复制或 Raft）
步骤 4：各副本的 Scheduler 按序列号顺序处理事务
        → 将 seq=42 的事务加入 A 和 B 的锁队列
        → 等待前序事务完成后，授予 A 和 B 的写锁
步骤 5：事务就绪，Executor 开始执行
        → 分区 1 读取 A 的余额 balance_A = 500
        → 分区 2 将 B 的余额发送给分区 1（协调分区）
        → 分区 1 计算新余额：A = 400, B = 300
        → 分区 1 写入 A = 400
        → 分区 1 将 B = 300 发送给分区 2 写入
步骤 6：事务完成，释放所有锁
步骤 7：客户端收到成功响应

延迟分解对比：

故障处理对比：

Spanner 的优势在于不需要预声明读写集，对交互式事务更友好，且只读事务可以无锁执行。Calvin 的优势在于避免了 2PC 的多轮协调和 Commit Wait，在高冲突场景下不会出现中止重试的级联效应。

五、与 Percolator 的比较

除了 Spanner 和 Calvin，Google 的 Percolator 也是分布式事务处理领域的重要系统。Percolator 基于 Bigtable 构建，采用乐观并发控制（Optimistic Concurrency Control，OCC）和快照隔离（Snapshot Isolation，SI）。

5.1 并发控制机制

Percolator 使用乐观锁。事务在执行过程中不获取锁，只在提交阶段检查冲突。如果发现其他事务已经修改了数据，当前事务中止并重试。这种机制在低冲突场景下效率很高，但在高冲突场景下会导致大量的中止和重试。

Calvin 使用悲观锁，但是是确定性的。事务在执行之前就获取所有需要的锁，并严格按照预定顺序执行。这避免了中止和重试，但可能导致更长的等待时间。

5.2 时间戳获取方式

Percolator 为每个事务分配两个时间戳：开始时间戳（Start Timestamp）和提交时间戳（Commit Timestamp）。这些时间戳来自一个中心化的时间戳服务器（Timestamp Oracle）。虽然时间戳的生成是中心化的，但 Percolator 通过批量获取时间戳来减轻这个瓶颈。

Calvin 不使用时间戳，而是使用序列号。序列号由 Sequencer 分配，并且与物理时间无关。这使得 Calvin 不需要全局的时间服务。

5.3 事务冲突处理

在 Percolator 中，事务冲突通过抢占（Preemption）和重试来解决。如果事务 T1 发现它要写入的数据已经被事务 T2 锁定，T1 可以选择等待或中止。Percolator 还支持伤口-等待（Wound-Wait）策略，较老的事务可以抢占较新的事务的锁。

Calvin 中的冲突是通过确定性排序解决的。如果两个事务冲突，序列号小的事务先执行，序列号大的事务等待。这是完全确定的，不存在抢占或中止。

5.4 适用场景

Percolator 最初是为 Google 的网页索引更新设计的。它适合的场景是：

1. 大规模数据处理：需要对海量数据进行增量更新。
2. 低冲突工作负载：大部分事务访问的数据是独立的。
3. 可以容忍偶尔的重试：事务中止不会对用户体验造成太大影响。

Calvin 更适合需要严格顺序保证和高吞吐量的场景，但受限于读写集预知的约束。

六、FaunaDB 的实践：从理论到工程

FaunaDB（现在称为 Fauna）是一个商业化的分布式数据库，它的设计受到了 Calvin 论文的启发。然而，从学术原型到生产系统，Fauna 团队做了大量的工程改进和妥协。

6.1 Calvin 理论到工程实践的差距

Calvin 论文主要关注核心算法和理论性能，很多工程细节被简化或忽略了。例如：

1. 故障恢复：论文对 Sequencer 和 Scheduler 的故障恢复机制描述较少。在生产环境中，需要处理各种故障场景，如节点崩溃、网络分区、数据损坏等。
2. 负载均衡：论文假设数据是均匀分布的，但实际应用中往往存在热点数据。如何动态调整分区和副本配置是一个挑战。
3. 查询优化：Calvin 专注于事务处理，对复杂查询（如多表连接、聚合等）的支持和优化讨论不多。

Fauna 在这些方面做了大量工作，使得系统能够在真实的生产环境中稳定运行。

6.2 FaunaDB 的改进与妥协

Fauna 对 Calvin 模型做了一些重要的改进：

1. 更灵活的事务模型

Fauna 引入了更灵活的事务 API，允许开发者以更自然的方式编写事务逻辑。虽然底层仍然需要读写集，但 Fauna 通过静态分析和运行时推断来自动确定读写集，对用户更加透明。

// Fauna 的事务示例
client.query(
  q.Let(
    {
      account: q.Get(q.Ref(q.Collection('accounts'), '123')),
      balance: q.Select(['data', 'balance'], q.Var('account'))
    },
    q.If(
      q.GTE(q.Var('balance'), 100),
      q.Update(
        q.Ref(q.Collection('accounts'), '123'),
        { data: { balance: q.Subtract(q.Var('balance'), 100) } }
      ),
      q.Abort('Insufficient balance')
    )
  )
)

2. 改进的 Sequencer 架构

Fauna 使用 Raft 协议来实现 Sequencer 的高可用性。相比于原始 Calvin 的异步复制，Raft 提供了更强的一致性保证和更快的故障切换。

3. 全球部署优化

Fauna 支持多区域部署，并对跨区域事务进行了优化。它采用了分层的 Sequencer 架构：每个区域有本地 Sequencer 处理区域内事务，全局 Sequencer 处理跨区域事务。这减少了广域网延迟的影响。

4. 混合隔离级别

除了可串行化隔离（Serializable Isolation），Fauna 还支持快照隔离（Snapshot Isolation）。对于只读事务或对一致性要求较低的场景，可以选择更宽松的隔离级别以获得更好的性能。

6.3 实际性能表现

根据 Fauna 公开的性能数据，在典型的 OLTP 工作负载下，Fauna 可以达到数十万 TPS 的吞吐量，单个事务的延迟在 50-100 毫秒之间（包括广域网传输）。这个性能对于大多数 Web 应用和微服务场景是足够的。

然而，Fauna 也继承了 Calvin 的一些限制。对于那些无法预先确定读写集的应用，Fauna 要么需要使用侦察查询（增加延迟），要么需要重新设计应用逻辑。这在实践中是一个显著的学习曲线。

6.4 工作负载适应性指南

Calvin 的确定性执行模型并非对所有工作负载都同样适用。理解不同工作负载特征与 Calvin 架构的匹配程度，对于技术选型至关重要。

高冲突工作负载：Calvin 的确定性排序从根本上消除了死锁和活锁问题，这在高冲突场景下是一个显著优势——传统系统在高冲突时可能陷入大量中止和重试的恶性循环。然而，Calvin 要求冲突事务严格按序列号串行执行，这意味着热点键上的吞吐量受限于单线程处理速度。如果大量事务竞争少数几个键，队列会快速累积，尾延迟显著增加。

低冲突工作负载：这是 Calvin 最擅长的场景。当事务之间的读写集交集很少时，Scheduler 可以并行调度大量事务，批处理机制摊销了 Sequencer 的协调开销，系统能够充分利用多核和多节点的并行能力，达到极高的吞吐量。

分布式事务（跨分区）：这是 Calvin 相对于传统方案的核心优势所在。Calvin 完全避免了两阶段提交（2PC），跨分区事务的延迟不会因为协调轮次而翻倍。所有分区按照相同的全局序列独立执行，天然保证一致性。

读密集型工作负载：Calvin 在此场景存在额外开销。所有读操作都必须经过 Sequencer 排序和 Scheduler 锁管理，即使是纯只读事务也不例外。相比之下，Spanner 的快照读可以在不获取任何锁的情况下执行，延迟更低。对于读多写少的场景，这一差异可能十分显著。

写密集型工作负载：如果写入的键集合是可预测的，Calvin 能够高效处理。批处理机制使得大量写入可以在一个 Epoch 内并行完成。但如果写入模式不可预测（例如，写入哪些键取决于读取的结果），则需要依赖侦察查询，增加延迟和复杂度。

交互式/即席查询：Calvin 在此场景面临根本性挑战。用户驱动的交互式事务通常无法预先确定读写集——第二步操作取决于第一步的结果。虽然侦察查询提供了一定的缓解手段，但额外的延迟和实现复杂度使得 Calvin 在此类场景中缺乏竞争力。

选择 Calvin 架构时，最重要的评估维度是：（1）读写集是否可预测；（2）是否存在大量跨分区事务；（3）是否能接受批处理引入的基础延迟。如果三个问题的答案都是肯定的，Calvin 很可能是最佳选择。

七、确定性事务的局限与改进

虽然 Calvin 提供了一种优雅的分布式事务解决方案，但它也有明显的局限性。学术界和工业界在过去十年中提出了多种改进方案。

7.1 BOHM：减少跨分区事务开销

BOHM（Best-effort One-shot Multiversion）是由与 Calvin 同一团队提出的改进方案。BOHM 的核心思想是利用多版本并发控制（Multiversion Concurrency Control，MVCC）来减少跨分区事务的协调开销。

在原始的 Calvin 中，跨分区事务需要等待所有分区都准备好数据才能开始执行。BOHM 允许事务在一个分区上预先执行，生成一个推测性的结果（Speculative Result）。如果后续发现这个结果是正确的（即其他分区的数据没有变化），就可以直接提交；否则，需要重新执行。

这种方法在数据相对静态的场景下可以显著减少延迟，但增加了系统的复杂性。

7.2 PWV：支持谓词查询

PWV（Predicate Write Visibility）解决了 Calvin 在处理范围查询和谓词查询时的问题。在原始的 Calvin 中，读写集必须是精确的键集合。但很多应用需要执行如”读取所有余额大于 1000 的账户”这样的查询，无法提前确定具体的键。

PWV 引入了谓词锁（Predicate Lock）的概念。事务可以声明一个谓词作为其读写集的一部分，例如”balance > 1000”。调度器在分配锁时，检查新事务的谓词是否与已有事务的谓词冲突。

这个扩展使得 Calvin 能够支持更丰富的查询语义，但也增加了调度器的复杂性和开销。

7.3 SLOG：针对多数据中心的优化

SLOG（Scalable LOw-latency General-purpose transaction processing）是 Daniel Abadi（Calvin 的作者之一）在 2019 年提出的系统。SLOG 针对的是跨数据中心的分布式事务场景。

SLOG 的关键洞察是：在多数据中心部署中，大多数事务只访问单个数据中心的数据。对于这类事务，没有必要通过全局 Sequencer 排序，可以在本地数据中心内部快速处理。只有少数跨数据中心的事务才需要全局协调。

SLOG 引入了”家乡”（Home）的概念。每个数据项有一个主数据中心作为其家乡。事务的家乡是其读写集中大多数数据项的家乡。本地事务（所有数据项的家乡都是同一个数据中心）可以在本地快速处理；跨数据中心事务则需要全局排序。

这种设计在保持 Calvin 的确定性优势的同时，显著降低了大多数事务的延迟。

7.4 其他改进方向

除了上述系统，还有一些其他的改进方向：

依赖图执行（Dependency Graph Execution）：不是严格按照序列号串行执行，而是构建事务之间的依赖图，只要依赖关系满足，就可以乱序执行。这可以提高并行度。

自适应批处理（Adaptive Batching）：根据当前负载动态调整 epoch 的大小。在低负载时使用更短的 epoch 以降低延迟，在高负载时使用更长的 epoch 以提高吞吐量。

混合确定性（Hybrid Determinism）：对于能够预先确定读写集的事务使用确定性执行，对于无法预先确定的事务回退到传统的 2PC。这可以扩大系统的适用范围。

八、确定性事务的理论意义与实践价值

回顾 Calvin 的设计，我们可以看到它在分布式事务处理领域提供了一种独特的视角。与其试图在不确定的执行环境中保持一致性（通过 2PC、时间戳排序等），Calvin 选择从源头消除不确定性。这种思路简洁而优雅，理论上可以避免许多传统方案的复杂性。

8.1 学术影响

Calvin 论文在学术界产生了广泛影响。它启发了一系列后续研究，包括前面提到的 BOHM、PWV、SLOG 等。确定性执行的思想也被应用到其他领域，如：

区块链共识：许多区块链系统（如 Ethereum 2.0）采用确定性执行来保证所有节点的状态一致。

分布式机器学习：在参数服务器架构中，确定性更新顺序可以提高训练的可重现性。

实时系统：确定性执行使得系统行为更可预测，有助于满足实时约束。

8.2 工业界的评价

工业界对 Calvin 的评价相对分化。一方面，确实有公司（如 Fauna）成功地将 Calvin 的思想商业化，并在生产环境中运行。另一方面，主流的分布式数据库（如 Google Spanner、Amazon Aurora、CockroachDB）并没有采用 Calvin 的架构。

原因可能包括：

1. 读写集预知的限制：这个约束对很多现有应用来说是一个障碍。将应用迁移到 Calvin 需要重新设计事务逻辑。

2. 生态系统兼容性：Calvin 的事务模型与 SQL 的传统语义有所不同，很难做到完全兼容。这增加了开发者的学习成本。

3. 成熟度差异：Spanner 等系统已经在 Google 内部运行多年，经过了大规模生产环境的考验。Calvin 相对较新，生态系统还在发展中。

4. 优化空间：传统方案（如 MVCC + 2PC）经过多年的优化，性能已经相当不错。Calvin 的理论优势在实际工作负载中可能不那么明显。

然而，Calvin 的价值不仅在于它是否被广泛采用，更在于它展示了一种不同的设计可能性。在特定的应用场景下，确定性执行可能是更好的选择。

8.3 适合 Calvin 的理想场景

总结来看，以下场景可能特别适合 Calvin：

1. 高吞吐量的键值存储：如果应用主要是简单的 GET/PUT/DELETE 操作，Calvin 可以通过批处理获得极高的吞吐量。

2. 预定义的存储过程：如果事务逻辑是固定的（例如，银行的标准转账操作），可以通过静态分析确定读写集。

3. 流式处理：对于流式数据处理管道，事务的输入和输出往往是预先确定的，符合 Calvin 的模型。

4. 需要严格顺序保证的应用：例如，金融交易系统，需要保证事务按照严格的时间顺序执行，Calvin 的确定性排序可以天然满足这个需求。

5. 成本敏感的部署：相比 Spanner，Calvin 不需要昂贵的硬件，更适合中小型公司或初创企业。

九、总结

Calvin 与确定性事务代表了分布式事务处理领域的一条独特道路。它通过预先排序和确定性执行，避免了传统分布式协议的复杂性和开销。这种设计在理论上简洁优雅，在特定场景下性能优异。

然而，Calvin 也不是银弹。读写集预知的约束限制了它的适用范围，使得很多传统的交互式事务难以直接迁移。此外，虽然 Calvin 消除了死锁和不确定性，但它引入了新的挑战，如跨分区事务的协调、故障恢复的复杂性等。

在分布式系统的设计中，没有一种方案能够适用于所有场景。Spanner 的时间同步、Percolator 的乐观并发、Calvin 的确定性执行，每一种方案都有其优势和劣势。理解这些不同的设计哲学和权衡取舍，有助于我们在面对具体问题时做出更明智的选择。

Calvin 的价值不仅在于它提供了一个可用的系统，更在于它拓展了我们对分布式事务的理解。它提醒我们：有时候，与其在混乱中寻求秩序，不如从一开始就建立秩序。这种思维方式在分布式系统的其他领域同样有启发意义。

随着云计算和微服务架构的普及，分布式事务处理的需求只会越来越强烈。Calvin 及其衍生系统（如 SLOG、Fauna）可能会在某些特定的领域找到自己的位置。即使它不会成为主流，它所代表的确定性执行思想也将继续影响着分布式系统的设计和演进。

参考文献

1. Thomson, A., Diamond, T., Weng, S. C., Ren, K., Shao, P., & Abadi, D. J. (2012). Calvin: fast distributed transactions for partitioned database systems. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data (pp. 1-12).

2. Corbett, J. C., Dean, J., Epstein, M., Fikes, A., Frost, C., Furman, J. J., … & Woodford, D. (2013). Spanner: Google’s globally distributed database. ACM Transactions on Computer Systems (TOCS), 31(3), 1-22.

3. Ren, K., Thomson, A., & Abadi, D. J. (2014). An evaluation of the advantages and disadvantages of deterministic database systems. Proceedings of the VLDB Endowment, 7(10), 821-832.

4. Faleiro, J. M., Thomson, A., & Abadi, D. J. (2014). Lazy evaluation of transactions in database systems. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (pp. 15-26).

5. Ding, B., Kot, L., Demers, A., & Gehrke, J. (2015). Centiman: elastic, high performance optimistic concurrency control by watermarking. In Proceedings of the Tenth European Conference on Computer Systems (pp. 1-15).

6. Ren, K., Thomson, A., & Abadi, D. J. (2019). SLOG: serializable, low-latency, geo-replicated transactions. Proceedings of the VLDB Endowment, 12(11), 1747-1761.

7. Peng, D., & Dabek, F. (2010). Large-scale incremental processing using distributed transactions and notifications. In Proceedings of the 9th USENIX conference on Operating systems design and implementation (pp. 251-264).

8. FaunaDB Inc. (2016). Consistency without Clocks: The FaunaDB Distributed Transaction Protocol. Technical Report.

上一篇：Spanner 与 TrueTime 下一篇：分布式快照隔离