DSG（Dependency Serialization Graph，依赖序列化图）

• 用途：判断一个并发事务历史是否可序列化。
• 节点：每个已提交的事务。
• 边类型（表示事务间的依赖）：
  • 写读（wr） 边：$T_1$ 写了数据 → $T_2$ 读了同一数据 ⇒ $T_1$ → $T_2$
  • 写写（ww）边：$T_1$ 写了数据 → $T_2$ 覆盖写同一数据 ⇒ $T_1$ → $T_2$
  • 读写（rw） 边：$T_1$ 读了数据 → $T_2$ 后来写了该数据 ⇒ $T_1$ → $T_2$
• 判断规则：
  • 若 DSG 中无环 → 历史是可序列化的
  • 若 DSG 中有环 → 不可序列化，存在异常（如 G0、G1 等）

G0 Write Cycle 写循环

场景描述

比如现在有两个事务

1. $T_i$: 写$x = 1,y=10$
2. $T_j$: 写$x = 2,y=20$

执行顺序可能为

1. $T_i$ 写 $x = 1$
2. $T_j$ 写 $x = 2$（覆盖了 $T_i$ 的 $x$ ）
3. $T_j$ 写 $y = 10$
4. $T_i$ 写 y = 20（覆盖了 $T_j$ 的 $y$）

最终观测到的结果为：

$x = 2$ 来自 $T_j$

$y = 20$ 来自 $T_i$

没有一个全局的串行顺序能解释这个结果 → 违反了可序列化的基本要求。

Ayda's Phd paper 中的形式化定义

写-写依赖（write-write dependency）：如果事务 $T_1$ 写了某个数据项，然后 $T_2$ 又写了同一个数据项，并且 $T_2$ 的写发生在 $T_1$ 提交之后（或逻辑上在其后），就有一条从 $T_1$ -> $T_2$ 的写依赖边。

T1 → T2
↑    ↓
└────┘   （即 T1 → T2 → T1，形成环）

如果这些写依赖边形成一个有向环，就构成了 $G0$ 写循环现象。

G1a Aborted Read 中止读取

场景描述

考虑两个事务：

1. $T_i$：写入 $x = x_i$，随后中止（abort）
2. $T_j$：读取 $x = x_i$，并成功提交（commit）

执行顺序如下：

1. $T_i$ 写 $x = x_i$
2. $T_i$ 中止
3. $T_j$ 读 $x = x_i$（读到了已中止事务的写）
4. $T_j$ 提交

最终观测到的结果为： 已提交事务 $T_j$ 读取了来自中止事务 $T_i$ 的值 $x_i$ 这导致中止事务的信息泄露至已提交事务

该现象在 Read Uncommitted 隔离级别下是允许的，但在 Read Committed 及更高隔离级别中被明确禁止。

形式化定义

一个历史 $H$ 展现出 G1a 现象，当且仅当其中包含一个中止的事务 $T_i$ 和一个已提交的事务 $T_j$，使得 $T_j$ 读取了某个（可能通过谓词访问的）被 $T_i$ 修改过的对象。

G1b Intermediate Read 中间读取

场景描述

考虑两个事务：

1. $T_i$：依次写入 $x = 1$，然后 $x = 2$（其中 $x = 1$ 是中间状态，$x = 2$ 是最终写入）
2. $T_j$：在 $T_i$ 写入 $x = 1$ 之后、写入 $x = 2$ 之前，读取 $x = 1$，并成功提交

执行顺序如下：

1. $T_i$ 写 $x = 1$
2. $T_j$ 读 $x = 1$
3. $T_i$ 写 $x = 2$
4. $T_i$ 提交（或中止，不影响 G1b 判定）
5. $T_j$ 提交

最终观测到的结果为： 已提交事务 $T_j$ 读取了 $T_i$ 的中间写入值（非最终值） 这导致 $T_i$ 的内部中间状态对外泄露

该现象在 Read Uncommitted 隔离级别下是允许的，但在 Read Committed 及更高隔离级别中被禁止。 注意：G1b 仅约束已提交事务的读行为；未提交事务读取中间状态不构成 G1b。

形式化定义

G1b：中间读取。
一个历史 $H$ 展现出 G1b 现象，当且仅当其中包含一个已提交的事务 $T_j$， 该事务读取了某个对象 $x$ 的一个版本（可能通过谓词访问），而该版本是由事务 $T_i$ 写入的、且并非 $T_i$ 对 $x$ 的最终修改。

扩展讨论：中间更新（Intermediate Update）

当写操作基于先前值进行变换（如 $x_j = f(x_i)$）时，经典 G1b 定义可能无法捕获信息泄露： $T_i$ 写中间值 $x = x_i$，后续可能写 $x = x_{\text{final}}$（或 abort） $T_j$ 读 $x_i$（隐式），计算并写 $x = f(x_i) = x_j$，然后提交 $T_k$ 读 $x = x_j$，并提交

此时： 没有事务直接读取 $T_i$ 的中间版本，因此不满足原始 G1b 但 $T_k$ 间接获得了 $T_i$ 的中间状态信息

若将写操作视为隐式读，则 $T_j$ 与 $T_i$ 构成 G1b。 Jepsen 将此类情况命名为 Intermediate Update（中间更新），作为 G1b 的语义扩展。

G1c Cyclic Information Flow 循环信息流

场景描述

考虑两个事务对同一对象（例如列表）进行操作，每次写入都向列表追加一个唯一整数：

1. $T_1$：向 $x$ 追加 1 → $x = [1]$
2. $T_2$：向 $x$ 追加 2 → $x = [1, 2]$
3. $T_1$ 随后读取 $x$，得到 $x = [1, 2]$
4. 两个事务均成功提交

执行顺序如下：

1. $T_1$ 写 $x \gets [1]$
2. $T_2$ 写 $x \gets [1, 2]$
3. $T_1$ 读 $x = [1, 2]$
4. $T_1$ 提交
5. $T_2$ 提交

最终观测到的结果为： $T_1$ 读到了 $T_2$ 的写入，说明 $T_2$ 的写在逻辑上对 $T_1$ 可见 但 $T_2$ 的写又是在 $T_1$ 的写之后发生的（覆盖或合并） 因此，二者之间形成了相互依赖的循环：$T_1 \to T_2$（通过写-写），$T_2 \to T_1$（通过写-读）

该现象在 Read Uncommitted 下是允许的，但在 Read Committed 及更高隔离级别中被禁止。 注意：G1c 仅约束已提交事务；中止事务的写入不参与依赖图构建。 形式化定义

G1c：循环信息流。
一个历史 $H$ 展现出 G1c 现象，当且仅当其直接序列化图 DSG($H$) 中包含一个完全由依赖边构成的有向环。

扩展讨论

G1c 揭示了一种无法用任何串行顺序解释的并发异常： 虽然每个事务都成功提交，但它们的读写交互形成了逻辑闭环 这破坏了可序列化的基础——即存在一个等价的串行执行

当写操作不是盲写，而是基于先前值的函数变换时（如 $x_j = f(x_i)$），即使没有直接读取中间值，也可能通过链式写入间接传播状态。若将写视为隐式读，则此类场景也可纳入 G1c 的广义理解。

避免 G1c 通常需要数据库提供一致的写可见性顺序，例如通过快照隔离、严格的两阶段锁（S2PL）或线性一致性存储，确保依赖图无环。

G-single Single Anti-dependency Cycle 单一反依赖循环

场景描述

考虑两个事务对两个独立数据项 $x$ 和 $y$ 的操作：

1. $T_i$：写入 $x = 1$，然后写入 $y = 1$
2. $T_j$：先读取 $x = 1$（看到 $T_i$ 的写），再读取 $y$，但此时 $y$ 尚未被 $T_i$ 写入（即读到“未出生”状态，如初始值或空）

执行顺序如下：

1. $T_i$ 写 $x = 1$
2. $T_j$ 读 $x = 1$
3. $T_j$ 读 $y$（读到旧值，如 0 或 null）
4. $T_i$ 写 $y = 1$
5. $T_i$ 和 $T_j$ 均提交

最终观测到的结果为： $T_j$ 部分观察到 $T_i$ 的效果（看到了 $x = 1$，但没看到 $y = 1$） 这导致在依赖图中形成一个包含恰好一条反依赖边（read-write） 的环： $T_i \xrightarrow{wr} T_j$（因 $T_j$ 读了 $T_i$ 写的 $x$） $T_j \xrightarrow{rw} T_i$（因 $T_j$ 在 $T_i$ 写 $y$ 前读了 $y$，构成反依赖）

该现象在 Read Committed 下是允许的，但在 PL-2+、快照隔离（Snapshot Isolation）及更强模型中被禁止。

形式化定义

G-single：单一反依赖循环。
一个历史 $H$ 展现出 G-single 现象，当且仅当其直接序列化图 DSG($H$) 中包含一个恰好包含一条反依赖边（即读-写边）的有向环。

其中： Anti-dependency edge（反依赖边） 即 read-write（RW）边：事务 $T_a$ 读某对象，之后事务 $T_b$ 写该对象 Dependency edges 指 write-read（WR）和 write-write（WW）边 G-single 要求循环中仅有一条 RW 边，其余均为 WR/WW 边

扩展讨论

G-single 是 G2（广义不可串行化） 的一种特例，揭示了“部分可见性”问题： 事务 $T_j$ 看到了 $T_i$ 的一部分写入，却错过了另一部分 这破坏了“原子性”的直观语义——要么看到全部，要么看不到

在 Read Committed 中，由于每次读可能看到不同时间点的已提交值，这种撕裂视图（fractured view）是可能的。 而 快照隔离通过为整个事务提供一致的快照，确保所有读基于同一全局状态，从而避免 G-single。

Jepsen 将此类异常视为弱一致性模型的重要边界标志：若系统允许 G-single，则不能保证因果一致性或可串行化。

G-nonadjacent (Non-adjacent Anti-dependency Cycle) G-非邻接（非邻接反依赖循环）

场景描述

G-非邻接（G-nonadjacent），又称非邻接反依赖循环，是 Jepsen 对一种特定类型 G2 异常的命名：即在依赖图中存在一个包含至少一条读-写边（反依赖）、任意数量写-读（WR）和写-写（WW）边，且任意两条读-写边不相邻的有向环。

考虑如下四事务对整数寄存器 $x$ 和 $y$ 的操作历史：

1. $T_1$：写入 $x = 1$
2. $T_2$：读取 $x = 1$（看到 $T_1$ 的写），随后读取 $y$，但此时 $y$ 尚未被写入（读到“未出生”状态，如 null 或初始值）
3. $T_3$：写入 $y = 3$
4. $T_4$：执行谓词读（例如 SELECT *），仅观察到 $y = 3$，未看到 $x = 1$

执行顺序与依赖关系

1. $T_1$ 写 $x = 1$
2. $T_2$ 读 $x = 1$ → $T_1 \xrightarrow{wr} T_2$（写-读依赖）
3. $T_2$ 读 $y$（未出生）
4. $T_3$ 写 $y = 3$ → $T_2 \xrightarrow{rw} T_3$（反依赖：$T_2$ 先读未写，$T_3$ 后写）
5. $T_4$ 谓词读，仅看到 $y = 3$ → $T_4 \xrightarrow{wr} T_3$
6. $T_4$ 未看到 $x = 1$ → $T_4 \xrightarrow{rw} T_1$（反依赖：$T_4$ 未见 $T_1$ 的写）

由此形成依赖环：

$$T_1 \xrightarrow{wr} T_2 \xrightarrow{rw} T_3 \xrightarrow{wr} T_4 \xrightarrow{rw} T_1$$

该环包含两条 RW（反依赖）边（$T_3 \to T_2$ 与 $T_1 \to T_4$），但它们不相邻（中间被 WR 边隔开），符合 G-nonadjacent 的定义。

形式化定义

一个历史 $H$ 展现出 G-nonadjacent 现象，当且仅当其直接序列化图 DSG($H$) 中存在一个有向环，满足： 包含 至少一条 RW（read-write）边（即反依赖） 所有 RW 边在环中 互不相邻（即任意两个 RW 边之间至少夹有一个 WR 或 WW 边） 其余边为 WR（write-read）或 WW（write-write）边

扩展讨论

G-nonadjacent 虽然不如 G-single 直观，却是快照隔离（Snapshot Isolation, SI）的关键边界特征： Read Committed 允许 G-nonadjacent（因其允许撕裂视图） Snapshot Isolation 明确禁止 G-nonadjacent，但允许相邻的 RW 边构成的环（即所谓的“危险结构”）

根据 Adya (1999)、Fekete et al. (2005) 及 Cerone & Gotsman 的研究： 在 SI 下，任何不可串行化的历史必须包含至少两个相邻的 RW 边（即危险结构） 换言之，SI 排除所有 RW 边不相邻的环 —— 这正是 G-nonadjacent 因此，G-nonadjacent 是 SI 所禁止、而更弱模型（如 Read Committed）可能允许的异常

Jepsen 基于与 Peter Alvaro 和 Alexey Gotsman 的交流，将此类被 SI 排除的“非邻接反依赖环”命名为 G-nonadjacent，以区别于 SI 允许的“邻接 RW 环”。 关键结论：若一个系统允许 G-nonadjacent，则它不满足快照隔离；反之，快照隔离通过确保所有读基于同一一致快照，避免了非邻接反依赖环的出现。

G2-item (Item Anti-dependency Cycle)（反依赖循环）

场景描述

G2-item（项目反依赖循环）是 G2 异常的一种特定形式，其关键特征在于： 所有反依赖边（read-write edges）均源于对具体命名数据项（如寄存器 $x$、$y$）的读操作，而非谓词读（如 SELECT WHERE ...）。

考虑两个事务对两个独立整数寄存器 $x$ 和 $y$ 的操作：

1. $T_1$： 读 $x$ → 发现 $x$ 不存在（读到初始值或 null） 写 $y = 1$

2. $T_2$： 读 $y$ → 发现 $y$ 不存在 写 $x = 1$

假设两者并发执行并最终提交。 执行顺序与依赖关系

1. $T_1$ 读 $x$（未出生）
2. $T_2$ 读 $y$（未出生）
3. $T_1$ 写 $y = 1$
4. $T_2$ 写 $x = 1$

→ 分析依赖： $T_1$ 读 $x$ 时未看到 $T_2$ 的写（因 $T_2$ 尚未写 $x$），而 $T_2$ 后续写了 $x = 1$

⇒ 为保持一致性，$T_1$ 必须在 $T_2$ 之前 ⇒ $T_1 \xrightarrow{rw} T_2$

$T_2$ 读 $y$ 时未看到 $T_1$ 的写（因 $T_1$ 尚未写 $y$），而 $T_1$ 后续写了 $y = 1$

⇒ $T_2$ 必须在 $T_1$ 之前 ⇒ $T_2 \xrightarrow{rw} T_1$

由此形成依赖环：

$$T_1 \xrightarrow{rw} T_2 \xrightarrow{rw} T_1$$

该环仅由两条 项反依赖边（RW）构成 所有读操作均针对具体数据项（$x$ 和 $y$），无任何谓词读 因此，这是一个典型的 G2-item 异常 此历史在 Repeatable Read（ANSI SQL 定义） 下非法，因为 RR 要求事务对已读数据项具有“完全隔离性”，防止其他事务在其执行期间修改这些项。

形式化定义

根据 Adya 博士论文（1999）第 3.2.4 节，基于直接序列化图（DSG）：

G2-item：若历史 $H$ 的直接序列化图 DSG($H$) 中包含一个具有一条或多条项反依赖边（item anti-dependency edges） 的有向环，则称该历史 $H$ 展现出 G2-item 现象。 其中： Item anti-dependency edge（项反依赖边）：指事务 $T_a$ 对某个具体数据项 $x$ 执行读操作（读到旧值或未出生值），随后事务 $T_b$ 写入 $x$，从而形成边 $T_a \xrightarrow{rw} T_b$。 尽管原文表述未显式排除谓词反依赖，但结合上下文及 PL-2.99 的语义可知，G2-item 专指非谓词的、针对具体项的反依赖循环。

Adya 定义的 PL-2.99（即 ANSI Repeatable Read）要求： 事务 $T_i$ 仅当满足以下条件时才可提交： 在数据项层面与其他事务完全隔离（即无 G2-item） 对谓词读提供 PL-2（Read Committed）

这表明：G2-item 被 PL-2.99 明确禁止，而 G2-predicate（涉及谓词读的反依赖）则可能被允许。

扩展讨论

ANSI SQL Repeatable Read 的设计动机： 传统 ANSI Repeatable Read 使用长持续读锁（long-duration read locks）保护所有被读取的具体数据项，防止其他事务在本事务提交前修改它们。这种机制天然阻断 G2-item 循环。 与 G2-predicate 的区别： G2-item：反依赖源于对具体项的读（如 READ(x)） → 被 ANSI RR 禁止 G2-predicate：反依赖源于范围/条件读（如 SELECT WHERE status='active'） → ANSI RR 不禁止（即允许幻读） 现代数据库实现差异： PostgreSQL 的 “Repeatable Read” 实际为 Snapshot Isolation，因此同时禁止 G2-item 和 G2-predicate 某些基于锁的系统（如早期 InnoDB）的 Repeatable Read 仅防止 G2-item，仍可能出现幻读（G2-predicate） 关键结论：G2-item 是区分 Read Committed 与 ANSI Repeatable Read 的核心异常。若系统允许 G2-item，则其隔离级别弱于 Repeatable Read；反之，禁止 G2-item 是实现 ANSI RR 的必要条件。

G2 (Anti-dependency Cycle)G2（反依赖循环）

场景描述

G2（反依赖循环） 是一种广义的不可串行化异常，其核心特征是： 一组事务形成一个依赖环，其中至少有一个事务覆盖了另一个事务所读取的数据项状态（即存在“未出生”或“被覆盖”的读），从而引入至少一条反依赖边（read-write edge）。

具体而言，G2 是一个由任意数量的写-写（WW）和写-读（WR）边，以及至少一条反依赖边（RW）组成的有向环。 该现象在 Repeatable Read（可重复读） 下是允许的，但在 Serializable（可串行化） 及更强的一致性模型中被禁止。

考虑两个事务对整数寄存器的操作：

1. $T_1$： 执行谓词读（如 SELECT ），发现数据库为空 写入 $x = 1$

2. $T_2$： 执行谓词读（如 SELECT ），也发现数据库为空 写入 $y = 2$

假设两者并发执行并提交。执行顺序与依赖关系如下

$T_1$ 谓词读时未看到 $T_2$ 的写（因 $T_2$ 尚未写 $y$），而 $T_2$ 后续写了 $y = 2$

⇒ 为保持一致性，$T_1$ 必须在 $T_2$ 之前 ⇒ $T_1 \xrightarrow{rw} T_2$

$T_2$ 谓词读时未看到 $T_1$ 的写（因 $T_1$ 尚未写 $x$），而 $T_1$ 后续写了 $x = 1$

⇒ $T_2$ 必须在 $T_1$ 之前 ⇒ $T_2 \xrightarrow{rw} T_1$

由此形成依赖环：

$$T_1 \xrightarrow{rw} T_2 \xrightarrow{rw} T_1$$

该环由两条 反依赖边（RW）构成 所有读操作均为谓词读（非针对具体项） 因此，这是一个典型的 G2 异常（也称为 G2-predicate） 此历史无法等价于任何串行执行，故在 Serializable 下非法。但 ANSI SQL 的 Repeatable Read 允许此类幻读，因此 G2 在 RR 下合法。

形式化定义

根据 Adya 博士论文（1999）第 3.2.3 节，基于直接序列化图（DSG）： G2：若历史 $H$ 的直接序列化图 DSG($H$) 中包含一个具有一条或多条反依赖边（anti-dependency edges） 的有向环，则称该历史 $H$ 展现出 G2 现象。

其中： 反依赖边（anti-dependency / RW 边）：指事务 $T_a$ 读取某数据状态（可能为空或旧值），而事务 $T_b$ 后续写入新值，且 $T_a$ 未看到该写入，从而形成边 $T_a \xrightarrow{rw} T_b$。 G2 不限定读操作类型，可包含项读（item read） 或谓词读（predicate read）；当涉及谓词读时，通常特指 G2-predicate（即幻读类异常）。

扩展讨论

G2 与隔离级别的关系： Read Committed：允许 G2（包括 G2-item 和 G2-predicate）

Repeatable Read（ANSI SQL）：允许 G2-predicate（即本例中的幻读），但禁止 G2-item

Serializable / Snapshot Isolation：禁止所有形式的 G2

G2 是可串行化的关键障碍： 任何包含 G2 循环的历史都无法映射到等价的串行调度，因此 Serializable 必须排除 G2。

现代数据库中的处理：

• PostgreSQL 的 “Serializable” 模式通过 SSI（Serializable Snapshot Isolation）检测并中止可能导致 G2 的事务
• Oracle、SQL Server 的 Serializable 通常通过范围锁或版本控制防止 G2-predicate