TiFlash 源码阅读（六）DeltaTree Index 的设计和实现分析

背景

在前面的源码分析中对 TiFlash 的核算层和存储层都进行了深化的分析，其间 TiFlash DeltaTree 存储引擎规划及完结分析 (Part 1) TiFlash DeltaTree 存储引擎规划及完结分析 (Part 2) 对 TiFlash 存储层的读写流程进行了完好的梳理，假如读者没有阅读过这两篇文章，主张阅读后再持续本文的阅读。

这儿简略回顾一下，TiFlash 存储层的数据是按表分隔存储的，每张表的数据会依据 Handle Range 切分为多个 Segment，每个 Segment 包括 Stable 层和 Delta 层，其间 Segment 的大部分数据存储在 Stable 层，Delta 层只负责处理少部分新写入的数据，并且在写入数据到达必定阈值后会将 Delta 层的数据兼并到 Stable 层。在读取时需求经过 DeltaTree Index 这个数据结构将 Stable 层和 Delta 层兼并成一个有序的数据流，本文会对 DeltaTree Index 在读取时的作用以及怎么维护 DeltaTree Index 进行讲解。

规划思路

多路归并

Stable 层的数据是依照 DTFile 的方式存储的，并且数据是依照 Handle 列和 Version 列全局有序的。Delta 层的数据分为磁盘和内存两部分，并且都是依照 ColumnFile 的方式安排的，可是 ColumnFile 内部不确保彻底有序。

关于 Stable 层和 Delta 层兼并这个问题，一个比较传统的做法是先对 Delta 层的不同 ColumnFile 进行内部排序，再经过多路归并的办法将 Stable 层和 Delta 层的数据兼并成一个有序的数据流。可是这种办法需求触及大量的比较操作以及入堆出堆操作等，因而功能比较差，所以咱们期望能在这个基础上进一步优化功能。

咱们考虑到已然多路归并比较耗时，那是否能够防止每次读都要重新做一次归并呢？答案是能够的。现实上有一些内存数据库现已实践了相似的思路。详细的思路是，榜首次读取操作完结后，咱们把多路归并算法产生的信息想办法存下来，然后使后续的读取能够重复利用这部分信息，关于新写入的数据能够经过增量更新的办法更新这部分信息即可。

DeltaTree Index

那么现在的问题是怎么存储多路归并算法产生的信息？一个比较朴素的主意是直接记载多路归并的操作次序，在下一次读取时依照这个次序读取即可。

如下图所示，咱们能够记载 Delta 层和 Stable 层兼并后的有序数据流中的榜首行来自 Stable 层的榜首行数据，第二行来自 ColumnFileInMemory[1] 的榜首行数据，第三行来自 Stable 层的第二行数据，并以此类推记载完好的操作次序，这样在下一次读取时直接依照这个次序读取就能够省掉多路归并的进程，然后提高读取功能。可是这个计划的缺点也比较明显，便是咱们需求为每一行数据记载相关的操作信息，因而会耗费大量的内存，并且这种记载办法不易进行增量更新，因而不太可行。

此刻咱们留意到 Stable 层的数据是全局有序的，所以 Stable 层数据在兼并的进程中必定是按次序读取的。因而咱们不需求再记载最终的有序数据流和 Stable 层数据的对应联系，只需求记载每条 Delta 层数据的读取次序，然后再记载一下两次 Delta 层读取操作之间需求读取的 Stable 数据的行数，就能够完好记载整个多路归并算法产生的信息。

如下图所示，咱们能够只记载在榜首次 Delta 层读取操作之前需求先从 Stable 层读取一行数据，在第二次 Delta 层读取操作之前需求再从 Stable 层读取五行数据，一起记载每次 Delta 层读取操作的详细内容，并以此类推即可记载完好的操作次序。考虑到 Delta 层数据只占整个 Segment 数据的极小部分，所以这种记载办法的内存耗费十分小，因而这种计划比较可行。那么最终剩下的问题便是怎么经过增量更新的办法维护这部分信息，为此咱们也进行了多次规划迭代，并参阅了许多现有的数据库的计划，最终形成的规划计划便是本文要介绍的 DeltaTree Index。

DeltaTree Index 是一个相似 B+ 树的结构，为了演示便利，这儿假定每个内部节点只要两个子节点，每个叶子节点能够包容两个 Entry，如下图所示，其间 sid 在叶子节点中代表在处理当时 Entry 之前需求处理的 Stable 的数据行数，在内部节点中代表右子树中最小的 sid；is_insert 只在叶子节点中存在，代表这个 Entry 对应的是刺进操作仍是删去操作，其间删去操作代表的是删去 Stable 层某个方位的数据；delta_id 也只在叶子节点中存在，代表的是这个 Entry 对应数据在 Delta 层的偏移；count 在内部节点中代表对应子树中刺进的数据行数减去删去的数据行数的值，而在叶子节点中 count 并没有实践存储下来，而是在遍历进程中核算得到，代表的是当时 Entry 之前刺进的数据行数减去删去的数据行数的值；row_id 也是一个遍历进程中核算得到的值，代表的是对应 Entry 在兼并之后的有序数据流中的方位。留意这儿仅仅对这些字段做一个基础的介绍，在后续的详细流程中会对这些字段有更深化的讲解。

要害流程

Search

首先介绍一下 DeltaTree Index 的遍历操作，这个操作主要是依据 row_id 查找或许包括其对应 Entry 的最右侧的叶子节点，根本的思路是在遍历的进程中维护一个 count 变量，代表遍历进程中一切越过的子树对应 count 字段值之和，因为内部节点中的 sid 代表的是其右子树中最小的 sid，因而内部节点的 sid 加上这儿维护的 count 变量再加上其左子树的对应 count 值，就代表其右子树中最小的 row_id，将这个值与要查找的 row_id 比较即能够判别方针 row_id 是在左子树仍是右子树中，然后持续向下遍历。

findRightLeafByRId(row_id) {
    node = root
    count = 0
    while !isLeaf(node) {
        for i = 0; i < child; i++ {
            count = count + node[i].count
            if node[i].sid + count > row_id {
                count = count - node[i].count
                break
            }
        }
        node = node[i].child
    }
    return node
}

下面以查找 row_id = 7 地点的最右侧叶子节点为例演示一下上面的算法，首先从根节点开端遍历，此刻 count 的初始值为 0，根节点的 sid 加上其左子树的 count 值小于要查找的 row_id，即右子树最小的 row_id 小于要查找的 row_id，因而接下来需求持续遍历右子树。

这儿持续依照上述的办法比较，能够核算得到当时节点的右子树最小的 row_id 为 8，大于要查找的 row_id，因而接下来需求持续遍历当时节点的左子树。

这儿现已遍历到叶子节点，那么这个叶子节点便是咱们要查找的或许包括 row_id 为 7 的最右侧的叶子节点。

Add Insert

关于 Delta 层内写入的一切数据行，都需求在 DeltaTree Index 中增加一条对应的 Insert Entry，对应的操作即为 DeltaTree Index 的 Add Insert 操作。在增加 Insert Entry 之前需求先获得对应数据行的 row_id，也即这条数据在 Stable 层和 Delta 层兼并后的有序数据流中的方位，详细这个 row_id 怎么获取咱们放在后面再讲，这儿先假定咱们现已拿到这条数据对应的 row_id，那么 Add Insert 操作对应的伪代码如下（留意这儿为了更便利的展现中心逻辑，省掉了更新 B+ 树结构的相关操作）。

leaf, count = findRightLeafByRId(row_id)
pos, count = searchLeafForRId(leaf, row_id, count)
shiftLeafEntries(leaf, pos, 1)
leaf[pos].sid = row_id - count
leaf[pos].delta_id = offset_in_delta_value_space

根本的思路是先经过 findRightLeafByRId 操作找到或许包括这个 row_id 的最右侧的叶子节点，然后再经过 searchLeafForRId 操作（这个操作比较简略，这儿就不展现了）在这个叶子节点上遍历找到这个 row_id 对应的 Entry 地点的方位，并将该方位原来的 Entry 向右移动一格（移动的进程或许会触发节点割裂等操作），最终把相关信息更新到这个 Entry 中即可。其间这个 Entry 的 sid 是经过核算 row_id – count 得到的，这儿能够直观理解一下这个核算的意义，咱们用 Stream 代表 Stable 层和 Delta 层兼并之后的有序数据流，那么这儿的 row_id 是新刺进数据在 Stream 中的方位，而咱们要核算的 sid 能够拆解为两部分，榜首部分是 Stream 中排在方针数据之前的 Stable 数据的行数，第二部分是处理该 Entry 之前现已被删去的 Stable 数据行数，其间榜首部分能够经过 row_id 减去 Stream 中排在方针数据之前的 Delta 数据的行数核算得到，而 count 刚好代表的是当时 Entry 之前刺进的数据行数减去删去的数据行数，所以 sid 能够经过核算 row_id – count 得到。

另外值得留意的是在 TiDB 中的 Update 和 Delete 操作都是经过对相同主键写入更新版别的数据行完结的，因而在 SQL 层面的 Insert，Update 和 Delete 操作都是需求在 Delta 层写入新的数据，并在 DeltaTree Index 中增加新的 Insert Entry。

Add Delete

然后再看一下怎么在 DeltaTree Index 中增加新的 Delete Entry，这儿也要先获取删去的数据行的 row_id，详细的获取办法也放在后面解释。对应的伪代码如下，

leaf, count = findRightLeafByRId(row_id)
pos, count = searchLeafForRId(leaf, row_id, count)
// skip delete chain
while leaf[pos].sid + count == row_id {
    if leaf[pos].is_insert {
        break 
    }
    pos += 1
    count -= 1
}
if leaf[pos].sid + count == row_id {
    shiftLeafEntries(leaf, pos + 1, -1)
} else {
    shiftLeafEntries(leaf, pos, 1)
    leaf[pos].sid = row_id - count
    leaf[pos].is_insert = false
}

删去数据有两种情况，分别是删去 Delta 层中的数据和删去 Stable 层中的数据。其间删去 Delta 层的数据只需求删去 DeltaTree Index 中对应的 Insert Entry 即可，也便是假如在 DeltaTree Index 中查找到需求删去数据对应 row_id 的 Insert Entry 时，阐明需求删去的数据在 Delta 层，此刻直接将该 Insert Entry删去即可完结删去操作。可是关于 Stable 层数据的删去则相对复杂一点，需求在 DeltaTree Index 中写入一条 Delete Entry 来代表删去一条 Stable 层的数据，对应 Delete Entry 的 sid 核算逻辑和 Insert Entry 相似，这儿不再赘述。

Add Delete 操作主要在 TiFlash 不同节点间 Region 产生迁移或许某张表的 TiFlash Replica 被删去时会触发，这些情况下某些 TiFlash 节点上的 Region 会被迁移走，因而需求删去该 Region 对应的数据，该删去操作经过向存储层写入一个 Delete Range 完结，这个 Delete Range 则会先写入 Delta 层，后续会扫描出该 Delete Range 掩盖的一切数据行，并依次在 DeltaTree Index 增加对应的 Delete Entry。

Read

上面介绍了 DeltaTree Index 的相关更新操作，接下来咱们再看一下怎么利用 DeltaTree Index 在读取时完结 Stable 层和 Delta 层的兼并，相关的伪代码如下所示：

total_stable_rows = 0
iter = index.begin()
while iter != index.end() {
    if iter->is_insert {
        rows = iter->sid - total_stable_rows
        read_stable_rows(rows)
        read_delta_row(delta_id)
        total_stable_rows += stable_rows
    } else {
        ignore_stable_rows(1)
        total_stable_rows += 1
    }
    iter++
}

根本思路是遍历一切的叶子节点，遍历进程中假如遇到 Insert Entry，依据当时 Entry 的 sid 和现已处理的 Stable 层数据行数核算出接下来需求读取的 Stable 数据行数，读取完之后再从 Delta 层读取当时 Entry 对应的数据行。假如遇到 Delete Entry，则从 Stable 层中读取一行数据并扔掉即可。

MinMax Index

现在咱们现已知道怎么用 DeltaTree Index 完结 Stable 层和 Delta 层的兼并，可是这个进程需求扫描 Delta 层和 Stable 层的一切数据，可是集群上的许多查询不需求扫描全表的数据，因而咱们想要尽或许过滤无效数据，防止无效的 IO 操作，所以咱们经过引入 MinMax 索引来完结这个意图。

因为 Stable 层数据是依照 DTFile 的方式存储的，且每个 DTFile 中包括多个 Pack，其间一个 Pack 中包括 8K 行或许更多的数据，因而咱们能够记载每个 Pack 中不同列的最大值和最小值，假如查询中有触及该列的相关条件时，能够依据该列的最大值和最小值判别对应 Pack 中是否或许包括需求扫描的数据，并过滤掉无效的 Pack 以减少 IO 操作的耗费，这便是 MinMax 索引的根本原理。

可是在 TiFlash 中完结 MinMax Index 还有一个需求留意的要害点，便是咱们需求确保相同主键的数据在同一个 Pack 中。比方看下面的比如，其间 Handle 代表的是主键列，Version 代表的是版别列，ColA 是一个普通列，假定有一个查询上包括条件 ColA < 30，那么咱们能够依据 MinMax 索引判别 Pack 1 中没有需求扫描的数据，因而咱们能够只从磁盘上扫描 Pack 0。可是假如这个查询的时间戳为 7，那么依照上述流程经过 MVCC 过滤后 Pack 0 中的最终一条数据会作为查询成果集的一部分回来。可是 Pack 1 中有一条主键相同且版别更新的数据，因而 Pack 0 中的最终一条数据理论上在 MVCC 过滤后应该被掩盖，而不是作为查询成果集回来。

所以咱们在写入 DTFile 时必须确保相同主键的数据会写入同一个 Pack，这样在经过 MinMax 索引过滤后才不会产生上述比如的异常情况。

Place Rows and Deletes

到目前为止怎么更新 DeltaTree Index 以及怎么利用 DeltaTree Index 完结读取操作现已悉数介绍完结。可是前面还遗留了一个问题，便是怎么获取需求刺进或许删去的数据行的 row_id？其实这个问题的答案也十分简略，便是将当时的 Delta 层和 Stable 层进行兼并之后，然后在其间找到需求刺进或许删去数据行的 row_id 即可。

当然假如每条数据的更新都要进行 Delta 层和 Stable 层的兼并会带来十分大的开支，所以为了减少这个开支，咱们采取了两种优化。榜首个优化是对数据进行攒批，当写入的数据到达必定阈值后会在后台更新 DeltaTree Index，以此来均摊更新 DeltaTree Index 的开支。另一个优化便是采用 Skippable Place，因为 Stable 层的数据是全局主键有序的，所以能够经过主键上的 MinMax 索引越过 Stable 层中与待更新数据规模没有堆叠的 Pack，并且因为在获取一切待更新数据的 row_id 后也不会再持续读取后面的 Pack，所以经过这种优化能够使得在通常情况下只需求读取 Stable 层中和待更新数据有堆叠的少部分 Pack 即可获取一切待更新数据的 row_id，因而能够大幅下降更新 DeltaTree Index 的开支。

小结

TiFlash 是 TiDB 的分析引擎，是 TiDB HTAP 形状的要害组件，因而 TiFlash 需求一起支撑高频小批量写入以及优异的读取功能。DeltaTree Index 结构的规划便是为了完结这个意图，更好地平衡 TiFlash 的读取和写入功能。本文只介绍了 DeltaTree Index 主要流程的根本原理，欢迎大家经过阅读 TiFlash 源码进一步了解更多的完结细节。