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]
其中 tablePrefix
和 recordPrefixSep
都是特定的字符串常量,用于在 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
映射关系小结
上述所有编码规则中的 tablePrefix
、recordPrefixSep
和 indexPrefixSep
都是字符串常量,用于在 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 中每个 Database
和 Table
都有元信息,也就是其定义以及各项属性。这些信息也需要持久化,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
,如果是的话,则返回这一行。具体流程如下:
- 构造出 Key Range:一个表中所有的
RowID
都在[0, MaxInt64)
这个范围内,使用0
和MaxInt64
根据行数据的Key
编码规则,就能构造出一个[StartKey, EndKey)
的左闭右开区间。 - 扫描 Key Range:根据上面构造出的 Key Range,读取 TiKV 中的数据。
- 过滤数据:对于读到的每一行数据,计算
name = "TiDB"
这个表达式,如果为真,则向上返回这一行,否则丢弃这一行数据。 - 计算
Count(*)
:对符合要求的每一行,累计到Count(*)
的结果上面。
整个流程示意图如下:
这个方案是直观且可行的,但是在分布式数据库的场景下有一些显而易见的问题:
- 在扫描数据的时候,每一行都要通过 KV 操作从 TiKV 中读取出来,至少有一次 RPC 开销,如果需要扫描的数据很多,那么这个开销会非常大。
- 并不是所有的行都满足过滤条件
name = "TiDB"
,如果不满足条件,其实可以不读取出来。 - 此查询只要求返回符合要求行的数量,不要求返回这些行的值。
分布式 SQL 运算
为了解决上述问题,计算应该需要尽量靠近存储节点,以避免大量的 RPC 调用。首先,SQL 中的谓词条件 name = "TiDB"
应被下推到存储节点进行计算,这样只需要返回有效的行,避免无意义的网络传输。然后,聚合函数 Count(*)
也可以被下推到存储节点,进行预聚合,每个节点只需要返回一个 Count(*)
的结果即可,再由 SQL 层将各个节点返回的 Count(*)
的结果累加求和。
以下是数据逐层返回的示意图:
SQL 层架构
通过上面的例子,希望大家对 SQL 语句的处理有一个基本的了解。实际上 TiDB 的 SQL 层要复杂得多,模块以及层次非常多,下图列出了重要的模块以及调用关系:
用户的 SQL 请求会直接或者通过 Load Balancer
发送到 TiDB Server,TiDB Server 会解析 MySQL Protocol Packet
,获取请求内容,对 SQL 进行语法解析和语义分析,制定和优化查询计划,执行查询计划并获取和处理数据。数据全部存储在 TiKV 集群中,所以在这个过程中 TiDB Server 需要和 TiKV 交互,获取数据。最后 TiDB Server 需要将查询结果返回给用户。