关于tidb:TiDB-的列式存储引擎是如何实现的

作者：韦万

TiDB 是一款分布式 HTAP 数据库，它目前有两种存储节点，别离是 TiKV 和 TiFlash。TiKV 采纳了行式存储，更适宜 TP 类型的业务；而 TiFlash 采纳列式存储，善于 AP 类型的业务。TiFlash 通过 raft 协定从 TiKV 节点实时同步数据，领有毫秒级别的提早，以及十分优良的数据分析性能。它反对实时同步 TiKV 的数据更新，以及反对在线 DDL。咱们把 TiFlash 作为 Raft Learner 交融进 TiDB 的 raft 体系，将两种节点整合在一个数据库集群中，下层对立通过 TiDB 节点查问，使得 TiDB 成为一款真正的 HTAP 数据库。

为了在列式存储上反对实时更新，咱们专门为 TiFlash 研发了新的列存引擎 Delta Tree。它能够在反对高 TPS 写入的同时，依然能保持良好的读性能。本文为大家具体解释 Delta Tree 的设计思路，欢送探讨。

整体架构

Delta Tree 的架构设计充沛参考了 B+ Tree 和 LSM Tree 的设计思维。从整体上看，Delta Tree 将表数据依照主键进行 range 分区，切分后的数据块称为 Segment；而后 Segment 外部则采纳了相似 LSM Tree 的分层构造。分区是为了缩小每个区的数据量，升高复杂度，咱们前面会看到这个设计带来的微小劣势。

Segment

Segment 的切分粒度通常在 150 万行左右，远超传统 B+ Tree 的 Leaf Node 的大小。Segment 的数量在一台机器上通常在 10 万以内，所以咱们能够把 Segment 的元信息齐全放在内存，这简化了工程实现的复杂度。和 B+ Tree 的叶子节点一样，Segment 反对 Split、Merge。在初始状态，一张表只存在一个 range 为 [-∞, +∞) 的 Segment。

2 Levels LSM Tree

在 Segment 外部，咱们通过相似 LSM Tree 的分层的形式组织数据。因为 Segment 的数据量绝对于其余 LSM Tree 实现要小的多，所以 Delta Tree 只须要固定的两层，即 Delta Layer 和 Stable Layer，别离对应 LSM Tree 的 L0 和 L1。咱们晓得对于 LSM Tree 来说，层数越少，写放大越小。默认配置下，Delta Tree 的实践写放大（不思考压缩）约为 19 倍。因为列式存储间断存储雷同类型的数据，人造对压缩算法更加敌对，在生产环境下，Delta Tree 引擎常见的理论写放大低于 5 倍。

下面介绍了 Delta Tree 的整体架构，上面咱们对 Segment 的外部设计细节做一个具体的探讨。

Pack

Segment 外部的数据管理单位是 Pack，通常一个 Pack 蕴含 8K 行或者更多的数据。关系型数据库的 schema 由多个列定义组成，每个列定义包含 column name，column id，column type 和 default value 等。因为咱们反对 DDL，比方加列、删列、改数据类型等操作，所以不同的 Pack schema 有可能是不一样的。Pack 的数据也由列数据（column data）组成，每个列数据其实就是一维数组。Pack 除了主键列 Primary Keys(PK) 以及 schema 蕴含的列之外，还额定蕴含 version 列和 del_mark 列。version 就是事务的 commit 工夫戳，通过它来实现 MVCC。del_mark 是布尔类型，表明这一行是否曾经被删除。

将 Segment 数据宰割成 Pack 的作用是，咱们能够以 Pack 为 IO 单位和索引过滤单位。在数据分析场景，从存储引擎获取数据的形式都是 Scan。为了进步 Scan 的性能，通常咱们的 IO 块要比拟大，所以每次读 IO 能够读一个或者多个 Pack 的数据。另外通常在剖析场景，传统的行级别的准确索引通常用途不大，然而咱们依然能够实现一些简略的毛糙索引，比方 Min-Max 索引，这类索引的过滤单位也是 Pack。

如果你相熟 TiDB 的架构，会理解 TiKV 的数据是以 Region 为调度单位，Region 是数据以 range 切分进去的虚构数据块。而 Delta Tree 的 Pack 外部的数据是以 (PK, version) 组合字段按升序排序的，与 TiKV 内的数据程序统一。这样能够让 TiFlash 无缝接入 TiDB 集群，复用原来的 Region 调度机制。

Delta Layer

Delta Layer 相当于 LSM Tree 的 L0，它能够认为是对 Segment 的增量更新，所以命名为 Delta。与 LSM Tree 的 MemTable 相似，最新的数据会首先被写入一个称为 Delta Cache 的数据结构，当写满之后会被刷入磁盘上的 Delta Layer。而当 Delta Layer 写满之后，会与 Stable Layer 做一次 Merge（这个动作称为 Delta Merge）失去新的 Sable Layer。

Stable Layer

Stable Layer 相当于 LSM Tree 的 L1，是寄存 Segment 的大部分数据的中央。它由一个不可批改的文件存储，称为 DTFile。一个 Segment 只有一个 DTFile。Stable Layer 同样由 Pack 组成，并且数据以 (PK, version) 组合字段按升序排序。不一样的是，Stable Layer 中的数据是全局有序，而 Delta Layer 则只保障 Pack 内有序。起因很简略，因为 Delta Layer 的数据是从 Delta Cache 写下去的，各个 Pack 之间会有 overlap；而 Stable Layer 的数据则通过了 Delta Merge 动作的整顿，能够实现全局有序。

当 Segment 的总数据量超过配置的容量下限，就会以 Segment range 的中点为决裂点，进行 split，决裂成两个 Segment；如果相邻的两个 Segment 都很小，则可能会被 merge 在一起，变成一个 Segment。

存储形式

Delta Tree 引擎的 Delta Layer 和 Stable Layer 在磁盘的存储形式并不统一，前者应用 PageStorage (PS) 存储，后者应用 DTFile 存储。

PageStorage

PS 相似与对象存储，它存储和治理数据块 Page，Page 其实是一段 bytes。它设计用来存储 Delta Tree 的 Delta Layer 的 Pack 数据以及 Segment 的元数据。PS 反对 Page Get、Insert、Delete、Update 操作，并且反对把多个操作组合为一个 WriteBatch，实现原子性写入。Page 存储在 PageFile 之中，一个 PageFile 能够存储多个 Page。咱们在内存中保护了一份 Page 的元数据 PageMap，通过它能够定位到 Page 存储的具体 PageFile 以及文件 offset，从而反对 Page 的随机读取。

PS 可能会存在一个或者多个 Writable PageFile，当 Writable PageFile 写满之后，会变成 Readonly PageFile。对 Page 的所有更新操作是间接写到 PageFile 的开端，比方 Page 的 Update 操作，是通过在 Writable PageFile 写一个新的 Page，而后在内存的元数据表中，将 PageId 指向新的 Page。随着工夫的推移，PageFile 中会呈现较多有效数据段，所以咱们设计了 GC 线程，在后盾把利用率低的 PageFile 合并，从而晋升读取效率及回收磁盘空间。

Delta Layer 中的 Pack 会被序列化成 Page，存储在 PS 中。通常业务的查问只会波及到一个表的局部列，所以 PS 也反对只读 Page 中的一部分数据。

DTFile

DTFile 在文件系统上的模式是一个文件夹，文件夹外部是规范的列存格局，即一个列应用一个文件来存储。DTFile 是只读的，且对它的读取模式都是程序读取，适宜存储 Stable Layer 的数据。DTFile 在三种状况被生成：别离是 Delta Merge、Segment Split 和 Segment Merge。

• Stable Layer 适宜用 DTFile 存储，而 Delta Layer 更适宜用 PageStorage 存储。次要思考到它们在以下几方面的差别：
• DTFile 用于一个列应用一个文件存储，所以如果须要读写间断的 Pack，能够做列级别的 IO 合并，这非常适合 Stable Layer 的读取和生成模式。
• DTFile 写入实现后是只读文件，如果用于存储 Delta Layer 数据，只能用 Pack 和 DTFile 一一对应的形式，这会造成大量小文件，影响零碎性能。而 PageStorage 把多个 Page 合并存储，没有小文件问题。
• PageStorage 能够对 Page 进行随机读取，和 Delta Layer 的读取模式相符合。
• PageStorage 能够缩小写过程中产生的 IO 次数。DTFile 在写入的时候，须要关上和列数一样多的文件，每个列至多会产生一个 IO。因为从新生成 Stable Layer 的频率并不高，并且写入多个 Pack 能够做列级别的 IO 合并，所以每次的 IO 大小是适合的，应用 DTFile 存储比拟适合。对于 Delta Layer，每次只会写一个 Pack，如果用 DTFile 存储，IO 单位只能是 Pack 的一个列；如果用 PageStorage 存储，咱们能够把 Pack 的所有列数据全副序列化为 Page 一次性写入磁盘，从而缩小 IO 次数。

写优化

TiFlash 目前次要面向实时 OLAP 场景，设计上须要同时反对高频写入和批量写入。高频写入是为了能实时同步 TiKV 在 OLTP 场景下的更新操作；而在数据的批量导入场景，以及刚刚开启 TiFlash 列存同步之后，都须要在短时间内写入大批量数据，所以 Delta Tree 也须要反对批量写入。咱们别离对这两种场景做了不同的解决，以达到最好的成果。

Delta Cache

为了缓解高频写入的 IOPS 压力，咱们在 Delta Tree 的 Delta Layer 中设计了内存 cache，称为 Delta Cache。更新会先写入 Delta Cache，写满之后才会被 flush 到磁盘。而批量写入是不须要写 Delta Cache 的，这种类型的数据会被间接写入磁盘。

你可能会留神到，Delta Cache 的设计有丢数据的危险。因而个别存储引擎在写入数据之前须要先写入 WAL，在重启之后从上一个 flush point 复原。但因为 Delta Tree 是为 TiDB 设计的列存引擎，它充分利用了 TiDB 的特点，即 raft 协定。在 raft 协定中，任何一个更新，会先写入 raft log，期待大多数正本确认之后，才会将这个更新 apply 到状态机（即数据库存储引擎）。所以咱们间接利用 raft log 实现了 WAL，即在 flush 之后才更新 raft log applied index。

继续写入能力

和 LSM Tree 相似，Delta Tree 在数据写入的过程中，应用后盾线程一直把 Delta Layer merge 到 Stable Layer 种。目标是为了将 Delta Layer 的数据量管制在肯定的比例以内，从而保持良好的读性能。Delta Merge 是 Delta Tree 的写放大（write amplification）的次要因素，Delta Tree 的写放大 write amplification ~= (Segment 均匀大小 / Delta 限额)。所以 Delta Merge 频率越高，写放大越大，Delta Layer 比例越小，读性能越好。

TiFlash 的设计理念是心愿尽可能的放弃写入能力，在 写入性能 和 读取性能 之间寻找平衡点。比方在业务写入量特地大的状况下，写入速度太快，如果后盾 Delta Merge 跟不上，就有可能产生 write stall，即阻塞前台的写入。在这种状况下，Delta Tree 会动静的限度写入速度，并且减小 Delta Merge 频率，减小写放大，使得写入和后盾 Delta Merge 从新达到均衡。这会就义局部读和写的性能，然而缓解了极其状况下齐全无奈写入的问题，业务上体验更好。

读优化

Delta Tree 没有间接做成一个列存的 LSM Tree 实现，而是折腾了下面一堆设计，很大一部分起因是为了做读减速。Delta Tree 的 Segment 分区设计能够减小读放大，而 Segment 分区内的双层结构也不便做读减速。

从存储引擎中读取数据对应执行打算中的 Scan 算子。它的次要工作是依据一段 range（比方 [x, y)），返回一个依据 (PK, version) 排好序的数据。过程中次要有三个耗时的局部，而 Delta Tree 的设计对它们都有优化成果。

A. 数据自身的读 IO 与解压缩的耗时。

B. 对多条排序数据流进行多路归并算法自身的耗费，比方常见的最小堆算法。

C. 多路归并之后把多个数据流的数据 copy 到输入流。

缩小读放大

咱们晓得 TiDB 集群的数据，是以 Region 为单位治理的。咱们通过调度 Region 的正本在集群的存储节点（即 TiKV 和 TiFlash）间正当散布，以取得负载平衡和数据高可用。因为 Region 只是逻辑分块，并且在一个节点的 Region 并不是间断的。所以当 Scan 波及大量 Region，必然会有读放大。显然，如果 Region 的数据分布在越多的文件，它的读放大越大。即层数越多，读放大越大。Delta Tree 的通过 Segment 分区升高了区内数据量，缩小层数，从而缩小读放大，即优化了 A 局部的耗时。

读索引 Delta Index

既然多路归并比拟耗时，那咱们是否能够防止每次读都要从新做一次呢？答案是能够的。事实上有一些内存数据库曾经实际了相似的思路。具体的思路是，第一次 Scan 实现后，咱们把多路归并算法产生的信息想方法存下来，从而使下一次 Scan 能够反复利用，只须要解决增量局部即可。这份能够被反复利用的信息咱们称为 Delta Index，它由一棵 B+ Tree 实现。Delta Index 的设计通过了屡次设计迭代，并参考了许多现有的数据库的计划。

1. 首先咱们把 Stable Layer 和 Delta Layer 并排放在一起，这时候每一行数据就领有了能够用于索引的 Tuple Id。而后用相似二级索引的思路，构建一个在内存的 B+ Tree，B+ Tree 的叶子节点的 Entry 同样依照 (PK, version) 的升序排序。Entry 的数据内容为 ((PK, version), is_insert, Tuple Id)。is_insert 示意是 Insert 还是 Delete。
2. 这时候 Segment 内的每一行须要有一个对应的 Entry，内存压力很大，须要做压缩。察看发现，(PK, version) 并不是必须的，因为咱们有 Tuple Id，能够从原始数据取得，不须要放到 Delta Index 中。这对于 PK 比拟大的场景比拟要害。
3. 而 Tuple Id 存在很多间断递增 Id 的景象，因为在 Segment 中，Stable Layer 的数据通常占了绝大多数。所以间断的 N 个 Stable Entry，应用一个 (Tuple Id, N) 代替即可。
4. 进一步察看，Stable Layer 数据的 Tuple Id 肯定是按增序排序的，因为它们在 Stable Layer 中是全局排序的。所以咱们能够只记录 Delta Layer 的数据，并额定记录两个 Delta Entry 之间插入了多少个 Stable Tuple。所以须要把 Stable Layer 和 Delta Layer 的 Tuple Id 进行辨别，别离称为 Stable Id 和 Delta Id。

最终的 Entry 记录的格局为 (is_insert, Delta Id, (Stable Id, N))，Entry 数据量等于 Delta Layer 的数据量。通常状况下，Delta Layer 的数据量占总数据量的 3% 以内，而一个 Entry 只须要 16 个字节，若依照单节点寄存 100 亿数据来估算，大略须要 4.5 GB 内存，内存开销还能够承受。

领有了 Delta Index 记录的信息，Scan 操作就能够很不便的把 Delta Layer 和 Stable Layer 合并到一起，输入一个排好序的 Stream。这里有个小问题，即在两次 Scan 之间，可能会有新的数据写进了 Delta Layer，所以咱们还是须要解决这部分增量数据，把他们更新到 Delta Index 中。因为上一次的后果能够被下一次反复利用，从而平摊了开销，即咱们优化了 B 局部的耗时。

对于 C 局部的耗时，Delta Tree 的次要优化是能够对间断的 Stable Layer 的数据做批量 copy，从而节俭 CPU cycle。LSM Tree 的多路归并算法当然也能够批量 copy，只是实现起来比拟麻烦。且因为 LSM Tree 上层和下层之间的数据量比为 10 倍，而 Delta Tree 通常是 37 倍以上，因而 Delta Tree 批量 copy 的成果会比 LSM Tree 更好。

Delta Tree vs LSM Tree

TiFlash 一开始尝试过基于 LSM Tree 架构实现，然而前面发现它的读性能并不能满足要求，并且还存在其余的问题。所以才启动了 Delta Tree 我的项目。上面是 Delta Tree 与基于 LSM Tree 实现的列存引擎在不同数据量（Tuple number）以及不同更新 TPS (Transactions per second) 下的读 (Scan) 耗时比照。

上面是在应用 ontime 数据集，不同 SQL 的耗时比照。能够看到 Delta Tree 在大部分状况下有更大的劣势，这不仅归功于 Delta Tree 有更好的 Scan 性能，也因为它反对了毛糙索引（如 Min-Max），能够防止读无关数据。

上面是 TiFlash 应用 Delta Tree 引擎，与其余数据库的比照。

如何处理事务

开启了 TiFlash 正本的 TiDB 集群，同样反对事务，并保障和原来 TiKV 一样的隔离级别，这在一个 AP 数据库中是比拟少见的，具体能够参考 TiDB 文档。可能有些同学比拟好奇 TiFlash 是怎么做到的。这里简略介绍比拟重要的点，有趣味的同学能够去看咱们刚刚发在 VLDB 的论文 “TiDB: A Raft-based HTAP Database”。

TiFlash 目前只实时同步 TiKV 的批改，在事务过程中并不会提供数据，所以它不须要提供点查能力，这避开了列存的弱点。

和 TiKV 一样，Delta Tree 中的每一条数据都有版本号字段 version，这个 version 就是事务 的提交工夫戳 commit_ts。所以在查问过程中，依据 query_ts 就能够过滤出合乎 version <= query_ts 的 data snapshot，实现 MVCC。

TiDB 应用的分布式事务模型名为 Percolator，它在事务过程中须要用到锁，一般来说这些锁是须要长久化的。TiKV 当然能够把这些锁长久化到本人的存储 RocksDB 中，然而 TiFlash 的列存 Delta Tree 无奈高效反对 K-V 模式的高 TPS、低提早的读操作。TiFlash 目前的解决方案也很简略，既然这些锁不不便长久化，那就放内存好了。咱们只会把在事务中曾经提交了的批改写入 Delta Tree 存储，没有提交的事务放在内存。须要留神的是，这里并不放心这些锁数据和未提交数据的失落，有两个机制保障：

1. 如前所述，所有的数据都当时落地到了 raft log。内存没有被长久化的局部，重启后能够从 raft log 复原。
2. 在内存的状态，包含锁和没有提交的数据，会定期被保留一份正本到磁盘，而后向前推动 raft log applied index。重启后从磁盘复原正本到内存。

结语

始终以来，在线上业务零碎和剖析零碎之间存在着一个微小的技术鸿沟，即数据的更新无奈实时顺畅的流动。外围起因是，剖析数据库的存储通常更新能力十分差，设想一下把 MySQL binlog 实时同步到 Hive 的苦楚。Delta Tree 列式存储引擎完满的解决了这个问题，让最适宜剖析场景的列式存储也能实时更新。

而 TiDB 通过引入了 TiFlash，在一个数据库系统内集成了行存与列存，让实时业务数据分析变得非常简单。你甚至能够在一个 SQL 之内同时应用行存与列存的数据，并且保证数据严格统一。在 TiDB 中，取得这个能力只须要一条 SQL: alter table my_table set tiflash replica 1;。