TiDB 数据库的计算

TiDB 在 TiKV 提供的分布式存储能力基础上,构建了兼具优异的交易处理能力与良好的数据分析能力的计算引擎。本文首先从数据映射算法入手介绍 TiDB 如何将库表中的数据映射到 TiKV 中的 (Key, Value) 键值对,然后描述 TiDB 元信息管理方式,最后介绍 TiDB SQL 层的主要架构。

对于计算层依赖的存储方案,本文只介绍基于 TiKV 的行存储结构。针对分析型业务的特点,TiDB 推出了作为 TiKV 扩展的列存储方案 TiFlash

表数据与 Key-Value 的映射关系

本小节介绍 TiDB 中数据到 (Key, Value) 键值对的映射方案。这里的数据主要包括以下两个方面:

  • 表中每一行的数据,以下简称表数据
  • 表中所有索引的数据,以下简称索引数据

表数据与 Key-Value 的映射关系

在关系型数据库中,一个表可能有很多列。要将一行中各列数据映射成一个 (Key, Value) 键值对,需要考虑如何构造 Key。首先,OLTP 场景下有大量针对单行或者多行的增、删、改、查等操作,要求数据库具备快速读取一行数据的能力。因此,对应的 Key 最好有一个唯一 ID(显示或隐式的 ID),以方便快速定位。其次,很多 OLAP 型查询需要进行全表扫描。如果能够将一个表中所有行的 Key 编码到一个区间内,就可以通过范围查询高效完成全表扫描的任务。

基于上述考虑,TiDB 中的表数据与 Key-Value 的映射关系作了如下设计:

  • 为了保证同一个表的数据放在一起,方便查找,TiDB 会为每个表分配一个表 ID,用 TableID 表示。表 ID 是一个整数,在整个集群内唯一。
  • TiDB 会为表中每行数据分配一个行 ID,用 RowID 表示。行 ID 也是一个整数,在表内唯一。对于行 ID,TiDB 做了一个小优化,如果某个表有整数型的主键,TiDB 会使用主键的值当做这一行数据的行 ID。

每行数据按照如下规则编码成 (Key, Value) 键值对:

Key:   tablePrefix{TableID}_recordPrefixSep{RowID}
Value: [col1, col2, col3, col4]

其中 tablePrefixrecordPrefixSep 都是特定的字符串常量,用于在 Key 空间内区分其他数据。其具体值在后面的小结中给出。

索引数据和 Key-Value 的映射关系

TiDB 同时支持主键和二级索引(包括唯一索引和非唯一索引)。与表数据映射方案类似,TiDB 为表中每个索引分配了一个索引 ID,用 IndexID 表示。

对于主键和唯一索引,需要根据键值快速定位到对应的 RowID,因此,按照如下规则编码成 (Key, Value) 键值对:

Key:   tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue
Value: RowID

对于不需要满足唯一性约束的普通二级索引,一个键值可能对应多行,需要根据键值范围查询对应的 RowID。因此,按照如下规则编码成 (Key, Value) 键值对:

Key:   tablePrefix{TableID}_indexPrefixSep{IndexID}_indexedColumnsValue_{RowID}
Value: null

映射关系小结

上述所有编码规则中的 tablePrefixrecordPrefixSepindexPrefixSep 都是字符串常量,用于在 Key 空间内区分其他数据,定义如下:

tablePrefix     = []byte{'t'}
recordPrefixSep = []byte{'r'}
indexPrefixSep  = []byte{'i'}

另外请注意,上述方案中,无论是表数据还是索引数据的 Key 编码方案,一个表内所有的行都有相同的 Key 前缀,一个索引的所有数据也都有相同的前缀。这样具有相同的前缀的数据,在 TiKV 的 Key 空间内,是排列在一起的。因此只要小心地设计后缀部分的编码方案,保证编码前和编码后的比较关系不变,就可以将表数据或者索引数据有序地保存在 TiKV 中。采用这种编码后,一个表的所有行数据会按照 RowID 顺序地排列在 TiKV 的 Key 空间中,某一个索引的数据也会按照索引数据的具体的值(编码方案中的 indexedColumnsValue)顺序地排列在 Key 空间内。

Key-Value 映射关系示例

最后通过一个简单的例子,来理解 TiDB 的 Key-Value 映射关系。假设 TiDB 中有如下这个表:

CREATE TABLE User (
    ID int,
    Name varchar(20),
    Role varchar(20),
    Age int,
    PRIMARY KEY (ID),
    KEY idxAge (Age)
);

假设该表中有 3 行数据:

1, "TiDB", "SQL Layer", 10
2, "TiKV", "KV Engine", 20
3, "PD", "Manager", 30

首先每行数据都会映射为一个 (Key, Value) 键值对,同时该表有一个 int 类型的主键,所以 RowID 的值即为该主键的值。假设该表的 TableID 为 10,则其存储在 TiKV 上的表数据为:

t10_r1 --> ["TiDB", "SQL Layer", 10]
t10_r2 --> ["TiKV", "KV Engine", 20]
t10_r3 --> ["PD", "Manager", 30]

除了主键外,该表还有一个非唯一的普通二级索引 idxAge,假设这个索引的 IndexID 为 1,则其存储在 TiKV 上的索引数据为:

t10_i1_10_1 --> null
t10_i1_20_2 --> null
t10_i1_30_3 --> null

以上例子展示了 TiDB 中关系模型到 Key-Value 模型的映射规则,以及选择该方案背后的考量。

元信息管理

TiDB 中每个 DatabaseTable 都有元信息,也就是其定义以及各项属性。这些信息也需要持久化,TiDB 将这些信息也存储在了 TiKV 中。

每个 Database/Table 都被分配了一个唯一的 ID,这个 ID 作为唯一标识,并且在编码为 Key-Value 时,这个 ID 都会编码到 Key 中,再加上 m_ 前缀。这样可以构造出一个 Key,Value 中存储的是序列化后的元信息。

除此之外,TiDB 还用一个专门的 (Key, Value) 键值对存储当前所有表结构信息的最新版本号。这个键值对是全局的,每次 DDL 操作的状态改变时其版本号都会加 1。目前,TiDB 把这个键值对持久化存储在 PD Server 中,其 Key 是 "/tidb/ddl/global_schema_version",Value 是类型为 int64 的版本号值。TiDB 采用 Online Schema 变更算法,有一个后台线程在不断地检查 PD Server 中存储的表结构信息的版本号是否发生变化,并且保证在一定时间内一定能够获取版本的变化。

SQL 层简介

TiDB 的 SQL 层,即 TiDB Server,负责将 SQL 翻译成 Key-Value 操作,将其转发给共用的分布式 Key-Value 存储层 TiKV,然后组装 TiKV 返回的结果,最终将查询结果返回给客户端。

这一层的节点都是无状态的,节点本身并不存储数据,节点之间完全对等。

SQL 运算

最简单的方案就是通过上一节所述的表数据与 Key-Value 的映射关系方案,将 SQL 查询映射为对 KV 的查询,再通过 KV 接口获取对应的数据,最后执行各种计算。

比如 select count(*) from user where name = "TiDB" 这样一个 SQL 语句,它需要读取表中所有的数据,然后检查 name 字段是否是 TiDB,如果是的话,则返回这一行。具体流程如下:

  1. 构造出 Key Range:一个表中所有的 RowID 都在 [0, MaxInt64) 这个范围内,使用 0MaxInt64 根据行数据的 Key 编码规则,就能构造出一个 [StartKey, EndKey)的左闭右开区间。
  2. 扫描 Key Range:根据上面构造出的 Key Range,读取 TiKV 中的数据。
  3. 过滤数据:对于读到的每一行数据,计算 name = "TiDB" 这个表达式,如果为真,则向上返回这一行,否则丢弃这一行数据。
  4. 计算 Count(*):对符合要求的每一行,累计到 Count(*) 的结果上面。

整个流程示意图如下:

naive sql flow

这个方案是直观且可行的,但是在分布式数据库的场景下有一些显而易见的问题:

  • 在扫描数据的时候,每一行都要通过 KV 操作从 TiKV 中读取出来,至少有一次 RPC 开销,如果需要扫描的数据很多,那么这个开销会非常大。
  • 并不是所有的行都满足过滤条件 name = "TiDB",如果不满足条件,其实可以不读取出来。
  • 此查询只要求返回符合要求行的数量,不要求返回这些行的值。

分布式 SQL 运算

为了解决上述问题,计算应该需要尽量靠近存储节点,以避免大量的 RPC 调用。首先,SQL 中的谓词条件 name = "TiDB" 应被下推到存储节点进行计算,这样只需要返回有效的行,避免无意义的网络传输。然后,聚合函数 Count(*) 也可以被下推到存储节点,进行预聚合,每个节点只需要返回一个 Count(*) 的结果即可,再由 SQL 层将各个节点返回的 Count(*) 的结果累加求和。

以下是数据逐层返回的示意图:

dist sql flow

SQL 层架构

通过上面的例子,希望大家对 SQL 语句的处理有一个基本的了解。实际上 TiDB 的 SQL 层要复杂得多,模块以及层次非常多,下图列出了重要的模块以及调用关系:

tidb sql layer

用户的 SQL 请求会直接或者通过 Load Balancer 发送到 TiDB Server,TiDB Server 会解析 MySQL Protocol Packet,获取请求内容,对 SQL 进行语法解析和语义分析,制定和优化查询计划,执行查询计划并获取和处理数据。数据全部存储在 TiKV 集群中,所以在这个过程中 TiDB Server 需要和 TiKV 交互,获取数据。最后 TiDB Server 需要将查询结果返回给用户。

下载 PDF文档反馈社区交流
文档内容是否有帮助?
产品
TiDB
学习
客户案例
PingCAP Education
TiDB in Action
© 2022 PingCAP. All Rights Reserved.