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

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

上面的图很粗略显示了一个列存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以表的形式存储数据。每个表的数据被组织成一个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列的单独处理，会在后续版本中改进。

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

1. 查询性能

2. 内存使用

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

严肃的存储引擎需要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设计会比行存更加复杂。在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回放。这个过程举例说明如下：

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

1. Txn2注册transaction node TN2-1 ，并写入数据W2-1 ，将W1-2 加入TN1-1

2. Txn3注册transaction node TN3-1 ，并写入数据W3-1

3. Txn4注册transaction node TN4-1 ，并写入数据W4-1 ，将W2-2 加入TN2-1

4. Txn5注册transaction node TN5-1 ，并写入数据W5-1

5. Txn6注册transaction node TN6-1 ，并写入数据W6-1 ，将W3-2 加入TN3-1 ，将W2-3 加入TN2-1 ，此时有事务发生提交，将Commit信息C5 加入TN5-1 ，创建一个Log Entry，将C4 加入TN4-1 ，创建对应的Log Entry

6. 在Buffer Manager中取消注册TN4-1 和TN5-1 。在将W3-3 写入TN3-1 之前，内存空间不足，TN2-1 被Buffer Manager选为可以evict的候选，它被卸载到WAL作为Log Entry存入。将W3-3 写入TN3-1 ，Txn2在Buffer Manager注册TN2-2 并写入W2-4 ，此时有事务发生提交，写入Commit信息C1 到TN1-1 并创建对应的Log Entry，写入C6 到TN6-1 并创建对应的Log Entry。将W2-5 写入TN2-2 ，给TN2-2 增加A2 并创建对应的Log Entry

通常情况下，Checkpoint是一个安全点，在重启期间，状态机可以从这个安全点开始应用Log Entry。Checkpoint之前的Log Entry不再需要，将在适当的时候被物理销毁。一个Checkpoint可以代表它所指示范围内的数据等价物。例如，CKPLSN-11($-\infty$, 10]]等价于从EntryLSN=1到EntryLSN=10的Log Entry，该范围内的日志已不再需要。重启时从最后一个Checkpoint CKPLSN-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时，第二个事务将由于写-写冲突而失败。

来自L0层的Block $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）的软删除和添加。在事务的执行过程中，每次写入都会检测到写写之间的冲突。一旦出现冲突，事务将被提前终止。

再来看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系列文章中会逐步介绍。