\[ \def\wr{\mathsf{\textcolor{teal}{wr}}} \def\ww{\mathsf{\textcolor{red}{ww}}} \def\rw{\mathsf{\textcolor{blue}{rw}}} \def\C{\mathsf{C}} \def\A{\mathcal{A}} \def\T{\mathcal{T}} \def\P{\mathcal{P}} \def\D{\mathrm{D}} \def\RC{\mathrm{RC}} \def\SI{\mathrm{SI}} \def\SSI{\mathrm{SSI}} \]
摘要
我们提出一种理论方法，能够为应用程序中的每个事务程序分配最低可行的隔离级别（在多隔离级别混合设置下），从而保证所有执行均可序列化，进而维护所有完整性约束（包括未显式声明的约束）。该理论扩展了先前针对完全已知事务的研究，以应对实际场景中事务由运行时参数化程序动态生成的挑战。基于此理论，我们提出一种优化方法——读提升与混合隔离级别分配（RePMILA），在确保执行可序列化的同时实现高吞吐量。该方法通过语义保持的代码修改（将部分读操作“提升”为无实际数据变更的写操作以获取排他锁），并结合隔离级别分配优化，探索性能最佳的实现方案。我们以 SmallBank 基准测试为例，展示了该方法在 PostgreSQL 上的性能表现：某些读提升策略的鲁棒分配方案，其吞吐量可与未修改程序在默认非鲁棒的“读已提交（Read Committed）”隔离级别下的性能相媲美，同时仍保证可序列化；相较于所有事务使用“可序列化快照隔离（SSI）”的方案，吞吐量可提升两倍。
作者：
- Brecht Vandevoort, UHasselt, Data Science Institute, ACSL, Belgium
- Alan Fekete, University of Sydney
- Bas Ketsman, Vrije Universiteit Brussel, Belgium
- Frank Neven, UHasselt, Data Science Institute, ACSL, Belgium
- Stijn Vansummeren, UHasselt, Data Science Institute
Introduction
事务管理是数据库管理系统的核心能力。尽管学界持续探索性能优化方法（尤其是利用新型硬件[9,12,18,19,24–26,29–32,35]），但大多数应用软件仍运行在并发控制机制陈旧的主流平台上。这些机制在竞争场景下存在瓶颈，导致可序列化事务性能低下[37,43]。为此，平台通常允许程序员选择弱隔离级别（如默认的“读已提交（Read Committed）” [6]），以在适用场景下提升性能。然而，目前仍缺乏系统化的方法帮助程序员判断何时接受非可序列化隔离是合理的。
事务的鲁棒性与可序列化保证
近年理论研究提出了分析事务集合的算法，可在混合隔离级别设置下为每个事务分配隔离级别，同时保证应用的鲁棒性（robustness）[41]。换言之，即使部分事务未运行在可序列化隔离级别，应用的所有可能执行仍可序列化。此任务被称为分配问题（allocation problem）[20]，其结论依赖于平台的具体并发控制机制。例如，基于单版本数据加锁的机制与支持多版本读（如读取已覆盖版本）的机制会得出不同结论[20,28]。然而，现有理论假设所有事务在分配时完全已知（包括读写项），这在实际中不成立：应用通常通过参数化程序生成事务，参数值（如用户输入的学生 ID 和课程代码）仅在运行时确定。
事务模板的鲁棒性
本文的核心理论贡献是提出一种算法，可为事务模板（transaction templates）集合分配隔离级别，确保在 PostgreSQL 等多版本并发控制平台上，任意参数实例化生成的事务执行均鲁棒（即可序列化）。模板是对参数化事务的抽象，其读写集由变量决定。该抽象假设存在固定的只读属性（如主键）用于筛选待更新元组，虽限制了部分场景（如禁止更新主键），但分析是保守且安全的：可能遗漏某些鲁棒的可行分配，但算法生成的分配必然保证可序列化。在此限制下，我们证明了所生成分配的最优性——为每个模板分配尽可能低的隔离级别（优先选择 RC 而非 SI，SI 而非 SSI），且任何符合模板的代码均鲁棒。
基于读提升与混合隔离级别分配的优化
利用分配算法，我们提出 RePMILA（读提升与混合隔离级别分配）优化方法，在保持代码语义的前提下，通过“提升”部分读操作为无实际变更的写操作（即设置排他锁），探索性能最优的鲁棒分配方案。我们以 SmallBank 基准测试[3]为例，在 PostgreSQL 上验证了不同读提升策略的性能。实验表明，某些提升策略的鲁棒分配吞吐量接近未修改程序在 RC 隔离级别下的性能（但后者无法保证可序列化），且相比全事务 SSI 隔离方案，吞吐量可提升两倍。
贡献
本文贡献包括理论与实证成果，并为实践者提供指导：
- 理论层面：提出多版本隔离级别在事务模板中鲁棒性的证明技术，以及生成唯一最低鲁棒分配的多项式时间算法；
- 实证层面：通过 SmallBank 案例证明部分读提升策略能实现接近非鲁棒分配的吞吐量，同时显著优于全事务 SSI 方案；
- 实践意义：RePMILA 为开发者提供了一种在高性能与可序列化执行间权衡的有效工具。
本文结构
本文剩余部分组织结构如下：
- 第 2 节：展示 RePMILA 在 SmallBank 基准测试中的应用，具体包括：
- 如何将每个程序抽象为事务模板；
- 分配算法如何确定模板的隔离级别分配；
- 不同读提升策略的生成方式；
- 各提升策略对应的最终分配方案。
- 第 3 节：测量不同提升策略的性能表现，并与以下基线方案对比：
- 全事务采用可序列化（Serializable）隔离级别；
- 全事务采用默认读已提交（Read Committed）隔离级别（可能导致未声明的数据约束被违反）。
- 第 4 节：阐述理论框架，包含分配算法的技术细节。
- 第 5 节：讨论相关研究工作。
- 第 6 节：分析本工作的实践意义与局限性，并提出未来研究方向。
READ PROMOTION AND MIXED ISOLATION LEVEL ALLOCATION (REPMILA)
EVALUATING REPMILA OVER SMALLBANK
ALLOCATION ALGORITHM
Transactions and Schedules
Conflict-Serializability
Isolation Levels
定义 4.3
调度 \(s\) 中的事务 \(T_i\) 在 RC 下允许，当且仅当：
- \(T_i\) 中的每个写操作遵守 \(s\) 的 commit order；
- 每个读操作 \(b_i \in T_i\) 都读到了 \(b_i\) 在 \(s\) 中的上一个相关写（read-last-committed）；
- \(T_i\) 在 \(s\) 中不产生脏写。
调度 \(s\) 中的事务 \(T_i\) 在 SI 下允许，当且仅当：
- \(T_i\) 中的每个写操作遵守 \(s\) 的 commit order；
- 每个 \(T_i\) 中的读操作都读到了 \(first(T_i)\) 在 \(s\) 中的上一个相关写（read-last-committed）；
- \(T_i\) 在 \(s\) 中不产生并发写。
调度 \(s\) 中的危险结构 \(T_1 \to T_2 \to T_3\) 是：
- \(T_1 \xrightarrow{\rw} T_2 \land T_2 \xrightarrow{\rw} T_3\)；
- \(T_1\) 和 \(T_2\) 在 \(s\) 中并发；
- \(T_2\) 和 \(T_3\) 在 \(s\) 中并发；
- \(\C_3 \le_s \C_1 \land \C_3 <_s \C_2\)；
- 如果 \(T_1\) 是只读，则 \(\C_3 <_S first(T_1)\)。
定义 4.5
事务集合 \(\T\) 在其上的分配 \(\A\) 下被允许，当且仅当：
- \(\forall T_i \in \T. \A(T_i) = \RC \implies T_i \models \RC\)；
- \(\forall T_i \in \T. \A(T_i) \in \set{\SI, \SSI} \implies T_i \models \SI\)；
- 不存在三个 \(\SSI\) 事务（不一定是不同事务）构成的危险结构 \(T_i \rightarrow T_j \rightarrow T_k\)。
Transaction Templates
Transaction and Template Robustness
Deciding Template Robustness
Finding Lowest Robust Allocations
定义 4.10
命题 4.12
