TiFlash 源码阅读（五） DeltaTree 存储引擎设计及实现分析

本文作者：施闻轩，TiFlash 资深研发工程师

布景

在 Part1 中咱们主要对 DeltaTree 引擎的结构和写入相关流程进行了介绍。本文对读取流程进行介绍。若读者没有阅览过 Part1 ，需求先阅览 Part1 文章了解前置常识。

本文根据写作时最新的 TiFlash v6.1.0 规划及源码进行剖析。跟着时间推移，新版本中部分规划或许会产生改变，使得本文部分内容失效，请读者留意甄别。TiFlash v6.1.0 的代码可在 TiFlash 的 git repo 中切换到 v6.1.0 tag 进行查看。

读

如 Part1 所述，写入时，DeltaTree 引擎构成的结构如下：

TiFlash 源码阅读（五） DeltaTree 存储引擎设计及实现分析 - Part 2

数据首先在值域规模上进行切分，分成了多个不同的 Segment，然后在时域规模上进行切分，依照新老数据分为 Stable 层（绝大多数数据）和 Delta 层（刚写入的数据）。其中，Delta 层又分为磁盘上的数据和内存中的 MemTable 数据。定期的 Flush 的机制会将内存数据写入到磁盘中。

如果想了解这个结构的具体情况，请参见 Part1 。

若要从这样的结构中顺次扫描数据，那么需求对每个 Segment 的 Stable、磁盘上的 Delta 层、内存中的 MemTable 数据这三部分数据进行联合扫描：

对 LSM Tree 比较了解的读者会发现，单个 Segment 内相似于一个 2 层 LSM Tree，因为两层的值域是堆叠的，因而需求一起读取，并结合 MVCC 版本号，以便得到一个终究结果。

快照读

在实践完成中，TiFlash 并非直接对这三块数据直接进行读取，而是首先为它们构建快照，然后根据快照进行读取。快照是一种抽象概念，被「快照」下来的数据在读取的时候永远不会产生变化，即使实践数据因为产生了并行写入产生了改变。

快照读机制供给了以下好处：

能够供给必定的 ACID 阻隔（快照阻隔等级），例如不会读出写到一半的数据
长时间的读和写不会相互阻塞，能够一起进行，关于读许多数据的场景比较友爱

从逻辑上来说，在读之前拿个锁阻塞写、并仿制一遍数据，就能够以最简单的方法完成快照。但清楚明了的是，仿制数据是一个十分耗时的操作（例如考虑要扫 1TB 数据）。以下具体剖析 TiFlash 各个部分数据是怎么完成高性能快照的。

MemTableSet 的快照

关于 MemTable 中的 ColumnFileInMemory 数据，TiFlash 经过仿制 Block 数据区指针的方法完成“快照”，不会仿制它所包括的 Block 数据内容：

for (const auto & file : column_files)
{
    if (auto * m = file->tryToInMemoryFile(); m)
    {
        snap->column_files.push_back(std::make_shared<ColumnFileInMemory>(*m));
    }
    else
    {
        snap->column_files.push_back(file);
    }
    total_rows += file->getRows();
    total_deletes += file->getDeletes();
}

留意，快照后的 ColumnFileInMemory 实践上与被快照的 ColumnFileInMemory 同享了相同的 Block 数据区域，而 ColumnFileInMemory 数据区是会跟着新写入产生改变的。因而这个 ColumnFileInMemory “快照”并不确保后续读的时候不会遇到新数据，不是一个真正意义上的快照。在读过程中，TiFlash 还额外进行了 TSO 的过滤来规避这些后续或许新写入的数据。

磁盘上 Delta 层数据的快照

关于 ColumnFilePersistedSet，其各个 ColumnFile 的数据经过 PageStorage 存储在了磁盘中。这些数据是 immutable 的，不会跟着新写入产生修改，因而直接仿制 ColumnFile 结构体指针（std::shared_ptr）、对其引证计数进行更新即可。

磁盘上 Stable 层数据的快照

在 Part1 中咱们能够了解到 Stable 层的数据也是 immutable 的：整个 Stable 层的数据文件不会被更改，只会在 Merge Delta 等过程中被全体替换成一个新的文件。因而与 Delta 层数据相似，Stable 层也是经过智能指针追寻引证计数、直接添加引证即可。

经过这些剖析大家能够发现，TiFlash 中的快照过程是十分轻量的，根本上都仅仅涉及到指针仿制和引证计数的更新，因而其效率十分高。

Scan 完成

Scan 是各个 AP 剖析引擎最重要的读操作，TiFlash 也不破例。TiFlash 中 Scan() 完成的语义为：给定一个主键区间，流式地、按顺序地回来在这个区间内指定列的所有数据。

TiFlash 的 Scan 是三个流（Stream）的组合：

最底层 DeltaMergeBlockInputStream：回来合并自 MemTableSet、磁盘上的 Delta 层、磁盘上的 Stable 层这三个来源的数据流。这个流回来的数据是有序的，必定依照 (Handle, Version) 升序摆放，但并不确保回来的数据必定契合给定的区间规模。
DMRowKeyFilterBlockInputStream：根据 Handle 列的规模进行过滤并回来
DMVersionFilterBlockInputStream：根据 Version 列的值进行 MVCC 过滤

DeltaMergeBlockInputStream

这个流有序地回来 MemTable、Delta、Stable 三层数据。在 Part1 中咱们介绍过，MemTable 中或许存在多个值域堆叠的 ColumnFileInMemory（每个 ColumnFile 内部是有序的），而 Delta 中也或许存在多个值域堆叠的 ColumnFileTiny，Stable 层则比较简单，只有一个 DMFile，且内部是有序的。

以下边的图片为例，假定 MemTable、Delta、Stable 中各自有一些数据，咱们期望 DeltaMergeBlockInputStream 回来的结果如图中最右侧红色表格所示：

由此可见，这个流本质是，关于多个有序流回来一个有序的合并后的流。这是一个标准的 K 路归并问题（K-way Sort Merge），这也正是许多 LSM Tree 存储引擎（如 RocksDB）等关于 N 层有序数据进行 Scan 的完成方法。K 路归并的流能够经过一个最小堆完成：

从各个底层流中取一行，放入最小堆中
从最小堆中取出当前最小的这一行（这一行必定是过程 1 中各行里最小的），作为流输出的榜首行
从取走行的流中弥补一行到最小堆中
重复过程 2

K 路归并完成简单、使用广泛，但它也存在一些问题：

无论读哪一列，都需求根据 Sort Key 作为最小堆的排序根据，换句话说 Sort Key 列总是需求被读出来，哪怕它并不是用户所请求的数据列
根据堆的算法只能以行为单位处理，有较多的分支判断，无法充分利用 CPU 流水线

TiFlash 中这个流并没有采用 K 路归并的方法完成，而是采用了业界比较新的 Positional Index 方法。与 K 路归并不同的是，Positional Index 并不是根据 Sort Key 进行排序合并，而是根据各个记载的下标方位（即 Positional 名称的来源）进行差分合并。

TiFlash 在写入的时候并不会更新 Positional Index，而是在读取的时候按需更新，这使得 TiFlash 得以保持高频写入性能。Positional Index 结构及算法比较复杂，后续的源码解读章节会独自涵盖，因而本文不作具体打开。感兴趣的读者也能够自行阅览 DeltaIndex.h 了解具体完成。

DMRowKeyFilterBlockInputStream

这个流会依照给定的 Handle 列规模对数据进行过滤。在 TiFlash 的完成中，虽然在从 Stable 读数据的时候也会指定读取的 Handle Range，但这个 Range 终究映射为了 Pack，回来的是以 Pack 为单位的流数据，因而还需求经过这个流对数据规模进行进一步准确地限定。

DMVersionFilterBlockInputStream

这个流的意图是完成 MVCC 过滤，下图展现了这个流的根本工作：接受一组包括 Version 及 Handle 列的数据（按 Handle, Version 排序），Handle 列或许存在多个 Version，并给定一个 MVCC 版本号，按序回来各个 Handle 不超过这个版本号最大的版本行。

因为全体数据是按 Handle, Version 有序摆放的，因而这个流的算法比较简单，这儿也不做具体打开，感兴趣的读者能够阅览 DMVersionFilterBlockInputStream.h。

TiFlash 源码阅读（五） DeltaTree 存储引擎设计及实现分析 – Part 2

布景

读