DDaM Online DDL 事务优化 (VLDB 23)

  1. 背景

应用程序经常需要更改 schema 来适应新的需求，但在线模式变更（DDL）与事务型（DML）的并发执行仍具有挑战，以往的工作实现在线DDL的方式是通过打补丁实现（比如 MySQL），只能支持部分在线DDL与DML操作并发执行，一些重要 schema 变更需要停机时间（指这段时间内，事务都被 abort，如果数据量特别大，停机时间就会很长，影响前台事务的执行）

Modern database applications often change their schemas to keep up with the changing requirements. However, support for online and transactional schema evolution remains challenging in existing database systems.

Applications therefore often have to carefully schedule downtimes for schema changes, sacrificing availability.

With continuous deployment and integration becoming a norm, however, schema evolution can happen quite frequently (e.g., several times a week), requiring reduced or no service downtime and robust error handling with little DBA intervention [10, 42, 43].

This in turn requires DDL statements be executed in a way that is

(1) online without blocking concurrent data accesses and

(2) transactional such that in case a DDL statement fails (e.g., attempting to convert VARCHAR that contain “illegal” characters to INT) the operation can be safely rolled back to leave the database in a consistent state.

  1. 挑战

  • 现有解决方案（MySQL）不支持事务型DDL，且并非所有DDL都是可以在线执行的，并发 DML 通常被禁止；
  • 并发效率低：DDL 操作普遍需要大量数据修改与迁移，与 DML 并发导致 WW 冲突，触发事务回滚；

  1. No transactional DDL support – Schema changes cannot be rolled back atomically. (更明确，补充关键影响)

  2. Limited online DDL capabilities – Many operations still block concurrent DML. (更简洁，”并非所有” → “Limited”)

  3. High overhead during DDL execution – Large-scale data migration often causes write-write (WW) conflicts, leading to transaction aborts and degraded performance.

  4. 贡献

核心思想：数据定义即修改（DDaM）

通过扩展 SI 协议，DDL 在线修改表模式可以建模成对整张表的一次常规 DML 事务，从而实现与 DML 事务无阻塞的并发执行。

  1. MVCC Background

（1）快照隔离级别（乐观锁机制）

  • 读取/修改：只能看到 begin 时间戳之前的最新版本；
  • 和 RR 能够看到的范围一样；
  • SI 提交时：检查数据项上是否存在大于自己事务 Begin 时间戳成功提交的修改，有则自己 Rollback；

（2）RC 隔离级别（悲观锁机制）

  • 读取 / 修改：始终能够读取最新已提交事务的数据版本，同时锁定数据项，其他事务不允许更改；

（3）First-Updater/Committer Win 协议 （FUW）

  • 同一时间点，一个数据项上只允许存在一个未提交事务的修改版本；（悲观）
  • 并发修改下，只允许第一个提交的事务完成更改，另一个回滚；（乐观）

无论是悲观锁机制还是乐观锁机制，都遵循 FUW 协议：

  • 悲观下，未提交事务 A 更新了数据项 x，未提交事务 B 也想更新数据项 x，但 x 上存在锁，只允许事务 A 更新成功，事务 B 要么被阻塞等待，要么超时回滚；
  • 乐观下，两个未提交事务都能修改数据项 x，但是在提交的时候，先提交的事务 A 能够成功，后提交的事务 B 在检查的时候发现，数据项上最新的成功提交时间戳在自己 Begin 时间戳之后，B 事务只能回滚；

（4）MySQL 间隙锁原理

  • 是 RR 下的一种锁机制，并不锁定行数据，而是锁定两个索引值之间的范围；
  • 目的是防止其他事务在这个范围内插入新数据，解决幻读问题；

  1. 具体实现

5.1 对 DDL 操作进行分类

Copy：操作是否对实际的数据进行复制或修改；

Verify：是否需要进行验证，比如这个DDL操作是否只对表数据进行只读操作；

（1）Copy + Verify

  • Modify: varchar 到 int，需要先扫描全部进行一遍验证，验证没问题后才拷贝数据进行格式转换。
  • 添加唯一索引需要验证，有需要拷贝；

（2）仅 Verify

  • 给列加 NOT NULL 约束，只需扫描全部检查，然后加个元数据约束；

（3）仅 Copy

  • 添加普通索引，根据某个select创建新表，直接复制相应数据项；

（4）都不需要

  • 建表和删表仅需要通过更改系统目录就能实现；

img

5.2 DDaM Overview

img

将原本数据项上的 MVCC 版本链扩展至表 Schema，每张表也维护一个版本链；

Tesseract里面对一个数据项的访问模式：

（1）Catalog表维护的是各个表的 schema 元信息，也就说左上角的表RID 实际上是 tableId，每个表项由一个链表维护，每个链表项含一个时间戳和整个表结构信息

（2）访问数据项时，首先根据 tableId 找到离事务自己最近的schema（图中第一行），比如T1找到的就是S2

（3）再根据数据项 RID 去 columns 表根据 MVCC 数据项版本链寻找可见版本的数据

（4）链表是按照新到旧排序的

5.3 基于通用快照隔离协议修改的 Basic DDaM

DDaM 为了能将 DDL 放入事务中执行，跟随 DML 操作通过 Commit 完成提交，修改了 SI 协议，以支持 DDL。

算法 1（3-20行是通用 SI 协议, 21-32行是用 SI 协议修改表 Schema）

  • generic_read: 遍历数据项 MVCC，找到离自己时间戳 lastest 的记录；
  • generic_write: 先进行 FUW 判断自己是否回滚，然后安装最新的数据版本；
  • ddam_get_schema: 通过系统表 catalog 的 MVCC 链表中寻找当前表最新可见的版本；
  • ddam_update_schema: 在 catalog 中安装一个新的 schema 版本，同时复制数据到新版本的表中；

img

Goal: Execute DDL within transactions, committing with DML. Method: Extend Snapshot Isolation (SI) to support DDL via MVCC.

2. 关键算法（Key Algorithms）

（1）通用 SI 协议（Generic SI Protocol）

  • generic_read: 基于 MVCC 找到 最新可见数据版本（按事务时间戳）。
  • generic_write: 先 检查写冲突（FUW），再安装新数据版本。

（2）DDaM 扩展（DDaM Extensions）

  • ddam_get_schema: 从系统表 catalog 的 MVCC 链 中读取最新表结构。
  • ddam_update_schema:
    • 在 catalog 中 新增 schema 版本。
    • 复制数据 到新版本表（保持一致性）。

（1）Generic SI:

  • generic_read: Find the latest visible data version via MVCC.
  • generic_write: Check conflicts (FUW), then commit new version.

（2）DDaM Extensions:

  • ddam_get_schema: Read latest schema from catalog’s MVCC chain.
  • ddam_update_schema:
    • Add a new schema version to catalog.
    • Copy data to the new schema table.

算法 2：DDaM 中（DDL+DML）事务对数据项的读写与提交

  • ddam_read: 先使用 ddam_get_schema 获取最新可见的表模式，然后用读取表中数据项的可见版本；
  • ddam_write: 先确保可见的表模式是不是最新的，不是则立刻回滚，是则对该表模式版本的数据项安装新版本
  • ddam_commit: 首先获取全局最新时间戳，先检查事务写集与已提交事务是否冲突，冲突则回滚（乐观控制）

img

1
ddam_read

(1) Call ddam_get_schema to get the latest visible schema. (2) Read the latest visible version of data items (MVCC).

ddam_write (1) Validate schema freshness; abort if stale (prevents dirty writes). (2) If valid, install a new data version (under current schema).

ddam_commit (1) Acquire global latest timestamp (commit point). (2) Optimistic conflict check: Abort if write-set conflicts with committed transactions.

5.4 Basic DDaM 存在的问题

（1）DDL 操作很重，大量数据修改与迁移，造成数据项 写-写 冲突发生的可能性非常大，并发效率低；

（2）由于是基于 SI 协议更改的，乐观控制最大的问题是两个事务在执行阶段都是正常的，但是提交阶段，如果 DML 事务先提交，而具有冲突的 DDL 事务在后面提交，根据 FUW，DDL 事务将被回滚，造成大量资源浪费；

（3）不经优化的 DDaM，由于事务需要维护自己的写集，DDL 操作很重导致写集维护成本高昂；

img

Limitations of Basic DDaM

\1. Heavy DDL Operations Impact Concurrency

Issue: Mass data modification/migration in DDL causes frequent write-write conflicts, significantly reducing throughput

Technical impact: High abort rates under concurrent DML operations

\2. Optimistic Control Commit Conflicts

Issue: When conflicting DML commits first, subsequent DDL must abort (per First-Updater-Wins), wasting: ✓ Compute cycles ✓ I/O bandwidth ✓ Schema change opportunities

Core problem: No DDL prioritization mechanism

\3. Excessive Write-Set Overhead

Issue: Unoptimized DDL generates prohibitively large write-sets requiring: ✓ Extended memory allocation ✓ CPU-intensive version tracking

Operational cost: O(n) scaling with table size

5.5 Relaxed DDaM（优化版本）

主要目的是解决 5.4 提出的挑战。

完整执行流程如下：

  • 如果 DML 事务在准备提交的时候，探测到有未提交的 DDL 事务正在执行，进入预提交阶段；
  • DML 事务的预提交阶段（与2PC不同）：DML 事务按照提交顺序放入全局管道（global pipeline），阻塞住，直到 DDL 事务完成 CDC 阶段，才能依次提交成功。
  • DDL 事务在准备提交时候，先进入 CDC 阶段，执行完成后，先提交，之后放行全局管道内的事务，依据最新的 schema 变更批准 DML 事务提交或回滚。

具体实现上的三个点：

（1）Out-of-Place Migration

  • DDL 事务创建新的数组存储数据版本，而非直接修改原数组；而 DML 事务则继续修改原数组；

优点：

  • DDL与DML事务分离的间接数组操作，避免同一个数据项的直接竞争；
  • 避免资源浪费，若 DDL 操作提交时验证失败回滚，不用回滚原数据项版本；

（2）变更数据捕获（Change Data Capture）

  • CDC 阶段的目的：捕获所有进入预提交 DML 事务，将它们的写集应用到新的 schema 上；
  • 若 DML 事务写集与这次模式变更存在冲突，DML 事务需要回滚；否则允许正常提交。

优点：

  • 尽可能减少 DML 事务的回滚（即先试着让 DML 事务适应新模式变更，如果实在存在冲突，则回滚）

（3）Relaxed Snapshots

将 DDL 事务的新数组应用到版本链上：

  • CDC 阶段结束后，通过原子操作将引用修改为新的数组（各数据项及其版本链）

优点：

  • DDL 事务执行过程中，无需再维护写集，减少开销。

图b：T1 预提交后等待 T3 CDC 阶段的完成，T2 由于在 CDC 阶段兼容失败，T2 回滚。

img

  1. 实验

BaseLine 与 对比对象：

  • NoDDL: 没有 DDL 的 ERMIA 系统，仅执行 DML 事务；
  • Blocking：用表锁控制 DDL 与 DML 的进行；
  • Lazy：在 Blocking 实现的基础上，DDL 事务中仅记录 schema 更改元信息，数据迁移在后台进行；
  • Tesseract：本文
  • Tesseract-lazy：在 Tesseract 实现的基础上，数据迁移在后台进行；

（由于 Basic DDaM 未做优化，高并发情况下 DDL 事务大量回滚，性能过差，故实验章节不讲）

测试方法和指标：

  • 由于数据量庞大，每个并发负载只发出一个 DDL 事务；
  • 每秒吞吐 TPS
  • YCSB（MicroBenchmark）
  • TPCC + 自定义的一组 DDL 操作，下称 TPC-CD

img

img

img

论文阅读
#transaction
DDaM Online DDL 事务优化 (VLDB 23)
https://yanghy233.github.io/2025/06/08/DDaM-VLDB/
作者
yanghy
发布于
2025年6月8日
许可协议