第3章 TiDB的计算（一）

作为一个优秀的NewSQL数据库，TiDB在TiKV提供的分布式存储能力基础上，构建了兼具优异的交易处理能力与良好的数据分析能力的计算引擎。本章首先从数据映射算法入手揭秘TiDB如何将库表中的数据映射到TiKV中的（Key，Value）键值对，然后描述了TiDB元信息数据管理方式。在此基础上，本章最后一节介绍了TiDB SQL层的主要架构。需要注意的是，对于计算层依赖的存储方案，本章只介绍了基于TiKV的行存储结构。针对分析型业务的特点，TiDB推出了作为TiKV扩展的列存储方案TiFlash。

1、关系模型到Key-Value模型的映射
表数据与Key-Value的映射关系，这里的数据主要包括两个方面：
1）表中的每一行的数据，以下简称表数据
2）表中所有索引的数据，以下简称索引数据

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

1）为了保证同一个表的数据放在一起，方便查找，TiDB会为每个表分配一个表ID，用TableID表示。表ID是一个整数，在整个集群内唯一。
2）TiDB会为表中每行数据分配一个行ID，用RowID表示。行ID也是一个整数，在表内唯一。对于行ID，TiDB做了一个小优化，如果某个表有整数型的主键，TiDB会使用主键的值当做这一行数据的行ID。
每行数据按照如下规则编码成（Key，Value）键值对：

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

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

1.2 索引数据和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

1.3 映射关系小结
最后，上述所有编码规则中的tablePrefix，recordPrefixSep和indexPrefixSep都是字符串常量，用于在Key空间内区分其他数据，定义如下：

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

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

1.4 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 模型的映射规则以及选择该方案背后的考量。