大型分布式数据库底层是如何对数据进行建模的 -- 学一下 TiDB 的数据存储方案

发表于 更新于 分类于 本文字数： 2k 阅读时长 ≈ 7 分钟

最近准备搞一些自建数据库相关的项目，偶然看到 TiDB的文档里面有介绍如何使用 Key-Value（键值对）来存储关系型数据库的表数据，我们跟着文档来过一遍这里的设计，也可以为我们自己的实现提供一些参考。

数据存储

数据库里面主要存在两种类型的数据，一是表中的数据，在结构上呈现出含有多个列的行结构，而是针对表中的数据构建的索引结构，常见的索引有 B+ Tree 索引，

由于 TiDB 的应用场景考虑到了 OLAP 和 OLTP 的混合场景，所以在将数据映射到键值对的时候需要考虑到以下问题：

  1. 能够快速对单行或者多行进行增删改查等操作（OLTP）
  2. 能够高效完成全表扫描的任务（OLAP）

这里所说的满足 OLAP 的场景需求，单纯通过数据组织到邻近区间的方式很难满足 OLAP 的需求，所以 TiDB 除了使用键值对的存储，还使用了 TiFlash 作为列存，印象中这里是直接通过 Raft 的 Listener 来同步数据同时来做数据转储的，不过这个不是今天的话题，我们继续回到正题。

首先我们定义几个不同的前缀以标记不同的数据：

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

以上前缀分别对应表、数据行和索引。

TiDB 的数据表中的行数据会采用如下规则来进行编码：

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

我们来看个例子，假设我们此时有如下这个表：

1
2
3
4
5
6
7
8
CREATE TABLE User (
    ID int,
    Name varchar(20),
    Role varchar(20),
    Age int,
    PRIMARY KEY (ID),
    KEY idxAge (Age)
);

同时这个表中有三行数据

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

假设这张表的 TableID 为 10，那么TiKV上的数据则是这样的结构：

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

这里将列的数据直接作为 value 来存储也是为了快速读取整行的数据。同时，由于 这些数据的 key具有相同的前缀，在底层存储中这些数据也会互相邻近（因为底层存储采用了 RocksDB，其中的 SSTable 会对 key 进行排序）。

在完成表的数据的存储之后，接下来就是如何实现高效的读。众所周知，在我们执行条件查询时，查询条件中会设定针对某个列的条件（比如查询主键为 1 的值），这个时候，由于 TiDB 不像 MySQL 或者 PostgreSQL 通过 B+ Tree组织数据，其在执行查询时天然无法快速基于某列的值来进行查询。 针对主键和唯一索引，TiDB 将主键的值加入到索引记录的 key 中，如下所示：

1
2
Key:   tablePrefix{tableID}_indexPrefixSep{indexID}_{indexedColumnsValue}
Value: {RowID}

假设主键索引 id 为 0，则上述表的主键索引的数据如下：

1
2
3
t10_i0_1 --> 1
t10_i0_2 --> 2
t10_i0_3 --> 3

可以发现，由于主键本身就是 RowID，所以其在功能上与表的数据有一定冲突（即可以直接通过表数据达到直接基于主键查询的效果）。但当主键不为RowID时，这个索引则能够快速定位特定行的数据。

唯一索引可以将 value 编入 key 中，非唯一索引则不能够采用这种方式，因为非唯一索引的值可以来自多个不同的行。因此，非唯一索引的数据格式如下：

1
2
Key:   tablePrefix{TableID}_indexPrefixSep{IndexID}_{indexedColumnsValue}_{RowID}
Value: null

假设非唯一索引的 IndexID为 1，则上述例子的二级索引数据如下：

1
2
3
t10_i1_10_1 --> null
t10_i1_20_2 --> null
t10_i1_30_3 --> null

可以想象，我们可以通过前缀匹配的方式，快速查询到对应值的不同行的 RowID，进而读取到相应行的数据。

对于元数据信息，TiDB 也会将这些数据编辑成键值对的模式，存储到 TiKV 中。每个 Database/Table 都被分配了一个唯一的 ID，这个 ID 作为唯一标识，并且在编码为键值对时，这个 ID 都会编码到 Key 中，再加上 m_ 前缀。这样可以构造出一个 Key，Value 中存储的是序列化后的元信息。

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

SQL引擎层

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

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

可以发现，这个操作需要扫描大量的数据，如果由计算节点来执行过滤数据这一操作，我们会产生大量的网络通信开销。

所以现在经常会听到一套优化的方式叫做查询函数下推或者谓词下推或者各种下推，本质上就是将过滤数据的操作下放到存储层，以实现并发查询，提高查询效率，并降低通信开销。

元信息管理

一开始的时候我以为 TiDB 的元信息管理和传统数据库的实现方式类似，是通过系统表来实现。看了文档之后才发现其实还有 PD Server。其实这里有不同的元数据信息，一部分放在 TiKV 里，比如Database和Table的元数据信息，通过特殊编码（给唯一 ID加上m_前缀的方式）来构成元信息的 Key，同时将元信息（表的定义和各种属性）作为Value来存储；另一部分放在 PD Server里，比如当前所有表结构信息的最新版本号，这个是全局的，其 Key 是 “/tidb/ddl/global_schema_version”，Value 是类型为 int64 的版本号值。TiDB 采用 Online Schema 变更算法，有一个后台线程在不断地检查 PD Server 中存储的表结构信息的版本号是否发生变化，并且保证在一定时间内一定能够获取版本的变化。（这部分信息影响的是数据的序列化反序列化，因为是Schema信息，我猜的）。

整体来讲就是这些内容。总的来说，不同业务场景下都还是会有各种对数据模式进行定义的方式，需要结合场景来寻找最优的数据定义方案和索引方案，TiDB 的实现方案也可以在我们做数据存储系统设计时给我们提供一些参考。类似的设计还有图场景下对图数据结构的建模（比如以前 FB 的 TAO，比如现在各种图数据库）、还有向量数据库里面对向量数据的建模。如何通过底层实现来支持这些场景下的需求，这也是目前数据库开发领域的一个卷的方向。