随着近期 TiFlash 开源，有更多的人想理解 TiFlash 是如何构建的。本次分享会让读者对 TiFlash 整体有初步认知，以及在 TiDB 的 HTAP 场景下，存储层 DeltaTree 引擎如何进行优化的设计思路以及其子模块。作者：黄俊深，PingCAP TiFlash 资深研发工程师
一、背景
本系列会聚焦在 TiFlash 本身，读者须要有一些对 TiDB 根本的常识。能够通过这三篇文章理解 TiDB 体系里的一些概念《说存储》、《说计算》、《谈调度》。
本文的配角 — TiFlash 是 TiDB HTAP 状态的要害组件，它是 TiKV 的列存扩大，通过 Raft Learner 协定异步复制，但提供与 TiKV 一样的快照隔离反对。咱们用这个架构解决了 HTAP 场景的隔离性以及列存同步的问题。自 5.0 引入 MPP 后，也进一步加强了 TiDB 在实时剖析场景下的计算减速能力。
上图形容了 TiFlash 整体逻辑模块的划分。咱们能够对照着 TiKV 来看：TiFlash 整体通过 Raft Learner Proxy 接入到 TiDB 的 multi-Raft 体系中；计算层的 MPP 可能在 TiFlash 之间做数据交换，领有更强的剖析计算能力；作为列存引擎，咱们有一个 schema 的模块负责与 TiDB 的表构造进行同步，将 TiKV 同步过去的数据转换为列的模式，并写入到列存引擎中；最上面的一块，是稍后会介绍的列存引擎，咱们将它命名为 DeltaTree 引擎。
有继续关注 TiDB 的用户可能之前浏览过《TiDB 的列式存储引擎是如何实现的？》这篇文章，随着 TiFlash 开源，也有新的用户想更多地理解 TiFlash 的外部实现。这篇文章会从更靠近代码层面，来介绍 TiFlash 外部实现的一些细节。
上面是 TiFlash 内一些重要的模块划分以及它们对应在代码中的地位。在后续的源码解读系列里，会逐步对外面的模块发展介绍。
dbms/
└── src
├── AggregateFunctions, Functions, DataStreams # 函数、算子
├── DataTypes, Columns, Core # 类型、列、Block
├── IO, Common, Encryption # IO、辅助类
├── Debug # TiFlash Debug 辅助函数
├── Flash # Coprocessor、MPP 逻辑
├── Server # 程序启动入口
├── Storages
│ ├── IStorage.h # Storage 形象
│ ├── StorageDeltaMerge.h # DeltaTree 入口
│ ├── DeltaMerge # DeltaTree 外部各个组件
│ ├── Page # PageStorage
│ └── Transaction # Raft 接入、Schema 同步等。└── TestUtils # Unittest 辅助类 二、TiFlash 中的一些根本元素形象
TiFlash 这款引擎的代码是 18 年从 ClickHouse fork 下来的。ClickHouse (以下简称为 CH) 为 TiFlash 提供了一套性能非常强劲的向量化执行引擎，咱们将其当做 TiFlash 的单机的计算引擎应用。在此基础上，咱们减少了针对 TiDB 前端的对接，MySQL 兼容，Raft 协定和集群模式，实时更新列存引擎，MPP 架构等等。尽管和本来的 CH 曾经齐全不是一回事，但代码天然地 TiFlash 代码继承自 CH，也沿用着 CH 的一些形象。比方：IColumn 代表内存外面以列形式组织的数据。IDataType 是数据类型的形象。Block 则是由多个 IColumn 组成的数据块，它是执行过程中，数据处理的根本单位。在执行过程中，Block 会被组织为流的模式，以 BlockInputStream 的形式，从存储层“流入”计算层。而 BlockOutputStream，则个别从执行引擎往存储层或其余节点“写出”数据。IStorage 则是对存储层的形象，定义了数据写入、读取、DDL 操作、表锁等基本操作。
三、DeltaTree 引擎
尽管 TiFlash 根本沿用了 ClickHouse 的向量化计算引擎，然而存储层最终没有沿用 CH 的 MergeTree 引擎，而是从新研发了一套更适宜 HTAP 场景的列存引擎，咱们称为 DeltaTree，对应代码中的 “StorageDeltaMerge”。
3.1 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 场景下，读、写性能都会有较大的稳定。
3.2 DeltaTree 的解决思路以及模块划分
在看实现之前，咱们来看看 DeltaTree 的疗效如何。上图是 Delta Tree 与基于 MergeTree 实现的带事务反对的列存引擎在不同数据量（Tuple number）以及不同更新 TPS (Transactions per second) 下的读 (Scan) 耗时比照。能够看到 DeltaTree 在这个场景下的读性能根本能达到后者的两倍。
那么 DeltaTree 具体面对上述问题，是如何设计的呢？首先，咱们在表内，把数据依照 handle 列的 key-range，横向宰割进行数据管理，每个分片称为 Segment。这样在 compaction 的时候，不同 Segment 间的数据就独立地进行数据整顿，可能缩小写放大。这方面与 PebblesDB 的思路有点相似。另外，在每个 Segment 中，咱们采纳了 delta-stable 的模式，即最新的批改数据写入的时候，被组织在一个写优化的构造的开端 (DeltaValueSpace.h)，定期被合并到一个为读优化的构造中 (StableValueSpace.h)。Stable Layer 寄存绝对老的，数据量较大的数据，它不能被批改，只能被 replace。当 Delta Layer 写满之后，与 Stable Layer 做一次 Merge（这个动作称为 Delta Merge），从而失去新的 Stable Layer，并优化读性能。很多反对更新的列存，都是采纳相似 delta-stable 这种模式来组织数据，比方 Apache Kudu。有趣味的读者还能够看看《Fast scans on key-value stores》的论文，其中对于如何组织数据，MVCC 数据的组织、对过期数据 GC 等方面的优劣取舍都做了剖析，最终作者也是抉择了 delta-main 加列存这样的模式。Delta Layer 的数据，咱们通过一个 PageStorage 的构造来存储数据，Stable Layer 咱们次要通过 DTFile 来存储数据、通过 PageStorage 来治理生命周期。另外还有 Segment、DeltaValueSpace、StableValueSpace 的元信息，咱们也是通过 PageStorage 来存储。下面三者别离对应 DeltaTree 中 StoragePool 这一数据结构的 log, data 以及 meta。
3.3 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 内局部数据的能力（只读抉择的列数据）
3.4 读索引 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 的性能。
3.5 Rough Set Index
很多数据库都会在数据块上加统计信息，以便查问时能够过滤数据块，缩小不必要的 IO 操作。有的将这个辅助的构造称为 KnowledgeNode、有的叫 ZoneMaps。TiFlash 参考了 InfoBright 的开源实现，采纳了 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%+，因而整体的过滤成果还不错。
3.6 代码模块
上面是 DeltaTree 引擎内各个模块对应的代码地位，读者能够回顾一下前文，它们别离对应前文的哪一部分 ;)# DeltaTree 引擎内各模块对应的代码地位
dbms/src/Storages/
├── Page # PageStorage
└── DeltaMerge
├── DeltaMergeStore.h # DeltaTree 引擎的定义
├── Segment.h # Segment
├── StableValueSpace.h # Stable Layer
├── Delta # Delta Layer
├── DeltaMerge.h # Stable 与 Delta merge 过程
├── File # Stable Layer 的存储格局
├── DeltaTree.h, DeltaIndex.h # Delta Index
├── Index, Filter, FilterParser # Rough Set Filter
└── DMVersionFilterBlockInputStream.h # MVCC Filtering小结
本篇文章次要介绍了 TiFlash 整体的模块分层，以及在 TiDB 的 HTAP 场景下，存储层 DeltaTree 引擎如何进行优化的思路。简略介绍了 DeltaTree 内组件的形成和作用，然而略去了一些细节，比方 PageStorage 的外部实现，DeltaIndex 如何构建、应答更新，TiFlash 是如何接入 multi-Raft 等问题。更多的代码浏览内容会在前面的章节中逐渐开展，敬请期待。