关于数据库:关于TAETransactional-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(-∞, 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在存算拆散体系下的调整逐渐开展分享。