TiDB概述

TiDB 是一款开源分布式关系型数据库，同时支持在线事务处理（OLTP）与在线分析处理（OLAP）的混合型（Hybrid Transactional and Analytical Processing, HTAP) 分布式数据库，具备水平扩容或缩容、金融级高可用、实时 HTAP、Kubernetes 云原生的分布式数据库、兼容MySQL 5.7协议和MySQL生态等重要特性，支持在本地和云上部署。

与传统的单机MySQL数据库相比，TiDB 具有以下优势：

TiDB组件

在内核设计上，TiDB 分布式数据库将整体架构拆分成了多个模块，各模块之间互相通信，组成完整的 TiDB 系统。对应的架构图如下：

计算引擎层：TiDB/TiSpark

OLTP计算引擎TiDB

TiDB Server 主要用于OLTP业务，属于 SQL 层，对外暴露 MySQL 协议的连接 endpoint，负责接受客户端的连接，执行 SQL 解析和优化，最终生成分布式执行计划。

TiDB 层本身是无状态的，实践中可以启动多个 TiDB 实例，通过负载均衡组件（如 LVS、HAProxy 或F5）对外提供统一的接入地址，客户端的连接可以均匀地分摊在多个 TiDB 实例上，以达到负载均衡的效果。

OLAP计算引擎TiSpark

TiSpark 作为 TiDB 中解决用户复杂OLAP需求的主要组件，它将Spark SQL直接运行在分布式键值对存储层 TiKV上，同时融合 TiKV 分布式集群的优势，并融入大数据社区生态。至此，TiDB 可以通过一套系统，同时支持 OLTP 与 OLAP，免除用户数据同步的烦恼。

分布式协调层：PD

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

此外，PD 本身也是由至少 3 个节点构成，拥有高可用的能力。建议部署奇数个 PD 节点。

存储引擎层：TiKV/TiFlash

行存储TiKV

用于存储 OLTP 数据，采用行存储格式，支持事务机制，TiKV 本身是一个分布式的 Key-Value 存储引擎。

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

列存储TiFlash

用于存储 OLAP 数据，和普通 TiKV 节点不一样的是，在 TiFlash 内部，数据是以列存储格式，主要的功能是为分析型的场景加速。

上图为 TiDB HTAP 形态架构，其中包含 TiFlash 节点。TiFlash 提供列式存储，且拥有借助ClickHouse高效实现的协处理器层。

TiFlash 以低消耗不阻塞TiKV 写入的方式，实时复制TiKV 集群中的数据，并同时提供与 TiKV 一样的一致性读取，且可以保证读取到最新的数据。TiFlash 中的 Region 副本与 TiKV 中完全对应，且会跟随 TiKV 中的 Leader 副本同时进行分裂与合并。

TiDB计算引擎

SQL层架构

用户的 SQL 请求会直接或者通过Load Balancer发送到 TiDB Server，TiDB Server 会解析MySQL Protocol Packet，获取请求内容，对 SQL 进行语法解析和语义分析，制定和优化查询计划，执行查询计划并获取和处理数据。整个流程如下图所示：

表数据映射到KV

由于 TiDB 底层基于键值对存储数据，TiDB 表中的行数据需要按照一定格式映射转换为键值对：

每行数据按照如下规则编码成 (Key, Value) 键值对：

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

表索引映射到KV

TiDB 同时支持主键索引和二级索引。与表数据映射方案类似，TiDB 为表中每个索引分配了一个索引 ID，用IndexID表示。

Key: tablePrefix{TableID}_indexPrefixSep{IndexID}_indexedColumnsValueValue: RowID

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

KV映射示例

数据与 KV 的映射关系，定义如下：

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

假设表结构如下：

CREATE_TABLE User (ID int,Name varchar(20),Role varchar(20),Age int,UID int,PRIMARY KEY (ID),KEY idxAge (Age),UNIQUE KEY idxUID (UID));

假设表数据如下：

1, "TiDB", "SQL Layer", 10, 100012, "TiKV", "KV Engine", 20, 100023, "PD", "Manager", 30, 10003

t10_r1 --> ["TiDB", "SQL Layer", 10, 10001]t10_r2 --> ["TiKV", "KV Engine", 20, 10002]t10_r3 --> ["PD","Manager",30, 10003]

t10_i1_10001 --> 1t10_i2_10002 --> 2t10_i3_10003 --> 3

# 假设 IndexID 为 1t10_i1_10_1 --> nullt10_i1_20_2 --> nullt10_i1_30_3 --> null

TiKV存储引擎

TiKV Region

TiKV 可以看做是一个巨大的、有序的 KV Map，为了实现存储的水平扩展，数据将被分散在多台机器上。对于一个 KV 系统，为了将数据 均衡分散 在多台机器上，通常有两种方案：

利用哈希函数将数据节点均匀打散到一个 0 ~ 2^32 - 1 的顺时针哈希环上面，对于数据的新增、查询和删除等操作者，首先通过同一个哈希函数计算数据的哈希值，然后再哈希环上顺时针寻址，找到第一个数据节点进行数据访问。如图所示：

TiKV 选择了连续分段哈希（Range），将整个 Key-Value 空间分成很多段，每一段是一系列连续的 Key，将每一段叫做一个 Region，可以用[StartKey，EndKey)这样一个左闭右开区间来描述。每个 Region 中保存的数据量默认在96 MiB左右（可以通过配置修改）。

TiKV集群架构

TiKV 参考 Google Spanner 论文设计了 multi-raft-group 的副本机制。它将数据按照 key 的范围划分成大致相等的分片 Region，每一个 Region 会有多个副本（默认是 3 个），其中一个副本是 Leader，提供读写服务。

TiKV 通过 PD 对这些 Region 以及副本进行调度，以保证数据负载和读写负载都均匀分散在各个 TiKV 节点上，保证了整个集群资源的充分利用，并且可以随着机器数量的增加水平扩展。

上图示意了一个典型的 TiKV 集群，中间有 4 个对等的 TiKV 节点，负责存放数据。其中一个 Region 存在3个副本，每个副本分布在不同的 TiKV 节点上。

右边是PD 集群，负责提供集群的元数据服务，比如 TiKV 节点信息和数据的路由信息，即数据存放在哪个 TiKV 节点上。

TiKV数据架构

按 Range 分片存在的问题是，数据的写入、读取可能集中在某一个 Region 上，造成计算资源、存储空间的倾斜。因此，当一个 Region 的数据量超过阈值时，TiKV 自动将其分裂成多个更小的 Region；当一个 Region 的数据量低于阈值时，TiKV 自动将其与相邻的 Region合并。

TiKV 采用了分层架构设计，将功能划分为四个层级，每一层都只负责自己的事情。

网络层

首先是网络层，TiKV 使用了高性能的gRPC作为网络通信框架。TiKV 对外暴露了多种形式的接口，包括支持事务的 KV 服务、高性能但不支持事务的纯 KV 服务，还有用于加速 SQL 查询的计算下推服务。

事务层

在网络层之下，是事务层。TiKV 实现了一个基于Percolator算法的事务处理机制，支持乐观事务。此外，TiKV 还对Percolator做了改进，加入了对悲观事务的支持。

用户可以根据业务负载特点，灵活选择事务模式：

一致性层

接下来是一致性层，该层提供了最基本的键值操作接口，如kv put/kv delete/kv get/snapshot。在一致性层内部，TiKV 实现了Raft 一致性算法，保证强一致性。

存储层

最底层是RocksDB，作为高效的键值存储引擎，它是 TiKV 真正存储数据的地方。RocksDB 提供了持久化存储的能力，并被 TiKV 内部的各个层级用来读写数据。

每个 TiKV 实例中有两个 RocksDB 实例，一个用于存储Raft 日志（通常被称为raftdb），另一个用于存储用户数据以及MVCC 信息（通常被称为kvdb）。kvdb中有四个ColumnFamily：raft、lock、default和write：

把 TiKV集群架构和数据架构整合起来，TiKV 集群的数据存储结构大致如图所示：

RocksDB原理

TiKV 使用RocksDB作为底层存储引擎，RocksDB 是一种内嵌式的KV 存储引擎，因此可以将 RocksDB 理解为一个单机持久化 Key-Value Map。

由于 RocksDB 是 TiKV 底层存储的核心引擎，所以接下来会花大篇幅介绍 RocksDB 的内部构造和部分优化原理。

RocksDB 是由 Facebook 基于Google LevelDB开发的一款提供键值存储和读写功能的LSM-tree架构引擎。

可见，RocksDB 底层基于 LSM-tree 实现。LSM Tree（Log Structured Merge Tree，日志结构合并树）是一种数据存储模型，而不是某一种具体的树型的数据结构。

LSM Tree结构

LSM树是一种用于键值存储的数据结构。LSM 的基本思想是将所有的数据修改操作（如插入、更新、删除）都记录在一个顺序日志文件中，这个日志文件又称为预写日志（Write-Ahead Log，WAL）。顺序日志文件的好处是顺序写入，相比随机写入的性能更好。

WAL（预写日志）

为了防止内存断电而丢失，LSM 在写入 Memtable 之前，会先将增删查改操作备份到 WAL磁盘日志，在系统故障时，WAL 可以用来恢复丢失的数据。

Memtable（内存表）

Memtable 是内存数据结构，可以使用跳跃表或红黑树来实现，以保持数据的有序性。当 Memtable 达到一定的数据量后，Memtable会转化成为 ****Immutable Memtable，同时会创建一个新的Memtable来存储新数据。

Immutable Memtable（不可变内存表）

Memtable 存储的数据达到一定数量后，就会把它拷贝一份出来成为 Immutable Memtable。

Immutable Memtable在内存中是不可修改的数据结构，它是处于Memtable和 SSTable 之间的一种中间状态，目的是避免在转存过程中不阻塞写操作。写操作可以由新的Memtable处理，避免由于Memtable 直接写入磁盘造成的 IO阻塞。

内存中的Immutable Memtable 是有大小限制的，需要定期持久化到磁盘上的 SSTable。

SSTable 是Sorted String Table的简称，是一种高性能的有序键值对存储结构，由于键是有序的，查找键可以采用二分搜索。

为了优化读取性能，LSM 树使用了多层级的 SSTable 文件。具体来说，RocksDB 的 SSTable 从 Level 0 到 Level N 分为多层，每层包含多个 SSTable 文件。层级越高的 SSTable 数据越新，层级越低的 SSTable 数据越旧。

SSTable 的基本组成部分包括：

SSTable 的优点包括：

RocksDB写操作

RocksDB 中写入操作的原理见下图：

RocksDB读操作

RocksDB 中读取操作的原理见下图：

Compaction操作

RocksDB 通过追加写的方式记录数据修改操作：

通过这种方式，将磁盘的随机写入转换为顺序写入，提高了写入性能，但也带来了以下问题：

因此，RocksDB 引入了compaction操作，依次将L(N) 层的数据合并到下一层L(N+1) 层，同时清理标记删除的数据，从而降低空间放大、读放大的影响。

Compaction的机制

RocksDB 在逻辑上把 SSTable 文件划分成多个层级（7 层），并且满足以下性质：

Compaction的作用

Compaction的类型

RocksDB 的 Compaction 操作分为两类，分别是Minor Compaction和Major Compaction。

Minor Compaction 是指将 Immutable MemTable 转存为 SSTable 文件写入L0 层

Major Compaction 是指合并压缩第L(N) 层的多个 SSTable 文件到第L(N+1) 层

Major Compaction 的触发条件：

布隆过滤器（Bloom Filter）

为了减小 读放大 导致性能下降，RocksDB 采取了以下两种策略：

布隆过滤器底层使用一个位数组（bit array），初始集合为空时，所有位都为 0：

当往集合中插入一个数据 x时，利用k 个独立的哈希函数分别对 x 进行散列，然后将k 个散列值按数组长度取余后，分别将位数组位置置为 1：

查找过程和插入过程类似，也是利用同样的k 个哈希函数对待查找数据按顺序进行哈希，得到 k 个位置。

RocksDB 并未使用 k 个哈希函数，而是用了double-hashing方法，利用一个哈希函数达到近似 k 个哈希函数的效果。

结语

本文详细介绍了 TiDB 的核心组件，尤其是用于 OLTP 的分布式计算引擎 TiDB和分布式存储引擎 TiKV。一方面阐述了 TiDB 是如何将关系型表数据、索引数据转换为键值对数据；另一方面，深度剖析了 TiKV 内部的架构设计和原理，尾篇大幅介绍了 TiKV 底层引入的单机键值对数据库 RocksDB 的原理，一定程度让大家知其然也知其所以然。本文抛砖引玉，关于 TiDB 内部的分布式通信、一致性原理、MVCC、GC清理算法、一些巧妙数据结构，仍需大家深入研究方可融会贯通，活学活用。

作者介绍

陈林，社区编辑，某零售银行龙头DevOps持续集成平台技术负责人，主导核心业务方案设计落地，推动产品架构持续演进。