数据库内核月报 - 2021 / 03

DataBase · 引擎特性 · OLAP/HTAP列式存储引擎概述

本文简要从存储结构、索引结构和数据更新方式等几个方面介绍当前比较热门的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。

tidb 图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采用后台任务来合并基线数据和增量数据形成一个新的基线数据,并基于新的基线数据构建全量索引。

adb 图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可以做基线数据的逻辑删除操作。

sqlserver 图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