大背景

本系列产品会著眼在 TiFlash 另一方面，听众需要有许多对 TiDB 基本的科学知识。能透过这三首诗介绍 TiDB 管理体系里的许多基本概念《 说储存 》、《 说排序 》、《 谈运维 》。

那时的主人公 — TiFlash 是 TiDB HTAP 型态的关键性模块，它是 TiKV 的列存扩充，透过 Raft Learner 协定触发器拷贝，但提供与 TiKV 一样的镜像隔绝全力支持。他们用这个构架化解了 HTAP 情景的隔绝性和列存并行的问题。自 5.0 导入 MPP 后，也进一步进一步增强了 TiDB 在动态预测情景下的排序快速潜能。

上图叙述了 TiFlash 总体方法论模块的分割，透过 Raft Learner Proxy 网络连接到 TiDB 的 multi-raft 管理体系中。他们能仔细分析着 TiKV 来看：排序层的 MPP 能在 TiFlash 之间做数据传输，保有大列佩季哈区的预测排序潜能；作为列存发动机，他们有一个 schema 的模块负责管理与 TiDB 的表结构进行并行，将 TiKV 并行回来的数据切换为列的方式，并载入到列存发动机中；最上面的几块，是接著会如是说的列存发动机，他们将它重新命名为 DeltaTree 发动机。

有稳步关注 TiDB 的使用者可能以后写作过 《TiDB 的Chalancon储存发动机是如何同时实现的？》 这首诗，上周随着 TiFlash 开放源码 ，也有捷伊使用者想更多地介绍 TiFlash 的外部同时实现。这首诗会从更吻合标识符微观，来如是说 TiFlash 外部同时实现的许多技术细节。

这里是 TiFlash 内许多重要的模块分割和它相关联在标识符中的边线。在那时的撷取和先期的系列产品里，会渐渐对里头的模块积极开展如是说。

TiFlash 模块相关联的标识符边线dbms/

└── src

├── AggregateFunctions, Functions, DataStreams表达式、微分├── DataTypes, Columns, Core类别、列、Block├── IO, Common, EncryptionIO、远距类├── DebugTiFlash Debug 远距表达式├── FlashCoprocessor、MPP 方法论├── Server程序开启出口处├── Storages

│ ├── IStorage.hStorage 抽象化│ ├── StorageDeltaMerge.hDeltaTree 出口处│ ├── DeltaMergeDeltaTree 外部各模块│ ├── PagePageStorage│ └── TransactionRaft 网络连接、Scehma 并行等。 待重构 https://github.com/pingcap/tiflash/issues/4646└── TestUtilsUnittest 远距类

TiFlash 中的许多基本元素抽象化

TiFlash 这款发动机的标识符是 18 年从 ClickHouse fork。ClickHouse 为 TiFlash 提供了一套性能十分强劲的向量化执行发动机，他们将其当做 TiFlash 的单机的排序发动机使用。在此基础上，他们增加了针对 TiDB 前端的对接，MySQL 兼容，Raft 协定和集群模式，动态更新列存发动机，MPP 构架等等。虽然和原本的 Clickhouse 已经完全不是一回事，但标识符自然地 TiFlash 标识符继承自 ClickHouse，也沿用着 CH 的许多抽象化。比如：

IColumn 代表内存里头以列方式组织的数据。IDataType 是数据类别的抽象化。Block 则是由多个 IColumn 组成的数据块，它是执行过程中，数据处理的基本单位。

在执行过程中，Block 会被组织为流的方式，以 BlockInputStream 的方式，从储存层 流入 排序层。而 BlockOutputStream，则一般从执行发动机往储存层或其他节点 写出 数据。

IStorage 则是对储存层的抽象化，定义了数据载入、读取、DDL 操作、表锁等基本操作。

DeltaTree 发动机

虽然 TiFlash 基本沿用了 CH 的向量化排序发动机，但是储存层最终没有沿用 CH 的 MergeTree 发动机，而是重新研发了一套更适合 HTAP 情景的列存发动机，他们称为 DeltaTree，相关联标识符中的 ” StorageDeltaMerge “。

DeltaTree 发动机化解的是什么问题

A. 原生全力支持高频率数据载入，适合对接 TP 系统，更好地全力支持 HTAP 情景下的预测工作。

B. 全力支持列存动态更捷伊前提下更好的读性能。它的设计目标是优先考虑 Scan 读性能，相对于 CH 原生的 MergeTree 可能部分牺牲写性能

C. 符合 TiDB 的事务模型，全力支持 MVCC 过滤

D. 数据被分片管理，能更方便的提供许多列存特性，从而更好的全力支持预测情景，比如全力支持 rough set index

为什么他们说 DeltaTree 发动机具备上面特性呢 ？回答这个疑问以后，他们先回顾下 CH 原生的 MergeTree 发动机存在什么问题。MergeTree 发动机能理解为经典的 LSM Tree（Log Structured Merge Tree）的一种列存同时实现，它的每个 “part 文件夹” 相关联 SSTFile（Sorted Strings Table File）。最开始，MergeTree 发动机是没有 WAL 的，每次载入，即使只有 1 条数据，也会将数据需要生成一个 part。因此如果使用 MergeTree 发动机承接高频载入的数据，磁盘上会形成大量碎片的文件。这个时候，MergeTree 发动机的载入性能和读取性能都会出现严重的波动。这个问题直到 2020 年，CH 给 MergeTree 发动机导入了 WAL，才部分缓解这个压力 ClickHouse/8290 。

那么是不是有了 WAL，MergeTree 发动机就能很好地承载 TiDB 的数据了呢？还不足够。因为 TiDB 是一个透过 MVCC 同时实现了 Snapshot Isolation 级别事务的关系型数据库。这就决定了 TiFlash 承载的负载会有比较多的数据更新操作，而承载的读请求，都会需要透过 MVCC 版本过滤，筛选出需要读的数据。而以 LSM Tree 方式组织数据的话，在处理 Scan 操作的时候，会需要从 L0 的所有文件，和其他层中 与查询的 key-range 有 overlap 的所有文件，以堆排序的方式合并、过滤数据。在合并数据的这个入堆、出堆的过程中， CPU 的分支经常会 miss，cache 命中也会很低。测试结果表明，在处理 Scan 请求的时候，大量的 CPU 都消耗在这个堆排序的过程中。

另外，采用 LSM Tree 结构，对于过期数据的清理，通常在 level compaction 的过程中，才能被清理掉（即 Lk-1 层与 Lk 层 overlap 的文件进行 compaction）。而 level compaction 的过程造成的写放大会比较严重。当后台 compaction 流量比较大的时候，会影响到前台的载入和数据读取的性能，造成性能不稳定。

MergeTree 发动机上面的三点：载入碎片、Scan 时 CPU cache miss 严重、和清理过期数据时的 compaction ，造成基于 MergeTree 发动机构建的带事务的储存发动机，在有数据更捷伊 HTAP 情景下，读、写性能都会有较大的波动。

DeltaTree 的化解思路和模块分割

在看同时实现以后，他们来看看 DeltaTree 的疗效如何。上图是 Delta Tree 与基于 MergeTree 同时实现的带事务全力支持的列存发动机在不同数据量（Tuple number）和不同更新 TPS (Transactions per second) 下的读 (Scan) 耗时对比。能看到 DeltaTree 在这个情景下的读性能基本能达到后者的两倍。

那么 DeltaTree 具体面对上述问题，是如何设计的呢？

首先，他们在表内，把数据按照 handle 列的 key-range，横向分割进行数据管理，每个分片称为 Segment。这样在 compaction 的时候，不同 Segment 间的数据就独立地进行数据整理，能减少写放大。这方面与 PebblesDB[1] 的思路有点类似。

另外，在每个 Segment 中，他们采用了 delta-stable 的方式，即最捷伊修改数据载入的时候，被组织在一个写优化的结构的末尾（ DeltaValueSpace.h ），定期被合并到一个为读优化的结构中（ StableValueSpace.h ）。Stable Layer 存放相对老的，数据量较大的数据，它不能被修改，只能被 replace。当 Delta Layer 写满之后，与 Stable Layer 做一次 Merge（这个动作称为 Delta Merge），从而得到捷伊 Stable Layer，并优化读性能。很多全力支持更捷伊列存，都是采用类似 delta-stable 这种方式来组织数据，比如 Apache Kudu[2]。有兴趣的听众还能看看《Fast scans on key-value stores》[3] 的论文，其中对于如何组织数据，MVCC 数据的组织、对过期数据 GC 等方面的优劣取舍都做了预测，最终作者也是选择了 delta-main 加列存这样的方式。

Delta Layer 的数据，他们透过一个 PageStorage 的结构来储存数据，Stable Layer 他们主要透过 DTFile 来储存数据、透过 PageStorage 来管理生命周期。另外还有 Segment、DeltaValueSpace、StableValueSpace 的元信息，他们也是透过 PageStorage 来储存。上面三者分别相关联 DeltaTree 中 StoragePool 这一数据结构的 log, data 和 meta。

PageStorage 模块

上面提到， Delta Layer 的数据和 DeltaTree 储存发动机的许多元数据，这类较小的数据块，在序列化为字节串之后，作为 “Page” 载入到 PageStorage 来进行储存。PageStorage 是 TiFlash 中的一个储存的抽象化模块，类似对象储存。它主要设计面向的情景是 Delta Layer 的高频读取：比如在 snapshot 上，以 PageID （或多个 PageID） 做点查的情景；和相对于 Stable Layer 较高频的载入。PageStorage 层的 “Page” 数据块典型大小为数 KiB～MiB。

PageStorage 是一个比较复杂的模块，那时先不如是说它外部的构造。听众能先理解 PageStorage 至少提供以下 3 点功能：

提供 WriteBatch 接口，保证载入 WriteBatch 的原子性提供 Snapshot 功能，能获取一个不阻塞写的只读 view提供读取 Page 外部分数据的潜能（只读选择的列数据）

读索引 DeltaTree Index

前面提到，在 LSM-Tree 上做多路归并比较耗 CPU，那他们是否能避免每次读都要重新做一次呢？答案是能的。事实上有许多内存数据库已经实践了类似的思路。具体的思路是，第一次 Scan 完成后，他们把多路归并算法产生的信息想办法存下来，从而使下一次 Scan 能重复利用。这份能被重复利用的信息他们称为 Delta Index，它由一棵 B Tree 同时实现。利用 Delta Index，把 Delta Layer 和 Stable Layer 合并到一起，输出一个排好序的 Stream。Delta Index 帮助他们把 CPU bound、而且存在很多 cache miss 的 merge 操作，转化为大部分情况下许多连续内存块的 copy 操作，进而优化 Scan 的性能。

Rough Set Index

很多数据库都会在数据块上加统计信息，以便查询时能过滤数据块，减少不必要的 IO 操作。有的将这个远距的结构称为 KnowledgeNode、有的叫 ZoneMaps。TiFlash 参考了 InfoBright [4] 的开放源码同时实现，采用了 Rough Set Index 这个名字，中文叫粗粒度索引。

TiFlash 给 SelectQueryInfo 结构中添加了一个 MvccQueryInfo 的结构，里头会带上查询的 key-ranges 信息。DeltaTree 在处理的时候，首先会根据 key-ranges 做 segment 级别的过滤。另外，也会从 DAGRequest 中将查询的 Filter 转化为 RSFilter 的结构，并且在读取数据时，利用 RSFilter，做 ColumnFile 中数据块级别的过滤。

在 TiFlash 内做 Rough Set Filter，跟一般的 AP 数据库不同点，主要在还需要考虑粗粒度索引对MVCC正确性的影响。比如表有三列 a、b 和载入的版本 tso，其中 a 是主键。在 t0 时刻载入了一行 Insert (x, 100, t0)，它在 Stable VS 的数据块中。在 t1 时刻载入了一个删除标记 Delete(x, 0, t1)，这个标记存在 Delta Layer 中。这时候来一个查询 select * from T where b = 100，很显然如果他们在 Stable Layer 和 Delta Layer 中都做索引过滤，那么 Stable 的数据块能被选中，而 Delta 的数据块被过滤掉。这时候就会造成 (x, 100, t0) 这一行被错误地返回给上层，因为它的删除标记被他们丢弃了。

因此 TiFlash Delta layer 的数据块，只会应用 handle 列的索引。非 handle 列上的 Rough Set Index 主要应用于 Stable 数据块的过滤。一般情况下 Stable 数据量占 90% ，因此总体的过滤效果还不错。

标识符模块

上面是 DeltaTree 发动机内各模块相关联的标识符边线，听众能回忆一下前文，它分别相关联前文的哪一部分 ;)

DeltaTree 发动机内各模块相关联的标识符边线dbms/src/Storages/├── PagePageStorage└── DeltaMerge

├── DeltaMergeStore.hDeltaTree 发动机的定义├── Segment.hSegment├── StableValueSpace.hStable Layer├── DeltaDelta Layer├── DeltaMerge.hStable 与 Delta merge 过程├── FileStable Layer 的储存格式├── DeltaTree.h, DeltaIndex.hDelta Index├── Index, Filter, FilterParserRough Set Filter└── DMVersionFilterBlockInputStream.hMVCC Filtering

小结

本首诗主要如是说了 TiFlash 总体的模块分层，和在 TiDB 的 HTAP 情景下，储存层 DeltaTree 发动机如何进行优化的思路。简单如是说了 DeltaTree 内模块的构成和作用，但是略去了许多技术细节，比如 PageStorage 的外部同时实现，DeltaIndex 如何构建、应对更新，TiFlash 是如何网络连接 multi-Raft 等问题。更多的标识符写作内容会在后面的章节中逐步展开，敬请期待。