万字长文 深化浅出讲遣散布式数据库TiDB架构设计

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继续集成平台技术担任人，主导外围业务方案设计落地，推进产品架构继续演进。