数据库内核月报 － 2021 / 03

本文简要从存储结构、索引结构和数据更新方式等几个方面介绍当前比较热门的OLAT/HATP列式存储引擎，包括TiFlash、AnalyticDB、ClickHouse和SqlServer。

TiFlash

存储结构和索引结构

TiFlash的列式存储引擎Delta Tree参考了B+ Tree和LSM Tree的设计思想。Delta Tree将数据按照主键划分为Range分区，每个分区称为Segment。Segment通过B+ Tree作为索引。也就是说，B+ Tree索引的叶子节点为Segment。在Segment内部采用类似LSM Tree的分层存储方式，不过采用固定两层的LSM Tree，分别为Delta层和Stable层。Delta层保存增量数据部分，其中，新写入的数据写入Delta Cache中，与LSM Tree的MemTable类似。当Delta Cache写满后，其中的数据刷入Delta层的Pack中，类似LSM Tree的L0层。Stable层类似于LSM Tree的L1层，其中的数据以主键和版本号排序。Delta层的Pack和Stable层需要做全量合并，得到新的Stable层数据。当Segment中的数据量超过阈值，就会做类似B+ Tree叶子节点的分裂操作，分裂成两个Segment。同时，如果相邻的Segment中的数据量都比较小，也会将相邻的Segment合并成一个Segment。

图1. TiDB Delta Tree[2]

数据更新方式

TiFlash面向OLAP场景，支持OLTP场景下的更新操作，可以采用TiDB的Raft Log作为WAL日志回放出事务更新操作；同时，也支持批量数据写入。与TiKV一样，TiFlash采用MVCC实现事务隔离，TiFlash中的数据包含版本号字段作为事务的时间戳。

AnalyticDB

存储结构和索引结构

AnalyticDB存储层采用Lambda架构，数据分为基线数据和增量数据两部分。基线数据中包含索引和数据两部分，增量数据中不包含索引。基线数据采用行列混存的结构，意图兼具行存和列存的优势。具体来说，对于每张表，每k行的数据组成一个Row Group。Row Group中的数据连续存放在磁盘中。整个Row Group中，又将数据按照列（聚集列）分别顺序存放。AnalyticDB会对每列构建一份元数据，用于维护列数据的统计信息（包括Cardinality、Sum和Min/Max等）、字典数据（采用字典编码）以及物理映射等。AnalyticDB默认会对每一列数据建立索引，索引中的Key是列的值，Value是值出现的所有行号集合，采用后台异步构建模式。由于增量数据部分没有索引，随着数据的不断实时写入，增量数据的查询性能会越来越慢。AnalyticDB采用后台任务来合并基线数据和增量数据形成一个新的基线数据，并基于新的基线数据构建全量索引。

图2. AnalyticDB行列混合存储[3]

数据更新方式

AnalyticDB支持实时的Insert、Update和Delete操作。Delete操作采用逻辑删除的方式，使用bitset标记被删除的数据行，在后台的合并任务中会把被逻辑删除的数据做真正的物理删除操作。Update操作被转换为Delete + Insert操作。AnalyticDB采用MVCC多版本控制实现事务隔离，当数据发生Delete或者Update时，AnalyticDB会产生一个新版本的bitset，此时正在运行的查询可以继续使用老版本的bitset，不会被写入阻塞。

ClickHouse

存储结构和索引结构

ClickHouse拥有多种表引擎类型，在这众多的表引擎中，MergeTree是比较有代表性的引擎之一，被广泛使用。MergeTree采用列式存储，类似LSM Tree的架构组织数据。数据导入时被划分为多个Part，每个Part对应一个目录。Part中包含各个列的数据，每个列都有独立的文件。后台会调度合并任务，将多个小的Part合并成更大的Part，类似LSM Tree的合并过程。 Part中包含几类文件：

1. 数据文件（.bin），每一列的数据都分别存储在数据文件，一般以主键排序。数据文件中划分为若干个Block，Block是列存文件的压缩单元。每个Block又会包含若干个索引Granularity，用于索引定位。
2. 索引文件（.idx），索引文件又分为主键索引和二级索引：
   • MergeTree的主键索引与传统数据库的主键索引有所不同，MergeTree的主键索引只负责排序，但是不会去重。主键索引文件中，存储的是每一个Granularity中起始行的主键值，可以在扫描过程中过滤部分Granularity。
   • MergeTree的二级索引文件中可以存储Granularity的minmax、set、bloom_filter、ngrambf_v1等信息。
3. Mark文件（.mrk），由于索引文件是对Granularity进行索引，类似于逻辑索引。Mark文件记录Granularity在数据文件中的物理偏移，类似于将逻辑索引转换成物理索引。

数据更新方式

MergeTree对于批量导入支持较好，对OLTP级事务更新仅有限支持。MergeTree存储引擎对数据实时可见要求非常高的场景是不太友好的。

SqlServer

存储结构和索引结构

SQL Server从SQL Server 2012开始涉及AP场景，当初只是提供了Read-Only Columnstore Index。从SQL Server 2016开始，SQL Server引入了三方面的改进，本文主要分析基于In-memory OLTP Hekaton的列存索引这一个方面。在SQL Server Hekaton中，列存是作为行存的索引存在，也就是说可以针对行存中的部分列做列存索引。因此，在做OLTP行存事务处理时，数据也会实时同步更新到列存中。对于列存索引，也是分为增量部分和基线部分。数据插入列存时，首先进入增量部分，后台会根据数据的冷热程度（数据更新的频繁程度），将冷数据合并到基线部分，而热数据会留在增量部分。基线部分数据采用行列混合存储形式，每个Row Group作为一个压缩单元，Row Group内是列式存储。数据在从增量部分合并到基线部分时会分配RowID，通过RowID可以做基线数据的逻辑删除操作。

图3. 基于Hekaton的列存索引[5]

数据更新方式

与Hekaton的行存使用相同的日志实时做事务处理，使用MVCC实现事务隔离。

整体对比

| | TiFlash | AnalyticDB | ClickHouse | SqlServer || — | — | — | — | — |
| 存储结构 | Delta Tree，磁盘行列混存 | 增量 + 基线，磁盘行列混存 | MergeTree，磁盘列存 | Hekaton列存索引，内存行列混存 |
| 索引结构 | 主键索引 | 全列倒排索引 | 主键索引 + 二级索引 | 本身是行存的索引，可以利用行存的其他索引 |
| 数据更新方式 | MVCC事务隔离，支持TP型事务和批量导入 | MVCC事务隔离，支持TP型事务 | 批量导入友好，有限支持更新 | 与行存保持一致 |
| 数据压缩 | 通用压缩 | 字典压缩 | 通用压缩 | RLE等专用压缩 |

参考文献

[1] TiDB 的列式存储引擎
[2] TiDB: A Raft-based HTAP Database
[3] AnalyticDB: Realtime OLAP Database System at Alibaba Cloud
[4] ClickHouse
[5] Real-time analytical processing with SQL server