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 工作，在最大化伸缩性的同时保障不同负载的互相隔离。在这个前提之下，采纳以列存为根底的构造，能够具备如下长处：
- 很容易对 AP 优化
- 通过引入 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 须要在以下三个方面做出衡量：
- 查问性能
- 内存应用
- 跟上述数据布局的匹配
从索引的粒度来看，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 个区域：
- Mutable：固定 size 的 buffer，用来寄存 L0 的 transient column block
- SST：给 L1 和 L2 的 block 应用
- Index：寄存索引信息
- 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 采纳如下的格局：
| Item | Size(Byte) |
|---|---|
GroupId |
4 |
LSN |
8 |
Length |
4 |
Type |
1 |
事务 Log Entry 蕴含如下类型：
| Type | Datatype | Value | Description |
|---|---|---|---|
AC |
int8 | 0x10 | 残缺的写操作的提交事务 |
PC |
int8 | 0x11 | 由局部写操作组成的已提交事务 |
UC |
int8 | 0x12 | 未提交的事务的局部写操作 |
RB |
int8 | 0x13 | 事务回滚 |
CKP |
int8 | 0x40 | Checkpoint |
大多数事务只有一个 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 回放。这个过程举例说明如下：
图中 TN1-1 示意事务 Txn1 的第一个 transaction node。在一开始，Txn1 在 Buffer Manager 中注册 transaction node TN1-1，并写入数据 W 1-1：
- Txn2 注册 transaction node TN2-1，并写入数据 W 2-1，将 W 1-2 退出 TN1-1
- Txn3 注册 transaction node TN3-1，并写入数据 W 3-1
- Txn4 注册 transaction node TN4-1，并写入数据 W 4-1，将 W 2-2 退出 TN2-1
- Txn5 注册 transaction node TN5-1，并写入数据 W 5-1
- Txn6 注册 transaction node TN6-1，并写入数据 W 6-1，将 W 3-2 退出 TN3-1，将 W 2-3 退出 TN2-1，此时有事务产生提交，将 Commit 信息 C 5 退出 TN5-1，创立一个 Log Entry，将 C 4 退出 TN4-1，创立对应的 Log Entry
- 在 Buffer Manager 中勾销注册 TN4-1 和 TN5-1。在将 W 3-3 写入 TN3-1 之前，内存空间有余，TN2-1 被 Buffer Manager 选为能够 evict 的候选，它被卸载到 WAL 作为 Log Entry 存入。将 W 3-3 写入 TN3-1，Txn2 在 Buffer Manager 注册 TN2-2 并写入 W 2-4，此时有事务产生提交，写入 Commit 信息 C 1 到 TN1-1 并创立对应的 Log Entry，写入 C 6 到 TN6-1 并创立对应的 Log Entry。将 W 2-5 写入 TN2-2，给 TN2-2 减少 A 2 并创立对应的 Log Entry
通常状况下，Checkpoint 是一个平安点，在重启期间，状态机能够从这个平安点开始利用 Log Entry。Checkpoint 之前的 Log Entry 不再须要，将在适当的时候被物理销毁。一个 Checkpoint 能够代表它所批示范畴内的数据等价物。例如，CKPLSN-11(-∞, 10]]等价于从 EntryLSN=1到 EntryLSN=10的 Log Entry，该范畴内的日志已不再须要。重启时从最初一个 Checkpoint CKPLSN-11(-∞, 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：
\((Txn_{commit}\geqslant T_{create}) \bigcap ((T_{drop}= 0) \bigcup (T_{drop}>Txn_{commit})) \)
segment 的产生和变动是由后盾异步工作进行的，因而 TAE 将这些异步工作也纳入到事务处理框架中，确保数据读取的一致性，举例如下：
\(Block1_{L_{0}} \)在 \(t_{1} \)创立，它蕴含来自 \({Txn1,Txn2,Txn3,Txn4} \)的数据。\(Block1_{L_{0}} \)在 \(t_{11} \)开始排序，它的 Read View 是基线加上一个 uncommitted update node。排序和长久化一个 block 可能须要很长的工夫。在提交排序的 \(Block2_{L_{1}} \)之前，有两个已提交事务 \({Txn5,Txn6} \)和一个未提交事务 \({Txn7} \)。当 \(Txn7 \)在 \(t_{16} \)提交时，将会失败，因为 \(Block1_{L_{0}} \) 曾经被终止了。在 \((t_{11}, t_{16}) \)之间提交的 update node \({Txn5,Txn6} \)将被合并为一个新的 update node，它将与 \(Block2_{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 在存算拆散体系下的调整逐渐开展分享。