关于 TAE(Transactional Analytical Engine) 的那些事

TAE 是 MatrixOne 的存储引擎，取这个名字，是因为它需要同时支撑 TP 和 AP 能力。第一个版本的 TAE 实现，已经随 MatrixOne 0.5 版本发布，这是一个单机存储引擎。从 MatrixOne 0.6 版本开始，TAE 将进化成为存算分离的云原生分布式架构。我们将分期跟随 MatrixOne 版本地演进，逐步揭示 TAE 存储引擎的设计内幕。

本文假定读者对列存有基本的了解，对于列存的数据常见组织，比如 block(或者 page，最小 IO 单元)，segment(若干 block 组成的 row group)，zonemap(column block 内的最大/最小值)等都有基本的认知，对普通的 Key Value 存储引擎实现，比如 LSM Tree 也有初步了解，比如它的 Memtable，WAL，SST 文件等概念。下图的 TAE 逻辑结构的左半部分，涉及到了列存的一些基本概念，可以供不具备相关背景的同学了解。

在介绍 TAE 设计之前，首先回答一个问题：为什么采用列存结构来设计一个数据库的核心存储引擎？

这是因为 MatrixOne 期望用一个存储引擎同时解决 TP 和 AP 的问题。至于为什么这样做，可以关注矩阵起源的其他文章，简单地讲，就是期望在共享存储的基础之上，可以随意弹性的启动不同计算节点分别处理 TP 和 AP 任务，在最大化伸缩性的同时保证不同负载的相互隔离。在这个前提之下，采用以列存为基础的结构，可以具备如下优点：

1. 很容易对 AP 优化

2. 通过引入 Column Family 的概念可以对负载灵活适配。假如所有列都是一个 Column Family，也就是所有的列数据保存在一起，这就跟数据库的 HEAP 文件非常类似，可以表现出行存类似的行为，典型的 OLTP 数据库如 PostgreSQL 就是基于 HEAP 来做的存储引擎。假如每个列都是独立的 Column Family，也就是每一列都独立存放，那么就是典型的列存。通过定义 Column Family，用户可以方便地在行存和列存之间切换，这只需要在 DDL 表定义中指定即可。

因此，从物理上来说，TAE 就是一个列存引擎。下文的行存，则是指普通的 Key Value 存储引擎如 RocksDB，因为很多典型的分布式数据库都基于它来构建。TAE 是一个类似 LSM Tree 的结构但却没有直接采用 RocksDB，是出于一些额外的考虑。

为什么列存比行存难设计？

众所周知 SQL 计算引擎处理 TP 请求和 AP 请求有着巨大的不同，前者以点查询为主，要求高并发能力，后者以 Scan 请求为主，通常采用 MPP 引擎，不追求并发而追求并行处理。对应到存储，行存天然是服务 TP 请求的，列存天然是服务 AP 请求的，因为前者可以采用基础的火山模型，少量读取若干行即返回结果，后者则必须批处理(所谓的向量化执行)，通常还要配合 Pipeline，一次读取某列的几千行这样，因此 MPP 计算引擎，读取完记录，需要极快地对整批数据做集中处理，而不能逐条的读取，反序列化，解码，那样将大大降低系统的吞吐量。

当存储引擎内部需要支持多张表的时候，对于行存来说，处理非常简单，只需要给每行增加 TableID 的前缀即可，这并没有给系统整体增加多少开销，因为反序列化，解码只需针对若干记录即可。这时的多张表，在存储引擎看来，都是统一的 Key Value，表之间并没有什么不同。

可是对于列存来说，首先，每张表的列都是独立存放的，不同的表也包含不同的列，这样表之间的数据摆放，完全不同。假定它也支持主键，那么同样给每行增加 TableID 的前缀，本质上是对向量化执行的打断，因此，TableID 这样的数据，需要存放到元数据。除了 TableID 之外，列存还需要记录每个列的信息(比如 block，segment，zonemap，等等)，并且不同的 Table 之间是完全不同的，而行存就没有这样的问题，所有的 Table 只要通过 TableID 作前缀，就可以，因此列存为什么比行存难，核心点之一在于元数据复杂度远高于行存。以树状视角来看，常见的列存元数据组织看起来像是这样：

|-- [0]dentry:[name="/"]|   |-- [1]dentry:[name="db1"]|   |    |-- [2]dentry:[name="table1"]|   |    |    |-- [3]dentry:[name="segment1"]|   |    |    |     |-- [4]dentry:[name="block1"]|   |    |    |     |    |-- col1 [5]|   |    |    |     |    |-- col2 [6]|   |    |    |     |    |-- idx1 [7]|   |    |    |     |    |-- idx2 [8]|   |    |    |     ||   |    |    |     |-- [9]dentry:[name="block2"]|   |    |    |     |    |-- col1 [10]|   |    |    |     |    |-- col2 [11]|   |    |    |     |    |-- idx1 [12]|   |    |    |     |    |-- idx2 [13]

除了元数据的复杂之外，还有崩溃恢复机制，这就是 WAL(Write Ahead Logging)，列存要考虑的事情，也会更多。对于行存来说，所有的表都共享同样的 Key Value 空间，因此就是一个普通的 Key Value 存储所需要的 WAL，记录一个 LSN(Last Sequence Number)水位即可。但如果列存也这么做，就会有一些问题：

上面的图很粗略显示了一个列存 Memtable 的样例，为方便管理，我们认定 Memtable 的每个 Block(Page)只能包含一张表的某列数据。假设在 Memtable 里包含多张表同时写入的数据，由于不同的表写入速度的不同，因此每张表在 Memtable 包含数据的多少也必然不同。如果我们在 WAL 中只记录一个 LSN，这就意味着当发生 Checkpoint 的时候，我们需要把 Memtable 每张表的数据都 Flush 到硬盘，哪怕这张表的数据在 Memtable 中只有 1 行。同时，由于列存的 schema 无法像行存那样完全融入到单一的 Key Value 中，因此，即使一行表数据，也会生成对应的文件，甚至是每列一个文件，在表的数量众多的时候，这会产生大量的碎片文件，导致巨大的读放大。当然，也可以不考虑这么复杂的场景，毕竟，很多列存引擎连 WAL 都还没有，而即使有 WAL 的列存引擎，也大都不这样考虑问题，比如所有表固定到某行数的时候才做 Checkpoint，那么表多的时候，Memtable 可能就会占据大量内存，甚至 OOM。TAE 是 MatrixOne 数据库主要甚至是唯一的存储引擎，它需要承载不仅 AP 还有 TP 的业务，因此对于数据库使用来说，它必须要能够像普通 Key Value 存储引擎那样任意创建表，因此，最直接的方案，就意味着在 WAL 中需要为每张表都维护一个 LSN，也就是说，在统一的 WAL 中，每张表都有自己独立的逻辑日志空间记录自己当前写入的水位。换句话，如果我们把 WAL 看做是一个消息队列，普通行存的 WAL 就相当于只有一个 Topic 的消息队列，而列存的 WAL 则相当于有一堆 Topic 的消息队列，而且这些 Topic 在物理上连续存放，并不像普通消息队列那样各个 Topic 数据独立存放。因此，列存的 WAL，需要更加精细化的设计，才能让它使用方便。

下面正式介绍 TAE 存储引擎的设计。

数据存储

TAE 以表的形式存储数据。每个表的数据被组织成一个 LSM 树。目前，TAE 是一个三层 LSM 树，称为 L0、L1 和 L2。L0 很小，可以完全驻留在内存中，就是上文提到的 Memtable，而 L1 和 L2 都驻留在硬盘上。在 TAE 中，L0 由 transient block 组成，不排序，L1 由 sorted block 组成。传入的新数据总是被插入最新的 transient block 中。如果插入导致该块超过了一个块的最大行数，该块将被按主键排序，并作为 sorted block 刷入 L1。如果被排序的块的数量超过了一个 segment 的最大数量，那么将使用 merge sort 方法按主键进行排序并写入 L2。column block 是 TAE 的最小 IO 单元，目前它是按照固定行数来组织的，对于 blob 列的单独处理，会在后续版本中改进。

L1 和 L2 存放的都是按主键排序的数据。排序的数据之间，主键会有范围重叠。L1 和 L2 的区别在于，L1 是保证 block 内按主键排序，而 L2 则是保证一个 segment 内按主键排序。这里 segment 是一个逻辑概念，它在同类实现中也可以等价为 row group，row set 等。如果一个 segment 有许多更新（删除），它可以被 compact 成一个新的 segment，多个 segment 也可以 merge 成一个新 segment，这些都通过后台的异步任务来完成，任务的调度策略，主要是写放大和读放大之间的权衡——基于此考虑 TAE 不推荐提供 L4 层，也就是说全部 segment 按照主键全排序，尽管从技术上可以这么做(通过后台异步任务反复 merge，比如 ClickHouse 等列存的行为)。

索引和元数据

跟传统列存一样，TAE 没有引入行存的次级索引，只有在 block 和 segment 级分别引入了 Zonemap(Min/Max 数据)信息，未来也会根据需要增加 Bloom Filter 数据，为查询执行的 Runtime Filter 优化提供支持。作为支撑 TP 的存储引擎，TAE 提供完整的主键约束，包含多列主键和全局自增 ID。TAE 默认为每个表的主键创建一个主键索引。主要功能是在插入数据时做去重满足主键约束，以及根据主键进行过滤。主键去重是数据插入的关键路径。TAE 需要在以下三个方面做出权衡：

1. 查询性能

2. 内存使用

3. 跟上述数据布局的匹配

从索引的粒度来看，TAE 可以有两类，一类是表级索引，另一类是 segment 级。例如，可以有一个表级的索引，或者每个 segment 有一个索引。TAE 的表数据由多个 segment 组成，每个 segment 的数据都经历了从 L1 到 L3，从无序，通过压缩/merge 到有序的过程，这种情况对表级索引非常不友好。所以 TAE 的索引是构建在 segment 级。有两种类型的 segment。一种是可以追加修改的，另一种是不可修改的。对于后者，segment 级索引是一个两级结构，分别是 bloomfilter 和 zonemap。对于 bloomfilter 有两种选择，一种是基于 segment 的 bloomfilter，另一种是基于 block 的 bloomfilter。当索引可以完全驻留在内存中时，基于 segment 的是一个更好的选择。一个可追加修改的 segment 至少由一个可追加的块加上多个不可追加的块组成。可追加的 block 索引是一个常驻内存的 ART-tree 加上 zonemap，而不可追加的则是 bloomfilter 加上 zonemap。

Buffer Manager

严肃的存储引擎需要 Buffer Manager 实现对内存的精细化控制。尽管 Buffer Manager 原理上只是一个 LRU Cache，但是没有数据库会直接采用操作系统 Page Cache 来取代 Buffer Manager，尤其是 TP 类数据库。TAE 用 Buffer Manager 管理内存 buffer，每个 buffer node 是固定大小，它们总共被划分到 4 个区域：

1. Mutable：固定 size 的 buffer，用来存放 L0 的 transient column block

2. SST：给 L1 和 L2 的 block 使用

3. Index：存放索引信息

4. Redo log：用来服务事务未提交数据，每个事务的 local 需要至少一个 Buffer

Buffer Manager 的每个 buffer node 有 Loaded 和 Unloaded 两种状态，当使用者请求 buffer manager 对一个 buffer node 进行Pin操作时，如果该 node 处于 Loaded 状态，那么它的引用计数会增加 1，如果节点处于 Unloaded 状态，它将从硬盘或远程存储读取数据，增加节点引用计数。当内存没有剩余空间时，将采用 LRU 策略把一些 buffer node 换出内存以腾出空间。当使用者卸载Unpin一个 node 时，只需调用节点句柄的 Close。如果引用次数为 0，则该节点将成为被换出内存的候选节点，引用次数大于 0 的节点永远不会被换出。

WAL 和日志回放

如前所述，列存引擎的 WAL 设计会比行存更加复杂。在 TAE 中，redo log 不需要记录每个写操作，但必须在事务提交时记录。TAE 通过使用 Buffer Manager 来减少 io 的使用，对于那些时间不长，可能因为各种冲突而需要回滚的事务，避免任何 IO 事件。它也可以支持长的或大的事务。TAE 的 WAL 的 Log Entry Header 采用如下的格式：

事务 Log Entry 包含如下类型：

大多数事务只有一个 Log Entry。只有那些长的或大的事务可能需要记录多个 Log Entry。所以一个事务的日志可能是 1 个以上 UC 类型的日志条目加上一个 PC 类型的 Log Entry，或者只有一个 AC 类型的 Log Entry。TAE 为 UC 类型的 Log Entry 分配了一个专用 Group。下图是六个已提交事务的事务日志。

一个事务 Log Entry 的 Payload 包括多个 transaction node，正如图中所示。transaction node 包含有多种类型，比如 DML 的 Delete，Append，Update，DDL 的 Create/Drop Table，Create/Drop Database 等。一个 node 是一个原子命令，它可以理解为一个已提交 Log Entry 的 sub-entry 的索引。正如在 Buffer Manager 部分所提到的，所有活动的事务共享固定大小的内存空间，该空间由 Buffer Manager 管理。当剩余空间不足时，一些 transaction node 将被卸载(Unload)。如果是第一次卸载 node，它将作为一个 Log Entry 保存在 Redo Log 中，而当加载时，相应的 Log Entry 将从 Redo Log 回放。这个过程举例说明如下：

图中 TN_1-1 表示事务 Txn1 的第一个 transaction node。在一开始，Txn1 在 Buffer Manager 中注册 transaction node TN_1-1 ，并写入数据 W_1-1 ：

1. Txn2 注册 transaction node TN_2-1 ，并写入数据 W_2-1 ，将 W_1-2 加入 TN_1-1
   

2. Txn3 注册 transaction node TN_3-1 ，并写入数据 W_3-1
   

3. Txn4 注册 transaction node TN_4-1 ，并写入数据 W_4-1 ，将 W_2-2 加入 TN_2-1
   

4. Txn5 注册 transaction node TN_5-1 ，并写入数据 W_5-1
   

5. Txn6 注册 transaction node TN_6-1 ，并写入数据 W_6-1 ，将 W_3-2 加入 TN_3-1 ，将 W_2-3 加入 TN_2-1 ，此时有事务发生提交，将 Commit 信息 C₅ 加入 TN_5-1 ，创建一个 Log Entry，将 C₄ 加入 TN_4-1 ，创建对应的 Log Entry

6. 在 Buffer Manager 中取消注册 TN_4-1 和 TN_5-1 。在将 W_3-3 写入 TN_3-1 之前，内存空间不足，TN_2-1 被 Buffer Manager 选为可以 evict 的候选，它被卸载到 WAL 作为 Log Entry 存入。将 W_3-3 写入 TN_3-1 ，Txn2 在 Buffer Manager 注册 TN_2-2 并写入 W_2-4 ，此时有事务发生提交，写入 Commit 信息 C₁ 到 TN_1-1 并创建对应的 Log Entry，写入 C₆ 到 TN_6-1 并创建对应的 Log Entry。将 W_2-5 写入 TN_2-2 ，给 TN_2-2 增加 A₂ 并创建对应的 Log Entry

通常情况下，Checkpoint 是一个安全点，在重启期间，状态机可以从这个安全点开始应用 Log Entry。Checkpoint 之前的 Log Entry 不再需要，将在适当的时候被物理销毁。一个 Checkpoint 可以代表它所指示范围内的数据等价物。例如，CKP_LSN-11($-\infty$, 10]]等价于从 Entry_LSN=1到 Entry_LSN=10的 Log Entry，该范围内的日志已不再需要。重启时从最后一个 Checkpoint CKP_LSN-11($-\infty$, 10]]开始重放即可。TAE 由于列存的原因，需要一个二级结构记录最后一个 Checkpoint 信息，在 WAL 上用 Group 来区分。

TAE 的实现，将 WAL 和日志回放的部分，专门抽象成独立的代码模块logstore，它对底层日志的存取做了抽象，可以对接从单机到分布式的不同实现，在物理层，logstore所依赖的行为类似消息队列语义。从 MatrixOne 0.6 版本开始，系统架构将演进到云原生版本，对应的日志服务将以shared log形式独立运行，因此届时 TAE 的logstore将略做修改，直接访问外部的shared log服务而不依赖任何本地存储。

事务

TAE 采用 MVCC 机制保证事务 SI 快照隔离机制。对于 SI 来说，每个事务都有一个一致性读取视图 Read View，它是由事务开始时间决定的，所以在事务内读取的数据永远不会反映其他同时进行的事务所做的改变。TAE 提供细粒度乐观并发控制，只有对同一行和同一列的更新才会发生冲突。事务使用的是事务开始时存在的 value 版本，在读取数据时不会对其加锁。当两个事务试图更新同一个 value 时，第二个事务将由于写-写冲突而失败。

在 TAE 中，一个表包括多个 segment，一个 segment 是多个事务共同产生作用的结果。所以一个 segment 可以表示为$[T_{start},T_{end}]$（$T_{start}$是最早的事务的提交时间，而$T_{end}$最新事务的提交时间）。由于 segment 可以被压缩成一个新的 segment，并且 segment 可以被合并成一个新的 segment，我们需要在 segment 的表示上增加一个维度来区分版本 $([T_{start},T_{end}]$, $[T_{create},T_{drop}])$ （$T_{create}$ 是 segment 的创建时间，而$T_{drop}$ 是 segment 的删除时间）。$T_{drop}=0$表示该 segment 没有被丢弃。Block 的表示方法与 segment$([T_{start},T_{end}]$, $[T_{create},T_{drop}])$ 相同。当事务提交的时候，需要根据提交时间来获得它的 Read View：

segment 的产生和变化是由后台异步任务进行的，因此 TAE 将这些异步任务也纳入到事务处理框架中，确保数据读取的一致性，举例如下：

来自 L0 层的 Block $Block{1}_{L_0}$在 $t_1$创建 ，它包含来自 $Txn1,Txn2,Txn3,Txn4$ 的数据。$Block{1}_{L_0}$在$t_{11}$ 开始排序，它的 Read View 是基线加上一个 uncommitted update node。排序和持久化一个 block 可能需要很长的时间。在提交排序的$Block{2}_{L_1}$之前，有两个已提交事务$Txn5,Txn6$和一个未提交事务$Txn7$。当 $Txn7$在$t_{16}$提交时，将会失败，因为$Block{1}_{L_0}$ 已经被终止了。在$(t_{11},t_{16})$之间提交的 update node $Txn5,Txn6$将被合并为一个新的 update node，它将与$Block{2}_{L_1}$ 在 $t_{16}$一起提交。

Compaction 过程会终止一系列的 block 或 segment，同时原子化地创建一个新的 block 或 segment（或者建立索引）。与正常的事务相比，它通常需要很长的时间，而且我们不希望在涉及的 block 或 segment 上阻止更新或删除事务。这里我们扩展了 Read View 的内容，将 block 和 segment 的元数据纳入其中。当提交一个正常的事务时，一旦检测到写操作对应的 block（或者 segment）的元数据被改变（提交），它就会失败。对于一个 Compaction 事务，写操作包括 block（或 segment）的软删除和添加。在事务的执行过程中，每次写入都会检测到写写之间的冲突。一旦出现冲突，事务将被提前终止。

MVCC

再来看 TAE 的 MVCC 版本信息存储机制。数据库的版本存储机制决定了系统如何存储这些版本以及每个版本包含哪些信息。基于数据 Tuple 的指针字段来创建一个 latch free 的链表，称为版本链。这个版本链允许数据库定位一个 Tuple 的所需版本。因此这些版本数据的存放机制是数据库存储引擎设计的一个重要考量。一个方案是采用 Append Only 机制，一个表的所有 Tuple 版本都存储在同一个存储空间。这种方法被用于 Postgres，为了更新一个现有的 Tuple，数据库首先为新的版本从表中获取一个空的 slot，然后，它将当前版本的内容复制到新版本。最后，它在新分配的 slot 中应用对 Tuple 的修改。Append Only 方案的关键决定是如何为 Tuple 的版本链排序，由于不可能维持一个 lock free 的双向链表，因此版本链只指向一个方向，或者从 Old 到 New(O2N)，或者从 New 到 Old(N2O)。另外一个类似的方案称为 Time-Travel，它会把版本链的信息单独存放，而主表维护主版本数据。第三种方案，是在主表中维护 Tuple 的主版本，在一个单独的 delta 存储中维护一系列 delta 版本。这种存储在 MySQL 和 Oracle 中被称为回滚段。为了更新一个现有的 Tuple，数据库从 delta 存储中获取一个连续的空间来创建一个新的 delta 版本。这个 delta 版本包含修改过的属性的原始值，而不是整个 Tuple。然后数据库直接对主表中的主版本进行 In Place Update。

这些方案各有不同的特点，影响它们在 OLTP 工作负载中的表现。对于 LSM Tree 来说，由于它天然就是 Append-only 结构，因此跟第一种较接近。只是版本链的链表未必会体现。例如 RocksDB，所有的写操作都是后期 Merge，因此自然也就是 Key 的多版本（不同的版本可能位于不同的 Level）。在更新量并不大的时候，这种结构简单，很容易达到较好的性能。TAE 则目前选择了第 3 种方案的变种，如下图所示。

这主要是出于以下考虑：在更新量巨大的时候，LSM Tree 结构的旧版本数据会引起较多的读放大，而 TAE 的版本链是由 Buffer Manager 维护，在需要被换出的时候，它会跟主表数据合并，重新生成新的 block。因此在语义上，它是 In-Place Update，但实现上，则是 Copy On Write，这对于云上存储是必须的。重新生成的新 block，它的读放大会较少，这对于发生频繁更新后的 AP 查询会更有利，目前在列存中采用类似机制的还有 DuckDB。当然，另一方面，语义上的 In Place Update 也带来了额外的困难，这在未来的 TAE 系列文章中会逐步介绍。

从本质上来说，TAE 作为一个全新设计和实现的存储引擎，距离成熟还需要时间，但是它的每个组件，都是完全从零搭建，并不断快速演进中。后边的系列文章，我们将逐步就 TAE 在存算分离体系下的调整逐步展开分享。