【分布式系统百科】分布式快照隔离：从 Write Skew 到 Serializable SI

在分布式数据库的事务处理领域，快照隔离（Snapshot Isolation，SI）已经成为工业界最主流的隔离级别实现。从 Oracle 到 PostgreSQL，从 CockroachDB 到 TiDB，SI 凭借其优秀的并发性能和相对简单的实现复杂度，在理论的严格性与工程的实用性之间找到了一个绝佳的平衡点。然而，SI 并非完美无缺——写偏斜（Write Skew）异常的存在使其无法满足最严格的可串行化（Serializability）语义。本文将深入探讨快照隔离的理论基础、Write Skew 异常的本质、可串行化快照隔离（SSI）的解决方案，以及这些技术在分布式环境下的实现挑战。

一、隔离级别的历史演进与批判

1.1 ANSI SQL-92 标准的定义

ANSI SQL-92 标准定义了四个事务隔离级别，通过禁止不同类型的异常现象来区分它们：

• Read Uncommitted（读未提交）：允许脏读（Dirty Read），即事务可以读取其他未提交事务写入的数据。
• Read Committed（读已提交）：禁止脏读，但允许不可重复读（Non-repeatable Read），即同一事务内多次读取同一数据可能得到不同结果。
• Repeatable Read（可重复读）：禁止不可重复读，但允许幻读（Phantom Read），即同一事务内多次执行相同查询可能返回不同的行集合。
• Serializable（可串行化）：最高隔离级别，禁止所有异常，保证事务执行的结果等价于某个串行执行顺序。

ANSI 标准通过”禁止异常”的方式定义隔离级别，看似简洁明了，但这种定义方式存在根本性缺陷。标准只列举了三种异常现象，却没有给出精确的形式化定义，也没有证明这些异常是否完备——是否存在其他类型的异常被遗漏了？

1.2 Berenson 等人的批判与扩展

1995 年，Hal Berenson、Phil Bernstein、Jim Gray 等人在论文 A Critique of ANSI SQL Isolation Levels 中对 ANSI 标准进行了系统性批判。他们指出了几个关键问题：

第一，定义的模糊性。ANSI 标准使用自然语言描述异常，缺乏严格的形式化定义。例如，“幻读”的定义是”同一查询返回不同行集合”，但没有明确说明是否包括因其他事务插入、删除或更新导致的谓词条件变化。

第二，异常列表的不完备性。Berenson 等人发现了至少三种 ANSI 标准未涵盖的异常：

• Read Skew（读偏斜）：事务 T1 读取 x，然后事务 T2 更新 x 和 y 并提交，随后 T1 读取 y。T1 看到的是不一致的快照——新的 y 和旧的 x。
• Write Skew（写偏斜）：两个并发事务各自读取一组数据，基于读取的结果分别更新不同的数据项，导致违反一致性约束。
• Lost Update（丢失更新）：两个事务读取相同数据，然后基于读取值进行更新，后提交的事务覆盖了前者的更新。

第三，隔离级别的不可比性。ANSI 标准假设隔离级别之间存在严格的强弱关系，但实际上不同的实现技术可能导致隔离级别之间不完全可比。

Berenson 等人提出了基于依赖图（Dependency Graph）的形式化定义方法。他们将事务之间的依赖关系分为三类：

• 写-读依赖（wr-dependency）：T1 写入 x，T2 读取 x，记作 T1 →wr T2。
• 写-写依赖（ww-dependency）：T1 写入 x，T2 也写入 x，记作 T1 →ww T2。
• 读-写依赖（rw-dependency）：T1 读取 x，T2 写入 x，记作 T1 →rw T2。

在这个框架下，可串行化的充要条件是事务依赖图中不存在环（Cycle）。不同隔离级别允许依赖图中存在不同类型的环，从而导致不同的异常行为。

1.3 快照隔离的出现

就在同一时期，快照隔离作为一种新的隔离级别被提出并迅速在工业界得到应用。Oracle 数据库早在 1980 年代就实现了类似 SI 的机制，而 Berenson 等人在 1995 年的论文中首次对 SI 进行了形式化描述。快照隔离的核心思想极其简洁：

1. 每个事务在开始时看到数据库的一个一致快照（Snapshot），这个快照反映了所有在事务开始前已提交事务的结果。
2. 事务的所有读操作都基于这个快照，不受其他并发事务的影响。
3. 事务的写操作在私有空间中进行，直到提交时才对其他事务可见。
4. First-Committer-Wins 规则：如果两个并发事务尝试写入相同的数据项，只有先提交的事务成功，后提交的事务必须中止。

SI 的优势在于读操作永远不会被阻塞，因为读取的是历史快照，不需要等待任何锁。这使得 SI 在只读事务占主导的 OLAP 负载下表现极为出色。然而，SI 并不等价于 Serializable——它允许某些不可串行化的执行历史，其中最著名的就是 Write Skew 异常。

二、快照隔离的精确语义

2.1 MVCC：多版本并发控制基础

快照隔离的实现依赖于多版本并发控制（Multi-Version Concurrency Control，MVCC）技术。MVCC 的核心思想是为每个数据项保存多个版本，每个版本带有时间戳信息，表示该版本的生效时间范围。

在 MVCC 系统中，每个事务 T 在开始时被分配一个时间戳 start_ts(T)，在提交时被分配另一个时间戳 commit_ts(T)。数据项 x 的每个版本可以表示为三元组 ⟨x, v, ts⟩，其中 v 是数据值，ts 是写入该版本的事务的提交时间戳。

读规则：当事务 T 读取数据项 x 时，返回满足以下条件的版本： - 版本的时间戳 ts ≤ start_ts(T) - 在所有满足上述条件的版本中，ts 最大

这保证了事务 T 读取的是其开始时刻之前最新的已提交版本。

写规则：事务 T 的写操作在私有空间中进行，生成新版本但不立即可见。提交时，系统检查是否存在冲突：

def can_commit(T):
    write_set_T = get_write_set(T)
    for x in write_set_T:
        # 检查是否有其他事务在 T 的快照之后修改了 x
        for version in get_versions(x):
            if version.ts > start_ts(T) and version.ts < commit_ts(T):
                return False  # First-Committer-Wins 规则
    return True

如果检查通过，事务的写操作被赋予 commit_ts(T) 并对后续事务可见；否则事务中止。

2.2 First-Committer-Wins 的实现细节

First-Committer-Wins 规则是 SI 防止丢失更新（Lost Update）的关键机制。考虑以下场景：

-- 初始状态：balance = 100
-- T1 和 T2 并发执行

-- T1: 存款 50
BEGIN;
  SELECT balance FROM account WHERE id = 1;  -- 读到 100
  UPDATE account SET balance = 150 WHERE id = 1;
COMMIT;

-- T2: 存款 30
BEGIN;
  SELECT balance FROM account WHERE id = 1;  -- 读到 100
  UPDATE account SET balance = 130 WHERE id = 1;
COMMIT;

在 SI 下，T1 和 T2 各自读取快照时看到 balance = 100。如果没有 First-Committer-Wins 规则，两个事务都可能提交，最终结果是 130 而非正确的 180。但 FCW 规则保证了只有先提交的事务（假设是 T1）成功，T2 会因为 write-write 冲突而中止，必须重试。

实现 FCW 的常见方法包括：

1. Write Lock（写锁）：事务在写入数据项时获取该项的写锁，持有到提交。如果另一个事务尝试写入已被锁定的项，立即检测到冲突。

2. Write Intent（写意图）：CockroachDB 使用的机制。事务写入时留下”write intent”标记，后续事务遇到 intent 时检查其所属事务的状态，如果仍在进行中则等待或中止。

3. Version Check（版本检查）：提交时检查写集合中每个数据项的最新版本时间戳，如果大于事务开始时间戳则中止。

2.3 SI 与 Serializable 的差异

快照隔离提供了优秀的异常隔离性，它天然防止：

• 脏读：读取的都是已提交版本
• 不可重复读：读取基于固定快照
• 幻读：快照固定了可见行集合
• 丢失更新：First-Committer-Wins 规则

然而，SI 不等价于 Serializable。形式化地说，可串行化要求存在一个串行执行顺序，使得所有事务的执行结果与该顺序一致。SI 允许某些不可串行化的执行历史，这些历史在依赖图中表现为包含两个或更多读-写反依赖（rw-antidependency）的环。

三、Write Skew 异常的深度解析

3.1 医生值班问题

Write Skew 的经典例子是”医生值班问题”。假设医院规定至少有一名医生值班，当前有 Alice 和 Bob 两人值班。他们各自感觉不适，想请假回家，于是分别提交请假请求：

-- 初始状态：Alice 值班，Bob 值班
-- 约束：至少一人值班

-- T1 (Alice 请假)
BEGIN;
  SELECT COUNT(*) FROM doctors WHERE on_call = true;  -- 返回 2
  -- 检查：2 >= 1，可以请假
  UPDATE doctors SET on_call = false WHERE name = 'Alice';
COMMIT;

-- T2 (Bob 请假)
BEGIN;
  SELECT COUNT(*) FROM doctors WHERE on_call = true;  -- 返回 2
  -- 检查：2 >= 1，可以请假
  UPDATE doctors SET on_call = false WHERE name = 'Bob';
COMMIT;

在快照隔离下，T1 和 T2 的读操作都基于初始快照，看到两人都在值班。由于它们更新不同的行（Alice 和 Bob），不存在 write-write 冲突，First-Committer-Wins 规则不会触发。两个事务都成功提交，最终结果是没有医生值班，违反了业务约束。

3.2 依赖图分析

我们用依赖图来分析这个异常。设 x 表示 Alice 的值班状态，y 表示 Bob 的值班状态：

• T1 读取 x 和 y（都为 true），写入 x（设为 false）
• T2 读取 x 和 y（都为 true），写入 y（设为 false）

依赖关系： - T1 读取 y，T2 写入 y：T1 →rw T2 - T2 读取 x，T1 写入 x：T2 →rw T1

这形成了一个包含两个 rw 边的环：T1 →rw T2 →rw T1。这种结构称为”dangerous structure”或”pivots”，是导致 Write Skew 的根本原因。

下面用依赖图直观展示这个环状结构：

graph LR
    T1["T1: 读取 x,y<br/>写入 x=false"]
    T2["T2: 读取 x,y<br/>写入 y=false"]
    T1 -- "rw-antidependency<br/>T1 读 y, T2 写 y" --> T2
    T2 -- "rw-antidependency<br/>T2 读 x, T1 写 x" --> T1

该依赖图清晰地展示了 Write Skew 的本质：T1 读取了 y 的旧版本而 T2 随后写入了 y，T2 读取了 x 的旧版本而 T1 随后写入了 x，两条 rw-antidependency 边形成闭环。在可串行化的执行历史中，依赖图必须是无环的；环的存在意味着不存在等价的串行执行顺序，因此该执行结果违反了可串行化语义。

3.3 Write Skew 与 Lost Update 的区别

Write Skew 和 Lost Update 都涉及并发事务基于过时数据进行更新，但它们有本质区别：

Lost Update 的模式是：

T1: r(x) ... w(x) ... commit
T2: r(x) ... w(x) ... commit

两个事务读写相同的数据项 x。SI 的 First-Committer-Wins 规则能够检测这种冲突。

Write Skew 的模式是：

T1: r(x), r(y) ... w(y) ... commit
T2: r(x), r(y) ... w(x) ... commit

事务读取重叠的数据集合 {x, y}，但写入不同的数据项（T1 写 y，T2 写 x）。不存在 write-write 冲突，FCW 规则无法检测。

3.4 实际系统中的 Write Skew 案例

Write Skew 并非纯理论问题，它在实际系统中导致了真实的 bug。

案例 1：会议室预订系统

某公司的会议室预订系统允许预订 1 小时时间段，约束是同一房间同一时段只能被一个会议预订：

-- T1 预订房间 A 的 10:00-11:00
BEGIN;
  SELECT COUNT(*) FROM bookings 
    WHERE room = 'A' AND time_slot = '10:00-11:00';  -- 返回 0
  INSERT INTO bookings (room, time_slot, user) 
    VALUES ('A', '10:00-11:00', 'Alice');
COMMIT;

-- T2 也预订房间 A 的 10:00-11:00
BEGIN;
  SELECT COUNT(*) FROM bookings 
    WHERE room = 'A' AND time_slot = '10:00-11:00';  -- 返回 0
  INSERT INTO bookings (room, time_slot, user) 
    VALUES ('A', '10:00-11:00', 'Bob');
COMMIT;

在 SI 下，两个事务都能成功提交，导致双重预订。这个 bug 在生产环境中出现过，直到用户投诉才被发现。

案例 2：游戏积分兑换

某在线游戏允许玩家用积分兑换虚拟物品。玩家当前有 100 积分，同时点击了两个各需 80 积分的物品：

-- T1 兑换物品 X（80 积分）
BEGIN;
  SELECT points FROM player WHERE id = 123;  -- 返回 100
  -- 检查：100 >= 80，可以兑换
  UPDATE player SET points = points - 80 WHERE id = 123;
  INSERT INTO inventory (player_id, item) VALUES (123, 'X');
COMMIT;

-- T2 兑换物品 Y（80 积分）
BEGIN;
  SELECT points FROM player WHERE id = 123;  -- 返回 100
  -- 检查：100 >= 80，可以兑换
  UPDATE player SET points = points - 80 WHERE id = 123;
  INSERT INTO inventory (player_id, item) VALUES (123, 'Y');
COMMIT;

两个事务都读到 100 积分，都认为可以兑换，最终玩家获得了两个物品但积分不足。虽然最终积分可能变成负数（取决于 UPDATE 的具体实现），但约束已被违反。

3.5 为什么 Write Skew 在实践中较少见

尽管 Write Skew 在理论上很重要，但在实际系统中遇到的频率相对较低，原因包括：

1. 约束检查通常在应用层：许多应用在执行数据库操作前先在应用代码中检查约束，这种检查基于快照数据，无法防止 Write Skew，但会在冲突发生后通过业务逻辑补偿。

2. 写集合重叠更常见：大多数事务模式倾向于更新它们读取的数据项，导致 write-write 冲突而非 Write Skew。

3. 锁定读（SELECT FOR UPDATE）：开发者为关键读操作添加锁定提示，将 rw-dependency 转化为 ww-dependency，从而被 FCW 规则捕获。

4. 悲观锁策略：某些关键业务流程使用悲观锁（如分布式锁），完全避免并发问题。

然而，当 Write Skew 确实发生时，它往往很难调试——表现为偶发的约束违反，难以复现，且传统的数据库隔离机制无法防止。

四、可串行化快照隔离（SSI）

4.1 Cahill 的突破性研究

2008 年，Michael Cahill 在其博士论文 Serializable Isolation for Snapshot Databases 中提出了可串行化快照隔离（Serializable Snapshot Isolation，SSI）。SSI 的核心思想是在快照隔离的基础上，通过检测可能导致不可串行化的依赖模式，动态中止事务以保证可串行化。

Cahill 的关键洞察是：在 SI 下，不可串行化的执行历史对应于依赖图中的环，且这些环必然包含至少两条连续的 rw-antidependency 边。形式化地说，如果存在事务序列 T1 →rw T2 →rw T3，且这三个事务构成环的一部分，则该执行历史不可串行化。

SSI 的策略是检测这种 dangerous structure 并中止其中一个事务。具体而言，系统跟踪每个事务的读集合（read set）和写集合（write set），检测以下两种冲突：

1. rw-outConflict：事务 T 读取数据项 x，另一个并发事务 T’ 写入 x 并已提交或正在提交。T 可能导致不可串行化。

2. rw-inConflict：事务 T 写入数据项 x，另一个并发事务 T’ 已经读取过 x 且仍在进行中。T 的提交可能导致 T’ 不可串行化。

如果事务 T 同时具有 rw-outConflict 和 rw-inConflict，则存在 pivot 结构，T 必须被中止。

4.2 算法详解

SSI 算法在事务的每个读写操作和提交时刻进行检查：

class Transaction:
    def __init__(self, txn_id, start_ts):
        self.txn_id = txn_id
        self.start_ts = start_ts
        self.read_set = set()
        self.write_set = set()
        self.rw_out_conflict = False
        self.rw_in_conflict = False
        
    def read(self, key):
        self.read_set.add(key)
        # 检查是否有并发事务已写入 key
        for version in get_versions_after(key, self.start_ts):
            if version.txn != self.txn_id:
                self.rw_out_conflict = True
                mark_rw_in_conflict(version.txn)
        return get_snapshot_value(key, self.start_ts)
    
    def write(self, key, value):
        self.write_set.add(key)
        # 检查是否有并发事务已读取 key
        for txn in get_concurrent_readers(key, self.start_ts):
            txn.rw_out_conflict = True
            self.rw_in_conflict = True
        write_to_private_space(key, value)
    
    def commit(self):
        # First-Committer-Wins 检查
        if not check_fcw(self.write_set, self.start_ts):
            self.abort()
            return False
        
        # SSI 检查：如果存在 pivot 结构则中止
        if self.rw_out_conflict and self.rw_in_conflict:
            self.abort()
            return False
        
        # 提交成功
        commit_ts = allocate_commit_ts()
        make_writes_visible(self.write_set, commit_ts)
        return True

4.3 SSI 检测机制实战演练

为更直观地理解 SSI 的工作原理，我们用一个具体场景完整演示检测流程。

场景：银行系统中，账户 A 和账户 B 各有余额 100 元，约束为 A + B >= 100。两个并发事务分别从 A 和 B 转出 50 元。

-- T1：从 A 转出 50 元
BEGIN;
  SELECT balance FROM accounts WHERE id = 'A';  -- 读到 100
  SELECT balance FROM accounts WHERE id = 'B';  -- 读到 100（检查约束：100+100-50 >= 100，通过）
  UPDATE accounts SET balance = 50 WHERE id = 'A';
COMMIT;

-- T2：从 B 转出 50 元
BEGIN;
  SELECT balance FROM accounts WHERE id = 'A';  -- 读到 100
  SELECT balance FROM accounts WHERE id = 'B';  -- 读到 100（检查约束：100+100-50 >= 100，通过）
  UPDATE accounts SET balance = 50 WHERE id = 'B';
COMMIT;

如果两个事务都成功提交，最终 A=50, B=50, A+B=100，恰好满足约束。但如果约束是 A + B >= 150，则两个事务都会通过检查（100+100-50=150 >= 150），最终结果 A+B=100 < 150，违反约束。这是典型的 Write Skew。

SSI 检测过程：

1. T1 读取 A 和 B 时，系统记录 T1 的读集 = {A, B}
2. T2 读取 A 和 B 时，系统记录 T2 的读集 = {A, B}
3. T1 写入 A 时，系统检查是否有并发事务读取过 A：发现 T2 读取了 A。标记 T1.rw_inConflict = true，T2.rw_outConflict = true
4. T2 写入 B 时，系统检查是否有并发事务读取过 B：发现 T1 读取了 B。标记 T2.rw_inConflict = true，T1.rw_outConflict = true
5. T1 尝试提交：检查 T1.rw_outConflict（true）且 T1.rw_inConflict（true），检测到 dangerous structure，T1 被中止
6. T2 提交成功（此时 T1 已中止，不再构成环）

SSI 的整体检测流程可概括为以下决策路径：

flowchart TD
    A["事务 T 开始<br/>分配 start_ts，初始化读集/写集"] --> B["执行读/写操作"]
    B --> C{"每次读操作：<br/>是否有并发事务<br/>已写入该数据？"}
    C -- "是" --> D["标记 T.rw_outConflict = true<br/>标记写入方.rw_inConflict = true"]
    C -- "否" --> E{"每次写操作：<br/>是否有并发事务<br/>已读取该数据？"}
    D --> E
    E -- "是" --> F["标记 T.rw_inConflict = true<br/>标记读取方.rw_outConflict = true"]
    E -- "否" --> G["继续执行"]
    F --> G
    G --> H{"事务请求提交"}
    H --> I{"FCW 检查：<br/>写集是否与已提交<br/>事务冲突？"}
    I -- "冲突" --> J["中止事务"]
    I -- "无冲突" --> K{"SSI 检查：<br/>rw_outConflict AND<br/>rw_inConflict？"}
    K -- "两者都为 true<br/>（dangerous structure）" --> J
    K -- "否" --> L["提交成功"]

该流程图展示了 SSI 算法在事务生命周期中的三个关键检测阶段：读操作时的 outConflict 标记、写操作时的 inConflict 标记，以及提交时的 dangerous structure 判定。当一个事务同时作为 rw-antidependency 的”入边目标”和”出边源头”时，它就处于潜在环的中心位置，必须被中止以保证可串行化。值得注意的是，SSI 采用保守策略——并非所有被中止的事务都真正会导致非可串行化结果，但这种策略保证了不会遗漏任何真正的违规。

4.4 PostgreSQL 的 SSI 实现

PostgreSQL 从 9.1 版本开始支持 SSI，是首个提供真正 SERIALIZABLE 隔离级别的开源数据库。其实现在 Cahill 算法基础上进行了工程优化：

SIREAD Locks（谓词锁近似）

为了跟踪事务的读集合，PostgreSQL 引入了 SIREAD Lock。与传统的行锁不同，SIREAD Lock 是共享的、非阻塞的，仅用于冲突检测而不阻止其他事务访问。

由于精确跟踪每个读操作的开销过大，PostgreSQL 使用粒度升级策略：

• 最初在元组（tuple）级别记录 SIREAD Lock
• 当一个事务的锁数量超过阈值，升级到页（page）级别
• 进一步超过阈值，升级到表（table）级别

粒度升级导致更多的 false positive（误判），但大幅降低了内存开销。

冲突检测优化

PostgreSQL 维护两个数据结构来检测 rw-antidependency：

1. SERIALIZABLEXACT（事务状态表）：记录每个活跃事务的读集合、写集合、冲突标记等信息。

2. Predicate Lock Table：记录 SIREAD Lock，按照锁对象（tuple/page/table）组织，支持快速查找哪些事务持有特定对象的锁。

当事务 T 写入数据项 x 时，系统查找 Predicate Lock Table，找到所有持有 x 的 SIREAD Lock 的事务，标记它们的 rw-outConflict 并标记 T 的 rw-inConflict。

Safe Snapshot（安全快照）

PostgreSQL 引入 Safe Snapshot 概念来减少不必要的中止。如果事务开始时，所有可能与其冲突的旧事务都已结束，则该事务的快照是”安全的”，不会导致不可串行化。Safe Snapshot 的事务可以跳过某些冲突检查。

4.5 性能影响与误判

SSI 的主要性能开销来自：

1. 内存开销：跟踪 SIREAD Lock 和冲突信息需要额外内存。PostgreSQL 通过粒度升级和老化机制（aging）来限制内存使用。

2. 计算开销：每次读写操作都需要检查冲突，增加了 CPU 开销。

3. 事务中止率：SSI 会中止某些实际上可串行化的事务（false positive），因为它使用保守的检测策略。

在 OLTP 负载下，SSI 的吞吐量通常比 SI 低 10%-30%，但仍然显著优于基于锁的 Serializable 实现（如 Two-Phase Locking）。对于只读事务占主导的 OLAP 负载，SSI 的开销更小，因为只读事务不会触发 pivot 结构。

False Positive 的来源

1. 粒度升级：页级或表级 SIREAD Lock 导致不相关的读操作被认为冲突。

2. 保守的环检测：检测到 pivot 结构时，实际的依赖图可能不包含环（例如，第三个事务可能在环形成前中止）。

3. 谓词锁的近似：范围查询的谓词锁可能覆盖实际未读取的数据项。

实践中，false positive 率通常在 1%-5% 之间，对大多数应用可接受。

五、分布式环境下的 SI 挑战

5.1 全局快照的实现

在单机数据库中，获取一致快照相对简单——递增的事务 ID 或时间戳即可标识快照版本。但在分布式系统中，问题变得复杂：

挑战 1：时钟同步

分布式系统中的各个节点有各自的物理时钟，由于时钟漂移（clock skew），不同节点的时钟可能不一致。如果直接使用本地时钟作为时间戳，可能导致因果关系倒置：

节点 A：T1 在时刻 10 写入 x=1 并提交
节点 B：T2 在时刻 9（本地时钟慢）读取 x，应该看到 x=1，但因时间戳判断错误读到旧值

解决方案：逻辑时钟与混合逻辑时钟

• Lamport 时间戳：纯逻辑时钟，通过消息传递同步，保证因果一致性。缺点是与物理时间脱节，无法支持某些需要真实时间的查询（如”查询 1 小时前的数据”）。

• TrueTime（Google Spanner）：使用 GPS 和原子钟提供高精度时间同步，将时钟不确定性控制在毫秒级，通过 wait 机制保证因果一致性。

• Hybrid Logical Clock（HLC，CockroachDB）：结合物理时钟和逻辑计数器，既保留因果关系又接近真实时间，成本远低于 TrueTime。

挑战 2：跨分片读取

假设数据分片存储在多个节点上，事务 T 需要读取分片 A 和分片 B 的数据。如何保证 T 在两个分片上看到同一时刻的一致快照？

方案 1：中心化时间戳分配

引入时间戳服务器（Timestamp Oracle），所有事务从该服务器获取全局唯一的开始时间戳和提交时间戳。这保证了全局顺序，但时间戳服务器可能成为瓶颈和单点故障。

方案 2：分布式快照协议

事务协调者向各分片发送快照时间戳，各分片基于该时间戳返回本地快照数据。需要确保快照时间戳在所有分片上的语义一致，通常要求分片间同步已提交事务信息。

5.2 分布式事务提交

跨分片写事务的提交需要原子性——要么所有分片都提交，要么都不提交。经典的两阶段提交（Two-Phase Commit，2PC）协议被广泛使用：

# 协调者（Coordinator）
def commit_distributed_transaction(txn):
    # Phase 1: Prepare
    prepare_ok = True
    for shard in txn.participating_shards:
        if not shard.prepare(txn):
            prepare_ok = False
            break
    
    # Phase 2: Commit/Abort
    if prepare_ok:
        for shard in txn.participating_shards:
            shard.commit(txn)
        return True
    else:
        for shard in txn.participating_shards:
            shard.abort(txn)
        return False

# 参与者（Participant）
def prepare(txn):
    # 检查 First-Committer-Wins 和 SSI 冲突
    if has_conflict(txn):
        return False
    # 将事务记录持久化到 WAL，状态为 PREPARED
    write_to_wal(txn, state=PREPARED)
    return True

def commit(txn):
    # 更新状态为 COMMITTED，使写操作可见
    apply_writes(txn)
    write_to_wal(txn, state=COMMITTED)

2PC 的问题是阻塞性：如果协调者在 Phase 2 之前崩溃，参与者会一直等待决定，持有的资源（如锁）无法释放。这对高可用性有严重影响。

改进方案：Paxos Commit 与 Raft-based 2PC

将 2PC 的协调者复制到多个节点，使用共识算法（Paxos 或 Raft）保证协调者的高可用性。即使单个协调者节点崩溃，其他节点可以接管并完成事务提交。

5.3 读写冲突的分布式检测

在分布式 SSI 实现中，检测 rw-antidependency 变得复杂，因为读写操作可能发生在不同节点上：

• 事务 T1 在节点 A 读取 x
• 事务 T2 在节点 B 写入 x

如何让两个节点感知到这个冲突？

方案 1：集中式冲突管理

所有读操作和写操作都向中心化的冲突检测服务报告，该服务维护全局的 SIREAD Lock 和冲突图。这种方案实现简单，但扩展性差。

方案 2：分片拥有权（Ownership）

每个数据项由特定分片”拥有”，该分片负责该项的冲突检测。读操作需要向拥有分片注册 SIREAD Lock，写操作向拥有分片查询是否有冲突的读者。这增加了网络开销，但避免了单点瓶颈。

方案 3：乐观检测

事务在本地节点跟踪读写集合，提交时通过 2PC 协议同步到所有参与分片，各分片在 Prepare 阶段检查本地冲突。这种方案网络开销较小，但可能在提交时才发现冲突，导致更多的事务中止。

六、CockroachDB 的 SSI 实现

6.1 架构概览

CockroachDB 是一个分布式 SQL 数据库，设计目标是提供可串行化事务语义、高可用性和水平扩展能力。它默认使用 SERIALIZABLE 隔离级别，基于 SSI 实现。

CockroachDB 的关键设计决策包括：

• MVCC 存储：底层使用 RocksDB 存储引擎，每个数据项的多个版本按时间戳排列。
• Hybrid Logical Clock（HLC）：每个节点维护 HLC，既保留因果顺序又与物理时间接近。
• Raft 复制：数据分片（Range）通过 Raft 协议复制到多个节点，保证高可用性。
• Distributed Transaction Protocol：基于 2PC 的分布式事务协议，协调者状态通过 Raft 复制。

6.2 事务生命周期

事务开始

事务 T 开始时，协调者节点分配一个 HLC 时间戳作为 start_ts。T 的所有读操作将基于这个时间戳读取快照。

func (tc *TxnCoordSender) BeginTxn(ctx context.Context) *Transaction {
    txn := &Transaction{
        ID:      generateTxnID(),
        StartTS: tc.clock.Now(), // HLC timestamp
        Status:  PENDING,
    }
    return txn
}

读操作

读操作发送到数据所在的 Range。Range 返回时间戳 ≤ start_ts 的最新已提交版本。如果遇到 Write Intent（未提交的写操作），需要判断：

• 如果 Intent 的事务已提交且 commit_ts ≤ start_ts，读取该版本。
• 如果 Intent 的事务仍在进行中或 commit_ts > start_ts，读操作被阻塞或返回错误。

func (r *Replica) Get(ctx context.Context, key Key, ts Timestamp) (Value, error) {
    // 查找时间戳 <= ts 的最新版本
    value, intent := r.mvccGet(key, ts)
    
    if intent != nil {
        // 遇到 Write Intent，检查所属事务状态
        txnStatus := r.checkTxnStatus(intent.TxnID)
        if txnStatus == COMMITTED && intent.Ts <= ts {
            return r.resolveIntent(intent)
        } else {
            // 等待或返回错误
            return nil, ErrWriteIntentFound
        }
    }
    
    return value, nil
}

写操作

写操作在本地缓存，提交时才发送到 Range。写操作在 Range 上留下 Write Intent，包含事务 ID 和数据值。

Read Refresh 机制

CockroachDB 的一个重要优化是 Read Refresh。当事务因时间戳过旧（即读快照过时）而面临中止时，系统尝试”刷新”读集合：检查读集合中的每个 key 在 start_ts 和当前时间之间是否有新版本。如果没有，可以安全地将事务的时间戳向前推进，避免中止。

func (tc *TxnCoordSender) Commit(ctx context.Context, txn *Transaction) error {
    // 尝试提交
    err := tc.sendCommitRequest(txn)
    
    if isTimestampPushedError(err) {
        // 时间戳被推进，尝试 Read Refresh
        if tc.canRefreshReads(txn) {
            txn.StartTS = txn.CommitTS
            return tc.sendCommitRequest(txn)
        }
    }
    
    return err
}

func (tc *TxnCoordSender) canRefreshReads(txn *Transaction) bool {
    for key := range txn.ReadSet {
        // 检查 [txn.StartTS, txn.CommitTS] 区间是否有新版本
        if tc.hasVersionInRange(key, txn.StartTS, txn.CommitTS) {
            return false
        }
    }
    return true
}

Read Refresh 显著降低了事务中止率，尤其对于只读事务，几乎可以完全避免因时间戳冲突导致的中止。

6.3 冲突检测

CockroachDB 结合 Write Intent 和 Transaction Record 来检测冲突：

Write Intent 作为锁

Write Intent 类似于悲观锁，后续事务遇到 Intent 时会检查其所属事务的状态：

• 如果事务已提交，解析 Intent 并读取或写入。
• 如果事务仍在进行，根据优先级判断：高优先级事务可以推进低优先级事务的时间戳或中止它；低优先级事务需要等待。

Transaction Record

每个事务有一个 Transaction Record 存储在特定 Range，记录事务状态（PENDING/COMMITTED/ABORTED）、时间戳、优先级等信息。Transaction Record 通过 Raft 复制，保证高可用性。

当事务 T2 遇到 T1 的 Write Intent 时，T2 查询 T1 的 Transaction Record 来决定如何处理冲突。如果 T1 已经长时间未活动（可能崩溃），T2 可以主动中止 T1。

SSI 冲突检测

CockroachDB 在 Write Intent 层面检测 rw-antidependency。当事务 T 写入 key 时，系统检查是否有其他事务的读操作与 T 冲突。具体实现依赖于在 Range 层面跟踪读取时间戳，但细节相对复杂且不断演进。

6.4 分布式提交协议

CockroachDB 使用并行提交（Parallel Commit）优化来减少分布式事务的延迟。传统 2PC 需要两次跨网络的同步往返，而并行提交在某些情况下可以将其减少到一次：

1. Prepare 阶段：协调者向所有参与 Range 并行发送 Prepare 请求，每个 Range 写入 Write Intent 并返回。

2. 隐式提交：协调者收集到所有 Prepare 成功响应后，更新 Transaction Record 为 COMMITTED，但不等待该更新完成，立即向客户端返回提交成功。

3. 懒提交传播：Transaction Record 的更新和 Write Intent 的解析异步进行，后续读取到 Intent 的事务会主动查询 Transaction Record 来确定事务状态。

这种设计在牺牲一定一致性检查复杂度的前提下，显著降低了提交延迟。

七、YugabyteDB 的事务模型

7.1 DocDB 与 MVCC

YugabyteDB 是另一个支持分布式 SQL 的数据库，其存储层 DocDB 基于 RocksDB，采用 MVCC 设计。与 CockroachDB 类似，YugabyteDB 也使用 Hybrid Time（类似 HLC）作为时间戳系统。

YugabyteDB 提供两种隔离级别：

• Snapshot Isolation：提供快照隔离语义，不检测 Write Skew，性能更高。
• Serializable：基于 SSI 实现，检测并阻止 Write Skew，保证可串行化。

7.2 Raft 与事务的结合

YugabyteDB 的数据分片称为 Tablet，每个 Tablet 通过 Raft 协议复制到多个节点。Raft 不仅用于复制数据，还用于复制事务的元数据和锁信息。

当事务在 Tablet 上执行写操作时，Write Intent 通过 Raft 日志复制到所有副本。这保证了即使 Leader 节点崩溃，新选举的 Leader 也能感知到所有未完成事务的状态。

7.3 Wait-on-Conflict vs Fail-on-Conflict

YugabyteDB 允许用户选择冲突处理策略：

Wait-on-Conflict（等待冲突）

当事务 T2 遇到 T1 的 Write Intent 时，T2 等待 T1 完成（提交或中止），然后继续执行。这类似于锁等待机制，优点是减少了不必要的中止，缺点是可能导致等待延迟甚至死锁（需要死锁检测机制）。

Fail-on-Conflict（快速失败）

T2 遇到冲突时立即中止并重试，不等待 T1。这降低了延迟的不确定性，适合延迟敏感的应用，但增加了事务中止率。

在 Serializable 模式下，YugabyteDB 还需要检测 rw-antidependency。实现上，它跟踪每个 Tablet 上的读操作时间戳，当写操作提交时检查是否有冲突的读者，如果有则中止相应事务。

7.4 与 CockroachDB 的对比

两者都是优秀的分布式数据库，但在事务协议的细节设计上有所不同，各有权衡。

八、SI 相关的经典研究

8.1 Fekete 的形式化分析

2005 年，Alan Fekete、Dimitrios Liarokapis、Elizabeth O’Neil、Patrick O’Neil 和 Dennis Shasha 在论文 Making Snapshot Isolation Serializable 中对 SI 的异常进行了形式化分析。他们证明了：

定理：在快照隔离下，执行历史 H 可串行化，当且仅当其依赖图中不存在包含两条连续 rw 边的环。

基于这个理论，他们提出了一种静态分析方法：通过分析应用程序的事务模式，识别可能导致 Write Skew 的”易损模式”（vulnerable patterns）。对于这些模式，开发者可以手动添加约束（如使用 SELECT FOR UPDATE）来消除 rw-dependency。

这种方法的优点是无需修改数据库，缺点是需要人工分析，且对动态生成的查询无效。

8.2 Generalized SI（GSI）

2007 年，Elnikety 等人提出了广义快照隔离（Generalized Snapshot Isolation，GSI），适用于复制系统。在主从复制架构中，写操作在主节点执行，读操作可以在从节点执行。GSI 保证即使读写分离，也能提供快照隔离语义。

GSI 的关键是定义”一致快照”的条件：从节点的快照必须反映所有在该快照时间戳之前已提交的写操作。这需要主从之间的时间戳同步和复制延迟控制。

8.3 Parallel SI（PSI）

Parallel Snapshot Isolation（PSI）是针对分布式数据库提出的一种隔离模型。PSI 放松了 SI 的全局快照要求，允许不同节点上的快照时间戳不同，只要满足因果一致性即可。

PSI 的优势是降低了跨节点同步开销，适合地理分布式系统。缺点是语义比 SI 更弱，不保证读到的是”全局时刻的快照”，对某些应用可能难以理解。

8.4 Clock-SI 协议

Clock-SI 是 Jiaqing Du 等人在 2014 年提出的快照隔离协议，专为广域网分布式数据库设计。它使用松散同步的物理时钟（如 NTP）来分配快照时间戳，无需中心化的时间戳服务器。

Clock-SI 的核心思想是利用时钟的单调性和有界偏差。即使时钟不完全同步，只要偏差在已知范围内，就可以通过延迟提交（commit delay）来保证快照一致性：

commit_delay = max_clock_skew + propagation_delay

事务提交后，等待 commit_delay 时间，确保所有节点的时钟都超过了提交时间戳，才使写操作对外可见。这避免了”未来写”问题（某节点时钟慢，导致读到未来时间戳的数据）。

Clock-SI 的优势是无中心化瓶颈，缺点是 commit_delay 增加了事务延迟。

九、总结与展望

9.1 SI 在工业界的统治地位

快照隔离已成为现代分布式数据库的事实标准。Oracle、PostgreSQL、MySQL（InnoDB）、SQL Server、CockroachDB、TiDB、YugabyteDB 等主流数据库都采用 SI 或其变种作为主要隔离级别。SI 的流行源于其在性能与正确性之间的优秀平衡：

• 读不阻塞写，写不阻塞读：MVCC 机制使得只读事务几乎无开销，适合 OLAP 负载。
• 相对简单的实现：相比 Serializable（如 Strict 2PL），SI 的实现复杂度更低，性能更好。
• 大多数应用不受 Write Skew 影响：实际业务中，真正导致 Write Skew 的场景较少，大多数应用可以接受 SI 的语义。

9.2 SSI 的理论与实践

可串行化快照隔离（SSI）通过在 SI 基础上增加依赖检测，实现了真正的 Serializable 语义。PostgreSQL 的成功实现证明了 SSI 在单机数据库中的可行性。然而，在分布式环境下，SSI 的实现仍面临挑战：

• 网络开销：分布式冲突检测需要跨节点通信，增加延迟。
• 误判率：保守的检测策略和粒度升级导致 false positive，增加事务中止率。
• 复杂性：分布式 SSI 的正确性证明和调试都极为困难。

CockroachDB 等系统通过 Read Refresh、并行提交等优化，在分布式环境下实现了可用的 SSI，但仍在不断演进。

9.3 从理论到实践的鸿沟

学术研究中的隔离级别定义往往基于理想化的模型，而工业界的实现需要考虑性能、可用性、可维护性等多重因素。这导致理论与实践之间存在鸿沟：

• 模糊的语义：许多数据库声称支持”Serializable”，但实际行为可能不同。开发者需要深入了解具体实现才能正确使用。
• 配置的复杂性：不同的隔离级别、冲突处理策略、优化开关，使得数据库配置成为一门艺术。
• 测试的困难：并发异常往往难以复现，单元测试和集成测试很难覆盖所有边界情况。Jepsen 等分布式系统测试工具变得越来越重要。

9.4 未来方向

快照隔离和事务处理领域仍有许多开放问题：

• 新硬件的利用：持久化内存（Persistent Memory）、RDMA 网络、智能网卡（SmartNIC）等新硬件如何改变事务协议的设计？
• 机器学习的应用：能否通过学习事务的访问模式，预测冲突并提前优化？
• 形式化验证：如何用形式化方法证明分布式事务协议的正确性？TLA+ 等工具已在部分系统中使用。
• 更弱的隔离级别：对于某些应用，SI 仍然过强。Causal Consistency、Session Guarantees 等更弱的模型如何与事务结合？

快照隔离的故事远未结束。从 Berenson 等人在 1995 年的开创性工作，到 Cahill 在 2008 年的 SSI 突破，再到今天各种分布式数据库的工程实践，我们见证了理论与实践的相互推动。Write Skew 这个看似边缘的异常，揭示了事务隔离的深层复杂性，也激发了无数研究者和工程师的创新。在追求性能与正确性的永恒平衡中，快照隔离将继续演进，为分布式系统提供坚实的事务基础。

参考文献

1. H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O’Neil, and P. O’Neil. “A Critique of ANSI SQL Isolation Levels.” ACM SIGMOD Record, 1995.

2. M. J. Cahill, U. Röhm, and A. D. Fekete. “Serializable Isolation for Snapshot Databases.” ACM Transactions on Database Systems (TODS), 2009.

3. A. Fekete, D. Liarokapis, E. O’Neil, P. O’Neil, and D. Shasha. “Making Snapshot Isolation Serializable.” ACM Transactions on Database Systems (TODS), 2005.

4. K. Daudjee and K. Salem. “Lazy Database Replication with Snapshot Isolation.” VLDB, 2006.

5. S. Elnikety, F. Pedone, and W. Zwaenepoel. “Database Replication Using Generalized Snapshot Isolation.” SRDS, 2005.

6. J. Du, S. Elnikety, A. Roy, and W. Zwaenepoel. “Orbe: Scalable Causal Consistency Using Dependency Matrices and Physical Clocks.” ACM SoCC, 2013.

7. J. C. Corbett et al. “Spanner: Google’s Globally-Distributed Database.” OSDI, 2012.

8. R. Taft et al. “CockroachDB: The Resilient Geo-Distributed SQL Database.” ACM SIGMOD, 2020.

9. K. Saur et al. “Building Consistent Transactions with Inconsistent Replication.” ACM SOSP, 2021.

10. D. R. K. Ports and K. Grittner. “Serializable Snapshot Isolation in PostgreSQL.” VLDB, 2012.

上一篇：Calvin 与确定性事务
下一篇：分布式事务实战对比