写点什么

TiDB 简述及 TiKV 的数据结构与存储 | 京东物流技术团队

  • 2023-07-10
    北京
  • 本文字数:5817 字

    阅读完需:约 19 分钟

TiDB简述及TiKV的数据结构与存储 | 京东物流技术团队

1 概述

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 中的每行记录是如何在内存和磁盘中进行存储的。

2 组件

先看一张 Tidb 的架构图,里面包含 TiDB、Storage(TiKV、TiFlash)、TiSpark、PD。其中的 TiDB、TiKV、PD 是核心组件;TIFlash、TiSpark 是为了解决复杂 OLAP 的组件。


TiDB 是 Mysql 语法的交互入口,TiSpark 是 sparkSAL 的交互入口。



2.1 TiDB Server

SQL 层,对外暴露 MySQL 协议的连接 endpoint,负责接受客户端的连接,执行 SQL 解析和优化,最终生成分布式执行计划。


TiDB 层本身是无状态的,实践中可以启动多个 TiDB 实例,通过负载均衡组件(如 LVS、HAProxy 或 F5)对外提供统一的接入地址,客户端的连接可以均匀地分摊在多个 TiDB 实例上以达到负载均衡的效果。TiDB Server 本身并不存储数据,只是解析 SQL,将实际的数据读取请求转发给底层的存储节点 TiKV(或 TiFlash)。

2.2 PD (Placement Driver) Server

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


PD 不仅存储元信息,同时还会根据 TiKV 节点实时上报的数据分布状态,下发数据调度命令给具体的 TiKV 节点,可以说是整个集群的“大脑”。此外,PD 本身也是由至少 3 个节点构成,拥有高可用的能力。建议部署奇数个 PD 节点。

2.3 存储节点

2.3.1 TiKV Server

负责存储数据,从外部看 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 中的数据都会自动维护多副本(默认为三副本),天然支持高可用和自动故障转移。

2.3.2 TiFlash

TiFlash 是一类特殊的存储节点。和普通 TiKV 节点不一样的是,在 TiFlash 内部,数据是以列式的形式进行存储,主要的功能是为分析型的场景加速。假如使用场景为海量数据,且需要进行统计分析,可以在数据表基础上创建 TiFlash 存储结构的映射表,以提高查询速度。


以上组件互相配合,支撑着 Tidb 完成海量数据存储、同时兼顾高可用、事务、优秀的读写性能。

3 存储架构

3.1 TiKV 的模型

前文所描述的 Tidb 架构中,其作为存储节点的有两个服务,TiKV 和 TiFlash。其中 TiFlash 为列式存储的形式实现的,可以参考 ClickHouse 的架构思路,二者具有相似性。本章节主要讨论 TiKV 的实现。



在上图中,TiKV node 所描述的就是 OLTP 场景下 Tidb 的存储组件,而 TiFlash 则是应对的 LOAP 场景。TiKV 选择的是 Key-Value 模型,作为数据的存储模型,并提供有序遍历方法进行读取。


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


  1. 是一个巨大的 Map(可以参考 HashMap),也就是存储的是 Key-Value Pairs(键值对)。

  2. 这个 Map 中的 Key-Value pair 按照 Key 的二进制顺序有序,也就是可以 Seek 到某一个 Key 的位置,然后不断地调用 Next 方法,以递增的顺序获取比这个 Key 大的 Key-Value。


需要注意的是,这里描述的 TiKV 的 KV 存储模型,与 SQL 中的 Table 无关,不要有任何代入。


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

3.2 TiKV 的行存储结构

在使用 Tidb 时,依然以传统“表”的概念进行读写,在关系型数据库中,一个表可能有很多列。而 Tidb 是以 Key-Value 形式构造数据的,因此需要考虑,将一行记录中,各列数据映射成一个 key-value 键值对。


首先,在 OLTP 场景,有大量针对单行或者多行的增、删、改、查操作,要求数据库具备快速读取一行数据的能力。因此,对应的 Key 最好有一个唯一 ID(显示或隐式的 ID),以方便快速定位。


其次,很多 OLAP 型查询需要进行全表扫描。如果能够将一个表中所有行的 Key 编码到一个区间内,就可以通过范围查询高效完成全表扫描的任务。

3.2.1 表数据的 KV 映射

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 的聚集索引。

3.2.2 索引数据的 KV 映射

对于普通索引,在 MySQL 中是有非聚集索引概念的,尤其 innodb 中,通过 B+Tree 形式,子节点记录主键信息,再通过回表方式得到结果数据。


在 Tidb 中是支持创建索引的,那么索引信息如何存储? 它同时支持主键和二级索引(包括唯一索引和非唯一索引),且与表数据映射方式类似。


设计如下:


  • Tidb 为表中每个索引,分配了一个索引 ID,用 IndexID 表示。

  • 对于主键和唯一索引,需要根据键值快速定位到 RowID,这个会存储到 value 中


因此生成的 key-value 键值对为:


Key:tablePrefix{TableID}_indexPrefixSep{IndexID}_indexedColumnsValueValue: RowID
复制代码


由于设计的 key 中存在 indexedColumnsValue,也就是查询的字段值,因此可以直接命中或模糊检索到。再通过 value 中的 RowID,去表数据映射中,检索到 RowID 对应的行记录。


对于普通索引,一个键值可能对应多行,需要根据键值范围查询对应的 RowID。


Key:   tablePrefix{TableID}_indexPrefixSep{IndexID}_indexedColumnsValue_{RowID}Value: null
复制代码


根据字段值,可以检索到具有相关性的 key 的列表,在根据 key 中包含的 RowID,再拿到行记录。

3.2.3 映射中的常量字符串

上述所有编码规则中的 tablePrefix、recordPrefixSep 和 indexPrefixSep 都是字符串常量,用于在 Key 空间内区分其他数据,定义如下:


tablePrefix     = []byte{'t'}recordPrefixSep = []byte{'r'}indexPrefixSep  = []byte{'i'}
复制代码


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


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

3.2.4 举例

假设数据库的一张表,如下:


CREATE TABLE User (    ID int,    Name varchar(20),    Role varchar(20),    Age int,    PRIMARY KEY (ID),    KEY idxAge (Age));
复制代码


表中有 3 行记录:


1, "TiDB", "SQL Layer", 102, "TiKV", "KV Engine", 203, "PD", "Manager", 304, "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 --> nullt10_i1_20_2 --> nullt10_i1_30_3 --> nullt10_i1_30_4 --> null
复制代码

3.3 SQL 与 KV 映射

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


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


  1. 根据表名、所有的 RowID,结合表数据的 Key 编码规则,构造出一个[StartKey,endKey)的左闭右开区间。

  2. 根据[StartKey,endKey)这个区间内的值,到 TiKV 中读取数据

  3. 得到每一行记录后,过滤出 name=’tidb’的数据

  4. 将结果进行统计,计算出 count(*)的结果,进行返回。



在分布式环境下,为了提高检索效率,实际运行过程中,上述流程是会将 name=’tidb’和 count( *)下推到集群的每个节点中,减少无异议的网络传输,每个节点最终将 count( *)的结果,再由 SQL 层将结果累加求和。

4 RockDB 持久化

4.1 概述

前文所描述的 Key-Value Pairs 只是存储模型,是存在于内存中的,任何持久化的存储引擎,数据终归要保存在磁盘上。TiKV 没有选择直接向磁盘上写数据,而是把数据保存在 RocksDB 中,具体的数据落地由 RocksDB 负责。


这个选择的原因是开发一个单机存储引擎工作量很大,特别是要做一个高性能的单机引擎,需要做各种细致的优化,而 RocksDB 是由 Facebook 开源的一个非常优秀的单机 KV 存储引擎,可以满足 TiKV 对单机引擎的各种要求。这里可以简单的认为 RocksDB 是一个单机的持久化 Key-Value Map。

4.2 RocksDB

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



以 Region 为单元,是基于顺序 I/O 的性能考虑的。而 TiKV 是如何有效的组织 Region 内的数据,保证分片均匀、有序,这里面用到了 LSM-Tree,如果有 HBase 经验一定不模式。

4.2.1 LSM-Tree 结构

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 文件。

4.2.2 LSM-Tree 执行过程

写入过程


  1. 首先会检查每个区域的存储是否达到阈值,未达到会直接写入;

  2. 如果 Immutable Memory-Table 存在,会等待其压缩过程。

  3. 如果 Memory-Table 已经写满,Immutable Memory-Table 不存在,则将当前 Memory-Table 设置为 Immutable Memory-Table,生成新的 Memory-Table,再触发压缩,随后进行写入。

  4. 写的过程会先写入 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+树一样,在磁盘中的找到相应的数据后再删除。


  1. 首先会在通过查找流程,在 Memory-Table、Immuatble Memory-Table 中进行查找。

  2. 如果找到则对结果标记为“删除”。

  3. 否则会在结尾追加一个节点,并标记为“删除”

  4. 在真正删除前,未来的查询操作,都会先找到这个被标记为“删除”的记录。

  5. 之后会在某一时刻,通过压缩过程真正删除它。


更新操作和删除操作类似,都是只操作内存区域的结构,写入一个标志,随后真正的更新操作被延迟在合并时一并完成。由于操作是发生在内存中,其读写性能也能保障。

4.3 RockDB 的优缺点

优点


  1. 将数据拆分为几百 M 大小的块,然后顺序写入

  2. 首次写入的目的地是内存,采用 WAL 设计思路,加上顺序写,提高写入的能力,时间复杂度近似常数

  3. 支持事务,但 L0 层的数据,key 的区间有重叠,支持较差


缺点


  1. 读写放大严重

  2. 应对突发流量的时候,削峰能力不足

  3. 压缩率有限

  4. 索引效率较低

  5. 压缩过程比较消耗系统资源,同时对读写影响较大

5 总结

以上针对 TiDB 的整体架构进行建单介绍,并着重描述了 TiKV 是如何组织数据、如何存储数据。将其 Key-Value 的设计思路,与 MySQL 的索引结构进行对比,识别相似与差异。TiDB 依赖 RockDB 实现了持久化,其中的 Lsm-Tree,作为 B+Tree 的改进结构,其关注中心是“如何在频繁的数据改动下保持系统读取速度的稳定性”,以顺序写磁盘作为目标,假设频繁地对数据进行整理,力求数据的顺序性,带来读性能的稳定,同时也带来了一定程度的读写放大问题。


作者:京东物流 耿宏宇

来源:京东云开发者社区 自猿其说 Tech

发布于: 刚刚阅读数: 4
用户头像

拥抱技术,与开发者携手创造未来! 2018-11-20 加入

我们将持续为人工智能、大数据、云计算、物联网等相关领域的开发者,提供技术干货、行业技术内容、技术落地实践等文章内容。京东云开发者社区官方网站【https://developer.jdcloud.com/】,欢迎大家来玩

评论

发布
暂无评论
TiDB简述及TiKV的数据结构与存储 | 京东物流技术团队_数据库_京东科技开发者_InfoQ写作社区