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_{5} \)加入\(TN_{5-1} \) ，创建一个Log Entry，将\(C_{4}\) 加入\(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_{1} \) 到\(TN_{1-1} \)并创建对应的Log Entry，写入\(C_{6} \) 到\(TN_{6-1} \)并创建对应的Log Entry。将\(W_{5-2} \)写入\(TN_{2-2} \)，给\(TN_{2-2} \)增加\(A_{2} \)并创建对应的Log Entry

通常情况下，Checkpoint是一个安全点，在重启期间，状态机可以从这个安全点开始应用Log Entry。Checkpoint之前的Log Entry不再需要，将在适当的时候被物理销毁。一个Checkpoint可以代表它所指示范围内的数据等价物。例如，\(CKP_{LSN-11}\)(-∞, 10]]等价于从\(Entry_{LSN=1}\)到\(Entry_{LSN=10}\)的Log Entry，该范围内的日志已不再需要。重启时从最后一个Checkpoint \(CKP_{LSN-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在存算分离体系下的调整逐步展开分享。