万字长文，深入浅出讲解分布式数据库TiDB架构设计

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

TiDB概述

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

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

• 分布式架构：纯分布式架构，拥有良好的扩展性，支持弹性的扩缩容
• 兼容MySQL：支持 SQL，对外暴露 MySQL 的网络协议，并兼容大多数 MySQL 的语法，在大多数场景下可以直接替换 MySQL
• 高可用部署：默认支持高可用，在少数副本失效的情况下，数据库本身能够自动进行数据修复和故障转移，对业务透明
• 支持强一致性：符合CAP理论的CP，支持 ACID 事务，对于一些有强一致需求的场景友好，例如：银行转账
• 丰富的开源生态链：具有丰富的工具链生态，覆盖数据迁移、同步、备份等多种场景

TiDB组件

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

计算引擎层：TiDB/TiSpark

OLTP计算引擎TiDB

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

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

TiDB Server 本身并不存储数据，只是解析 SQL，将实际的数据读取请求转发给底层的存储节点 TiKV（或 TiFlash）。

OLAP计算引擎TiSpark

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

TiFlash 和 TiSpark 都允许使用多个主机在 OLTP 数据上执行 OLAP 查询。TiFlash 是列式存储，它提供了更高效的分析查询。TiFlash 和 TiSpark 之间的关系，可类比于 Clickhouse 和 Spark。

分布式协调层：PD

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

PD 不仅存储集群元信息，同时还会根据 TiKV 节点实时上报的数据分布状态，下发数据调度命令给具体的 TiKV 节点，可以说是整个集群的“大脑”。

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

存储引擎层：TiKV/TiFlash

行存储TiKV

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

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

• TiKV 的 API 在 KV 键值对层面提供对分布式事务支持，默认提供了 SI (Snapshot Isolation) 的隔离级别。
• TiDB 的 SQL 层做完 SQL 解析后，会将 SQL 的执行计划转换为对 TiKV API 的实际调用。
• TiKV 支持高可用和自动故障转移，所有数据都会自动维护多副本（默认为三副本）。

列存储TiFlash

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

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

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

TiFlash 可以兼容 TiDB 与 TiSpark 两种计算引擎，TiDB 适合用于中等规模的 OLAP 计算，而 TiSpark 适合大规模的 OLAP 计算。

TiDB计算引擎

SQL层架构

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

1. 用户发起请求：数据库客户端向指定的 TiDB 集群发起请求。
2. 目标数据库响应：TiDB 集群指定 TiDB 节点响应用户的请求。
3. 两者建立会话：TiDB 集群其中一个 TiDB Server 节点与客户端建立会话。
4. 对象请求解析：TiDB Server 节点对接收到的请求进行语法检查、词法分析、对象解析，并将其转换为关系代数结构，然后完成执行计划优化。
5. 调度并且执行：TiDB Server 根据 PD 寻找最合适的 TiKV 副本，根据优先级执行 SQL，按照内存、缓存、数据快照、磁盘存储的顺序查询。
6. 监测任务状态：TiDB Server 监测执行中任务的状态。
7. 返回数据结果：TiDB Server将执行结果返回给数据库客户端。

表数据映射到KV

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

• 为了保证同一张表的数据放在一起，方便查找，TiDB 会为每个表分配一个表 ID，用TableID表示。表 ID 是一个整数，在整个集群内唯一。
• TiDB 会为表中每行数据分配一个行 ID，用RowID表示。行 ID 也是一个整数，在表内唯一。对于行 ID，TiDB 做了一个小优化，如果某个表有整数型的主键，TiDB 会使用主键的值当做这一行数据的行 ID。

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

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

表索引映射到KV

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

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, 10001
2, "TiKV", "KV Engine", 20, 10002
3, "PD", "Manager", 30, 10003

• 表数据映射到KV如下：

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

• 唯一索引映射到KV如下：

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

• 非唯一索引映射到KV如下：

# 假设 IndexID 为 1
t10_i1_10_1 --> null
t10_i1_20_2 --> null
t10_i1_30_3 --> null

TiKV存储引擎

TiKV Region

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

• 一致性哈希（Hash）：按照 Key 做 Hash，根据 Hash 值选择对应的存储节点

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

• 连续分段哈希（Range）：按照 Key 分 Range，某一段连续的 Key 都保存在一个存储节点上

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 API 负责 gRPC KV API 逻辑，Coprocessor API 负责 TiDB 的算子下推计算
• Transaction 负责数据的读写冲突和事务的隔离性
• Raft 负责节点间数据同步，保证数据的安全性
• RocksDB 负责数据的存储

网络层

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

事务层

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

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

• 如果业务依赖于MySQL 事务的行为，可以选择悲观事务模式
• 如果业务冲突较少，则可以选择乐观事务，以获得更高的吞吐量和较低的延迟

事务层提供了快照隔离的特性和事务 ACID 属性中的 ACI（原子性、一致性、隔离性）特性，而 D（持久性）特性由下一层实现。

一致性层

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

TiKV 还扩展了 Raft 算法，并引入了 multi-raft 算法，使数据能够自动分片。通过 multi-raft 算法，每个 Region 的大小可以保持在大约 96MB，而 PD（Placement Driver）则可以通过调度实现水平扩展。

存储层

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

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

• raft 列：存储各个 Region 的元信息，仅占极少量空间。
• lock 列：存储悲观事务的悲观锁，以及分布式事务的一阶段 Prewrite 锁。当分布式事务提交之后，lock cf 中的数据会被快速删除。因此，大部分情况下 lock cf 中的数据也很少（少于 1GB）。
• write 列：存储表数据以及MVCC 信息（该数据所属事务的开始时间以及提交时间）。当用户写入了一行数据时，如果该行数据长度小于 255 字节，那么会被存储write列中，否则该行数据会被存入到default列中。
• default 列：用于存储超过 255 字节长度的数据。

把 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 树的核心思想是顺序 IO 远快于随机 IO，因此适用于写多读少的业务场景。

LSM Tree结构

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

除了TiKV以外，Hbase、Cassandra和MongoDB等NoSQL底层的存储模型用的是LSM。

WAL（预写日志）

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

WAL 是一个只允许追加的文件，包含一组更改记录序列。每个记录包含键值对、记录类型（Put / Merge / Delete）和校验和（checksum）。

Memtable（内存表）

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

跳表：跳表是一种非常简单的链状二分搜索结构，期望时间复杂度 O(log n) ，最坏 O(n)

Immutable Memtable（不可变内存表）

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

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

SSTable

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

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

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

SSTable 的基本组成部分包括：

• 数据：这是存储在 SSTable 中的实际数据。数据被组织成键值对，并且每个键值对都被写入到磁盘中。
• 索引：除了数据，SSTable 还包含一个索引，这个索引用于快速查找数据。索引包含了所有键的列表，以及每个键在数据中的位置。
• 元数据：SSTable还包含一些元数据，如创建时间、最后修改时间等。

SSTable 的优点包括：

• 数据的有序性：SSTable 中的数据是有序的，这使得查找数据变得非常快速。
• 数据的持久性：SSTable 中的数据被写入到磁盘中，因此即使在系统重启后，数据也不会丢失。
• 数据的压缩：SSTable 中的数据被压缩，这使得存储的数据量更小，提高了存储效率。
• 数据的恢复：SSTable 中的数据可以被恢复，这使得数据库的备份和恢复变得非常简单。

RocksDB写操作

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

1. 写入时首先写WAL 日志文件，方便进程闪崩时可以根据日志快速恢复。
2. 将请求写入到内存中的跳表 SkipList 即Memtable中，立即返回给客户端。当 Memtable 写满后，将其转换成Immutable Memtable，并切换到新的 Memtable 提供写入。
3. RocksDB 在后台会通过一个flush 进程将这个 Memtable 刷新到磁盘，生成一个Sorted String Table(SST)文件，放在Level 0 层，删除对应的 WAL 日志。L0 层的文件，是由内存中的 Memtabledump到磁盘上生成的，单个文件内部按 key 有序，文件之间无序，而L1 ~ L6 层的文件都是按照 key 有序；
4. 当Level 0 层的 SST 文件个数超过阈值之后，就会通过Compaction 策略将其放到Level 1 层，以此类推。每一层的数据是上一层的10 倍（因此90%的数据存储在最后一层）。

RocksDB读操作

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

1. 首先在Memtable中查找指定的 key，如果查到符合条件的数据，结束查找。
2. 然后在Immutable Memtable中查找指定的 key，如果查到符合条件的数据，结束查找。
3. 按低层至高层的顺序，从level 0层到level 1层的SST文件中查找指定的 key，如果查到符合条件的数据，结束查找，否则返回 Not Found 错误。

Compaction操作

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

• Insert 操作：直接写入新的 KV
• Update 操作：写入修改后的 KV
• Delete 操作：写入一条tombstone 标记删除的记录

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

1. 大量的冗余和无效数据占用磁盘空间，造成空间放大。
2. 如果在内存中没有读取到数据，需要从L0层开始查找SST文件，造成读放大。

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

Compaction的机制

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

1. 层级越高说明其数据写入越早，即先往上层进行 “放”（minor compaction），上层 “满”（达到容量限制）之后“溢”（major compaction）到下层进行合并。
2. 每层文件总大小都有限制，层级大小成指数级增长。比如L0 层文件总大小上限为10MB，L1 层为100MB，L21 层为1000MB。依次类推，最下层（L6 层）没有限制。
3. 由于L0 层每个SSTable 文件都是直接由Memtable落盘而来，因此L0 层多个SSTable文件的 key 范围可能会有重合。而其他层（L1 ~ L6）的多个SSTable文件，则通过一些规则保证没有重合。

Compaction的作用

1. 数据持久化：将内存中的数据持久化到磁盘中的 SSTable 文件
2. 提高读写效率：将L0层的 SSTable 文件合并为若干个没有数据重合的L1 ~L6层文件，避免多层无效遍历
3. 平衡读写差异：当L0层SSTable 文件数量过多时，暂停写入操作，直到 compaction 完成为止
4. 节约磁盘空间：同一个 key 可能存在着多条数据，对不同版本进行合并可以节省磁盘空间。

Compaction的类型

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

• Minor Compaction

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

• Major Compaction

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

Major Compaction 的触发条件：

当L0 层SSTable文件数超过预定的上限（默认为4个）

当L(N)层文件的总大小超过(10 ^ i) MB

当某个 SSTable 文件无效读取的次数过多

布隆过滤器（Bloom Filter）

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

• 通过 major compaction 尽量减少 SSTable 文件数
• 使用布隆过滤器，快速判断 key 是否在某个 SSTable 文件中

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

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

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

• 如果位数组中 k 个位置上的位均为 1，则该元素有可能存在
• 如果任意一位置上值为位为0，则该值一定不存在。

布隆过滤器用于快速判断一条数据是否在集合中。其本质上是通过容忍一定的错误率，来换取时空的高效性。

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

结语

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

作者介绍

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