TiDB原理解析系列（二）---SQL到KV模型的存储与查询映射

考虑做一个存储系统，首先要考虑的就是数据的存储模型。TiKV选择的是Key-Value模型，并且这个模型提供有序遍历的方法。简单来讲，TiKV就是一个巨大的Map，其中Key和Value都是原始的Byte数组，在这个Map中，Key按照Byte数组二进制比特位比较排列。

TiKV是一个巨大的Map，存储的是Key-Value Pair。
TiKV Map中的Key-Value pair按照Key的二进制顺序有序。可以Seek到某一个Key的位置，然后不断的调用Next方法，以递增的顺序获取比这个Key大的Key-Value。

实现上，TiKV没有直接向磁盘上写数据，而是把数据写入RocksDB中，具体的数据落地由RocksDB负责。可以简单的认为，TiKV是一个分布式Key-Value Map，RocksDB是一个单机的Key-Value Map。

有了这个存储模型，接下来就需要考虑如何在KV模型上保存关系型数据以及如何在KV上运行SQL语句。

一、`SQL`到`KV`模型的存储

创建一个表结构：

CREATE TABLE User {
        ID int,
        Age int,
        Name varchar(20),
        Gender varchar(20),
        PRIMARY KEY (ID),
        UNIQUE index idxName (Name),  //唯一索引
        index idxGender (Gender)
};

接着插入数据：

image.png

那么到底需要存储哪些数据，做哪些映射？为了方便理解，我们拿SQL到B+树模型（MySQL默认数据引擎InnoDB数据存储模型）来做说明。

1.表数据以及主索引存储

InnoDB中，表数据本身就是按B+树组织的一个索引结构，B+树叶节点的data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据本身就是主索引。表数据以及主索引实际存储如下图：

image.png

TiDB也采用了这个方式，即表数据本身也就是主索引。data域即value:[col1,col2,col3,col4]保存完整的数据记录，这里的难点是key的设计。
TiKV使用了RocksDB的Column Families(CF)特性，默认 RocksDB 实例将 KV 数据存储在内部的 default、write 和 lock 3 个 CF 内：

default CF存储的是真正的数据，与其对应的参数位于[rocksdb.defaultcf]项中；
write CF存储的是数据的版本信息 (MVCC)以及索引相关的数据，相关的参数位于[rocksdb.writecf]项中；
lock CF存储的是锁信息，系统使用默认参数。

表数据文件数据存储在rocksdb.defaultcf中，索引存储在rocksdb.writecf。所以KEY中需要包含识别Database/Table的tableID，识别的行的rowID(Primary Key)，识别索引的indexID。每行数据按照规则进行编码成KV pair:

Key: tablePrefix{tableID}_recordPrefixSep{rowID}
Value: [col1,col2,col3,col4]

注：tablePrefix/recordPrefixSep 都是特定的字符串常量，用于区分其他数据。

var(
    tablePrefix     = []byte{"_t"}
    recordPrefixSep = []byte("_r")
    indexPrefixSep  = []byte("_i")
)

假设TiDB分配的tableId为10，表数据以及主索引实际存储如下：

t10_r15--->[34,Bob,Female]
t10_r18--->[77,Alice,Male]
t10_r20--->[5,Jim,Female]
t10_r30--->[91,Eric,Female]
t10_r49--->[22,Tom,Male]
t10_r50--->[89,Rose,Male]

2.辅助索引存储

InnoDB中除了主索引以外还有辅助索引。InnoDB的辅助索引data域存储相应记录主键的值，而不是完整的数据记录。主索引key是唯一的，而辅助索引的key可以重复。但是B+树要求键的值必须唯一，所以这里把辅助键的值和主键的值合并起来作为在B+树中的真正键值，保证了唯一性。辅助索引存储如下图：

image.png

TiDB与InnoDB辅助索引的设计基本保持一致，但是区分了重复辅助索引和唯一辅助索引，并且为每个辅助索引分配了一个indexID。
唯一辅助索引：

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

假设TiDB分配的tableID为10，indexID为1。Unique索引indexName实际存储为：

t10_r1_Bob--->15
t10_r1_Alice--->18
......

重复辅助索引：

Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue_rowID
Value: null

假设TiDB分配的tableId为10，indexID为2。索引idxGender实际存储为：

t10_r2_Fmale_15--->null
t10_r2_Male_18--->null
......

3.表结构存储

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

Key: tableMetaPrefix{tableID}
value:[TableName,cloName,cloName,colName,colName]

假设TiDB分配的tableId为10,实际表结构存储为：

m10--->[User,ID,Age,Name,Gender]

二、`SQL`到`kv`模型的查询映射

前面提到，将TiKV看做一个巨大的有序的KV Map，那么为了实现存储的水平扩展，需要将数据分散在多台机器上。对于一个KV系统，将数据分散在多台机器上有两种比较典型的方案：一种是按照Key做Hash，根据Hash值选择对应的存储节点；另一种是分Range，某一段连续的Key都保存在一个存储节点上。TiKV选择了第二种方式，将整个Key-Value空间分成很多段，每一段是一系列连续的Key，我们将每一段叫做一个Region，并且会尽量保持每个Region中保存的数据不超过一定的大小(这个大小可以配置，目前默认是64mb)。每一个Region都可以用StartKey到EndKey这样一个左闭右开区间来描述。也就是说上面的数据在实际存储中，按Region划分，是存储在不同的TiKV的Node中。如下图所示：

image.png

当对这个表执行一条SQL语句Select count(*) from User where id > 0 and id < 90时，数据不再分布在一台物理机上，而是分布在3个物理机上。分布式SQL操作如下：

构造Key Range区间（主键ID划分）。区间：[0,20)，[20,40)，[40,60)…
获取key Range所在Tikv节点。
优化执行计划。即将where条件与count(*)，一起推到相应的Tikv节点。
每个Tikv节点过滤数据，计算count(*)。
TiDB Server将每个Tikv节点计算count(*)，合并起来计算。

image.png

以上就是一个分布式的SQL计算，很明显它是不同于MySQL的SQL查询。不管是NewSQL数据库还是传统数据库，都会对 optimizer进行优化。上面对count(*)的优化设计，一方面增加了计算并行度，同时也减少了网络交互。TiDB在优化方面做了很多工作，比如常量折叠、常量传播、JOIN选择等，并且有一个框架去统计下层数据信息，在此基础上继续做优化。具体优化可以参考MPP and SMP in TiDB。

三、`TiDB SQL`层框架

上面主要介绍了SQL到KV存储映射以及SQL分布式计算相关功能，让我们从SQL的角度去了解数据是如何存储，SQL是如何计算执行的。这些都是在SQL层框架中实现的。实际TiDB的SQL层非常复杂，涉及到很多优化器分布原理，分布框架执行的细节，是TiDB中比较复杂的模块。下图列出了重要的模块以及调用关系（部分来图来自网络）：

image.png

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

TiDB原理解析系列（二）---SQL到KV模型的存储与查询映射

一、SQL到KV模型的存储

1.表数据以及主索引存储

2.辅助索引存储

3.表结构存储

二 、SQL到kv模型的查询映射

三、TiDB SQL层框架

一、`SQL`到`KV`模型的存储

二、`SQL`到`kv`模型的查询映射

三、`TiDB SQL`层框架