AI 日报

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

  • By 51ITO
  • May 20, 2024 - 2 min read



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 层 的文件，是由内存中的 Memtable dump 到磁盘上生成的，单个 文件内部 按 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清理算法、一些巧妙数据结构，仍需大家深入研究方可融会贯通，活学活用。

作者介绍

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