MatrixOne超融合HTAP数据库的存储引擎设计

导读：本文介绍了MatrixOne向HSTAP迭代的过程中的思考与总结。矩阵起源是一家数据库创业公司，致力于建设开放的开源技术社区，打造服务企业数字化的超融合异构云原生数据库产品MatrixOne，帮助用户降本增效，无需操心一切基础技术挑战而只专注于业务本身。MatrixOne作为从零开始研发的数据库，目标是实现One Size fits Most的超融合HTAP数据库，目前已经积累了50多万行代码，预计2022年下半年发布完整的HTAP引擎供试用。

今天的介绍会围绕下面三点展开：

HTAP的技术路线

MatrixOne的存储架构

MatrixOne的HTAP存储引擎

01HTAP的技术路线

1. HTAP问题与挑战

HTAP指将OLTP和OLAP数据库进行融合，但融合的方式多种多样，同时面临多种问题。数据插入和更新对于OLTP实时可见，而对OLAP存在挑战；OLTP对数据事务可以支持不同隔离级别，OLAP大多没有事务支持。OLTP索引的设计也非常直接，可以设计各种次级索引如HashIndex、BitMapIndex、B-Tree、B+Tree，满足范围类的、数据量不大的range query的查询加速过滤场景。由于OLAP更看重扫描数据的性能、任何索引OLAP上都会产生更大的随机 IO 以及更大的构建开销，导致在OLAP上实现的索引意义不大，它对索引的需求也不明确，在OLAP上更多的索引实现是Zonemap这类简单索引。OLTP对完整性约束的要求非常严格，需要支持如组件去重、唯一键等功能，但OLAP支持的完整性约束的并不多。

2. HTAP分类

OLTP和OLAP满足的是不同场景下的需求，如何将TP和AP进行融合？什么叫做融合？业界的看法多种多样。

首先看学术界对HTAP融合的看法。

下图引用自：

Retrofitting High Availability Mechanism to Tame Hybrid Transaction/Analytical Processing, OSDI 2021.

图中将可以HTAP融合分为两个维度：横轴是数据新鲜度，纵轴是TP transaction性能下降的维度。数据越新鲜，对transaction的影响越大、性能越差，各家厂商的trade off选择不同。

图中划分了三大区域，最左上角的HyPer是慕尼黑工大实验室的闭源产品，它是一个纯内存的HTAP数据库，MemSQL也是纯内存数据库。HyPer和MemSQL选择数据插入即可见，且需要满足事务，这个设计使数据库事务的并发能力受限。

图中中间部分是SQLServer的融合型引擎，数据可见度在百毫秒到几十毫秒左右，性能损耗相对可控。

图中右下部分是各种数据库的组合，可以看到TiDB和Google的F1 Lightning等，这些数据库通过某种方式将数据进行从行到列的转化、分离，数据可见度在秒级甚至更久。但这类系统的存储计算分离，对系统没有损耗。

3. HTAP路线

我们认为，HTAP路线分为两大类：第一类是将现有的OLTP和OLAP进行封装，第二类是从底层存储到计算一步一步地整合成一体化的数据库。可以认为封装型路线将会使用多套数据库系统，融合性路线只使用一套数据库系统。

路线1

图中是路线1的实现，能满足多数需求，本质是中台组件，通过ETL任务实现流式Join将TP和AP连接起来。ETL任务可以利用大数据生态组件，选择很多，这里列举的CDC工具Debezium、消息队列Kafka、流式计算引擎Flink是比较常见的选择，但无论如何都会需要这三样组件结合才能达到将TP内数据整合到AP中的目的。

这个实现方案存在的问题是实时性不好、使用复杂、负载隔离容易、组件多、成本高。我们需要在整个系统前面实现SQL Proxy，将SQL请求区按AP和TP划分后发到不同存储引擎进行处理；如果不实现SQL Proxy，则需要中台的业务开发人员从业务逻辑入手对请求进行分类和拆解。

路线2

路线2的实现上相比路线1具有更好的完整性。通过“MQ”将TP的日志复制到独立的AP引擎中，从存储上看TP和AP是两套独立的存储系统。广义 MQ 指的是数据可以通过MQ同步，也可以通过其他创新的方式同步，比如大家都比较熟悉的TiDB HTAP就是这类实现，TiDB通过Raft Learner实现数据同步，比一般的MQ效果好很多。

路线2的实现完整性、实时性、数据一致性都比路线1更好，且用户只需要面对一个数据库。但是，由于这个实现需要把TP的Binlog/Redo log通过广义MQ传到OLAP存储引擎中进行回放，这里需要TP侧和AP侧的Table一一对应关系成立。

企业内部的数据探索需求常常需要通过大宽表的形式满足，即需要将几十、上百张TP表连成一张大宽表进行数据探索，数据在TP和AP间直接复制和同步，缺少了流式处理的能力，使数据库能覆盖的场景有限。这里的流式处理（Stream）指的是需要完整的Stream SQL能力，可以对数据进行Join处理，将数据链接成一张宽表，不只是将数据从一处传送到另一处。

路线3、4、5并没有直接解决实时地把TP内数据Join成宽表的问题，尝试了从另一个角度解决问题，着眼于数据新鲜度这一指标，对存储引擎进行创新。

路线3

当前很多新数据库都是分布式数据库，分布式数据库都是高可用的。绝大多数提供高可用的方案都是采用复制状态机。从复制状态机的角度来说，我们没有必要把三个副本全部都交给一种引擎。我们可以拆出一个副本来，比如三副本中的两副本可以交给TP，就是行存；另一个副本我们会交给AP，也就是列存。

这个路线相比和路线2类似。路线2中可选择learner参与日志的同步。路线3可以让状态及可以投票的角色（voter）参与到整个系统的共识中。这个方案目前主要停留在学术界，暂时没有产品化的实现。

方案3存在的问题是，如果列存本身没有创新，会影响整个集群的共识，最终影响整个集群的写入性能。

路线4

路线4将AP和TP进一步整合，在引擎内同时存在行列两种存储，行列间进行自动转化。查询引擎方面进一步优化，查询优化器自动选择存储引擎。存储引擎充分融合，共享数据库其他基础设施。

SQL Server是一个具有代表性的路线4实现方案。行存中存储全量数据，列存是行存的索引，使用Bw-tree在内存中存放行存数据。这里认为列存是行存的索引。

SQL Server列存采用Delta(Tail Index)+Main方式，从Delta到Main时分配RowID。Main按照Row Group组织Append Only列存。列存更新时也需要回写行存的RowID，列存回写时会跟行存事务产生竞争，GC时也会竞争。

Oracle也是路线4的一种实现。Oracle采用堆表保存全量数据，行存和列存分别是堆表的索引缓存(内存)。堆表更新数据，先更新Transaction Journal，定期或触发将Transaction Journal写入列存。更新不会影响Layout，阿里云PolarDB也是类似的实现思路。

路线5

在系统中，使用一份数据同时满足TP和AP。

SingleStore是开头论文截图中的MemSQL提供的云原生托数据托管服务，数据存储两份，delta数据以行的格式存储在内存中，将列存数据持久化到文件中，列存数据文件可以被存储到云原生存储内。delta的行存到列存转换是在数据库内部完成的，整体来说是一份数据存储。

HANA也是路线5的一种实现。HANA使用列存同时服务TP和AP，采用Delta+Main结构，Delta面向写优化，Main面向读优化，L1-delta行存，L2-delta appendonly列存。

行存数据落盘时会发生compaction行为，通过合并不断增加写放大对读进行优化。

4. 如何定义HTAP“有多好”

五种实现路线各有优劣。路线1作为中台模式的方案，相对于其他集中实现方案的运维成本是最高的。由于路线1的跨数据组件交互的特点，一致性也难以保障，经常出现一致性问题。路线2到5都可以提供事务一致性的保障，但路线2在强一致读时候会对AP的性能有一定影响，放弃强一致性会获得更高的AP性能。

实效性方面，路线3、4、5由于融合更加紧密，数据的实时性更好；路线2可以实现秒级的准实时同步数据，由于路线1的同步任务是定时任务同步，最快只能实现分钟级的数据实时同步。

路线1和路线2的隔离型更好，可以原生地实现存储和计算隔离。路线3的存储分离，理论上可以做到计算隔离；路线4的存储是隔离的，但计算不能隔离；路线5存储和计算都不分离。

路线1由于使用多套系统、多分存储，使用成本高。路线2使用两套系统、两份存储，分别做高可用多副本，成本比路线1略低；路线3使用一套系统，两份存储，共用一套多副本，存储的冗余性更好；路线4使用两份存储，用一套多副本，存储开销比路线3更大；路线5开销最小，作为一个完整的数据引擎，使用一个引擎、一份存储、一套高可用方案，满足AP和TP两种负载。

80%-90%用户使用路线1即可满足探索式分析、交互式分析的使用场景。路线2-5对实时分析这类对数据实时性要求非常高对场景更加合适。

02MatrixOne的存储架构

MatrixOne预计年终发布完整HTAP引擎试用，届时大家可以看到这方面更加详细的介绍。

1. MatrixOne 存储架构

图中是MatrixOne的存储架构，中间是MatrixCube，是单独开源的。MatrixCube是一个复制状态机，其中有些存储调度的逻辑，可以用Raft机制管理不同存储引擎，当前我们使用开源的Pebble做行存存放Catalog信息，使用矩阵起源自研的AOE（Append Only Columnar Store）引擎做列存。目前我们在使用AOE引擎验证列存和复制状态机结合的可行性，接下来AOE存储引擎将进化到TAE，支持事务处理。

2. MatrixOne AOE

图中是AOE的Layout，在 AOE 的列存中从数据库到Table之间的单元叫做 Segment。Segment与其他数据库中的Group概念类似，内部有Block类似行存B+Tree内的Page，也类似于RocksDB、LSM Tree的Block。Block 在 AOE 中的Segment内部。

一个Segment形成后，Segment内部是全排序的，但是在因为数据会增量、实时地写入，Block在Segment还没有形成时在Block内部排序，但在Block间无法排序。因此，如果有Block之间的排序查询，性能会受到一些影响。

下图中展示了Block和Segment的设计，Segment是由多个Block组成的。Block中存放着一列数据，Segment中的数据区域会把所有列的数据以列的格式分别存放，然后以Block的单元把数据进行包装。

此外Segment的索引区域存放着一些和AP相关的索引，如Sparse Index 或Zone map 等，此外还有一些元数据。

下图中是AOE 与 Raft 交互的场景。我们在做 MatrixOne 最初版本时希望探索列存与Raft机制进行交互。我们已知基于Raft的存储有TiDB、CockroachDB，但是这些都是基于KV的数据库，而我们是把列存与Raft结合。

通常情况下存储引擎和Raft结合起来后会产生4份数据冗余，其中包括 Raft log 两份写入和数据（Apply到状态机后）的两次写入，其中存储的冗余和开销较大。我们希望减少数据冗余，将4份数据减少到2份，Raft log一份、存储引擎（状态机）一份，这就需要存储引擎提供采用外部Log store作为WAL的能力。

除了Raft Log的Last Log Index, Commit Log Index, Applied Log Index外，我们又增加了Checkpoint Log Index。它的作用是什么？MatrixOne的数据在内存中有Mem Table，Mem Table内存写满后落盘形成Block，这个时候需要记录水位信息，方便在整个系统崩溃被恢复时，能够根据 Raft Log 做回放、恢复数据。

除此之外，由于列存的Schema不能像KV那样通过给Key增加Prefix编码来共享同一个namespac，因此它跟Raft结合时，会带来更多的复杂度，比如多个Table（对应多个物理的Storage文件）能否够共享一个Raft group？如果一个Table只能对应一个Raft Group，在创建很多Table的情况下是否会受到影响（正如Apache Kudu所面临的同类问题）？

这些问题带来了更多的水位信息的维护，因此单纯将列存和Raft像NewSQL那样结合，在状态维护上要复杂很多。当前的AOE出于展示目的，采用了Table和Raft Group一一对应的方式，但实际上，在AOE内部的状态管理上，已经做到了跟Raft Group分离，在TAE交付后，它不会跟Raft有任何耦合。

03MatrixOne的HTAP存储引擎

下图是MatrixOne关于HTAP的愿景。前面介绍的几种HTAP路线中，并没有完美的解决方案，我们的目标是实现One Size for Most的超融合HTAP数据库，这里边对应的是两个实现路径：

第一条，我们认为前述的路线一仍然有着巨大的用户惯性，因此我们希望用数据库内置的流计算引擎，把内部的各种表实时Join成一张宽表，同时做到该过程端到端的自动化，避免路线一由中间件组合带来的巨大冗余和维护开销。当然，一个额外的收益是，用户还可以针对某类特定查询做优化，实现增量物化视图能力，这两者在技术上是一起完成的。

第二条，MatrixOne AOE进一步迭代，演化为可支持事务的分析性引擎——TAE（Transactional Analytical Engine），作为MatrixOne内部唯一的存储引擎（尽管MatrixCube具备管理多种存储引擎的能力）。从存储引擎实现的角度来说，这里有个选择的问题：TAE到底是为AP优化的TP，还是为TP优化的AP？我们希望是AP和TP兼顾，通过一个存储引擎的实现服务两个目标，事实上这并不难理解：一个列存结构，如果我们让所有列成为一个Column Family，那么数据的存储布局跟PostgreSQL里的堆表结构，并没有本质区别，而这可以服务TP型负载，如果让每个列都是独立的Column Family，那它就应该跟普通的OLAP没有区别。本质上，我们是希望通过存储引擎底层的灵活设计，实现对多种负载的支持，让用户在创建表的时候可以灵活指定。

一个灵魂拷问是：是否可以用通常OLTP存储引擎中的KV来做TAE？已知这些KV很多是LSM Tree结构，且OLAP引擎很多也是LSM Tree结构，如Clickhouse。

那么，我们能否利用RocksDB实现TAE？这会有两方面的问题：

① TiDB和CockroachDB可以用一个RocksDB这种类型的存储存放所有Table，每个Table仅用Key前缀进行区分即可，但列存不能这样做，因为列存的表Schema不能共享一个namespace，同时管理复杂，它的水位管理和元数据管理都更加复杂，因此不能简单地把RocksDB拿来做列存。

② OLAP大都采用LSM Tree结构，但很少用Key Value Store。如果直接用Key Value直接做列存，这在Scan的时候会导致序列化开销非常大，性能降低几个数量级。如果用Column Family模拟列存，每个Column Family放列存，会导致Key存放开销大。

因此，TAE可以是LSM Tree结构，它对外仍暴露KV接口，但内涵并不是普通KV Store。

《Fast Scans on Key-Value Stores, VLDB 2017》这篇论文中对存储引擎设计和架构进行了很好的总结。

数据的更新有多种方式，传统的B-Tree就是替换更新，数据直接会写到Page中；日志结构更新，如LSM-Tree通过日志的Compaction更新数据；delta main方式存放写优先数据结构，main存放读优先数据，delta可以用行存或内存存放数据，main使用列存存放数据。几种方式各有优劣，替换更新会让scan查询性能更好，但并发受限；日志方式的更新让点查和写入可以承受更高并发，但Compaction带来的GC开销更大；delta main方式的优缺点则是前面两种方案的折中。

列存对scan性能友好，但点查性能受限；行存让点查性能更好，但scan性能受限。版本方面，事务型数据库必然有MVCC结构，MVCC的数据版本有两种方式存放，一种是clustered方式存放，另一种是chained。clustered版本信息和原始数据放在一起，读性能更好，但GC开销大。chained把版本信息作为链表独立存储。更新非常频繁且没有compaction时会对scan不友好。在compaction时把chain 的版本信息，压缩到原始的存储内。

对比下图的两个设计构型：如果在行存引擎中，把数据在Page或Block中按列摆放，是否能够实现TAE？本质上这是为TP优化的引擎，而我们希望保持对AP友好。如果行存中数据按列摆放，每次IO时要访问一个Page，Page内无效的信息也需要进行访问，导致IO性能受影响。而典型的列存一次IO只访问一个列的Block，列存中的AP查询也可以消除随机IO。我们最终选择了列存方案，因为我们希望在配置为AP时，它能达到跟普通OLAP一样的性能。

TAE构型上选择了和AOE类似的结构。再看下图的2个构型：下图中，堆表+次级索引的模式下，文件也可以按照列摆放。堆文件不排序，需要单独的索引存放去重信息，会引入额外开销，在内存中用ART Tree方式存放主键信息。

根据在AOE上的SSB性能测试经验，主键是否排序这一点会对IO性能有不小的影响，因此我们希望引入带排序的构型来提升压测结果。但全排序会导致不断地进行compaction，有写放大问题。我们在平衡各类开销后选择在Segment内部排序，避免了写放大问题，但在Segment之间会存在重叠。由于Segment内部已经进行了排序，接下来在内部建立主键索引时可以不用ART Tree转而用简单的索引结构即可完成索引。

数据更新和版本管理的构型对比：下图左边的堆表结构通过索引访问到堆文件，更新数据时需要删除原记录，同时在文件后面新增，这会导致堆文件体积不断膨胀。PostgreSQL中Vacuum机制就是针对文件膨胀问题的垃圾回收。下图中右边的结构以Segment组织数据，可以做到列数据单独存放，每个列的更新对应一个delta block，其中对应的是数据版本链的信息，版本链会在Compaction过程中存进数据Block中。

以上是MatrixOne的HTAP设计思路，在HTAP版本正式发布后，关于存储数据结构方面的设计会有进一步的详细介绍。

MatrixOne的RoadMap如图，我们在2021年发布了一个版本，其中使用了列存和Raft结合的分布式AOE结构，配合我们自己设计的MPP计算引擎。今年年中我们会发布单机版本的HTAP，同时实现行存的分布式事务；第三季度MatrixOne会开源完整的、支持分布式事务的TAE存储；年终时会发布MatrixOne的流引擎。

MatrixOne的AOE引擎支持多表复杂Join，分组聚合性能表现优秀。0.2.0 Release (2022/01)，是业界最快的SQL分析引擎。

性能表现(On SSB Test): 在未叠加过滤、分区等存储优化手段，同等只PK计算引擎的能力维度下，MO性能表现已优于 ClickHouse/StarRocks。