Tesseract：在线高性能表结构变更方法（VLDB23）

背景

在需求的驱动下，现代数据库应用经常会修改表结构。但是，目前的数据库系统对在线表结构变更的支持仍然不足。这导致用户需要小心规划停机时间才能执行表结构变更，影响业务的可用性。随着持续部署和持续集成的流行，表结构变更发生的频率更为频繁，可以达到一周好几次，这要求在没有DBA介入的情况下实现0停机和鲁棒的错误处理。也就是说，表结构变更需要（1）支持在线执行，不阻塞数据读写（2）支持事务的ACID性质，从而在表结构变更失败时实现安全的回滚，不损坏用户数据。

表结构变更的必要性

在需求的驱动下，现代数据库应用经常会修改表结构，例如增加列，修改约束等。表结构变更一般是通过DDL语句完成的，例如CREATE INDEX, ALTER TABLE等。

数据库系统执行DDL的一般步骤为，首先更新数据库的元信息，以存储演进后的表结构，然后对照新增加的约束检查数据，最后将现存的数据进行修改以满足新的表结构。表结构变更中的数据检查和数据修改会引发大量的数据扫描或移动，从而阻塞并发的DML。

现有技术的不足

过去的工作常常通过在现有系统上挂插件的方式来解决表结构变更的问题，这导致其方案存在一些边角条件（corner case），或者功能不完备。

MySQL: 不支持事务性的DDL，并不是所有的操作都是在线/原子的，并且经常不支持并发的DML。事务中执行DDL会导致之前的操作被静默提交，可能导致隐藏的正确性问题。

一些延迟执行数据迁移的方法，例如Bullfrog，仅能够支持前后兼容的表结构变更。如果表结构变更会引入不兼容的变化，用户需要提前检查表中的数据。因为一旦改变完元数据后，应用就开始使用新版本的表结构，很难再回滚到旧版本的表结构（部分数据已经丢失了）上了。

使用创建视图或者触发器的方法同样可能带来问题，这些方法会锁表，从而导致一段时间内无法对表进行并发更新。

总结：上述表结构变更的问题，主要由于数据库引擎设计时未给与表结构变更足够的重视，导致后续需要通过打补丁的方式来支持用户的表结构变更需求。DDL操作通常被视为危险的，应用开发者通常尽量避免DDL操作。

Tesseract（超立方体）：一种在MVCC系统中支持非阻塞、事务性的表结构变更的方法

动机

在使用MVCC的数据库系统中，可以将表结构变更视为一种修改整个表的DML操作，也可以称为“被作为数据修改的数据定义”（data-definition-as-modification, DDaM）（拔高立意）。在这种视角下，只需要对现有的快照行为进行简单的调整，就可以通过MVCC机制几乎零成本地支持表结构变更，并且不需要停机。

具体来讲，事务性的DDL操作可以被视为对表结构的DML语句和对整个用户表的DML语句，这两个DML语句的和。MVCC系统中对表结构版本的支持为DDL的事务属性提供了天生的便利。这样就可以通过修改数据库引擎的方式将DDL语句也作为DML语句处理，而无需依赖视图和触发器等特性。

在实现DDaM时，也有一些挑战要解决。（1）DDL事务需要访问整个表，可能会执行很长时间，从而阻塞其它事务，或者是由于其它事务的不兼容修改而回滚（2）如果严格遵循快照隔离的流程，追踪修改数据的集合，会导致极高的代价。（3）使用旧版本表结构完成的DML事务必须在新版本表结构提交前提交。（如果旧版本表结构完成的DML，在新版本表结构提交后一段时间才提交，那么在新版本表结构提交后开始的读取事务会使用新的表结构来解析旧的数据，从而读取出错误的数据）。为了解决上述问题，需要通过松弛的DDaM调整快照的使用方式，来提供更多的并发，并且减少不必要的回滚。

尽管Terreract聚焦在MVCC系统上，单版本的系统通过直接的修改也可以使用Tesseract的方法。Tesseract还可以和上面的延迟执行数据迁移的方法一起使用，以支持立即提交兼容的表结构变更。

Tessract基于之前的内存数据库ERMIA实现。

基础的DDaM（被作为数据修改的数据定义）

对DDL操作的分类的两个维度

（1）拷贝（COPY）: DDL操作是否需要真的需要拷贝或修改数据
（2）验证（VERIFY）: DDL操作是否需要验证数据（扫描全部数据并判断是否满足要求）

下表给出了几个典型的例子。
（1）修改列类型（MODIFY COLUMN）时，系统需要扫描整表的数据以确认数据能从旧的类型转变为新的类型，系统还需要修改数据来将数据真的转换为新类型，因此修改列类型同时涉及拷贝和验证
（2）增加非空约束时(ADD CONSTRAINT)，系统需要全表扫描以验证数据满足要求（ TODO 可能把专利中的唯一性约束例子换成非空约束更好？），因此增加非空约束只涉及验证
（3）新增一列时(例如通过JOIN现存表的方式创建新的一列 CREATE 新列 AS SELECT)，系统只需要修改存量数据，而无需验证数据，因此增加列只涉及拷贝
（4）部分DDL可以实现为仅修改表结构而无需检查全量数据。例如CREATE/DROP TABLE, ADD/DROP COLUMN。此类DDL既不涉及拷贝，也不涉及验证。

表结构版本（Schema Versioning）

和经典的表结构管理方法类似，Tesseract使用catalog表中的一条表结构记录来记录数据库中的每种资源，例如表、视图等。catalog表本身的表结构则时预定义好的。借助于数据库系统内置的多版本能力，这一条表结构记录本身也是多版本的。这样表结构的变更就可以实现为（1）通过标准的数据更新流程向catalog表中新增一个新的表结构版本（2）完成数据的验证和迁移，这两件事可以通过一个事务完成，并且符合MVCC的提交和回滚流程，从而确保事务的ACID属性。

访问表中的用户数据时，只需要遵循MVCC的要求和快照语义，读取对当前事务可见的表结构记录即可。

具体到DDaM中的情况如下图所示：

• 每个记录用户数据的表都对应了catalog表中的一条（多版本的）表结构记录
• 表结构记录中定义了表的列、数据类型、约束等信息
• 多版本的表结构记录可以通过一个链表承载，catalog表中记录指向该链表头部的一个指针
• 每个版本的表结构记录带有一个提交时间戳（CommitTS）以标记其可见时间，此外还有一个指向数据的指针，这些数据全部满足该版本的表结构
• 当访问一条记录时，先访问catalog表，以获取合适版本的表结构记录，然后通过表结构记录中的数据指针访问对应的表数据。对* 表结构记录和数据的访问均服从MVCC中快照隔离级别的已有数据访问流程，细节将在下面描述。
• 备注：catalog表中的RID事实上唯一标识了一张用户数据表

使DDL和DML满足事务的ACID要求

Tesseract允许一个事务中同时包括DML和DDL。下面给出Tesseract执行DDL和DML操作的步骤。

DML操作

DML操作仍然遵循快照隔离的常规步骤访问合适的数据版本，但是DML操作必须确保数据版本和表结构版本是一致的。

正如上面的图片所示，当事务T1试图读取表1中RID为1的数据时，其首先访问catalog表来获取对应版本的表结构，也即S2。这是因为T1的快照时间戳为600，而S2的时间戳为500，S2是版本链中第一个对T1可见的版本。然后，T1使用S2来访问相应的数据，也即S2V2.

对于同样要访问表1的事务T2来讲，情况有所不同。因为T2的快照时间戳为200，catalog表中第一个对T2可见的版本是S1。S2对T2不可见，因为S2的提交时间戳是500，大于200，也即S2在T2开始以后才提交。然后，T2使用S1来访问相应的数据，也即S1V2.

更新操作的处理和上面类似，但是需要确保更新操作是在最新的表结构版本，并且在最新的数据版本上进行更新的。“更新操作要基于最新的表结构版本”反映了DDaM方法的一个核心问题：如果并发的DDL操作创建了一个新的表结构版本，但是还没有提交，这样并发的DML事务旧无法修改数据，导致两个事务之间的写写冲突，只有两个事务之一回滚才能解决。

假设在DDL事务提交后，无视写写冲突，强行提交并发的DML事务，并发DML事务更新后得到的数据版本将会获得一个（比DDL事务）更大的提交时间戳（但是表结构版本却是旧版本），这样后续事务在读取这条数据版本时，就会出现数据和表结构版本不匹配的问题，导致错误。

DDL操作

DDL操作会按照快照隔离的一般步骤更新catalog表中的表结构记录，如果有必要的话，再通过DML操作更新表中的用户数据。这两步是在同一个事务上下文中进行的，因此满足事务的原子性、一致性和隔离性。

提交事务

事务在提交时，首先获取一个提交时间戳。然后确认本事务中修改的每一条记录，在修改时使用的表结构版本，在提交时（也就是现在）仍然是最新的表结构版本。最后，完成提交并记录提交时间戳。

备注：快照隔离无需跟踪读取记录的集合。

基础DDaM的问题

通过严格应用快照隔离的流程，基础的DDaM可以简单地允许在线、事务性的DDL操作，而无需挂件式的涉及。但是严格应用快照隔离也会带来严重的并发冲突问题，如下图所示：

（1）DDL操作可能会导致全表扫描和全表数据修改。如下图中(a)所示，这可能会导致并发的DML事务（T2）出现写写冲突（DDL事务先修改一行，然后T2试图修改同一行），从而导致事务回滚。值得一提的是，未修改相同记录的事务不会同DDL冲突，例如下图中更新表2的事务就不会和表1上的DDL操作冲突。

（2）如果并发DML事务（T1）在DDL之前修改了某一行数据，会导致DDL事务在更新这一行时回滚，这样DDL事务的工作就被浪费了。DDL事务能否提交成功，完全是基于运气。

（3）典型的快照隔离流程要求事务追踪更新过的行的集合，对于更新全表的DDL事务来说，会带来很大的开销。

松弛的DDaM （Relaxed DDaM, RDDaM）

上述问题主要是由于一般的快照隔离流程很容易出现写写冲突：

（1）DDL和DML事务可能尝试更新同以行数据，导致写写冲突

（2）DDL事务需要执行较长时间，导致冲突的时间窗口很大

（3）DDL事务需要修改全表数据，导致所有行上都可能出现冲突

Tesseract通过以下两个手段解决上述问题：

（1）通过“表外”DDL修改、冲突解决方案、松弛的快照语义，放松写写冲突的判定条件，允许更多的并发写事务成功。

（2）增加DDL事务的并行度，缩短冲突的时间窗口

“表外”(out-of-place)DDL修改

如下图所示，RDDaM为每个表结构版本创建一个新的虚拟数据表（indirection array）来存储DDL操作产生的数据。在快照隔离的控制下，新的虚拟数据表直到DDL事务提交才对其它事务可见。

因此，并发的DML事务（下图中的T1和T2）继续使用旧版本的虚拟数据表（indirection array）来执行读和写，无需感知并发的DDL操作。这些DML操作可以一直执行到开始提交而不会报错。

但是，基于正确性的考虑，直到并发DDL提交完毕之前，并发的DML操作都不会提交成功。

也就是说，Tesseract松弛了快照隔离的写写冲突解决策略来允许试探性的DML写入，并且将写写冲突的解决推迟到DDL提交之前。（TODO 这一方法的问题是，DML事务提交需要等待DDL提交后才能提交，极大增长了DML事务的时延）

与此同时，DDL事务使用多个线程扫描旧版本的虚拟数据表，并将修改后的数据写入新的虚拟数据表。对于旧版本的每一条数据，DDL事务（1）将其修改为满足新的表结构的数据（2）将修改后的数据写入新的虚拟数据表。扫描完毕后，DDL事务会获取一个预提交时间戳tpre.

由于仅有DDL事务会访问新的虚拟数据表，DDL的写入操作一定能够成功。但是，如果DDL的操作和现有数据不兼容（例如将数据从bigint转换为int），DDL还会报错回滚。

变更数据捕获（Change Data Capture, CDC）

DDL开始后，并发的DML还会继续向旧的虚拟数据表中写入数据。为了确保这些新写入的数据被DDL事务处理，Tesseract在RDDaM中引入了CDC阶段。

为了缩短DDL的执行时间，CDC阶段的速度是至关重要的。Tesseract通过下面两个方法来加快CDC的速度：

（1）控制CDC阶段的工作量。CDC阶段在DDL事务扫描完数据，获取到预提交时间戳之后开始。此时DDL事务会让新的表结构可见，但是会将其设置在一个特殊的“等待中”状态。这样，每个在tpre之后开始的事务都会使用新的表结构，从而避免更多的CDC工作量。然后DDL事务转而执行CDC，扫描DDL开始后，并发DML的WAL（write ahead log，预写日志），一直扫描到tpre为止。具体来讲，在DDL开始扫描时，记录当前的LSN（log sequence number，日志序列号），作为CDC阶段的开始点。CDC阶段的结束点（下图中的t3），则意味者DDL事务的完成，任何依赖CDC阶段完成的事务都可以继续进行。

（2）使用更多的并行度并发处理CDC，并且允许CDC在扫描阶段结束前就开始。值得一提的时，和扫描同时进行的CDC处理，可能会需要向新的虚拟数据表的同一行写入数据，具体保留哪条数据，取决于哪个数据的版本更新，只保留最新版本的数据。

松弛的快照

在上文介绍的基础DDaM中，DDL事务遵循快照隔离的要求，始终使用DDL事务开始时所获取的快照。随之并发事务的执行，DDL事务的快照很快就会变得过时，导致CDC阶段需要处理更多数据。这可能会导致CDC阶段发生更多的冲突。

幸运的是，“表外”修改让Tesseract有了松弛快照要求的可能性，也即DDL事务在扫描阶段就可以直接基于旧版本虚拟数据表上最新的已提交（已预提交）版本修改数据，并将修改完毕的数据写入新版本的虚拟数据表。写入时使用原记录的提交时间戳（而非使用DDL的提交时间戳）（TODO 为什么使用原记录的提交时间戳？）。这使得DDL事务能够迁移尽可能新的版本。新版本的数据写入时使用原记录的提交时间戳，也就无需为新版本维护写入集（以在DDL事务提交时更新写入集中数据的提交时间戳）。从而减轻了写入集维护的开销。

这一方案初看起来，会导致新的虚拟数据表中的数据，其时间戳小于对应表结构版本的时间戳，但却不会影响正确性。原因如下：

（1）由于新的虚拟数据表的存在，新的数据直到DDL完全提交（CDC阶段执行完毕）后才可见

（2）更重要的是，在DDL事务预提交后（tpre）开启的事务，会直接使用新的虚拟数据表。这意味着对这些事务来讲,在新的虚拟表中,只有一个版本是对这些事务可见的。

为了进一步地减少CDC对DDL事务预提交后，新开启事务的阻塞，Tesseract允许特定的DML事务直接继续执行，而无需等待DDL事务结束。也就是说，当DDL事务仅涉及数据拷贝而无需验证时，盲写数据（例如INSERT和不依赖数据原始值的UPDATE）的DML事务可以直接继续执行，无需判断旧版本的数据是否已经被迁移到新的虚拟表上。对于还需要读取数据的DML事务，则要进行检查。DML事务在读取数据时首先预览一下新的虚拟表上的对应数据版本，如果该数据不存在（数据将会被DDL修改），或者该版本的提交时间戳比旧的虚拟表上的对应行的提交时间戳大（另一个DML事务已经更新了目标行），则DML事务不能正确更新此行，需要回滚。在其它场景下，DML事务可以先读取数据，然后正常对数据进行更新。

如果DDL事务涉及到唯一性检查，则所有的DML事务都需要等待DDL事务提交。

实验评估

实验条件设置

在实验评估环节设置了如下几个条件以进行对照分析。

• NoDDL：不支持DDL功能的原始ERMIA版本。这一版本能够支持最快的DML速度。
• Blocking：DDL功能的基线，通过表级锁来实现表结构的一致性。DML事务以读模式获取表锁，DDL事务以写模式获取表锁。表锁通过pthread_rwlock_t实现。
• Lazy：在ERMIA上实现的类似于BullFrog的方案。这个方案中，DDL事务仅更新表结构。数据的修改是在DDL提交后在后台进行或者按需进行。
• Tesseract：在ERMIA上实现的RDDaM方法
• Tesseract-Lazy：同上个方法类似，但是DDL事务仅更新表结构。由于DDL事务难以回滚，因此不支持不兼容的表结构修改。

表结构变更场景下的性能

微测试设置

基于YCSB测试各个场景下的性能。每个DML事务随机选取两行数据读取，选取八行数据更新。此外，还引入了一个并发的DDL事务以执行两个操作：AddColumn和AddConstraint。在AddColumn操作中新增了一个8字节的列。在AddConstraint操作中约束第三列小于一个随机数。AddColumn操作评估系统在DDL执行数据迁移时的表现。AddConstraint操作评估验证操作的性能。
在YCSB开始两秒后，执行并发DDL事务。

性能结果

执行微测试，重点关注并发DDL执行时，DML事务的吞吐量，如下图所示。

• Blocking方法使用悲观锁，导致DDL执行时DML事务吞吐量下降为0
• Lazy方法会在一段时间内影响DML的吞吐量，这是因为表结构变更后面的DML需要进行数据修改操作。
• 仅有Blocking方法和Tesseract方法支持执行带有验证操作的DDL。
  

端到端的TPC-CD结果

实验设置

作为OLTP的测试标准，原始的TPC-C测试模拟了数据仓库的操作。但是TPC-C自身不涉及DDL操作。文章基于过去的工作，为TPC-C扩展了一系列DDL操作。扩展后的测试被称为TPC-CD。同上面的实验类似，DDL开始于两秒后。

设置了如下DDL操作：

• AddColumn：在order_line表中新增一列ol_tax，默认值为0.1
• AddConstraint：在order_line表中新增约束 1 <= ol_number < o_ol_cnt
• AddColumnWithConstraint: 在order_line表中新增一列ol_tax，默认值为0.1，同时新增约束 ol_amount >= 0
• SplitTable：将customer表拆分为两个表，一个包含用户的私人信息，例如credit, payment, balance等，另一张表包含用户的公开信息，例如state, city, street等
• Preaggregate：在order表中新增一列，该列的值为order_line中值的和，且满足如下条件：order_line.ol_w_id = oorder.o_w_id, order_line.ol_d_id = oorder.o_d_id and order_line.ol_o_id = oorder.o_id
• JoinTable：将stock和order_line两张表join为一张新表，从而优化StockLevel事务，该事务原本需要先读取stock表，然后再从order_line表中查询出货信息。
• CreateIndex：为order_line表创建一个主键索引

Scale Factor设置为50

实验结果

如下图所示，有如下观察：

• 对于添加主键索引这种DDL，在主键索引创建完之前，Tesseract难以提交任何事务（Figure 8）
  
  
  
  

结论

支持在线的、事务性的表结构变更对DBMS的线上使用是直观重要的。但是现有的DBMS对这个功能支持不足。Tesseract提供了一种在数据库系统内部原生支持DDL的方法。通过合理使用MVCC和快照隔离，可以将DDL视为一种数据修改（DDaM），从而支持上述在线事务性的表结构变更。实验结果显示，Tesseract能够在执行DDL的同时提供高性能的DML。