数据库内核月报

数据库内核月报 - 2022 / 02

DataBase · 理论基础 · HTAP列存引擎探秘

Author: 顾绅

背景

TP查询和AP查询具有截然不同的特点,促使TP数据库和AP数据库采用不同的设计理念。然而,在一些业务中,事务处理的同时往往会伴随一些分析型的查询,传统的解决方案是由TP数据库进行事务处理,通过ETL将数据导出到AP数据库来服务分析型查询,但是这样的解决方案具有同步延时高、架构复杂、运维难度大、成本高的缺点。在这样的背景下,HTAP数据库应运而生,成为了学术界和工业界关注的热点。 ​

本文中,我们调研了一些有代表性的HTAP数据库列存引擎实现,分析并总结了HTAP列存引擎的设计选择。

SQL Server:基于索引组织表的列存

SQL Server最初是一个OLTP的DBMS,从SQL Server 2012开始逐渐增强了OLAP和In-memory OLTP的能力,经历了从面向数仓的Read Only Column Index到支持更新的Column Index再到In-memory HTAP的发展过程。本节主要关注SQL Server的In-memory HTAP。 ​

image.png

SQL Server通过引入Apollo Engine for AP和Hekaton for In-memory TP来实现In-memory HTAP,其中Hekaton的行存表是基于BwTree的索引组织表,列存和行存通过在行存表中加上一个字段存储每一行对应记录在列索引中的RowID联系在一起,即利用行存的索引来作为列索引的辅助数据结构。

在这样的存储设计下,行存中存储全量数据,列存分为Tail Index和Column Store Index(CSI),其中CSI以列的形式存储绝大部分数据,并以Row Group为单位划分,每个Row Group对应行存中一定数量的记录,Tail Index则索引行存中还没有迁移到CSI的数据(这部分数据被称为tail of the table,这也是被称为Tail Index的原因)。CSI以append-only的方式更新,借助被称为Delete Mask的bitmap标记删除,Tail Index则支持原地更新删除。事务插入数据时,会同时插入行存和Tail Index,并且记录还没有迁移到CSI时是不会分配RowID的,只有迁移到CSI时才会分配RowID。而事务删除数据时,如果记录被Tail Index索引,则直接在行存和Tail Index中删除,如果在CSI中,则需要根据行存中存储的RowID在Delete Mask中标记删除。更新则通过删除+插入实现。列存scan需要扫描CSI,并根据Delete Mask剔除已删除数据,还需要通过Tail Index从行存表中获取未迁移到CSI的数据进行扫描。 ​

image.png

当Tail Index索引的数据达到一定阈值后会将其中较冷的数据迁移到CSI,冷热通过统计信息来判断。同步分为两个阶段:

SQL Server从两个方面来减少数据迁移对行存性能的影响:

CSI中标记删除的记录会影响scan的性能,也会带来额外的内存开销,因此需要进行重整。CSI上的重整由Row Group中标记删除的比例触发(90%),由后台任务将触发重整的Row Group中的有效记录重新插入Tail Index中,随后和其他前台写入的记录一起被迁移到CSI形成新的Row Group,而重整的Row Group则被回收。

这样的存储设计有两个优点:

缺点也很明显:

Oracle:基于堆表的列存

Oracle从12c版本开始就通过在堆表(Heap Table)上建立In-memory Column Index(IMCI)来支持HTAP。实际上包括堆表在内,Oracle中的表一共有三种组织形式:

但Oracle IMCI只能在堆表上建立,后面我们会看到,堆表会给IMCI的建立和维护带来很大的便利。

image.png

Oracle IMCI实际上是堆表在内存中的列式缓存,和原有的行式缓存一起,形成了“一份数据,两种缓存”的架构。堆表中的数据以IMCU(In-memory Compression Unit)的形式缓存在内存中,每个IMCU对应堆表中若干个DataBlock,因为堆表上Insert不会改变原有数据的组织形式,而Update和Delete又可以原地进行,所以实际上IMCU和Datablock之间的映射关系是不会改变的,也不需要额外的数据结构维护这个映射关系。构建IMCI的过程称为Populate,Populate可以在数据库初始化时进行,相当于缓存预热,也可以在运行时进行,相当于数据第一次被访问时加载进缓存。 ​

image.png

每个IMCU还有一个与之对应的SMU(Snapshot Metadata Unit),用于存储一些元信息,比如记录数量,Min/Max等,另外还会存储用于处理更新的Transaction Journal。当堆表中记录发生更新时,不会立即去更新IMCU中的对应内容,而是会在Transaction Journal中记录RowID和System Change Number(SCN,类似Snapshot)。在IMCU上scan时,如果遇到记录的RowID在Transaction Journal中存在,则需要在Transaction Journal中找到当前事务可见的RowID,根据这个RowID去堆表中获取更新后的数据,以此实现事务的一致性和隔离性。 ​

image.png

虽然堆表中的更新可以只写Transaction Journal,但是当Transaction Journal中存储的记录增加时,IMCU上的scan性能也会下降,因此还是需要将堆表中的更新实际应用到IMCU上,这一过程称为Repopulate。由于IMCU和堆表Datablock之间的映射关系是不会改变的,所以Repopulate只需要加载对应的Datablock建立新版本的IMCU来替换旧版本的IMCU。Repopulate会由两种方式触发:

相比SQL Server在索引表上构建类似Delta-Main架构的列索引,在堆表上构建列索引的优势就在于堆表上的Insert/Update/Delete不会影响数据组织形式,因此堆表中DataBlock和对应的列式缓存IMCU之间的映射关系不会改变,带来两个优点:

SAP HANA:同时服务TP和AP的列存

SAP HANA是Delta-Main架构的HTAP数据库,以列的方式存储一份数据,并以列存同时服务TP和AP查询。其中Main Store是面向读优化的,而Delta Store是面向写优化的,Delta Store进一步分为L1-delta和L2-delta两层,L1-delta是行存,支持高效更新,而L2-delta则是append-only方式更新的列存。 ​

73811F80-F400-4119-BAF4-892D0FF315AB.png

数据在L2-delta和Main Store中并不是使用朴素的列式存储,而是使用Domain Coding的方式压缩列式存储。SAP HANA会为每一层中的每一列的所有字段构建一个字典,并为每一个字段分配一个Value ID,每一列不再存储列的原始数据,而是将对应的Value ID存储在Data Vector中,并且采用Bit Packing压缩。SAP HANA还支持在Bit Packing的基础上对Data Vector应用其他压缩方式,比如RLE,Sparse Encoding,Indirect Encoding等。面向写优化的L2-delta的字典是无序的,而面向读优化的Main Store的字典是有序的,有序字典还可以进一步使用前缀编码。 ​

更新的数据会先写入到L1-delta中,L1-delta的数据达到阈值后进行L1-to-L2-delta Merge,以append-only的方式将记录合并到L2-delta。合并记录时会首先检查L2-delta的字典中是否已经包含要迁移的字段,如果包含则直接将对应Value ID追加写入L2-delta的Data Vector,否则需要先将字段追加写入到字典并分配Value ID。L2-delta的数据达到阈值后进行L2-delta-to-main Merge,将L2-delta和Main Store的字典合并并排序,再合并两层的Data Vector,回收事务不可见的无效数据。 ​

15E7D1AA-2BFF-404F-8372-038A6CCAE925.png

FBE8D72D-6C95-4C69-9944-F57FEC7BF101.png

列存scan需要扫描三层,扫描L2-delta和Main Store时先扫描字典,然后根据得到的Value ID扫描Data Vector得到对应记录,最后归并得到事务可见的正确结果。SAP HANA还可以构建Inverted Index,存储Value ID到Data Vector中出现这个Value ID的位置,加速根据Value ID搜索对应记录的过程。 ​

SAP HANA最初是一个全内存的数据库,通过redo和savepoint做持久化,随着数据量的增大,又引入了磁盘的存储形式(Piecewise columnar access),虽然各个模块可以在全内存形式和磁盘形式之间转换,但是因为存储格式的差异,转换的开销很大,难以在不同工作负载下进行动态调整。因此SAP HANA引入了统一持久化格式(Unified Persistency Format),统一持久化格式提供了一系列兼容字节寻址的基于页的基本存储单元,列存的各个模块通过这些基本存储单元进行组织,在全内存形式和磁盘形式之间转换时不需要改变存储格式,只需要在内存中分配连续的内存将磁盘上的内容拷贝到内存中,或者将内存中的数据写入磁盘。 ​

20210602175020.jpg

SAP HANA这样的设计优势和缺陷都很明显,优势是:

缺陷是由于没有行存的聚簇索引,点查询和unique check的代价比较高,并且列存scan时需要归并获得正确的查询结果,效率较低。

TiFlash:与行存松耦合的列存

TiDB是基于Raft的HTAP数据库,行存数据存储在TiKV中,列存数据存储在TiFlash中,行存和列存的松耦合,通过异步复制Raft log的方式将更新从行存同步到列存,列存不参与Raft协议的日志提交和leader选举,因此列存几乎不会对行存产生影响。 ​

TiFlash根据主键范围将表划分为不同的partition,每个partition采用类似LSM-tree的Delta tree存储。划分partition的目的是为了减少一个Delta tree存储的数据量,使得Delta tree只需要两层,相对多层的LSM-tree能有效减少读放大。随着数据量的变化,partition也会被进一步被划分或合并,保持每个partition的数据量在一定范围内。 ​

0C79500F-D37C-46C8-871E-1B51695C872D.png

Delta tree中的两层分别被称为Delta Space和Stable Space,其中Delta Space中的数据是无序的,和Raft log中同步的顺序一致,而Stable Space中的数据是全局有序的。更新会以追加的方式写入内存中的Delta Cache,写满之后持久化到磁盘上的Delta Space,当Delta Space写满后则会和Stable Space进行合并。列上的scan需要扫描Delta Space中的多个文件和Stable Space,由于采用追加写入的更新方式,扫描的结果中一条记录可能存在多个版本,需要进行归并得到事务可见的正确结果。 ​

由于Delta Space中数据是无序的,因此Delta Space和Stable Space合并以及scan后归并得到正确结果的过程相对LSM-tree会产生很大的额外开销,Delta tree通过引入基于B+tree的Delta Index来解决这两个问题。Delta Index以主键顺序索引Delta Space中的每条记录。为了节省内存开销,Delta Index中存储的是Delta RowID到(Stable RowID,N)的映射,通过Delta RowID可以很方便地获得对应Delta Space记录的主键实现顺序索引,而(Stable RowID,N)则表示了Delta Index索引中相邻两条Delta Space记录范围内的Stable Space记录,因为Stable Space的数据全局有序,因此范围内的记录一定是连续的,可以简化表示。借助Delta Index,Delta tree实现了全局逻辑有序,合并和scan后的整合都可以高效进行。 ​

HTAP列存引擎设计选择

根据对上述四种HTAP列存引擎的调研,我们分析HTAP列存引擎的设计选择本质上就是回答三个问题:

参考文献

[1] Larson P Å, Clinciu C, Hanson E N, et al. SQL server column store indexes[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. 2011: 1177-1184.

[2] Larson P A, Clinciu C, Fraser C, et al. Enhancements to SQL server column stores[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 2013: 1159-1168.

[3] Larson P Å, Birka A, Hanson E N, et al. Real-time analytical processing with SQL server[J]. Proceedings of the VLDB Endowment, 2015, 8(12): 1740-1751.

[4] Lahiri T, Chavan S, Colgan M, et al. Oracle database in-memory: A dual format in-memory database[C]//2015 IEEE 31st International Conference on Data Engineering. IEEE, 2015: 1253-1258.

[5] Oracle Database In-Memory with Oracle Database 19c Technical Overview https://www.oracle.com/technetwork/database/in-memory/overview/twp-oracle-database-in-memory-2245633.pdf

[6] Sikka V, Färber F, Lehner W, et al. Efficient transaction processing in SAP HANA database: the end of a column store myth[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. 2012: 731-742.

[7] Sherkat R, Florendo C, Andrei M, et al. Page as you go: Piecewise columnar access in SAP HANA[C]//Proceedings of the 2016 International Conference on Management of Data. 2016: 1295-1306.

[8] Sherkat R, Florendo C, Andrei M, et al. Native store extension for SAP HANA[J]. Proceedings of the VLDB Endowment, 2019, 12(12): 2047-2058.

[9] Huang D, Liu Q, Cui Q, et al. TiDB: a Raft-based HTAP database[J]. Proceedings of the VLDB Endowment, 2020, 13(12): 3072-3084.