关于tidb:TiDB简述及TiKV的数据结构与存储-京东物流技术团队

TiDB 是 PingCAP 公司自主设计、研发的开源分布式关系型数据库，是一款同时反对在线事务处理与在线剖析解决 (Hybrid Transactional and Analytical Processing, HTAP) 的交融型分布式数据库产品，具备程度扩容或者缩容、金融级高可用、实时 HTAP、云原生的分布式数据库、兼容 MySQL 5.7 协定和 MySQL 生态等重要个性。指标是为用户提供一站式 OLTP (Online Transactional Processing)、OLAP (Online Analytical Processing)、HTAP 解决方案。TiDB 适宜高可用、强统一要求较高、数据规模较大等各种利用场景。

总结一下，Tidb 是个高度兼容 MySQL 的分布式数据库，并领有以下几个个性：

高度兼容 MySQL：把握 MySQL，就能够零根底应用 TIDB
程度弹性扩大：自适应扩大，基于 Raft 协定
分布式事务：乐观锁、乐观锁、因果一致性
真正金融级高可用：基于 Raft 协定
一站式 HTAP 解决方案：单个数据库同时反对 OLTP 和 OLAP，进行实时智能解决的能力

其中 TiDB 的外围个性是：程度扩大、高可用。

本文次要从 TiDB 的各类组件为终点，理解它的基础架构，并重点剖析它在存储架构方面的设计，探索其如何组织数据，Table 中的每行记录是如何在内存和磁盘中进行存储的。

先看一张 Tidb 的架构图，外面蕴含 TiDB、Storage(TiKV、TiFlash)、TiSpark、PD。其中的 TiDB、TiKV、PD 是外围组件；TIFlash、TiSpark 是为了解决简单 OLAP 的组件。
TiDB 是 Mysql 语法的交互入口，TiSpark 是 sparkSAL 的交互入口。

[]()

SQL 层，对外裸露 MySQL 协定的连贯 endpoint，负责承受客户端的连贯，执行 SQL 解析和优化，最终生成分布式执行打算。

TiDB 层自身是无状态的，实际中能够启动多个 TiDB 实例，通过负载平衡组件（如 LVS、HAProxy 或 F5）对外提供对立的接入地址，客户端的连贯能够平均地摊派在多个 TiDB 实例上以达到负载平衡的成果。TiDB Server 自身并不存储数据，只是解析 SQL，将理论的数据读取申请转发给底层的存储节点 TiKV（或 TiFlash）。

整个 TiDB 集群的元信息管理模块，负责存储每个 TiKV 节点实时的数据分布状况和集群的整体拓扑构造，提供 TiDB Dashboard 管控界面，并为分布式事务调配事务 ID。

PD 不仅存储元信息，同时还会依据 TiKV 节点实时上报的数据分布状态，下发数据调度命令给具体的 TiKV 节点，能够说是整个集群的“大脑”。此外，PD 自身也是由至多 3 个节点形成，领有高可用的能力。倡议部署奇数个 PD 节点。

负责存储数据，从内部看 TiKV 是一个分布式的提供事务的 Key-Value 存储引擎。

存储数据的根本单位是 Region，每个 Region 负责存储一个 Key Range（从 StartKey 到 EndKey 的左闭右开区间）的数据，每个 TiKV 节点会负责多个 Region。

TiKV 的 API 在 KV 键值对层面提供对分布式事务的原生反对，默认提供了 SI (Snapshot Isolation) 的隔离级别，这也是 TiDB 在 SQL 层面反对分布式事务的外围。

TiDB 的 SQL 层做完 SQL 解析后，会将 SQL 的执行打算转换为对 TiKV API 的理论调用。所以，数据都存储在 TiKV 中。另外，TiKV 中的数据都会主动保护多正本（默认为三正本），人造反对高可用和主动故障转移。

TiFlash 是一类非凡的存储节点。和一般 TiKV 节点不一样的是，在 TiFlash 外部，数据是以列式的模式进行存储，次要的性能是为剖析型的场景减速。如果应用场景为海量数据，且须要进行统计分析，能够在数据表根底上创立 TiFlash 存储构造的映射表，以进步查问速度。

以上组件互相配合，撑持着 Tidb 实现海量数据存储、同时兼顾高可用、事务、优良的读写性能。

前文所形容的 Tidb 架构中，其作为存储节点的有两个服务，TiKV 和 TiFlash。其中 TiFlash 为列式存储的模式实现的，能够参考 ClickHouse 的架构思路，二者具备相似性。本章节次要探讨 TiKV 的实现。

[]()

在上图中，TiKV node 所形容的就是 OLTP 场景下 Tidb 的存储组件，而 TiFlash 则是应答的 LOAP 场景。TiKV 抉择的是 Key-Value 模型，作为数据的存储模型，并提供有序遍历办法进行读取。

TiKV 数据存储有两个关键点：

是一个微小的 Map（能够参考 HashMap），也就是存储的是 Key-Value Pairs（键值对）。
这个 Map 中的 Key-Value pair 依照 Key 的二进制程序有序，也就是能够 Seek 到某一个 Key 的地位，而后一直地调用 Next 办法，以递增的程序获取比这个 Key 大的 Key-Value。

须要留神的是，这里形容的 TiKV 的 KV 存储模型，与 SQL 中的 Table 无关，不要有任何代入。

在图中 TiKV node 外部，有 store、Region 的概念，这是高可用的解决方案，TiDB 采纳了 Raft 算法实现，这里细剖析。

在应用 Tidb 时，仍然以传统“表”的概念进行读写，在关系型数据库中，一个表可能有很多列。而 Tidb 是以 Key-Value 模式结构数据的，因而须要思考，将一行记录中，各列数据映射成一个 key-value 键值对。

首先，在 OLTP 场景，有大量针对单行或者多行的增、删、改、查操作，要求数据库具备疾速读取一行数据的能力。因而，对应的 Key 最好有一个惟一 ID（显示或隐式的 ID），以不便疾速定位。

其次，很多 OLAP 型查问须要进行全表扫描。如果可能将一个表中所有行的 Key 编码到一个区间内，就能够通过范畴查问高效实现全表扫描的工作。

Tidb 中表数据与 Key-Value 的映射关系，设计如下：

为了保障同一个表的数据会放在一起，不便查找，TiDB 会为每个表调配一个表 ID，用 TableID 示意，整数、全局惟一。
TiDB 会为每行数据调配一个行 ID，用 RowID 示意，整数、表内惟一。如果表有主键，则行 ID 等于主键。

基于以上规定，生成的 Key-Value 键值对为：

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

其中 tablePrefix 和 recordPrefixSep 都是特定的字符串常量，用于在 Key 空间内辨别其余数据。

这个例子中，是齐全基于 RowID 造成的 Key，能够类比 MySQL 的汇集索引。

对于一般索引，在 MySQL 中是有非汇集索引概念的，尤其 innodb 中，通过 B +Tree 模式，子节点记录主键信息，再通过回表形式失去后果数据。

在 Tidb 中是反对创立索引的，那么索引信息如何存储？它同时反对主键和二级索引（包含惟一索引和非惟一索引），且与表数据映射形式相似。

设计如下：

Tidb 为表中每个索引，调配了一个索引 ID，用 IndexID 示意。
对于主键和惟一索引，须要依据键值疾速定位到 RowID，这个会存储到 value 中

因而生成的 key-value 键值对为：

Key：tablePrefix{TableID}_indexPrefixSep{IndexID}_indexedColumnsValue
Value: RowID

因为设计的 key 中存在 indexedColumnsValue，也就是查问的字段值，因而能够间接命中或含糊检索到。再通过 value 中的 RowID，去表数据映射中，检索到 RowID 对应的行记录。

对于一般索引，一个键值可能对应多行，须要依据键值范畴查问对应的 RowID。

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

依据字段值，能够检索到具备相关性的 key 的列表，在依据 key 中蕴含的 RowID，再拿到行记录。

上述所有编码规定中的 tablePrefix、recordPrefixSep 和 indexPrefixSep 都是字符串常量，用于在 Key 空间内辨别其余数据，定义如下：

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

在上述映射关系中，一个表内所有的行都有雷同的 Key 前缀，一个索引的所有数据也都有雷同的前缀。这样具备雷同的前缀的数据，在 TiKV 的 Key 空间内，是排列在一起的。

因而，只须要设计出稳固的后缀，则能够保障表数据或索引数据，有序的存储在 TiKV 中。而有序带来的价值就是可能高效的读取。

假如数据库的一张表，如下：

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
4, "TiFlash", "OLAP", 30

这张表中有一个主键 ID、一个一般索引 idxAge，对应的是列 Age.

假如该表的 TableID=10，则其表数据的存储如下：

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

其一般索引 idxAge 的存储如下：

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

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

举例，“select count(*) from user where name=’tidb’;”这样的 SQL 语句，在 Tidb 中进行检索，流程如下：

依据表名、所有的 RowID，联合表数据的 Key 编码规定，结构出一个 [StartKey,endKey) 的左闭右开区间。
依据 [StartKey,endKey) 这个区间内的值，到 TiKV 中读取数据
失去每一行记录后，过滤出 name=’tidb’的数据
将后果进行统计，计算出 count(*)的后果，进行返回。

[]()

在分布式环境下，为了进步检索效率，理论运行过程中，上述流程是会将 name=’tidb’和 count()下推到集群的每个节点中，缩小无异议的网络传输，每个节点最终将 count( )的后果，再由 SQL 层将后果累加求和。

前文所形容的 Key-Value Pairs 只是存储模型，是存在于内存中的，任何长久化的存储引擎，数据终归要保留在磁盘上。TiKV 没有抉择间接向磁盘上写数据，而是把数据保留在 RocksDB 中，具体的数据落地由 RocksDB 负责。

这个抉择的起因是开发一个单机存储引擎工作量很大，特地是要做一个高性能的单机引擎，须要做各种粗疏的优化，而 RocksDB 是由 Facebook 开源的一个十分优良的单机 KV 存储引擎，能够满足 TiKV 对单机引擎的各种要求。这里能够简略的认为 RocksDB 是一个单机的长久化 Key-Value Map。

TiKV Node 的外部被划分成多个 Region，这些 Region 作为数据切片，是数据一致性的根底，而 TiKV 的长久化单元则是 Region，也就是每个 Region 都会被存储在 RocksDB 实例中。

[]()

以 Region 为单元，是基于程序 I / O 的性能思考的。而 TiKV 是如何无效的组织 Region 内的数据，保障分片平均、有序，这外面用到了 LSM-Tree，如果有 HBase 教训肯定不模式。

LSM-Tree（log structured merge-tree）字面意思是“日志构造的合并树”，LSM-Tree 的构造是横跨磁盘和内存的。它将存储介质依据性能，划分磁盘的 WAL(write ahead log)、内存的 MemTable、磁盘的 SST 文件；其中 SST 文件又分为多层，每一层数据达到阈值后，会筛选一部分 SST 合并到下一层，每一层的数据是上一层的 10 倍，因而 90% 的数据会存储在最初一层。

[]()

WAL：是预写 Log 的实现，当进行写操作时，会将数据通过 WAL 形式备份到磁盘中，避免内存断电而失落。

Memory-Table：是在内存中的数据结构，用以保留最近的一些更新操作；memory-table 能够应用跳跃表或者搜寻树等数据结构来组织数据，以保持数据的有序性。当 memory-table 达到肯定的数据量后，memory-table 会转化成为 immutable memory-table，同时会创立一个新的 memory-table 来解决新的数据。

Immutable Memory-Table：immutable memory-table 在内存中是不可批改的数据结构，它是将 memory-table 转变为 SSTable 的一种中间状态。目标是为了在转存过程中不阻塞写操作。写操作能够由新的 memory-table 解决，而不必因为锁住 memory-table 而期待。

SST 或 SSTable：有序键值对汇合，是 LSM 树组在磁盘中的数据的构造。如果 SSTable 比拟大的时候，还能够依据键的值建设一个索引来减速 SSTable 的查问。SSTable 会存在多个，并且按 Level 设计，每一层级会存在多个 SSTable 文件。

写入过程

首先会查看每个区域的存储是否达到阈值，未达到会间接写入；
如果 Immutable Memory-Table 存在，会期待其压缩过程。
如果 Memory-Table 曾经写满，Immutable Memory-Table 不存在，则将以后 Memory-Table 设置为 Immutable Memory-Table，生成新的 Memory-Table，再触发压缩，随后进行写入。
写的过程会先写入 WAL，胜利后才会写 Memory-Table，此刻写入才实现。

数据存在的地位，按程序会顺次经验 WAL、Memory-Table、Immutable Memory-Table、SSTable。其中 SSTable 是数据最终长久化的地位。而事务性写入只须要经验 WAL 和 Memory-Table 即可实现。

查找过程

1. 依据指标 key，逐级顺次在 Memory-Table、Immutable Memory-Table、SSTable 中查找
2. 其中 SSTable 会分为几个级别，也是按 Level 中进行查找。

Level- 0 级别，RocksDB 会采纳遍历的形式，所有为了查找效率，会管制 Level- 0 的文件个数。
而 Level- 1 及以上层级的 SSTable，数据不会存在交叠，且因为存储有序，会采纳二分查找提高效率。

RocksDB 为了进步查找效率，每个 Memory-Table 和 SSTable 都会有相应的 Bloom Filter 来放慢判断 Key 是否可能在其中，以缩小查找次数。

删除和更新过程

当有删除操作时，并不需要像 B + 树一样，在磁盘中的找到相应的数据后再删除。

首先会在通过查找流程，在 Memory-Table、Immuatble Memory-Table 中进行查找。
如果找到则对后果标记为“删除”。
否则会在结尾追加一个节点，并标记为“删除”
在真正删除前，将来的查问操作，都会先找到这个被标记为“删除”的记录。
之后会在某一时刻，通过压缩过程真正删除它。

更新操作和删除操作相似，都是只操作内存区域的构造，写入一个标记，随后真正的更新操作被提早在合并时一并实现。因为操作是产生在内存中，其读写性能也能保障。

长处

将数据拆分为几百 M 大小的块，而后程序写入
首次写入的目的地是内存，采纳 WAL 设计思路，加上程序写，进步写入的能力，工夫复杂度近似常数
反对事务，但 L0 层的数据，key 的区间有重叠，反对较差

毛病

读写放大重大
应答突发流量的时候，削峰能力有余
压缩率无限
索引效率较低
压缩过程比拟耗费系统资源，同时对读写影响较大

以上针对 TiDB 的整体架构进行建单介绍，并着重形容了 TiKV 是如何组织数据、如何存储数据。将其 Key-Value 的设计思路，与 MySQL 的索引构造进行比照，辨认类似与差别。TiDB 依赖 RockDB 实现了长久化，其中的 Lsm-Tree，作为 B +Tree 的改良构造，其关注核心是“如何在频繁的数据改变下放弃零碎读取速度的稳定性”，以程序写磁盘作为指标，假如频繁地对数据进行整顿，力求数据的程序性，带来读性能的稳固，同时也带来了肯定水平的读写放大问题。

作者：京东物流耿宏宇

起源：京东云开发者社区自猿其说 Tech

关于tidb:TiDB简述及TiKV的数据结构与存储-京东物流技术团队

1 概述

2 组件

2.1 TiDB Server

2.2 PD (Placement Driver) Server

2.3 存储节点

2.3.1 TiKV Server

2.3.2 TiFlash

3 存储架构

3.1 TiKV 的模型

3.2 TiKV 的行存储构造

3.2.1 表数据的 KV 映射

3.2.2 索引数据的 KV 映射

3.2.3 映射中的常量字符串

3.2.4 举例

3.3 SQL 与 KV 映射

4 RockDB 长久化

4.1 概述

4.2 RocksDB

4.2.1 LSM-Tree 构造

4.2.2 LSM-Tree 执行过程

4.3 RockDB 的优缺点

5 总结

Just My Socks（注册教程内含优惠码）

关于tidb:TiDB简述及TiKV的数据结构与存储-京东物流技术团队

1 概述

2 组件

2.1 TiDB Server

2.2 PD (Placement Driver) Server

2.3 存储节点

2.3.1 TiKV Server

2.3.2 TiFlash

3 存储架构

3.1 TiKV 的模型

3.2 TiKV 的行存储构造

3.2.1 表数据的 KV 映射

3.2.2 索引数据的 KV 映射

3.2.3 映射中的常量字符串

3.2.4 举例

3.3 SQL 与 KV 映射

4 RockDB 长久化

4.1 概述

4.2 RocksDB

4.2.1 LSM-Tree 构造

4.2.2 LSM-Tree 执行过程

4.3 RockDB 的优缺点

5 总结

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）